面向非均衡數(shù)據(jù)類的樸素貝葉斯改進(jìn)算法

譚志 侯濤文

摘 ?要： 針對樸素貝葉斯分類器存在對非均衡樣本分類時(shí)，易將少數(shù)類樣本分到多數(shù)類的問題，利用感受性曲線的性質(zhì)和深度特征加權(quán)的思想，提出一種面向非均衡數(shù)據(jù)類的樸素貝葉斯加權(quán)算法（DA?WNB）。為了驗(yàn)證該算法對不平衡數(shù)據(jù)分類的有效性，實(shí)驗(yàn)結(jié)果以AUC、真正類率、整體精度為指標(biāo)，仿真結(jié)果表明，該算法能提高少數(shù)類分類準(zhǔn)確率（最高達(dá)60%），且能保持較高的整體精度。

關(guān)鍵詞： 樸素貝葉斯; 監(jiān)督學(xué)習(xí); 感受性曲線; 非均衡樣本; 深度特征加權(quán); 數(shù)據(jù)挖掘

中圖分類號： TN911.1?34; TP3 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）09?0118?05

An improved naive Bayesian algorithm for unbalanced data classes

TAN Zhi， HOU Taowen

（Beijing University of Civil Engineering and Architecture， Beijing 100044， China）

Abstract： Naive Bayesian classifier is easy to divide minority?class samples into majority class samples while classifying unbalanced samples. In view of this phenomenon， an deep AUC （area under curve） weighted naive Bayesian （DA?WNB） algorithm for unbalanced data classes is proposed， which is based on property of receiver operating characteristic curve and thought of deep feature weighting. In order to verify the effectiveness of the algorithm for unbalanced data classification， the AUC， true positive rate （TPR） and overall accuracy are taken as the indicators for experiments. The simulation results show that the algorithm can improve the minority?class classification accuracy highest to 60%， and can maintain the high overall accuracy.

Keywords： naive Bayesian; supervised learning; receiver operating characteristic curve; unbalanced sample; deep feature weighting; data mining

0 ?引 ?言

樸素貝葉斯（Naive Bayesian，NB）是現(xiàn)今最普遍的監(jiān)督學(xué)習(xí)分類算法，以計(jì)算成本低、運(yùn)行效率高著稱，被廣泛用到文本分類、信息檢索、醫(yī)療診斷等領(lǐng)域。NB基于一個(gè)強(qiáng)獨(dú)立性假設(shè)，具體指各特征向量相互獨(dú)立且同等重要，這導(dǎo)致分類時(shí)損失大量有益信息。

研究者為了削弱獨(dú)立性假設(shè)造成的不良影響，提出不同形式加權(quán)貝葉斯算法。加權(quán)算法的關(guān)鍵是利用指標(biāo)衡量各個(gè)特征重要性，然后將指標(biāo)轉(zhuǎn)化為權(quán)值形式。文獻(xiàn)[1]提出用相對熵計(jì)算每個(gè)屬性在分類中的重要程度。文獻(xiàn)[2]提出用差分進(jìn)化算法搜索出最佳權(quán)值。文獻(xiàn)[3]通過多元線性回歸模型分析各特征之間的聯(lián)系，再將相關(guān)度轉(zhuǎn)化為權(quán)值系數(shù)。Kim T于2016年提出NB加權(quán)算法是為了最大化整體分類精度，沒有考慮非均衡樣本分類問題。

