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

硕士学位论文一种基于生物数据的多层关联规则挖掘算法A Thesis Submitted in fulfillment of the Requirements for the Degree of Master of EngineeringAn Algorithm for Mining Biological Data Multilevel Association RulesCandidate: Zhang PingMajor: Computer Software and TheorySupervisor: Prof. Lu YanshengHuazhong University of Science & TechnologyWhuhan 430074, P.R.ChinaJune, 2007独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期：     年   月   日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于 保 密 ，在_年解密后适用本授权书。不保密。（请在以上方框内打“”）学位论文作者签名：                   指导教师签名：日期：    年   月   日              日期：    年   月    日摘 要数据挖掘是从大量数据中发现潜在的、有趣的知识的过程，是解决“数据丰富，知识贫乏”状况的有效方法。关联规则挖掘用于从大量数据中揭示项集之间的有趣关联或相关联系，是数据挖掘的一项重要研究内容，在现实生活中有着广泛的应用。研究表明，关联规则挖掘技术是寻找基因间关系的有效手段；但现有算法未针对高通量生物数据的特点进行优化，而存在着效率低下、规则缺乏生物学意义等缺点。与单层关联规则挖掘相比，多层关联规则能够提供更加丰富、更具普遍意义的知识；选用合理的概念层次结构与多层关联规则挖掘算法，能够更好的适应生物数据挖掘的需要。已有的多层关联规则挖掘算法如Cumulate 算法、ML_T2L1算法，都是通过对Apriori算法进行扩展得到的。这些算法仍采用候选生成并验证的方式得到频繁模式，导致了巨大的计算和I/O 开销，使得效率较低。选用Gene Ontology完善的概念层次结构，通过对FP_Growth算法进行扩展，获得了一种优化的生物数据多层关联规则挖掘算法MAGO-FP。MAGO-FP算法采用的扩展措施如下：(1)在扫描数据库的过程中通过把每个项的全部祖先加入到事务中对每条事务进行扩充，该措施能够确保得到多层关联规则；(2)通过及时删除概念层次树中不是频繁项的祖先项来压缩搜索空间，提高挖掘效率；(3)避免产生冗余的频繁模式。性能实验表明MAGO-FP算法是正确的，并继承了FP_Growth算法运行效率高的优点。应用MAGO-FP算法分析了一组由S.cerevisiae酵母菌cDNA微阵列芯片产生的实验数据，发现了一些候选关联规则。并针对其中一些重要的关联规则，通过相关文献证实了其真实性，表明该算法在基因表达分析、基因调控网络等研究中具有一定的应用价值。关键词：数据挖掘，多层关联规则，基因本体论，MAGO-FP算法AbstractData mining is a process to reveal latent and interesting knowledge from massive data, and an effective approach to solve the problem of "rich data and poor knowledge". Association rules mining can reveal interesting correlations among item sets from massive 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 between genes, showing patterns that may not have been identified using traditional clustering methods; 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目 录摘 要IABSTRACTII1 绪 论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)4.3 实验结果与分析(46)4.4 小结(48)5 结 论(50)致 谢(51)参考文献(52)附录1（攻读学位期间发表论文目录）(60)1 绪 论1.1 研究背景与意义生命科学近年来获得突破性进展1，随着生物学和医学的迅速发展，生物数据呈指数级增长，无论是在数量上还是在质量上都极大的丰富了生命科学的数据资源，提供了揭开生命奥秘的数据基础。然而生物数据种类丰富，高通量，维数高，本质上具有异质性与网络性，远远超出传统的分析方法的能力和速度，其处理、挖掘、分析和理解日益迫切。如何分析这些具有丰富内涵的数据并从中获得关生物结构和功能的信息，从中得到对人类有益的信息，是生物研究的瓶颈，是当前研究所面临的一个严峻挑战。生物信息学是在此背景下发展起来的综合运用生物学、数学、信息学以及计算机科学等诸多学科理论方法的崭新交叉学科，是在生命科学的研究中,以计算机科学知识为辅导工具对生物信息进行储存、检索和分析的科学，是当今生命科学和自然科学的重大前沿领域之一。它包含两方面的内容，一方面是对海量数据的搜索、管理、服务，即“管好数据”；另一方面从中发现规律，即“读懂”数据。随着人类基因组计划的完成，生物信息学的研究重点已经从开始的序列分析、数据库查询逐渐向生物信息的挖掘、表达、数据多样性分析的方向发展，高通量实验数据分析成为目前生物信息学研究的热点和重点。这些数据是通过一些高通量实验测量技术得到的，往往包含着几千个基因或基因片断和几十个属性。高通量实验数据，无论是转录水平上还是蛋白质水平上，其中都蕴含着丰富的生物学知识，可以帮助我们理解基因、理解生物、理解细胞等等，例如某疾病是由什么基因引起的、细胞是处于正常还是恶化状态、药物对肿瘤细胞是否有效等。由于越来越多数据得以公开，人们迫切希望通过数据挖掘技术在这些具有丰富内涵的海量数据中获得有益的信息。对高通量实验数据的分析可以获取基因功能和基因表达调控信息，这是生物信息学的重大挑战之一，也是基因组学、蛋白质组学的相关实验技术能够在生物医学领域中广泛应用的关键原因之一，它们在医学临床诊断、药物疗效判断、揭示疾病发生机制等方面有重要的应用。数据挖掘2是新兴的一种科学计算技术与数据分析方法，它能够有效地从存有海量信息的数据库中提取隐含的、事先未知的潜在的和有用的信息和知识，经过多年的研究与发展，它已经成为一项很重要的数据分析工具。作为一种以数据库、统计学和人工智能学为基础的新兴技术，数据挖掘给基因组学家们提供了前所未有的数据分析工具，为基因和蛋白信息的分析和提取提供了强有力的手段。生物信息学、数据挖掘两者的结合，不论是现在还是将来，不论在理论上还是应用上都具有十分重要的意义。因此生物数据挖掘日益重要，逐渐成为生物信息学研究领域的关键。数据挖掘的常用技术中，聚类和分类技术已经成为基因鉴定、功能预测和基因表达分析等研究中最常用的手段。而关联规则挖掘技术，作为分析海量数据库中项目间相关联系的重要技术，目前在生物学领域中并未得到广泛应用，相应的算法也不够成熟。与数据挖掘的其他技术相比，关联规则更能挖掘出基因间的网络结构。因为聚类和分类技术只能显示数据中基因群普遍的表现形式；而关联规则的频繁模式集不但可以显示出表现形式，其所产生的推论规则更可以描述基因间的联系；另外还有支持度和置信度参数可供生物学家作评价标准。同时，关联规则能有效的克服聚类等分析技术只能将基因分到某一群，往往忽略了基因可能同时参与几个生化路径的缺点。但是，目前的生物数据关联规则挖掘算法仍然存在着挖掘结果缺乏很强的生物学意义，候选规则冗余度高和挖掘计算效率低等不足，迫切需要针对生物数据的特殊性建立适用的关联规则挖掘算法。本研究拟选用Gene Ontology完善的概念层次结构3，通过对FP_Growth算法4进行扩展，期望实现一种优化的生物数据多层关联规则挖掘算法：能有效地克服传统的、基于Apriori5的多层关联规则挖掘算法的缺点，大幅提高挖掘效率；并且保证挖掘结果具有良好的生物学意义。因此，拟提出的新算法预期在基因表达分析、基因调控网络等研究中具有广泛的应用价值。1.2 关联规则挖掘研究进展关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。它是数据挖掘中的一个重要问题，其研究目标是找出满足最小支持度和最小可信度要求的关联规则。关联规则是形如AB的蕴涵式，其中A、B都是项集。一般地,关联规则发现分为找出所有的频繁项集和由频繁项集产生强关联规则两个步骤，其中找出所有的频繁项集是关联规则算法的性能瓶颈。因此绝大部分对关联规则算法的研究都集中在第一步，即如何在保证精度的基础上提高算法的运行效率，其中精度是指所找出的频繁项集的满足要求的程度。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-候选频繁项集的频繁度。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算法的思路基本一致，不同在于：前者在经过一次扫描数据库后，不再利用数据库来计算项目集的支持度，而利用候选项集来计算，因而减少了对交易数据库的遍历次数，提高了效率。基于采样的技术，是先利用从数据库中抽取出来的采样，生成一些可能的规则，然后再针对数据库中剩余的部分验证这些规则。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。此算法构造一个词典树，并根据已发现的频繁项集，将数据库投影到一组精简的子数据库上。由于词典树提升了检验候选频繁项集的效率，并且此算法还使用其它各种提高效率的技术，所以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。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等提出的模板概念的一种简单推广。这种类型的发现算法首先由用户给定要发现的关联规则的元模式或模板，然后根据这些模板在数据库中发现与模板相适应的实际存在的关联规则。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基础上的实现框架，同时论证了将反单调约束推进到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)的挖掘，与布尔关联挖掘不同的是在挖掘前需要对数值及分类属性进行必要的预处理。长模式频繁集的发现，也有很多的进展。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提到使用Apriori算法挖掘微阵列芯片数据，以进行转录因子的预测；但由于关联规则挖掘的过程中产生了大量的冗余规则，影响到了后续的分析应用。Tuzhilin等56提到如何处理从微阵列芯片中挖掘出的大量关联规则，并首次提出以概念分层来后续分类规则的想法。继而，Tseng等57实现了使用概念分层的方法来归纳大量且复杂的规则，继而引入多层关联规则挖掘算法ML_T2L128来寻找基因间的隐含关系。候选项生成并验证的方式成为该算法的性能瓶颈，使得它们的效率较低。而高通量生物实验中需一次性处理的候选模式往往长度很大，支持度有时也较低，因此该算法用来处理生物数据效率并不理想。1.3 生物数据关联规则挖掘的基本步骤一次高