一種基于屬性加權(quán)的平均單一依賴估計(jì)改進(jìn)算法

秦懷強(qiáng)，趙茂先

(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

一、引 言

貝葉斯網(wǎng)(Bayesian Network，BN)也叫做貝葉斯信度網(wǎng)絡(luò)，它是一個(gè)有向非循環(huán)圖解模型，是概率圖解模型的家族成員，它能展示出隨機(jī)變量間的條件依賴關(guān)系[1-2]。然而從一個(gè)任意的BN離散變量搜索空間中學(xué)習(xí)一個(gè)最優(yōu)的BN網(wǎng)絡(luò)結(jié)構(gòu)是一個(gè)NP難問題，因此必須在一定的限制條件下尋找一個(gè)最優(yōu)的BN網(wǎng)絡(luò)結(jié)構(gòu)[3]。許多學(xué)者遵從于這個(gè)建議，通過限制BN網(wǎng)絡(luò)的復(fù)雜結(jié)構(gòu)提出了許多合理、有效的算法，如樸素貝葉斯(Naive Bayes，NB)算法，以及在NB算法的基礎(chǔ)上進(jìn)行改進(jìn)得來的樹擴(kuò)展的樸素貝葉斯(Tree-Augmented Naive Bayes，TAN)算法、平均單一依賴估計(jì)(AODE)算法、隱樸素貝葉斯(Hidden Naive Bayes，HNB)算法、加權(quán)樸素貝葉斯分類(Weighted Naive Bayesian Classifier， WNBC)算法和消減樸素貝葉斯獨(dú)立性假設(shè)的屬性加權(quán)(Weighting Attributes to Alleviate Naive Bages Independence Assumption，WANBIA)算法等[4-8]。

NB算法因?yàn)樗募僭O(shè)條件(一個(gè)實(shí)例數(shù)據(jù)在給定類別屬性值的條件下，特征屬性值間是相互獨(dú)立的)，使得它對(duì)屬性間相關(guān)性很弱的數(shù)據(jù)集進(jìn)行分類時(shí)，效果好速度快。但當(dāng)這個(gè)假設(shè)條件被違背時(shí)，它的分類效果將會(huì)變差。而在現(xiàn)實(shí)情況下，數(shù)據(jù)集中的屬性之間大多是有較強(qiáng)相關(guān)性的。

AODE算法通過統(tǒng)計(jì)的方法，依據(jù)訓(xùn)練集中的數(shù)據(jù)，從測(cè)試實(shí)例的特征屬性值中選出父屬性值，將特征屬性分為父屬性和子屬性。它還規(guī)定一個(gè)測(cè)試實(shí)例在給定類別屬性值和父屬性值的條件下，特征屬性值間是相互獨(dú)立的，這極大地消減了NB算法的假設(shè)條件。并且AODE算法還是一系列可靠分類模型的聚合，上述這些原因使得AODE算法的分類精確度較NB算法有很大的提高。

在AODE算法的基礎(chǔ)上，許多學(xué)者又紛紛做出改進(jìn)。Zheng和Webb提出了一個(gè)改進(jìn)的AODE算法，稱為惰性消除(Lazy Elimation，LE)的AODE算法[9]，該算法可以刪除掉訓(xùn)練集中的無用數(shù)據(jù)，從而提高AODE算法的分類精確率。Jiang 和Zhang提出了加權(quán)平均單一依賴估計(jì)(Weightily Averaged One Dependence Estimators，WAODE)算法[10]。該算法利用互信息計(jì)算父屬性和類別屬性間的關(guān)聯(lián)程度，并將計(jì)算結(jié)果作為權(quán)重對(duì)父屬性加權(quán)。Zhong和Kang也提出了一種WAODE算法，但該算法是利用條件互信息計(jì)算在類別屬性的條件下父屬性和子屬性間的關(guān)聯(lián)程度，并將計(jì)算結(jié)果作為權(quán)重對(duì)父屬性加權(quán)。

一般AODE算法將所有的特征屬性對(duì)分類的貢獻(xiàn)程度看成是一樣的，在處理一些實(shí)際問題時(shí)，這樣會(huì)極大地限制它的分類效果，而上述AODE的改進(jìn)算法通常采取某種方法來衡量特征屬性和類別屬性的相關(guān)程度，并構(gòu)造相應(yīng)的加權(quán)公式對(duì)特征屬性加權(quán)。

