基于散列的频繁项集分组算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于散列的频繁项集分组算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：

Apriori算法是频繁项集挖掘的经典算法。针对Apriori算法的剪枝操作和多次扫描数据集的缺点，提出了基于散列的频繁项集分组（HFG）算法。证明了2项集剪枝性质，采用散列技术存储频繁2项集，将Apriori算法剪枝操作的时间复杂度从O（k×|Lk|）降低到O（1）；定义了首项的子项集概念，将数据集划分为以Ii为首项的数据子集并采用分组索引表存储，在求以Ii为首项的频繁项集时，只扫描以Ii为首项的数据子集，减少了对数据集扫描的时间代价。实验结果表明，由于HFG算法的剪枝操作产生了累积效益，以及分组扫描排除了无效的项集和元组，使得HFG算法在时间性能方面与Apriori算法相比有较大提高。

关键词：

频繁项集；2项集剪枝；散列表；首项分组；索引表

0引言

随着频繁项集挖掘应用领域的扩展，吸引了很多学者加入研究，提出了许多频繁项集挖掘算法，其中，美国学者Agrawal等[1]提出的Apriori算法是一个里程碑，其基本原理是用频繁k项集找出候选频繁（k+1）项集，再扫描数据集得到频繁（k+1）项集及其支持度。Apriori算法的缺点是产生大量候选频繁项集，并且需要多次扫描数据集。针对Apriori算法的缺点，很多学者对Apriori算法进行了改进研究，如采用FP树（FrequentPattern tree）存储数据集[2-4]、采用垂直格式存储数据集[5-6]、采用散列表存储候选频繁项集[7]、分段计算支持度[6，8-10]、不产生候选项集[2-3]等。近年来，有学者提出基于概念格的挖掘算法[11]、基于滑动窗口的挖掘算法[12]等。

本文针对Apriori算法的剪枝操作和多次扫描数据集的缺点，证明了非频繁2项集剪枝性质，采用散列表存储频繁2项集，在O（1）时间完成了与Apriori算法同样的剪枝操作；定义了首项的子项集概念，将数据集按首项进行分组，在求以Ii为首项的频繁项集时，只扫描以Ii为首项的数据子集，从而减小了对数据集扫描的时间代价；在此基础上，提出了基于散列的频繁项集分组（Hashbased Frequent itemsets Grouping， HFG）算法。相比其他频繁项集挖掘算法，HFG算法没有复杂的理论推导，容易理解和实现。实验结果表明，HFG算法在时间性能方面与Apriori算法相比有较大提高。

1相关工作

1.1问题描述

问题描述[1，13]如下：设I={I1，I2，…，Im}是所有项的集合，非空项集中包含项的个数称为项集A的长度，长度为k的项集记为k项集。设T={T1，T2，…，Tn}是相关事务的数据集合，其中每个事务由TID标识，且1≤i≤n。

设A是一个项集，数据集T包含项集A当且仅当1≤i≤n，数据集T中包含项集A的事务的个数，称为项集A在数据集T中的支持度，记为sup_count（A）。给定支持度阈值min_sup，如果项集A满足sup_count（A）≥min_sup，则称项集A为数据集T的一个频繁项集。频繁项集挖掘的任务就是在数据集T中找出所有支持度不小于给定阈值min_sup的频繁项集。

1.2Apriori算法

Apriori算法采用逐层搜索的迭代方法，具体过程是：扫描数据集找出所有频繁1项集（记为L1）；将L1进行自身连接，产生所有候选频繁2项集（记为C2），再扫描数据集得到L2；将L2进行连接，产生C3，再扫描数据集得到L3；依此下去，直至不能找到频繁项集为止。

在Apriori算法的连接步，对于两个频繁k项集A和B，假定数据集中的项集按字典排序，如果A[1]=B[1]∧A[2]=B[2]∧…∧A[k-1]=B[k-1]∧A[k]

1.3Apriori算法的改进研究

为了避免对数据集进行重复扫描，文献[2]提出FPGrow（FrequentPatternGrow）算法将数据集压缩存储到FP树中，然后递归地对FP树进行挖掘。FPGrow算法的缺点是遍历树的开销仍然很大，而且当数据集规模很大时，构造基于内存的FP树遇到困难。文献[3]提出OP（Opportune Project）算法集成了自顶向下和自底向上的方法遍历FP树；文献[4]使用基于投影进行超集检测的机制，减少了遍历树的开销；文献[5]使用了空间代价较大的垂直格式存储数据集，通过取频繁k项集的TID集的交得到频繁（k+1）项集的TID集。

为了减少对整个数据集的扫描，文献[6]提出Partition算法将数据集从逻辑上划分为互不相交的块，对每个分块生成局部频繁项集，再扫描数据集得到全局频繁项集；文献[8]将数据集划分为用开始点标记的块，然后动态评估已计数的所有项集的支持度；文献[9]提取候选模式的紧密上阶，从而减少对数据集的扫描；文献[10]提出分段计算支持度的思想，并对数据集进行约简，缩减了潜在项集的规模。上述改进算法的共同缺点是需要设定合理的局部支持度阈值或划分点，才能不丢失全局频繁项集，而且由于局部频繁项集之间可能互不相同，导致全局候选频繁项集非常庞大。

为了加快对候选频繁项集的支持度计算，文献[7]采用散列表存储候选频繁项集并增加桶计数，如果某散列表项的桶计数小于支持度阈值，则该项集一定非频繁。该算法的缺点是存放项集计数的散列树与存放候选项集的散列表之间存在内存争用问题，而且由于无法避免冲突，当桶计数大于等于支持度阈值时，还须判断其中每个候选项集是否满足最小支持度。

