《一种基于生物数据的多层关联规则挖掘算法.docx》由会员分享，可在线阅读，更多相关《一种基于生物数据的多层关联规则挖掘算法.docx（67页珍藏版）》请在金锄头文库上搜索。
1、分 类 号学 号2004611700092学校代码10487密 级硕士学位论文一种基于生物数据的多层关联规则挖掘算法学位申请人：张平学 科 专 业：计算机软件与理论指 导 教 师：卢炎生 教授答 辩 日 期：2007 年 6 月 2 日A Thesis Submitted in fulfillment of the Requirements forthe Degree of Master of EngineeringAn Algorithm for Mining Biological DataMultilevel Association RulesCandidate : Zhang PingM
2、ajor: Computer Software and TheorySupervisor : Prof. Lu YanshengHuazhong University of Science & TechnologyWhuhan 430074, P.R.ChinaJune, 2007独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学
3、位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密 ，在_年解密后适用本授权书。本论文属于不保密。（请在以上方框内打“”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日摘要数据挖掘是从大量数据中发现潜在的、有趣的知识的过程，是解决“数据丰富，知识贫乏”状况的有效方法。关联规则挖掘用于从大量数据中揭示项集之间的有趣关联或相关联系，是数据挖掘的
4、一项重要研究内容，在现实生活中有着广泛的应用。研究表明，关联规则挖掘技术是寻找基因间关系的有效手段；但现有算法未针对高通量生物数据的特点进行优化，而存在着效率低下、规则缺乏生物学意义等缺点。与单层关联规则挖掘相比，多层关联规则能够提供更加丰富、更具普遍意义的知识；选用合理的概念层次结构与多层关联规则挖掘算法，能够更好的适应生物数据挖掘的需要。已有的多层关联规则挖掘算法如 Cumulate 算法、ML_T2L1 算法，都是通过对 Apriori 算法进行扩展得到的。这些算法仍采用候选生成并验证的方式得到频繁模式，导致了巨大的计算和 I/O 开销，使得效率较低。选用 Gene Ontology 完
5、善的概念层次结构，通过对 FP_Growth 算法进行扩展，获得了一种优化的生物数据多层关联规则挖掘算法 MAGO-FP。MAGO-FP 算法采用的扩展措施如下：(1)在扫描数据库的过程中通过把每个项的全部祖先加入到事务中对每条事务进行扩充，该措施能够确保得到多层关联规则；(2)通过及时删除概念层次树中不是频繁项的祖先项来压缩搜索空间，提高挖掘效率；(3)避免产生冗余的频繁模式。性能实验表明 MAGO-FP 算法是正确的，并继承了 FP_Growth 算法运行效率高的优点。应用 MAGO-FP 算法分析了一组由 S.cerevisiae 酵母菌 cDNA 微阵列芯片产生的实验数据，发现了一些候
6、选关联规则。并针对其中一些重要的关联规则，通过相关文献证实了其真实性，表明该算法在基因表达分析、基因调控网络等研究中具有一定的应用价值。关键词：数据挖掘，多层关联规则，基因本体论，MAGO-FP 算法IAbstractData mining is a process to reveal latent and interesting knowledge from massivedata, and an effective approach to solve the problem of rich data and poor knowledge.Association rules mining c
7、an reveal interesting correlations among item sets frommassive data. It is an important subject of data mining and is widely used in real life.Recent studies have proved that association rules can reveal the interactions betweengenes, showing patterns that may not have been identified using traditio
8、nal clusteringmethods; but existing algorithms still have some shortcomings. The proposed algorithmsfor mining multilevel association rules, such as Cumulate algorithm and ML_T2L1algorithm, are based on Apriori algorithm. These algorithms still adopt candidategenerate and test method to get frequent
9、 patterns which cause large cost in computingand I/O; so they are inefficient.Improved from FP_Growth algorithm, MAGO-FP, an optimized data miningtechnique to discover the multilevel association rules from gene expression data and theconcept hierarchy of Gene Ontology (GO) has been proposed. The fol
10、lowing measuresare applied to expand FP-Growth algorithm: (1) Expanding every transaction by addingall ancestors of each item during the process of scanning the database. This measureensures that we can get multilevel association rules; (2) Deleting the ancestors that arenot frequent items in time t
11、o compress search space and enhance the efficiency of mining;(3) Avoiding generating redundant frequent patterns. The multilevel association rulesmining algorithm can figure out the relations between GO terms by summarizing thegenes with the hierarchy of GO. An experiment showed that MAGO-FP algorit
12、hm got thesame result as Cumulate algorithm did and inherited the strongpoint of high efficiency ofFP_Growth algorithm.A data set of 300 expression profiles for yeast has been analyzed; using the algorithm,we found numerous rules in the data. A cursory analysis of some of these rules revealsnumerous
13、 associations between certain genes, many of which made sense biologically,others suggesting new hypotheses that may worth of being further investigated. Thealgorithm could be used to analyze gene expression profiles and uncover gene networks.Key words: Data Mining, Multilevel Association Rules, Gene Ontology, MAGO-FPAlgorithmII目录摘要. IAbstract .
