樸素貝葉斯和半樸素貝葉斯（AODE）分類器Python實(shí)現(xiàn)

　　一、概述

　　機(jī)器學(xué)習(xí)最后一次實(shí)驗(yàn)，要求實(shí)現(xiàn)樸素貝葉斯和AODE的半樸素貝葉斯分類器。由于老師說可以調(diào)用現(xiàn)成的相關(guān)機(jī)器學(xué)習(xí)的庫(kù)，所以我一開始在做樸素貝葉斯分類器的時(shí)候，直接調(diào)用了sklearn庫(kù)，很方便，可是問題來了，在做AODE半樸素貝葉斯分類器的時(shí)候，并沒有找到集成好的方法。所以就想著自己把半樸素貝葉斯分類器實(shí)現(xiàn)了，樸素貝葉斯分類就直接調(diào)用庫(kù)算了?？墒亲屓祟^大的是，上來就直接實(shí)現(xiàn)AODE分類器還是不太科學(xué)，還得從基本的貝葉斯原理到樸素貝葉斯開始，所以我又從頭看，主要看的這篇博客 西瓜書讀書筆記——第七章：貝葉斯分類器，寫的非常好，看完之后就基本弄懂了。我感覺實(shí)現(xiàn)起來，樸素貝葉斯和半樸素貝葉斯有很多相似之處，索性就先把樸素貝葉斯實(shí)現(xiàn)了，正好也能加深一下理解，然后再實(shí)現(xiàn)AODE半樸素貝葉斯分類器就會(huì)容易些了。

　　二、貝葉斯分類器

　　2.1 樸素貝葉斯分類器

　　(1)貝葉斯分類基本思想簡(jiǎn)單解釋

　　首先，貝葉斯分類的思想很簡(jiǎn)單，假設(shè)數(shù)據(jù)一共有nnn種類別，即Label={L1,L2,??,Ln}Label=\{L_1,L_2,\cdots,L_n\}Label={L1,L2,?,Ln}，給定一個(gè)樣本數(shù)據(jù)x={x1,x2,??,xm}x=\{x_1,x_2,\cdots,x_m\}x={x1,x2,?,xm}，注意，這里的xxx是一個(gè)樣本數(shù)據(jù)，x1,x2,??,xmx_1,x_2,\cdots,x_mx1,x2,?,xm表示這個(gè)數(shù)據(jù)有mmm維特征，當(dāng)知道了樣本數(shù)據(jù)xxx，根據(jù)xxx計(jì)算出來這個(gè)數(shù)據(jù)屬于每一種類別的概率P={PL1,PL2,??,PLn}P=\{P_{L_1},P_{L_2},\cdots,P_{L_n}\}P={PL1,PL2,?,PLn}，最后將這個(gè)數(shù)據(jù)xxx劃分為最大概率對(duì)應(yīng)的類別。比如，如果argmax{PL1,PL2,??,PLn}=L2argmax\{P_{L_1},P_{L_2},\cdots,P_{L_n}\}=L_2argmax{PL1,PL2,?,PLn}=L2，那么xxx就被劃分為L(zhǎng)2L_2L2。

　　(2)貝葉斯分類基本原理

　　其次，貝葉斯分類的實(shí)現(xiàn)也很簡(jiǎn)單?，F(xiàn)在已經(jīng)知道了基本原理，設(shè)xxx所屬的類別為ccc，xix_ixi代表樣本xxx的第iii個(gè)屬性值(第iii個(gè)維度的值)，那么上面所說的要求樣本xxx屬于每種類別的概率就記為P(c∣x)P(c|x)P(c∣x)，根據(jù)貝葉斯模型和極大似然估計(jì)原理，那么就有：

　　P(c∣x)=P(x∣c)P(c)P(x)=P(c)P(x)∏i=1mP(xi∣c)

　　P(c|x)=\frac{P(x|c)P(c)}{P(x)}=\frac{P(c)}{P(x)}\prod_{i=1}^mP(x_i|c)

　　P(c∣x)=P(x)P(x∣c)P(c)=P(x)P(c)i=1∏mP(xi∣c)

