基于屬性值加權(quán)的隱樸素貝葉斯算法

，

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

貝葉斯網(wǎng)絡(luò)(Bayesian networks, BN)源于概率統(tǒng)計(jì)學(xué)，作為機(jī)器學(xué)習(xí)的重要方法受到了廣泛的關(guān)注[1]。在無限制條件下學(xué)習(xí)最優(yōu)的BN網(wǎng)絡(luò)結(jié)構(gòu)是一個(gè)NP難問題，所以GREGOR[2]建議在一定的限制條件下尋找最優(yōu)的BN網(wǎng)絡(luò)結(jié)構(gòu)，而樸素貝葉斯(Naive Bayes,NB)分類算法是一個(gè)很好的解決思路。樸素貝葉斯分類算法是一種以概率密度分析為基礎(chǔ)，根據(jù)已知事件來預(yù)測(cè)未知事件發(fā)生可能性的分類算法[3]，具有易于實(shí)現(xiàn)、計(jì)算速度快和分類精確率高的特點(diǎn)，但是當(dāng)其特征屬性條件獨(dú)立這一假設(shè)在一些數(shù)據(jù)集上被違背時(shí)，其分類精確率會(huì)降低。因此學(xué)者們紛紛通過放松NB算法的假設(shè)條件，提出了許多更加優(yōu)化的改進(jìn)算法，如樹擴(kuò)展的樸素貝葉斯(tree-augmented Naive Bayes,TAN)算法[4]、平均單一依賴估計(jì)(averaged one-dependence estimators, AODE)算法[5]和隱樸素貝葉斯算法[6]等。

其中HNB算法具有分類效率高，計(jì)算速度快的特點(diǎn)，且因其給訓(xùn)練集中的每一個(gè)特征屬性虛構(gòu)了一個(gè)隱藏的父屬性，這個(gè)隱藏的父屬性是由其他所有特征屬性共同作用產(chǎn)生的，所以HNB算法極大的放松了樸素貝葉斯分類算法的假設(shè)條件，使HNB算法能夠在更多的不同種類的數(shù)據(jù)集上均有較好的分類表現(xiàn)。

但HNB算法提出的構(gòu)建隱藏父屬性的方法太過簡(jiǎn)單，無法詳細(xì)地描述訓(xùn)練集中各屬性間的相互依賴關(guān)系，針對(duì)這個(gè)問題，許多學(xué)者又提出了一些改進(jìn)的HNB算法。李晶輝[7]提出了雙層隱樸素貝葉斯分類(Double-layer Hidden Naive Bayes Classification, DHNBC)算法，該算法在HNB算法的基礎(chǔ)上為每個(gè)特征屬性多引入一個(gè)隱藏父屬性，表示其他屬性與該特征屬性相關(guān)程度的加權(quán)和，其中權(quán)值的大小為屬性間的條件互信息值。杜婷[8]提出加權(quán)隱樸素貝葉斯分類(weighted hidden Naive Bayes classification, WHNBC)算法，該算法利用KL距離和分裂信息的屬性權(quán)值計(jì)算公式來構(gòu)造相應(yīng)的加權(quán)公式，設(shè)計(jì)了一個(gè)改進(jìn)的HNB算法。

上述關(guān)于HNB的改進(jìn)算法均是從特征屬性出發(fā)，而實(shí)際上特征屬性的不同取值對(duì)分類的貢獻(xiàn)程度也是不同的[9]。在分類階段，HNB算法沒有考慮測(cè)試實(shí)例的特征屬性不同的取值對(duì)分類的貢獻(xiàn)程度，這在一定程度上限制了其表現(xiàn)。針對(duì)這個(gè)問題，本研究提出利用訓(xùn)練集中的相應(yīng)特征屬性值的統(tǒng)計(jì)信息來構(gòu)建加權(quán)函數(shù)，在分類階段計(jì)算每個(gè)測(cè)試實(shí)例的特征屬性在取不同屬性值時(shí)對(duì)分類的貢獻(xiàn)程度，并把計(jì)算結(jié)果作為權(quán)重，對(duì)HNB算法中用到的條件概率計(jì)算公式加權(quán)，得到基于屬性值加權(quán)的隱樸素貝葉斯(attribute value weighting for Hidden Naive Bayes，AVWHNB)算法，然后通過實(shí)驗(yàn)驗(yàn)證AVWHNB算法較原始的HNB算法在分類精確率方面有很大的提高。

