譚 浩，田愛奎，吳志勇

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255049)

由于現(xiàn)代社會(huì)信息爆炸式發(fā)展，如何從海量的信息中提取有用的知識(shí)越來越受到重視.其中分類是一種重要方法.分類已經(jīng)被廣泛運(yùn)用到各領(lǐng)域，而大多數(shù)的分類方法都要求各種類型的數(shù)據(jù)具有較為均勻的分布，但是有一些特殊的事件比較罕見.針對(duì)罕見事件的分類是許多領(lǐng)域中常見的問題，如欺詐交易、網(wǎng)絡(luò)入侵檢測(cè)和醫(yī)學(xué)診斷等.而分類中伴隨著分類成本不同的問題[1]，如將病人誤診為健康人的代價(jià)比將健康人誤診為病人的大得多，后者只是增加成本，而前者會(huì)導(dǎo)致失去生命.針對(duì)包含罕見事件的不平衡數(shù)據(jù)集的研究方法主要分為兩個(gè)方面:數(shù)據(jù)層方法和算法層方法[2].數(shù)據(jù)層方法是先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，然后用于學(xué)習(xí).主要的方法可分為過抽樣和欠抽樣兩種.過抽樣是通過增加數(shù)據(jù)集中少數(shù)類實(shí)例的數(shù)量以提高少數(shù)類分類精度，本文所用的SMOTE算法就是一種過抽樣算法；欠抽樣就是減少數(shù)據(jù)集中多數(shù)類實(shí)例的數(shù)量來平衡數(shù)據(jù)集的類別分布，如文獻(xiàn)[3]為此提出了一種基于樣本權(quán)重的欠抽樣方法，該方法引入了樣本權(quán)重來反映樣本所處的區(qū)域，通過多次聚類修改樣本權(quán)重，然后根據(jù)樣本權(quán)重進(jìn)行抽樣.過抽樣與欠抽樣都可以達(dá)到平衡數(shù)據(jù)集的目的，但一般欠抽樣算法優(yōu)于過抽樣算法[4].算法層方法就是通過修改分類算法本身,來提高少數(shù)類的分類精度，當(dāng)不同類被錯(cuò)分的代價(jià)不等時(shí), 便引出了代價(jià)敏感(Cost-sensitive) 分類，較為著名的有 MetaCost方法[5]，但它不能估計(jì)后驗(yàn)概率；FU[6]提出一種多標(biāo)簽代價(jià)敏感分類集成學(xué)習(xí)算法，算法的流程類似于自適應(yīng)提升，可以自動(dòng)學(xué)習(xí)多個(gè)弱分類器來組合成強(qiáng)分類器；文獻(xiàn)[7]提出了一種局部代價(jià)敏感算法.代價(jià)敏感學(xué)習(xí)要求設(shè)計(jì)的分類器滿足錯(cuò)分代價(jià)最小而非分類錯(cuò)誤率最小，從而提高錯(cuò)分代價(jià)高的樣本分辨率.本文將兩者結(jié)合，通過在AdaCost算法每次迭代前插入合成的少數(shù)類以提高分類器在分布不平衡的數(shù)據(jù)集上的表現(xiàn)，實(shí)驗(yàn)驗(yàn)證了算法的有效性.

1 評(píng)價(jià)標(biāo)準(zhǔn)和相關(guān)算法

1.1 不平衡數(shù)據(jù)集分類的評(píng)價(jià)標(biāo)準(zhǔn)

表1所示的混淆矩陣通常被用于評(píng)估機(jī)器學(xué)習(xí)算法的性能.在分類問題中，假設(shè)C類為少數(shù)類，在代價(jià)敏感分類算法中也被稱為正類，而NC作為所有其他類的結(jié)合，在代價(jià)敏感分類算法中也被稱為負(fù)類，在檢測(cè)C類時(shí)有四種可能的結(jié)果.通過表1，精確率(Precision)，召回率(Recall)，F(xiàn)-measure有如下定義：

式中：β表示Recall和Precision的相對(duì)重要性，在本文中β=1.只有Recall和Precision都比較大時(shí)，F(xiàn)-measure才會(huì)相應(yīng)比較大.因此，F(xiàn)-measure可以合理評(píng)價(jià)分類器對(duì)于少數(shù)類(正類)的分類性能.

表1 分類混淆矩陣
Tab.1 Confusion matrix defines

