第六章 关联规则挖掘

1 概念定义

关联规则

• 项i：事务数据库TDB中的基本元素或对象

• 项集I：项的集合

• 事务T：事务数据库中每条数据都是一条事务

• 关联规则：形如A⇒B{support,confidence}A \Rightarrow B\{support,confidence\}A⇒B{support,confidence}的蕴涵式，表示A发生时，B也跟着发生的规律。其中A、B是包含于I，不相交的两个非空项集

• 支持度support(sup)：表示关联规则的频繁程度
  $$sup(A\Rightarrow B)=P(A\cup B)$$
  支持度也被称为相对支持度，而出现频度support_count，即出现次数计数被称为支持度计数或绝对支持度

• 置信度confidence(conf)：表示关联规则的可靠程度
  $$\begin{array}{c}\begin{array}{rl}conf(A\Rightarrow B)& =P(B|A)\\ & =\frac{sup(A\cup B)}{sup(A)}\\ & =\frac{sup\_count(A\cup B)}{sup\_count(A)}\end{array}\end{array}$$

• 强关联规则：满足最小支持度阈值min_sup和最小置信度阈值min_conf的关联规则

频繁项集及其紧凑表示

• 频繁项集：在数据集中出现频率大于最小支持度的项集，含有k个项的频繁项集被称为频繁k项集

• 闭项集：对项集$X$，如果不存在项集$Y$使得$X\subset Y$且$sup(X)=sup(Y)$，则项集$X$在事务数据库中是闭的

• 闭频繁项集：若项集$X$在事务数据库中是闭的和频繁的，则项集$X$是闭频繁项集

  通过闭频繁项集的集合和它的支持度计数信息能导出频繁项集的完整信息

• 超项集和真超项集：若对项集$A$，存在项集$B$，使得$A\subseteq B$，则项集$B$是项集$A$的超项集。若项集$A、B$还满足$A\ne B$，即$A\subset B$，则项集$B$是项集$A$的真超项集

• 极大频繁项集：若项集$X$是频繁的，且不存在项集$Y$使得$X\subset Y$且$sup(Y)\ge min\_sup$，则项集$X$是事务数据库中的极大频繁项集

---

2 由频繁项集生成关联规则

from mlxtend.frequent_patterns import association_rules

1. 逐个拆分频繁$k(k\ge 2)$项集$l$，产生$l$的所有非空子集
2. 对于$l_k$的每个非空子集$s$，如果$sup\_count(l_k)/sup\_count(s)\ge min\_conf$，则输出强关联规则$s\Rightarrow (l_k-s)$

---

3 关联规则评估

支持度-置信度框架的局限性

1. 支持度要求关联规则中的项集都是频繁的，但一些有意义的关联规则包含的项集可能为非频繁项集

例如：分析商场的购物记录时，奢侈品一般是非频繁项，但奢侈品间通常表现出极强的关联性

2. 当关联规则$A\Rightarrow B$中$B$为高频项集时，$A\Rightarrow B$极易满足最小置信度阈值，得到与现实相反的误导性结论

相关性度量

• 提升度lift：评估一个事件提升另一个事件发生概率的程度
  $$lift(A\Rightarrow B)=\frac{P(A\cup B)}{P(A)P(B)}=\frac{P(B|A)}{P(B)}=\frac{conf(A\Rightarrow B)}{sup(B)}$$
  当$lift(A,B)>1$时，认为两事件存在正相关性；当$lift(A,B)<1$时，认为两事件存在负相关性

• 卡方检验：比较两个项集实际观测值和期望频数之间的差异，较大的${\chi }^2$值表明可能存在显著的关联。使用卡方检验确认项集间的相关性存在时，可进一步使用条件概率$P(A|B)$和$P(A)$判断项集之间相关性的正负

• 其他相关性度量

描述度量的性质

• 对称性：适用于不需要区分方向性的场合，即只关心两个项集之间的关联强度，而不关心哪个项集是前提条件，哪个项集是结果
  $$0(M)=0(M^T)$$

