一種改進的少數(shù)類樣本識別方法

董 璇，蔡立軍（西北工業(yè)大學(xué) 理學(xué)院，陜西 西安710129）

非均衡數(shù)據(jù)集的分類問題是模式識別和機器學(xué)習(xí)的研究熱點。所謂非均衡數(shù)據(jù)集是指數(shù)據(jù)集合中，某些類的數(shù)據(jù)樣本較多，而其他類數(shù)據(jù)樣本較少[1]。樣本較少的為少數(shù)類，樣本較多的為多數(shù)類。非均衡數(shù)據(jù)集分類問題可應(yīng)用于風(fēng)險管理、網(wǎng)絡(luò)入侵檢測、銀行預(yù)測、醫(yī)療診斷等領(lǐng)域。例如，醫(yī)生疾病診斷中錯將癌癥病人診斷為正常人，損失會很大。這種情況下少數(shù)類樣本卻是人們更加關(guān)注的。針對該特點，傳統(tǒng)的分類算法不再適用，有必要尋求好的分類方法使其在類別不均衡條件下，提高對少數(shù)類的識別率。

目前，解決非均衡數(shù)據(jù)集分類問題主要通過兩種途徑：算法層面方法和數(shù)據(jù)層面方法。算法層面方法主要是對已有分類算法進行改進或提出新的算法，如李亞軍等[2]提出的改進的Adaboost算法與SVM的組合分類器。數(shù)據(jù)層面的解決辦法有欠抽樣方法，隨機去掉部分多數(shù)類樣本使不同類別樣本數(shù)量均衡，此方法缺點是丟失了多數(shù)類的一些重要信息，造成分類性能降低。改進的欠抽樣方法有托梅克聯(lián)系對（Tomek Link）[3]方法、壓縮最近鄰法（CNN）[4]。簡單的過抽樣方法隨機復(fù)制少數(shù)類樣本的缺點是易導(dǎo)致過學(xué)習(xí)。Chawla等[5]提出了SMOTE（Synthetic Minority Over-sampling Technique）方法，人工合成少數(shù)類樣本，但是生成樣本范圍受到極大限制。本文提出了S-SMO-Boost方法，利用Adaboost提升算法，每次迭代不僅僅增大錯分樣本權(quán)值，還從迭代過程中抽取錯分少數(shù)類樣本，并對該部分樣本進行過抽樣，過抽樣過程采用SMOTE的改進方法——空間插值法，增強對錯分少數(shù)類樣本的訓(xùn)練，以訓(xùn)練出一個強分類器，提高分類性能。

1 分類原理

對于含有兩個不同類的數(shù)據(jù)集(多類可化為兩類)S={(X1，y1)，(X2，y2)， … ，(Xm，ym)}，每 個 數(shù) 據(jù) 元 組 Xi(0≤i≤m)用 n 維屬性向量 Xi={xi1，xi2，…，xin}表示，yi∈Y={1，0}為Xi的類標(biāo)號，即數(shù)據(jù)元組所屬類別。對數(shù)據(jù)集進行分類即將數(shù)據(jù)集分為訓(xùn)練集和檢驗集，分類原理如圖1所示。

對于兩類非均衡類數(shù)據(jù)集 S=P∪N，|P|=np，|N|=nN，設(shè) nN=λnp，λ 為非均衡率，λ>1且 λ∈Q+。 圖 2為一個非均衡數(shù)據(jù)集樣本分布情況。

訓(xùn)練集為數(shù)據(jù)集中抽取的樣本，由于訓(xùn)練集中兩類樣本數(shù)量同樣相差極大，訓(xùn)練分類算法得到的分類器分類結(jié)果向多數(shù)類偏斜，故對測試集進行分類時，少數(shù)類樣本識別率較低。本文提出S-SMO-Boost方法。

2 S-SMO-Boost方法

