购物篮分析：通过搜索经常一起（或依次）购买的商品的集合，研究顾客的购买习惯。

啤酒-尿布：沃尔玛行分析了多年来的事务数据，发现在周末晚上啤酒与尿布常常被一起购买，因此改变商品摆放方式，将两商品放在一起。结果啤酒与尿布的销售量大增。

1. 基本概念

频繁模式（frequent pattern）是频繁出现在数据集中的模式（如项集、子序列或子结构）。

• 频繁项集：频繁同时出现在交易数据集中的商品（牛奶、面包）的集合
• 频繁序列模式：一个子序列，首先购买PC，然后是数码相机，再后是内存卡，频繁出现在购物历史数据库中
• 频繁结构模式：一个子结构（如子图、子树或子格）频繁出现

规则的支持度（support）和置信度（confidence）是规则兴趣度的两种度量，分别反应了所发现规则的有用性和确定性。

$$support(A\Rightarrow B)=P(A\cup B)$$$$confidence(A\Rightarrow B)=P(B\mid A)=\frac{\mid A\cup B\mid }{\mid A\mid }$$

关联规则（association rule）被认为是有趣的（强规则），如果同时满足最小支持度阈值（min_sup）和最小置信度阈值（min_conf）。阈值可以由用户或领域专家设定。

关联规则的两个步骤:

• 找出所有的频繁项集：每一个项集出现的次数满足最小支持度阈值min_sup。
• 由频繁项集产生强关联规则：每个规则必须满足最小置信度阈值。
  还可以进一步进行关联分析，发现项集之间具有统计相关性的相关规则。

2. 主要算法

2.1 Apriori

Apriori算法由Agrawal和R.Srikant于1994年提出，使用频繁项集性致的先验知识。

先验性质（Apriori property）：频繁项集的所有非空子集也一定是频繁的。该性质属于一类特殊的性质，称为反单调性（antimonotone），指如果一个集合不能通过测试，则它所有超集也都不能通过相同的测试。

在第$k(k\ge 2)$次迭代，根据频繁$k-1$项集形成$k$项集候选，并扫描数据库一次，形成完整的频繁$k$项集的集合$L_k$。
首先，扫描数据库并累计每个项的计数，并统计满足最小支持度的项，找出频繁1项集的集合，记为$L_1$；然后使用$L_1$找出频繁2项集的集合$L_2$；使用$L_2$找出$L_3$，知道不能再找到频繁$k$项集（找出每个$L_k$需要一次数据库的完整扫描）。

TID	ItemID
T1	I1,I2,I5
T2	I2,I4
T3	I2,I3
T4	I1,I2,I4
T5	I1,I3
T6	I2,I3
T7	I1,I3
T8	I1,I2,I3,I5
T9	I1,I2,I3

由频繁项集产生关联规则：

• 对每个频繁项集合$l$，产生$l$的所有非空子集
• 对$l$的每个非空子集$s$，如果$\frac{\mid l\mid }{\mid s\mid }\le min\_conf$，则输出规则$s\Rightarrow (l-s)$

Apriori算法的候选产生-检查方法显著压缩了候选项集的规模，并产生很好的性能。然后可能受两种非平凡开销的影响：

• 可能仍然需要产生大量候选项集
• 可能需要重复扫描整个数据库

使用涉及散列和事务压缩计数的变形以及划分数据（对每个分区玩，然后合并结果）和抽样数据（对数据子集挖掘）可以将数据扫描次数减少到1到2次。

2.2 FP-growth

频繁模式增长（Frequent-Pattern Growth）采用分治策略，将发现长频繁模式的问题转换成在较小的条件数据库中递归地搜索一些较短模式，然后连接后缀。

• 将代表频繁项集的数据库压缩到一颗频繁模式树（FP-Tree），该树仍保留项集的关联信息。
• 把压缩后的数据库划分成一组条件数据库（特殊类型的投影数据库），每个数据库关联一个频繁项或“模式段”，并分别挖掘每个条件数据库（递归实现）。

2.3 Eclat

Eclat（Equivalence CLAss Transformation）使用垂直数据格式（vertical data fromat）挖掘频繁项集。将给定的、用TID-项集形式的水平数据格式事务数据集变成项-TID-集合形式的垂直数据格式。根据先验性质和附加的优化技术（如diffset），通过取TID-集的交，对变换后的数据集进行挖掘。

3. 模式评估

3.1 相关规则

相关规则（correlation rule）使用支持度、置信度以及相关性度量：
$$A\Rightarrow B[support,confidence,correlation]$$
其中，相关性使用提升度（lift）来度量：
$$lift(A,B)=\frac{P(A\cup B)}{P(A)P(B)}=\frac{\frac{count(A\cup B)}{count(D)}}{\frac{count(A)}{count(D)}\frac{count(B)}{count(D)}}=\frac{P(B\mid A)}{P(B)}=\frac{P(A\mid B)}{P(A)}$$

