频繁模式(frequent pattern)

频繁模式一般是指频繁地出现在数据集中的模式。这种频繁模式和关联规则是数据挖掘中想要挖掘的知识。我们都知道一个很有趣的故事，就是啤酒和尿布的故事，

在某些特定的情况下，“啤酒”与“尿布”两件看上去毫无关系的商品，会经常出现在同一个购物篮中，且大多出现在年轻的父亲身上。

分析背后原因是，在美国有婴儿的家庭中，一般是母亲在家中照看婴儿，年轻的父亲去超市买尿布。父亲在购买尿布的同时，往往会顺便为自己购买啤酒。

由此，沃尔玛就在卖场尝试将啤酒与尿布摆放在相同区域，让年轻的父亲可以同时找到这两件商品，并很快地完成购物，从而极大提升商品销售收入。

数据挖掘就是想要挖掘出这种有趣的模式，可以称做频繁模式和关联规则的挖掘，一般情况下使用支持度(support)和置信度(confidence)来表示关联的程度，领域的专家设置最小支持度和最小置信度阈值，如果某个模式大于最小支持度和最小置信度，就认为是频繁模式。

为了挖掘这种模式，一般常用的有两种算法:

1. Apriori
2. Fp-tree

在介绍这两个算法之前需要给出一些定义:

1. A=>B的支持度:
   upport(A=>B)=p(A\cup B) \tag{1}
2. A=>B的置信度:
   onfidence(A=>B)=P(B|A)
   \frac{support(A \cup B)}{supoort(A)}=\frac{support_count(A \cup B)}{supoort_count(A)} \tag{2}
3. 一般关联规则的挖掘有两步过程:
   • 找出所有的频繁项集: 每一个频繁出现的次数大于等于最小支持度技术min_sup.
   • 由频繁相机产生强关联规则: 这些规则必须满足最小支持度和最小置信度.

Apriori

Apriori通过限制候选产生发现频繁项集,它是为布尔关联规则挖掘频繁项集的原创性算法. 根据先验知识(频繁项集的所有非空子集也一定是频繁的).Apriri算法使用一种称为逐层搜索的迭代过程，其中k项集用于探索(k+1)项集.
Apriori主要有两步完成: 连接步和剪枝步。
这个算法给出一个例子更容易理解:

解答(详细过程请参考《数据挖掘概念与技术第三版》 p250)

FPTree

FPTree是基于频繁模式的增长，不产生候选挖掘频繁项集的挖掘方法，
使用频繁模式增长方法,我们重新考察例图6.2事务数据库 D 的挖掘。
数据库的第一次扫描与 Apriori 相同,它导出频繁项(1-项集)的集合,并得到它们的支持度计数(频繁性)。设最小支持度计数为 2。频繁项的集合按支持度计数的递减序排序。结果集或表记作 L 。这样,我们有：
L = [I2:7, I1:6, I3:6, I4:2, I5:2]。
FP-树构造如下:

1. 首先,创建树的根结点,用“null”标记。
2. 二次扫描数据库 D。每个事务中的项按 L 中的次序处理(即,根据递减支持度计数排序)并对每个事务创建一个分枝.
3. 例如,
   第一个事务“T100: I1, I2, I5”按 L 的次序包含三个项{ I2, I1, I5},导致构造树的第一个分
   枝<(I2:1), (I1:1), (I5:1)>。该分枝具有三个结点,其中,I2 作为根的子女链接,I1 链接到 I2,
   I5 链接到 I1。第二个事务 T200 按 L 的次序包含项 I2 和 I4,它导致一个分枝,其中,I2 链接到根,
   I4 链接到 I2。然而,该分枝应当与 T100 已存在的路径共享前缀。这样,我们将结点 I2 的计
   数增加 1,并创建一个新结点(I4:1),它作为(I2:2)的子女链接。一般地,当为一个事务考虑增加
   分枝时,沿共同前缀上的每个结点的计数增加 1,为随在前缀之后的项创建结点并链接。
4. 为方便树遍历,创建一个项头表,使得每个项通过一个结点链指向它在树中的出现。扫描所有
   的事务之后得到的树展示在图 6.8 中,附上相关的结点链。这样,数据库频繁模式的挖掘问题就转换成挖掘 FP-树问题.
   
5. 根据fp tree得到频繁项集，根据支持度计数依次考虑每一个满足的元素，首先考虑计数最小的ID I5. 从根节点遍历所有到I5的路径，记录这个路径作为条件模式基,之后根据最小支持度得到条件Fp-tree，最后产生频繁项集. 具体的操作表格如下:
   

注: 详细见数据挖掘概念与技术第6章

