笔记分享: 西安交通大学COMP551705数据仓库与数据挖掘——02. 关联规则挖掘

有关 $\text{Github}$仓库，欢迎来 $\text{Star}$

$\text{1. }$基本概念

1️⃣关联规则挖掘

1. 含义：从事务数据库中发现项集之间有趣的关联
2. 定义：对于$Y\text{⊆}I/X\text{⊆}{T}_i$且$X\text{∩}Y\text{=}\varnothing$，$X\text{→}Y$表示既然$T_i$中含$X$则也(以一定支持/置信度)含$Y$

   集合	含义	示例
   项集$I$	I = { i 1 , i 2 , ⋯   , i m } I\text{=}\left\{i_1, i_2, \cdots, i_m\right\} I={i1​,i2​,⋯,im​}	超市中的所有商品
   事务集$D$	D = { T 1 , T 2 , ⋯   , T n } D\text{=}\left\{T_1, T_2, \cdots, T_n\right\} D={T1​,T2​,⋯,Tn​}且$T_i\text{⊆}I$	所有交易($T_i$为第$i$次交易结算商品)
   事务包含项集$X$	$X\text{⊆}I$且$X\text{⊆}{T}_i$	每次交易所结算的(部分)商品

3. 表示：
   • 数学表示：$A\text{→}B[S,C]$ (当$SC$都超过阈值时认为该规则强相关)
   • 可视化图：
     

2️⃣规则度量