$lift(A,B)<1$，则A和B负相关；$lift(A,B)>1$，则A和B正相关；$lift(A,B)=1$，则A和B相互独立，没有相关性，此时$P(A\cup B)=P(A)P(B)$

Contingency table

购买游戏的概率：$P(game)=0.6$

购买视频的概率：$P(video)=0.75$

同时购买两者的概率：$P(game,video)=0.4$

$support(game\Rightarrow video)=0.4$

$confidence(game\Rightarrow video)=\frac{0.4}{0.6}=0.66$

$lift(game,video)=\frac{0.4}{0.6\times 0.75}=0.89<1$，game与video之间为负相关。

3.2 模式评估度量

（1）全置信度（all_confidence） a l l _ c o n f ( A , B ) = s u p ( A ∪ B ) m a x { s u p ( A ) , s u p ( B ) } = m i n { P ( A ∣ B ) , P ( B ∣ A ) } all\_conf(A,B) = \frac {sup(A \cup B)}{max\{ sup(A), sup(B)\}} = min\{P(A \mid B),P(B \mid A)\} all_conf(A,B)=max{sup(A),sup(B)}sup(A∪B)​=min{P(A∣B),P(B∣A)}
（2）最大置信度（max_confidence） m a x _ c o n f ( A , B ) = m a x { P ( A ∣ B ) , P ( B ∣ A ) } max\_conf(A,B) = max\{P(A \mid B),P(B \mid A)\} max_conf(A,B)=max{P(A∣B),P(B∣A)}
（3）余弦度量 $$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\mid B)\times P(B\mid A)}$$
（4）Kulczynski度量 $$Kulc(A,B)=\frac{1}{2}(P(A\mid B)+P(B\mid A))$$

以上4中度量具有以下性质：

• 仅受条件概率$P(A|B)$和$P(B|A)$的影响，而不受事务总个数的影响。
• 每个度量值取值在0-1之间，并且值越大，A和B联系越紧密。
• 不受零事务（null-transaction，指不好喊任何考察项集的事务）影响。

推荐Kluc与不平衡比使用。不平衡比（IR，Imbalance Ratio）评估规则蕴含式中两个项集A和B的不平衡程度，这个比率独立于零事务的个数，也独立于事务的总数。

$$IR(A,B)=\frac{\mid sup(A)-sup(B)\mid }{sup(A)+sup(B)-sup(A\cup B)}$$

如果A和B两个方向的蕴含相同，则$IR(A,B)=0$；否则，两者之差越大，不平衡比就越大。

4. 高级模式挖掘

（1） 基本模式

• 频繁模式：满足最小支持度阈值的模式（或项的集合）
• 闭模式：模式$p$是一个闭模式，如果不存在与$p$具有相同支持度的超模式$p^{\prime }$
• 极大模式：模式$p$是一个极大模式，如果不存在$p$的频繁超模式
• 不频繁模式（稀有模式）：很少出现但非常重要的模式
• 负模式：揭示项之间的负相关的模式

（2）基于模式所涉及的抽象层
模式或关联规则可能处于高、低，或者多个抽象层的项。如

$$buys(X,"computer")\Rightarrow buys(X,"printer")$$$$buys(X,"laptop\_computer")\Rightarrow buys(X,"color\_laser\_printer")$$

$"computer"$处于比$"laptop\_computer"$更高的抽象层，我们称所挖掘的规则由多层关联规则组成。

反之，规则不涉及不同抽象层的项或属性，则该集合包含单层关联规则。

（3）基于规则或模式所涉及的维数
如果关联规则或模式中的项或属性只涉及一个维，则它是单维关联规则/模式。

如果关联规则或模式涉及两个或多个维，则它是多维关联规则。

$$age(X,"20...29")\wedge income(X,"52K...58K")\Rightarrow buys(X,"iPad")$$

（4）基于规则或模式中所处理的值类
如果规则考虑的关系是项是否出现，则它是布尔关联规则；

如果规则描述的是量化的项或属性之间的关联，则它是量化关联规则（quantitative assocaition rule）。在这种规则中，项或属性的量化值被划分为区间。

（5）基于挖掘选择性模式的约束或标准
被发现的模式或规则可以是基于约束的（即满足用户指定的约束）、近似的、压缩的、近似匹配的、$top-k$（即用户指定的$k$值的$k$最频繁项集）、感知冗余的$top-k$（即相似的或排除冗余模式的$top-k$模式）等。

（6）基于所挖掘的数据类型和特征

• 频繁项集
• 频繁子序列
• 频繁子结构