0
0

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

image-20241112204045174

文章目录

有关 

  1.      Github 
  2.     
  3.    
  4.   
  5.     \text{Github} 
  6.    
  7.   
  8. Github仓库，欢迎来 
  11.  
  12.   
  13.   
  14.     Star 
  15.    
  16.   
  17.  
  18.    \text{Star} 
  19.   
  20.

Star

  1.      1. 
  2.     
  3.    
  4.        
  5.     
  6.    
  7.   
  8.     \textbf{1. } 
  9.    
  10.   
  11. 1. 基本概念

1️⃣关联规则挖掘

  1. 含义：从事务数据库中发现项集之间有趣的关联
  2. 定义：对于 Y ⊆ I / X ⊆ T i Y\text{⊆}I/X\text{⊆}T_i Y⊆I/X⊆Ti​且 X ∩ Y = ∅ X\text{∩}Y\text{=}\varnothing X∩Y=∅， X → Y X\text{→}Y X→Y表示既然 T i T_i Ti​中含 X X X则也(以一定支持/置信度)含 Y Y Y集合含义示例项集 I I 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 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 ⊆ I T_i\text{⊆}I Ti​⊆I所有交易( T i T_i Ti​为第 i i i次交易结算商品)事务包含项集 X X X X ⊆ I X\text{⊆}I X⊆I且 X ⊆ T i X\text{⊆}T_i X⊆Ti​每次交易所结算的(部分)商品
  3. 表示： - 数学表示： A → B    [ S , C ] A\text{→}B,,[S,C] A→B[S,C] (当 S C SC SC都超过阈值时认为该规则强相关)- 可视化图：

2️⃣规则度量

  1. 客观度量： Item \textbf{Item} Item公式含义支持度 S ( A → B ) = P ( A ∩ B ) S(A\text{→}B)\text{=}P(A\text{∩}B) S(A→B)=P(A∩B), S ( A ) = P ( A ) S(A)\text{=}P(A) S(A)=P(A)所有事务中，有多少事务同时含 A B AB AB/含 A A A置信度 C ( A → B ) = P ( A ∩ B ) P ( A ) C(A\text{→}B)\text{=}\cfrac{P(A\text{∩}B)}{P(A)} C(A→B)=P(A)P(A∩B)​在包含 A A A的事务中，有多少同时还含 B B B- 示例： TID Item 2000 A , B , C 1000 A , C 4000 A , D 5000 B , E , F ⇒ { P ( A ) = 3 4 P ( A ∩ B ) = 1 4 ⇒ A → B   [ 1 4 , 1 3 ] \text{ \large } \begin{array}{|c|c|} \hline \text{\small TID} & \text{\small Item} \ \hline \small 2000 & \small A, B, C \ \hline \small 1000 & \small A, C \ \hline \small 4000 & \small A, D \ \hline \small 5000 & \small B, E, F \ \hline \end{array} \text{ ⇒ } \begin{cases} P(A) = \cfrac{3}{4} \[5pt] P(A \cap B) = \cfrac{1}{4} \end{cases} \text{ ⇒ } A \to B , \left[\cfrac{1}{4}, \cfrac{1}{3}\right] TID2000100040005000​ItemA,B,CA,CA,DB,E,F​​ ⇒ ⎩⎨⎧​P(A)=43​P(A∩B)=41​​ ⇒ A→B[41​,31​]
  2. 主观度量：个人常识/实际情况…

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

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

  1.      2. 
  2.     
  3.    
  4.        
  5.     
  6.    
  7.   
  8.     \textbf{2. } 
  9.    
  10.   
  11. 2. 布尔关联规则

  1.       2.1. 
  2.      
  3.     
  4.         
  5.      
  6.     
  7.    
  8.      \textbf{2.1. } 
  9.     
  10.    
  11.  2.1. 一些基本概念

1️⃣频繁项集

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

2️⃣闭合集 

  1.        & 
  2.       
  3.      
  4.     
  5.       \& 
  6.      
  7.     
  8.   &最大集：为解决组合爆炸( 
  9.    
  10.     
  11.      
  12.      
  13.        规则数目 ∝  
  14.       
  15.       
  16.       
  17.         2 
  18.        
  19.       
  20.         数据集规模 
  21.        
  22.       
  23.      
  24.     
  25.       规则数目\text{ ∝ }2^{数据集规模} 
  26.      
  27.     
  28.   规则数目 ∝ 2数据集规模)问题
  1. 定义：对于事务集 D D D集合含义意义闭合集(模式) X X X闭合 ⇔ 等价于 X \xLeftrightarrow{等价于}X 等价于​X频繁 ∩ X \text{∩}X ∩X所有超集的支持度小于 X X X的 D D D无损压缩最大集(模式) X X X最大 ⇔ 等价于 X \xLeftrightarrow{等价于}X 等价于​X频繁 ∩ X \text{∩}X ∩X所有超集都非频繁 D D 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​⟩}，最小支持度 =1 \text{=1} =1集合 Item \textbf{Item} Item闭合模式 A 1 A_1 A1​(支持度 =1 / \text{=1}/ =1/无频繁超集)， A 2 A_2 A2​(支持度 =2/ \text{=2/} =2/频繁超集支持度 =2 \text{=2} =2)最大模式 A 1 A_1 A1​(支持度 =1 / \text{=1}/ =1/无频繁超集)所有模式所有的频繁子集，比如 ⟨ a 1 , … , a 49 ⟩ \left\langle a_1, \ldots, a_{49}\right\rangle ⟨a1​,…,a49​⟩

  1.       2.2. 
  2.      
  3.     
  4.    
  5.      \textbf{2.2.} 
  6.     
  7.    
  8.  2.2. 
  9.   
  10.    
  11.     
  12.     
  13.       Apriori 
  14.      
  15.     
  16.    
  17.      \textbf{Apriori} 
  18.     
  19.    
  20.  Apriori算法