非均衡分類問題始于二分類任務(wù)中數(shù)據(jù)存在偏態(tài)的問題[4]，即在二分類任務(wù)中，一類的樣本數(shù)目遠(yuǎn)遠(yuǎn)大于另一類的樣本數(shù)目。傳統(tǒng)監(jiān)督學(xué)習(xí)分類算法都假設(shè)類的樣本數(shù)量大致相同，在對非均衡樣本分類時(shí)，往往易將少數(shù)類樣本分到多數(shù)類，導(dǎo)致分類器性能大大降低。其原因是分類器訓(xùn)練是為了最大化整體精度，當(dāng)多數(shù)類樣本準(zhǔn)確識別時(shí)，錯分少數(shù)類樣本不影響訓(xùn)練效果?，F(xiàn)實(shí)中，數(shù)據(jù)類經(jīng)常表現(xiàn)出非均衡的狀態(tài)[5]，比如垃圾郵件多于正常郵件，謠言多于真相等。為了精準(zhǔn)識別少數(shù)類樣本，眾多研究者提出了各種改進(jìn)方法，主要分為重采樣和代價(jià)敏感學(xué)習(xí)算法兩類。文獻(xiàn)[6]提出從不平衡數(shù)據(jù)特征研究非均衡數(shù)據(jù)，并討論非均衡數(shù)據(jù)分類器的評價(jià)指標(biāo)，文獻(xiàn)[7]通過集成算法解決不平衡問題，Kim S基于NB提出在計(jì)算似然概率時(shí)，用泊松分布代替多項(xiàng)式分布，同時(shí)考慮樣本大小標(biāo)準(zhǔn)化對分類結(jié)果的影響。Rennie等提出3種規(guī)范數(shù)據(jù)集的方法，并通過實(shí)驗(yàn)確定了三種方法的實(shí)用性順序。代價(jià)敏感學(xué)習(xí)被結(jié)合到各種經(jīng)典分類器，比如決策樹[8]、支持向量機(jī)[9]。樸素貝葉斯加權(quán)算法在不平衡數(shù)據(jù)分類領(lǐng)域的應(yīng)用仍未被挖掘。

Kim T于2016年提出了一種高效且針對非均衡數(shù)據(jù)集的貝葉斯加權(quán)算法[10]。文獻(xiàn)[11]利用感受性曲線對偏態(tài)數(shù)據(jù)集不敏感的性質(zhì)，實(shí)現(xiàn)了樣本重要特征選取和特征加權(quán)。本文在Kim T提出的算法基礎(chǔ)上結(jié)合深度特征加權(quán)的思想[12]，使算法原理更貼近實(shí)際，進(jìn)一步減弱獨(dú)立性假設(shè)對非均衡樣本分類的影響。

1 ?研究背景

1.1 ?樸素貝葉斯

樸素貝葉斯是一個(gè)簡單高效的分類模型，分類原理是將測試樣本[x]轉(zhuǎn)化為數(shù)據(jù)特征向量[a1，a2，…，am]，然后通過最大似然估計(jì)實(shí)現(xiàn)分類，如下：

式中：[cx]為NB分類器預(yù)測的類別;[Pc]稱為先驗(yàn)概率，為[c]類別樣本個(gè)數(shù)占所有類別樣本個(gè)數(shù)的百分比;[Pa1，a2，…，amc]稱為似然概率，指在[c]類中各個(gè)特征同時(shí)出現(xiàn)的概率。先驗(yàn)概率和似然概率通過訓(xùn)練樣本得到。樸素貝葉斯分類器假設(shè)各個(gè)特征相互獨(dú)立且同等重要，得出：

式中[Paic]在數(shù)據(jù)離散時(shí)采取多項(xiàng)式分布形式計(jì)算，在數(shù)據(jù)連續(xù)時(shí)采用高斯分布模擬。雖然獨(dú)立性假設(shè)不切實(shí)際，但提出NB多數(shù)情況下能準(zhǔn)確分類的原因是分類判別式只作為區(qū)別函數(shù)，不代表實(shí)際發(fā)生概率。

1.2 ?深度特征加權(quán)樸素貝葉斯（D?WNB）

加權(quán)貝葉斯分類器是基于不同特征重要性有差異的事實(shí)，通過訓(xùn)練樣本，得到不同特征對應(yīng)的權(quán)值，代入式（3）實(shí)現(xiàn)分類。