相關(guān)系數(shù)Tau-y和Lambda-y可以衡量一個(gè)特征屬性與類別屬性的相關(guān)程度[11]，它們的計(jì)算值表示以某一個(gè)特征屬性預(yù)測(cè)或解釋類別屬性時(shí)可以消減的預(yù)測(cè)誤差值。因此，可以用Tau-y和Lambda-y衡量一個(gè)特征屬性對(duì)分類的貢獻(xiàn)程度，它們針對(duì)一個(gè)特征屬性和類別屬性的計(jì)算值越大，說明該特征屬性對(duì)分類的貢獻(xiàn)程度越大。利用相關(guān)系數(shù)Tau-y和Lambda-y，依據(jù)訓(xùn)練集中的數(shù)據(jù)，計(jì)算所有特征屬性對(duì)分類的貢獻(xiàn)程度，并把相應(yīng)的結(jié)果作為父屬性的權(quán)值，得到了兩個(gè)改進(jìn)的AODE算法：T-AODE和L-AODE算法，然后通過實(shí)驗(yàn)驗(yàn)證了這兩個(gè)算法的分類精確度相較于AODE算法有明顯的提高。

二、NB算法和AODE算法介紹

(一)NB算法

在處理分類問題時(shí)，給定一個(gè)訓(xùn)練數(shù)據(jù)集D={X(1)，X(2)，…，X(t)}包含t個(gè)實(shí)例，每一個(gè)實(shí)例X=(a1，a2，…，an)∈D(它是一個(gè)n維的向量，有n個(gè)特征屬性值)，并且每一個(gè)實(shí)例都被一個(gè)類別屬性值y∈Y所標(biāo)記。在給定X的條件下計(jì)算y的后驗(yàn)概率，依據(jù)貝葉斯理論可以得到式(1)：

(1)

為了能更加簡單地計(jì)算似然函數(shù)p(X|y)，依據(jù)貝葉斯理論的假設(shè)條件，可以得到式(2)：

(2)

然后，依據(jù)上述的理論就可以得到樸素貝葉斯分類器的構(gòu)建公式，其具體的形式如式(3)所示：

(3)

(二)AODE算法

AODE算法是結(jié)構(gòu)擴(kuò)展后的NB算法，它消減了NB算法的假設(shè)條件，其具體的描述如下。

給定一個(gè)測(cè)試實(shí)例X=(a1，a2，…，an)，并且X∈D，因?yàn)樘卣鲗傩灾礱i∈X，所以可以得到式(4)：

p(y，X)=p(y，ai，X)=p(y，ai)p(X|y，ai)

(4)

結(jié)合式(1)和(4)可以得到式(5)：

∝p(y，ai)p(X|y，ai)

(5)

基于式(5)和條件獨(dú)立性假設(shè)，可以得到式(6)，并且在式(6)中ai，aj∈X。

(6)

結(jié)合上面的理論可以得到AODE算法構(gòu)建分類器的公式如式(7)所示：

(7)

在式(7)中，F(xiàn)(ai)表示在訓(xùn)練集中特征屬性值為ai的訓(xùn)練實(shí)例的數(shù)目，g為限制條件(取值一般為30)[5]。

三、相關(guān)系數(shù)加權(quán)的AODE算法

在這里我們用相關(guān)系數(shù)Tau-y和Lambda-y計(jì)算訓(xùn)練集中的特征屬性對(duì)分類的貢獻(xiàn)程度，并把計(jì)算結(jié)果作為父屬性的權(quán)重，與原有的AODE算法相結(jié)合，得到了兩個(gè)改進(jìn)的AODE算法：T-AODE和L-AODE算法。

(一)T-AODE算法

在利用相關(guān)系數(shù)Tau-y對(duì)父屬性進(jìn)行加權(quán)時(shí)，首先，用Tau-y計(jì)算每一個(gè)特征屬性對(duì)分類的貢獻(xiàn)程度，其具體公式如式(8)～(11)所示：

(8)

(9)

式(8)表示的是在不知道第i個(gè)特征屬性的情況下預(yù)測(cè)類別屬性時(shí)的全部誤差。其中，t指的是訓(xùn)練集中訓(xùn)練實(shí)例的數(shù)目，而式(9)中fiy指的是訓(xùn)練集中第i個(gè)特征屬性的某一個(gè)屬性值與類別值y同時(shí)出現(xiàn)的訓(xùn)練實(shí)例的數(shù)目，Ai表示第i個(gè)特征屬性。

(10)

(11)

式(10)表示的是在知道第i個(gè)特征屬性的情況下預(yù)測(cè)類別屬性時(shí)的誤差。

然后結(jié)合式(8)和式(10)就可以得到第i個(gè)特征屬性的權(quán)值wi，其具體公式如式(12)所示：

(12)