0️⃣总论

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

1️⃣算法流程：原始数据 

  1.         → 
  2.        
  3.        
  4.        
  5.          Apriori算法 
  6.         
  7.        
  8.       
  9.      
  10.     
  11.       \xrightarrow{\text{Apriori}算法} 
  12.      
  13.     
  14.   Apriori算法​频繁项集

image-20241116154336636

  1. 初始化：事务 D → 清洗 D\xrightarrow{清洗} D清洗​单项 { { 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 → 执行以下操作 L_1\xrightarrow{执行以下操作} L1​执行以下操作​候选集 L 2 L_2 L2​ (下一轮循环) - 组合：本轮频繁项集 L 1 → ( 具体见例子 ) 两两组合 L_{1}\xrightarrow[(具体见例子)]{两两组合} L1​两两组合(具体见例子)​候选项集 C 2 C_2 C2​- 剪枝：候选项集 C 2 → 去处有非频繁子集的项 C_2\xrightarrow{去处有非频繁子集的项} C2​去处有非频繁子集的项​下一候频繁集 L 2 L_2 L2​，以进行下轮以此循环
  3. 输出：当循环到 L α L_\alpha Lα​为空集时停止循环，频繁项集 L = { L 1 ∪ L 2 ∪ . . . ∪ L α } L\text{=}{L_1\text{∪}L_2\text{∪}...\text{∪}L_\alpha} L={L1​∪L2​∪...∪Lα​}

2️⃣频繁项集 

  1.         → 
  2.        
  3.        
  4.        
  5.          生成 
  6.         
  7.        
  8.       
  9.      
  10.     
  11.       \xrightarrow{生成} 
  12.      
  13.     
  14.   生成​关联规则
  1. 基本流程： - 子集：频繁项集 L L 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 → S j S_i\text{→}S_j Si​→Sj​组合满足支持度- 规则：对每个子集计算 S i → L \ S i S_i\text{→}L\backslash{}S_i Si​→L\Si​的置信度，若小于阈值则视 S i → L \ S i S_i\text{→}L\backslash{}S_i Si​→L\Si​强相关
  2. 效率优化： - 原理：对 ( X → L - X ) (X\text{→}L\text{-}X) (X→L-X)置信度不满足阈值 → X ′ ⊆ X ( X ′ → L - X ′ ) \xrightarrow{X^{\prime}\text{⊆}X}(X^{\prime}\text{→}L\text{-}X^{\prime}) X′⊆X​(X′→L-X′)也不满足- 优化：先验证 L - X L\text{-}X L-X只有单一项的规则，若不满足则剪枝/满足则再去验证 L - X L\text{-}X L-X多项的规则

  1.       2.3. 
  2.      
  3.     
  4.    
  5.      \textbf{2.3.} 
  6.     
  7.    
  8.  2.3. 
  9.   
  10.    
  11.     
  12.     
  13.       Apriori 
  14.      
  15.     
  16.    
  17.      \textbf{Apriori} 
  18.     
  19.    
  20.  Apriori算法示例

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

  1.        2 
  2.       
  3.      
  4.     
  5.       2 
  6.      
  7.     
  8.   2
  10.       
  11.        
  12.         
  13.          
  14.          
  15.            T 
  16.           
  17.          
  18.         
  19.        
  20.          \small\textbf{T} 
  21.         
  22.        
  23.      T 
  24.       
  25.        
  26.         
  27.          
  28.          
  29.            Beer 
  30.           
  31.          
  32.         
  33.        
  34.          \small\textbf{Beer} 
  35.         
  36.        
  37.      Beer 
  38.       
  39.        
  40.         
  41.          
  42.          
  43.            Diap. 
  44.           
  45.          
  46.         
  47.        
  48.          \small\textbf{Diap.} 
  49.         
  50.        
  51.      Diap. 
  52.       
  53.        
  54.         
  55.          
  56.          
  57.            Powd 
  58.           
  59.          
  60.         
  61.        
  62.          \small\textbf{Powd} 
  63.         
  64.        
  65.      Powd 
  66.       
  67.        
  68.         
  69.          
  70.          
  71.            Bread 
  72.           
  73.          
  74.         
  75.        
  76.          \small\textbf{Bread} 
  77.         
  78.        
  79.      Bread 
  80.       
  81.        
  82.         
  83.          
  84.          
  85.            Umbre. 
  86.           
  87.          
  88.         
  89.        
  90.          \small\textbf{Umbre.} 
  91.         
  92.        
  93.      Umbre. 
  94.       
  95.        
  96.         
  97.          
  98.          
  99.            Milk 
  100.           
  101.          
  102.         
  103.        
  104.          \small\textbf{Milk} 
  105.         
  106.        
  107.      Milk 
  108.       
  109.        
  110.         
  111.          
  112.          
  113.            Deter. 
  114.           
  115.          
  116.         
  117.        
  118.          \small\textbf{Deter.} 
  119.         
  120.        
  121.      Deter. 
  122.       
  123.        
  124.         
  125.          
  126.          
  127.            Cola 
  128.           
  129.          
  130.         
  131.        
  132.          \small\textbf{Cola} 
  133.         
  134.        
  135.      Cola 
  136.       
  137.        
  138.         
  139.         
  140.           1 
  141.          
  142.         
  143.        
  144.          1 
  145.         
  146.        
  147.      1✅✅✅✅✅❌❌❌ 
  148.       
  149.        
  150.         
  151.         
  152.           2 
  153.          
  154.         
  155.        
  156.          2 
  157.         
  158.        
  159.      2❌✅✅❌❌❌❌❌ 
  160.       
  161.        
  162.         
  163.         
  164.           3 
  165.          
  166.         
  167.        
  168.          3 
  169.         
  170.        
  171.      3✅✅❌❌❌✅❌❌ 
  172.       
  173.        
  174.         
  175.         
  176.           4 
  177.          
  178.         
  179.        
  180.          4 
  181.         
  182.        
  183.      4✅✅❌❌❌❌✅❌ 
  184.       
  185.        
  186.         
  187.         
  188.           5 
  189.          
  190.         
  191.        
  192.          5 
  193.         
  194.        
  195.      5✅❌❌❌❌✅❌✅

1️⃣ 

  1.        Apriori 
  2.       
  3.      
  4.     
  5.       \text{Apriori} 
  6.      
  7.     
  8.   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 L1​- 组合： L 1 → 简单两两组合 C 2 = { [ Beer Diap ] , [ Beer Powd ] , [ Beer Milk ] , [ Diap Powd ] , [ Diap Milk ] , [ Powd Milk ] } L_1 \xrightarrow{\text{简单两两组合}} C_2 \text{=} \left{ \small {\begin{bmatrix} \text{Beer} \ \text{Diap} \end{bmatrix}}, \cancel{\begin{bmatrix} \text{Beer} \ \text{Powd} \end{bmatrix}}, \begin{bmatrix} \text{Beer} \ \text{Milk} \end{bmatrix}, \begin{bmatrix} \text{Diap} \ \text{Powd} \end{bmatrix}, \cancel{ \begin{bmatrix} \text{Diap} \ \text{Milk} \end{bmatrix}}, \cancel{ \begin{bmatrix} \text{Powd} \ \text{Milk} \end{bmatrix}} \right} L1​简单两两组合​C2​={[BeerDiap​],[BeerPowd​]​,[BeerMilk​],[DiapPowd​],[DiapMilk​]​,[PowdMilk​]​}- 剪枝： C 2 → 剪掉包含非频繁子集的 L 2 = { [ Beer Diap ] , [ Beer Milk ] , [ Diap Powd ] } C_2\xrightarrow{剪掉包含非频繁子集的}L_2\text{=}\left{ \small \begin{bmatrix} \text{Beer} \ \text{Diap} \end{bmatrix}, \begin{bmatrix} \text{Beer} \ \text{Milk} \end{bmatrix}, \begin{bmatrix} \text{Diap} \ \text{Powd} \end{bmatrix} \right} C2​剪掉包含非频繁子集的​L2​={[BeerDiap​],[BeerMilk​],[DiapPowd​]}
  3. 主循环：当前为 L 2 L_2 L2​- 组合： L 2 → 组合逻辑见下表 两两组合 C 3 = { [ Beer Diap Milk ] , [ Beer Diap Powd ] } L_2 \xrightarrow[组合逻辑见下表]{\text{两两组合}} C_3\text{=}\left{ \small \cancel{ \begin{bmatrix} \text{Beer} \ \text{Diap} \ \text{Milk} \ \end{bmatrix}}, \cancel{ \begin{bmatrix} \text{Beer} \ \text{Diap} \ \text{Powd} \end{bmatrix}}\right} L2​两两组合组合逻辑见下表​C3​={[BeerDiapMilk​]​,[BeerDiapPowd​]​}合并的集条件: 二者有 k -1 k\text{-1} k-1项(此处为 1 1 1)相等操作 L 2 [ 1 ] / L 2 [ 2 ] L_2[1]/L_2[2] L2​[1]/L2​[2]共有 Beer→ \text{Beer}\text{→} Beer→满足执行组合 L 2 [ 1 ] / L 2 [ 3 ] L_2[1]/L_2[3] L2​[1]/L2​[3]共有 Diap→ \text{Diap}\text{→} Diap→满足执行组合 L 2 [ 2 ] / L 2 [ 3 ] L_2[2]/L_2[3] L2​[2]/L2​[3]不满足不执行组合- 剪枝： C 2 → 剪掉包含非频繁子集的 L 3 = ∅ C_2\xrightarrow{剪掉包含非频繁子集的}L_3\text{=}\varnothing C2​剪掉包含非频繁子集的​L3​=∅，故终止循环
  4. 输出： L = L 1 ∪ L 2 = { Beer , Diap , Powd , Milk , [ Beer Diap ] , [ Beer Milk ] , [ Diap Powd ] } L\text{=}L_1\text{∪}L_2\text{=}\left{ \small \text{Beer}, \text{Diap}, \text{Powd}, \text{Milk}, \begin{bmatrix} \text{Beer} \ \text{Diap} \end{bmatrix}, \begin{bmatrix} \text{Beer} \ \text{Milk} \end{bmatrix}, \begin{bmatrix} \text{Diap} \ \text{Powd} \end{bmatrix} \right} L=L1​∪L2​={Beer,Diap,Powd,Milk,[BeerDiap​],[BeerMilk​],[DiapPowd​]}

2️⃣生成规则 

  1.        →  
  2.       
  3.       
  4.        
  5.         
  6.          
  7.           
  8.            
  9.            
  10.              Item 
  11.             
  12.            
  13.           
  14.           
  15.            
  16.            
  17.              Support(A,B) 
  18.             
  19.            
  20.           
  21.           
  22.            
  23.            
  24.              Support A 
  25.             
  26.            
  27.           
  28.           
  29.            
  30.            
  31.              Confidence 
  32.             
  33.            
  34.           
  35.          
  36.          
  37.           
  38.            
  39.             
  40.             
  41.               Beer 
  42.              
  43.             
  44.               → 
  45.              
  46.             
  47.               Diaper 
  48.              
  49.             
  50.            
  51.           
  52.           
  53.            
  54.             
  55.             
  56.               60 
  57.              
  58.             
  59.               % 
  60.              
  61.             
  62.            
  63.           
  64.           
  65.            
  66.             
  67.             
  68.               80 
  69.              
  70.             
  71.               % 
  72.              
  73.             
  74.            
  75.           
  76.           
  77.            
  78.             
  79.             
  80.               75 
  81.              
  82.             
  83.               % 
  84.              
  85.             
  86.            
  87.           
  88.          
  89.          
  90.           
  91.            
  92.             
  93.             
  94.               Beer 
  95.              
  96.             
  97.               → 
  98.              
  99.             
  100.               Milk 
  101.              
  102.             
  103.            
  104.           
  105.           
  106.            
  107.             
  108.             
  109.               40 
  110.              
  111.             
  112.               % 
  113.              
  114.             
  115.            
  116.           
  117.           
  118.            
  119.             
  120.             
  121.               80 
  122.              
  123.             
  124.               % 
  125.              
  126.             
  127.            
  128.           
  129.           
  130.            
  131.             
  132.             
  133.               50 
  134.              
  135.             
  136.               % 
  137.              
  138.             
  139.            
  140.           
  141.          
  142.          
  143.           
  144.            
  145.             
  146.             
  147.               Diaper 
  148.              
  149.             
  150.               → 
  151.              
  152.             
  153.               Powd 
  154.              
  155.             
  156.            
  157.           
  158.           
  159.            
  160.             
  161.             
  162.               40 
  163.              
  164.             
  165.               % 
  166.              
  167.             
  168.            
  169.           
  170.           
  171.            
  172.             
  173.             
  174.               80 
  175.              
  176.             
  177.               % 
  178.              
  179.             
  180.            
  181.           
  182.           
  183.            
  184.             
  185.             
  186.               50 
  187.              
  188.             
  189.               % 
  190.              
  191.             
  192.            
  193.           
  194.          
  195.          
  196.           
  197.            
  198.             
  199.             
  200.               Diaper 
  201.              
  202.             
  203.               → 
  204.              
  205.             
  206.               Beer 
  207.              
  208.             
  209.            
  210.           
  211.           
  212.            
  213.             
  214.             
  215.               60 
  216.              
  217.             
  218.               % 
  219.              
  220.             
  221.            
  222.           
  223.           
  224.            
  225.             
  226.             
  227.               80 
  228.              
  229.             
  230.               % 
  231.              
  232.             
  233.            
  234.           
  235.           
  236.            
  237.             
  238.             
  239.               75 
  240.              
  241.             
  242.               % 
  243.              
  244.             
  245.            
  246.           
  247.          
  248.          
  249.           
  250.            
  251.             
  252.             
  253.               Milk 
  254.              
  255.             
  256.               → 
  257.              
  258.             
  259.               Beer 
  260.              
  261.             
  262.            
  263.           
  264.           
  265.            
  266.             
  267.             
  268.               40 
  269.              
  270.             
  271.               % 
  272.              
  273.             
  274.            
  275.           
  276.           
  277.            
  278.             
  279.             
  280.               40 
  281.              
  282.             
  283.               % 
  284.              
  285.             
  286.            
  287.           
  288.           
  289.            
  290.             
  291.             
  292.               100 
  293.              
  294.             
  295.               % 
  296.              
  297.             
  298.            
  299.           
  300.          
  301.          
  302.           
  303.            
  304.             
  305.             
  306.               Powd 
  307.              
  308.             
  309.               → 
  310.              
  311.             
  312.               Diaper 
  313.              
  314.             
  315.            
  316.           
  317.           
  318.            
  319.             
  320.             
  321.               40 
  322.              
  323.             
  324.               % 
  325.              
  326.             
  327.            
  328.           
  329.           
  330.            
  331.             
  332.             
  333.               40 
  334.              
  335.             
  336.               % 
  337.              
  338.             
  339.            
  340.           
  341.           
  342.            
  343.             
  344.             
  345.               100 
  346.              
  347.             
  348.               % 
  349.              
  350.             
  351.            
  352.           
  353.          
  354.         
  355.        
  356.       
  357.          etc..... 
  358.        
  359.       
  360.      
  361.     
  362.       \text{→ } \small \begin{array}{|c|c|c|c|} \hline \text{Item} & \text{Support(A,B)} & \text{Support A} & \text{Confidence} \\ \hline \text{Beer} \to \text{Diaper} & 60 \% & 80 \% & 75 \% \\ \hline \text{Beer} \to \text{Milk} & 40 \% & 80 \% & 50 \% \\ \hline \text{Diaper} \to \text{Powd} & 40 \% & 80 \% & 50 \% \\ \hline \text{Diaper} \to \text{Beer} & 60 \% & 80 \% & 75 \% \\ \hline \text{Milk} \to \text{Beer} & 40 \% & 40 \% & 100 \% \\ \hline \text{Powd} \to \text{Diaper} & 40 \% & 40 \% & 100 \% \\ \hline \end{array} \text{ etc.....} 
  363.      
  364.     
  365.   → ItemBeer→DiaperBeer→MilkDiaper→PowdDiaper→BeerMilk→BeerPowd→Diaper​Support(A,B)60%40%40%60%40%40%​Support A80%80%80%80%40%40%​Confidence75%50%50%75%100%100%​​ etc.....

  1.      3. 
  2.     
  3.    
  4.        
  5.     
  6.    
  7.   
  8.     \textbf{3. } 
  9.    
  10.   
  11. 3. 多层关联规则挖掘

  1.       3.1. 
  2.      
  3.     
  4.         
  5.      
  6.     
  7.    
  8.      \textbf{3.1. } 
  9.     
  10.    
  11.  3.1. 算法概述

1️⃣基本概念

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

2️⃣每层最小支持度的设定
方法描述特点一致所有曾的最小支持度一致忽略底层(地层支持度一般较低)递减层次越低 

  1.           → 
  2.          
  3.         
  4.        
  5.          \text{→} 
  6.         
  7.        
  8.      →最小支持度越低保留底层罕见但有意义的规则分组专家指重点项集 
  9.       
  10.        
  11.         
  12.         
  13.           → 
  14.          
  15.         
  16.        
  17.          \text{→} 
  18.         
  19.        
  20.      →由此设置每层不同最小支持度 
  21.       
  22.        
  23.         
  24.         
  25.           N/A 
  26.          
  27.         
  28.        
  29.          \text{N/A} 
  30.         
  31.        
  32.      N/A

3️⃣分层挖掘：

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

  1.       3.2. 
  2.      
  3.     
  4.         
  5.      
  6.     
  7.    
  8.      \textbf{3.2. } 
  9.     
  10.    
  11.  3.2. 算法实例

0️⃣基本情况：

  1. 概念分层： 分层表示最大支持度第一层(顶层) {1**, 2**, 3**, 4**} \text{{1**, 2**, 3**, 4}} {1, 2**, 3**, 4**}等 4 4 4第二层(中层) {11*, 12*, 21*, 22*} \text{{11*, 12*, 21*, 22}} {11, 12*, 21*, 22*}等 3 3 3第三层(低层) {111, 121, 211, 713} \text{{111, 121, 211, 713}} {111, 121, 211, 713}等 3 3 3
  2. 事务集：第 i i i位表示在第 i i i层的分类，如 524 524 524表示在高/中/低层分属第 5 5 5/第 2 2 2/第 4 4 4类 TID \textbf{TID} TID底层中层顶层 T1 \text{T1} 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**} T2 \text{T2} 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**} T3 \text{T3} 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**} T4 \text{T4} T4 { 111,121 } {\text{111,121}} {111,121} { 11*,12* } {\text{11*,12*}} {11*,12*} { 1** } {\text{1**}} {1**} T5 \text{T5} 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**} T6 \text{T6} 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**} T7 \text{T7} 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️⃣顶层的 

  1.        Apriori 
  2.       
  3.      
  4.     
  5.       \text{Apriori} 
  6.      
  7.     
  8.   Apriori算法：最小支持度为 
  9.     
  10.      
  11.       
  12.       
  13.         4 
  14.        
  15.       
  16.      
  17.        4 
  18.       
  19.      
  20.    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 5 5的- 表过滤： L ( 1 , 1 ) L(1,1) L(1,1)中项的子节点必定以 1 / 2 1/2 1/2开头，故滤掉以其它开头的 TID \textbf{TID} TID当前事务表 T[1] \textbf{T[1]} T[1]滤后事务表 T[2] \textbf{T[2]} T[2] T1 \text{T1} 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} T2 \text{T2} T2 { 111,211,222,323 } {\text{111,211,222,323}} {111,211,222,323} { 111,211,222 } {\text{111,211,222}} {111,211,222} T3 \text{T3} T3 { 112,122,221,411 } {\text{112,122,221,411}} {112,122,221,411} { 112,122,221 } {\text{112,122,221}} {112,122,221} T4 \text{T4} T4 { 111,121 } {\text{111,121}} {111,121} { 111,121 } {\text{111,121}} {111,121} T5 \text{T5} 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} T6 \text{T6} T6 { 211,323,524 } {\text{211,323,524}} {211,323,524} { 211 } {\text{211}} {211} T7 \text{T7} T7 { 323,411,524,713 } {\text{323,411,524,713}} {323,411,524,713} { ∅ } {\varnothing} {∅}
  2. 主循环：当前为 L ( 1 , 1 ) L(1,1) 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 ] T[2] T[2]传给下一层