2基于散列的频繁项集分组算法

2.1基本概念

定义1设I={I1，I2，…，Im}，非空项集的第一项称为项集A的首项。设T={T1，T2，…，Tn}，对于Ii∈I（1≤i≤m），Tj∈T（1≤j≤n），若Ii∈Tj，则事务Tj中Ii之后的所有项构成以Ii为首项的子项集，所有以Ii为首项的子项集构成的集合称为以Ii为首项的数据子集，记为STi。

例如，对表1所示事务数据集T，以I3为首项的数据子集ST3如表2所示。显然，sup_count（Ii）=|STi|（1≤i≤m）。

定理1设Ci，k表示所有以Ii为首项的候选频繁k项集，则Ci，k中的所有项集只包含于数据子集STi中。

证明设c∈Ci，k，则Ii为项集c的首项，设TjSTi，若Tj包含项集c，则一定有Ii∈Tj，与TjSTi产生矛盾，因此，结论成立。证毕。

定理2连接频繁k项集A和B得到（k+1）项集c，项集c存在非频繁k项子集当且仅当c存在非频繁2项子集{A[k]，B[k]}。

证明设c={A[1]，A[2]，…，A[k-1]，A[k]，B[k]}，则项集c的k项子集{A[1]，A[2]，…，A[k-1]，A[k]}和{A[1]，A[2]，…，A[k-1]，B[k]}一定是频繁的。设a[1]a[2]…a[k-2]A[1]A[2]…A[k-1]，在项集c的k项子集{a[1]，a[2]，…，a[k-2]，A[k]，B[k]}中，根据Apriori性质，项集{a[1]，a[2]，…，a[k-2]，A[k]}一定是频繁的，如果2项子集{A[k]，B[k]}非频繁，则k项子集{a[1]，a[2]，…，a[k-2]，A[k]，B[k]}一定非频繁，反之亦然，从而结论成立。证毕。

定理3设项l∈T，若sup_count（l）

证明任取c∈UkLk，则sup_count（c）≥min_sup，设项l′∈c，则sup_count（l′）≥min_sup，因此，一定有l′≠l，即项l一定不会出现在任意频繁项集中。证毕。

定理4在计算（k+1）项集的支持度时，可以忽略数据集中项集长度小于等于k的事务。

证明若数据集中某项集的长度小于等于k，则该项集不存在长度为k+1的子集，因此，该项集对计算（k+1）项集的支持度没有贡献，可以忽略。证毕。

2.2改进的着眼点

针对Apriori算法的剪枝操作和多次扫描数据集的缺点，HFG算法提出了以下改进：

1）Apriori算法应用Apriori性质剪掉存在非频繁k项子集的候选频繁（k+1）项集，从而得到精简的候选频繁（k+1）项集，最坏情况下需要查找k个k项子集，其时间复杂度是O（k×|Lk|）。在长模式挖掘以及候选项集的规模增大时，剪枝操作非常耗时。本文采用散列表存储频繁2项集，利用定理2只须执行一次判断，即可在O（1）时间完成与Apriori算法同样的剪枝操作，这个改进由于频繁执行剪枝操作将获得较大的累积效益。

2）Apriori算法在计算Ck的支持度时需要对数据集进行全扫描，当数据集的规模很大时，扫描一次所花费的代价也相当大。根据定理1，本文对数据集进行首项分组，在求以Ii为首项的频繁项集时，只须扫描数据子集STi，从而减小了扫描的数据集规模。

3）数据结构的设计。

采用分组索引表[14]存储以Ii为首项的数据子集，节点结构如图1所示，其中：TID表示元组的标识号，first表示项Ii在元组中的序号，length表示从项Ii开始的项集长度。

3实验及结论

实验环境为CPU Intel Core 2、主频1.8GHz、2GB内存，操作系统为Windows XP 2002，编程环境为Visual C++ 6.0，分别实现了Apriori算法和HFG算法，实验数据采用文献[1]的人工合成方法，具体参数如表3所示，实验中设定项的总个数是1000，最大潜在频繁项集的个数是500。

4结语

HFG算法采用散列技术，应用非频繁2项集性质进行剪枝；采用分治技术，通过将数据集进行首项分组，在每个数据子集中分别进行频繁项集挖掘，提高了Apriori算法的时间性能。HFG算法采用分组索引表存储数据子集，用索引来表示首项的子项集，避免了数据子集的重复存储。HFG算法没有复杂的理论推导，易于理解和实现，其基本思想可以移植到最大频繁项集挖掘、序列模式挖掘等领域。

参考文献：

[1]

AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules [C]// VLDB94： Proceedings of the 1994 International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann， 1994： 487-499.

[2]

HAN J， PEI J， YIN Y. Mining frequent patterns without candidate generation [C]// SIGMOD00： Proceedings of the 2000 International Conference on Management of Data. New York： ACM Press， 2000： 1-12.

[3]

LIU J Q， PAN Y H， WANG K， et al. Mining frequent item sets by opportunistic projection [C]// KDD02： Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press， 2002： 229-238.

[4]

颜跃进，李舟军，陈火旺.基于FPTree有效挖掘最大频繁项集[J].软件学报，2005，16（2）：215-222.

[5]

ZAKI M J. Scalable algorithms for association mining [J]. IEEE Transactions on Knowledge and Data Engineering， 2000， 12（3）： 372-390.