基于多支持度的增量式关联规则挖掘算法.docx

基于多支持度的增量式关联规则挖掘算法
摘要：
关联规则挖掘是数据挖掘领域的重要内容，旨在从大量数据中发现特定项目之间的关联规律，是一项有效的分析数据的方法。近年来，随着数据量和数据维度的不断增加，如何快速而准确地挖掘关联规则成为了研究的热点。本文介绍了一种基于多支持度的增量式关联规则挖掘算法，它可以在大规模的数据集上进行高效的挖掘。具体地，本算法通过将支持度的计算和关联规则的挖掘分离，实现对支持度计算的增量更新，并结合了多支持度的思想，挖掘出多个支持度级别下的最大频繁项集。实验结果表明，本算法具有较好的效果和性能。
关键词：关联规则挖掘；多支持度；增量式；频繁项集
引言
关联规则挖掘是数据挖掘领域中一项重要的任务，旨在从大量数据中发现项目之间的关联规律。常见的关联规则有若干前提项决定若干结论项，如“购买尿布”的前提项是“购买啤酒”，则可以推出“购买尿布+购买啤酒”的结论项。关联规则不仅可以用于分析销售数据，还可以用于网站推荐、异常检测等领域。
在挖掘关联规则时，常用的算法有Apriori算法、FP-growth算法等。然而，这些算法在面对大规模数据集时，效率较低，需要较大的计算资源和时间。此外，对于已经被保存的数据集进行更新或增加时，需要重新进行一遍全量挖掘，增量更新效率低下。因此，研究一种高效的增量式挖掘算法是非常有意义的。
多支持度是一种使用多个支持度阈值进行关联规则挖掘的方法，可以减少噪声数据的影响，提高挖掘的准确性。该方法结合了Apriori算法和FP-growth算法的优点，可以在大数据量下进行高效挖掘。本文基于多支持度的思想，设计了一种增量式关联规则挖掘算法。
本文的组织机构如下：第二部分介绍相关工作；第三部分阐述本文算法的设计和实现；第四部分是实验结果和讨论；最后是结尾和展望。
相关工作
Apriori算法
Apriori算法是一种基于频繁项集的关联规则挖掘算法，流程如下：
1.扫描数据集，获取频繁项集的1-项集；
2.以频繁项集的1-项集作为基础，不断扩展，挖掘出频繁项集2-项集、3-项集等；
3.给定支持度和置信度阈值，从频繁项集中挖掘出符合条件的关联规则。
Apriori算法的主要瓶颈在于频繁项集的挖掘速度较慢，在处理大量数据时，计算复杂度较高，因此需要进行优化，如候选项集剪枝等。
FP-growth算法
FP-growth算法是基于FP树的关联规则挖掘算法，是一种优化后的算法。它将完整数据集递归地建立成一棵FP树，然后挖掘每个子树的频繁项集，最终将这些项集合并，得到原始数据集的所有频繁项集。相较于Apriori算法，FP-growth算法的优点在于用某一次扫描数据就构建了FP树，从而减少了扫描数据的次数。
多支持度
多支持度是一种使用多个支持度进行关联规则挖掘的方法，用来控制噪声数据对挖掘结果的影响。多支持度需要设置多个支持度阈值，挖掘结果中的频繁项集需要满足多个支持度阈值中的任意一个。这样，对于噪声数据而言，即使在某个支持度阈值下满足频繁项集的条件，但在其他支持度阈值下情况可能并不一样，从而减少了误判的情况。同时，多支持度方法也可以提高挖掘结果的准确率。
本文算法的设计和实现
算法流程
本文算法的流程如下：
1.初始时，对数据集进行一次完整的扫描，并生成1-项集；
2.对于新增数据，根据已有的1-项集，更新1-项集的支持度；
3.根据1-项集生成2-项集，3-项集等，挖掘出所有的频繁项集；
4.给定多个支持度阈值，在所有生成的频繁项集中选择符合多个支持度阈值的频繁项集；
5.根据符合条件的频繁项集，挖掘关联规则。
具体实现
该算法的主要实现在支持度的增量更新和多支持度方法的选择上。
支持度的增量更新
支持度的增量更新实现如下：
1.对于新增数据d，计算它对所有1-项集的影响，如果属于某个1-项集的成员，则将该1-项集的支持度加1；
2.对于已经更新过的1-项集，计算它们对新数据的影响，如果属于该成员，则将该1-项集的支持度加1。
在此基础上，对于生成的2-项集、3-项集等频繁项集，同样进行支持度的增量更新，减少了重新计算支持度的次数，提高了效率。
多支持度方法的选择
多支持度方法的选择依据如下：
1.根据给定的支持度阈值列表，将所有的频繁项集按照支持度递增排序。
2.遍历按照支持度排好序的频繁项集，挑选出满足某个支持度阈值条件的频繁项集，加入到挖掘结果中。
3.对于还未挑选的频繁项集，如果剩余的支持度阈值中有可以使用的，继续挑选，直到所有阈值均已使用为止。
实验结果和讨论
本文算法的实验数据是公开数据集，包含了约500万条销售数据和100万条网站浏览数据。实验环境为IntelCorei72.4GHz处理器和16GB内存的PC。
实验结果表明，本算法在处理大规模数据集上具有较好的性能和效果。在数据量较小的