Adaboost是一種流行的提升算法，利用樣本的權(quán)值來確定訓(xùn)練集的抽樣分布。 令 S={(Xj，yj)|j=1，2，…，m}表示包含m個訓(xùn)練樣本的集合，初始時所有樣本權(quán)值均為1/m，根據(jù)訓(xùn)練樣本的抽樣分布來抽取樣本，得到新的樣本集，由該訓(xùn)練集訓(xùn)練一個分類器，對原數(shù)據(jù)集樣本進行分類。每一輪迭代結(jié)束時更新訓(xùn)練樣本的權(quán)值，增加錯誤分類樣本權(quán)值，減少正確分類樣本權(quán)值。使分類器在隨后迭代中關(guān)注那些很難分類的樣本。算法中基分類器Ci的重要性依賴于它的錯誤率。組合分類器的最終結(jié)果通過取每個基分類器預(yù)測的加權(quán)平均得到。但是，由于少數(shù)類樣本與多數(shù)類樣本數(shù)量相差較大，即使增大錯分少數(shù)類樣本的權(quán)值，抽取的少數(shù)類樣本仍然很少。利用S-SMO-Boost方法，在每次迭代中，記錄錯分少數(shù)類樣本，利用空間插值法（S-SMOTE）在其周圍產(chǎn)生相似的少數(shù)類樣本，加入訓(xùn)練集中，進入下次迭代，訓(xùn)練分類器，有針對性地加強了對錯分少數(shù)類樣本的訓(xùn)練，提高了少數(shù)類樣本的識別率。

S-SMO-Boost方法具體算法如下：

輸入： 訓(xùn)練集 S={(xj，yj)|j=1，2， …，m}， 其中 yj∈(1，0)，k 表示迭代次數(shù)。

(1)初始化權(quán)值 w={wj=1/m|j=1，2，…，m}。

(2)for i=1 to k do

(3)根據(jù) w，通過對 S進行抽樣（有放回），產(chǎn)生訓(xùn)練集 Si。用Si訓(xùn)練基分類器 Ci，用 Ci對原訓(xùn)練集S中所有樣本分類。

(5)if εi>0.5， 重 設(shè) 樣 本 權(quán) 值 ，w={wj=1/m|j=1，2，…，m}，返回步驟(4)。

end if

(6)對于 xj，if yj=1，而 Ci(xj)=0，則記錄 xj。

(7)對其利用空間插值方法，產(chǎn)生虛擬樣本 syn′i∈Pcreat。

(10)將 Pcreat歸入訓(xùn)練集 S。

(11)end for

上述算法中，步驟(6)～(7)對迭代過程中錯分的少數(shù)類利用空間插值法進行過抽樣，在其鄰域空間內(nèi)產(chǎn)生類似有效少數(shù)類樣本；步驟（10）將虛擬樣本加入訓(xùn)練集，同樣加大了少數(shù)類被抽到的概率，加強了對易錯分少數(shù)類樣本的訓(xùn)練，降低了數(shù)據(jù)集的非均衡程度，有效提高了非均衡數(shù)據(jù)集的分類性能，其有效性將在實驗中得到驗證。

3 空間插值方法

SMOTE方法是一種過抽樣方法，該方法在少數(shù)類p與其同類k（k=5）近鄰p′之間的連線上人工合成少數(shù)類樣 本 pnew=p+random(0，1)×(p′-p)，其 中 random（0，1）是介于0與1之間的隨機數(shù)。根據(jù)需要循環(huán)以上過程生成更多新的虛擬樣本，避免了過度擬合問題。

其缺點是：(1)沒有針對性，對于分類正確的少數(shù)類樣本，同樣產(chǎn)生虛擬樣本，增加了分類成本；(2)生成樣本僅介于少數(shù)類樣本之間的連線上，限制了生成范圍，不符合真實數(shù)據(jù)分布情況，有一定局限性。

空間插值法S-SMOTE(Space Synthetic Minority Oversampling Technique)對SMOTE方法中少數(shù)類樣本的生成范圍進行了改進。設(shè)數(shù)據(jù)集中少數(shù)類樣本集為P={(p1，1)，(p2，1)， … ，(pi，1)}(0≤i≤np)，pi為 P 中 樣 本 元組；多數(shù)類樣本集為 N={(n1，0)，(n2，0)，…，(nj，0)}（0≤j≤nN），1 和 0 分別為少數(shù)類和多數(shù)類標(biāo)號。nN=λ np(λ>1且 λ∈Q+)。