2️⃣中层的 

  1.        Apriori 
  2.       
  3.      
  4.     
  5.       \text{Apriori} 
  6.      
  7.     
  8.   Apriori算法：最小支持度为 
  9.     
  10.      
  11.       
  12.       
  13.         3 
  14.        
  15.       
  16.      
  17.        3 
  18.       
  19.      
  20.    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 3 3的- 事务表过滤： L ( 2 , 1 ) L(2,1) L(2,1)中项的子节点必定以 11 / 12 / 21 / 22 11/12/21/22 11/12/21/22开头，滤掉以其他开头的 TID \textbf{TID} TID当前事务表 T[2] \textbf{T[2]} T[2]滤后事务表 T[3] \textbf{T[3]} T[3] T1 \text{T1} 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} T2 \text{T2} T2 { 111,211,222 } {\text{111,211,222}} {111,211,222} { 111,211,222 } {\text{111,211,222}} {111,211,222} T3 \text{T3} T3 { 112,122,221 } {\text{112,122,221}} {112,122,221} { 112,122,221 } {\text{112,122,221}} {112,122,221} T4 \text{T4} T4 { 111,121 } {\text{111,121}} {111,121} { 111,121 } {\text{111,121}} {111,121} T5 \text{T5} 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} T6 \text{T6} T6 { 211 } {\text{211}} {211} { 211 } {\text{211}} {211} T7 \text{T7} T7 { ∅ } {\varnothing} {∅} { ∅ } {\varnothing} {∅}
  2. 主循环：当前为 L ( 2 , 1 ) L(2,1) 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) 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) 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 ) → 依据 T[3] 减去包含非频繁子集的 L ( 2 , 4 ) = ∅ → C(2,4) \xrightarrow[]{\text{依据 T[3] 减去包含非频繁子集的}} L(2,4) \text{=}\varnothing\text{ → } C(2,4)依据 T[3] 减去包含非频繁子集的​L(2,4)=∅ → 停止循环
  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)}；将滤后事务表 T[3] \text{T[3]} T[3]传到下一层image-20241117005904932