文獻(xiàn)[12]提出深度特征加權(quán)貝葉斯分類器，指出在對離散型數(shù)據(jù)分類時(shí)，大多數(shù)改進(jìn)形式都只對條件概率的公式進(jìn)行了加權(quán)，沒有將訓(xùn)練得到的權(quán)值加入到條件概率的計(jì)算當(dāng)中，為更好利用權(quán)值中所含信息，形式變換為：

式中：[naic]指第[c]類中[ai]的個(gè)數(shù);[nc]指[c]類別中所有樣本的個(gè)數(shù);[ni]指第[i]個(gè)特征向量不同特征值的個(gè)數(shù)，它與分子中“1”是為了避免零概率問題。其中，[Wi]通過特征抽取得到，選取的特征[Wi=2]，其他特征[Wi=1]，這加強(qiáng)了重要特征在預(yù)測中的作用，降低了樸素貝葉斯假設(shè)的影響。

1.3 ?AUC加權(quán)樸素貝葉斯

真陽性率（TPR）和假陽性率（FPR）是描述感受性曲線（Receiver Operating Characteristic Curve，ROC）和AUC（Area Under Curve）的重要指標(biāo)。

True Positive（TP），指樣本正確類別為正類，分類器預(yù)測類別為正類，TPR指TP的個(gè)數(shù)占正類總數(shù)的比例;False Positive（FP），指樣本正確類別為負(fù)類，但分類器預(yù)測類別為正類的樣本，F(xiàn)PR指FP的個(gè)數(shù)占負(fù)類總數(shù)的比例。在不同閾值（區(qū)別正樣本、負(fù)樣本的得分臨界值）的情況下，得到不同的TPR和FPR，再以TPR為縱坐標(biāo)，F(xiàn)PR為橫坐標(biāo)，得到一個(gè)經(jīng)過（0，0），（1，1）的曲線，即為ROC，AUC指ROC曲線下的面積。二者常被用來評價(jià)二值分類器的優(yōu)劣。

ROC曲線具有三大優(yōu)點(diǎn)[11]：

1） ROC曲線下面積越大，即AUC越大，其分類能力越強(qiáng);

2） ROC曲線下的面積可以轉(zhuǎn)化為標(biāo)量AUC，能夠體現(xiàn)ROC曲線的分類能力;

3） 當(dāng)測試樣本中正類和負(fù)類樣本數(shù)比變化時(shí)，測試結(jié)果ROC曲線基本保持不變，能體現(xiàn)AUC作為非均衡樣本分類器性能指標(biāo)的穩(wěn)定性。

根據(jù)以上性質(zhì)，Kim T等提出AUC加權(quán)樸素貝葉斯（AUC Wighted Naive Bayesian，A?WNB），該算法將單個(gè)特征作為整個(gè)訓(xùn)練樣本，用NB訓(xùn)練出每個(gè)特征對應(yīng)的[AUCi]，然后通過式（6）或式（7）計(jì)算似然概率，代入式（1）實(shí)現(xiàn)分類。

對離散型數(shù)據(jù)集：

2 ?提出的DA?WNB算法

現(xiàn)實(shí)中存在離散型數(shù)據(jù)和連續(xù)型數(shù)據(jù)，所以為提高數(shù)據(jù)模擬精度和算法實(shí)用性，本文從這兩方面提出DA?WNB。

2.1 ?離散型數(shù)據(jù)集

此時(shí)函數(shù)隨著自變量[Wi]的增加而增加，相當(dāng)于[Wi]越大，函數(shù)值越接近[fai-]，在計(jì)算[cx]時(shí)，越接近[fai-]的函數(shù)值所取的指數(shù)權(quán)值[Wi]越大。

綜上可得，深度特征加權(quán)樸素貝葉斯的本質(zhì)是權(quán)值越大的特征，似然概率越接近該特征值發(fā)生的頻率，在判別式計(jì)算中起到的作用越大，即該特征對預(yù)測實(shí)際類別的重要性越大。所以在A?WNB的基礎(chǔ)上，將各個(gè)特征對應(yīng)的[AUCi]形式作為權(quán)值加入到特征值條件概率計(jì)算之中，更能突出不同特征在分類中的不同重要性，使算法思想更符合實(shí)際。

