基于貪婪選擇的半樸素貝葉斯分類器研究

王 輝，張 帆，李玉杰

(中央民族大學信息工程學院，北京 100081)

0 引言

數據挖掘的深入發展，賦予數據新的意義，通過數據的不斷積累和挖掘，可以從數據中獲得更多有價值和有意義的信息，因此數據挖掘(Data mining，DM)[1]的重要性尤其突出.樸素貝葉斯分類器(Naive Bayes Classifiers，NBC)[2]作為經典的數據挖掘算法，在科研領域快速發展，但NBC假設屬性間條件獨立，忽略它們之間應用的聯系.

對NBC的改進相對比較發散，不同應用場景下對NBC的改進方式也是千差萬別的，但歸結起來，主要有以下幾種思路：(1)基于貝葉斯網絡結構擴展技術放寬屬性獨立性假設方面的改進，典型代表為樹依賴擴展的著名TAN分類器[3]；(2)基于屬性選擇技術，改進模型分類方法，此種方法可以借助聚類、互信息[4]、屬性貪婪搜索算法等對屬性空間進行子集化分，剔除無關噪聲屬性，對屬性進行分組保留，這類分類器稱為選擇性貝葉斯分類器[5](Selective Bayesian Classifier，SBC)；(3)基于概率調整技術改進NBC的算法，如采用了充分加權算子作為概率乘積的權重來擴展NBC[6]；(4)王雙成等[7]基于TAN分類器進行無向網絡依賴擴展，把屬性之間的樹結構擴展成可分解馬爾科夫網絡，使經過依賴擴展得到的分類器能夠更有效地利用屬性間的依賴信息，提高分類能力，并能夠通過調節閾值大小避免過度擬合.

各種對NBC獨立性假設方面的改進，在不同數據集上不同程度地提高了數據分類準確性，說明從獨立性假設方面改進NBC是有效可行的.

本文將貪婪選擇算法思想運用于半樸素貝葉斯分類器的屬性分組，通過對屬性的循環掃描獲取到最優屬性分組，直至所有屬性劃分結束，獲得最終分組結果，最后利用所獲取的分組進行分類預測，較好地改進了樸素貝葉斯分類器的不足.

1 半樸素貝葉斯分類器

半樸素貝葉斯分類器[8](Semi-Naive Bayesian Classifier，SNBC)是通過尋找并利用NBC的屬性依賴關系進行依賴擴展的分類器.用πi作為變量集合X的一個劃分(組的劃分方法將在下文中給出介紹)，假設待分類數據各組之間條件相互獨立，組內數據各屬性相互依賴，通過合理選取依賴性強的幾個屬性作為屬性組來達到改進分類器的目的，依賴性強弱模型可以表示為

(1)

推知SNBC模型為

(2)

通過(2)式可知分母的值對于選定的數據集是一個定值，使用中以常數對待，重點解決求解分子問題，取其最大值表示屬性組π屬于類C的可能性.SNBC表示為

(3)

2 模型建立與評價體系

本文將貪婪選擇算法思想融入到樸素貝葉斯分類器的改進過程中，結合分類器判別標準進行相應的實驗.

2.1 貪婪選擇算法

貪婪選擇算法(Greedy Selection Algorithm，GSA)又稱為貪心算法[9]，在尋找最優解或最佳路徑問題中有著廣泛的應用.實際應用中將待求解問題分拆成多個步驟進行，分步求得局部最優解，以最優解為所需結果.在求解過程中，通過一次次的局部最優解的求解，獲得一系列局部最優選擇，從而找出所求問題的全局最優解.

2.2 數據來源及模型建立

(1) 數據來源.實驗所用數據來自國際標準數據集倉庫UCI，選取21個數據集用于實驗，進行貝葉斯分類的學習.

(2) 模型建立.分組模型采用貪婪選擇算法順序求解，按照尋求最優的原則進行，在實驗過程中通過相關參數的調整，獲取最優的分類效果，實驗步驟如下：

步驟2：利用3種判別標準(概率最大原則、屬性出現次數最少原則、屬性出現次數最少原則基礎上的概率最大化原則)，分別獲取最佳屬性分組.

步驟3：重新組合數據，獲取分類結果.

步驟4：利用步驟1獲取到的結果，重復步驟2、步驟3，設定不同的權值和參數，獲取最佳分類效果.

步驟5：利用實驗所選取的數據集，與主流分類器做對比實驗.

2.3 評價標準

本文以分類器的分類準確率作為判斷分類器性能的標準，準確率是目錄最為常用的分類器判斷標準，特點是計算簡單，能體現出分類器的實際分類效果.計算公式為

在分類器分類性能驗證過程中，采用國際通用的十折交叉驗證(10-fold cross-validation)方法[9]，即在實驗過程中，將每一個數據集D均分為10份(D1，D2，…，D10)，對每一份實驗數據單獨訓練分類模型，對訓練好的模型應用于其他兄弟集進行分類準確性驗證，保證了在小數據集情況下也可以得到很好的分類效果.十折交叉法表達式為

(4)