空間插值法的基本思想如下：

(1)對少數(shù)類樣本 pi，利用歐式空間距離公式求其 k（k=5）近鄰。

(2)利用該少數(shù)類及其k近鄰構(gòu)造超幾何體（三維空間中為四面體），在該超幾何體內(nèi)隨機插值，產(chǎn)生虛擬少數(shù)類樣本，相比SMOTE方法，生成樣本范圍變大。對于存在多數(shù)類近鄰的少數(shù)類，更容易被錯分，故在分類過程中貢獻較大，因此構(gòu)造部分邊界虛擬少數(shù)類樣本。圖3表示利用空間插值法在超幾何體內(nèi)隨機產(chǎn)生虛擬少數(shù)類樣本。

產(chǎn)生虛擬樣本具體步驟：

(1)求少數(shù)類樣本 pi的 k近鄰，設(shè) k1為其 k近鄰中多數(shù)類樣本個數(shù)。

(2)若k1=0，則從 k近鄰中隨機取 4個設(shè)為pi1、pi2、pi3、pi4構(gòu)成一個四面體，如圖4(左)所示。據(jù)式(1)～式(3)構(gòu)造四 面體 內(nèi)部樣 本，syn′inew=(syni1，syni2，… ，synin)∈Pcreat

其中，r1，r2，r3∈(0，1)。

(3)若k1=1，則將該多數(shù)類樣本看作噪聲去除，從剩余近鄰中選取3個與pi構(gòu)成超幾何體產(chǎn)生虛擬樣本sy∈Pcreat。

(4)若 2≤k1≤4，則從其 k近鄰中隨機選取 3個與 pi構(gòu)成超幾何體，pi為頂點，如圖 4（右）所示，sy=pi+r3×(bi-pi)∈Pcreat，集中于pi為頂點等比縮小的幾何體內(nèi)。

(5)若 k1=5，則該少數(shù)類被認(rèn)為是噪聲，不再產(chǎn)生虛擬樣本。

(6)記錄|Pcreat|，循環(huán)此過程直至產(chǎn)生所需虛擬樣本數(shù)量。

步驟(2)中，少數(shù)類pi的k近鄰均為少數(shù)類，構(gòu)造超幾何體 G1(如圖3所示)，G1內(nèi)隨機虛擬樣本以該少數(shù)類樣本及其k近鄰為近鄰，則根據(jù)K-NN算法思想，近鄰多為少數(shù)類的樣本屬于少數(shù)類的概率很大，故可歸入少數(shù)類樣本集 S中。步驟（3）、（4）中，k近鄰中存在多數(shù)類樣本時，當(dāng)產(chǎn)生的虛擬樣本靠近多數(shù)類時，根據(jù)最近鄰思想，則其可能屬于多數(shù)類，故構(gòu)造超幾何體 G2、G3(如圖3所示)，將生成樣本范圍控制在以pi為頂點的等比縮小的幾何體內(nèi)，使生成樣本更靠近少數(shù)類樣本，提高了生成樣本的質(zhì)量，避免噪聲產(chǎn)生。所以空間插值的方法能生成有效的虛擬少數(shù)類樣本。

4 實驗結(jié)果及其分析

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

實 驗 采 用 Haberma、Pima Indians、Wisconsin-breastcancer、Machine 4個公開數(shù)據(jù)集，它們均選自 UCI機器學(xué)習(xí)數(shù)據(jù)庫[6]。4個數(shù)據(jù)集除Machine外均為兩類非均衡數(shù)據(jù)集，對 Machine數(shù)據(jù)集選取類標(biāo)為“3”的一類作為少數(shù)類，將其余類別合并為多數(shù)類。表1為4個數(shù)據(jù)集的基本信息。

表1 數(shù)據(jù)集描述

4.2 實驗結(jié)果