1 基于屬性值加權(quán)的隱樸素貝葉斯算法

構(gòu)建樸素貝葉斯分類器是一個(gè)利用給定類標(biāo)記的訓(xùn)練集構(gòu)建分類器的過程，其中訓(xùn)練集定義為D={X(1),X(2),…,X(t)}，包含t個(gè)訓(xùn)練實(shí)例。假設(shè)Ai(i=1,2,…,n)是訓(xùn)練集中的n個(gè)特征屬性，并且假定訓(xùn)練集中有m個(gè)類標(biāo)記，記為C={c1,c2,…,cm}，給定一個(gè)具體的測(cè)試實(shí)例X=(a1,a2,…,an)，這里ai就是特征屬性Ai的取值，則可以依據(jù)公式(1)來判斷測(cè)試實(shí)例X的類標(biāo)記。

(1)

HNB算法是結(jié)構(gòu)擴(kuò)展后的NB改進(jìn)算法，針對(duì)訓(xùn)練集中的每一個(gè)特征屬性Ai，給其構(gòu)建一個(gè)隱藏的父屬性Ahpi，并且Ahpi是由除了特征屬性Ai之外的其他所有的特征屬性共同作用產(chǎn)生的，ahpi為Ahpi的取值。由此得到HNB算法的分類公式

(2)

本節(jié)中將要介紹的AVWHNB算法即是在HNB算法的基礎(chǔ)上得到的。

1.1 AVWHNB算法介紹

由公式(2)可以看出，在分類階段，HNB算法把每個(gè)測(cè)試實(shí)例的特征屬性的各個(gè)不同取值對(duì)分類的貢獻(xiàn)看成是一樣的，這在一定程度上限制了HNB算法的分類精確度。針對(duì)這一問題，構(gòu)建加權(quán)函數(shù)wijk對(duì)公式(2)中的條件概率計(jì)算公式進(jìn)行加權(quán)，得到AVWHNB算法。其中wijk的計(jì)算公式如式(3)所示。

(3)

(4)

式(4)中的Wij可由式(5)求得。

(5)

式(5)中的Ip(Ai;AjC)可由式(6)求得。

(6)

公式(6)表示的是訓(xùn)練集中兩個(gè)特征屬性的條件互信息值。

1.2 AVWHNB算法步驟

結(jié)合1.1節(jié)中的內(nèi)容，本節(jié)給出AVWHNB算法對(duì)一個(gè)測(cè)試實(shí)例X=(a1,a2,…,an)的具體分類步驟，如表1所示。

表1 AVWHNB算法步驟Tab.1 Steps of AVWHNB algorithm

在實(shí)驗(yàn)時(shí)需要計(jì)算P(ck)、P(ajck)和P(aiaj,ck)的值。為了避免零概率估計(jì)對(duì)實(shí)驗(yàn)的影響，采用拉普拉斯平滑對(duì)上述的概率公式進(jìn)行估計(jì)，其具體的公式[10]為：

(7)

(8)

(9)

在實(shí)驗(yàn)前需要對(duì)訓(xùn)練集中的數(shù)據(jù)做如下的預(yù)處理：

1) 把訓(xùn)練集中各訓(xùn)練實(shí)例的缺失特征屬性值補(bǔ)齊，使用的是weka中的無監(jiān)督過濾器Replace Missing Values；

2) 把訓(xùn)練集中各訓(xùn)練實(shí)例的數(shù)值型特征屬性值離散化，使用的是weka中的無監(jiān)督過濾器Discretization；

3) 把訓(xùn)練集中無用的特征屬性刪除，使用的是weka中的無監(jiān)督過濾器Remove；

4) 把訓(xùn)練集中類標(biāo)記缺失的訓(xùn)練實(shí)例刪除，使用的是weka中Instances類下的方法delete with Missing Class。

表1中的第一步為分類器構(gòu)建過程的訓(xùn)練階段，第二步和第三步為分類構(gòu)建過程的分類階段。第三步中主要是利用公式(4)來判斷測(cè)試實(shí)例X屬于哪個(gè)類標(biāo)記，公式(4)得到的結(jié)果可以解釋為：在設(shè)計(jì)的公式中，測(cè)試實(shí)例屬于這個(gè)類標(biāo)記的概率最大。

2 實(shí)驗(yàn)分析

