semi-Naive Bayesian（半朴素贝叶斯）

semi-Naive Bayesian（半朴素贝叶斯）

引言

朴素贝叶斯算法是基于特征是相互独立这个假设开展的（为了降低贝叶斯公式:$P(c|x)=\frac{P(c)P(x|c)}{P(x)}$中后验概率$P(c|x)$的困难），但在现实中这个假设往往很难成立。对条件独立假设进行适当的放宽，便引申出了“半朴素贝叶斯”。半朴素的意思就是，在朴素和非朴素之间寻找平衡，并不完全遵从条件独立，也不完全符合现实情况。

原理

在朴素贝叶斯中，对一个样本进行预测就是要找最大概率对应的类别，即
$$argma{x}_{c_k}p(c_k)\prod _{i=1}^{d}P(x_i|c_l)$$
半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息，从而既不需进行完全联合概率计算，又不至于彻底忽略了比较强的属性依赖关系。“独依赖估计”（One-Dependent Estimator，简称ODE）是半朴素贝叶斯分类器最常用的一种策略。“独依赖”就是假设每个属性在类别之外最多仅依赖于一个其他属性，即:
$$p(c|x)\propto p(c_k)\prod _{i=1}^{d}p(x_i|c_k,p{a}_i)$$
其中$p{a}_i$为属性$x_i$所依赖的属性，称为$x_i$的父属性。此时，对每个属性$x_i$，若其父属性$p{a}_i$已知，则可采用类似
$$\hat{p}(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$$
的方法来估计概率值$p(x_i|c,p{a}_i)$。于是，问题就转化为如何确定每个属性的父属性，不同的做法产生不同的独依赖分类器。

根据不同确定父属性可以有不同的半朴素贝叶斯分类器：

1. 选择贝叶斯分类器(SBC:Selective Bayesian Classifier)
2. 超父独依赖估计分类器(SPODE:Super Parent ODE)
3. 树增广朴素贝叶斯网络分类器(TAN:Tree Augmented NaiveBayes)
4. 平均独依赖估测器(AODE:Averaged ODE)
5. 加权平均独依赖估测器(WAODE:Weightily Averaged ODE)

• SPODE

  确定父属性最直接的做法是假设所有属性都依赖于同一个属性，称为“超父”（super-parent），然后通过交叉验证等模型选择方法来确定超父属性，由此形成了SPODE（Super-Parent ODE）方法。

• AODE

  将每个属性都作为超父来构建SPODE，然后将具有足够训练数据支撑的SPODE集成起来作为最终结果，由此形成了AODE算法（Averaged ODE），AODE是一种基于集成学习机制、更为强大的独依赖分类器。表达式：
  $$\sum _{i=1}^{d}p(c,x_i)\prod {j=1}^{d}p(x_j|c,x_i)，|D_{x_i}|\ge m^{\prime }$$

  $|D_{x_i}|$ 是在第i个属性上取值为$x_i$的样本的集合，m’是阈值常数。
  $p(c,x_i)=\frac{|D_{c,x_i}|+1}{|D|+N_c\ast N_i}$
  $p(x_j|c,x_i)=\frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j}$其中，$N_c$表示分类类别数，$N_i$表示第i个属性可能的取值数，$N_j$表示第j个属性可能的取值数，$|D_{c,x_I}|$表示分类为c，第i个属性取值为$x_i$的样本集合，$|D_{c,x_i,x_j}|$表示分类为c，第i个属性取值为$x_i$，第j个属性取值为$x_j$的样本集合。

• TAN

  TAN（Tree Augmented naive Bayes）是在最大带权生成树（maximum weighted spanning tree）算法的基础上，通过以下步骤将属性间依赖关系约简为如上图©所示的树形结构：

  1. 计算任意两个属性之间的条件互信息:
     $$I(x_i,x_j|y)=\sum _{x_i,x_j;c\in y}P(x_i,x_j|c)log\frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}$$
  2. 以属性为结点，构建完全图，任意两个结点之间边的权重设为$I(x_i,x_j|y)$。
  3. 构建此完全图的最大带权生成树，挑选根变量，将边置为有向。
  4. 加入类别节点y，增加从y到每个属性的有向边。

代码