預(yù)測(cè)的正類“C”預(yù)測(cè)的負(fù)類“NC”真實(shí)的正類 “C”真實(shí)的負(fù)類“NC”TPFPFNTN

1.2 相關(guān)算法

1.2.1 SMOTE算法

SMOTE (Synthetic Minority Oversampling Technique)算法[8]是為減小數(shù)據(jù)集中少數(shù)類影響而提出的人工合成抽樣技術(shù).算法在“特征空間”中操作，而不是在“數(shù)據(jù)空間”中合成少數(shù)類實(shí)例，算法偽代碼如圖1所示.

圖1 偽代碼Fig.1 Pseudocode

對(duì)于連續(xù)性特征：

(1)取少數(shù)類樣本的特征向量和它K近鄰中任意一個(gè)少數(shù)類樣本的特征向量之間的差.

(2)用0到1之間的隨機(jī)數(shù)乘以這個(gè)差.

(3)將第(2)步計(jì)算結(jié)果添加到原始特征向量的特征值中，從而創(chuàng)建一個(gè)新的特征向量.

對(duì)于標(biāo)稱特性：

(1)少數(shù)類樣本的特征向量和它K近鄰中少數(shù)類樣本的特征向量進(jìn)行投票選擇.在平局的情況下，隨機(jī)選擇.

(2)將該值分配給新合成的少數(shù)類樣本.

使用這種技術(shù)，可以在連接少數(shù)類樣本及其最近鄰的線段上創(chuàng)建一個(gè)新的少數(shù)類樣本.通過合成少數(shù)類實(shí)例可以拓寬決策樹(如C4.5)、規(guī)則學(xué)習(xí)算法(如RIPPER算法)的決策區(qū)域[9].

1.2.2 AdaCost算法

AdaCost算法是AdaBoost算法[10]的一個(gè)變種.AdaCost算法[11]保持了AdaBoost算法核心理論.而在AdaCost算法中，權(quán)值更新規(guī)則給予被錯(cuò)誤分類的錯(cuò)分代價(jià)高的樣本更高的權(quán)重，而被正確分類的錯(cuò)分代價(jià)高的樣本較為保守的權(quán)重.這是通過在權(quán)重更新公式中引入誤分類代價(jià)調(diào)整函數(shù)來實(shí)現(xiàn)的.在這種更新規(guī)則下，錯(cuò)分代價(jià)高的樣本權(quán)重較高，而錯(cuò)分代價(jià)低的樣本權(quán)重相對(duì)較低.這樣，每輪迭代產(chǎn)生的弱分類器都更加關(guān)注錯(cuò)分代價(jià)高的樣本，最終投票產(chǎn)生的強(qiáng)分類器也將正確地識(shí)別錯(cuò)分代價(jià)更高的樣本.

2 Cost-SMOTEBoost算法

AdaCost通過錯(cuò)分代價(jià)來更新每輪迭代中訓(xùn)練樣本的權(quán)重，給予少數(shù)類(正類)更大的權(quán)重，算法更關(guān)注那些少數(shù)類樣本.通過SMOTE合成實(shí)例可以改善樣本的類別分布.本文將兩者結(jié)合，提出了Cost-SMOTEBoost算法，在每輪迭代的開始向數(shù)據(jù)集中插入合成的少數(shù)類實(shí)例，改善少數(shù)類的分布，同時(shí)分類結(jié)果向更被人們關(guān)注的錯(cuò)分代價(jià)更高的少數(shù)類(正類)傾斜，通過關(guān)注分類困難的少數(shù)類(正類)樣本來提高整體的精度.利用SMOTE人工合成實(shí)例也可以增加集合中分類器之間的多樣性，因?yàn)樵诿看蔚校a(chǎn)生了不同的合成訓(xùn)練集.

Cost-SMOTEBoost算法流程為:

(2)在每一輪迭代中都會(huì)調(diào)用一個(gè)弱分類器h(xi)進(jìn)行訓(xùn)練，并運(yùn)用SMOTE算法合成少數(shù)類(正類)實(shí)例加入訓(xùn)練集中，改善訓(xùn)練集中類別的分布.

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

3.1 數(shù)據(jù)集

