結(jié)合馬氏距離的smote改進(jìn)算法研究

徐湘君 劉波濤

摘要：傳統(tǒng)的smote算法應(yīng)用于非平衡數(shù)據(jù)集研究領(lǐng)域，它可以將少數(shù)類樣本按照一定的條件進(jìn)行擴(kuò)充，以達(dá)到讓非平衡數(shù)據(jù)集中少數(shù)類樣本和多數(shù)類樣本達(dá)到平衡這一目的。但是它在對(duì)于邊界元素的選擇生成數(shù)據(jù)的時(shí)候具有盲目性，使得生成的新的數(shù)據(jù)降低少數(shù)類樣本的質(zhì)量。針對(duì)這種情況，提出了將馬氏距離結(jié)合SMOTE算法的改進(jìn)算法Maha-smote，讓生成的新元素更加靠近樣本集中心，提高生成的數(shù)據(jù)集的總體質(zhì)量。本文分別使用傳統(tǒng)SMOTE、Pychon的sklearn庫(kù)中的SMOTE算法以及Maha-smote算法對(duì)所選用的3個(gè)不平衡數(shù)據(jù)集進(jìn)行過(guò)采樣數(shù)據(jù)預(yù)處理然后使用決策樹和高斯樸素貝葉斯GNB分類器對(duì)預(yù)處理后的數(shù)據(jù)集進(jìn)行預(yù)測(cè)，選擇F-Measure、AUC作為分類性能的評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)表明Maha-smote算法預(yù)處理的不平衡數(shù)據(jù)集的分類效果更好，證明了該算法的有效性。

關(guān)鍵詞：非平衡數(shù)據(jù)集;上采樣;SMOTE算法;馬氏距離;邊界樣本

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）29-0028-04

1 引言

現(xiàn)如今常見(jiàn)的數(shù)據(jù)分類方法通常假設(shè)數(shù)據(jù)之間是平衡的，認(rèn)為不同樣本之間的數(shù)據(jù)數(shù)量是相差不多的，但是在我們的日常生活中還存在著許多非平衡的數(shù)據(jù)。例如醫(yī)療領(lǐng)域的病癥方面的識(shí)別、金融方面的信用卡欺詐檢測(cè)以及關(guān)于貸款方面的貸款檢測(cè)[1]等。通常我們把數(shù)量大的類型成為多數(shù)類，數(shù)量少的類型成為少數(shù)類，在這些領(lǐng)域通常少數(shù)類與多數(shù)類之間的比例為1：10、1：100甚至為1：10000或更大[2]，這種情況下，傳統(tǒng)的分類方法就不適用于非平衡的數(shù)據(jù)，因?yàn)樗麄兺ǔ?huì)將少數(shù)類當(dāng)作噪聲處理掉，這樣分類的話結(jié)果也不是我們想要的，在現(xiàn)實(shí)生活中也會(huì)帶來(lái)不好的影響。

關(guān)于非平衡數(shù)據(jù)現(xiàn)如今有很多的研究，目前基本上是分為兩個(gè)層面進(jìn)行研究，分別為數(shù)據(jù)層面和算法層面。從數(shù)據(jù)層面出發(fā)就是改變數(shù)據(jù)之間的分布將不平衡的數(shù)據(jù)通過(guò)采樣方法變成平衡的數(shù)據(jù)，N.V.Chawlac3]等人提出了最經(jīng)典的SMOTE（Synthetic Minority Over-sampling TEchnique）過(guò)采樣技術(shù)，Tor-res F Rc4]等人提出使用少數(shù)類k近鄰樣本的均值點(diǎn)來(lái)合成新樣本的SMOTE-D算法，han hc5]等人提出來(lái)一種是自適應(yīng)上采樣方法Borderline-SMOTE。

從算法層面主要通過(guò)對(duì)算法進(jìn)行優(yōu)化來(lái)提高分類器的性能，例如徐麗麗[6]等人提出一種新的不平衡數(shù)據(jù)加權(quán)集成學(xué)習(xí)算法，主要是通過(guò)為各類別分配不同的權(quán)重將加權(quán)支持向量機(jī)模型WSVM（Weighted Support Vector Machine）與模糊聚類相結(jié)合。Nghe等[7]為降低不平衡數(shù)據(jù)集誤分類的成本將采樣技術(shù)與使用支持向量機(jī)SVM的代價(jià)敏感學(xué)習(xí)算法相結(jié)合。