　　其中P(x)=∏i=1mP(xi)P(x)=\prod_{i=1}^mP(x_i)P(x)=∏i=1mP(xi)，對(duì)于數(shù)據(jù)xxx來說，計(jì)算對(duì)應(yīng)的每一種類別的概率時(shí)，P(x)P(x)P(x)是相同的，所以為了計(jì)算方便，可以省略掉，記為：

　　P(c∣x)∝P(c)∏i=1mP(xi∣c)

　　P(c|x)\propto P(c)\prod_{i=1}^mP(x_i|c)

　　P(c∣x)∝P(c)i=1∏mP(xi∣c)(注：在實(shí)現(xiàn)時(shí)，為了防止概率連乘導(dǎo)致趨近于0，將∏i=1mP(xi∣c)\prod_{i=1}^mP(x_i|c)∏i=1mP(xi∣c)取對(duì)數(shù)變成連加)所以最終計(jì)算xxx所對(duì)應(yīng)的類別就有：

　　L(x)=argmaxP(c)∏i=1mP(xi∣c)

　　L(x)=argmax P(c)\prod_{i=1}^mP(x_i|c)

　　L(x)=argmaxP(c)i=1∏mP(xi∣c)這里c是所要求的值。根據(jù)這個(gè)公式就知道，要求xxx所屬的類別，只要求出P(c)P(c)P(c)和P(xi∣c)P(x_i|c)P(xi∣c)就行了。

　　設(shè)整個(gè)樣本數(shù)據(jù)集為DDD，當(dāng)∣D∣|D|∣D∣足夠大時(shí)(即樣本數(shù)量足夠多)，就可以利用頻率估計(jì)概率(大數(shù)定律)來計(jì)算出先驗(yàn)概率P(c)P(c)P(c)，

　　P(c)=∣Dc∣∣D∣

　　P(c)=\frac{|D_c|}{|D|}

　　P(c)=∣D∣∣Dc∣∣D∣|D|∣D∣代表所有數(shù)據(jù)的數(shù)量，∣Dc∣|D_c|∣Dc∣表示類別為ccc的樣本的數(shù)量?，F(xiàn)在P(c)P(c)P(c)很容易的求出來了，然后就是P(xi∣c)P(x_i|c)P(xi∣c)了。

　　然而，對(duì)于樣本屬性xix_ixi來說，其可分為連續(xù)性樣本屬性和離散型樣本屬性。先理解一下什么是“離散型樣本屬性”，那么“連續(xù)型”就比較容易理解了。

　　“離散型樣本屬性”：比如，對(duì)于西瓜AAA來說，AAA就是整個(gè)西瓜家族里面的一個(gè)樣本，那么AAA的屬性就會(huì)有{外皮顏色，敲擊聲音，觸摸手感，??}\{外皮顏色，敲擊聲音，觸摸手感，\cdots\}{外皮顏色，敲擊聲音，觸摸手感，?}，而對(duì)于“外皮顏色”這個(gè)屬性來說，它的取值可能有{黃色，綠色，青綠色，??}\{黃色，綠色，青綠色，\cdots\}{黃色，綠色，青綠色，?}，這個(gè)屬性的取值是離散的，有限的，那么這個(gè)屬性就是“離散型”屬性了，另外兩個(gè)屬性也是一樣。對(duì)于離散型樣本屬性的條件概率計(jì)算公式也是根據(jù)頻率估計(jì)概率得到：

　　P(xi∣c)=∣Dc,xi∣∣Dc∣

　　P(x_i|c)=\frac{|D_{c,x_i}|}{|D_c|}

　　P(xi∣c)=∣Dc∣∣Dc,xi∣∣Dc,xi∣|D_{c,x_i}|∣Dc,xi∣為類別ccc中的所有數(shù)據(jù)的第iii個(gè)屬性值為xix_ixi的樣本的數(shù)量。

