深入理解机器学习——关联规则挖掘：基础知识

分类目录：《深入理解机器学习》总目录

许多商业企业在日复一日的运营中积聚了大量的数据。例如，食品商店的收银台每天都收集大量的顾客购物数据。下图给出一个这种数据的例子，通常称作购物篮事务（Market Basket Transaction）。表中每一行对应一个事务，包含一个唯一标识TID和给定顾客购买的商品的集合。零售商对分析这些数据很感兴趣，以便了解他们的顾客的购买行为。可以使用这种有价值的信息来支持各种商务应用，如市场促销，库存管理和顾客关系管理等。

关联规则挖掘系列文章主要是介绍一种称作关联分析（Association Analysis）的方法，用于发现隐藏在大型数据集中的有意义的联系。所发现的联系可以用关联规则（Association Rule）或频繁项集的形式表示。例如，从上图数据中可以提取出如下规则：

尿布 → 啤酒

该规则表明尿布和啤酒的销售之间存在着很强的联系，因为许多购买尿布的顾客也购买啤酒。零售商们可以使用这类规则，帮助他们发现新的交叉销售商机。

除了购物篮数据外，关联分析也可以应用于其他领域，如生物信息学、医疗诊断、网页挖掘和科学数据分析等。例如，在地球科学数据分析中，关联模式可以揭示海洋、陆地和大气过程之间的有趣联系。这样的信息能够帮助地球科学家更好地理解地球系统中不同的自然力之间的相互作用。尽管这里提供的技术一般可以都用于更广泛的数据集，但是为了便于解释，讨论将主要集中在购物篮数据上。

在对购物篮数据进行关联分析时，需要处理两个关键的问题：第一，从大型事务数据集中发现模式可能在计算上要付出很高的代价：第二，所发现的某些模式可能是虚假的，因为它们可能是偶然发生的。

二元表示

购物篮数据可以用下图所示的二元形式来表示，其中每行对应一个事务，而每列对应一个项。项可以用二元变量表示，如果项在事务中出现，则它的值为1，否则为0。因为通常认为项在事务中出现比不出现更重要，因此项是非对称（Asymmetric）二元变量。或许这种表示是实际购物篮数据极其简单的展现，因为这种表示忽略数据的某些重要的方面，如所购商品的数量和价格等。

项集和支持度计数

令

     I 
    
   
     = 
    
   
     { 
    
    
    
      i 
     
    
      1 
     
    
   
     , 
    
    
    
      i 
     
    
      2 
     
    
   
     , 
    
   
     ⋯ 
     
   
     , 
    
    
    
      i 
     
    
      d 
     
    
   
     } 
    
   
  
    I=\{i_1, i_2, \cdots, i_d\} 
   
  
I={i1​,i2​,⋯,id​}是购物篮数据中所有项的集合，而 
 
  
   
   
     T 
    
   
     = 
    
   
     { 
    
    
    
      t 
     
    
      1 
     
    
   
     , 
    
    
    
      t 
     
    
      2 
     
    
   
     , 
    
   
     ⋅ 
    
   
     , 
    
    
    
      t 
     
    
      N 
     
    
   
     } 
    
   
  
    T=\{t_1, t_2, \cdot, t_N\} 
   
  
T={t1​,t2​,⋅,tN​}是所有事务的集合。每个事务 
 
  
   
    
    
      t 
     
    
      i 
     
    
   
  
    t_i 
   
  
ti​包含的项集都是 
 
  
   
   
     I 
    
   
  
    I 
   
  
I的子集。在关联分析中，包含0个或多个项的集合被称为项集（Itemset）。如果一个项集包含 
 
  
   
   
     k 
    
   
  
    k 
   
  
k个项，则称它为 
 
  
   
   
     k 
    
   
  
    k 
   
  
k-项集。例如，{啤酒，尿布，牛奶}是一个3-项集，而空集是指不包含任何项的项集。

事务的宽度定义为事务中出现项的个数。如果项集

     X 
    
   
  
    X 
   
  
X是事务 
 
  
   
    
    
      t 
     
    
      j 
     
    
   
  
    t_j 
   
  
tj​的子集，则称事务 
 
  
   
    
    
      t 
     
    
      j 
     
    
   
  
    t_j 
   
  
tj​包括项集 
 
  
   
   
     X 
    
   
  
    X 
   
  
