摘 要：分類是數(shù)據(jù)挖掘中很重要的一個(gè)組成部分，利用貝葉斯理論的分類算法分類準(zhǔn)確，可解釋性強(qiáng)。本文對(duì)基于貝葉斯理論的分類算法進(jìn)行分析總結(jié)，首先闡明了貝葉斯理論，介紹了基于貝葉斯理論的樸素貝葉斯分類器、TAN模型分類算法、AODE分類算法和AnDE分類算法及其原理，以及各個(gè)算法的特征。

關(guān)鍵詞：貝葉斯理論；分類器

中圖分類號(hào)：TP311.13

數(shù)據(jù)挖掘是研究從數(shù)據(jù)中提取知識(shí)的理論和技術(shù)[1]，分類是數(shù)據(jù)挖掘中最主要的研究?jī)?nèi)容之一。Thomas Bayes于18世紀(jì)提出了貝葉斯理論，這個(gè)理論描述了當(dāng)已知一個(gè)事件發(fā)生，預(yù)測(cè)另一件事也發(fā)生的概率的方法。Domingos.P與Pazzani.M基于貝葉斯理論提出了樸素貝葉斯分類算法[2]。但由于樸素貝葉斯是基于描述一個(gè)事件的屬性都是相互獨(dú)立的假設(shè)，與客觀世界的情況不符，因此精度尚有提高的空間。TAN模型（Tree Augmented Naive Bayes model）[3]即樹增強(qiáng)樸素貝葉斯模，類變量是根，屬性為葉子節(jié)點(diǎn)，并在葉子節(jié)點(diǎn)增加一些必要的邊，以表示各屬性之間的依賴關(guān)系。但是TAN模型需要學(xué)習(xí)網(wǎng)絡(luò)的結(jié)構(gòu)，計(jì)算量大幅增加。對(duì)這兩種算法進(jìn)行改進(jìn)，就得到了AODE的算法。AnDE是在AODE的基礎(chǔ)上，將AODE應(yīng)推廣到更高維的依賴中，此算法不是直接從觀測(cè)到的多元概率分布中尋找適合的模型，而是通過(guò)搜索假設(shè)空間來(lái)發(fā)現(xiàn)最適合的訓(xùn)練集。下面我們將分別對(duì)這幾個(gè)算法進(jìn)行介紹。

1 貝葉斯理論

有訓(xùn)練樣本集T，在T內(nèi)有t個(gè)已分類的樣本，通過(guò)對(duì)樣本集T進(jìn)行分析，來(lái)估計(jì)概率P（y|X），其中樣本X={x1，…，xa}屬于y類，xi是第i個(gè)屬性的值，y∈{c1，…，ck}，用 來(lái)表示每個(gè)屬性的平均值。根據(jù)貝葉斯理論，條件概率公式如下，

2 樸素貝葉斯（Naive Bayes，NB）

從貝葉斯的理論的公式可以看出，概率p（X|y）很難計(jì)算，甚至?xí)衴類的樣本集中沒(méi)有屬性為X的樣本，但是它在其它類中又出現(xiàn)了，這種“零概率”樣本就很難處理。

NB的解決方法是假設(shè)類中的屬性是相互獨(dú)立的，通過(guò)對(duì)估計(jì) 的概率來(lái)估計(jì) 。

以此，NB使用下面的公式進(jìn)行分類

在底層的概率分布中，獨(dú)立假設(shè)是非常強(qiáng)的假設(shè)。以此，NB的偏差非常高。但是，由于在這種模型中低維基礎(chǔ)概率是估計(jì)出來(lái)的，其方差較低。

3 TAN（Tree Augmented Naive Bayes）模型

TAN模型在NB的基礎(chǔ)上在葉子節(jié)點(diǎn)之間增加了一些邊，但每個(gè)葉子節(jié)點(diǎn)最多只有一條邊，其計(jì)算公式如下：

由上式可以看出，TAN不再要求局部獨(dú)立假設(shè)成立，因此TAN模型的分類效果比NB的分類效果要好。

4 AODE

由于NB的獨(dú)立條件太高，因而其分類效果較差，而TAN模型需要進(jìn)行結(jié)構(gòu)學(xué)習(xí)，增加了算法的復(fù)雜度，因此在兩者的基礎(chǔ)上，提出了AODE的算法。

AODE（Averaged One-Dependence Estimators）是從低維的NB自由搜索概率擴(kuò)展到三維概率。主要通平均類中所有的三維概率估計(jì)。

SPODE（A Super-Parent One-Dependence Estimator）是一個(gè)三維概率分布，放寬了條件獨(dú)立的假設(shè)。在這個(gè)算法中，有一個(gè)特定的屬性xa作為其他所有屬性的父節(jié)點(diǎn)，其他屬性相互獨(dú)立。這是比NB相對(duì)弱的條件獨(dú)立假設(shè)。如果NB的推斷是對(duì)的，那么SPODE的推斷一定是對(duì)的，如果NB不一定是對(duì)的，SPODE可能是對(duì)的。

SPODE在條件獨(dú)立假設(shè)的條件下，使用以下的公式