核心公式

1. 如何评估哪些模式是有趣的?

相关规则是A=>B[support, confidence]进一步扩充到相关分析A=>B[support, confidence, correlation]，
常用的相关性度量:

• 提升度(lift),计算公式如下:

lift(A,b)=\frac{p(A \cup B)}{p(A)p(B)}=\frac{P(B|A)}{p(B)}=\frac{conf(A=>B)}{sup(B)} \tag{3}

• 使用\chi^2进行相关分析

2. 常用的模式评估度量

• 全置信度(all_confidence)

all_conf(A,B)=\frac{A \cup B}{max\{sup(A),sup(B)\}}=min\{p(A|B),p(B|A)\} \tag{4}

• 最大置信度(max_confidence)

max_conf(A,B)=max\{P(A|B),p(B|A)\} \tag{5}

• Kulczynski(Kulc)度量

Kulc(A,B)=\frac{1}{2}(P(A|B)+P(B|A)) \tag{6}

• 余弦度量

cosine(A,B)=\frac{P(A\cup B)}{\sqrt{P(A) \times P(B)}}=\frac{sup(A \cup B)}{\sqrt{(sup(A) \times sup(B))}}=\sqrt{P(A|B)\times P(B|A)} \tag{7}

对于指示有趣的模式联系，全置信度、最大置信度、Kulczynsji和余弦哪个最好? 为了回答这个问题，引进不平衡比(Imbalance Ratio, IR)

算法十问

1. 强规则一定是有趣的吗?

不一定，规则是否有兴趣可能用主观或客观的标准来衡量。最终,只有用户能够确定规则是否是有趣的,并且这种判断是主观的,因不同用户而异。

2. 如何提高Apriori算法的效率?

• 事务压缩(压缩进一步迭代扫描的事务数):不包含任何 k-项集的事务不可能包含任何(k+1)-项集。这样,这种事务在其后的考虑时,可以加上标记或删除,因为为产生 j-项集(j > k),扫描数据库时不再需要它们。
• 基于散列的技术(散列项集计数):一种基于散列的技术可以用于压缩候选 k-项集 Ck (k >1)。
  划分(为找候选项集划分数据):可以使用划分技术,它只需要两次数据库扫描,以挖掘频繁项集。
• 选样(在给定数据的一个子集挖掘):选样方法的基本思想是:选取给定数据库 D 的随机样本 S,然后,在 S 而不是在 D 中搜索频繁项集。用这种方法,我们牺牲了一些精度换取了有效性。
• 动态项集计数(在扫描的不同点添加候选项集):动态项集计数技术将数据库划分为标记开始点的块。

3. Apriori算法的优缺点?

1. 优点：

• 简单、易理解
• 数据要求低。

2. 缺点：

• 在每一步产生候选项目集时循环产生的组合过多，没有排除不应该参与组合的元素。
• 每次计算项集的支持度时，都对数据库中的全部记录进行了一遍扫描比较，如果是一个大型的数据库时，这种扫描会大大增加计算机的I/O开销。

3. 改进:

• 利用建立临时数据库的方法来提高Apriori算法的效率。
• Fp-tree 算法。以树形的形式来展示、表达数据的形态；可以理解为水在不同河流分支的流动过程。
• 垂直数据分布。相当于把原始数据进行行转列的操作，并且记录每个元素的个数。

4. FPtree vs Apriori算法

FP-tree算法相对于Apriori算法，时间复杂度和空间复杂都有了显著的提高。但是对海量数据集，时空复杂度仍然很高，此时需要用到数据库划分等技术。

面试真题

1. 简述Apriori算法的思想，谈谈该算法的应用领域并举例?
   思想：其发现关联规则分两步，第一是通过迭代，检索出数据源中所有烦琐项集，即支持度不低于用户设定的阀值的项即集，第二是利用第一步中检索出的烦琐项集构造出满足用户最小信任度的规则，其中，第一步即挖掘出所有频繁项集是该算法的核心，也占整个算法工作量的大部分。在商务、金融、保险等领域皆有应用。在建筑陶瓷行业中的交叉销售应用，主要采用了Apriori算法.

2. 简述FPtree的原理和Apriori的不同?

3. 豆瓣电影数据集关联规则挖掘?
   如果让你分析电影数据集中的导演和演员信息，从而发现两者之间的频繁项集及关联规则，你会怎么做？

参考

1. https://saliormoon.github.io/2016/07/01/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E9%9D%A2%E8%AF%95%E9%97%AE%E9%A2%981/
2. 数据挖掘概念与技术第三版
3. https://baijiahao.baidu.com/s?id=1607039314145277013&wfr=spider&for=pc