本文主要從數(shù)據(jù)層面出發(fā)，對(duì)其中的上采樣方法方面進(jìn)行研究，提出一種基于馬氏距離的SMOTE改進(jìn)算法Maha-smote算法，以少數(shù)類樣本為中心，選擇k個(gè)近鄰，通過(guò)比較元素與元素之間的馬氏距離來(lái)判斷生成的新元素應(yīng)當(dāng)更加靠近哪個(gè)元素，從而讓生成的新元素更加的靠近整個(gè)集群的中心，而不會(huì)像傳統(tǒng)的SMOTE算法一樣，在邊界上的離群點(diǎn)附近也會(huì)隨機(jī)生成許多的新元素，從而使得新的平衡樣本盡量少的產(chǎn)生質(zhì)量較差的數(shù)據(jù)。

2 基礎(chǔ)算法簡(jiǎn)介

2.1 SMOTE算法

SMOTE算法[1]的原理是通過(guò)相鄰的兩個(gè)少數(shù)類之間線性插值生成一個(gè)新元素，最終使得少數(shù)類與多數(shù)類數(shù)量達(dá)到一個(gè)數(shù)據(jù)之間的平衡。算法流程如下：

（1）對(duì)于少數(shù)類中每一個(gè)樣本x，計(jì)算它的近鄰的歐幾里得距離，按照從小到大的順序排序，將前k個(gè)近鄰合并為k近鄰集合;

（2）根據(jù)多數(shù)類和少數(shù)類樣本的不平衡比例設(shè)置上采樣倍率N，對(duì)于每一個(gè)少數(shù)類樣本x，從其k近鄰集合中隨機(jī)選擇幾個(gè)樣本，近鄰樣本為x。;

（3）對(duì)于每一個(gè)隨機(jī)選出的近鄰x。，分別與樣本x按照合成新樣本的公式構(gòu)建新的樣本。

Xnew=x+rand（0，1）×（xn-x）

SMOTE算法避免了隨機(jī)過(guò)采樣算法中造成分類器模型過(guò)擬合的問(wèn)題，但是其在生成新樣本的時(shí)候關(guān)于樣本邊界方面并沒(méi)有進(jìn)行考慮，因而在生成新樣本還存在著些許的問(wèn)題。

2.2馬氏距離

馬氏距離（Mahalanobis distance）是由印度統(tǒng)計(jì)學(xué)家馬哈拉諾比斯提出的，它可以用來(lái)計(jì)算一個(gè)點(diǎn)與一個(gè)分布之間的距離。相對(duì)于歐氏距離，馬氏距離對(duì)于樣本的計(jì)算會(huì)考慮到特征的聯(lián)系，但是卻不會(huì)受到特征的尺度影響。

假設(shè)身高和體重，這兩個(gè)變量擁有不同的單位標(biāo)準(zhǔn)，也就是有不同的尺度。比如身高用mm計(jì)算，而體重用kg計(jì)算，顯然差lOmm的身高與差lOkg的體重是完全不同的。但在普通的歐氏距離計(jì)算中，這將會(huì)算作相同的差距。

上圖中如果不考慮分布，按照歐式距離計(jì)算，那么A點(diǎn)相對(duì)B點(diǎn)就更加接近綠點(diǎn)，但是考慮到樣本分布更像是一個(gè)樣本基本服從f（x）=x的線性分布，按照馬氏距離計(jì)算，此時(shí)A點(diǎn)相對(duì)于B點(diǎn)更像是一個(gè)離群點(diǎn)。

相對(duì)于歐氏距離，馬氏距離的計(jì)算會(huì)更加考慮總體樣本的分布，可以更好地排除樣本變量之間的相關(guān)性的干擾。它不受量綱的影響，兩點(diǎn)之間的馬氏距離與原始數(shù)據(jù)的測(cè)量單位無(wú)關(guān)，由標(biāo)準(zhǔn)化數(shù)據(jù)和中心化數(shù)據(jù)（即原始數(shù)據(jù)與均值之差）計(jì)算出的二點(diǎn)之間的馬氏距離相同。