• 行/列缩放不变性：能够确保分析结果在不同样本比例下的稳定性和一致性，从而提高分析的可靠性和有效性
  $$0(M)=O(RMC)$$

• 行/列排序下的反对称性：反对称性适用于区分正负关联的场合
  $$\begin{gathered} O(SM)=-O(M)orO(MS)=-O(M) \\ S=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right) \end{gathered}$$

• 反转不变性：反转可视为行与行、列与列的同时交换，适用于需要在数据特征变化时保持度量稳定和一致的情景
  $$\begin{gathered} O(M)=O(SMS) \\ S=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right) \end{gathered}$$

• 零不变性：度量在增加不包含项集$A$和项集$B$的事务时，其值保持不变的特性
  $$\begin{gathered} O(M)=O(M+C) \\ C=\left(\begin{array}{cc}0& 0\\ 0& k\end{array}\right) \end{gathered}$$

相关性度量	对称性	行/列缩放不变性	行/列排序下的反对称性	反转不变性	零不变性
支持度	✔
置信度					✔
提升度	✔
卡方值	✔			✔
全置信度	✔				✔
优势比	✔	✔		✔
余弦度量	✔				✔
Kulc度量	✔				✔
杠杆率	✔
确信度
Added Value
确定性因子
Yule’ Y	✔	✔	✔	✔
Jaccard系数	✔				✔

---

4 Apriori算法

from mlxtend.frequent_patterns import apriori

先验性质

项集$A$为频繁项集，若存在非空项集$B$，满足$B\subset A$，则$B$为频繁项集

即频繁项集的子集都是频繁项集，非频繁项集的超集都不是频繁项集

算法步骤

1. 扫描TDB，对项进行支持度计数，生成频繁1项集的集合$L_1$
2. 对$L_k$使用连接步产生候选k+1项集的集合$C_{k+1}$，使用剪枝步修剪$C_{k+1}$
3. 遍历扫描TDB，对$C_{k+1}$进行支持度计数，找到频繁k+1项集的集合$L_{k+1}$
4. 重复步骤2和步骤3，直到$C_k$或$L_k$为空

算法评价

Apriori算法实现过程中需生成大量的候选项集，多次遍历TDB来计算候选项集的支持度，大量的时间消耗在内存与数据库的数据交换中

更适合稀疏型数据集和短模式的关联规则挖掘

算法优化

• 基于散列的技术：构建Hash表
• 事务压缩技术：减少事务的数量
• 划分技术：将TDB划分成多个分区进行并行计算
• 抽样：从数据库中随机抽样
• 动态项集计数：将数据库划分为若干个区段，逐个扫描区段，并动态添加频繁项集和生成的候选项集

---

5 FP-grouth算法

from mlxtend.frequent_patterns import

算法步骤

1. 扫描TDB，计算单一项的支持度计数（频率）

2. 每条事务内部按频率降序排列，写出频繁1项集的集合$L_1$

   1. 支持度过滤（丢弃非频繁的项）
   2. 按频率递减序排序（降序排列）
   3. 对于相同频率的项，按项字典序进行排序

3. 构建FP-树

   1. 创建树的根结点null
   2. 扫描TDB，将项集按$L_1$中的次序处理，针对每个事务创建一个分支
   3. 创建项头表，使每个项目通过节点链指向它在FP-树中的位置

4. FP-树挖掘生成频繁项集

   1. 对项头表按频率从低到高遍历，构造各个项（节点）的条件模式基

      **条件模式基：**头部链表中某一节点的前缀路径

   2. 构造条件FP-树

      **条件FP-树：**支持度计数大于等于最小支持度计数

   3. 条件FP-树与叶子节点组合得到频繁项集

算法评价

FP-growth算法对不同长度的项集都有很好的适应性，同时在效率上较Apriori算法有较大的提高

FP-growth算法实现过程中需动态生成和释放条件FP-树，在大型数据库中仍然要生成数量庞大的条件FP-树，可能会耗费大量的时间和空间，当数据集较为稀疏时，FP-树的压缩效果较差，算法效率会大幅度下降