仿真實驗在CPU雙核2.80 GHz、內(nèi)存2 GB的PC機上進行，將S-SMO-Boost方法分別與單獨使用S-SMOTE、SMOTE、J48方法進行比較，均以 J48為基分類器，并采用十折交叉驗證法。其中，S-SMOTE方法處理數(shù)據(jù)時，循環(huán)其構(gòu)造樣本的過程直至|Pcreat|=nN-nP=(λ-1)nP。 則Pcreat、P與剩余多數(shù)類樣本集合并為均衡數(shù)據(jù)集訓(xùn)練分類器。

分類性能評價準(zhǔn)則采用幾何均值G-mean值與少數(shù)類的F-value值：

其中，TP與TN分別表示正確分類的少數(shù)類與多數(shù)類數(shù)量，F(xiàn)P與FN分別表示錯分為少數(shù)類與多數(shù)類的樣本數(shù)量。G-mean值中 TP/(TP+TN)指少數(shù)類精確度，TN/(TN+FP)指多數(shù)類精確度，只有兩者的值都大時，幾何均值才會大，因此幾何均值能合理地評價非均衡數(shù)據(jù)集的整體分類性能。F-value值中 Recall=TP/(TP+FN)與Precision=TP/(TP+FP)分別表示少數(shù)類查全率和查準(zhǔn)率，兩者值都大時F-value值才會大，因此F-value值能正確反映少數(shù)類的分類性能。

圖5表示分別用四種方法對4個數(shù)據(jù)集分類時得到的少數(shù)類F-value值。同種方法得到的F-value值點用線連起可清晰顯示，利用S-SMO-Boost方法得到的F-value值相比其他方法均有一定程度的提高。

表2對不同方法，分別比較了4個數(shù)據(jù)集的G-mean值，由實驗結(jié)果可知，直接用J48進行分類得到的值最小，因為數(shù)據(jù)集嚴(yán)重不均衡。相比SMOTE方法，SSMOTE在少數(shù)類鄰域空間內(nèi)插值產(chǎn)生有效虛擬樣本，并加強靠近邊界少數(shù)類樣本的訓(xùn)練，故分類性能相對較好。S-SMO-Boost將空間插值法融入提升算法，在迭代過程中利用錯分樣本產(chǎn)生虛擬樣本，增強對錯分少數(shù)類樣本的訓(xùn)練，且增大錯分樣本的權(quán)值，加大迭代中作訓(xùn)練集的概率，并將弱分類器組合成強分類器。由表2知，用S-SMO-Boost方法得到的G-mean值最大，提高了非均衡數(shù)據(jù)集的整體分類性能。

表2 數(shù)據(jù)集G-mean值比較

為了解決非均衡數(shù)據(jù)集中少數(shù)類識別率較低的問題，本文提出了S-SMO-Boost方法，利用空間插值方法，產(chǎn)生有效虛擬樣本，并將其與提升算法融合，加強對錯分少數(shù)類樣本的訓(xùn)練。經(jīng)實驗驗證，該方法提高了少數(shù)類識別率和數(shù)據(jù)集整體分類性能。

[1]WEISS G.Mining with rarity：an unifying framework[J].Sigkdd Explorations，2004，6(7)：7-19.

[2]李亞軍，劉曉霞，陳平.改進的AdaBoost算法與SVM的組合分類器[J].計算機工程與應(yīng)用，2008，44(32)：140-142.

[3]TOMEK I.Two modi-cations of CNN[J].IEEE Transactions on Systems Man and Communications，1976，SMC-6：769-772.

[4]MANNILA，LIU，MOTODA.Adavances in instance selection for instance-based leaning algorithms[J].Data Mining and Knowledge Discovery，2002(6)：153-172.

[5]CHAWLA N，BOWYER K，HALL L，et al.SMOTE：synthetic minority over-sampling echnique[J].Journal of Artificial Intelligence Research，2002(16)：321-357.

[6]BLAKE C，MERZ C.UCI repository of machine learning databases[DB/OL].1998.http：//archive.ics.uci.edu/ml/.