為了獲得更好的測試效果，D1，D2，…，D10利用隨機算法隨機產生，保證分類器選用訓練集的普適性.當k=|D|時，使用leave-one-out法(每次測試僅用一個測試數據，其他數據用于訓練)進行估計，對不同分類器分類準確性進行比較.本文采用Everitt提出的比較方法McNemar測試[10]，該方法要求把數據集D分成訓練集Dh和測試集Dt2個部分，在訓練集上利用不同的學習算法A和B，得到對應的分類器FA和FB，之后通過測試集對訓練出的分類器進行測試，并構造出列聯表(見表1).

表1 列聯表

表中分類數據總和為n00+n01+n10+n11.

3 實驗與分析

利用貪婪搜索算法構建分類模型，進行反復對比實驗并調整參數，獲得最佳實驗結果.在實驗過程中，采用樸素貝葉斯(NB)分類器、樸素貝葉斯的鏈擴展(CENB)分類器、樸素貝葉斯的樹擴展(TENB)分類器、樸素貝葉斯的圖擴展(GENB)分類器、C4.5分類器(C4.5)、分類與回歸樹(CARET)分類器和BP神經網絡(BPNN)分類器、貪婪選擇算法改進的NBC(GSA-NB)進行分類實驗[11]，其中GSA-NB1、 GSA-NB2 、GSA-NB3代表3種分組原則獲取的分類準確率(見表2).

表2 實驗結果與其他分類器分類結果對比

由表2可知：對不同的數據集，改進方式體現出了差異性.3種分類原則在數據集上平均分類效果優于對比分類器，大部分數據集分類準確率有了不同程度的提升，個別數據集改進效果不明顯.

GSA-NB3與其他分類器在21個數據集上進行了對比，分類準確率的散點對比情況見圖1.圖1中的點代表對應分類器的準確率，對角線上方的點代表在相同數據集下的縱坐標對應分類器的分類準確率高于橫坐標分類器，反之則代表小于橫坐標分類器.

(a)NB與GSA-NB

(c)TENB與GSA-NB

(e)C4.5與GSA-NB

從圖1可以看出，GSA-NB3分類準確率除個別數據集略遜于對比分類器外，分類效果有明顯提升，在21個數據集中，以GSA-NB3與對比分類器在分類準確率方面做差異統計，以區段([0.5%，∞)、(-0.5%，0.5%)、(-∞，-0.5%])作為對比分類器計數依據獲得百分比統計結果如表3所示.

表3 GSA-NB3與其他分類器分類結果對比 %

在所選取的21個相同數據集下各分類器分類準確率的差異統計中，GSA-NB3的平均分類準確率明顯優于對比分類器，說明改進的分類器GSA-NB在分類準確率方面優于其他分類器.

4 小結

本文在NBC和SNBC理論基礎上，建立了基于貪婪選擇算法的GSA-NB分類器.GSA-NB在屬性組合方面選用合理的分組規則，在實驗過程中進行參數調整，充分利用了屬性間的依賴關系.實驗過程從UCI數據庫中選取21個數據集進行分類和對比實驗，分別從理論和實驗驗證了對NBC進行擴展的必要性和擴展方法的合理有效性.

[參 考 文 獻]

[1] 黃春華，陳忠偉，李石君.貝葉斯決策樹方法在招生數據挖掘中的應用[J].計算機技術與發展，2016(4)：114-118.

[2] 王輝，王雙成，周顏軍，等.基于廣義樸素貝葉斯分類器的空值處理方法[J].東北師大學報(自然科學版)，2004，36(1)：34-38.

[3] PERNKOPF F，BILMES J A.Efficient heuristics for discrimi-naive structure learning of Bayesian network classifiers[J].Journal of Machine Learning Research，2010，11：2323-2360.

[4] 趙亮，劉建輝，崔彩峰.互信息匹配的半樸素貝葉斯分類器[J].計算機工程與應用，2015(18)：84-87.

[5] 王輝，韓旭，王雙成，等.連續屬性樸素貝葉斯分類器的依賴擴展研究[J].東北師大學報(自然科學版)，2012，44(2)：41-45.

[6] YAGER-R R.An extension of the Na?ve Bayesian classifier[J].Information Science，2006，176：577-588.

[7] 王雙成，高瑞，杜瑞杰.具有超文結點時間序列貝葉斯網絡集成回歸模型[J].計算機學報，2017，40(12)：2748-2761.

[8] JULIA M，FLORES J A，GAMEZ J M，et al.Domains of competence of the semi-naive Bayesian network classifiers[J].Information Sciences，2014，260(1)：120-148.

[9] CHICKERING D M.Learning equivalence classes of Bayesian network structures[J].Journal of Machine Learning Research，2002，2(3)：445-498.

[10] ADEDOKUN OA，BURGESS WD.Analysis of paired dichotomous data：a gentle introduction to the McNemar test in SPSS[J].Journal of Multidisciplinary Evaluation，2012，8(17)：125-131.

[11] 王雙成，高瑞，杜瑞杰.基于高斯Copula的約束貝葉斯網絡分類器研究[J].計算機學報，2016，39(8)：1612-1625.