0
0

机器学习：详解半朴素贝叶斯分类AODE原理(附Python实现)

目录

0 写在前面

机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理；“广”在分析多个机器学习模型：决策树、支持向量机、贝叶斯与马尔科夫决策、强化学习等。

🚀详情：机器学习强基计划(附几十种经典模型源码合集)

1 独依赖假设

在机器学习强基计划4-3：详解朴素贝叶斯分类原理 | 例题分析 | Python实现中我们介绍了朴素贝叶斯之所以“朴素”，是因为其给定了很强的属性独立性假设。然而，属性独立性假设在实际上很难成立，因此引入半朴素贝叶斯分类器(Semi-Naïve Bayes Classifier)，其核心思想是：适当考虑部分属性的相互依赖，从而既简化了联合概率计算，又不至于彻底忽略属性间的强依赖关系。

在这里插入图片描述

半朴素贝叶斯分类器最常见的建模策略是**独依赖估计(One-Dependent Estimator, ODE)**，即假设每个属性在类别外最多依赖于一个属性

  1.       f
  2.      
  3.      
  4.       ∗
  5.      
  6.     
  7.     
  8.      
  9.       (
  10.      
  11.      
  12.       x
  13.      
  14.      
  15.       )
  16.      
  17.     
  18.     
  19.      =
  20.     
  21.     
  22.      
  23.       
  24.        
  25.         
  26.          a
  27.         
  28.         
  29.          r
  30.         
  31.         
  32.          g
  33.         
  34.        
  35.        
  36.         max
  37.        
  38.        
  39.         ⁡
  40.        
  41.       
  42.       
  43.        
  44.         C
  45.        
  46.        
  47.         ∈
  48.        
  49.        
  50.         Y
  51.        
  52.       
  53.      
  54.     
  55.     
  56.      P
  57.     
  58.     
  59.      
  60.       (
  61.      
  62.      
  63.       C
  64.      
  65.      
  66.       )
  67.      
  68.     
  69.     
  70.      
  71.       ∏
  72.      
  73.      
  74.       
  75.        i
  76.       
  77.       
  78.        =
  79.       
  80.       
  81.        1
  82.       
  83.      
  84.      
  85.       d
  86.      
  87.     
  88.     
  89.      
  90.       P
  91.      
  92.      
  93.       
  94.        (
  95.       
  96.       
  97.        
  98.         x
  99.        
  100.        
  101.         i
  102.        
  103.       
  104.       
  105.        ∣
  106.       
  107.       
  108.        C
  109.       
  110.       
  111.        ,
  112.       
  113.       
  114.        p
  115.       
  116.       
  117.        
  118.         a
  119.        
  120.        
  121.         i
  122.        
  123.       
  124.       
  125.        )
  126.       
  127.      
  128.     
  129.    
  130.    
  131.     {f^*\left( \boldsymbol{x} \right) =\underset{C\in \mathcal{Y}}{\mathrm{arg}\max}P\left( C \right) \prod_{i=1}^d{P\left( x_i|C, pa_i \right)}}
  132.    
  133.   
  134.  f∗(x)=C∈Yargmax​P(C)i=1∏d​P(xi​∣C,pai​)

其中

  1.     p
  2.    
  3.    
  4.     
  5.      a
  6.     
  7.     
  8.      i
  9.     
  10.    
  11.   
  12.   
  13.    pa_i
  14.   
  15.  
  16. pai​为属性
  18.  
  19.   
  20.    
  21.     
  22.      x
  23.     
  24.     
  25.      i
  26.     
  27.    
  28.   
  29.   
  30.    x_i
  31.   
  32.  
  33. xi​所依赖的父属性。若对
  35.  
  36.   
  37.    
  38.     ∀
  39.    
  40.    
  41.     
  42.      x
  43.     
  44.     
  45.      i
  46.     
  47.    
  48.   
  49.   
  50.    \forall x_i
  51.   
  52.  
  53. ∀xi​确定了其
  55.  
  56.   
  57.    
  58.     p
  59.    
  60.    
  61.     
  62.      a
  63.     
  64.     
  65.      i
  66.     
  67.    
  68.   
  69.   
  70.    pa_i
  71.   
  72.  
  73. pai​，则可按朴素贝叶斯的方式进行贝叶斯分类，因此问题的核心转换为如何确定
  75.  
  76.   
  77.    
  78.     p
  79.    
  80.    
  81.     
  82.      a
  83.     
  84.     
  85.      i
  86.     
  87.    
  88.   
  89.   
  90.    pa_i
  91.   
  92.  
  93. pai​。

