频繁项集

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

常用的频繁项集的评估标准有支持度,置信度和提升度三个。

支持度

支持度就是几个关联的数据在数据集中出现的次数占总数据集的比重。或者说几个数据关联出现的概率。如果我们有两个想分析关联性的数据 $X$ 和 $Y$ ，则对应的支持度为：

$\text{Support}(X,Y)=P(XY)=\frac{\#(XY)}{\#(\text{all samples})}$

以此类推，如果我们有三个想分析关联性的数据 $X$ ， $Y$ 和 $Z$ ，则对应的支持度为：

$\text{Support}(X,Y,Z)=P(XYZ)=\frac{\#(XYZ)}{\#(\text{all samples})}$

一般来说，支持度高的数据不一定构成频繁项集，但是支持度太低的数据肯定不构成频繁项集。

置信度

置信度体现了一个数据出现后，另一个数据出现的概率，或者说数据的条件概率。如果我们有两个想分析关联性的数据 $X$ 和 $Y$ ， $X$ 对 $Y$ 的置信度为

$\text{Confidence}(X\Leftarrow Y)=P(X|Y)=\frac{P(XY)}{P(Y)}=\frac{\#(XY)}{\#(Y)}$

以此类推到多个数据的关联置信度，比如对于三个数据 $X$ ， $Y$ ， $Z$ ，则 $X$ 对于 $Y$ 和 $Z$ 的置信度为：

$\text{Confidence}(X\Leftarrow YZ)=P(X|YZ)=\frac{P(XYZ)}{P(YZ)}=\frac{\#(XYZ)}{\#(YZ)}$

举个例子，在购物数据中，纸巾对应鸡爪的置信度为40%，支持度为1%。则意味着在购物数据中，总共有1%的用户既买鸡爪又买纸巾；同时买鸡爪的用户中有40%的用户购买纸巾。

提升度

提升度表示含有 $Y$ 的条件下，同时含有 $X$ 的概率，与 $X$ 总体发生的概率之比，即：

$\text{Lift}(X\Leftarrow Y)=\frac{P(X|Y)}{P(X)}$

Apriori

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

找到支持度大于 $\sigma_{threshold}$ 的项集，若 $s({a,b})<\sigma_{threshold}$ 了，那 $s(a,b,c)$ 更小，所以 $(a,b,c)$ 不可能是频繁项集，所以就不用计算了。反之， $s(a,b,c)\geq \sigma_{threshold}$ 那肯定 $s(a,b)\geq \sigma_{threshold}$ 。Apriori就基于此思想迭代和剪枝

扫描数据库，生成高频1-项集(只有1项的)
while:
     根据上一轮k-项集生成(k+1)-项集作为候选集
     扫描数据库测试生成的(k+1)-项集候选集是否高频(这里构造时，新加的项必须也满足支持度)
     k = k+1
     Until: 没有大于阈值的 或 没有新候选集可生成
return: 返回所有满足频繁项集