数据挖掘笔记（三）

频繁模式(frequent-itemsets)

基本概念

（1）频繁项集：频繁项集是经常出现在数据集中的模式
（2）购物篮分析：频繁项集的挖掘可以发现大数据集中项之间的关联和相关性。这有助于许多业务决策过程，如菜单设计、交叉营销和客户购物行为分析。购物篮分析就是分析客户的购买习惯。

（1）支持度 support(A -> B) = P ( AUB )
（2）置信度 confidence(A -> B) = P (A | B) = support(A -> B)/support(A) = support_count( AUB ) /support(A)
（3）最小支持阈值
（4）最小置信阈值

（4）同时满足最小支持阈值和最小置信度阈值的关联规则就称为强关联规则。
（5）k-itemsets （k项集），比如{a，b}就是一个2-itemsets
（6）itemsets的出现频率是包含itemsets的transaction数,也称为项目集的 frequency,、support count或 count .
（7）如果一个项集满足一个预定义的最小支持阈值，那么它就是一个频繁项集。
（8）关联规则挖掘分两步：

（1）查找所有频繁项集(大部分计算成本来自此步骤)
（2）从频繁项集中生成关联规则

（9）几个概念：

（1）超集：有项集S1={a,b}，那么它是项集{a}{b}的超集；{a}{b}是S1的真子集。
（2）最大频繁项集：如果频繁项集L的所有超集都是非频繁项集，那么称L为最大频繁项集或称最大频繁模式，记为MFI (Maximal Frequent Itemset)。
（3）闭项集：称X是数据集D上的闭项集，当且仅当没有合适的超项集Y有与X相同的支持计数。
（4）项目集X是D中的闭频繁项集，如果X在D中同时是闭的和频繁的。
（5）举例：最大频繁项集和频繁闭项集之间的区别：假如现在频繁阈值是3。有10个事例里都有“花生-啤酒”，而且这10个事例没有其它共同项，那么“花生-啤酒”就是一个频繁闭项集，因为它首先是闭项集（没有总是跟它们同时出现的其它项），然后也满足频繁阈值。在10个事例里其中有5个同时也有“饼干”，因此“花生-啤酒-饼干”也是频繁集，因为“花生-啤酒-饼干”是“花生-啤酒”的超集，所以“花生-啤酒”不是最大频繁集。至于“花生-啤酒-饼干”是不是最大频繁集，那要看有没有它的超集满足频繁阈值，没有的话它就是最大频繁集。
（比如{a,b,c}出现了10次，没有它的超集等于10次的了，则{a,b,c}为频繁闭项集，但是有{a,b,c,d}出现了5次，最小支持阈值为4，则{a,b,c,d}也是频繁项集，若没有它的超集满足频繁阈值，则它就是最大频繁集）
模式的数目：最大频繁集<频繁闭项集<频繁项集，不过最大频繁集丢失了很多信息，比如可能在买“花生-啤酒-饼干”的人群中，还有一部分是买洗发水的，数目也达到了频繁项阈值，那么“花生-啤酒-饼干-洗发水”就是“花生-啤酒-饼干”的一个超集，所以“花生-啤酒-饼干”这个集合的独特性就不会在频繁最大集里体现；而频繁闭项集实际上还保留着频繁项集的信息，可以继续拆分为原来的频繁项集。
D为数据集，C为频繁闭项集，M为最大频繁集。

频繁项集挖掘方法

（1）Apriori Algorithm

基本概念：该方法在1994年由Agrawal 和Srikant提出
（1）找到满足最小支持度的频繁项集
①Apriori 属性：频繁项集的子集也一定是频繁的，例如{a,b}是频繁的，则{a}和{b}都应该是频繁的。
②迭代寻找基数从1到k的频繁项集(Kitemset)
（2）使用频繁项集生成关联规则
（3）步骤：

例子：给出一个有6个事务组成的数据集，设定最小支持度为2（2/9，22%），最小置信度为70%

第一步：构建1-候选项集与最小支持度比较，构建1-频繁项集

第二步：L1自连接形成C2，扫描D获得支持数，获得2-频繁项集（直到2此步还未曾使用先验属性）

第三步：L2自连接，使用Apriori属性进行剪枝（比如{l2,l3,l5}的子集{l3,l5}不是L2的成员即不是频繁项集，所以{l2,l3,l5}从C3删去），对D中的事务进行扫描，以确定L3

第四步：根据Apriori属性: 一个频繁项集的所有子集也必须是频繁的，我们可以确定四个字母候选项不可能是频繁的。

第五步：从频繁项集生成关联规则

（1）对于每一个频繁项集I，生成I的所有非空子集

（2）对于I的每一个非空子集S，如果support_count( I ) / support_ count( s ) >= min_confidence

则输出关联规则S->(I-S)

Apriori方法的效率改进：

（2）Pattern Growth Approach

（1）概念：无需生成候选集即可发现频繁项集

2步方法：
（1）构建一个紧凑的数据结构，叫做FP-tree
（2）直接从FP-tree中提取频繁项集

FP-tree的大小：

（1）FP-树通常比未压缩数据的大小更小，因为通常许多事务共享项(前缀)。
（2）最好的场景：所有事务都包含相同的项集。（fp-树只有1条路径）
（3）最坏的情况：每个事务都有一组唯一的项(没有共同的项)。（fp树的存储要求更高，因为需要在节点和计数器之间存储指针。）
（4）fp树的大小取决于item的排序方式。根据支持数的降序排序通常是可用的，但不一定生成最小的树（启发式的）

（2）从fp树提取频繁项集

（1）分而治之（Divide and conquer）：首先寻找以e结尾的频繁项集，然后寻找de结尾等等，再找以d结尾的，然后cd等等

（2）首先从生成的FP树中提取以某一个项结尾的子树（比如以e结尾的）

（3）通过在链接列表(虚线)上添加计数来检查e是否是一个频繁项。如果是的话，就把它提取出来。

（4）由于e是频繁的，查找以e结尾的频繁项集，即de、ce、be和ae。即构建以e结尾的条件FP树。使用e的条件fp-树查找以de、ce和ae结尾的频繁项集。注意be不被考虑，因为b在e的条件FP树中计数为1，是非频繁的。递归计算e->de->ade