3 主要內(nèi)容

基于馬氏距離的改進(jìn)SMOTE算法Maha-smote算法

馬氏距離在本文中的算法流程：

（1）輸入少數(shù)類元素x，以及少數(shù)類集合D;

（2）計(jì)算少數(shù)類元素與集合D平均值DM的距離xm=x- DM;

（3）求少數(shù)類x和集合D的協(xié)方差矩陣S以及協(xié)方差矩陣的逆矩陣SI：

（4）最后馬氏距離公式計(jì)算每個(gè)元素的馬氏距離mahal（x）。

Maha-smote算法流程是在SMOTE算法上的改進(jìn)：

（1）對(duì)于少數(shù)類中每一個(gè)樣本x，計(jì)算它的近鄰的歐幾里得距離，按照從小到大的順序排序，將前k個(gè)近鄰合并為k近鄰集合;

（2）根據(jù)多數(shù)類和少數(shù)類樣本的不平衡比例設(shè)置上采樣倍率N，對(duì)于每一個(gè)少數(shù)類樣本x.從其k近鄰集合中隨機(jī)選擇幾個(gè)樣本，近鄰樣本為x。;

（3）對(duì)于每一個(gè)選出的近鄰xn，計(jì)算其馬氏距離mahal（xn），以及中心元素的馬氏距離mahal（x）;

（4）比較中心元素x與近鄰元素xn的馬氏距離，如果mahal（x） >mahal（xn），那么代表x相對(duì)于xn更加的靠近邊界，因而生成的元素則要相對(duì)靠近xn，反之則需要靠近x，保證生成的新元素更加的接近集合中心;

（5）因此生成元素的公式則變成：

依據(jù)馬氏距離生成的元素更加靠近集合中心，生成的新元素質(zhì)量將會(huì)更高，由噪聲數(shù)據(jù)生成的新元素對(duì)總體帶來(lái)的影響將會(huì)被減少到更小的程度，從而提高分類算法的整體性能。

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

4.1 不平衡數(shù)據(jù)集評(píng)價(jià)指標(biāo)

在傳統(tǒng)的分類學(xué)習(xí)方法中，常用的方法是采用分類精度（正確分類的樣本占總樣本的比例）作為判斷分類器好壞的指標(biāo)。但是對(duì)于不平衡數(shù)據(jù)集來(lái)說(shuō)，用分類精度來(lái)評(píng)價(jià)分類器的性能是不合理的。例如當(dāng)少數(shù)類比例非常少時(shí)，即使將全部少數(shù)類都分為多數(shù)類，總精度仍然能達(dá)到很高的程度。但這樣的分類器是沒(méi)有實(shí)際意義的，其對(duì)少數(shù)類的分類正確率非常低。

對(duì)于不平衡問(wèn)題，已有新的評(píng)價(jià)標(biāo)準(zhǔn)，如F-Measure方法。這里F-Measure是一種統(tǒng)計(jì)量，F(xiàn)-Measure又稱為F-Score，F(xiàn)-Measure是Precision和Recall加權(quán)調(diào)和平均，常用于評(píng)價(jià)分類模型的優(yōu)劣程度。關(guān)于F的計(jì)算公式為：

其中β是參數(shù)，P是精確率（Precision），R是召回率（Recall）。

如表1所示，通常情況下我們可以對(duì)識(shí)別數(shù)據(jù)的情況分成四類：

β<1時(shí)代表著更加注重精確率（precision）;β>1時(shí)則代表著更加注重召回率（recall）的作用。這里參數(shù)β取1時(shí)，代表著精確率（precision）和召回率（recall）同樣重要，那么F-Measure值越高代表著性能越好。因此，它可以作為不平衡數(shù)據(jù)集分類問(wèn)題的一種有效評(píng)估標(biāo)準(zhǔn)。

ROC曲線AUC面積

