频繁项集Apriori算法

频繁模式和对应的关联或相关规则在一定程度上刻画了属性条件与类标号之间的有趣联系，因此将关联规则挖掘用于分类也会产生比较好的效果。apriori

关联规则就是在给定训练项集上频繁出现的项集与项集之间的一种紧密的联系。其中“频繁”是由人为设定的一个阈值即支持度 （support）来衡量，“紧密”也是由人为设定的一个关联阈值即置信度（confidence）来衡量的。这两种度量标准是频繁项集挖掘中两个至关重 要的因素，也是挖掘算法的关键所在。对项集支持度和规则置信度的计算是影响挖掘算法效率的决定性因素，也是对频繁项集挖掘进行改进的入口点和研究热点。

基于关联规则的分类主要分为以下以个步骤：

1. 对训练数据进行预处理（包括离散化、缺失值处理等）

2. 关联规则挖掘

2.1 频繁项集挖掘

2.2 关联规则生成

3. 规则处理

4. 对测试集进行测试

二、频繁项集挖掘

目前频繁项集挖掘已经有很多比较成熟的算法，在网上也可以找到相关的优秀论文或源代码。算法中最经典的莫过于Apriori算法，它可以算得上是频 繁项集挖掘算法的鼻祖，后续很多的改进算法也是基于Apriori算法的。但是遗憾的是Apriori算法的性能实在不咋的，当当玩具玩玩还可以，但是即 使如此，该算法却是频繁项集挖掘必须要掌握的入门算法。

题外话：关健是要了解算法的思想，你可以不了解一个东西是怎样具体实现的，但是一定得了解它是如何出来的。这样遇到相关的问题，你可以有一个参考的 解决方法，或者在关键时刻可以跟别人忽悠忽悠。当然，了解思想的最佳途径就是自己动手去实现实现了，哪怕实现得不咋样，起码思想掌握了，也是个不小的收 获。

下面就要具体介绍如何利用Apriori算法进行频繁项集挖掘了。

（1）相关概念

项集：“属性-值”对的集合，一般情况下在实际操作中会省略属性。

候选项集：用来获取频繁项集的候选项集，候选项集中满足支持度条件的项集保留，不满足条件的舍弃。

频繁项集：在所有训练元组中同时出现的次数超过人工定义的阈值的项集称为频繁项集。

极大频繁项集：不存在包含当前频繁项集的频繁超集，则当前频繁项集就是极大频繁项集。

支持度：项集在所有训练元组中同时出现的次数。

置信度：形如A->B，置信度为60%表示60%的A出现的同时也出现B。

k项集：项集中的每个项有k个“属性-值”对的组合。

（2）两个定理

i：连接定理。若有两个k-1项集，每个项集按照“属性-值”（一般按值）的字母顺序进行排序。apriori如果两个k-1项集的前k-2个项相同，而最后一 个项不同，则证明它们是可连接的，即这个k-1项集可以联姻，即可连接生成k项集。使如有两个3项集：｛a, b, c｝{a, b, d}，这两个3项集就是可连接的，它们可以连接生成4项集｛a, b, c, d｝。又如两个3项集｛a, b, c｝｛a, d, e｝，这两个3项集显示是不能连接生成3项集的。要记住，强扭的瓜是不甜的，也结不了果的。

ii：频繁子集定理。若一个项集的子集不是频繁项集，则该项集肯定也不是频繁项集。这个很好理解，举一个例子，若存在3项集｛a, b, c｝，如果它的2项子集｛a, b｝的支持度即同时出现的次数达不到阈值，则｛a, b, c｝同时出现的次数显然也是达不到阈值的。因此，若存在一个项集的子集不是频繁项集，那么该项集就应该被无情的舍弃。倘若你舍不得，那么这个项集就会无情 的影响你的效率以及处理器资源，所以在这时，你必须无情，斩立决！

（3）Apriori算法流程

1. 扫描，生成候选1项集和频繁1项集。

2. 从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-62906-1.html