semi-Naive Bayesian(半朴素贝叶斯)
引言
朴素贝叶斯算法是基于特征是相互独立这个假设开展的(为了降低贝叶斯公式: P ( c ∣ x ) = P ( c ) P ( x ∣ c ) P ( x ) P(c|x) = \frac {P(c)P(x|c)}{P(x)} P(c∣x)=P(x)P(c)P(x∣c)中后验概率 P ( c ∣ x ) P(c|x) P(c∣x)的困难),但在现实中这个假设往往很难成立。对条件独立假设进行适当的放宽,便引申出了“半朴素贝叶斯”。半朴素的意思就是,在朴素和非朴素之间寻找平衡,并不完全遵从条件独立,也不完全符合现实情况。
原理
在朴素贝叶斯中,对一个样本进行预测就是要找最大概率对应的类别,即
a
r
g
m
a
x
c
k
p
(
c
k
)
∏
i
=
1
d
P
(
x
i
∣
c
l
)
argmax_{c_k}p(c_k)\prod_{i=1}^d P(x_i|c_l)
argmaxckp(ck)i=1∏dP(xi∣cl)
半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息,从而既不需进行完全联合概率计算,又不至于彻底忽略了比较强的属性依赖关系。“独依赖估计”(One-Dependent Estimator,简称ODE)是半朴素贝叶斯分类器最常用的一种策略。“独依赖”就是假设每个属性在类别之外最多仅依赖于一个其他属性,即:
p
(
c
∣
x
)
∝
p
(
c
k
)
∏
i
=
1
d
p
(
x
i
∣
c
k
,
p
a
i
)
p(c|x) \propto p(c_k)\prod_{i=1}^d p(x_i|c_k,pa_i)
p(c∣x)∝p(ck)i=1∏dp(xi∣ck,pai)
其中
p
a
i
pa_i
pai为属性
x
i
x_i
xi所依赖的属性,称为
x
i
x_i
xi的父属性。此时,对每个属性
x
i
x_i
xi,若其父属性
p
a
i
pa_i
pai已知,则可采用类似
p
^
(
x
i
∣
c
)
=
∣
D
c
,
x
i
∣
+
1
∣
D
c
∣
+
N
i
\hat p(x_i|c) = \frac{|D_{c,x_i}|+1}{|D_c|+N_i}
p^(xi∣c)=∣Dc∣+Ni∣Dc,xi∣+1
的方法来估计概率值
p
(
x
i
∣
c
,
p
a
i
)
p(x_i|c,pa_i)
p(xi∣c,pai)。于是,问题就转化为如何确定每个属性的父属性,不同的做法产生不同的独依赖分类器。
根据不同确定父属性可以有不同的半朴素贝叶斯分类器:
- 选择贝叶斯分类器(SBC:Selective Bayesian Classifier)
- 超父独依赖估计分类器(SPODE:Super Parent ODE)
- 树增广朴素贝叶斯网络分类器(TAN:Tree Augmented NaiveBayes)
- 平均独依赖估测器(AODE:Averaged ODE)
- 加权平均独依赖估测器(WAODE:Weightily Averaged ODE)
-
SPODE
确定父属性最直接的做法是假设所有属性都依赖于同一个属性,称为“超父”(super-parent),然后通过交叉验证等模型选择方法来确定超父属性,由此形成了SPODE(Super-Parent ODE)方法。
-
AODE
将每个属性都作为超父来构建SPODE,然后将具有足够训练数据支撑的SPODE集成起来作为最终结果,由此形成了AODE算法(Averaged ODE),AODE是一种基于集成学习机制、更为强大的独依赖分类器。表达式:
∑ i = 1 d p ( c , x i ) ∏ j = 1 d p ( x j ∣ c , x i ) , ∣ D x i ∣ ≥ m ′ \sum_{i=1}^d p(c,x_i)\prod{j=1}^dp(x_j|c,x_i),|D_{x_i}|\geq m' i=1∑dp(c,xi)∏j=1dp(xj∣c,xi),∣Dxi∣≥m′∣ D x i ∣ |D_{x_i}| ∣Dxi∣ 是在第i个属性上取值为 x i x_i xi的样本的集合,m’是阈值常数。
p ( c , x i ) = ∣ D c , x i ∣ + 1 ∣ D ∣ + N c ∗ N i p(c,x_i) = \frac{|D_{c,x_i}|+1}{|D|+N_c*N_i} p(c,xi)=∣D∣+Nc∗Ni∣Dc,xi∣+1
p ( x j ∣ c , x i ) = ∣ D c , x i , x j ∣ + 1 ∣ D c , x i ∣ + N j p(x_j|c,x_i) = \frac {|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_j} p(xj∣c,xi)=∣Dc,xi∣+Nj∣Dc,xi,xj∣+1其中, N c N_c Nc表示分类类别数, N i N_i Ni表示第i个属性可能的取值数, N j N_j Nj表示第j个属性可能的取值数, ∣ D c , x I ∣ |D_{c,x_I}| ∣Dc,xI∣表示分类为c,第i个属性取值为 x i x_i xi的样本集合, ∣ D c , x i , x j ∣ |D_{c,x_i,x_j}| ∣Dc,xi,xj∣表示分类为c,第i个属性取值为 x i x_i xi,第j个属性取值为 x j x_j xj的样本集合。 -
TAN
TAN(Tree Augmented naive Bayes)是在最大带权生成树(maximum weighted spanning tree)算法的基础上,通过以下步骤将属性间依赖关系约简为如上图©所示的树形结构:
- 计算任意两个属性之间的条件互信息:
I ( x i , x j ∣ y ) = ∑ x i , x j ; c ∈ y P ( x i , x j ∣ c ) l o g P ( x i , x j ∣ c ) P ( x i ∣ c ) P ( x j ∣ c ) 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)} I(xi,xj∣y)=xi,xj;c∈y∑P(xi,xj∣c)logP(xi∣c)P(xj∣c)P(xi,xj∣c) - 以属性为结点,构建完全图,任意两个结点之间边的权重设为 I ( x i , x j ∣ y ) I(x_i,x_j|y) I(xi,xj∣y)。
- 构建此完全图的最大带权生成树,挑选根变量,将边置为有向。
- 加入类别节点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 = Py
return
#计算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] = {} #第二层是不同的变量X
setX = 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 = Pxy
return
#训练
def train(self, X, Y):
self.calPy(Y)
print('P(y)训练完毕')
self.calPxy(X, Y)
print('P(x|y)训练完毕')
self.X = X
self.Y = Y
return
#连续变量求概率密度
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.shape
for yi, Py in self.PyArr.items():
Ptest = Py
print(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 *= pxy
print(yi,Ptest)
preP[yi] = Ptest
return preP
#防止数值下溢,预测时用log
def predictlog(self, testX):
preP = {}
m, n = testX.shape
for yi, Py in self.PyArr.items():
Ptest = 0
for 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*Ptest
return 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] = {} #第二层是不同的变量X
for 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 = Py
return
#计算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] = {} #第三层是超父变量的属性值superXi
for xIdx in range(n):
if xIdx == superX:
continue
Pxy[yi][superX][superXi][xIdx] = {} #第四层是不同的变量X
setX = 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 = Pxy
return
#训练
def train(self, X, Y):
self.calPy(X, Y)
print('P(y)训练完毕')
self.calPxy(X, Y)
print('P(x|y)训练完毕')
self.X = X
self.Y = Y
return
#连续变量求概率密度
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.shape
for yi, Py in self.PyArr.items():
Ptest = Py
print(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 *= pxy
print(yi,Ptest)
preP[yi] = Ptest
return preP
#防止数值下溢,预测时用log
def predictlog(self, testX):
preP = {}
m, n = testX.shape
for yi, superXdict in self.PyArr.items():
print('yi是{}================'.format(yi))
Ptest = 0
for superX, superXidict in superXdict.items():
superXi = testX[0,superX]
Py = superXidict[superXi]
print('超父属性是{},Py概率是{}'.format(superX, Py))
print('----------------')
Pxi = 0
for xIdx in range(n):
if xIdx == superX:
continue
xi = 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*Pxi
preP[yi] = Ptest
return preP
#训练
HNB = HalfNBayes()
HNB.train(X, Y)
logPdict = HNB.predictlog(X[15,:].reshape(1,-1))
参考
机器学习基础
知乎
知乎
代码