Apriori算法

“种一棵树最好的时间是十年前，其次是现在”1 数据挖掘 VS 机器学习数据挖掘是利用各种技术与统计方法，将大量的历史数据，进行整理分析，归纳与整合，是从海量数据中“挖掘”隐藏信息，如趋势、特征及相关的一种过程。数据挖掘可以视为数据库、机器学习和统计学三者的交叉。简单来说，对数据挖掘而言，数据库提供了数据管理技术，而机器学习和统计学则提供了数据分析技术。机器学习是以数据为基础，设法构建或训练出...

cdknight_happy

856人浏览 · 2018-10-30 14:23:21

cdknight_happy · 2018-10-30 14:23:21 发布

“种一棵树最好的时间是十年前，其次是现在”

1 数据挖掘 VS 机器学习

数据挖掘是利用各种技术与统计方法，将大量的历史数据，进行整理分析，归纳与整合，是从海量数据中“挖掘”隐藏信息，如趋势、特征及相关的一种过程。数据挖掘可以视为数据库、机器学习和统计学三者的交叉。简单来说，对数据挖掘而言，数据库提供了数据管理技术，而机器学习和统计学则提供了数据分析技术。

机器学习是以数据为基础，设法构建或训练出一个模型，进而利用这个模型来实现数据分析的一类技术。这个被训练出来的机器学习模型当然也可以认为是我们从数据中挖掘出来的那些潜在的、有意义的信息和知识。

数据挖掘包含了机器学习，或者说机器学习是数据挖掘的弹药库中一类相当庞大的弹药集。既然是一类弹药，其实也就是在说数据挖掘中肯定还有其他非机器学习范畴的技术存在。在非机器学习的数据挖掘技术中，我们并不会去建立一个机器学习的模型，而是直接从原数据集入手，设法分析出隐匿在数据背后的某些信息或知识。

2 频繁项集的评估标准

Aprior算法是一种不属于机器学习的数据挖掘技术，是常用的用于挖掘出数据关联规则的算法，它用来找出数据集中频繁出现的数据集合，找出这些集合的模式有助于我们做一些决策。比如在常见的超市购物数据集，或者电商的网购数据集中，如果我们找到了频繁出现的数据集，那么对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。

什么样的数据才是频繁项集呢？也许你会说，这还不简单，肉眼一扫，一起出现次数多的数据集就是频繁项集吗！的确，这也没有说错，但是有两个问题，第一是当数据量非常大的时候，我们没法直接肉眼发现频繁项集，这催生了关联规则挖掘的算法，比如Apriori, PrefixSpan, CBA。第二是我们缺乏一个频繁项集的标准。比如10条记录，里面A和B同时出现了三次，那么我们能不能说A和B一起构成频繁项集呢？因此我们需要一个评估频繁项集的标准。

常用的频繁项集的评估标准有支持度和置信度。

支持度就是几个关联的数据在数据集中同时出现的次数占总数据集的比重。比如对于数据X和Y，其支持度为：
$\frac{num(XY)}{num(allSamples)}$
所有满足最小支持度阈值的项集，构成频繁项集。
置信度体现了一个数据出现后，另一个数据出现的概率，也就是条件概率。比如两个拟进行关联分析的数据X和Y，X对Y的置信度为在包含X的数据种，同时也包含Y的数据所占的比例：
$\Rightarrow Y) = P(X|Y) = \frac{num(XY)}{num(X)}$
从频繁项集种提取所有高置信度的规则，称之为强规则。

根据支持度、置信度的定义可知，任意两个实体之间如果存在强关联规则，那么一定存在于频繁项集之中，反之，如果这两个实体不存在于频繁项集，则一定不会产生强关联规则。

关联关系的挖掘就是频繁项集的挖掘，从数据集中找出超过指定阈值的频繁项集，再由频繁项集产生强关联规则。其过程为：

找出所有的频繁项集：遍历所有可能的项集，找到支持度超过指定阈值的项集组成频繁项集；
由频繁项集产生强关联规则：计算频繁项集中超出置信度阈值的规则，找到实体间的强规则。

3 暴力检索

暴力检索(Brute-force)是最容易想到的从数据中进行关联关系挖掘的方法。