因?yàn)楸龋?）的條件假設(shè)更寬松，這個(gè)模型的偏差會(huì)比NB低。但是，是由高維概率分布得出，因此其方差會(huì)更高。

AODE利用了SPODE的低方差，同時(shí)使用不同的節(jié)點(diǎn)當(dāng)父節(jié)點(diǎn)，并求在不同父節(jié)點(diǎn)下所有P（y，x）的平均，來(lái)獲得更高的方差。AODE使用公式如下：

但是在實(shí)際情況中，只使用在數(shù)據(jù)中出現(xiàn)的實(shí)例，因此，AODE實(shí)際使用

只要屬性值xα在數(shù)據(jù)集中出現(xiàn)，函數(shù)δ（xα）為1，否則為0。也就是說(shuō)平均所有在數(shù)據(jù)中有值的父節(jié)點(diǎn)，如果父節(jié)點(diǎn)的值沒(méi)有出現(xiàn)，就默認(rèn)是NB。

因?yàn)锳ODE使用了的預(yù)定義的估計(jì)算法，每一次推斷的高維概率都是從低維得到的，因此不會(huì)執(zhí)行搜索的操作。

5 AnDE

AnDE在AODE策略的基礎(chǔ)上，將本策略應(yīng)推廣到更高維的依賴中。

在上述公式中，s是屬性集A的n個(gè)子屬性的集合，故上式表示從屬性集中選擇n個(gè)屬性作為父節(jié)點(diǎn)，其他節(jié)點(diǎn)相互獨(dú)立，然后將所有屬性組合相加，然后進(jìn)行平均，最后得到p（y，x）的概率估計(jì)。

但是在實(shí)際應(yīng)用中，會(huì)出現(xiàn)xs不出現(xiàn)的情況，故使用下面這個(gè)公式來(lái)避免某個(gè)屬性值在訓(xùn)練集中不出現(xiàn)。

在上式中，如果屬性組合xs在數(shù)據(jù)集中沒(méi)有出現(xiàn)，就不進(jìn)行計(jì)算，如果所有的屬性組合均沒(méi)有出現(xiàn)，則將計(jì)算A（n-1）DE。

在此，假設(shè)屬性與父節(jié)點(diǎn)和類相互獨(dú)立，因此對(duì)p（x|y，xs）的估計(jì)使用以下公式

若i∈s，則p（x|y，xs）=1。因此A0DE是NB，A1DE是AODE。

當(dāng)n=a時(shí)，xs=x，此時(shí)AnDE為AaDE，用下式表示：

當(dāng)p（y，x）是直接從訓(xùn)練集中估計(jì)出來(lái)的，則產(chǎn)生更低的依賴，估計(jì)應(yīng)該結(jié)合屬性值，因?yàn)閜（x|y，x）和 都等于1，分類只使用對(duì)p（y，x）的直接估計(jì)。因此AaDE的分類性能等于貝葉斯最優(yōu)分類器。

6 結(jié)束語(yǔ)

基于貝葉斯理論的分類算法與其他分類算法比較，具有明顯優(yōu)勢(shì)。樸素貝葉斯假設(shè)類中的屬性相互獨(dú)立，方差較低，偏差較高。TAN模型不再要求局部獨(dú)立，因此其分類效果明顯優(yōu)于樸素貝葉斯。AODE是綜合考慮了樸素貝葉斯和TAN模型的特點(diǎn)，使用不同的節(jié)點(diǎn)當(dāng)父節(jié)點(diǎn)，偏差更低。AnDE是對(duì)AODE的擴(kuò)展，隨著n的增加，偏差降低，方差增大，可以看出AnDE是以方差的增加來(lái)?yè)Q取偏差的減少。

參考文獻(xiàn)：

[1]Dietterich T G.Machine—Learning Research：Four Current Directions[J].AI MAGAZINE，WINTER，1997：97-136.

[2]Witten I H，F(xiàn)rank E.Data Mining：Practical Machine Learning Tools and Techniques with Java Implementaons[J].San Francisco，California：Morgan Kaufmann Publishers，2000.

[3]Friedman N，Goldszmidt M.Building Classifiers Using Bayesian Networks[A].In：Proceedings of the Thirteenth National Conference on Artificial Intelligence[C].Menlo Park，CA：The AAAI Press，1996：1277-1284.

[4]Webb，G.I.，Boughton，J.，Wang，Z.Not so naive Bayes：Aggregating one-dependence estimators[J].Machine Learning，2005（01）：5-24.

[5]Geoffrey I.Webb，Janice R.Boughton，F(xiàn)ei Zheng.Learning by extrapolation from marginal to full-multivariate probability distributions：Decreasingly naive Bayesian classification[J].Machine Leaning，2012（02）：233-272.

[6]Mitchell，T.M.Generalization as search[J].Artificial Intelligence，1982（02）：203-226.

作者簡(jiǎn)介：劉文娟，女，河南孟州人，研究生，研究方向：機(jī)器學(xué)習(xí)、進(jìn)化算法。

作者單位：山西財(cái)經(jīng)大學(xué)信息管理學(xué)院，太原 030031