1. 客观度量：

   $\text{Item}$	公式	含义
   支持度	$S(A\text{→}B)\text{=}P(A\text{∩}B)$, $S(A)\text{=}P(A)$	所有事务中，有多少事务同时含$AB$/含$A$
   置信度	$C(A\text{→}B)\text{=}\frac{P(A\text{∩}B)}{P(A)}$	在包含$A$的事务中，有多少同时还含$B$

   • 示例：$\begin{array}{cc}\text{TID}& \text{Item}\\ 2000& A,B,C\\ 1000& A,C\\ 4000& A,D\\ 5000& B,E,F\end{array}\text{ ⇒ }\{\begin{array}{l}P(A)=\frac{3}{4}\\ P(A\cap B)=\frac{1}{4}\end{array}\text{ ⇒ }A\to B\left[\frac{1}{4},\frac{1}{3}\right]$
2. 主观度量：个人常识/实际情况…

3️⃣关联规则/相关性/因果关系

1. 关联规则/相关性
   • 相关性衡量：$\text{Lift}(A,B)\text{=}\frac{P(A\text{∪}A)}{P(A)P(B)}\text{→}\{\begin{array}{l}\text{＜}1\text{→}AB负相关\\ \\ \text{=}1\text{→}AB无相关\\ \\ \text{>}1\text{→}AB正相关\end{array}$
   • 二者关系：强关联规则$\text{≠} $正相关
     
2. 关联规则/因果关系：二者无关，但相关性有助于为发现因果关系提供线索

$\text{2. }$布尔关联规则

$\text{2.1. }$一些基本概念

1️⃣频繁项集

1. 定义：$X$频繁$\stackrel{等价于}{}$事务集$D$中含$X$的$T_i$数量($X$支持度)超过阈值$\stackrel{等价于}{}X$满足最小支持度
2. 性质：
   • 如果$X$频繁$\text{→}X$的子集也一定频繁(向下封闭)
   • 如果$X$非频繁$\text{→}X$的超集(如 { X , x n + 1 , x n + 2 , . . . } \{X,x_{n+1},x_{n+2},...\} {X,xn+1​,xn+2​,...})也一定非频繁

2️⃣闭合集$\&$最大集：为解决组合爆炸($规则数目\text{ ∝ }{2}^{数据集规模}$)问题

1. 定义：对于事务集$D$

   集合	含义	意义
   闭合集(模式)	$X$闭合$\stackrel{等价于}{}X$频繁$\text{∩}X$所有超集的支持度小于$X$的	$D$无损压缩
   最大集(模式)	$X$最大$\stackrel{等价于}{}X$频繁$\text{∩}X$所有超集都非频繁	$D$有损压缩

2. 示例： D = { A 1 = ⟨ a 1 , a 2 , … , a 100 ⟩ , A 2 = ⟨ a 1 , a 2 , … , a 50 ⟩ } D\text{=}\left\{A_1\text{=}\left\langle a_1, a_2, \ldots, a_{100}\right\rangle,A_2\text{=}\left\langle a_1, a_2, \ldots, a_{50}\right\rangle\right\} D={A1​=⟨a1​,a2​,…,a100​⟩,A2​=⟨a1​,a2​,…,a50​⟩}，最小支持度$\text{=1}$

   集合	$\text{Item}$
   闭合模式	$A_1$(支持度$\text{=1}/$无频繁超集)，$A_2$(支持度$\text{=2/}$频繁超集支持度$\text{=2}$)
   最大模式	$A_1$(支持度$\text{=1}/$无频繁超集)
   所有模式	所有的频繁子集，比如$⟨a_1,\dots ,a_{49}⟩$

$\text{2.2.}$ $\text{Apriori}$算法

0️⃣总论

1. 原有方案：原始数据$\stackrel{(暴力)生成}{\to }$关联规则
2. 现有方案：原始数据$\stackrel{\text{Apriori}算法}{\to }$频繁项集$\stackrel{生成}{\to }$关联规则

1️⃣算法流程：原始数据$\stackrel{\text{Apriori}算法}{\to }$频繁项集

1. 初始化：事务$D\stackrel{清洗}{\to }$单项 { { T 1 } , { T 2 } , . . . , { T n } } → 满足最小支持度 \small\{\{\mathrm{T_1}\}, \{\mathrm{T_2}\},..., \{\mathrm{T_n}\}\}\xrightarrow{满足最小支持度} {{T1​},{T2​},...,{Tn​}}满足最小支持度 ​ L 1 = { { T i 1 } , { T i 2 } , . . . , { T i m } } L_1\text{=}\small\{\{\mathrm{T_{i_1}}\}, \{\mathrm{T_{i_2}}\},..., \{\mathrm{T_{i_m}}\}\} L1​={{Ti1​​},{Ti2​​},...,{Tim​​}}
2. 主循环：候选集$L_1\stackrel{执行以下操作}{\to }$候选集$L_2$ (下一轮循环)
   • 组合：本轮频繁项集$L_1\underset{(具体见例子)}{\overset{两两组合}{\to }}$候选项集$C_2$
   • 剪枝：候选项集$C_2\stackrel{去处有非频繁子集的项}{\to }$下一候频繁集$L_2$，以进行下轮以此循环
3. 输出：当循环到$L_{\alpha }$为空集时停止循环，频繁项集 L = { L 1 ∪ L 2 ∪ . . . ∪ L α } L\text{=}\{L_1\text{∪}L_2\text{∪}...\text{∪}L_\alpha\} L={L1​∪L2​∪...∪Lα​}

2️⃣频繁项集$\stackrel{生成}{\to }$关联规则

1. 基本流程：
   • 子集：频繁项集$L$所有非空子集 S = { S 1 , S 2 , . . . , S 2 ∣ L ∣ − 2 } S\text{=}\{S_1,S_2,...,S_{2^{|L|}-2}\} S={S1​,S2​,...,S2∣L∣−2​}，任意$S_i\text{→}{S}_j$组合满足支持度
   • 规则：对每个子集计算$S_i\text{→}L\backslash S_i$的置信度，若小于阈值则视$S_i\text{→}L\backslash S_i$强相关
2. 效率优化：
   • 原理：对$(X\text{→}L\text{-}X)$置信度不满足阈值$\stackrel{X^{\prime }\text{⊆}X}{\to }(X^{\prime }\text{→}L\text{-}{X}^{\prime })$也不满足
   • 优化：先验证$L\text{-}X$只有单一项的规则，若不满足则剪枝/满足则再去验证$L\text{-}X$多项的规则

$\text{2.3.}$ $\text{Apriori}$算法示例

0️⃣基本条件：事务及其项集如下表，设定最小支持度为$2$

$\text{T}$	$\text{Beer}$	$\text{Diap.}$	$\text{Powd}$	$\text{Bread}$	$\text{Umbre.}$	$\text{Milk}$	$\text{Deter.}$	$\text{Cola}$
$1$	✅	✅	✅	✅	✅	❌	❌	❌
$2$	❌	✅	✅	❌	❌	❌	❌	❌
$3$	✅	✅	❌	❌	❌	✅	❌	❌
$4$	✅	✅	❌	❌	❌	❌	✅	❌
$5$	✅	❌	❌	❌	❌	✅	❌	✅

1️⃣$\text{Apriori}$算法：得到频繁项集

1. 初始化： L 1 ⇐ 出现超过两次的商品 { Beer,Diap,Powd,Milk } L_1\xLeftarrow{出现超过两次的商品}\{\small\text{Beer,Diap,Powd,Milk}\} L1​出现超过两次的商品 ​{Beer,Diap,Powd,Milk}
2. 主循环：当前为$L_1$
   • 组合：$L_1\stackrel{\text{简单两两组合}}{\to }{C}_2\text{=}\left\{\left[\begin{array}{c}\text{Beer}\\ \text{Diap}\end{array}\right],\cancel{\left[\begin{array}{c}\text{Beer}\\ \text{Powd}\end{array}\right]},\left[\begin{array}{c}\text{Beer}\\ \text{Milk}\end{array}\right],\left[\begin{array}{c}\text{Diap}\\ \text{Powd}\end{array}\right],\cancel{\left[\begin{array}{c}\text{Diap}\\ \text{Milk}\end{array}\right]},\cancel{\left[\begin{array}{c}\text{Powd}\\ \text{Milk}\end{array}\right]}\right\}$
   • 剪枝：$C_2\stackrel{剪掉包含非频繁子集的}{\to }{L}_2\text{=}\left\{\left[\begin{array}{c}\text{Beer}\\ \text{Diap}\end{array}\right],\left[\begin{array}{c}\text{Beer}\\ \text{Milk}\end{array}\right],\left[\begin{array}{c}\text{Diap}\\ \text{Powd}\end{array}\right]\right\}$
3. 主循环：当前为$L_2$
   • 组合：$L_2\underset{组合逻辑见下表}{\overset{\text{两两组合}}{\to }}{C}_3\text{=}\left\{\cancel{\left[\begin{array}{c}\text{Beer}\\ \text{Diap}\\ \text{Milk}\end{array}\right]},\cancel{\left[\begin{array}{c}\text{Beer}\\ \text{Diap}\\ \text{Powd}\end{array}\right]}\right\}$

     合并的集	条件: 二者有$k\text{-1}$项(此处为$1$)相等	操作
     $L_2[1]/L_2[2]$	共有$\text{Beer}\text{→}$满足	执行组合
     $L_2[1]/L_2[3]$	共有$\text{Diap}\text{→}$满足	执行组合
     $L_2[2]/L_2[3]$	不满足	不执行组合

   • 剪枝：$C_2\stackrel{剪掉包含非频繁子集的}{\to }{L}_3\text{=}\varnothing$，故终止循环
4. 输出：$L\text{=}{L}_1\text{∪}{L}_2\text{=}\left\{\text{Beer},\text{Diap},\text{Powd},\text{Milk},\left[\begin{array}{c}\text{Beer}\\ \text{Diap}\end{array}\right],\left[\begin{array}{c}\text{Beer}\\ \text{Milk}\end{array}\right],\left[\begin{array}{c}\text{Diap}\\ \text{Powd}\end{array}\right]\right\}$

2️⃣生成规则$\text{→ }\begin{array}{cccc}\text{Item}& \text{Support(A,B)}& \text{Support A}& \text{Confidence}\\ \text{Beer}\to \text{Diaper}& 60\%& 80\%& 75\%\\ \text{Beer}\to \text{Milk}& 40\%& 80\%& 50\%\\ \text{Diaper}\to \text{Powd}& 40\%& 80\%& 50\%\\ \text{Diaper}\to \text{Beer}& 60\%& 80\%& 75\%\\ \text{Milk}\to \text{Beer}& 40\%& 40\%& 100\%\\ \text{Powd}\to \text{Diaper}& 40\%& 40\%& 100\%\end{array}\text{ etc.....}$

$\text{3. }$多层关联规则挖掘

$\text{3.1. }$算法概述

1️⃣基本概念

1. 概念分层：按层次组织的数据(一般概念$\stackrel{\text{高层→低层}}{\to }$具体概念)，正符合事务数据库的存储
   
2. 规则示例：高层规则 (计算机$\text{→}$电器)，低层规则 (台式机$\text{→}$打印机)

2️⃣每层最小支持度的设定

方法	描述	特点
一致	所有曾的最小支持度一致	忽略底层(地层支持度一般较低)
递减	层次越低$\text{→}$最小支持度越低	保留底层罕见但有意义的规则
分组	专家指重点项集$\text{→}$由此设置每层不同最小支持度	$\text{N/A}$

3️⃣分层挖掘：

1. 含义：在多个抽象层挖掘关联规则$\text{→}$在不同的抽象层进行转化
2. 性质：(支持度的传播)父节点支持度$\text{≥}$其子节点支持度，且根结点的支持度为$100\%$
3. 策略：(自顶向下)具体步骤看例子
   • 最高层：用$\text{Apriori}$寻找高层频繁项集$+$过滤事务集
   • 向下迭代：传递过滤后事务集到下一层，继续用$\text{Apriori}$寻找高层频繁项集$+$过滤事务集
   • 终止：迭代到层次(子节点)时停下

$\text{3.2. }$算法实例

0️⃣基本情况：

1. 概念分层：

   分层	表示	最大支持度
   第一层(顶层)	$\text{{1**, 2**, 3**, 4**}}$等	$4$
   第二层(中层)	$\text{{11*, 12*, 21*, 22*}}$等	$3$
   第三层(低层)	$\text{{111, 121, 211, 713}}$等	$3$

2. 事务集：第$i$位表示在第$i$层的分类，如$524$表示在高/中/低层分属第$5$/第$2$/第$4$类

   $\text{TID}$	底层	中层	顶层
   $\text{T1}$	{ 111,121,211,221 } \{\text{111,121,211,221}\} {111,121,211,221}	{ 11*,12*,21*,22* } \{\text{11*,12*,21*,22*}\} {11*,12*,21*,22*}	{ 1**, 2** } \{\text{1**, 2**}\} {1**, 2**}
   $\text{T2}$	{ 111,211,222,323 } \{\text{111,211,222,323}\} {111,211,222,323}	{ 11*,21*,22*,32* } \{\text{11*,21*,22*,32*}\} {11*,21*,22*,32*}	{ 1**, 2**, 3** } \{\text{1**, 2**, 3**}\} {1**, 2**, 3**}
   $\text{T3}$	{ 112,122,221,411 } \{\text{112,122,221,411}\} {112,122,221,411}	{ 11*,12*,22*,41* } \{\text{11*,12*,22*,41*}\} {11*,12*,22*,41*}	{ 1**, 2**, 4** } \{\text{1**, 2**, 4**}\} {1**, 2**, 4**}
   $\text{T4}$	{ 111,121 } \{\text{111,121}\} {111,121}	{ 11*,12* } \{\text{11*,12*}\} {11*,12*}	{ 1** } \{\text{1**}\} {1**}
   $\text{T5}$	{ 111,122,211,221,413 } \{\text{111,122,211,221,413}\} {111,122,211,221,413}	{ 11*,12*,21*,22*,41* } \{\text{11*,12*,21*,22*,41*}\} {11*,12*,21*,22*,41*}	{ 1**, 2**, 4** } \{\text{1**, 2**, 4**}\} {1**, 2**, 4**}
   $\text{T6}$	{ 211,323,524 } \{\text{211,323,524}\} {211,323,524}	{ 21*,32*,52* } \{\text{21*,32*,52*}\} {21*,32*,52*}	{ 2**, 3**, 5** } \{\text{2**, 3**, 5**}\} {2**, 3**, 5**}
   $\text{T7}$	{ 323,411,524,713 } \{\text{323,411,524,713}\} {323,411,524,713}	{ 32*,41*,52*,71* } \{\text{32*,41*,52*,71*}\} {32*,41*,52*,71*}	{ 3**, 4**, 5**, 7** } \{\text{3**, 4**, 5**, 7**}\} {3**, 4**, 5**, 7**}

1️⃣顶层的$\text{Apriori}$算法：最小支持度为$4$

1. 初始化：
   • 初始频繁集： L ( 1 , 1 ) = { {1**},{2**} } ⇐ 得到 L(1,1)\text{=}\{\text{\{1**\},\{2**\}}\}\xLeftarrow{得到} L(1,1)={{1**},{2**}}得到 ​ 筛选出 { i ** } \{i\text{**}\} {i**}中支持度大于$5$的
   • 表过滤：$L(1,1)$中项的子节点必定以$1/2$开头，故滤掉以其它开头的

     $\text{TID}$	当前事务表$\text{T[1]}$	滤后事务表$\text{T[2]}$
     $\text{T1}$	{ 111,121,211,221 } \{\text{111,121,211,221}\} {111,121,211,221}	{ 111,121,211,221 } \{\text{111,121,211,221}\} {111,121,211,221}
     $\text{T2}$	{ 111,211,222,323 } \{\text{111,211,222,323}\} {111,211,222,323}	{ 111,211,222 } \{\text{111,211,222}\} {111,211,222}
     $\text{T3}$	{ 112,122,221,411 } \{\text{112,122,221,411}\} {112,122,221,411}	{ 112,122,221 } \{\text{112,122,221}\} {112,122,221}
     $\text{T4}$	{ 111,121 } \{\text{111,121}\} {111,121}	{ 111,121 } \{\text{111,121}\} {111,121}
     $\text{T5}$	{ 111,122,211,221,413 } \{\text{111,122,211,221,413}\} {111,122,211,221,413}	{ 111,122,211,221 } \{\text{111,122,211,221}\} {111,122,211,221}
     $\text{T6}$	{ 211,323,524 } \{\text{211,323,524}\} {211,323,524}	{ 211 } \{\text{211}\} {211}
     $\text{T7}$	{ 323,411,524,713 } \{\text{323,411,524,713}\} {323,411,524,713}	{ ∅ } \{\varnothing\} {∅}

2. 主循环：当前为$L(1,1)$
   • 组合： L ( 1 , 1 ) → 简单两两组合 C ( 1 , 2 ) = { {1**,2** } } L(1,1) \xrightarrow{\text{简单两两组合}} C(1,2) \text{=}\{\text{\{1**,2**}\}\} L(1,1)简单两两组合 ​C(1,2)={{1**,2**}}
   • 剪枝： C ( 1 , 2 ) → 滤无可滤 依据T[2]减去包含非频繁子集的 L ( 1 , 2 ) = { {1**,2** } } C(1,2)\xrightarrow[滤无可滤]{依据\text{T[2]}减去包含非频繁子集的}L(1,2) \text{=}\{\text{\{1**,2**}\}\} C(1,2)依据T[2]减去包含非频繁子集的 滤无可滤​L(1,2)={{1**,2**}} (不可再组合故循环结束)
3. 输出：第一层频繁集 L ( 1 ) = { {1**},{2**} , {1**,2** } } L(1)\text{=}\{\text{\{1**\},\{2**\}},\text{\{1**,2**}\}\} L(1)={{1**},{2**},{1**,2**}}；将滤后事务表$T[2]$传给下一层

2️⃣中层的$\text{Apriori}$算最小支持度为$3$法：

1. 初始化：
   • 初始频繁集： L ( 2 , 1 ) = { {11*},{12*},{21*},{22*} } ⇐ 得到 L(2,1)\text{=}\{\text{\{11*\},\{12*\},\{21*\},\{22*\}}\}\xLeftarrow{得到} L(2,1)={{11*},{12*},{21*},{22*}}得到 ​ 筛出 { i j * } \{ij\text{*}\} {ij*}中支持度大于$3$的
   • 事务表过滤：$L(2,1)$中项的子节点必定以$11/12/21/22$开头，滤掉以其他开头的

     $\text{TID}$	当前事务表$\text{T[2]}$	滤后事务表$\text{T[3]}$
     $\text{T1}$	{ 111,121,211,221 } \{\text{111,121,211,221}\} {111,121,211,221}	{ 111,121,211,221 } \{\text{111,121,211,221}\} {111,121,211,221}
     $\text{T2}$	{ 111,211,222 } \{\text{111,211,222}\} {111,211,222}	{ 111,211,222 } \{\text{111,211,222}\} {111,211,222}
     $\text{T3}$	{ 112,122,221 } \{\text{112,122,221}\} {112,122,221}	{ 112,122,221 } \{\text{112,122,221}\} {112,122,221}
     $\text{T4}$	{ 111,121 } \{\text{111,121}\} {111,121}	{ 111,121 } \{\text{111,121}\} {111,121}
     $\text{T5}$	{ 111,122,211,221 } \{\text{111,122,211,221}\} {111,122,211,221}	{ 111,122,211,221 } \{\text{111,122,211,221}\} {111,122,211,221}
     $\text{T6}$	{ 211 } \{\text{211}\} {211}	{ 211 } \{\text{211}\} {211}
     $\text{T7}$	{ ∅ } \{\varnothing\} {∅}	{ ∅ } \{\varnothing\} {∅}

2. 主循环：当前为$L(2,1)$
   • 组合： L ( 2 , 1 ) → 两两组合 C ( 2 , 2 ) = { {11*,12* } , { 11*,21* } . . . . . } L(2,1) \xrightarrow[]{\text{两两组合}} C(2,2) \text{=}\{\text{\{11*,12*}\},\{\text{11*,21*}\}.....\} L(2,1)两两组合 ​C(2,2)={{11*,12*},{11*,21*}.....}
   • 剪枝： C ( 2 , 2 ) → 依据 T[3] 减去包含非频繁子集的 L ( 2 , 2 ) = { { 11*, 12* } { 11*, 21* } { 11*, 22* } { 12*, 22* } { 21*, 22* } } C(2,2) \xrightarrow[]{\text{依据 T[3] 减去包含非频繁子集的}} L(2,2) \text{=} \left\{ \begin{array}{l} \{\text{11*, 12*}\} \\ \{\text{11*, 21*}\} \\ \{\text{11*, 22*}\} \\ \{\text{12*, 22*}\} \\ \{\text{21*, 22*}\} \end{array} \right\} C(2,2)依据 T[3] 减去包含非频繁子集的 ​L(2,2)=⎩ ⎨ ⎧​{11*, 12*}{11*, 21*}{11*, 22*}{12*, 22*}{21*, 22*}​⎭ ⎬ ⎫​
3. 主循环：当前为$L(2,2)$
   • 组合： L ( 2 , 2 ) → 两两组合 C ( 2 , 3 ) = { {11*,12*,21* } , { 11 ∗ , 12 ∗ , 22 ∗ } . . . . . } L(2,2) \xrightarrow[]{\text{两两组合}} C(2,3) \text{=}\{\text{\{11*,12*,21*}\},\{11*,12*,22*\}.....\} L(2,2)两两组合 ​C(2,3)={{11*,12*,21*},{11∗,12∗,22∗}.....}
   • 剪枝： C ( 2 , 3 ) → 依据 T[3] 减去包含非频繁子集的 L ( 2 , 3 ) = { { 11*,12*,22* } , { 11*,21*,22* } } C(2,3) \xrightarrow[]{\text{依据 T[3] 减去包含非频繁子集的}} L(2,3) \text{=} \left\{ \begin{array}{l} \{\text{11*,12*,22*}\} , \{\text{11*,21*,22*}\} \end{array} \right\} C(2,3)依据 T[3] 减去包含非频繁子集的 ​L(2,3)={{11*,12*,22*},{11*,21*,22*}​}
4. 主循环：当前为$L(2,3)$
   • 组合： L ( 2 , 3 ) → 两两组合 C ( 2 , 4 ) = { {11*,12*,21*,22* } } L(2,3) \xrightarrow[]{\text{两两组合}} C(2,4) \text{=}\{\text{\{11*,12*,21*,22*}\}\} L(2,3)两两组合 ​C(2,4)={{11*,12*,21*,22*}}
   • 剪枝：$C(2,4)\stackrel{\text{依据 T[3] 减去包含非频繁子集的}}{\to }L(2,4)\text{=}\varnothing \text{ → }$停止循环
5. 输出：第二层频繁集 L ( 2 ) = { L ( 2 , 1 ) ∪ L ( 2 , 2 ) ∪ L ( 2 , 3 ) } L(2)\text{=}\{L(2,1)\text{∪}L(2,2)\text{∪}L(2,3)\} L(2)={L(2,1)∪L(2,2)∪L(2,3)}；将滤后事务表$\text{T[3]}$传到下一层
   

3️⃣底层的$\text{Apriori}$算最小支持度为$3$法：

1. 初始化：
   • 初始频繁集： L ( 3 , 1 ) = { {111},{211},{221} } ⇐ 得到 L(3,1)\text{=}\{\text{\{111\},\{211\},\{221\}}\}\xLeftarrow{得到} L(3,1)={{111},{211},{221}}得到 ​ 筛选出 { i j k } \{ijk\text{}\} {ijk}中支持度大于$3$的
   • 事务表过滤：接下来只考虑 { {111},{211},{221} } \{\text{\{111\},\{211\},\{221\}}\} {{111},{211},{221}}中的，故滤掉其他的

     $\text{TID}$	当前事务表$\text{T[3]}$	滤后事务表$\text{T[4]}$
     $\text{T1}$	{ 111,121,211,221 } \{\text{111,121,211,221}\} {111,121,211,221}	{ 111,,211,221 } \{\text{111,,211,221}\} {111,,211,221}
     $\text{T2}$	{ 111,211,222 } \{\text{111,211,222}\} {111,211,222}	{ 111,211 } \{\text{111,211}\} {111,211}
     $\text{T3}$	{ 112,122,221 } \{\text{112,122,221}\} {112,122,221}	{ 221 } \{\text{221}\} {221}
     $\text{T4}$	{ 111,121 } \{\text{111,121}\} {111,121}	{ 111 } \{\text{111}\} {111}
     $\text{T5}$	{ 111,122,211,221 } \{\text{111,122,211,221}\} {111,122,211,221}	{ 111,211,221 } \{\text{111,211,221}\} {111,211,221}
     $\text{T6}$	{ 211 } \{\text{211}\} {211}	{ 211 } \{\text{211}\} {211}
     $\text{T7}$	{ ∅ } \{\varnothing\} {∅}	{ ∅ } \{\varnothing\} {∅}

2. 主循环：当前为$L(3,1)$
   • 组合： L ( 3 , 1 ) → 两两组合 C ( 3 , 2 ) = { {111,211 } , {111,221 } , {211,221 } } L(3,1) \xrightarrow[]{\text{两两组合}} C(3,2) \text{=}\{\text{\{111,211}\},\text{\{111,221}\},\text{\{211,221}\}\} L(3,1)两两组合 ​C(3,2)={{111,211},{111,221},{211,221}}
   • 剪枝：$C(3,2)\stackrel{\text{依据 T[4] 减去包含非频繁子集的}}{\to }L(3,2)\text{=}\text{{111,221}\}\text{ → }$无法再组合(停止循环)
3. 输出：第一层频繁集 L ( 1 ) = { {111},{211},{221} , {111,221 } } L(1)\text{=}\{\text{\{111\},\{211\},\{221\}},\text{\{111,221}\}\} L(1)={{111},{211},{221},{111,221}}

$\text{4. }$多维关联规则挖掘

1️⃣多维关联规则

1. 含义：涉及两个或多个维或谓词的关联规则
2. 示例：<Age: 30..39> and <Married: Yes> -> <NumCars: 2>
   $\begin{array}{cccc}\text{RecordID}& \text{Age}& \text{Married}& \text{NumCars}\\ 100& 23& \text{No}& 1\\ 200& 25& \text{Yes}& 1\\ 300& 29& \text{No}& 0\\ 400& 34& \text{Yes}& 2\\ 500& 38& \text{Yes}& 2\end{array}$

2️⃣处理思路

1. 处理对象：搜索频繁项集$\stackrel{转为}{\to }$搜索频繁谓词集
2. 量化预处理：数值型关联规则挖掘$\stackrel{转化}{\to }$布尔型关联规则挖掘，如下例子
   $\begin{array}{cccc}\text{RecordID}& \text{Age}& \text{Married}& \text{NumCars}\\ 100& 23& \text{No}& 1\\ 200& 25& \text{Yes}& 1\\ 300& 29& \text{No}& 0\\ 400& 34& \text{Yes}& 2\\ 500& 38& \text{Yes}& 2\\ 600& 45& \text{No}& 3\\ 700& 50& \text{Yes}& 1\\ 800& 60& \text{No}& 0\end{array}$

3️⃣处理算法：$\text{ARCS}$大致流程

1. 分箱：根据数据的分布，将数值属性离散化到箱(固定区间)
2. 搜索：找出频繁谓词集，得到一系列强关联规则(如下)
   • $\text{RuleSet =}\{\begin{array}{l}\text{age}(X,35)\text{∧}\text{income}(X,31K\dots 40K)\text{⇒}\text{buys}(X,\text{TV})\\ \\ \text{age}(X,34)\text{∧}\text{income}(X,41K\dots 50K)\text{⇒}\text{buys}(X,\text{TV})\\ \\ \text{age}(X,35)\text{∧}\text{income}(X,41K\dots 50K)\text{⇒}\text{buys}(X,\text{TV})\end{array}$
3. 聚类：将所得强关联规则映射到$2D$栅格上，得到范围矩形
   
   • $\text{RuleSet}\text{→}\text{age}(X,34\text{-}35)\text{∧}\text{income}(X,31K\text{-}40K)\text{⇒}\text{buys}(X,\text{TV})$

原文地址：https://blog.csdn.net/qq_64091900/article/details/143841041

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！