2.2 ?連續(xù)型數(shù)據(jù)集

式（7）中標(biāo)準(zhǔn)差乘[1-AUCi]的原因如下：

1） AUC值越大，標(biāo)準(zhǔn)差越小，同一特征值[ai]計(jì)算得出的似然概率會增大，AUC值小則增長幅度較小，能突出AUC大的特征在判別式計(jì)算中的重要性;

2） 這種轉(zhuǎn)變能夠擴(kuò)大判別式計(jì)算下同一特征值在不同類別中的似然概率差值[5]。若在式（7）基礎(chǔ)上加入指數(shù)權(quán)值，可繼續(xù)擴(kuò)大該優(yōu)勢。

將深度特征加權(quán)思想應(yīng)用于A?WNB中，提出兩種形式的DA?WNB（Deep AUC Weighting Naive Bayesian，深度特征AUC加權(quán)樸素貝葉斯）算法。具體形式見式（9）～式（12），所提出算法與其他四類算法的關(guān)系如圖1所示。

圖1 ?五種算法的關(guān)系

采取這兩種形式的原因如下：將權(quán)值擴(kuò)大到1～2的范圍，更易區(qū)分重要特征和次要特征;兩種權(quán)值比較進(jìn)行實(shí)驗(yàn)，判斷權(quán)值變化程度大的DA1?WNB形式是否起到更好的效果。

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

3.1 ?仿真實(shí)驗(yàn)

非均衡數(shù)據(jù)大多為兩類，因此從UCI機(jī)器學(xué)習(xí)庫中選取13個(gè)數(shù)據(jù)集進(jìn)行二分類實(shí)驗(yàn)，規(guī)定正類為少數(shù)類。這些數(shù)據(jù)集來源于眾多領(lǐng)域，有圖像、醫(yī)療，郵件等，具體情況如表1所示。為簡化訓(xùn)練復(fù)雜度，同時(shí)保證分類的精度，特征抽取時(shí)，舍去不利于分類的特征（對應(yīng)AUC值低于50%）。實(shí)驗(yàn)結(jié)果如表2所示，表中加粗?jǐn)?shù)字為行中最大值。AUC，TPR，ACC（精度）通過文獻(xiàn)[11]中的方法計(jì)算。

表1 ?數(shù)據(jù)具體描述

3.2 ?結(jié)果分析

1） 從表2可看出，DA1?WNB和A?WNB的少數(shù)類分類準(zhǔn)確率較NB有顯著提高，9個(gè)樣本TPR超過了NB，7個(gè)樣本AUC超過了NB。但其對樣本總數(shù)少的樣本分類時(shí)，如樣本3，結(jié)果不如預(yù)期。主要原因是，少量數(shù)據(jù)時(shí)主成分提取不準(zhǔn)確，兩個(gè)加權(quán)算法擴(kuò)大了次要特征的作用，導(dǎo)致了TPR降低。

2） TPR的增加伴隨著FPR的增加，這會導(dǎo)致分類器整體精度的降低，最佳結(jié)果是在TPR增長相同的情況下，F(xiàn)PR增加較少，精度降低較少。相對于NB，A?WNB對一些數(shù)據(jù)集分類時(shí)，極大降低了精度，比如第6和第9個(gè)樣本（最高損失14.3%），而DA?WNB 對13個(gè)樣本分類時(shí)都未表現(xiàn)出精度失衡（最高損失5.4%）。這說明DA?WNB穩(wěn)定性強(qiáng)于A?WNB。

表2 ?實(shí)驗(yàn)結(jié)果

