一种改进关联规则挖掘算法.doc

一种改进关联规则挖掘算法 　　摘要：针对Apriori算法存在的缺陷，提出一种改进的关联规则算法。该算法对数据库中的项采用二进制编码，且只需扫描一次事物数据库就能找出所有的频繁项集，减少了扫描数据库的次数和计算成本，从而大大提高了算法的执行效率。 　　关键词：关联规则；Apriori算法；频繁项集；数据挖掘；数据库 　　中图分类号：TP311.13文献标识码：A文章编号：1009-3044(2012)05-1015-04 　　An Improved Algorithm for Mining Association Rules 　　BAI Xue-feng 　　(Chongqing Three Gorges Medical College, Chongqing 404120, China) 　　Abstract: According to the inefficiency problems about the Apriori algorithm, this thesis proposes a new improved algorithm of association rules. This algorithm uses the binary code to the database item. This algorithm is able to discover all the frequent item sets only by searching the database once. Because this algorithm reduces the number of scanning the database and computational cost, so it has higher efficiency. 　　Key words: association rule; apriori algorithm; frequent item set; date mining; database 　　关联规则挖掘是研究人员于1993年研究市场购物篮问题时提出的[1]，它是用来从大量的数据中挖掘出数据项间隐藏的相互关联的有用知识，应用极其广泛，在数据挖掘中具有重要的地位。 　　针对关联规则的经典算法―Apriori算法存在的不足，本文提出了一种新的关联规则挖掘算法―GApriori算法，该算法对数据库中的项采用二进制编码，提高了算法的执行速度，节省了大量的时间。同时，该算法只需对数据库进行一次扫描就能找出所有的频繁项集，而连接前剪枝有效的减少了挖掘过程中需要进行连接的项集数目，因而对算法效率有了很大提高。 　　 1关联规则挖掘 　　先介绍关联规则的几个基本概念，具体描述如下[2]： 　　定义1：假设关联规则挖掘的事务数据集记为D，其中，D= {t1,t2,…,tk,…,tn}，tk={i1,i2,…,im,…ip}，那么tk（k=1，2，…，n）称为事务(Transaction)，im（m=1，2，…，p）称为项目（Item）。 　　定义2：假设I={i1,i2,…,im }是由D中所有项目组成的集合，则I的每一个子集X就称为D的项目集（Itemset）。假设X、Y都是项目集，且X?Y=?，则蕴含式X?Y称为关联规则。 　　定义3：对于关联??则X?Y，如果数据集D中拥有项目集X?Y的个数为σ，交易数据集D的事务数为||D，那么，关联规则X?Y的支持度就是σ与||D之比。 　　定义4：如果项目集X的支持度大于等于事先设定的最小支持度minsupport，那么就称X为频繁项目集。 　　关联规则的挖掘过程是先查找符合既定条件的频繁项集，然后利用频繁项集生成关联规则。通过对数据库使用关联规则挖掘，可以得到一些潜在有用的挖掘结果。将这些结果同事先设定的最小支持度minsupport和最小置信度minconfidence进行比较，如果其值不小于事先设定的值，那么就是有趣的规则。 　　Apriori算法是通过对数据库进行反复逐层搜索，来得到频繁项集。首先，对数据库进行第一次扫描，得到频繁1-项集L1；然后，由L1产生C2，并对数据库进行第二次扫描，得到频繁2-项集L2；接着利用上述方法，得到频繁3-项集L3，然后不断重复上述过程，直到找出所有的频繁项集。通过研究分析频繁项集，可以得到用户感兴趣的规则。 　　显然，对于Apriori算法，存在着如下缺陷[3]： 　　1）Apriori算法在对候选项集进行模式匹配时，需要对数据库进行多次重复扫描。当数据库规模庞大时，大量的时间将消耗在内存与数据库中的数据的交换上，使得整个扫描过程的时间复杂度很大。 　　2）算法可能需要产生大量的候选项集。比如说，如