實(shí)驗(yàn)是在表2中3個(gè)數(shù)據(jù)集上進(jìn)行的.這些數(shù)據(jù)來源于UCI公開數(shù)據(jù)集[12-13]. Credit-g是來自德國(guó)的信用卡數(shù)據(jù)，由一組屬性描述一個(gè)人的行為，評(píng)估每個(gè)人信用風(fēng)險(xiǎn)的高低；Seismic-bumps是采礦地震預(yù)測(cè)數(shù)據(jù)，采礦活動(dòng)經(jīng)常發(fā)生采礦威脅，這種威脅的一個(gè)特例就是在許多地下礦井經(jīng)常發(fā)生地震危險(xiǎn)，由于地震過程中低能和高能現(xiàn)象的地震事件數(shù)量之間不相稱的復(fù)雜性，導(dǎo)致統(tǒng)計(jì)技術(shù)不足以預(yù)測(cè)地震災(zāi)害.因此，有必要利用機(jī)器學(xué)習(xí)方法尋找更好的危險(xiǎn)預(yù)測(cè)方法；Thoraric Surgery是在弗羅茨瓦夫胸外科中心回顧性地收集2007—2011年期間接受肺癌切除術(shù)患者的數(shù)據(jù)，該中心與波蘭的弗羅茨瓦夫醫(yī)科大學(xué)和下西里西亞肺病研究中心的胸外科有關(guān)，研究數(shù)據(jù)庫(kù)是國(guó)立肺癌登記處的一部分.

表2 實(shí)驗(yàn)數(shù)據(jù)集
Tab.2 Dataset

數(shù)據(jù)集多數(shù)類(負(fù)類)實(shí)例數(shù)量少數(shù)類(正類)實(shí)例數(shù)量屬性數(shù)量類別Credit-gSeismic-bumpsThoraric Surgery7002 41440030017070211917222

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

圖2顯示了Cost-SMOTEBoost算法和AdaCost算法在Credit-g數(shù)據(jù)集上的對(duì)比.隨著迭代次數(shù)的增加兩個(gè)算法的精確率和召回率都有不同程度的增加，兩個(gè)算法有著接近的精確率，但是Cost-SMOTEBoost算法明顯提高了召回率，得到了更高的F-measure值.

圖2 在數(shù)據(jù)集Credit-g上的對(duì)比Fig.2 The contrast on the Credit-g dataset

圖3顯示了Cost-SMOTEBoost算法和Adacost算法在Seismic-bumps數(shù)據(jù)集上的對(duì)比.兩個(gè)算法在經(jīng)過5次迭代后精確率和召回率都趨于平穩(wěn)，同樣兩者的精確率比較接近，Cost-SMOTEBoost算法在召回率上有更好的表現(xiàn)從而得到了更高的F-measure.

圖3 在數(shù)據(jù)集Seismic-bumps上的對(duì)比Fig.3 The contrast on the dataset Seismic-bumps

圖4顯示了Cost-SMOTEBoost算法和Adacost算法在Thoraric Surgery數(shù)據(jù)集上的對(duì)比.在迭代初期兩算法的表現(xiàn)比較接近，隨著迭代次數(shù)的增加Cost-SMOTEBoost算法的精確率和召回率都超過了AdaCost算法.

圖4 在數(shù)據(jù)集Thoraric Surgery上的對(duì)比Fig.4 The contrast on the dataset Thoraric Surgery

由圖2、圖3和圖4可知，Cost-SMOTEBoost算法在3個(gè)數(shù)據(jù)集上有更高的召回率，它在不降低精確率的情況下，提高了召回率從而得到了更高的F-measure.

4 結(jié)束語

本文提出了一種基于AdaCost的集成算法——Cost-SMOTEBoost算法，該算法通過在每輪迭代前加入由SMOTE算法合成的人工實(shí)例以改變數(shù)據(jù)的分布，同時(shí)利用成本敏感函數(shù)使分類結(jié)果向更被人們關(guān)注、錯(cuò)分代價(jià)更高的正類傾斜.在實(shí)驗(yàn)中使用的數(shù)據(jù)集包含不同程度的不平衡和不同的規(guī)模，從而提供了一個(gè)多樣化的測(cè)試，以精確率(Precision)，召回率(Recall)和F-measure為度量指

標(biāo)對(duì)算法進(jìn)行評(píng)價(jià)，并與AdaCost算法進(jìn)行比較.實(shí)驗(yàn)結(jié)果表明，Cost-SMOTEBoost算法平衡了精確率和召回率，在不降低整體精確率的同時(shí)提高了針對(duì)少數(shù)類(正類)的表現(xiàn).