式(12)表示的是以第i個(gè)特征屬性預(yù)測(cè)類別屬性時(shí)能消減的誤差數(shù)。結(jié)合式(12)和式(7)可以得到T-AODE算法構(gòu)建的分類器模型，具體形式如式(13)所示：

(13)

(二)L-AODE算法

利用相關(guān)系數(shù)Lambda-y計(jì)算第i個(gè)特征屬性的權(quán)重的公式如式(14)～(16)所示：

(14)

(15)

(16)

式(14)表示的是以第i個(gè)特征屬性預(yù)測(cè)類別屬性時(shí)能消減的誤差數(shù)。結(jié)合式(14)和式(7)可以得到L-AODE算法構(gòu)建的分類器模型，如式(17)所示：

(17)

(三)T-AODE和L-AODE算法步驟

結(jié)合上文內(nèi)容，這里給出T-AODE和L-AODE算法步驟如表1所示。它們的算法步驟基本是相同的，不同之處只是特征屬性權(quán)重wi的計(jì)算公式，其分別為式(12)和式(14)。

表1 T-AODE和L-AODE算法步驟

四、實(shí)驗(yàn)分析

這里將對(duì)T-AODE、L-AODE、AODE和NB算法進(jìn)行數(shù)值分類實(shí)驗(yàn)。實(shí)驗(yàn)使用的數(shù)據(jù)是UCI標(biāo)準(zhǔn)數(shù)據(jù)集，數(shù)據(jù)集的具體描述如表2所示[12]。在實(shí)驗(yàn)前需要對(duì)數(shù)據(jù)做如下的預(yù)處理。

表2 訓(xùn)練集數(shù)據(jù)描述

(一)補(bǔ)充缺失的特征屬性值

使用weka中的無監(jiān)督過濾器Replace Missing Values對(duì)特征屬性的缺失值進(jìn)行補(bǔ)充。Replace Missing Values使用從訓(xùn)練集中獲得的模型或均值補(bǔ)充缺失的特征屬性值。

(二)離散化數(shù)值型特征屬性值

利用weka中的無監(jiān)督過濾器Discretization離散化數(shù)值型的特征屬性值，實(shí)驗(yàn)時(shí)使用的參數(shù)是10-bin。

(三)將無用的特征屬性刪除

如果一個(gè)特征屬性的某一種屬性值的數(shù)目幾乎就和訓(xùn)練集中的訓(xùn)練實(shí)例的數(shù)目相等，這說明該特征屬性對(duì)分類幾乎沒有貢獻(xiàn)，可以使用weka中的無監(jiān)督過濾器Remove將這種特征屬性刪除。

(四)去除類別值缺失的訓(xùn)練實(shí)例

使用weka中Instances類下的方法delete With Missing Class，將訓(xùn)練集中類別值缺失的訓(xùn)練實(shí)例刪除。

為了使實(shí)驗(yàn)?zāi)軌蜻M(jìn)行，需要計(jì)算概率p(y)、P(ai|y)、p(y，ai)和p(aj|y，ai)，并且為了避免零概率估計(jì)對(duì)實(shí)驗(yàn)的影響，采用拉普拉斯估計(jì)對(duì)上述的概率公式進(jìn)行估計(jì)，其具體的公式如下：

(18)

(19)

(20)

(21)

在上述公式中，F(xiàn)(y)指的是訓(xùn)練集中類別值為y的訓(xùn)練實(shí)例的數(shù)目，F(xiàn)(aj，y)指的是訓(xùn)練集中類別值y和特征屬性值aj同時(shí)出現(xiàn)的訓(xùn)練實(shí)例的數(shù)目，F(xiàn)(aj，y，ai)指的是訓(xùn)練集中類別值為y和特征屬性值ai、aj同時(shí)出現(xiàn)的訓(xùn)練實(shí)例的數(shù)目，c(Y)指的是類別值的種類數(shù)，c(Aj)指的是特征屬性Aj的屬性值的種類數(shù)。

實(shí)驗(yàn)采用的是十折交叉驗(yàn)證的方式，所謂的十折交叉驗(yàn)證指的是將一個(gè)原始訓(xùn)練數(shù)據(jù)集平分成10份，進(jìn)行10次實(shí)驗(yàn)，每一次都將這10份數(shù)據(jù)中的一份作測(cè)試集，其它9份作訓(xùn)練集，最終的結(jié)果為這10次實(shí)驗(yàn)結(jié)果的平均值[13]330-333。經(jīng)過上述的準(zhǔn)備，借助Eclipse和weka中的軟件包，最終得到了NB、AODE、T-AODE和L-AODE算法的分類精確度，如表3所示。