import numpy as np
import pandas as pd######一、朴素贝叶斯分类器
class NBayes(object):#设置属性def __init__(self):self.Y = 0          #训练集标签self.X = 0          #训练集数据self.PyArr = {}     #先验概率总容器self.PxyArr = {}    #条件概率总容器#连续变量处理，返回均值和标准差def Gaussian(self, xArr):miu = np.mean(xArr)            #变量平均数sigma = np.std(xArr)           #变量标准差return miu, sigma#离散变量直接计算概率def classify(self, x, xArr, countSetX):countX = len(xArr)              #计算变量X的数量countXi = sum(xArr == x)   #计算变量X某个属性的数量Pxy = (countXi+1)/(countX+countSetX)    #加入拉普拉斯修正的概率return Pxy#计算P(y)，加入了拉普拉斯修正def calPy(self,Y):Py = {}countY = len(Y)for i in set(Y.flatten()):countI = sum(Y[:,0] == i)Py[i] = (countI + 1) / (countY + len(set(Y.flatten())))self.PyArr = Pyreturn#计算P(x|y)，加入了拉普拉斯修正def calPxy(self, X, Y):m, n = np.shape(X)Pxy = {}for yi in set(Y.flatten()):countYi = sum(Y[:,0] == yi)Pxy[yi] = {}                        #第一层是标签Y的分类for xIdx in range(n):Pxy[yi][xIdx] = {}              #第二层是不同的变量XsetX = set(X[:,xIdx])tempX = X[np.nonzero(Y[:,0] == yi)[0],xIdx]for xi in setX:countSetX = len(setX)if countSetX <= 10:Pxy[yi][xIdx][xi] = self.classify(xi, tempX, countSetX)     #第三层是变量Xi的分类概率，离散变量else:Pxy[yi][xIdx]['miu'], Pxy[yi][xIdx]['sigma'] = self.Gaussian(tempX)self.PxyArr = Pxyreturn#训练def train(self, X, Y):self.calPy(Y)print('P(y)训练完毕')self.calPxy(X, Y)print('P(x|y)训练完毕')self.X = Xself.Y = Yreturn#连续变量求概率密度def calContinous(self, x, miu, sigma):Pxy = np.exp(-(x-miu)**2/(2*sigma**2))/(np.power(2*np.pi,0.5)*sigma)   #计算概率密度return Pxy#预测def predict(self, testX):preP = {}m, n = testX.shapefor yi, Py in self.PyArr.items():Ptest = Pyprint(yi,Ptest)for xIdx in range(n):xi = testX[0,xIdx]if len(set(self.X[:,xIdx])) <= 10:Ptest *= self.PxyArr[yi][xIdx][xi]else:pxy = self.calContinous(xi, self.PxyArr[yi][xIdx]['miu'], self.PxyArr[yi][xIdx]['sigma'])Ptest *= pxyprint(yi,Ptest)preP[yi] = Ptestreturn preP#防止数值下溢，预测时用logdef predictlog(self, testX):preP = {}m, n = testX.shapefor yi, Py in self.PyArr.items():Ptest = 0for xIdx in range(n):xi = testX[0,xIdx]if len(set(self.X[:,xIdx])) <= 10:Ptest += np.log(self.PxyArr[yi][xIdx][xi])else:pxy = self.calContinous(xi, self.PxyArr[yi][xIdx]['miu'], self.PxyArr[yi][xIdx]['sigma'])Ptest += np.log(pxy)print(yi,Ptest)preP[yi] = Py*Ptestreturn preP#数据集准备
from sklearn.preprocessing import OrdinalEncoder
dataSet = [['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', 0.697, 0.460, '好瓜'],['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', 0.774, 0.376, '好瓜'],['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', 0.634, 0.264, '好瓜'],['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', 0.608, 0.318, '好瓜'],['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', 0.556, 0.215, '好瓜'],['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', 0.403, 0.237, '好瓜'],['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', 0.481, 0.149, '好瓜'],['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', 0.437, 0.211, '好瓜'],['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', 0.666, 0.091, '坏瓜'],['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', 0.243, 0.267, '坏瓜'],['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', 0.245, 0.057, '坏瓜'],['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', 0.343, 0.099, '坏瓜'],['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', 0.639, 0.161, '坏瓜'],['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', 0.657, 0.198, '坏瓜'],['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', 0.360, 0.370, '坏瓜'],['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', 0.593, 0.042, '坏瓜'],['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', 0.719, 0.103, '坏瓜']]
#特征值列表
labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感', '密度', '含糖率']
dataX = np.array(dataSet)[:,:6]
oriencode = OrdinalEncoder(categories='auto')
oriencode.fit(dataX)
X1=oriencode.transform(dataX)           #编码后的数据
X2=np.array(dataSet)[:,6:8].astype(float)
X = np.hstack((X1,X2))
Y = np.array(dataSet)[:,8]
Y[Y=="好瓜"]=1
Y[Y=="坏瓜"]=0
Y=Y.astype(float)
Y = Y.reshape(-1,1)#训练
NB = NBayes()
NB.train(X, Y)
Pdict = NB.predict(X[0,:].reshape(1,-1))
logPdict = NB.predictlog(X[0,:].reshape(1,-1))######二、半朴素贝叶斯分类器(Averaged One-Dependent Estimator)
class HalfNBayes(object):#设置属性def __init__(self):self.Y = 0          #训练集标签self.X = 0          #训练集数据self.PyArr = {}     #先验概率总容器self.PxyArr = {}    #条件概率总容器#连续变量处理，返回均值和标准差def Gaussian(self, xArr):miu = np.mean(xArr)            #变量平均数sigma = np.std(xArr)           #变量标准差return miu, sigma#离散变量直接计算概率def classify(self, x, xArr, countSetX):countX = len(xArr)              #计算变量X的数量countXi = sum(xArr == x)   #计算变量X某个属性的数量Pxy = (countXi+1)/(countX+countSetX)    #加入拉普拉斯修正的概率return Pxy#计算P(xi,y)，加入了拉普拉斯修正def calPy(self, X, Y):m, n = np.shape(X)Py = {}countY = len(Y)for i in set(Y.flatten()):Py[i] = {}                          #第一层是标签Y的分类for j in range(n):setX = set(X[:,j])countSetX = len(setX)if countSetX <= 10:Py[i][j] = {}               #第二层是不同的变量Xfor xi in setX:countI = sum((Y[:,0] == i) & (X[:,j] == xi))Py[i][j][xi] = (countI + 1) / (countY + countSetX*len(set(Y.flatten())))       #第二层是分类变量xi的不同值self.PyArr = Pyreturn#计算P(x|y,xi)，加入了拉普拉斯修正def calPxy(self, X, Y):m, n = np.shape(X)Pxy = {}for yi in set(Y.flatten()):countYi = sum(Y[:,0] == yi)Pxy[yi] = {}                        #第一层是标签Y的分类for superX in range(n):setSuperX = set(X[:,superX])countSuperX = len(setSuperX)if countSuperX <= 10:Pxy[yi][superX] = {}        #第二层是超父变量X，只有离散变量for superXi in setSuperX:Pxy[yi][superX][superXi] = {}               #第三层是超父变量的属性值superXifor xIdx in range(n):if xIdx == superX:continuePxy[yi][superX][superXi][xIdx] = {}     #第四层是不同的变量XsetX = set(X[:,xIdx])tempX = X[np.nonzero((Y[:,0] == yi)&(X[:,superX] == superXi))[0],xIdx]for xi in setX:countSetX = len(setX)if countSetX <= 10:Pxy[yi][superX][superXi][xIdx][xi] = self.classify(xi, tempX, countSetX)     #第五层是变量Xi的分类概率，离散变量else:Pxy[yi][superX][superXi][xIdx]['miu'], Pxy[yi][superX][superXi][xIdx]['sigma'] = self.Gaussian(tempX)self.PxyArr = Pxyreturn#训练def train(self, X, Y):self.calPy(X, Y)print('P(y)训练完毕')self.calPxy(X, Y)print('P(x|y)训练完毕')self.X = Xself.Y = Yreturn#连续变量求概率密度def calContinous(self, x, miu, sigma):Pxy = np.exp(-(x-miu)**2/(2*sigma**2+1.0e-6))/(np.power(2*np.pi,0.5)*sigma+1.0e-6)   #计算概率密度return Pxy#预测def predict(self, testX):preP = {}m, n = testX.shapefor yi, Py in self.PyArr.items():Ptest = Pyprint(yi,Ptest)for xIdx in range(n):xi = testX[0,xIdx]if len(set(self.X[:,xIdx])) <= 10:Ptest *= self.PxyArr[yi][xIdx][xi]else:pxy = self.calContinous(xi, self.PxyArr[yi][xIdx]['miu'], self.PxyArr[yi][xIdx]['sigma'])Ptest *= pxyprint(yi,Ptest)preP[yi] = Ptestreturn preP#防止数值下溢，预测时用logdef predictlog(self, testX):preP = {}m, n = testX.shapefor yi, superXdict in self.PyArr.items():print('yi是{}================'.format(yi))Ptest = 0for superX, superXidict in superXdict.items():superXi = testX[0,superX]Py = superXidict[superXi]print('超父属性是{}，Py概率是{}'.format(superX, Py))print('----------------')Pxi = 0for xIdx in range(n):if xIdx == superX:continuexi = testX[0,xIdx]print('第{}个变量，值是{}'.format(xIdx, xi))if len(set(self.X[:,xIdx])) <= 10:Pxi += np.log(self.PxyArr[yi][superX][superXi][xIdx][xi])print('概率是：',np.log(self.PxyArr[yi][superX][superXi][xIdx][xi]))else:pxy = self.calContinous(xi, self.PxyArr[yi][superX][superXi][xIdx]['miu'], self.PxyArr[yi][superX][superXi][xIdx]['sigma'])print('概率是：',pxy)Pxi += np.log(pxy)Ptest += Py*PxipreP[yi] = Ptestreturn preP#训练
HNB = HalfNBayes()
HNB.train(X, Y)
logPdict = HNB.predictlog(X[15,:].reshape(1,-1))

参考

机器学习基础

知乎

知乎

代码