3️⃣底层的 

  1.        Apriori 
  2.       
  3.      
  4.     
  5.       \text{Apriori} 
  6.      
  7.     
  8.   Apriori算法：最小支持度为 
  9.     
  10.      
  11.       
  12.       
  13.         3 
  14.        
  15.       
  16.      
  17.        3 
  18.       
  19.      
  20.    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 3 3的- 事务表过滤：接下来只考虑 { {111},{211},{221} } {\text{{111},{211},{221}}} {{111},{211},{221}}中的，故滤掉其他的 TID \textbf{TID} TID当前事务表 T[3] \textbf{T[3]} T[3]滤后事务表 T[4] \textbf{T[4]} T[4] T1 \text{T1} T1 { 111,121,211,221 } {\text{111,121,211,221}} {111,121,211,221} { 111,,211,221 } {\text{111,,211,221}} {111,,211,221} T2 \text{T2} T2 { 111,211,222 } {\text{111,211,222}} {111,211,222} { 111,211 } {\text{111,211}} {111,211} T3 \text{T3} T3 { 112,122,221 } {\text{112,122,221}} {112,122,221} { 221 } {\text{221}} {221} T4 \text{T4} T4 { 111,121 } {\text{111,121}} {111,121} { 111 } {\text{111}} {111} T5 \text{T5} T5 { 111,122,211,221 } {\text{111,122,211,221}} {111,122,211,221} { 111,211,221 } {\text{111,211,221}} {111,211,221} T6 \text{T6} T6 { 211 } {\text{211}} {211} { 211 } {\text{211}} {211} T7 \text{T7} T7 { ∅ } {\varnothing} {∅} { ∅ } {\varnothing} {∅}
  2. 主循环：当前为 L ( 3 , 1 ) L(3,1) 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 ) → 依据 T[4] 减去包含非频繁子集的 L ( 3 , 2 ) ={111,221 } → C(3,2) \xrightarrow[]{\text{依据 T[4] 减去包含非频繁子集的}} L(3,2) \text{=}\text{{111,221}}\text{ → } C(3,2)依据 T[4] 减去包含非频繁子集的​L(3,2)={111,221} → 无法再组合(停止循环)
  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}}

  1.      4. 
  2.     
  3.    
  4.        
  5.     
  6.    
  7.   
  8.     \textbf{4. } 
  9.    
  10.   
  11. 4. 多维关联规则挖掘

