一种基于生物数据的多层关联规则挖掘算法_硕士学位论文.doc

硕硕士士学学位位论论文文 一种基于生物数据的多层关联规则一种基于生物数据的多层关联规则 挖掘算法挖掘算法 a thesis submitted in fulfillment of the requirements for the degree of master of engineering an algorithm for mining 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 algorithm 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 discover 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 database. 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 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 yeast 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 could be used to analyze gene expression profiles and uncover gene networks. key words: data mining, multilevel association rules, gene ontology, mago-fp algorithm 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 iii 目目 录录 摘 要.i abstractii 1 绪 论 1.1 研究背景与意义.(1) 1.2 关联规则挖掘研究进展.(2) 1.3 生物数据关联规则挖掘的基本步骤.(11) 1.4 论文组织结构.(14) 2 关联规则挖掘算法 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) 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 iv 4.3 实验结果与分析.(46) 4.4 小结.(48) 5 结 论 .(50) 致 谢 .(51) 参考文献 .(52) 附录 1（攻读学位期间发表论文目录） (60) 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 1 1 绪绪 论论 1.1 研究背景与意义研究背景与意义 生命科学近年来获得突破性进展1，随着生物学和医学的迅速发展，生物数据 呈指数级增长，无论是在数量上还是在质量上都极大的丰富了生命科学的数据资源， 提供了揭开生命奥秘的数据基础。然而生物数据种类丰富，高通量，维数高，本质 上具有异质性与网络性，远远超出传统的分析方法的能力和速度，其处理、挖掘、 分析和理解日益迫切。如何分析这些具有丰富内涵的数据并从中获得关生物结构和 功能的信息，从中得到对人类有益的信息，是生物研究的瓶颈，是当前研究所面临 的一个严峻挑战。生物信息学是在此背景下发展起来的综合运用生物学、数学、信 息学以及计算机科学等诸多学科理论方法的崭新交叉学科，是在生命科学的研究中, 以计算机科学知识为辅导工具对生物信息进行储存、检索和分析的科学，是当今生 命科学和自然科学的重大前沿领域之一。它包含两方面的内容，一方面是对海量数 据的搜索、管理、服务，即“管好数据” ；另一方面从中发现规律，即“读懂”数 据。 随着人类基因组计划的完成，生物信息学的研究重点已经从开始的序列分析、 数据库查询逐渐向生物信息的挖掘、表达、数据多样性分析的方向发展，高通量实 验数据分析成为目前生物信息学研究的热点和重点。这些数据是通过一些高通量实 验测量技术得到的，往往包含着几千个基因或基因片断和几十个属性。高通量实验 数据，无论是转录水平上还是蛋白质水平上，其中都蕴含着丰富的生物学知识，可 以帮助我们理解基因、理解生物、理解细胞等等，例如某疾病是由什么基因引起的、 细胞是处于正常还是恶化状态、药物对肿瘤细胞是否有效等。由于越来越多数据得 以公开，人们迫切希望通过数据挖掘技术在这些具有丰富内涵的海量数据中获得有 益的信息。对高通量实验数据的分析可以获取基因功能和基因表达调控信息，这是 生物信息学的重大挑战之一，也是基因组学、蛋白质组学的相关实验技术能够在生 物医学领域中广泛应用的关键原因之一，它们在医学临床诊断、药物疗效判断、揭 示疾病发生机制等方面有重要的应用。 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 2 数据挖掘2是新兴的一种科学计算技术与数据分析方法，它能够有效地从存有 海量信息的数据库中提取隐含的、事先未知的潜在的和有用的信息和知识，经过多 年的研究与发展，它已经成为一项很重要的数据分析工具。作为一种以数据库、统 计学和人工智能学为基础的新兴技术，数据挖掘给基因组学家们提供了前所未有的 数据分析工具，为基因和蛋白信息的分析和提取提供了强有力的手段。生物信息学、 数据挖掘两者的结合，不论是现在还是将来，不论在理论上还是应用上都具有十分 重要的意义。因此生物数据挖掘日益重要，逐渐成为生物信息学研究领域的关键。 数据挖掘的常用技术中，聚类和分类技术已经成为基因鉴定、功能预测和基因 表达分析等研究中最常用的手段。而关联规则挖掘技术，作为分析海量数据库中项 目间相关联系的重要技术，目前在生物学领域中并未得到广泛应用，相应的算法也 不够成熟。与数据挖掘的其他技术相比，关联规则更能挖掘出基因间的网络结构。 因为聚类和分类技术只能显示数据中基因群普遍的表现形式；而关联规则的频繁模 式集不但可以显示出表现形式，其所产生的推论规则更可以描述基因间的联系；另 外还有支持度和置信度参数可供生物学家作评价标准。同时，关联规则能有效的克 服聚类等分析技术只能将基因分到某一群，往往忽略了基因可能同时参与几个生化 路径的缺点。但是，目前的生物数据关联规则挖掘算法仍然存在着挖掘结果缺乏很 强的生物学意义，候选规则冗余度高和挖掘计算效率低等不足，迫切需要针对生物 数据的特殊性建立适用的关联规则挖掘算法。 本研究拟选用 gene ontology 完善的概念层次结构3，通过对 fp_growth 算法4 进行扩展，期望实现一种优化的生物数据多层关联规则挖掘算法：能有效地克服传 统的、基于 apriori5的多层关联规则挖掘算法的缺点，大幅提高挖掘效率；并且保 证挖掘结果具有良好的生物学意义。因此，拟提出的新算法预期在基因表达分析、 基因调控网络等研究中具有广泛的应用价值。 1.2 关联规则挖掘研究进展关联规则挖掘研究进展 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。它是数据挖 掘中的一个重要问题，其研究目标是找出满足最小支持度和最小可信度要求的关联 规则。关联规则是形如 ab 的蕴涵式，其中 a、b 都是项集。一般地,关联规则发 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 3 现分为找出所有的频繁项集和由频繁项集产生强关联规则两个步骤，其中找出所有 的频繁项集是关联规则算法的性能瓶颈。因此绝大部分对关联规则算法的研究都集 中在第一步，即如何在保证精度的基础上提高算法的运行效率，其中精度是指所找 出的频繁项集的满足要求的程度。 1993 年，agrawal 等提出了关联规则发现问题6，同时提出了第一个频繁项集 发现算法。此后，在各种问题背景下，围绕着提高算法效率和结果的有用性（即用 户对其感兴趣程度） ，研究者们提出了各种频繁项集发现算法7,8。根据这些算法的 研究重点不同，可将其分为基本频繁项集发现算法和增强频繁项集发现算法。 基本频繁项集发现算法致力于设计各种算法框架，高效地发现所有支持度大于 某个不变的最小支持度的频繁项集。但是它存在一些缺陷，比如所发现的频繁项集 的有用性不高、发现的频繁项集数量过多、遗漏用户感兴趣的频繁项集等等。 增强频繁项集发现算法致力于提高发现结果的有用性，它通过引入概念层次结 构、约束条件、可变支持度等方式来克服基本频繁项集算法的缺陷。 基本频繁项集发现算法是在单数据库、单概念层次和最基本要求（即使用相同 的最小支持度发现所有频繁项集）的条件下发现频繁项集，它是其它更“高级”频繁 项集发现算法的基础。根据算法提出的时间和算法原理的不同，可将它们细分为 apriori 算法出现之前的算法、apriori 类算法、基于分块的算法、基于采样的算法、 新出现的高性能算法、基于最大频繁项集的算法和频繁封闭项集发现算法等。其中 后三类算法在分析强相关性数据时有明显的性能优势。 1993 年，agrawal 等提出面向单个事务的频繁项集发现算法 ais8。1995 年， houtsma 等提出面向集合的频繁项集发现算法 setm9。这是两种在 apriori 算法出 现之前的算法，它们根据每个事务中的已发现频繁项集和此事务中的其它项生成候 选频繁项集，因此生成的非候选频繁项集数量很多，导致性能在各种情况下都不如 apriori 算法，因此没有得到实际应用。 1994 年，agrawal 等提出简单高效的频繁项集发现算法 apriori5。该算法是基 于广度优先搜索策略的，它利用了频繁项集的反单调性频繁项集的子集必定是 频繁的，通过在第(k-1)次扫描数据库后所得到的长度为(k-1)的频繁项集（简记为(k- 1)-频繁项集，下同）生成 k-候选频繁项集，然后在第 k 次扫描数据库时统计 k-候选 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 4 频繁项集的频繁度。apriori 算法在巨型数据库上有良好性能。但是，由于 apriori 算法使用生成-检验循环的方式发现频繁项集，因此当数据库中频繁项集的密度比较 大或最长频繁项集比较长时，apriori 算法不能避免所生成的候选频繁项集数量的指 数爆炸，导致性能急剧下降；而且 apriori 算法需要多次扫描数据库，造成沉重的 i/o 负担。 agrawal 等还发现，apriori 算法的最大运行时间开销阶段是刚开始的几次生成- 检验循环，特别是发现 2-频繁项集的循环，在此阶段生成了大量无效的候选频繁项 集，限制了算法的效率。 大部分改进的算法把注意力集中在生成大项目集的优化上，主要有四种优化方 法:基于划分的方法，基于 hash 表的方法，减少对交易数据库的遍历次数，基于随 机采样技术的方法。 1995 年 savasere 等设计了一个基于划分原理的 partition 算法10。partition 算法 将原数据库逻辑地分成若干个互不相交的子数据库，其中每个子数据库都充分小， 足以放入内存。由于任何频繁项集至少在其中一个子数据库中是频繁的，所以可先 分别发现每个子数据库中的频繁项集，然后将这些频繁项集汇总作为总候选频繁项 集，再扫描一遍原数据库发现其中满足全局支持度条件的频繁项集。由于每个子数 据库可放入内存，所以发现其中的频繁项集不需要使用非常耗时的 i/o 操作，算法 总体执行速度比较快。另外，partition 算法还是一种本质并行算法。不过，当子数 据库数目增大时，partition 算法生成的无效总候选频繁项集数目快速增长，导致效 率降低，因此 partition 算法在较大数据库上的性能不如 apriori 算法。brin 等提出 dic（动态项集计数）算法，可视为一种串行化的 partition 算法11。 采用哈希修剪技术在快速发现 2-项集的过程中十分有效，park 等在这个方法的 基础上引入哈希技术来改进产生 2-项集的方法，提出 apriori 算法的一种改进 dhp（直接乱散与删剪）算法12。通过使用哈希技术，dhp 比 apriori 算法少生 成一个数量级的 2-候选频繁项集，从而提高了算法性能。另外，由于所生成的 2-候 选频繁项集数量大大减小，所以 dhp 算法可在发现 2-频繁项集之后就从数据库中 删掉无需再考虑的事务和项。 aprioritid 算法13与 apriori 算法的思路基本一致，不同在于：前者在经过一次 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 5 扫描数据库后，不再利用数据库来计算项目集的支持度，而利用候选项集来计算， 因而减少了对交易数据库的遍历次数，提高了效率。 基于采样的技术，是先利用从数据库中抽取出来的采样，生成一些可能的规则， 然后再针对数据库中剩余的部分验证这些规则。toivenen 提出的随机抽样技术14可 以节约相当可观的 i/o 代价，但是一个很大的缺点就是产生的结果不精确，即存在 所谓的数据扭曲(data skew)。分布在同一页面上的数据时常是高度相关的，可能不 能表示整个数据库中模式的分布，由此而导致的是采样 5%的交易数据所花费的代 价可能同扫描一遍数据库相近。lin 和 dunham 讨论了反扭曲(anti-skew)算法来挖 掘关联规则15，他们引入的技术使得扫描数据库的次数少于 2 次。brin 等16提出的 算法使用比传统算法少的扫描遍数来发现频繁项集，同时比基于采样的方法使用更 少的候选集，这些改进了算法在低层的效率。具体的考虑是：在计算 k-项集时，一 旦认为某个(k+1)-项集可能是频繁项集时，就并行地计算这个(k+1)-项集的支持度。 该算法需要的总的扫描次数通常少于最大的频繁项集的项数。这里他们也使用了杂 凑技术，并提出产生“相关规则”（correlation rules）的一个新方法。 zaki 等认为，在频繁项集发现过程中使用采样技术至少可提高一个数量级的速 度，而且精度损失不多17。1996 年，toivonen 提出一种基于采样的频繁项集发现 算法18，其基本思想是对数据库进行采样，形成采样数据库；然后用较小的最小支 持度发现采样数据库中的频繁项集 s；再将 s 和它的负边界 bd(s)合并，构成候选 频繁项集 sbd(s)；接着扫描一遍原数据库从 sbd(s)中发现所有频繁项集 s/：如果其中 bd(s)包含频繁项集，那么说明原数据库中可能存在还未被发现的频 繁项集，这时需要用公式 s/=s/bd(s/)叠代计算直到 s/不再增大，然后将 s/作为 候选集再扫描一遍原数据库，发现所有被遗漏的频繁项集。此算法在一般情况下只 需扫描数据库一次，在最差情况下需要扫描两次。1997 年，park 等提出两个可调节 精度的算法 ds 和 sh19。其中 ds 算法可视为 dhp 算法加入采样技术之后的推广。 ds 和 sh 算法可用于为了提高效率而允许损失一些精度的场合。 apriori 类算法在数据库为高密度、长模式或低支持度等情况下性能急剧下降， 针对这个问题，一些新的高性能频繁项集发现算法被提出来。 2000 年，agarwal 等提出一种全新的高效算法 treeprojection20,21。此算法构造 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 6 一个词典树，并根据已发现的频繁项集，将数据库投影到一组精简的子数据库上。 由于词典树提升了检验候选频繁项集的效率，并且此算法还使用其它各种提高效率 的技术，所以 treeprojection 算法比 apriori 算法的性能高一个数量级。 2000 年，han 等提出一种不需要生成候选频繁项集的算法 fp_growth4。此算 法是基于深度优先搜索策略的：首先扫描两遍数据库，生成信息高度压缩的高频模 式树，该树中仍保留了项集的关联信息；然后在其上递归生成条件高频模式树，同 时找出所有频繁项集。由于此算法不需要生成候选频繁项集，避免了 apriori 类算 法本质具有的候选频繁项集数量指数爆炸情况，对于挖掘长的和短的频繁模式，它 是有效和可伸缩的，并且大约比 apriori 算法快一个数量级。但 apriori 算法对空间 的需求比较低，对数据库规模的伸缩性要好于 fp_growth 算法。两者各有所长。 如果一个频繁项集不是其它频繁项集的真子集，那么称此频繁项集为最大频繁 项集。最大频繁项集集合的每一个元素的所有子集的集合的并集就是完整的频繁项 目集集合，但每一个频繁项目集的支持度不能由最大频繁项集推导出来，因此还需 要对数据库扫描一次并进行计数，这一趟扫描的时间花销通常很大。典型的基于最 大频繁项目集的算法是 zaki 等在 1997 年提出的算法 clusterapr22。该算法首先使 用聚类技术将相关的项集分组，以此得到最大频繁项集集合的超集，然后生成此超 集的所有子集，将这些子集作为候选频繁项集，最后扫描一遍数据库验证此候选频 繁项集。clusterapr 算法的性能优于 apriori 算法，逊于 partition 算法。而后，shen 等提出与 zaki 算法类似的基于最大频繁项集的频繁项集发现算法23，并且此算法 具有本质并行性。 封闭项集是一组事务都包含的项的最大项集。一个数据库的频繁封闭项集集合 与其频繁项集集合的信息量相等，但是前者比后者小得多，因此发现频繁封闭项集 能够减少数据库的扫描遍数和 cpu 开销，从而提升频繁项集发现的效率，并大幅 减少输出冗余信息。 1999 年，pasquier 等提出基于 apriori 算法框架的频繁封闭项集发现算法 close24。相对于 apriori 算法，close 算法在分析强相关数据时具有明显的性能优势， 可将数据库扫描遍数减少到原来遍数的 1/4 到 1/2。 1999 年，zaki 等提出使用垂直数据库结构的频繁封闭项集发现算法 charm25。 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 7 close 算法和 charm 算法在发现长模式或低支持度阈值时效率不高。2000 年，pei 等提出基于 fp_growth 算法框架的频繁封闭项集发现算法 closet26。 项一般具有概念层次关系。当存在概念层次关系时，用户通常对包含不同概念 层次的项的规则感兴趣，并称这种规则为广义关联规则或多层关联规则发现。广义 关联规则发现算法提高性能的关键也在于广义频繁项集发现的效率。 1995 年，srikant 等提出直接推广 apriori 算法的广义频繁项集发现算法 cumulate 算法27。此算法将数据库中所有事务的每个项的所有高层次概念项都加入 到此事务中，形成扩展事务，然后再套用 apriori 算法。由于和高层次概念有关的 项集一般有较大的支持度，和低层次概念有关的项集一般有较小的支持度，而 cumulate 算法对不同类型项集只能使用相同的最小支持度，导致其发现结果不太有 用。 1995 年，han 等在 aprior 算法基础上提出多层频繁项集发现算法 ml_t2l128。 该算法首先将所有项替换为最高层次上的项，同时设置较高的最小支持度，然后找 出满足支持度要求的第一层次频繁项集 l1。在 l1基础上，将所有项替换为第二层 次上的项，降低最小支持度，找出第二层次频繁项集 l2。反复进行，直到 lk为空。 在传统的关联规则发现中，用户仅仅设置了初始阈值（包括支持度，置信度） ， 然后就是等待系统交付最终的结果。系统往往需要经过几个小时或者更长多时间来 产生大量的关联规则，而在这些关联规则中，往往只有小部分是用户关心的。显然， 如果用户能对关联规则的发现过程进行指导，使得产生的关联规则就是用户需要的， 这样不仅规则的数目大大减少了，而且挖掘的效率更高29。 1994 年，klemettinen 等提出在关联规则中应用模板以发现用户感兴趣的关联规 则30。模板是用户自定义词汇表示的规则，其中词汇使用项集进行定义。如果一条 规则满足模板，那么这条规则就是用户感兴趣的。但是由于用户自定义模板的复杂 性，频繁项集发现算法难以高效地检验一个频繁项集是否满足模板。1995 年，fu 提出元规则指导的关联规则发现31。元规则可视为 klemettinen 等提出的模板概念 的一种简单推广。这种类型的发现算法首先由用户给定要发现的关联规则的元模式 或模板，然后根据这些模板在数据库中发现与模板相适应的实际存在的关联规则。 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 8 fu 提出了两个相应的算法：大谓词增长算法和直接 p谓词剥试算法。 srikant 等研究了在提供布尔表达式约束情况下的关联规则发现问题32。这种布 尔表达式约束允许用户指定他所感兴趣的关联规则的集合，这种约束不仅可以用来 对事务数据库进行预加工，而且可以把它集成在挖掘算法内部，从而提高算法的执 行效率，文中根据这种集成方式的不同给出了三种实现项约束的算法： multiple_joins、recorder、direct。其中项约束就是要求所发现的频繁项集必须包含 或不包含用户所指定的若干项。这三种算法推广了 apriori 算法的候选频繁项集生 成过程，在生成候选频繁项集时检验其满足项约束的情况。崔立新提出 direct 算法 的改进算法 separate33。 用户往往只对满足一定约束条件的频繁项集感兴趣，因此如果频繁项集发现算 法只发现满足用户指定约束条件的频繁项集，那么将大量节省用户处理不感兴趣的 频繁项集的时间，同时也可提高算法执行速度。 1998 年，ng 等在分析一般挖掘过程缺乏用户反馈与指导的弊端的基础上，提 出两阶段的关联规则挖掘系统结构，提出并分析了反单调性、简洁性这两种性质的 约束。这里，约束形式可以是项的合取和否定，以及求均值等集合操作29。按照约 束的性质将约束分为反单调、简洁、顽固的三大类，同时将反单调、简洁性的约束 进行组合，将其运用到频繁项集的剪枝过程中，提出了可使用单维变量约束的 cap 算法。该算法是基于 apriori 算法的，通过使用约束对中间频繁项集进行剪枝，使 得频繁项集的发现效率提高了一个数量级。 随后 lakshmanan 等提出可使用二维变量约束的频繁项集发现算法34。由于二 维变量约束大部分不满足反单调性、或者简洁性，因此提出一个“类简洁性”约束， 先将二维的约束转换或弱化成两个一维的简洁性约束，然后再运用 cap 算法。简 单的说，就是把多维约束转换成一维约束，这里提出了一个转换的基本思路。 在对约束的性质讨论上，前后共提出五类性质的约束，分别是反单调的、单调 的、简洁的、可转变的、不可转变的，针对这些性质，关联规则挖掘算法又有了很 大发展35,36,37。 jean-francois 等人提出一个“负边界”的思想38,39,40,41,42，将单调约束与反单调约 束结合起来，提出了一个在 apriori 基础上的实现框架，同时论证了将反单调约束 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 9 推进到 apriori 算法中是有利的，论证了 free 集是一种反单调的约束。 leung 等43提出了一个利用 fp 树实现简洁约束的算法 fps，而且能实现复杂 的简洁约束，有很高的性能。 pei 等提出可使用可转变约束的频繁项集发现算法（算法 ficm、fica）44。其 基本思想是对项集进行某种次序的排序，使得约束满足反单调性或单调性。可转变 的约束可以在 fp_growth 算法框架中实现，不能在 apriori 算法框架中实现。该算 法提出一种前缀增长函数（prefix increasing function） ，利用该函数，可以比较容易 的判断一些形式复杂的约束函数是否是可转变的，是哪种可转变的。这里，将可转 变的约束细分为单调可转变的、反单调可转变的、强可转变的三类。该算法不能解 决多个需要不同方式排序的可转变约束。 支持度约束也是一种反单调的约束。apriori 算法适用的前提之一是对于所有频 繁项集使用相同的最小支持度。如果在数据库中存在出现频率较低的项（称为稀疏 项） ，同时用户对这些稀疏项又比较感兴趣，那么需要使用可变的最小支持度以发 现包含稀疏项的频繁项集，同时不发现太多的用户不感兴趣的频繁项集。 lee 将数据库根据项出现频率分为几部分，然后对每部分应用不同的最小支持 度进行频繁项集发现。此方法难以发现跨越不同部分的频繁项集。而 han 等将若干 相关的稀疏项合并为高层次概念的项，以增加稀疏项的支持度，但这种方法无法发 现包含单个稀疏项的频繁项集。1999 年，liu 等提出的 msapriori 算法是 apriori 算 法的一种推广45。此算法赋予每个项一个最小项支持度（mis） ，并以频繁项集所 包含的项的最小项支持度作为频繁项集支持度的推广定义。通过将项根据其 mis 值 从小到大排序，就可满足推广的频繁项集的逆单调性。2000 年，wang 等提出实现 非统一的支持度（support）约束的算法 adaptive apriori46，将 apriori 算法推广到 使用可变的最小支持度的情况，这样可以避免很多“无意义”的中间频繁项集的生成， 使得结果对于用户更有意义。 apriori 算法首先解决的是布尔关联规则(boolean associatin rules)的挖掘问题， 其后又扩展到对数值型关联规则(quantitative association rules)及分类关联规则 (categorical association rules)的挖掘，与布尔关联挖掘不同的是在挖掘前需要对数 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 10 值及分类属性进行必要的预处理。 长模式频繁集的发现，也有很多的进展。1997 年，gunopulos 等提出一种可用 于长模式发现的随机频繁项集发现算法47。算法循环地试图随机扩展一个工作项集， 直到失败。由于是随机算法，所以此算法不能保证发现所有的长模式，但能够有效 地发现其中的一部分，不过它不能处理内存放不下的数据库。zaki 等提出的 maxeclat 和 maxclique 算法使用 apriori 算法框架，试图在其生成-检验循环开始前 识别长模式，以减少候选频繁项集的生成数目。lin 等提出 pincer-search 算法48， 此算法同样使用 apriori 算法框架，并在其生成-检验循环中识别长模式。1998 年， bayardo 等提出专门的长模式发现算法 max-miner 算法49，此算法按照启发式知识 对项进行排序，以提高发现长模式的效率。在某些数据集上 max-miner 算法比 apriori 算法快 1 到 2 个数量级，而且其运行时间与最大频繁项集数目和数据库大小 成线性关系，与最长频繁项集的长度无关。 由于关联规则挖掘是一项非常耗时的工作，从而导致了很多并行算法的相关研 究，这些并行算法的主要特征是充分利用并行系统的强大运算能力，通过对发现频 繁集这个任务的有效分割提高算法的效率。 频繁项集发现算法发展到目前为止，已经获得了长足的进步。作为许多面向应 用的数据挖掘技术的基础，提高频繁项集发现算法的性能、满足不同应用背景下的 不同要求，依然是一项值得研究的课题。 另外，还有很多其他的关联规则的研究。liu 等人提出利用 x2检验缩小规则数 量的方法50，padmanabhan 等人提出置信驱动的关联规则挖掘算法(belief-driven method for discovering unexpected pattern)51，同时提出了两个算法 estmerge 和 cumulate，解决泛化(generalized)关联规则的问题。savasere 等52研究了挖掘否定关 联规则的问题，他们的方法是使用分组信息如项之间的层次关系，以及现有数据中 的正关联性来导出与正关联中的项“相近”的项之间的否定规则。 在使用关联规则挖掘生物数据的研究方面，creighton 等53详细阐述了将关联规 则挖掘技术应用于生物学数据的方法，并指出了其在寻找基因间的联系、构造基因 调控网络中的应用前景；但并未涉及具体的算法讨论。kotala 等54提出了使用优化 的数据结构 peano-count trees 来挖掘微阵列芯片数据的关联规则。chen 等55提到 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 11 使用 apriori 算法挖掘微阵列芯片数据，以进行转录因子的预测；但由于关联规则 挖掘的过程中产生了大量的冗余规则，影响到了后续的分析应用。tuzhilin 等56提 到如何处理从微阵列芯片中挖掘出的大量关联规则，并首次提出以概念分层来后续 分类规则的想法。继而，tseng 等57实现了使用概念分层的方法来归纳大量且复杂 的规则，继而引入多层关联规则挖掘算法 ml_t2l128来寻找基因间的隐含关系。 候选项生成并验证的方式成为该算法的性能瓶颈，使得它们的效率较低。而高通量 生物实验中需一次性处理的候选模式往往长度很大，支持度有时也较低，因此该算 法用来处理生物数据效率并不理想。 1.3 生物数据关联规则挖掘的基本步骤生物数据关联规则挖掘的基本步骤 一次高通量实验能获得细胞在某一条件下的全基因组表达数据，包含成千上万 个基因在细胞中的相对或绝对丰度，不同条件（细胞周期的不同阶段、药物作用时 间、肿瘤类型、不同病人等）下的全基因组表达数据就构成了一个 gn 的数据矩 阵 m，通常情况下 gn，其中元素 xij表示第 i 个基因在第 j 个条件下的表达水平 值，行向量 xi=(xi1,xi2,xin)代表基因 i 在不同条件下的表达水平，列向量 xj=(x1j,x2j,xgj)代表某一条件下的各基因的表达水平。本文其它关于高通量生物数 据的描述都以矩阵 m 为例（如图 1.1 所示） 。 图 1.1 高通量生物数据矩阵 按行来分析，关系可以表示为 r(gid, xi1,xi2,xin)，其中，gid表示的是标识不 同基因的基因名，xi1,xi2,xin则表示不同基因在不同实验环境中的值。比较矩阵行 的相似性或差别，如果发现两个行相似，可以推测它们对应的基因具有协同调节和 功能相关性。聚类和分类分析正是基于行进行分析。 按列分析，关系可以表示为 r(tid, x1j,x2j,xgj)，其中，tid表示不同的环境的 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 12 标识，而 x1j,x2j,xgj则表示在环境 tid下各个基因的表达水平。通过分析在同一环 境下各个基因的关联度，发现基因之间的关联水平。对高通量生物数据进行关联规 则挖掘多是基于列进行分析。 从数据分析可知，高通量生物学实验数据反映的是基因在细胞中的相对或绝对 丰度，是数值型数据，而传统的购物篮交易数据可看作是布尔型数据，因而对于生 物数据进行关联规则挖掘与对交易数据进行挖掘并不完全相同。对于数值型数据关 联规则挖掘最常用的是将其转换为布尔关联规则挖掘，目前对高通量生物数据的关 联规则挖掘正是采用这类方法。 生物数据关联规则挖掘的基本步骤如下： 一、数据预处理 对实验数据进行关联、聚类等分析之前，需要进行预处理，包括对丢失数据进 行填补、清除不完整的数据或合并重复数据等数据清洗，根据分析的目的进行数据 过滤，以及针对分析方法选择合适的数据转换方法等。 1. 数据清洗：数据分析前必须进行的一项工作，对于生物实验数据，目的是去 除表达水平是负值或很小的数据、或者明显的噪声数据(单个异常大或小的峰谷信号)， 同时处理缺失数据。 2. 数据转换：许多高通量实验的结果是测量样本与对照样本间信号强度的 ratio 值。对于 ratio 值，在大多数情况下是转换到对数(log)空间中进行处理，常 用的对数底为 2，e，10。 3. 数据的标准化：是将所有的数据转换到同一个范围内，这样做的好处是方便 比较和计算相关系数。数据标准化按如下公式进行: 标准化变量公式： (1.1) 2 1 1 () 1 iji ij n iji j xx x xx n 其中 (1.2) 1 1 n iij j xx n 将所有的数据 x 分布在a,b之间，还需要进行如下转换： 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 13 (1.3) min maxmin ()() ba xx xa xx 其中 xm in =min x1 , x 2, ,x n, x max =max x1 , x2 , , xn 。 二、布尔矩阵的生成 与购物篮交易数据相比，高通量实验数据的不同条件相当于不同的交易，而每 个基因则可看作是不同的商品。进行关联规则挖掘是为了找出各种项，即各个基因 之间的相关联系。然而还有一个关键问题需要解决，对于交易数据，交易中的每一 项是以布尔值的形式出现的，它只能是两种状态之一：存在和不存在。而生物学实 验数据中的项则表现为一定量的数值。在进行关联分析之前，必须对基因表达数据 做离散化处理，使得各种条件下基因的表现形式为布尔值，也就是 true(1)， false(0)。根据生物数据关联规则挖掘的不同要求，对其进行转换的方法也有差别， 目前常采用的布尔矩阵转换方法有以下两种： 1. 根据实验数据的数值的大小，将其表达方式分为三种：偏高（up） 、偏低 （down）以及正常（neither up nor down） 。给出一个区间a，b，对与 xij ，xij a，b，则将它视为正常表达；xij b，视它为偏高。因为对 高通量实验数据关联规则挖掘的兴趣在表达不正常的基因上，故将每个基因分割为 两个状态，一是偏高，一是偏低。这样，每个交易的项分为两个项。如图 1.2 所示， 以-0.2，0.2为例对以下基因表达数据进行转换。依据这种转化方法即可得到形如 cancer genea，geneb，genec的关联规则，揭露疾病与基因之间的关 系。其中a，b的确定则根据不同的离散化方法得到。 图 1.2 布尔矩阵的生成 2. 根据实验数据的数值的大小，将其表达方式分为两种：超高 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 14 （overexpressed）与正常(not overexpressed)。当其值超高的时候，将其赋值为 1， 否则赋值为 0。其阀值（cutoff）可根据个人经验或目的自由根据不同的离散化方 法确定。经过这种转换，可以得出形如geneageneb的关联规则，揭露基因之 间的相关联系。 三、使用挖掘算法对其进行挖掘 这一步是核心步骤。将高通量生物学实验数据转化后，可以采用与挖掘交易数 据库的算法对其进行关联规则挖掘。 四、结果表现形式 根据不同的挖掘目的，基因表达数据的关联规则按其表示形式可以分为两类： 1. 基因之间的关联，形如genea geneb的关联规则，揭露基因之间的相 关联系。为单维的关联规则。 2. 基因与疾病之间的关联，形如cancer genea，geneb，genc的关联规 则，揭露疾病与基因之间的关系。因为其要处理的数据涉及到疾病以及基因两个属 性，属于多维的关联规则。 也有在 2 的基础上再考虑另一些因素的，例如，根据表达值的大小将基因划分 为三个区间，得出形如cancergenea，geneb，genc。对于多维关联规 则的处理方法就是将不同的维当作不同的属性，根据不同的维的性质指定它在关联 规则中的位置，例要求在规则的右边必须是疾病这一属性的某一个值，如cancer。 1.4 论文组织结构论文组织结构 本文内容包含以下几个部分： 第一章：介绍生物数据关联规则挖掘的研究背景、研究现状和基本步骤等。 第二章：介绍两种经典的关联规则挖掘算法和两种经典的多层关联规则挖掘算 法的原理及实现过程，并作出了分析与比较。 第三章：选用 gene ontology 完善的概念层次结构，通过对 fp_growth 算法进 行扩展，提出一种优化的生物数据多层关联规则挖掘算法 mago-fp，并分析其时 间复杂度。 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 15 第四章：应用 mago-fp 算法分析实际的生物数据，发现一些候选关联规则。 进行实验结果分析，并与传统的多层关联规则挖掘算法进行性能比较。 第五章：对全文进行总结，并提出进一步的研究方向。 华华 中中 科科 技技 大大 学学 硕硕 士士 学学 位位 论论 文文 16 2 关联规则挖掘关联规则挖掘算法算法 2.1 关联规则关联规则的定义和相关概念的定义和相关概念 关联规则是数据挖掘技术所能发现的非常重要的一类规则，它首先由 agrawal 等人6于 1993 年提出，能够揭示项集之间的有趣联系。关联规则挖掘能够从大量 数据中发现关联规则，例如，关联规则挖掘可用于发现交易数据库中不同商品(项) 之间的联系，从而找出顾客购买商品的行为模式，进而把它应用于商品货架设计、 货存安排以及根据购买模式对用户进行分类等。通常会提出这样的问题，如“购买 牛奶的顾客同时也购买面包的可能性有多大？”， “购买计算机的顾客大多在哪个年 龄段？”等，这些都是属于关联规则挖掘所要解决的问题。 2.1.1 基本概念 设 i=i1,i2,im是项目的集合，其中的元素 ik(k=1,2,m)称为项目(item)。d 是一个事务(transaction)数据库，其中，每个事务 t 是满足 ti 的项的集合，而且 有唯一的标识 tid。 定义 2.1 如果一个项目 i 属于事务 t，则称事务 t 支持项目 i；如果一个事务 t 支持项集(或称模式)a 中的每个项，则称事务 t 支持项集(或模式)a。 定义 2.2 项集 a 在事务数据库 d 中的支持度(support)为： support(a)= (d 中支持 a 的事务数)/( d 中的事务数) 100 而将 d 中支持 a 的事务数称为 a 在 d 中的支持数。 定义 2.3 给定最小支持度 minsup(或最小支持数 )，若项目集 a 的支持率大 于等于 minsup(或支持数大于等于 )，则称项目集 a 是频繁项集或频繁模式。 定义 2.4 关联规则是形式为 ab 的蕴涵式,其中 ai、bi、ab=， 其支持度 support(ab)=support(ab);置信度 confidence(ab)=support(ab) /support(a)100 定义 2.5 把同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)