表3中的分類精確度的單位為%，由表3可以看出T-AODE和L-AODE算法的平均分類精確度均大于AODE算法和NB算法，而且T-AODE算法是這四個(gè)算法中平均分類精確度最高的。然后，對(duì)比這四個(gè)算法在每一訓(xùn)練集上的表現(xiàn)，可以得到表4。

由表4可以看出T-AODE算法針對(duì)于每一個(gè)數(shù)據(jù)集與NB、AODE和L-AODE算法比較分類效果。T-AODE分類效果好的數(shù)據(jù)集數(shù)目多于NB、AODE和L-AODE算法，而L-AODE算法分類效果好的數(shù)據(jù)集數(shù)目也多余NB和AODE算法。綜上所述，可以看出T-AODE和L-AODE算法的整體分類效果是優(yōu)于原始的AODE算法。

表3 各算法分類精確度對(duì)比

表4 各算法在每個(gè)數(shù)據(jù)集上的分類精度對(duì)比

五、結(jié)束語

本文提出了兩個(gè)改進(jìn)的AODE算法:T-AODE和L-AODE算法，它們的核心思想是分別利用相關(guān)系數(shù)Tau-y和Lambda-y計(jì)算各個(gè)特征屬性對(duì)分類的貢獻(xiàn)程度，并將得到的結(jié)果作為父屬性的權(quán)值來改進(jìn)AODE算法。然后通過實(shí)驗(yàn)對(duì)比了T-AODE、L-AODE、NB和AODE算法的平均分類精確度和在每個(gè)數(shù)據(jù)集上的分類精確度，結(jié)果顯示T-AODE和L-AODE算法的整體分類效果要優(yōu)于原始的AODE算法，而且T-AODE算法相較于L-AODE算法效果要更好。

雖然T-AODE和L-AODE算法的整體分類效果都要優(yōu)于AODE算法，但是二者的加權(quán)方式還是過于簡單，而且在某些數(shù)據(jù)集上的分類效果要比AODE算法甚至是NB算法還差，所以在以后的研究中，要探究用更加有效的加權(quán)方式改進(jìn)AODE算法，使得改進(jìn)算法在每個(gè)數(shù)據(jù)集上的分類效果都要優(yōu)于原始AODE算法。為此可以考慮利用某種技術(shù)計(jì)算多個(gè)屬性混合在一起對(duì)于分類的貢獻(xiàn)程度，并將計(jì)算結(jié)果作為特征屬性的權(quán)值。

參考文獻(xiàn)：

[1] Zhong L X，Daeki K.Attribute Weighting for Averaged One-dependence Estimators[J].Applied Intelligence，2017，46(3).

[2] Wu J，Cai Z H，Pan S R，et al.Attribute Weighting：How and When Does It Work for Bayesian Network Classification[C].2014 International Joint Conference on Neural Networks，2014.

[3] Gregory F Cooper. The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks [J].Artificial Intelligence，1990，42(2/3).

[4] Friedman N，Geiger D，Goldszmidt M.Bayesian Network Classifiers[J].Machine Learning，1997，29(2/3).

[5] Geoffrey I W，Janice R B，Wang Z H.Not So Naive Bayes：Aggregating One-dependence Estimators[J].Machine Learning，2005，58(1).

[6] Jiang L X，Zhang H，Cai Z H.A Novel Bayes Model:Hidden Naive Bayes[C].IEEE，Transactions on Knowledge and Data Engineering，2009，21(10).

[7] Hamad A.Weighted Naive Bayesian Classifier[C].IEEE International Conference on Computer Systems and Application，2007.

[8] Nayyar A，Zaidi，Jesus C，et al.Alleviating Naive Bayes Attribute Independence Assumption by Attribute Weighting[J].Journal of Machine Learning Research，2013，14(1).

[9] Zheng F，Webb G I.Efficient Lazy Elimination for Averaged One-dependence Estimators[C].Proceeding of the 23rd International Conference on Machine Learning，2006.

[10] Jiang L X，Zhang H.Weightily Averaged One-dependence Estimators[C].The 9thPacific Rim International Conference on Artificial Intelligence，2006.

[11] 喻凱西.樸素貝葉斯分類算法的改進(jìn)及其應(yīng)用[D].北京：北京林業(yè)大學(xué)，2016.

[12] Merz C，Murphy P，Aha D.UCI Repository of Machine Learning Database[DS/OL].Dept.of ICS，Univ.of California，http://www.ics.uci.edu/mlearn/MLRep-ository.html，1997.

[13] 袁梅宇.數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)WEKA應(yīng)用技術(shù)與實(shí)踐[M].北京：清華大學(xué)出版社，2014.