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

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

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

1 分類原理

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

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

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

2 S-SMO-Boost方法

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

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

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

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

(2)for i=1 to k do

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

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

end if

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

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

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

(11)end for

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

3 空間插值方法

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

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

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

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

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

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

產生虛擬樣本具體步驟：

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

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

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

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

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

(5)若 k1=5，則該少數類被認為是噪聲，不再產生虛擬樣本。

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

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

4 實驗結果及其分析

4.1 數據集

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

表1 數據集描述

4.2 實驗結果

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

分類性能評價準則采用幾何均值G-mean值與少數類的F-value值：

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

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

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

表2 數據集G-mean值比較

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

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

[2]李亞軍，劉曉霞，陳平.改進的AdaBoost算法與SVM的組合分類器[J].計算機工程與應用，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/.