数据挖掘笔记（三）

---

频繁模式(frequent-itemsets)

---

• 基本概念

（1）频繁项集 ：反映了在数据集中频繁出现的模式
（2）在购物篮分析中，在通过对大数据中各项之间的深入挖掘与研究，则能够揭示出各项之间存在的内在联系及其相互作用机制，在这些发现对于优化企业运营策略、制定精准营销方案以及提升客户满意度具有重要意义；实际上，在这一过程中所进行的数据采集与整理工作，则是为了全面了解客户群体的行为特征及其消费偏好。

（1）置信度 confidence(A → B)，即事件A与B同时发生的概率；
（2）confidence(A → B)=probability of event A occurring given that event B has occurred= support ratio= occurrence count of the union of events A and B divided by total occurrences；
（3）minimum support threshold；
（4）minimum confidence threshold。

（4）满足最小支持阈值 和最小置信度阈值 的关联规则被称为强关联规则 。
（5）k- itemset （k项集），例如{a,b}就是一个典型的2- itemset。
（6）itemsets的发生频率是指包含该itemsets的transaction数量；这一概念也被称为项目集的支持计数或发生次数。
（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}必然也是高频的
（2）第二步则是利用这些高频项集生成关联规则
（3）详细步骤如下：
首先从单个项目开始考察
然后逐步考虑多项目组合的情况
最终得出所需的所有关联规则

例子：
考虑一个由6个事务构成的数据集合，并设定其最小支持度为2（即约为2/9或约22.2%），同时将置信度阈值设为70%。

第一步：
构建候选1-项目集合并将其与预设的支持率阈值进行对比以获取1-项目频繁集合。

第二步：
计算所有候选1-项目集合中的事务子集及其对应的支持率。

第三步：
剔除那些不符合最低支持率要求的支持率低于阈值的目标事务子集。

第四步：
从剩余的目标事务子集中提取所有可能的关联式模式。

第五步：
对于每一个组合模式计算其相应的信心水平。

第六步：
筛选出信心水平高于预设最低信心水平的所有关联式模式。

第七步：
获得最终的所有关联式集合。

第二步首先进行L1自联结操作生成C2集合。
随后遍历数据集D并计算其支持计数。
最终得出所有候选项集直至当前步骤尚未利用任何先验属性。

第三步：L2自连接，并基于Apriori属性执行剪枝操作（例如，在\{l_2, l_3, l_5\}中找到一个子集\{l_3, l_5\}并不属于L_2集合（即不具备频繁项集属性），因此相应的\{l_2, l_3, l_5\}被移除于C_3列表中）。接着对数据集D中的所有事务进行遍历扫描以便识别出满足条件的候选项

第四步：基于Apriori属性：任何高频项群的所有子群必然也是高频的 ，因此我们可以确认四个字母候选项不会成为高频群。
第五步：基于高频项群生成关联规则

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

对于I的所有非空子集S，在满足支持计数比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-树只有一条路径）。
（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

（3）FP-tree的优缺点

（1）优点：

（1）仅在数据集中执行了两步操作
（2）一定程度地减少了数据集的规模
（3）未生成候选集
（4）该算法相较于Apriori方法表现出显著的优势

（2）缺点：

（1） fp 树 不适合 存储 在内存中。
（2） 对于 fp 树 而言 ，构建耗费高昂 。
（权衡在于构建过程耗时 ，但 一旦 构建完成 ，频繁查询项目集变得容易；时间 是 浪费 的 （ 尤其 是 当 min_upp 较高时 ）， 因为 剪枝只能在单个项目上实施；仅在将所有数据加载进 fp 树 后 才能 计算其 支持 度 ）。

• 频繁模式的评价方法

强关联规则并非一定局限于感兴趣的领域。

该关联规则表现出很强的效果，并且实际独立概率仅为75%，这一数值甚至达到了或超过了60%的水平。实际上，在这种情况下（即电脑游戏与视频之间），两者呈现出负相关关系的原因在于：购买其中一个项目会降低对另一个项目的采购概率。

（1）相关性测量( A -> B [support, confidence, correlation])：

（1）Lift（ lift值=1表示A和B是独立的，>1表示正相关，<1表示负相关 ）

（2）Chi-square measure卡方测试