《《一种基于生物数据的多层关联规则挖掘算法论文》-公开DOC·毕业论文》由会员分享，可在线阅读，更多相关《《一种基于生物数据的多层关联规则挖掘算法论文》-公开DOC·毕业论文（66页珍藏版）》请在金锄头文库上搜索。
1、分分 类类 号号 学学 号号 2004611700092 学校代码学校代码10487 密密 级级 硕硕士士学学位位论论文文 一种基于生物数据的多层关联规则一种基于生物数据的多层关联规则 挖掘算法挖掘算法 学位申请人 学位申请人 学学科科专专 业 计算机软件与理论业 计算机软件与理论 指指导导教教 师 师 教授教授 答答辩辩日日 期 期 2007 年年 6 月月 2 日日 A Thesis Submitted in fulfillment of the Requirements for the Degree of Master of Engineering An Algorithm for Mi
2、ning Biological Data Multilevel Association Rules Candidate Zhang Ping Major Computer Software and Theory Supervisor Prof Lu Yansheng Huazhong University of Science but existing algorithms still have some shortcomings The proposed algorithms for mining multilevel association rules such as Cumulate a
3、lgorithm and ML T2L1 algorithm are based on Apriori algorithm These algorithms still adopt candidate generate and test method to get frequent patterns which cause large cost in computing and I O so they are inefficient Improved from FP Growth algorithm MAGO FP an optimized data mining technique to d
4、iscover the multilevel association rules from gene expression data and the concept hierarchy of Gene Ontology GO has been proposed The following measures are applied to expand FP Growth algorithm 1 Expanding every transaction by adding all ancestors of each item during the process of scanning the da
5、tabase This measure ensures that we can get multilevel association rules 2 Deleting the ancestors that are not frequent items in time to compress search space and enhance the efficiency of mining 3 Avoiding generating redundant frequent patterns The multilevel association rules mining algorithm can
6、figure out the relations between GO terms by summarizing the genes with the hierarchy of GO An experiment showed that MAGO FP algorithm got the same result as Cumulate algorithm did and inherited the strongpoint of high efficiency of FP Growth algorithm A data set of 300 expression profiles for yeas
7、t has been analyzed using the algorithm we found numerous rules in the data A cursory analysis of some of these rules reveals numerous associations between certain genes many of which made sense biologically others suggesting new hypotheses that may worth of being further investigated The algorithm
8、could be used to analyze gene expression profiles and uncover gene networks Key words Data Mining Multilevel Association Rules Gene Ontology MAGO FP Algorithm 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 II 目目 录录 摘 要 I Abstract II 1 绪 论 1 1 研究背景与意义 1 1 2 关联规则挖掘研究进展 2 1 3 生物数据关联规则挖掘的基本步骤 11 1 4 论文组织结构 14 2 关联
9、规则挖掘算法 2 1 关联规则的定义和相关概念 15 2 2 两种经典的关联规则挖掘算法 17 2 3 多层关联规则的定义和相关概念 25 2 4 两种经典的多层关联规则挖掘算法 28 2 5 小结 31 3 GENE ONTOLOGY 结构下优化的多层关联规则挖掘算法 3 1 基于 APRIORI 算法的多层关联规则挖掘算法的局限性 32 3 2 基因本体论 GENE ONTOLOGY 及其概念分层结构 32 3 3 MAGO FP 算法 39 3 4 小结 44 4 MAGO FP 算法的实验分析 4 1 实验平台与过程 45 4 2 性能优势分析 45 华华 中中 科科 技技 大大 学学
10、 硕硕 士士 学学 位位 论论 文文 III 4 3 实验结果与分析 46 4 4 小结 48 5 结 论 50 致 谢 51 参考文献 52 附录 1 攻读学位期间发表论文目录 60 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 0 1 绪绪 论论 1 1 研究背景与意义研究背景与意义 生命科学近年来获得突破性进展 1 随着生物学和医学的迅速发展 生物数据 呈指数级增长 无论是在数量上还是在质量上都极大的丰富了生命科学的数据资源 提供了揭开生命奥秘的数据基础 然而生物数据种类丰富 高通量 维数高 本质 上具有异质性与网络性 远远超出传统的分析方法的能力和速度 其处理
11、 挖掘 分析和理解日益迫切 如何分析这些具有丰富内涵的数据并从中获得关生物结构和 功能的信息 从中得到对人类有益的信息 是生物研究的瓶颈 是当前研究所面临 的一个严峻挑战 生物信息学是在此背景下发展起来的综合运用生物学 数学 信 息学以及计算机科学等诸多学科理论方法的崭新交叉学科 是在生命科学的研究中 以计算机科学知识为辅导工具对生物信息进行储存 检索和分析的科学 是当今生 命科学和自然科学的重大前沿领域之一 它包含两方面的内容 一方面是对海量数 据的搜索 管理 服务 即 管好数据 另一方面从中发现规律 即 读懂 数 据 随着人类基因组计划的完成 生物信息学的研究重点已经从开始的序列分析 数据
12、库查询逐渐向生物信息的挖掘 表达 数据多样性分析的方向发展 高通量实 验数据分析成为目前生物信息学研究的热点和重点 这些数据是通过一些高通量实 验测量技术得到的 往往包含着几千个基因或基因片断和几十个属性 高通量实验 数据 无论是转录水平上还是蛋白质水平上 其中都蕴含着丰富的生物学知识 可 以帮助我们理解基因 理解生物 理解细胞等等 例如某疾病是由什么基因引起的 细胞是处于正常还是恶化状态 药物对肿瘤细胞是否有效等 由于越来越多数据得 以公开 人们迫切希望通过数据挖掘技术在这些具有丰富内涵的海量数据中获得有 益的信息 对高通量实验数据的分析可以获取基因功能和基因表达调控信息 这是 生物信息学的
13、重大挑战之一 也是基因组学 蛋白质组学的相关实验技术能够在生 物医学领域中广泛应用的关键原因之一 它们在医学临床诊断 药物疗效判断 揭 示疾病发生机制等方面有重要的应用 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 1 数据挖掘 2 是新兴的一种科学计算技术与数据分析方法 它能够有效地从存有 海量信息的数据库中提取隐含的 事先未知的潜在的和有用的信息和知识 经过多 年的研究与发展 它已经成为一项很重要的数据分析工具 作为一种以数据库 统 计学和人工智能学为基础的新兴技术 数据挖掘给基因组学家们提供了前所未有的 数据分析工具 为基因和蛋白信息的分析和提取提供了强有力的手
14、段 生物信息学 数据挖掘两者的结合 不论是现在还是将来 不论在理论上还是应用上都具有十分 重要的意义 因此生物数据挖掘日益重要 逐渐成为生物信息学研究领域的关键 数据挖掘的常用技术中 聚类和分类技术已经成为基因鉴定 功能预测和基因 表达分析等研究中最常用的手段 而关联规则挖掘技术 作为分析海量数据库中项 目间相关联系的重要技术 目前在生物学领域中并未得到广泛应用 相应的算法也 不够成熟 与数据挖掘的其他技术相比 关联规则更能挖掘出基因间的网络结构 因为聚类和分类技术只能显示数据中基因群普遍的表现形式 而关联规则的频繁模 式集不但可以显示出表现形式 其所产生的推论规则更可以描述基因间的联系 另
15、外还有支持度和置信度参数可供生物学家作评价标准 同时 关联规则能有效的克 服聚类等分析技术只能将基因分到某一群 往往忽略了基因可能同时参与几个生化 路径的缺点 但是 目前的生物数据关联规则挖掘算法仍然存在着挖掘结果缺乏很 强的生物学意义 候选规则冗余度高和挖掘计算效率低等不足 迫切需要针对生物 数据的特殊性建立适用的关联规则挖掘算法 本研究拟选用 Gene Ontology 完善的概念层次结构 3 通过对 FP Growth 算法 4 进行扩展 期望实现一种优化的生物数据多层关联规则挖掘算法 能有效地克服传 统的 基于 Apriori 5 的多层关联规则挖掘算法的缺点 大幅提高挖掘效率 并且保
16、 证挖掘结果具有良好的生物学意义 因此 拟提出的新算法预期在基因表达分析 基因调控网络等研究中具有广泛的应用价值 1 2 关联规则挖掘研究进展关联规则挖掘研究进展 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系 它是数据挖 掘中的一个重要问题 其研究目标是找出满足最小支持度和最小可信度要求的关联 规则 关联规则是形如 AB 的蕴涵式 其中 A B 都是项集 一般地 关联规则发 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 2 现分为找出所有的频繁项集和由频繁项集产生强关联规则两个步骤 其中找出所有 的频繁项集是关联规则算法的性能瓶颈 因此绝大部分对关联规则算法的研究都集 中在第一步 即如何在保证精度的基础上提高算法的运行效率 其中精度是指所找 出的频繁项集的满足要求的程度 1993 年 Agrawal 等提出了关联规则发现问题 6 同时提出了第一个频繁项集 发现算法 此后 在各种问题背景下 围绕着提高算法效率和结果的有用性 即用 户对其感兴趣程度 研究者们提出了各种频繁项集发现算法 7 8 根据这些算法的 研究重点不同 可将其分为基本频繁项集发现算法