X。例如，在上图中第二个事务包括项集{面包，尿布}，但不包括项集{面包，牛奶}。项集的一个重要性质是它的支持度计数，即包含特定项集的事务个数。数学上，项集 
 
  
   
   
     X 
    
   
  
    X 
   
  
X的支持度计数 
 
  
   
   
     σ 
    
   
     ( 
    
   
     X 
    
   
     ) 
    
   
  
    \sigma(X) 
   
  
σ(X)可以表示为：
  
   
    
    
      σ 
     
    
      ( 
     
    
      X 
     
    
      ) 
     
    
      = 
     
    
      ∣ 
     
    
      { 
     
     
     
       t 
      
     
       i 
      
     
    
      ∣ 
     
    
      X 
     
    
      ⊆ 
     
     
     
       t 
      
     
       i 
      
     
    
      , 
     
     
     
       t 
      
     
       i 
      
     
    
      ∈ 
     
    
      T 
     
    
      } 
     
    
      ∣ 
     
    
   
     \sigma(X)=|\{t_i|X\subseteq t_i, t_i\in T\}| 
    
   
 σ(X)=∣{ti​∣X⊆ti​,ti​∈T}∣

其中，符号

     ∣ 
    
   
     ⋅ 
    
   
     ∣ 
    
   
  
    |·| 
   
  
∣⋅∣表示集合中元素的个数。在上图显示的数据集中，项集{啤酒，尿布，牛奶}的支持度计数为2，因为只有2个事务同时包含这3个项。

关联规则（Association Rule）

关联规则是形如

     X 
    
   
     → 
    
   
     Y 
    
   
  
    X\rightarrow Y 
   
  
X→Y的蕴涵表达式，其中 
 
  
   
   
     X 
    
   
  
    X 
   
  
X和 
 
  
   
   
     Y 
    
   
  
    Y 
   
  
Y是不相交的项集，即 
 
  
   
   
     X 
    
   
     ∩ 
    
   
     Y 
    
   
     = 
    
   
     ∅ 
    
   
  
    X\cap Y=\varnothing 
   
  
