华中科技大学硕士学位论文PAGEII硕士学位论文一种基于生物数据的多层关联规则挖掘算法AThesisSubmittedinfulfillmentoftheRequirementsfortheDegreeofMasterofEngineeringAnAlgorithmforMiningBiologicalDataMultilevelAssociationRulesCandidate:ZhangPingMajor:ComputerSoftwareandTheorySupervisor:Prof.LuYanshengHuazhongUniversityofScience&TechnologyWhuhan430074,P.R.ChinaJune,2007独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于保密□，在_____年解密后适用本授权书。不保密□。（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日摘要数据挖掘是从大量数据中发现潜在的、有趣的知识的过程，是解决“数据丰富，知识贫乏”状况的有效方法。关联规则挖掘用于从大量数据中揭示项集之间的有趣关联或相关联系，是数据挖掘的一项重要研究内容，在现实生活中有着广泛的应用。研究表明，关联规则挖掘技术是寻找基因间关系的有效手段；但现有算法未针对高通量生物数据的特点进行优化，而存在着效率低下、规则缺乏生物学意义等缺点。与单层关联规则挖掘相比，多层关联规则能够提供更加丰富、更具普遍意义的知识；选用合理的概念层次结构与多层关联规则挖掘算法，能够更好的适应生物数据挖掘的需要。已有的多层关联规则挖掘算法如Cumulate算法、ML_T2L1算法，都是通过对Apriori算法进行扩展得到的。这些算法仍采用候选生成并验证的方式得到频繁模式，导致了巨大的计算和I/O开销，使得效率较低。选用GeneOntology完善的概念层次结构，通过对FP_Growth算法进行扩展，获得了一种优化的生物数据多层关联规则挖掘算法MAGO-FP。MAGO-FP算法采用的扩展措施如下：(1)在扫描数据库的过程中通过把每个项的全部祖先加入到事务中对每条事务进行扩充，该措施能够确保得到多层关联规则；(2)通过及时删除概念层次树中不是频繁项的祖先项来压缩搜索空间，提高挖掘效率；(3)避免产生冗余的频繁模式。性能实验表明MAGO-FP算法是正确的，并继承了FP_Growth算法运行效率高的优点。应用MAGO-FP算法分析了一组由S.cerevisiae酵母菌cDNA微阵列芯片产生的实验数据，发现了一些候选关联规则。并针对其中一些重要的关联规则，通过相关文献证实了其真实性，表明该算法在基因表达分析、基因调控网络等研究中具有一定的应用价值。关键词：数据挖掘，多层关联规则，基因本体论，MAGO-FP算法AbstractDataminingisaprocesstoreveallatentandinterestingknowledgefrommassivedata,andaneffectiveapproachtosolvetheproblemof"richdataandpoorknowledge".Associationrulesminingcanrevealinterestingcorrelationsamongitemsetsfrommassivedata.Itisanimportantsubjectofdataminingandiswidelyusedinreallife.Recentstudieshaveprovedthatassociationrulescanrevealtheinteractionsbetweengenes,showingpatternsthatmaynothavebeenidentifiedusingtraditio