频繁项集挖掘算法的优化

2025-09-29 历史故事版权反馈

【摘要】：在所有可能的项集中，有很多候选都不是频繁的。算法4.2Apriori算法伪代码FPGrowth方法使用一种增强的前缀树对数据D进行索引，以实现快速的支持度计算。FPGrowth将所有的项按照支持度的降序排列。FP树构建完成后，所有的频繁项集就可以从树中挖掘出来。基于频繁树模式的频繁集搜索方法见算法4.3。算法4.3FPGrowth算法伪代码

频繁项集是指支持度大于等于最小支持度(minsup)的集合(颜跃进等，2004)，频繁项集挖掘的主要步骤为:①候选生成，在集合I中，每一个项集都可能是频繁模式，候选项集的搜索空间是指数式的；②支持度计算，计算每个候选模式X并判定它是否为频繁的。

在所有可能的项集中，有很多候选都不是频繁的。令X，Y⊆I为任意两个项集，若X⊆Y，则sup(X)≥sup(Y)，由此可得:①如果X是频繁的，则其任意子集Y⊆X也是频繁的；②如果X不是频繁的，则其任意超集Y⊇X都不是频繁的。

Apriori方法利用以上两个性质，采用逐层或宽度优选的方法来访问项集搜索空间，并修剪掉所有非频繁候选的超集，因为非频繁项集的超集都是非频繁的，这就避免了生成含有非频繁项子集的候选。

除了通过项集剪枝来改进候选的生成步骤，Apriori方法同样大大降低了I/O复杂性，它对前缀进行深度优先搜索，并计算所有大小为k的有效候选(即构成了前缀树的第k层)的支持。

计算流程见算法4.2中伪代码。令C(k)代表包含所有k-项集的前缀树。首先将单个项插入一个初始为空的前缀树，得到C(1)。while循环(第5～11行)通过生成D中每个事务的k-子集，对每个这样的子集，对C(k)中的对应候选(如果存在)的支持度加1，从而实现第k层支持的度的计算。通过这种方式，在每一层都只会扫描一次，并且在扫描的过程中对所有候选k－项集的支持度进行增量。接下来，移除任意的非频繁候选(第9行)。剩余的前缀的叶子就构成了频繁k-项集的集合F(k)，然后可用于下一层的候选(k＋1)－项集(第10行)。

算法4.2　Apriori算法伪代码(https://www.chuimin.cn)

FPGrowth方法使用一种增强的前缀树对数据D进行索引(冯晓龙等，2018)，以实现快速的支持度计算。树中的每个节点都用单个项标注，每一个子节点代表一个不同的项，每个节点同时存储了从根节点到它路径上的项，从而构成项集的支持度信息。

FP树按照以下方式构建:树的根初始化为空项∅。对于每一个＜t，X＞∈D，其中X＝i(t)，将项集X插到FP树，代表X的路径上的所有节点的计数值都加1。若X与某些之前插入的事务共享前缀，则在整个共同前缀上，X会遵循相同的路径。对于X中剩余的项，在共同前缀下创建新的节点(计数初始化为1)。当所有事务都插入之后，FP树就构建完成了。

FPGrowth将所有的项按照支持度的降序排列。首先计算所有单项i＝I的支持度；然后，丢弃非频繁的项，并对频繁项按支持度值降序排列；最后，每个元组＜t，X＞∈D都插到FP树中(X中的项按照支持度降序重新排列)。FP树构建完成后，所有的频繁项集就可以从树中挖掘出来。

基于频繁树模式的频繁集搜索方法见算法4.3。当FP树是多条路径时，枚举所有路径子集的项集，且每个项集的支持度等于其中最不频繁项的支持度值(第2～6行)。当FP树是单一路径时，按照支持度的升序为其中的每一个频繁项i建立投影FP树。产生FP树是当前前缀和项i的项集X的投影(第9行)。找到树中所有i的出现，对于每一个出现，确定其对应的从根到i的路径(第13行)。一个给定路径中的项i的计数存在于cnt(i)中(第14行)，并将该路径插到新的投影树RX，其中X是对前缀P新增项i得到的项集。然后，以FP树RX和新的前缀集X作为参数，递归调用FPGrowth。

算法4.3　FPGrowth算法伪代码

频繁项集挖掘算法的优化

相关推荐