　　“連續(xù)型樣本屬性”：還是對(duì)西瓜AAA來說，AAA除了上面提到的那些屬性之外，還有{含糖量，水分}\{含糖量，水分\}{含糖量，水分}這些屬性，這兩個(gè)屬性如果以定量方法(精確地測(cè)量數(shù)值)來表示，比如含糖量為45.678%45.678\%45.678%，這樣就叫做“連續(xù)型”屬性了，但是如果以定性方法來表示，比如將含糖量劃分為{低，中，高}\{低，中，高\(yùn)}{低，中，高}三個(gè)等級(jí)，那么就是“離散型”屬性了。對(duì)于連續(xù)型樣本屬性的條件概率計(jì)算公式使用高斯核密度估計(jì)(應(yīng)該是這么叫吧，希望數(shù)理統(tǒng)計(jì)沒白學(xué))得到：

　　P(xi∣c)=12πσc,iexp(?(xi?μc,i)22σc,i2)

　　P(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}exp\left(-\frac{(x_i-\mu_{c,i})^2}{2\sigma^2_{c,i}}\right)

　　P(xi∣c)=2πσc,i1exp(?2σc,i2(xi?μc,i)2)其中μc,i\mu_{c,i}μc,i和σc,i\sigma_{c,i}σc,i分別為第ccc類樣本在第iii個(gè)屬性取值的均值和標(biāo)準(zhǔn)差。

　　為了避免數(shù)據(jù)集不充分而導(dǎo)致估計(jì)概率為0的情況，需要在實(shí)現(xiàn)過程中引入拉普拉斯修正(具體拉普拉斯修正方法也很簡(jiǎn)單)，但我為了圖方便，直接在先驗(yàn)概率和條件概率(針對(duì)離散型屬性)的分子和分母都 +1 了(實(shí)際測(cè)試中，并沒有發(fā)現(xiàn)有太大的差別)。

　　2.2 AODE半樸素貝葉斯分類器

　　首先，要知道什么是AODE(Averaged One-Dependent Estimator)，就要先了解什么是SPODE(Super-Parent One-Dependent Estimator)。在上面所講的樸素貝葉斯分類都是基于樣本的所有屬性是相互獨(dú)立的，那么如果某些屬性存在依賴關(guān)系怎么辦呢。SPODE就是假設(shè)樣本的每個(gè)屬性都依賴于某一個(gè)屬性，這個(gè)屬性就叫做“超父”。比如，將x1x_1x1屬性設(shè)置為“超父”，那么計(jì)算xxx屬于第ccc類數(shù)據(jù)的概率公式為：

　　P(c∣x)∝P(c)∏i=1mP(xi∣c,x1)

　　P(c|x)\propto P(c)\prod_{i=1}^mP(x_i|c,x_1)

　　P(c∣x)∝P(c)i=1∏mP(xi∣c,x1)而AODE就是在此基礎(chǔ)上，將樣本的屬性依次作為超父來計(jì)算概率,最后求和，同時(shí)，假設(shè)類別ccc也依賴于樣本的屬性，那么計(jì)算xxx屬于類別ccc的概率公式為：

　　P(c∣x)∝∑i=1mP(c,xi)∏j=1mP(xj∣c,xi)

　　P(c|x)\propto \sum_{i=1}^m P(c,x_i)\prod_{j=1}^mP(x_j|c,x_i)

　　P(c∣x)∝i=1∑mP(c,xi)j=1∏mP(xj∣c,xi)同樣的，利用頻率估計(jì)概率的方法可以得到：

　　P(xj∣c,xi)=∣Dc,xi,xj∣∣Dc,xi∣

　　P(x_j|c,x_i)=\frac{|D_{c,x_i,x_j}|}{|D_{c,x_i}|}

　　P(xj∣c,xi)=∣Dc,xi∣∣Dc,xi,xj∣與樸素貝葉斯分類相同，實(shí)現(xiàn)時(shí)也要引入拉普拉斯修正，我還是分子分母都 +1 了。