ROCc9]曲線的設(shè)置橫坐標(biāo)為假正類率（False Positive Rate），設(shè)置縱坐標(biāo)為真正類率（True Positive Rate），相應(yīng)的還有真負(fù)類率（True Negative Rate）和假負(fù)類率（False Negative Rate）。這四類指標(biāo)：

（1）假正類率（FPR）：判定為正例卻不是真正例的概率，即真負(fù)例中判為正例的概率;

（2）真正類率（TPR）：判定為正例也是真正例的概率，即真正例中判為正例的概率;

（3）真負(fù)類率（FNR）：判定為負(fù)例卻不是真負(fù)例的概率，即真正例中判為負(fù)例的概率;

（4）假負(fù)類率（TNR）：判定為負(fù)例也是真負(fù)例的概率，即真負(fù)例中判為負(fù)例的概率。

ROC曲線的特點(diǎn)：

（1）ROC曲線能查出不同的閾值對(duì)分類器的泛化性能影響;

（2）ROC曲線越靠近左上角，代表著分類器模型的準(zhǔn)確性就越高;

（3）ROC曲線上最靠近左上角的點(diǎn)是分類錯(cuò)誤最少的最好閾值;

（4）可以比較不同的分類器的性能。將各個(gè)分類器的ROC曲線繪制到同一坐標(biāo)中，直觀地比較優(yōu)劣。

我們?nèi)绻M(jìn)行分類器的比較，若一個(gè)分類器的ROC曲線把另一個(gè)分類器的曲線完全包住，我們就能輕易地判斷兩者優(yōu)劣程度;但是如果兩個(gè)分類器的ROC曲線發(fā)生交叉，那么就很難判斷兩者的優(yōu)劣程度。此時(shí)我們?nèi)绻砸M(jìn)行判斷可以使用AUC[10-11]，就是ROC曲線下方的面積（Area under the Curve），在比較不同的分類模型時(shí)，可以將每個(gè)模型的ROC曲線都畫出來(lái)，比較曲線下面積來(lái)判斷組好的模型是什么。其意義是。

（1）因?yàn)槭窃?x1的方格里求面積，AUC的值必定在0到1之間。

（2）假設(shè)一個(gè)閾值，閾值以上是正類，以下是負(fù)類;若隨機(jī)抽取一個(gè)正類樣本和一個(gè)負(fù)類樣本，分類器正確判斷正類樣本的值高于負(fù)類樣本的概率= AUC。

（3）總的來(lái)說(shuō)：AUC值越大的分類器，正確率越高。

4.2 實(shí)驗(yàn)結(jié)果與分析

為了評(píng)估Maha-smote算法的性能，本次研究使用的數(shù)據(jù)集是UCI平臺(tái)的SPECTF Heart、Online Shoppers Purchasing In-tention Dataset以及采用sklearn的相關(guān)技術(shù)隨機(jī)制造數(shù)據(jù)集Skleam-data。下表顯示每個(gè)數(shù)據(jù)集的樣本規(guī)模、屬性以及多數(shù)類少數(shù)類數(shù)量和不平衡比。可以看到每個(gè)數(shù)據(jù)集的數(shù)據(jù)分布非常不平衡，可以很好地使用算法進(jìn)行研究。

除此之外，本文在生成新數(shù)據(jù)的時(shí)候還使用了SMOTE經(jīng)典算法以及skleam庫(kù)里的smote方法進(jìn)行對(duì)比，為了公平起見(jiàn)，k近鄰的選擇均將k值設(shè)置為5，借此展示Maha-smote算法的性能，然后還將使用決策樹、Gaussian Navie Bayes來(lái)采用K折交叉驗(yàn)證來(lái)對(duì)經(jīng)過(guò)不同SMOTE算法進(jìn)行采樣后的新數(shù)據(jù)進(jìn)行預(yù)測(cè)，分類的效果將使用F-Measure、AUC這些評(píng)價(jià)指標(biāo)進(jìn)行展示。

在使用決策樹和GNB分類器對(duì)不同采樣算法在三個(gè)數(shù)據(jù)集進(jìn)行采樣后的表現(xiàn)，可以看到相對(duì)于經(jīng)典SMOTE算法和sklearn-smote方法的表現(xiàn)，Maha-smote算法的f-score、AUC評(píng)分均高于前兩個(gè)采樣方法，且在某些方面和GNB-起搭配能夠?qū)Ψ瞧胶鈹?shù)據(jù)集進(jìn)行更好的預(yù)測(cè)。