格结构常被用来枚举所有可能的结构。如下图为 $I=\{A,B,C,D,E\}$ 的格项集。
在这里插入图片描述一个大小为K的数据集最多可包含 $C_K^1 + C_K^2 + \cdots + C_K^K = 2^K - 1$ 个频繁项。对于一个较大的K值进行暴力检索，数据量太大，不具备实现的可能性。

4 先验知识

上一节我们看到了暴力检索因为计算量太大，不具备实现的可能性。我们必须设法降低产生频繁项集的计算复杂度。

频繁项集挖掘过程中有几条先验知识：

如果一个集合属于频繁项集，那么它所有子集都属于频繁项集；
假如集合 ${A,B,C\}$ 出现的次数超过了指定阈值，那么 ${A,B\},\{A,C\},\{B,C\}$ 出现的次数也一定超过了指定阈值。
如果一个集合不属于频繁项集，那么它所有的超集都不属于频繁项集；
假如集合 ${A,B,C\}$ 出现的次数未超过指定阈值，那么 ${A,B,C,D\},\{A,B,C,E\}$ 出现的次数也一定不会超过指定阈值，需要进行剪枝处理。

5 Aprior原理

对于Apriori算法，我们使用支持度来作为我们判断频繁项集的标准。Apriori算法的目标是找到最大的K项频繁集。这里有两层意思，首先，我们要找到符合支持度标准的频繁集。但是这样的频繁集可能有很多。第二层意思就是我们要找到最大个数的频繁集。比如我们找到符合支持度的频繁集AB和ABE，那么我们会抛弃AB，只保留ABE，因为AB是2项频繁集，而ABE是3项频繁集。

Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度的1项集，得到频繁1项集。然后对剩下的频繁1项集进行连接，得到候选的频繁2项集，筛选去掉低于支持度的候选频繁2项集，得到真正的频繁二项集，以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。

在这里插入图片描述
我们的数据集D有4条记录，分别是134,235,1235和25。现在我们用Apriori算法来寻找频繁k项集，最小支持度设置为50%。首先我们生成候选频繁1项集，包括我们所有的5个数据并计算5个数据的支持度，计算完毕后我们进行剪枝，数据4由于支持度只有25%被剪掉。我们最终的频繁1项集为1235，现在我们链接生成候选频繁2项集，包括12,13,15,23,25,35共6组。此时我们的第一轮迭代结束。

进入第二轮迭代，我们扫描数据集计算候选频繁2项集的支持度，接着进行剪枝，由于12和15的支持度只有25%而被筛除，得到真正的频繁2项集，包括13,23,25,35。现在我们链接生成候选频繁3项集,123, 125，135和235共4组，这部分图中没有画出。通过计算候选频繁3项集的支持度，我们发现123,125和135的支持度均为25%，因此接着被剪枝，最终得到的真正频繁3项集为235一组。由于此时我们无法再进行数据连接，进而得到候选频繁4项集，最终的结果即为频繁3三项集235。

下面我们对Aprior算法流程做一个总结。

输入：数据集合D，支持度阈值α

输出：最大的频繁k项集

1）扫描整个数据集，得到所有出现过的数据，作为候选频繁1项集。k=1，频繁0项集为空集。

2）挖掘频繁k项集

a) 扫描数据计算候选频繁k项集的支持度

b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空，则直接返回频繁k-1项集的集合作为算法结果，算法结束。如果得到的频繁k项集只有一项，则直接返回频繁k项集的集合作为算法结果，算法结束。

c) 基于频繁k项集，连接生成候选频繁k+1项集。

3）令k=k+1，转入步骤2。

从算法的步骤可以看出，Aprior算法每轮迭代都要扫描数据集，因此在数据集很大，数据种类很多的时候，算法效率很低。

5 Apriori总结

Apriori算法是一个非常经典的频繁项集的挖掘算法，很多算法都是基于Apriori算法而产生的，包括FP-Tree,GSP, CBA等。这些算法利用了Aprior算法的思想，但是对算法做了改进，数据挖掘效率更好一些，因此现在一般很少直接用Aprior算法来挖掘数据了，但是理解Aprior算法是理解其它Aprior类算法的前提，同时算法本身也不复杂，因此值得好好研究一番。