本節(jié)對(duì)NB算法、AODE算法、HNB算法和AVWHNB算法進(jìn)行分類實(shí)驗(yàn)，實(shí)驗(yàn)采用的數(shù)據(jù)是UCI標(biāo)準(zhǔn)數(shù)據(jù)集，數(shù)據(jù)集的具體描述如表2所示[11]。編程使用Java語言和Weka軟件中的core.jar算法包，使用的實(shí)驗(yàn)平臺(tái)為Eclipse，運(yùn)行程序時(shí)的電腦配置為：處理器為AMD Phenom(tm)II P920,內(nèi)存大小為2 GB。

表2 訓(xùn)練集數(shù)據(jù)描述Tab.2 Training set data description

實(shí)驗(yàn)采用的是十折交叉驗(yàn)證的方法。十折交叉驗(yàn)證指的是將一個(gè)原始訓(xùn)練數(shù)據(jù)集平分成10份，進(jìn)行10次實(shí)驗(yàn)，每一次都是將這10份數(shù)據(jù)中的1份作測(cè)試集、9份做訓(xùn)練集，10次實(shí)驗(yàn)結(jié)果的平均值為最終的結(jié)果[12]。在上面的準(zhǔn)備工作后，通過數(shù)值實(shí)驗(yàn)得到了NB、AODE、HNB和AVWHNB算法的分類精確率，如表3所示。

表3 各算法分類精確率對(duì)比Tab.3 Classification accuracy comparison of different algorithms %

對(duì)比這4個(gè)算法在每一個(gè)訓(xùn)練集上的表現(xiàn)得到表4。

表4 各算法在每個(gè)數(shù)據(jù)集上的分類精確率對(duì)比Tab.4 Classification accuracy comparison of different algorithms at each dataset

對(duì)比上述4個(gè)算法的時(shí)間復(fù)雜度得到表5。

表5 各算法時(shí)間復(fù)雜度對(duì)比Tab.5 Time complexity comparison of different algorithms

在表5中，m是類標(biāo)記的種類數(shù)，n是特征屬性的數(shù)目，v是一個(gè)特征屬性的各個(gè)屬性值的平均數(shù)目，t是訓(xùn)練集中訓(xùn)練實(shí)例的數(shù)目[13]。

由表3可知AVWHNB算法的平均分類精確率大于NB算法、AODE算法和HNB算法。由表4看出AVWHNB算法分類效果好的數(shù)據(jù)集數(shù)目多于NB、AODE和HNB算法。由表5可以看出AVWHNB算法的訓(xùn)練時(shí)間、分類時(shí)間和HNB算法相同，即AVWHNB算法的時(shí)間復(fù)雜度和HNB算法相同。綜合上面的分析可知，AVWHNB算法在提高分類精確率的同時(shí)并未增加算法的時(shí)間復(fù)雜度，這充分說明了AVWHNB算法的分類效果比HNB算法好。

從表3和表4的數(shù)據(jù)中可以看出AVWHNB算法也存在著一些不足。首先，當(dāng)數(shù)據(jù)集中各特征屬性間的關(guān)聯(lián)程度較弱[14]時(shí)，其在某些數(shù)據(jù)集上的表現(xiàn)不如NB算法。其次，在某些數(shù)據(jù)集上的表現(xiàn)不如原始HNB算法說明AVWHNB算法的穩(wěn)定性有待提高。針對(duì)上述問題，在分類中常用的多分類器思想是一個(gè)很好的解決辦法，而針對(duì)于多個(gè)分類器的輸出，則可以用投票機(jī)制來進(jìn)行綜合以給出最終的分類結(jié)果[15-16]。

4 結(jié)束語

本研究提出的AVWHNB算法為一種改進(jìn)的HNB算法，其核心思想是利用構(gòu)建的加權(quán)函數(shù)計(jì)算各個(gè)特征屬性值對(duì)分類的貢獻(xiàn)程度，并將得到的結(jié)果對(duì)HNB算法中用到的條件概率計(jì)算公式加權(quán)來改進(jìn)HNB算法，然后通過實(shí)驗(yàn)對(duì)比了AVWHNB、HNB、NB和AODE算法的平均分類精確率、在每個(gè)數(shù)據(jù)集上的分類精確率和時(shí)間復(fù)雜度，結(jié)果顯示AVWHNB算法的整體分類效果要優(yōu)于原始的HNB算法。

