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

，

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

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

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

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

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

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

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

(1)

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

(2)

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

1.1 AVWHNB算法介紹

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

(3)

(4)

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

(5)

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

(6)

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

1.2 AVWHNB算法步驟

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

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

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

(7)

(8)

(9)

在實驗前需要對訓練集中的數(shù)據(jù)做如下的預處理：

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

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

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

4) 把訓練集中類標記缺失的訓練實例刪除，使用的是weka中Instances類下的方法delete with Missing Class。

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

2 實驗分析

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

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

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

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

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

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

對比上述4個算法的時間復雜度得到表5。

表5 各算法時間復雜度對比Tab.5 Time complexity comparison of different algorithms

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

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

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

4 結(jié)束語

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

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

參考文獻：

[1]秦鋒，任詩流，程澤凱，等.基于屬性加權(quán)的樸素貝葉斯分類算法[J].計算機工程與應用，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)粗糙樸素貝葉斯算法及其應用研究[J].計算機應用研究，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].長沙:湖南大學,2012.

[8]杜婷.基于屬性選擇的樸素貝葉斯分類[D].合肥:中國科學技術(shù)大學，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ù)挖掘與機器學習WEKA應用技術(shù)與實踐[M].北京：清華大學出版社，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.