关联规则数据挖掘国内外研究现状

菜单

数据库中的知识发现源于八十年代后期，1989年在美国底特律召开了首次关于知识发现和数据挖掘的国际会议，内容涉及机器学习、模式识别、统计学、知识获取、智能数据库、数据可视化、专家系统、高性能计算等领域。随后， 1995年8月，在加拿大蒙特利尔市召开的第一届知识发现与数据挖掘的学术会议上，人们开始重新认识数据、重新认识存储、重新认识数据统计和分析。而亚太地区，于1997年在新加坡也举行了首届知识发现和数据挖掘的国际性会议(Pacific-Asia Conference on Knowledge Discovery and Data Mining，PAKDD)。65325

然而，知识发现与数据挖掘的相关研究一直作为数据库和机器学习的一个分支领域，处于依附的地位。直到1998年6月，知识发现与数据挖掘的国际性会议ACM SIGKDD(Association of Computing Machinery，Special Interest Group on Knowledge Discovery and Data Mining)正式成立，标志着知识发现和数据挖掘成为一个独立的学科。

关联规则作为数据挖掘的重要组成部分，于1993年由Agrawal，Imielinski和Swami首次提出，一直是数据挖掘领域的研究热点。Apriori算法是关联规则中最重要的算法之一，其最主要工作是对频繁项集的挖掘，之后的大部分算法都是在此基础上进行的一系列改进。论文网

经典的Apriori算法在频繁项集挖掘过程中所需时间多的主要原因是数据库中的庞大数据量，再加之需要多次的数据库扫描，如果可以有效地减少挖掘过程中所需处理的数据量，便可大大提高挖掘的处理效率。因此，Toivonen等人于1996年提出了一种基于采样(Sampling)技术来产生频繁项集的算法[5]。该算法的基本思想是：首先选取事务数据库D的随机抽样样本，然后在该样本上进行关联规则挖掘，找出可能的频繁项集，最后，再利用事务数据库中的剩余项来验证这些频繁项集，找出最终的关联规则。Toivonen所提出的基于采样的挖掘算法处理起来比较简单，而且可以明显降低扫描数据库所带了的巨大I/Q负荷，但它所带来的最大问题是，抽样数据的样本并不一定能代表整体事务数据库的特性，并可能由此产生挖掘出来的结果偏差较大的现象，即所谓的数据扭曲(Data Skew)问题。采样的方法是统计学中经常使用的一门技术，虽然在挖掘过程中产生不了十分精确的结果，但是如果适当使用，也能在满足一定精度的前提下，明显提高挖掘的效率或是利用有限的资源处理更多的数据。同时，Lin和Dunham等人于1998年提出了一种采用反扭曲(Anti-skew)技术改善抽样挖掘过程中的数据扭曲问题。

随着研究的不断深入，后续的学者又提出了一种基于事务压缩的方法。该方法可以有效减少后续扫描数据库的大小。该算法所利用的一个基本原理是，当一个事务不包含任何频繁k-项集的时候，该事务必然也不会包含任何频繁(k+1)项集，因为任何频繁(k+1)项集的子集均为频繁k-项集，而这k-项集都不会出现在该事务中，再加一项就更不会出现了，因此在之后的处理中可以把该事务删除，缩小事务数据集的事务个数，减少后续频繁项集的遍历数量，提高算法的处理效率。

我国在数据挖掘领域的研究起步较晚，开始于90年代中期，直到90年代中后期，才初步形成了知识发现与数据挖掘的基本框架。国家科学自然基金于1993年首次支持对该领域的研究项目，国内从事该领域的研究人员主要集中在大学，少部分存在于研究所或公司之中，所涉及的研究领域也很广泛，一般集中在学习算法的研究、数据挖掘的实际应用和有关数据挖掘理论方面的研究。国内关联规则挖掘领域的研究在国家和政府的大力支持下正蓬勃发展。