1️⃣多维关联规则

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

2️⃣处理思路

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

3️⃣处理算法： 

  1.       ARCS 
  2.      
  3.     
  4.    
  5.      \text{ARCS} 
  6.     
  7.    
  8.  ARCS大致流程
  1. 分箱：根据数据的分布，将数值属性离散化到箱(固定区间)
  2. 搜索：找出频繁谓词集，得到一系列强关联规则(如下) - RuleSet = { age ( X , 35 ) ∧income ( X , 31 K … 40 K ) ⇒buys ( X , TV ) age ( X , 34 ) ∧income ( X , 41 K … 50 K ) ⇒buys ( X , TV ) age ( X , 35 ) ∧income ( X , 41 K … 50 K ) ⇒buys ( X , TV ) \text{RuleSet =}\begin{cases} \text{age}(X, 35) \text{∧} \text{income}(X, 31K \ldots 40K) \text{⇒} \text{buys}(X, \text{TV}) \\ \text{age}(X, 34) \text{∧} \text{income}(X, 41K \ldots 50K) \text{⇒} \text{buys}(X, \text{TV}) \\ \text{age}(X, 35) \text{∧} \text{income}(X, 41K \ldots 50K) \text{⇒} \text{buys}(X, \text{TV}) \end{cases} RuleSet =⎩⎨⎧​age(X,35)∧income(X,31K…40K)⇒buys(X,TV)age(X,34)∧income(X,41K…50K)⇒buys(X,TV)age(X,35)∧income(X,41K…50K)⇒buys(X,TV)​
  3. 聚类：将所得强关联规则映射到 2 D 2D 2D栅格上，得到范围矩形image-20241117015014348- RuleSet→age ( X , 34 - 35 ) ∧income ( X , 31 K - 40 K ) ⇒buys ( X , TV ) \text{RuleSet}\text{→}\text{age}(X,34\text{-}35) \text{∧} \text{income}(X, 31K\text{-}40K) \text{⇒} \text{buys}(X, \text{TV}) RuleSet→age(X,34-35)∧income(X,31K-40K)⇒buys(X,TV)
标签： 笔记 数据仓库 数据挖掘
本文转载自: https://blog.csdn.net/qq_64091900/article/details/143841041
版权归原作者 Dann Hiroaki 所有， 如有侵权，请联系我们删除。
登录后发布评论

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

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航