X∩Y=∅。关联规则的强度可以用它的支持度（Support）和置信度`（Confidence）度量。支持度确定规则可以用于给定数据集的频繁程度，而置信度确定 
 
  
   
   
     Y 
    
   
  
    Y 
   
  
Y在包含 
 
  
   
   
     X 
    
   
  
    X 
   
  
X的事务中出现的频繁程度。支持度 
 
  
   
   
     s 
    
   
  
    s 
   
  
s和置信度 
 
  
   
   
     c 
    
   
  
    c 
   
  
c这两种度量的形式定义如下：
  
   
    
     
      
       
        
        
          s 
         
        
          ( 
         
        
          X 
         
        
          → 
         
        
          Y 
         
        
          ) 
         
        
       
      
      
       
        
         
        
          = 
         
         
          
          
            σ 
           
          
            ( 
           
          
            X 
           
          
            ∪ 
           
          
            Y 
           
          
            ) 
           
          
         
           N 
          
         
        
       
      
     
     
      
       
        
        
          c 
         
        
          ( 
         
        
          X 
         
        
          → 
         
        
          Y 
         
        
          ) 
         
        
       
      
      
       
        
         
        
          = 
         
         
          
          
            σ 
           
          
            ( 
           
          
            X 
           
          
            ∪ 
           
          
            Y 
           
          
            ) 
           
          
          
          
            σ 
           
          
            ( 
           
          
            X 
           
          
            ) 
           
          
         
        
       
      
     
    
   
     \begin{align*} s(X\rightarrow Y) & =\frac{\sigma(X\cup Y)}{N}\\ c(X\rightarrow Y) & =\frac{\sigma(X\cup Y)}{\sigma(X)} \end{align*} 
    
   
 s(X→Y)c(X→Y)​=Nσ(X∪Y)​=σ(X)σ(X∪Y)​​

考虑规则{牛奶，尿布} → {啤酒}，由于项集{牛奶，尿布，啤酒}的支持度计数是2，而事务的总数是5，所以规则的支持度为

      2 
     
    
      5 
     
    
   
     = 
    
   
     0.4 
    
   
  
    \frac{2}{5}=0.4 
   
  
52​=0.4。置信度是项集{牛奶，尿布，啤酒}的支持度计数与项集{牛奶，尿布}支持度计数的商。由于存在3个事务同时包含牛奶和尿布，所以该规则的置信度为 
 
  
   
    
    
      2 
     
    
      3 
     
    
   
     = 
    
   
     0.67 
    
   
  
    \frac{2}{3}=0.67 
   
  
32​=0.67。

支持度是一种重要度量，因为支持度很低的规则可能只是偶然出现。从商务角度来看，低支持度的规则多半也是无意义的，因为对顾客很少同时购买的商品进行促销可能并无益处。因此，支持度通常用来删去那些无意义的规则。此外，支持度还具有一种期望的性质，可以用于关联规则的有效发现。另一方面，置信度度量通过规则进行推理具有可靠性。对于给定的规则

     X 
    
   
     → 
    
   
     Y 
    
   
  
    X\rightarrow Y 
   
  
X→Y，置信度越高， 
 
  
   
   
     Y 
    
   
  
    Y 
   
  
Y在包含 
 
  
   
   
     X 
    
   
  
    X 
   
  
X的事务中出现的可能性就越大。置信度也可以估计 
 
  
   
   
     Y 
    
   
  
    Y 
   
  
Y在给定 
 
  
   
   
     X 
    
   
  
    X 
   
  
X下的条件概率。

应当小心解释关联分析的结果。由关联规则作出的推论并不必然蕴涵因果关系。它只表示规则前件和后件中的项明显地同时出现。另一方面，因果关系需要关于数据中原因和结果属性的知识，并且通常涉及长期出现的联系。

关联规则的挖掘问题可以形式地描述如下：关联规则发现给定事务的集合

     T 
    
   
  
    T 
   
  
T，关联规则发现是指找出支持度大于等于 
 
  
   
   
     minsup 
    
   
  
    \text{minsup} 
   
  
minsup，并且置信度大于等于 
 
  
   
   
     minconf 
    
   
  
    \text{minconf} 
   
  
minconf的所有规则，其中 
 
  
   
   
     minsup 
    
   
  
    \text{minsup} 
   
  
minsup和 
 
  
   
   
     minconf 
    
   
  
    \text{minconf} 
   
  
minconf是对应的支持度和置信度阀值。

控据关联规则的一种原始方法是：计算每个可能规则的支持度和置信度。但是这种方法的代价很高，令人望而却步，因为可以从数据集提取的规则的数目达指数级。更具体地说，从包含

     d 
    
   
  
    d 
   
  
d个项的数据集提取的可能规则的总数为：
  
   
    
    
      R 
     
    
      = 
     
     
     
       3 
      
     
       d 
      
     
    
      + 
     
     
     
       2 
      
      
      
        d 
       
      
        + 
       
      
        1 
       
      
     
    
      + 
     
    
      1 
     
    
   
     R=3^d+2^{d+1}+1 
    
   
 R=3d+2d+1+1

提高关联规则挖掘算法性能的第一步是拆分支持度和置信度要求。由前文可知，规则

     X 
    
   
     → 
    
   
     Y 
    
   
  
    X\rightarrow Y 
   
  
X→Y的支持度仅依赖于其对应项集 
 
  
   
   
     X 
    
   
     ∪ 
    
   
     Y 
    
   
  
    X\cup Y 
   
  
X∪Y的支持度。例如，{啤酒，尿布} 
 
  
   
   
     → 
    
   
  
    \rightarrow 
   
  
→{牛奶}和{啤酒，牛奶} 
 
  
   
   
     → 
    
   
  
    \rightarrow 
   
  
→{尿布}有相同的支持度，因为它们涉及的项都源自同一个项集{啤酒，尿布，牛奶}。

如果项集{啤酒，尿布，牛奶}是非频繁的，则可以立即剪掉所有相关的候选规则（如：{啤酒，尿布}

     → 
    
   
  
    \rightarrow 
   
  
→{牛奶}、{啤酒，牛奶} 
 
  
   
   
     → 
    
   
  
    \rightarrow 
   
  
→{尿布}、{尿布，牛奶} 
 
  
   
   
     → 
    
   
  
    \rightarrow 
   
  
→{啤酒}等），而不必计算它们的置信度值。

因此，大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：

• 频繁项集产生：其目标是发现满足最小支持度阀值的所有项集，这些项集称作频繁项集（Frequent Itemset）。
• 规则的产生：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（Strongrule）。

通常，频繁项集产生所需的计算开销远大于产生规则所需的计算开销。频繁项集和关联规产生的有效技术将在后续文章中讨论。

参考文献：
[1] Pang-NingTan, MichaelSteinbach, VipinKumar. 数据挖掘导论[M]. 人民邮电出版社, 2006.