摘 要：关联规则是数据挖掘的主要技术之一，它是描述数据库中一组数据项之间的某种潜在关系的规则。关联规则挖掘算法——Apriori算法，主要过程是对频繁项集的挖掘,而在对频繁项集的挖掘中首先要生成候选频繁项集，然后再从候选集中确定出满足最小支持度计数的频繁项集,这会耗费大量的CPU开销。使用垂直数据格式挖掘频繁项集可避免候选项目集的求解。
关键词:关联规则；Apriori算法；频繁项集；垂直数据格式
通常，关联规则挖掘是指从一个大型的数据集中发现有趣的关联或相关关系，即从数据集中识别出频繁出现的属性值集（Sets of Attribute-Values），也称为频繁项集（Frequent Itemsets,简称频繁集），然后再利用这些频繁集创建描述关联规则的过程。
1 关联规则挖掘算法
关联规则挖掘算法——Apriori算法是使用候选项集找频繁项集的过程。
Apriori算法通过对数据库D的多趟扫描来发现所有的频繁项目集。在第一趟扫描数据库时，对项集I中的每一个数据项计算其支持度，确定出满足最小支持度的频繁1项集的集合L1，然后，L1用于找频繁2项集的集合L2，如此下去……在后续的第k次扫描中，首先以k-1次扫描中所发现的含k-1个元素的频繁项集的集合Lk-1为基础，生成所有新的候选项目集CK（Candidate Itemsets），即潜在的频繁项目集，然后扫描数据库D，计算这些候选项目集的支持度，最后从候选集CK中确定出满足最小支持度的频繁k项集的集合Lk,并将Lk作为下一次扫描的基础。重复上述过程直到不再发现新的频繁项目集[1]。
2 关联规则算法的改进
从Apriori算法中由k频繁项集生成k+1频繁项集时，首先生成候选项目集Ck+1，该函数不仅要对k项集的所有符合Apriori算法条件的数据进行交集，并且要判断候选项目集的所有子集是否在k频繁项集中。该函数生成的许多候选项目集并不是要找的频繁项集，但在扫描数据库时，要记录下这些数据的出现次数，这会耗费大量的CPU开销。如果D中的事务数很大，k频繁项集中项数很多，则侯选项目集的元素个数就会很大，例如2 000个频繁1项集，将产生2 000×999/2=999 000个候选2项集。如此巨大数量的候选项目集，对它进行出现次数的统计时开销非常大，这也是整个算法性能优劣的关键所在。
（1）使用垂直数据格式挖掘频繁项集
Apriori算法是从TID项集格式（即{TID：itemset}）的事务集挖掘频繁模式，其中TID是事务标识符，而itemset是事务TID中购买的商品集。这种数据格式称作水平数据格式。另外,数据也可以用项-TID集格式(即{item:TID_set})表示，其中item是项的名称，而TID_set是包含item事务标识符的集合。这种格式称作垂直数据格式。下面使用垂直数据格式进行有效的挖掘频繁项集。
首先，通过扫描一次数据库D，在求频繁l项集的同时，把数据由水平格式转化为垂直格式，即记录下每个项集在事务数据库中出现时该条数据在数据库D中的TID号，则项集的支持度计数直接是项集的TID集的长度。从k=2开始，根据Apriori性质中相交条件的项集进行Apriroi连接运算，使用频繁k项集来构造候选k+1项集。通过取频繁k项集的TID集的交计算对应的k+1项集的TID集。如果该TID集的长度大于最小支持度计数，则该记录为频繁项集。重复该过程，每次k值增加1，直到不能再找到频繁项集或候选项集。
通过挖掘可以验证最终得到的频繁项集和用Apriori算法得到的结果是相同的[2-3]。
3 改进算法的分析
理论上，改进算法应快于算法Apriori，原因如下：
(1)该算法不用求候选频繁项集，从而省去了项集进行连接步以后对该项集所有子集的判断，这会节省大量
的CPU开销，尤其是当数据库D中的数据比较多，同时候选项集比较多时，例如频繁1项集2 000个，根据Apriori性质,则候选频繁1项集要有2 000×999/2=999 000个，但其中也许只有少数是要找的频繁2项集。Apriori算法要求其中所有999 000个在数据库中的频繁度。
(2) 除了由频繁k项集产生候选k+1项集时利用Apriori性质之外，这种方法的另一优点是不需要扫描数据库来确定k+1项集(k≥1)的支持度。这是因为每个k项集的TID集携带了计算该支持度所需的完整信息。
该算法的缺点是TID集可能很长，长集合不仅需要大量空间，而且求交运算需要大量计算时间。
参考文献
[1] 韩家炜. 数据挖掘概念与技术[M].北京：机械工业出版社，2000.
[2] 陆楠.关联规则的挖掘及其算法的研究[D]. 长春：吉林大学，2007.
[3] 罗可，张学茂. 一种高效的频集挖掘算法[J]. 长沙理工大学学报(自然科学版)，2006，3(3)：84-90.
[4] 汪光一. 关联规则挖掘算法的研究[D]. 北京：北京交通大学,2007.
[5] 高峰，谢剑英. 发现关联规则的增量式更新算法[J].计算机工程，2000(12):49-50.
[6] KANTARDZIC M(美).数据挖掘-概念、模型、方法和算法[M]. 北京：清华大学出版社，2003.