更适合挖掘单维的布尔关联规则过程和密集型数据库，在大型数据库的挖掘上相比Apriori算法有明显优势

---

6 Eclat算法

from pyECLAT import ECLAT

数据格式

• TID set：在TDB中，包含项$i$的所有事务的标识符的集合称为项$i$的TID set
• 垂直数据格式：即形如{item:TIDset}\{item:TID set\}{item:TIDset}的数据格式，$item$为项的名称

水平数据格式

TID	事务
1	{a,b,c}\{a,b,c\}{a,b,c}
2	{b}\{b\}{b}
3	{a,c,d}\{a,c,d\}{a,c,d}
4	{a,c}\{a,c\}{a,c}
5	{b,c}\{b,c\}{b,c}
6	{c}\{c\}{c}
7	{a,b,c,d}\{a,b,c,d\}{a,b,c,d}
8	{d}\{d\}{d}

垂直数据格式

项集	TID集
{a}\{a\}{a}	{1,3,4,7}\{1,3,4,7\}{1,3,4,7}
{b}\{b\}{b}	{1,2,5,7}\{1,2,5,7\}{1,2,5,7}
{c}\{c\}{c}	{1,3,4,5,6,7}\{1,3,4,5,6,7\}{1,3,4,5,6,7}
{d}\{d\}{d}	{3,7,8}\{3,7,8\}{3,7,8}

算法步骤

1. 扫描TDB，将水平数据格式转化为垂直数据格式
2. 使用项的TID set计算项的支持度，得到频繁$1$项集和对应的TID set，即$L_1:T_1$
3. 频繁k项集及其对应的TID set为$L_k:T_k$，对$L_k$中两个前$k-1$个项相同的项集$l_1$和$l_2$求并集，$l_1$和$l_2$对应的TID set求交集，得到候选$k+1$项集及其对应的TID set，即$C_{k+1}:T_{k+1}$
4. 对候选$k+1$项集和TID set中的事务数进行计数，如果大于$min\_sup$，则该候选项集为频繁项集，得到$L_{k+1}:T_{k+1}$
5. 重复步骤2和步骤3，直到$L_k$或$C_k$为空

算法评价

Eclat算法生成候选项集时，需要先判断两个项集是否满足连接条件，导致长集合的运算仍然运算时间较长

更适合挖掘短模式的数据集

---

7 H-mine算法

from mlxtend.frequent_patterns import hmine

H-mine算法是使用超链接数据结构H-struct（项头表，频繁项投影，超链接）来挖掘频繁项集的算法

算法步骤

1. 构建H-struct
   1. 第一次扫描数据库，找到所有频繁1项集，并生成事务的频繁项集投影
   2. 按照频繁项集的某种固定顺序F-list将事务中项重新排序
   3. 第二次扫描TDB，根据事务的频繁项集投影建立H-struct
2. 生成频繁项集
   1. 扫描$a$队列，对$H_a$中各项进行支持度计数，将频繁项与$a$组合成频繁2项集
   2. 为项$a$构建项头表$H_a$，并将$a$-队列中频繁项投影链接到$H_a$中的队列
   3. 挖掘所有包含$a、b$的频繁项集
   4. 调整$ab$-队列中事务的超链接，$ab$-队列中的每个投影加入该投影中项$b$的下一个项的队列中
   5. 挖掘包含$a、c$，且不包含$b$的频繁项集
   6. 调整超链接，更新队列

算法评价

通过动态调整链接，实现了小而可精确预测的空间开销，并且运行速度快，在挖掘大型数据库时展现出良好的可扩展性

在处理密集数据库时仍面临挑战

在处理大型和稀疏数据库时表现优异

---

8 算法对比

算法	适用场景
Apriori算法	稀疏型数据集和短模式的关联规则挖掘
FP-growth算法	更适合挖掘单维的布尔关联规则过程和密集型数据库，在大型数据库的挖掘上相比Apriori算法有明显优势
Eclat算法	更适合挖掘短模式的数据集
H-mine算法	在处理大型和稀疏数据库时表现优异