3） 較DA1?WNB，DA2?WNB在對第2和第9個(gè)樣本分類時(shí)TPR失常，其他表現(xiàn)持平。觀察發(fā)現(xiàn)，兩樣本在NB分類下TPR較低。這說明主成分抽取準(zhǔn)確，但其沒有起到突出主成分的作用。主要原因在于，兩樣本中只有個(gè)別重要特征對應(yīng)的AUC較大，其他都接近50%。因此，權(quán)值變化程度大的DA1?WNB算法能避免損失主成分的重要信息，更貼近實(shí)際。

4 ?結(jié) ?語

在實(shí)際應(yīng)用中，數(shù)據(jù)分布往往是偏態(tài)的。樸素貝葉斯對偏態(tài)數(shù)據(jù)分類時(shí)，結(jié)果易傾向于多數(shù)類，導(dǎo)致少數(shù)類準(zhǔn)確率降低。本文針對此問題，綜合AUC對偏態(tài)樣本集不敏感的性質(zhì)和深度利用權(quán)值信息的思想，提出加權(quán)形式貝葉斯算法DA?WNB。結(jié)果顯示，DA?WNB有效地提高了少數(shù)類分類的準(zhǔn)確率，且較A?WNB不易總體精度失常，同時(shí)證明了權(quán)值變化程度較大的DA1?WNB有利于保留主成分重要信息。算法不足在于未能準(zhǔn)確提取小樣本集主要特征。今后將利用多項(xiàng)指標(biāo)得出權(quán)值，并挖掘主要特征與權(quán)值之間的關(guān)系，這將更大程度減弱樸素貝葉斯獨(dú)立性假設(shè)的影響。

參考文獻(xiàn)

[1] LEE C H， GUTIERREZ F， DOU D. Calculating feature weights in naive Bayes with Kullback?Leibler measure [C]// 2011 IEEE International Conference on Data Mining. Vancouver： IEEE， 2011： 1146?1151.

[2] WU J， CAI Z. Attribute weighting via differential evolution algorithm for attribute weighted naive Bayes （WNB） [J]. Journal of computational information systems， 2011， 7（5）： 1672?1679.

[3] WANG X， SUN X. An improved weighted naive Bayesian classification algorithm based on multivariable linear regression model [C]// 2017 International Symposium on Computational Intelligence and Design. Hangzhou： IEEE， 2017： 219?222.

[4] KRAWCZYK B. Learning from imbalanced data： open challenges and future directions [J]. Progress in artificial intelligence， 2016， 5（4）： 1?12.

[5] LEE J S， ZHU D. When costs are unequal and unknown： a subtree grafting approach for unbalanced data classification [J]. Decision sciences， 2011， 42（4）： 803?829.

[6] PRATI R C， BATISTA G E A P A， SILVA D F. Class imba?lance revisited： a new experimental setup to assess the performance of treatment methods [J]. Knowledge & information systems， 2015， 45（1）： 1?24.

[7] GALAR M， FERNANDEZ A， BARRENECHEA E， et al. A review on ensembles for the class imbalance problem： bagging， boosting， and hybrid?based approaches [J]. IEEE transactions on systems man & cybernetics Part C， 2012， 42（4）： 463?484.

[8] KRAWCZYK B， WONIAK M， SCHAEFER G. Cost?sensitive decision tree ensembles for effective imbalanced classification [J]. Applied soft computing， 2014， 14（1）： 554?562.

[9] YAN Q， XIA S， MENG F. Optimizing cost?sensitive SVM for imbalanced data： connecting cluster to classification [EB/OL]. [2017?11?05]. https：//arxiv.org/pdf/1702.01504.pdf.

[10] KIM T， CHUNG B D， LEE J S. Incorporating receiver opera?ting characteristics into naive Bayes for unbalanced data classification [J]. Computing， 2016 （3）： 1?16.

[11] KRUPINSKI E A. Receiver operating characteristic （ROC） analysis [J]. Frontline learning research， 2017， 5（3）： 31?42.

[12] JIANG L， LI C， WANG S， et al. Deep feature weighting for naive Bayes and its application to text classification [J]. Engineering applications of artificial intelligence， 2016， 52（C）： 26?39.