　　通過觀察xxx屬于類別ccc的概率公式就能看出，這個(gè)方法的時(shí)間復(fù)雜度很高，實(shí)際上，對(duì)于每一個(gè)樣本，計(jì)算出分別屬于哪一個(gè)類的概率一共有三層循環(huán)(不知是否有優(yōu)化方法，但是時(shí)間復(fù)雜度幾乎不可能降低了)。實(shí)現(xiàn)之后，這個(gè)方法并沒有進(jìn)行實(shí)驗(yàn)結(jié)果的驗(yàn)證，因?yàn)闀r(shí)間代價(jià)太大，所以我猜測(cè)，這也是為什么sklearn中有樸素貝葉斯卻沒有AODE半樸素貝葉斯方法的原因了。

　　三、實(shí)驗(yàn)結(jié)果與代碼

　　3.1 實(shí)驗(yàn)結(jié)果

　　對(duì)于樸素貝葉斯分類器的實(shí)現(xiàn)，我只實(shí)現(xiàn)了離散型樣本屬性的分類(連續(xù)性屬性也比較容易，只要把條件概率函數(shù)換成高斯核即可)，使用了MNIST、Yale和COIL20這三個(gè)數(shù)據(jù)對(duì)其進(jìn)行了實(shí)驗(yàn)，使用ACC評(píng)價(jià)標(biāo)準(zhǔn)對(duì)其進(jìn)行評(píng)價(jià)。(注：由于AODE時(shí)間成本過高，不太適合屬性維度較多數(shù)據(jù)，我沒有進(jìn)行數(shù)據(jù)實(shí)驗(yàn)，所以我也不知道對(duì)不對(duì)，不過按照樸素貝葉斯的思路來應(yīng)該也不會(huì)錯(cuò)吧。。。)

　　方法\數(shù)據(jù)　　MNIST　　Yale　　COIL20

　　McQueen_NBC　　0.95　　1　　1

　　GaussianNB　　0.55　　0.8　　1

　　這里我就沒有將數(shù)據(jù)集劃分成測(cè)試集和訓(xùn)練集了，這三組數(shù)據(jù)測(cè)試集是在訓(xùn)練集中每個(gè)類別數(shù)據(jù)分別抽取前0.005%，0.1%，0.01%得到的。McQueen_NBC方法是我自己實(shí)現(xiàn)的樸素貝葉斯分類器(實(shí)際上是多項(xiàng)式貝葉斯)，適用于離散屬性樣本，而GaussianNB是調(diào)用的sklearn庫(kù)的方法，這個(gè)方法是基于連續(xù)型屬性的，由結(jié)果可以看出，在MNIST和Yale這兩個(gè)數(shù)據(jù)上，連續(xù)型準(zhǔn)確率不如離散型(因?yàn)檫@兩個(gè)數(shù)據(jù)是離散型樣本數(shù)據(jù))。

　　3.2 完整代碼

　　datadvi.py

　　from scipy.io import loadmat

　　import numpy as np

　　def divdata():

　　filename = 'C:/Users/ALIENWARE/Documents/作業(yè)/機(jī)器學(xué)習(xí)/datasets/' + input("input name of data file: ")

　　data = loadmat(filename)

　　# print(data['X'])

　　if filename == 'C:/Users/ALIENWARE/Documents/作業(yè)/機(jī)器學(xué)習(xí)/datasets/COIL20.mat':

　　dataX = data['fea']

　　dataY = data['gnd'][0]

　　else:

　　dataX = data['X']

　　dataY = data['Y'].T[0]

　　print(len(dataX[0]))

　　divideornot = input("divide data or not?(Yes/No): ")

　　if divideornot == 'Yes':

　　dataX_train = []

　　dataX_predict = []

　　dataY_train = []

　　dataY_predict = []

　　num_Y = np.unique(dataY).astype(int)

　　for i in range(len(num_Y)):

　　temp = dataY == num_Y[i]

　　temp.astype(float)

　　num_Y[i] = np.sum(temp)

　　flag = 0

　　for j in range(len(dataY)):

　　if temp[j] == 1:

　　if flag < int(round(0.9 * num_Y[i])):

　　dataX_train.append(dataX[j])

　　dataY_train.append(dataY[j])

　　flag += 1

　　else:

　　dataX_predict.append(dataX[j])

　　dataY_predict.append(dataY[j])

　　dataX_train = np.array(dataX_train)

　　dataX_predict = np.array(dataX_predict)

　　dataY_train = np.array(dataY_train)

　　dataY_predict = np.array(dataY_predict)

　　return dataX_train,dataX_predict,dataY_train,dataY_predict

　　else:

　　return dataX,dataX,dataY,dataY

　　def decreaseData(dataX,dataY):

　　dataX_train = []

　　dataY_train = []

　　num_Y = np.unique(dataY).astype(int)

　　print("this data has {} samples".format(len(dataX)))

　　ratio = float(input("input the ratio you want to decrease: "))

　　for i in range(len(num_Y)):

　　temp = dataY == num_Y[i]

　　temp.astype(float)

　　num_Y[i] = np.sum(temp)

　　flag = 0

　　for j in range(len(dataY)):

　　if temp[j] == 1:

　　if flag < round(ratio * num_Y[i]):

　　dataX_train.append(dataX[j])

　　dataY_train.append(dataY[j])

　　flag += 1

　　dataX_train = np.array(dataX_train)

　　dataY_train = np.array(dataY_train)

　　print(dataX_train)

　　return dataX_train,dataY_train

　　Acc.py

　　import numpy as np

　　def acc(L1, L2):

　　sum = np.sum(L1[:]==L2[:])

　　return sum/len(L2)

　　NBC.py

　　import math

　　import numpy as np

　　import datadvi

　　import Acc

　　#加載數(shù)據(jù)

　　def loadData(filename):

　　return datadvi.divdata()

　　#按標(biāo)簽類別生成不同標(biāo)簽樣本組成的集合，返回值為每種類別樣本的索引

　　def divSamples(dataY):

　　label = np.unique(dataY)

　　D = []

　　for i in label:

　　D.append(np.argwhere(dataY==i).T[0])

　　return np.array(D)

　　# 計(jì)算第c類樣本在第i個(gè)屬性上取值的均值和標(biāo)準(zhǔn)差,smaple_cIndx是第c類樣本的索引(用于連續(xù)型屬性，此次未用到)

　　def calcMuSig(sample_cIndx,i,D):

　　mu = np.average(D[sample_cIndx][:,i])

　　sigma = np.std(D[sample_cIndx][:,i])

　　return mu,sigma

　　#計(jì)算類先驗(yàn)概率P(c),

　　def beforeProb(sample_cIndx,D):

　　return float(len(sample_cIndx)+1)/(D.shape[0]+1)

　　#計(jì)算離散型條件概率P(xi|c)

　　def condProb_disp(i,xi,sample_cIndx,D):

　　numerator = np.sum(D[sample_cIndx][:,i]==xi)+1

　　denominator = len(sample_cIndx)+1

　　return float(numerator)/denominator

　　#計(jì)算連續(xù)型條件概率P(xi|c)

　　def condProb_cont(i,xi,sample_cIndx,D):

　　mu,sigma = calcMuSig(sample_cIndx,i,D)

　　prob = 1/(math.sqrt(2*3.14)*sigma)*math.exp(-float((xi-mu)*(xi-mu))/(2*sigma*sigma))

　　return prob 鄭州婦科醫(yī)院哪家好 http://mobile.120zzzy.com/

　　#計(jì)算類后驗(yàn)概率P(c|x)

　　def afterProb(sample_x,c,dataX,dataY):

　　sample_c = divSamples(dataY)

　　p = beforeProb(sample_c[c],dataX)

　　#p = beforeProb(sample_c[c],dataX)

　　p1 = 0

　　for i in range(len(sample_x)):

　　p1 += math.log10(condProb_disp(i,sample_x[i],sample_c[c],dataX))

　　#p1 *= condProb_cont(i,sample_x[i],sample_c[c],dataX) #會(huì)下溢

　　return p*p1

　　#計(jì)算最大概率對(duì)應(yīng)的類

　　def argMaxProb_c(sample_x,dataX,dataY):

　　label = np.unique(dataY)