雖然AVWHNB算法的整體分類效果要優(yōu)于HNB算法，但在對(duì)比每個(gè)數(shù)據(jù)集上的分類效果時(shí)，AVWHNB算法分類效果好的數(shù)據(jù)集的數(shù)目只是略高于HNB算法，這說明改進(jìn)的算法還是不夠穩(wěn)定，所以在以后的研究中，可以將特征屬性值加權(quán)和特征屬性加權(quán)相結(jié)合，并借鑒AODE算法聚合分類器的思想。具體的思路是：先找到一個(gè)合適的方法來判斷數(shù)據(jù)集中各個(gè)特征屬性的關(guān)聯(lián)程度。然后設(shè)置一個(gè)閾值，當(dāng)關(guān)聯(lián)程度低于這個(gè)閾值時(shí)可以使用NB算法來對(duì)數(shù)據(jù)集進(jìn)行分類，而當(dāng)關(guān)聯(lián)程度高于這個(gè)閾值時(shí)可以采用AVWHNB算法對(duì)數(shù)據(jù)集進(jìn)行分類。對(duì)于這兩類分類器，在每一類上均可以設(shè)置多個(gè)分類器，在具體分類時(shí)可采用某種方法將原始數(shù)據(jù)集分成若干份，每一份數(shù)據(jù)都由一個(gè)分類器來處理。最后用投票機(jī)制綜合多個(gè)分類器的分類結(jié)果來確定測(cè)試實(shí)例的類標(biāo)記。經(jīng)過上述處理，理論上可以得到分類效果好且穩(wěn)定的HNB改進(jìn)算法。

參考文獻(xiàn)：

[1]秦鋒，任詩流，程澤凱，等.基于屬性加權(quán)的樸素貝葉斯分類算法[J].計(jì)算機(jī)工程與應(yīng)用，2008,44(6):107-109.

QIN Feng,REN Shiliu,CHENG Zekai,et al.Attribute weighted Naive Bayes classification[J].Computer Engineering and Applications,2008,44(6):107-109.

[2]GREGORY F C.The computational complexity of probabilistic inference using Bayesian belief networks[J].Artificial Intelligence,1990,42(2/3):393-405.

[3]王輝，黃自威，劉淑芬.新型加權(quán)粗糙樸素貝葉斯算法及其應(yīng)用研究[J].計(jì)算機(jī)應(yīng)用研究，2015,32(12):3668-3672.

WANG Hui,HUANG Ziwei,LIU Shufen.Novel weighted rough naive Bayes algorithm and its application[J].Application Research of Computers,2015,32(12):3668-3672.

[4]FRIEDMAN N,GEIGER D,GOLDSZMIDT M.Bayesian network classifiers[J].Machine Learning,1997,29:131-163.

[5]GEOFFREY I W,JANICE R B,WANG Z H.Not so Naive Bayes:Aggregating one-dependence estimators[J].Machine Learning,2005,58(1):5-24.

[6]JIANG L X,ZHANG H,CAI Z H.A novel Bayes Model:Hidden Naive Bayes[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1361-1371.

[7]李晶輝.基于互信息的多層隱樸素貝葉斯算法研究[D].長(zhǎng)沙:湖南大學(xué),2012.

[8]杜婷.基于屬性選擇的樸素貝葉斯分類[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué)，2016.

[9]CHANG H L.A gradient approach for value weighted classification learning in Naive Bayes[J].Knowledge -Based Systems,2015,85:71-79.

[10]ZHONG L X,XIANG R Y,DAE K K.Experimental analysis of Naive Bayes classifier based on an attribute weighting framework with smooth kernel density estimations[J].Applied Intelligence,2016,44(3):611-620.

[11]MERZ C,MURPHY P,AHA D.UCI repository of machine learning database[DB/OL].[2017-09-08],http://www.ics.uci.edu/mlearn/MLRpository.html.

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

[13]ZHONG L X,DAE K K.Attribute weighting for averaged one-dependence estimators[J].Applied Intelligence,2017,46(3):616-629.

[14]JUN Y.Correlation coefficient between dynamic single valued neutrosophic multisets and its multiple attribute decision-making method[J].Information,2017,8(2):41.

[15]CAGATAY C,MEHMET N.A sentiment classification model based on multiple classifiers[J].Applied Soft Computing,2017,50:135-141.

[16]ANDRONIKI T,GEORGE E T,ANASTASIOS R,et al.A methodology to carry out voting classification tasks using a particle swarm optimization-based neuro-fuzzy competitive learning network[J].Evolving Systems,2017,8(1):49-69.