另一个问题是，可以假设属性依赖多个父属性吗？答案是：高阶依赖估计的准确性要求训练样本随指数级增加，在有限样本条件下，一般不适合采用。

2 AODE原理

先介绍一个比较直接的想法——假设所有属性都依赖于同一个父属性，称该属性为**超父(super-parent)，这种半朴素贝叶斯分类器称为SPODE(Super-Parent ODE)**算法。

  1.       f
  2.      
  3.      
  4.       ∗
  5.      
  6.     
  7.     
  8.      
  9.       (
  10.      
  11.      
  12.       x
  13.      
  14.      
  15.       )
  16.      
  17.     
  18.     
  19.      =
  20.     
  21.     
  22.      
  23.       
  24.        
  25.         
  26.          a
  27.         
  28.         
  29.          r
  30.         
  31.         
  32.          g
  33.         
  34.        
  35.        
  36.         max
  37.        
  38.        
  39.         ⁡
  40.        
  41.       
  42.       
  43.        
  44.         C
  45.        
  46.        
  47.         ∈
  48.        
  49.        
  50.         Y
  51.        
  52.       
  53.      
  54.     
  55.     
  56.      P
  57.     
  58.     
  59.      
  60.       (
  61.      
  62.      
  63.       C
  64.      
  65.      
  66.       )
  67.      
  68.     
  69.     
  70.      
  71.       ∏
  72.      
  73.      
  74.       
  75.        i
  76.       
  77.       
  78.        =
  79.       
  80.       
  81.        1
  82.       
  83.      
  84.      
  85.       d
  86.      
  87.     
  88.     
  89.      
  90.       P
  91.      
  92.      
  93.       
  94.        (
  95.       
  96.       
  97.        
  98.         x
  99.        
  100.        
  101.         i
  102.        
  103.       
  104.       
  105.        ∣
  106.       
  107.       
  108.        C
  109.       
  110.       
  111.        ,
  112.       
  113.       
  114.        p
  115.       
  116.       
  117.        a
  118.       
  119.       
  120.        )
  121.       
  122.      
  123.     
  124.    
  125.    
  126.     f^*\left( \boldsymbol{x} \right) =\underset{C\in \mathcal{Y}}{\mathrm{arg}\max}P\left( C \right) \prod_{i=1}^d{P\left( x_i|C, pa \right)}
  127.    
  128.   
  129.  f∗(x)=C∈Yargmax​P(C)i=1∏d​P(xi​∣C,pa)

建立在SPODE的基础上，**AODE(Averaged ODE)**算法是一种基于集成学习机制、更为强大的ODE分类器，其将每个属性作为超父构造SPODE，再加权计算各属性间的平均依赖，即

  1.       f
  2.      
  3.      
  4.       ∗
  5.      
  6.     
  7.     
  8.      
  9.       (
  10.      
  11.      
  12.       x
  13.      
  14.      
  15.       )
  16.      
  17.     
  18.     
  19.      =
  20.     
  21.     
  22.      
  23.       
  24.        
  25.         
  26.          a
  27.         
  28.         
  29.          r
  30.         
  31.         
  32.          g
  33.         
  34.        
  35.        
  36.         max
  37.        
  38.        
  39.         ⁡
  40.        
  41.       
  42.       
  43.        
  44.         C
  45.        
  46.        
  47.         ∈
  48.        
  49.        
  50.         Y
  51.        
  52.       
  53.      
  54.     
  55.     
  56.      
  57.       ∑
  58.      
  59.      
  60.       
  61.        i
  62.       
  63.       
  64.        =
  65.       
  66.       
  67.        1
  68.       
  69.       
  70.        ,
  71.       
  72.       
  73.        ∣
  74.       
  75.       
  76.        
  77.         D
  78.        
  79.        
  80.         
  81.          x
  82.         
  83.         
  84.          i
  85.         
  86.        
  87.       
  88.       
  89.        ∣
  90.       
  91.       
  92.        ⩾
  93.       
  94.       
  95.        m
  96.       
  97.      
  98.      
  99.       d
  100.      
  101.     
  102.     
  103.      
  104.       P
  105.      
  106.      
  107.       
  108.        (
  109.       
  110.       
  111.        C
  112.       
  113.       
  114.        ,
  115.       
  116.       
  117.        
  118.         x
  119.        
  120.        
  121.         i
  122.        
  123.       
  124.       
  125.        )
  126.       
  127.      
  128.      
  129.       
  130.        ∏
  131.       
  132.       
  133.        
  134.         j
  135.        
  136.        
  137.         =
  138.        
  139.        
  140.         1
  141.        
  142.       
  143.       
  144.        d
  145.       
  146.      
  147.      
  148.       
  149.        P
  150.       
  151.       
  152.        
  153.         (
  154.        
  155.        
  156.         
  157.          x
  158.         
  159.         
  160.          j
  161.         
  162.        
  163.        
  164.         ∣
  165.        
  166.        
  167.         C
  168.        
  169.        
  170.         ,
  171.        
  172.        
  173.         
  174.          x
  175.         
  176.         
  177.          i
  178.         
  179.        
  180.        
  181.         )
  182.        
  183.       
  184.      
  185.     
  186.    
  187.    
  188.     f^*\left( \boldsymbol{x} \right) =\underset{C\in \mathcal{Y}}{\mathrm{arg}\max}\sum_{i=1,|\boldsymbol{D}_{x_i}|\geqslant m}^d{P\left( C,x_i \right) \prod_{j=1}^d{P\left( x_j|C, x_i \right)}}
  189.    
  190.   
  191.  f∗(x)=C∈Yargmax​i=1,∣Dxi​​∣⩾m∑d​P(C,xi​)j=1∏d​P(xj​∣C,xi​)