　　argProb1 = []

　　for c in label:

　　temp_prob = afterProb(sample_x,c-1,dataX,dataY)

　　argProb1.append(temp_prob)

　　argProb = np.array(argProb1)

　　return label[np.argmax(argProb)]

　　#將所有數(shù)據(jù)分類

　　def bayesClassifier(dataPredict,dataX,dataY):

　　pred = []

　　for sample_x in dataPredict:

　　pred.append(argMaxProb_c(sample_x,dataX,dataY))

　　print(len(pred))

　　return pred

　　dataX_train, dataX_predict, dataY_train, dataY_predict = datadvi.divdata()

　　dataX_predict,dataY_predict = datadvi.decreaseData(dataX_predict,dataY_predict)

　　print(len(dataX_predict))

　　sample_c = divSamples(dataY_train)

　　pred = bayesClassifier(dataX_predict,dataX_train,dataY_train)

　　print(pred)

　　print(Acc.acc(pred,dataY_predict))

　　AODE.py

　　import math

　　import numpy as np

　　import datadvi

　　import Acc

　　import RBFNN

　　#加載數(shù)據(jù)

　　def loadData(filename):

　　return datadvi.divdata()

　　#按標(biāo)簽類別生成不同標(biāo)簽樣本組成的集合，返回值為每種類別樣本的索引

　　def divSamples(dataY):

　　label = np.unique(dataY)

　　D = []

　　for i in label:

　　D.append(np.argwhere(dataY==i).T[0])

　　return np.array(D)

　　#計(jì)算先驗(yàn)概率P(c,xi)

　　def beforeProb(sample_cIndx,i,xi,D):

　　numerator = len(np.argwhere(D[sample_cIndx][:,i]==xi).T[0])+1 #索引改變了，但是數(shù)量沒變

　　denominator = D.shape[0]+1 #此處1需被替換為N*Ni

　　return float(numerator)/denominator

　　#計(jì)算條件概率P(xj|c,xi)

　　def condProb(i,xi,j,xj,sample_cIndx,D):

　　D_c = D[sample_cIndx]

　　D_c_xi = D_c[np.argwhere(D_c[:,i]==xi).T[0]]

　　D_c_xi_xj = D_c_xi[np.argwhere(D_c_xi[:,j]==xj).T[0]]

　　numerator = len(D_c_xi_xj)+1

　　denominator = len(D_c_xi)+1

　　return float(numerator)/denominator

　　#計(jì)算后驗(yàn)概率P(c|x)

　　def afterProb(sample_x,c,dataX,dataY):

　　sample_c = divSamples(dataY)

　　prob = 0

　　for i in range(len(sample_x)):

　　p1 = 0

　　p = beforeProb(sample_c[c],i,sample_x[i],dataX)

　　for j in range(len(sample_x)):

　　p1 += math.log10(condProb(i,sample_x[i],j, sample_x[j],sample_c[c], dataX)) #防止下溢

　　prob += p*p1

　　return prob

　　#計(jì)算最大概率對(duì)應(yīng)的類

　　def argMaxProb_c(sample_x,dataX,dataY):

　　label = np.unique(dataY)

　　argProb1 = []

　　for c in label:

　　temp_prob = afterProb(sample_x, c - 1, dataX, dataY)

　　argProb1.append(temp_prob)

　　argProb = np.array(argProb1)

　　return label[np.argmax(argProb)]

　　#將所有數(shù)據(jù)分類

　　def bayesClassifier(dataPredict,dataX,dataY):

　　pred = []

　　for sample_x in dataPredict:

　　label_pred = argMaxProb_c(sample_x,dataX,dataY)

　　pred.append(label_pred)

　　print(len(pred))

　　return pred

　　dataX_train, dataX_predict, dataY_train, dataY_predict = datadvi.divdata()

　　dataX_predict,dataY_predict = datadvi.decreaseData(dataX_predict,dataY_predict)

　　print(len(dataX_predict))

　　pred = bayesClassifier(dataX_predict,dataX_train,dataY_train)

　　print(Acc.acc(pred,dataY_predict))