一、基本概念
（一）基本概念
二元概念
对于购物篮数据，使用二元变量表示。1表示购买，0表示没有购买。
项集和支持度计数
事务：一行数据。
k-项集：一个事务中，出现项。如：3-项集，{啤酒，尿布，牛奶}
支持度计数：
$$\sigma (X)=|\left \{ t_{i}|X\subseteq t_{i},t_{i}\in T \right \}|$$
如，上式中，项集{啤酒，尿布，牛奶}的支持度计数为2，因为只有2个事务同时包含3个项。
关联规则（association rule）
关于 X、Y 的关联规则，支持度、置信度的定义如下：
$$s(X\rightarrow Y)=\frac{\sigma (X\cup Y)}{N}$$
$$s(X\rightarrow Y)=\frac{\sigma (X\cup Y)}{\sigma (X)}$$
例如：X{牛奶，尿布}，Y{啤酒}，则并集{牛奶，尿布，啤酒}的支持度计数为2，N为事务总数5，所以支持度=2/5=0.4。X 的支持度=3，所以置信度为2/3=0.67。
支持度很低的规则可能只是偶然出现，低的支持度计数也是无意义的。支持度通常用于删去无意义的规则，
置信度越高，表示Y在包含X的事务中出现的可能性较大。Y也可以用于估计在给定X的条件下的条件概率。
（二）关联规则挖掘
1、频繁项集产生：发现满足最小支持度阈值的所有项集，这些项是频繁项集。
2、规则产生：从频繁项集中提取所有高置信度规则，这些规则是强规则。
（三）频繁项集的产生
格结构（lattice structure）：
原始方法：
遍历每个项集，使用项集与事务进行比较，计算每个项集的支持度计数。但是该方法的算法复杂度很高：O(NMw)。
改进方法：
1、减少候选项的数目。先验原理，不计算支持度而删除某些候选项集。
2、减少比较次数。更高级的数据结构。
先验原理
先验原理：如果一个项集是频繁的，则它的所有子集也一定是频繁的。
相反的，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的。
支持度计数的反单调性：一个项集的支持度不会超过它的子集的支持度。
（四）Apriori 算法的频繁项集产生
过程图：
算法的流程：
算法讲解：
1、先定一个阈值k。
2、候选项集为1-项集的，计算支持度，若支持度大于阈值，则保留；若小于则剔除。
3、使用(k-1)-项集，产生k-项集。
4、重复上面的步骤，直到无候选集（频繁集），结束。
1、Apriori 算法：
|
|
2、Apriori_gen方法：
F(k-1)*F(1)方法
F(k-1)*F(k-1)方法
原理：使用了字典序，例如：算法不会合并{啤酒，尿布}{尿布，牛奶}，因为如果{啤酒，尿布，牛奶}有效，则它应该由{啤酒，尿布}{啤酒，牛奶}合并。
支持度计数
支持度计数在apriori_gen函数的候选项保留下来的之中计算。
一种枚举方法是：
每项都以字典序排列，按照上面的枚举。
使用hash树进行支持度计数
[略]
计算复杂度
[略]
二、规则产生
（1）基于置信度的剪枝
定理
如果 X->Y-X 不满足置信度阈值，则X’->Y-X’ 的规则一定不满足置信度阈值，其中，X’ 是 X 的子集。
（2）Apriori 规则产生
可以利用上面的定理进行剪枝，如左边的bcd->a不满足置信度阈值，则下面的都减去：
算法
三、频繁项集的紧凑表示
（1）极大频繁项集
极大频繁项集（maximal frequent itemset）：它的直接超集都不是频繁的，频繁项集。
如上图，{ad}、{ace}、{bcde} 均是极大频繁项集。
（2）闭频繁项集
闭项集（closed itemset）：项集X是闭的，如果它的直接超集都不具有和它相同的支持度计数。
如上图，{b}{ad}都不是闭项集，而{bc}是闭项集。
闭频繁项集（closed frequent itemset）一个项集是闭频繁项集，它是闭的，并且它的支持度计数大于或等于最小支持度阈值。
计算闭频繁项集的支持度算法：
项集之间的关系：
四、产生频繁项集的其他方法
[略]
五、FP增长算法
[略]
六、关联模式的评估
（1）兴趣度的客观度量
支持度-置信度框架的局限性
[略]
兴趣因子
[略]
相关分析
[略]
IS度量
[略]
1、其他客观度量
度量分为对称和非对称：
对称：M(A->B)=M(B->A)。用于评价项集。
非对称：M(A->B)!=M(B->A)。用于分析关联规则。
对称度量：
非对称度量：
2、客观度量的一致性
上面提到的一系列的度量，不一定都是一致的，需要具体分析。
3、客观度量的性质
[略]
[后略]