其中

  1.      D
  2.     
  3.     
  4.      
  5.       x
  6.      
  7.      
  8.       i
  9.      
  10.     
  11.    
  12.   
  13.   
  14.    \boldsymbol{D}_{x_i}
  15.   
  16.  
  17. Dxi​​为第
  19.  
  20.   
  21.    
  22.     i
  23.    
  24.   
  25.   
  26.    i
  27.   
  28.  
  29. i属性上取值为
  31.  
  32.   
  33.    
  34.     
  35.      x
  36.     
  37.     
  38.      i
  39.     
  40.    
  41.   
  42.   
  43.    x_i
  44.   
  45.  
  46. xi​的样本子集，
  48.  
  49.   
  50.    
  51.     m
  52.    
  53.   
  54.   
  55.    m
  56.   
  57.  
  58. m默认设为30。类似地，AODE的拉普拉斯平滑修正为
  60.  
  61.   
  62.    
  63.     
  64.      {
  65.     
  66.     
  67.      
  68.       
  69.        
  70.         
  71.          
  72.           P
  73.          
  74.          
  75.           
  76.            (
  77.           
  78.           
  79.            C
  80.           
  81.           
  82.            ,
  83.           
  84.           
  85.            
  86.             x
  87.            
  88.            
  89.             i
  90.            
  91.           
  92.           
  93.            )
  94.           
  95.          
  96.          
  97.           =
  98.          
  99.          
  100.           
  101.            
  102.             ∣
  103.            
  104.            
  105.             
  106.              D
  107.             
  108.             
  109.              
  110.               C
  111.              
  112.              
  113.               ,
  114.              
  115.              
  116.               
  117.                x
  118.               
  119.               
  120.                i
  121.               
  122.              
  123.             
  124.            
  125.            
  126.             ∣
  127.            
  128.            
  129.             +
  130.            
  131.            
  132.             1
  133.            
  134.           
  135.           
  136.            
  137.             ∣
  138.            
  139.            
  140.             D
  141.            
  142.            
  143.             ∣
  144.            
  145.            
  146.             +
  147.            
  148.            
  149.             N
  150.            
  151.            
  152.             ×
  153.            
  154.            
  155.             
  156.              N
  157.             
  158.             
  159.              i
  160.             
  161.            
  162.           
  163.          
  164.         
  165.        
  166.       
  167.      
  168.      
  169.       
  170.        
  171.         
  172.          
  173.           P
  174.          
  175.          
  176.           
  177.            (
  178.           
  179.           
  180.            
  181.             x
  182.            
  183.            
  184.             j
  185.            
  186.           
  187.           
  188.            ∣
  189.           
  190.           
  191.            C
  192.           
  193.           
  194.            ,
  195.           
  196.           
  197.            
  198.             x
  199.            
  200.            
  201.             i
  202.            
  203.           
  204.           
  205.            )
  206.           
  207.          
  208.          
  209.           =
  210.          
  211.          
  212.           
  213.            
  214.             ∣
  215.            
  216.            
  217.             
  218.              D
  219.             
  220.             
  221.              
  222.               C
  223.              
  224.              
  225.               ,
  226.              
  227.              
  228.               
  229.                x
  230.               
  231.               
  232.                i
  233.               
  234.              
  235.              
  236.               ,
  237.              
  238.              
  239.               
  240.                x
  241.               
  242.               
  243.                j
  244.               
  245.              
  246.             
  247.            
  248.            
  249.             ∣
  250.            
  251.            
  252.             +
  253.            
  254.            
  255.             1
  256.            
  257.           
  258.           
  259.            
  260.             ∣
  261.            
  262.            
  263.             
  264.              D
  265.             
  266.             
  267.              
  268.               C
  269.              
  270.              
  271.               ,
  272.              
  273.              
  274.               
  275.                x
  276.               
  277.               
  278.                i
  279.               
  280.              
  281.             
  282.            
  283.            
  284.             ∣
  285.            
  286.            
  287.             +
  288.            
  289.            
  290.             
  291.              N
  292.             
  293.             
  294.              j
  295.             
  296.            
  297.           
  298.          
  299.         
  300.        
  301.       
  302.      
  303.     
  304.    
  305.    
  306.     \begin{cases} P\left( C,x_i \right) =\frac{|\boldsymbol{D}_{C,x_i}|+1}{|\boldsymbol{D}|+N\times N_i}\\ P\left( x_j|C,x_i \right) =\frac{|\boldsymbol{D}_{C,x_i,x_j}|+1}{|\boldsymbol{D}_{C,x_i}|+N_j}\\\end{cases}
  307.    
  308.   
  309.  ⎩⎨⎧​P(C,xi​)=∣D∣+N×Ni​∣DC,xi​​∣+1​P(xj​∣C,xi​)=∣DC,xi​​∣+Nj​∣DC,xi​,xj​​∣+1​​

简单说，AODE就是SPODE的加权平均版本

在这里插入图片描述

接下来基于上述原理开始编程，并和朴素贝叶斯分类做个比较，看性能有没提升

3 Python实现

3.1 计算类先验概率

  1. '''
  2. * @breif: 计算类先验概率P(C, xi)
  3. * @param[in]: None
  4. * @retval: None
  6. {
  7.     C1: { 
  8.             超父属性(只能是离散属性)
  9.             pa1: {
  10.                     超父属性值
  11.                     px1: {
  12.                             p: p(C1, x1)
  13.                             N: n(C1, x1)
  14.                         }
  15.                     ...
  16.                     pxn: ...
  17.                     num(pa1): int 属性a1的可取值数
  18.                 }
  19.             ...
  20.             pan: ...
  21.         }
  22.     ...
  23.     Cn: ...
  24.     num: 类别数
  25. }
  27. '''defcalPrior(self):# 可选的类别数
  28.     label = np.unique(self.y)
  29.     self.prior['num']=len(label)# 计算先验概率for _label in label:
  30.         self.prior[_label]={}# 获取标签取值_label的样本集
  31.         labelIndex = np.squeeze(np.argwhere(np.squeeze(self.y)==_label))
  32.         labelX = self.X[:, labelIndex]# 超父特征层for i inrange(self.d):# 属性i的可选属性值列表
  33.             attr = np.unique(self.X[i,:])# 可选属性数
  34.             attrNum =len(attr)# 离散属性(只有离散属性能作为超父属性)if attrNum <=0.85* self.m:
  35.                 self.prior[_label][str(i)]={}
  36.                 self.prior[_label][str(i)]['num']= attrNum
  37.                 # 计算每个取值的联合先验概率for a in attr:
  38.                     self.prior[_label][str(i)][a]={}
  39.                     n =int(sum(labelX[i,:]== a))
  40.                     self.prior[_label][str(i)][a]['p']=(n + self.laplace)/(self.m + self.prior['num']* attrNum)
  41.                     self.prior[_label][str(i)][a]['N']= n

3.2 计算属性后验概率

  1. '''
  2. * @breif: 计算属性后验概率P(xj|C, xi)
  3. * @param[in]: None
  4. * @retval: None
  6. {
  7.     C1: { 
  8.             超父属性(只能是离散属性)
  9.             pa1: {
  10.                     超父属性值
  11.                     px1: {
  12.                             常规属性
  13.                             a1: {
  14.                                     type: discrete 离散属性
  15.                                     x1: p(x1)
  16.                                     ...
  17.                                     xn: p(xn)
  18.                                     num(a1): int 属性b1的可取值数
  19.                                 }
  20.                             a2: {
  21.                                     type: continous 连续属性
  22.                                     mean: 样本均值
  23.                                     std: 标准差
  24.                                 }
  25.                         }
  26.                     ...
  27.                     pxn: ...
  28.                 }
  29.             ...
  30.             pan: ...
  31.         }
  32.     ...
  33.     Cn: ...
  34.     num: 类别数
  35. }
  37. '''defcalPosterior(self):ifnot self.prior:raise ValueError("please calculate prior first!")# 可选的类别数
  38.     label = np.unique(self.y)
  39.     self.posterior['num']=len(label)# 标签层for _label in label:
  40.         self.posterior[_label]={}# 获取标签取值_label的样本集
  41.         labelIndex = np.squeeze(np.argwhere(np.squeeze(self.y)==_label))
  42.         labelX = self.X[:, labelIndex]# 超父特征层for pa, paDict in self.prior[_label].items():
  43.             self.posterior[_label][pa]={}# 超父属性值层for paVal, paValDict in paDict.items():ifisinstance(paValDict,dict):
  44.                     self.posterior[_label][pa][paVal]={}# 常规属性层for i inrange(self.d):# 常规属性为超父属性则跳过if i == pa:continue# 获取超父属性值为paVal的样本子集
  45.                         paIndex = np.squeeze(np.argwhere(labelX[int(pa),:]==paVal))
  46.                         paLabelX = labelX[:, paIndex].reshape(self.d,-1)
  47.                         _, mpa = paLabelX.shape
  49.                         self.posterior[_label][pa][paVal][str(i)]={}# 属性i的可选属性值列表
  50.                         attr = np.unique(self.X[i,:])# 可选属性数
  51.                         attrNum =len(attr)# 离散属性if attrNum <=0.85* self.m:
  52.                             self.posterior[_label][pa][paVal][str(i)]['num']= attrNum
  53.                             self.posterior[_label][pa][paVal][str(i)]['type']='discrete'# 计算每个取值的后验概率for a in attr:
  54.                                 n =int(sum(paLabelX[i,:]== a))
  55.                                 self.posterior[_label][pa][paVal][str(i)][a]= \
  56.                                     (n + self.laplace)/(self.prior[_label][pa][paVal]['N']+ attrNum)# 连续属性else:
  57.                             self.posterior[_label][pa][paVal][str(i)]['type']='continous'# 发生的概率足够大，才会产生足够的样本if mpa >1:
  58.                                 self.posterior[_label][pa][paVal][str(i)]['std']= paLabelX[i,:].std(ddof=1)
  59.                                 self.posterior[_label][pa][paVal][str(i)]['mean']= paLabelX[i,:].mean()else:
  60.                                 self.posterior[_label][pa][paVal][str(i)]['std']= self.sigmaEpi
  61.                                 self.posterior[_label][pa][paVal][str(i)]['mean']=0

3.3 预测

采用机器学习强基计划2-3：图文详解决策树预剪枝、后剪枝原理+Python实现的数据集训练，获得准确率如下

  1. model = AODE(X, y)# 训练模型
  2. model.train()# 模型预测
  3. predictY = model.predict(X)print("错误:", np.sum(predictY!=y.T),"个\n准确率为:", np.sum(predictY==y.T)/y.size)>>> 错误:0 个
  4. >>> 准确率为:1.0

而在机器学习强基计划4-3：详解朴素贝叶斯分类原理 | 例题分析 | Python实现中准确率只有83.2%，可见适当的依赖性假设有助于提高分类准确率

完整代码联系下方博主名片获取

🔥 更多精彩专栏：

  • 《ROS从入门到精通》
  • 《机器人原理与技术》
  • 《机器学习强基计划》
  • 《计算机视觉教程》
  • …

👇源码获取 · 技术交流 · 抱团学习 · 咨询分享 请联系👇

标签： 机器学习 python 分类
本文转载自: https://blog.csdn.net/FRIGIDWINTER/article/details/127087623
版权归原作者 Mr.Winter` 所有， 如有侵权，请联系我们删除。
登录后发布评论

“机器学习：详解半朴素贝叶斯分类AODE原理(附Python实现)”的评论:

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

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

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

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

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

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

Kafka学习笔记

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