5 結(jié)束語(yǔ)

本文提出將馬氏距離結(jié)合到smote算法來(lái)更好的生成新數(shù)據(jù)，它可以更好地提高新生成樣本的樣本質(zhì)量，可以降低邊界元素在生成樣本之后對(duì)經(jīng)過(guò)采樣后造成不好的影響，可以讓生成元素更加接近集合中心，提高整個(gè)新少數(shù)類集合的總體質(zhì)量，以便于后續(xù)的分類算法更好地對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)等操作。不過(guò)Maha-smote對(duì)于遠(yuǎn)離邊界的數(shù)據(jù)或是噪聲數(shù)據(jù)并沒(méi)有進(jìn)一步的操作，如果能夠進(jìn)一步地進(jìn)行噪聲數(shù)據(jù)方面的識(shí)別與處理，如果刪去或是降低其生成元素時(shí)的占比，那么算法可能還將進(jìn)一步優(yōu)化，可以提高運(yùn)行效率。

參考文獻(xiàn)：

[1]謝艷晴.基于非平衡數(shù)據(jù)集的貸款違規(guī)預(yù)測(cè)研究[D].荊州：長(zhǎng)江大學(xué)，2019.

[2] Provost F，F(xiàn)awcett T.Robust classification for imprecise envi-ronments[J].Machine Learning，2001，42（3）：203 -23 1.

[3] Chawla N V，Bowyer K W，Hall L O，et aI.SMOTE：synthetic mi-nority over-sampling technique[J].Journal of Artificial Intelli-gence Research，2002，16：321-357.

[4] Torres F R，Carrasco-Ochoa J A，Martinez-Trinidad J F.SMOTE-D a deterministic version of SMOTE[M]//LectureNotes in Computer Science.Cham：Springer Intemational Pub-lishing，2016：177-188.

[5] Han H，Wang W Y，Mao B H.Borderline-SMOTE：a newoversampling method in imbalanced data sets learning[C]//ln-ternational Conference on Advances in Intelligent Computing.Berlin：Springer一Verlag，2005.878—887.

[6]Nghe N T，Janecek P，Haddawy P.A compamtive analysis oftechniques for predicting academic performance[C]//Proc ofthe 37th IEEE Fmntiers in Education Conference—dobal Engi—neering：Knowledge Without Borders，2007：7—12.

[7]徐麗麗，閆德勤.不平衡數(shù)據(jù)加權(quán)集成學(xué)習(xí)算法[J]，微型機(jī)與應(yīng)用，2015，34（23）：7—10.

[8]李克文，林亞林，楊耀忠.一種改進(jìn)的基于歐氏距離的SDR—SMOTE算法[J].計(jì)算機(jī)工程與科學(xué)，2019，41（11）：2063—2070.

[9]AUC一—百度百科https：//baike.baidu.com/item/AUC/19282953.

[10]汪云云，陳松燦.基于AUC的分類器評(píng)價(jià)和設(shè)計(jì)綜述[J].模式識(shí)別與人工智能，2011，24（1）：64—71.

[11]Evaluation of clustering.斯坦福大學(xué)自然語(yǔ)言處理實(shí)驗(yàn)室網(wǎng)站https：//nlp.staJlford.edu/IR-bookmtInl/lltIIlleditioIl/evalua—tion—of-clustering一1.htInl[2013—04—20].

【通聯(lián)編輯：梁書】

作者簡(jiǎn)介：徐湘君（1997-），河南固始人，長(zhǎng)江大學(xué)研究生，研究方向?yàn)閿?shù)據(jù)分析;劉波濤（1980-），男，副教授，博士，碩士生導(dǎo)師，王要研究方向：軟件開發(fā)技術(shù)、人工智能技術(shù)、物聯(lián)網(wǎng)應(yīng)用技術(shù)、計(jì)算機(jī)在石油勘探及開發(fā)中的應(yīng)用研究等。