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

王 輝，張 帆，李玉杰

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

0 引言

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

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

各種對NBC獨(dú)立性假設(shè)方面的改進(jìn)，在不同數(shù)據(jù)集上不同程度地提高了數(shù)據(jù)分類準(zhǔn)確性，說明從獨(dú)立性假設(shè)方面改進(jìn)NBC是有效可行的.

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

1 半樸素貝葉斯分類器

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

(1)

推知SNBC模型為

(2)

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

(3)

2 模型建立與評價體系

本文將貪婪選擇算法思想融入到樸素貝葉斯分類器的改進(jìn)過程中，結(jié)合分類器判別標(biāo)準(zhǔn)進(jìn)行相應(yīng)的實(shí)驗(yàn).

2.1 貪婪選擇算法

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

2.2 數(shù)據(jù)來源及模型建立

(1) 數(shù)據(jù)來源.實(shí)驗(yàn)所用數(shù)據(jù)來自國際標(biāo)準(zhǔn)數(shù)據(jù)集倉庫UCI，選取21個數(shù)據(jù)集用于實(shí)驗(yàn)，進(jìn)行貝葉斯分類的學(xué)習(xí).

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

步驟2：利用3種判別標(biāo)準(zhǔn)(概率最大原則、屬性出現(xiàn)次數(shù)最少原則、屬性出現(xiàn)次數(shù)最少原則基礎(chǔ)上的概率最大化原則)，分別獲取最佳屬性分組.

步驟3：重新組合數(shù)據(jù)，獲取分類結(jié)果.

步驟4：利用步驟1獲取到的結(jié)果，重復(fù)步驟2、步驟3，設(shè)定不同的權(quán)值和參數(shù)，獲取最佳分類效果.

步驟5：利用實(shí)驗(yàn)所選取的數(shù)據(jù)集，與主流分類器做對比實(shí)驗(yàn).

2.3 評價標(biāo)準(zhǔn)

本文以分類器的分類準(zhǔn)確率作為判斷分類器性能的標(biāo)準(zhǔn)，準(zhǔn)確率是目錄最為常用的分類器判斷標(biāo)準(zhǔn)，特點(diǎn)是計算簡單，能體現(xiàn)出分類器的實(shí)際分類效果.計算公式為

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

(4)

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

表1 列聯(lián)表

表中分類數(shù)據(jù)總和為n00+n01+n10+n11.

3 實(shí)驗(yàn)與分析

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

表2 實(shí)驗(yàn)結(jié)果與其他分類器分類結(jié)果對比

由表2可知：對不同的數(shù)據(jù)集，改進(jìn)方式體現(xiàn)出了差異性.3種分類原則在數(shù)據(jù)集上平均分類效果優(yōu)于對比分類器，大部分?jǐn)?shù)據(jù)集分類準(zhǔn)確率有了不同程度的提升，個別數(shù)據(jù)集改進(jìn)效果不明顯.

GSA-NB3與其他分類器在21個數(shù)據(jù)集上進(jìn)行了對比，分類準(zhǔn)確率的散點(diǎn)對比情況見圖1.圖1中的點(diǎn)代表對應(yīng)分類器的準(zhǔn)確率，對角線上方的點(diǎn)代表在相同數(shù)據(jù)集下的縱坐標(biāo)對應(yīng)分類器的分類準(zhǔn)確率高于橫坐標(biāo)分類器，反之則代表小于橫坐標(biāo)分類器.

(a)NB與GSA-NB

(c)TENB與GSA-NB

(e)C4.5與GSA-NB

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

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

在所選取的21個相同數(shù)據(jù)集下各分類器分類準(zhǔn)確率的差異統(tǒng)計中，GSA-NB3的平均分類準(zhǔn)確率明顯優(yōu)于對比分類器，說明改進(jìn)的分類器GSA-NB在分類準(zhǔn)確率方面優(yōu)于其他分類器.

4 小結(jié)

本文在NBC和SNBC理論基礎(chǔ)上，建立了基于貪婪選擇算法的GSA-NB分類器.GSA-NB在屬性組合方面選用合理的分組規(guī)則，在實(shí)驗(yàn)過程中進(jìn)行參數(shù)調(diào)整，充分利用了屬性間的依賴關(guān)系.實(shí)驗(yàn)過程從UCI數(shù)據(jù)庫中選取21個數(shù)據(jù)集進(jìn)行分類和對比實(shí)驗(yàn)，分別從理論和實(shí)驗(yàn)驗(yàn)證了對NBC進(jìn)行擴(kuò)展的必要性和擴(kuò)展方法的合理有效性.

[參 考 文 獻(xiàn)]

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

[2] 王輝，王雙成，周顏軍，等.基于廣義樸素貝葉斯分類器的空值處理方法[J].東北師大學(xué)報(自然科學(xué)版)，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].計算機(jī)工程與應(yīng)用，2015(18)：84-87.

[5] 王輝，韓旭，王雙成，等.連續(xù)屬性樸素貝葉斯分類器的依賴擴(kuò)展研究[J].東北師大學(xué)報(自然科學(xué)版)，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] 王雙成，高瑞，杜瑞杰.具有超文結(jié)點(diǎn)時間序列貝葉斯網(wǎng)絡(luò)集成回歸模型[J].計算機(jī)學(xué)報，2017，40(12)：2748-2761.

[8] JULIA M，F(xiàn)LORES 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的約束貝葉斯網(wǎng)絡(luò)分類器研究[J].計算機(jī)學(xué)報，2016，39(8)：1612-1625.