類不平衡數(shù)據(jù)的EM 聚類過采樣算法

謝子鵬，包崇明，周麗華，王崇云，孔 兵+

1.云南大學(xué)信息學(xué)院，昆明650504

2.云南大學(xué)軟件學(xué)院，昆明650504

3.云南大學(xué)生態(tài)學(xué)與環(huán)境學(xué)院，昆明650504

分類問題幾乎出現(xiàn)在日常生活的各個方面，被認(rèn)為是人類最常執(zhí)行的決策功能。分類問題是機器學(xué)習(xí)、深度學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域不可缺失的一部分，分類任務(wù)存在于絕大多數(shù)應(yīng)用當(dāng)中，如人臉識別任務(wù)[1]、風(fēng)險管理[2]、欺詐檢測[3]、污染檢測[4]、醫(yī)學(xué)診斷[5]以及各種數(shù)據(jù)的分類任務(wù)[6-7]。只有正確地將數(shù)據(jù)分類之后，才能通過數(shù)據(jù)挖掘、數(shù)據(jù)分析等方法挖掘信息的潛在價值。

現(xiàn)有的分類算法有很多，如決策樹分類算法[8]、線性分類算法[9]、樸素貝葉斯分類算法[10]、KNN（Knearest neighbor）分類算法[11]、SVM（support vector machine）分類算法[12]等。這些算法處理平衡的二分類問題比較有效，但是對于不平衡的二分類數(shù)據(jù)集，不能很好地擬合少數(shù)類數(shù)據(jù)，導(dǎo)致所訓(xùn)練的分類器分類效果不佳[13-14]。

數(shù)據(jù)級方法[15-16]是最常用于解決類不平衡問題的方法。數(shù)據(jù)級方法通過減少多數(shù)類樣本數(shù)量或者增加少數(shù)類樣本數(shù)量來使樣本平衡[17]，直接解決類不平衡問題的根源，并且不被特定的分類模型限制[18-19]。數(shù)據(jù)級方法包括三個方向，即過采樣方法[20]、欠采樣方法以及混合方法[21-22]。其中，過采樣方法比其他數(shù)據(jù)級方法更常用，Batista 等人實驗結(jié)果表明，以ROC曲線下的面積衡量，過采樣的效果通常比欠采樣好[23]。

現(xiàn)有的數(shù)據(jù)級過采樣技術(shù)有許多，但是采樣方式大多屬于隨機采樣。SMOTE（synthetic minority over-sampling technique）過采樣算法[15]被認(rèn)為是最有影響力的數(shù)據(jù)采樣算法，SMOTE 的思想是通過在相鄰的少數(shù)類樣本之間進行隨機插值過采樣，從而平衡原始的訓(xùn)練數(shù)據(jù)。由Georgios 等人提出的Cluster-SMOTE[24]的做法是首先對整個樣本空間進行聚類，通過選取多個聚類空間中少數(shù)類樣本占比最大的空間進行過采樣，但是該方法的聚類空間數(shù)量以及對每個簇中生成新樣本的數(shù)量都無法很好確定。Han等人提出的Borderline-SMOTE[20]僅對靠近邊界線的少數(shù)實例進行過采樣。NRSBoundary-SMOTE[25]使用粗糙集理論查找邊界區(qū)域并對邊界區(qū)域中的少數(shù)實例進行過采樣。Lin等人提出較為新穎的基于Cluster的欠采樣[26]，對多數(shù)類樣本進行聚類，但是該算法將聚類數(shù)量盲目設(shè)置為少數(shù)類樣本數(shù)量，選取聚類中心作為欠采樣樣本點，在不平衡率較高的數(shù)據(jù)集上會損失大量多數(shù)類樣本點信息，該方法只適用于不平衡率較低的數(shù)據(jù)集。

為了克服過采樣的局限性，并且使過采樣得到更真實樣本點，本文使用聚類算法來代替隨機過采樣策略，提出了一種EM（expectation-maximization）聚類過采樣算法（oversampling based on EM-clustering,OEMC）。聚類算法可將空間中樣本以某種相似性劃分為同一簇，而EM 聚類可產(chǎn)生最能夠代表該簇特性的樣本，即稱為簇中心點，對少數(shù)類進行聚類，以簇中心點作為過采樣的樣本。為了避免盲目追求兩類樣本數(shù)量平衡而導(dǎo)致分類性能下降，即避免盲目采樣問題，將新增樣本點占少數(shù)類樣本的比例稱為采樣率，通過實驗選取不同的采樣率得到能夠在普遍數(shù)據(jù)集上使得分類性能最佳的采樣率。具體來說,通過對少數(shù)類樣本按照最佳采樣率，過采樣得到每個簇的中心點作為最有代表性的樣本點添加到訓(xùn)練集中，從而增加少數(shù)類樣本數(shù)量，達到降低數(shù)據(jù)不平衡率[27]的目的。

本文的主要貢獻如下：為了解決類不平衡問題,提出了一種新的數(shù)據(jù)級過采樣算法。首先，本文提出的算法采用聚類技術(shù)，通過歐氏距離衡量樣本間的相似度，選取每個聚類簇的中心點作為過采樣點，解決了樣本的重要程度不夠的問題；其次，該算法通過直接在少數(shù)類樣本空間上進行采樣，解決了SMOTE、Cluster-SMOTE 等方法對聚類空間沒有針對性的問題；最后，該算法通過對少數(shù)類樣本數(shù)量的30%進行過采樣，解決了基于Cluster聚類的欠采樣盲目追求兩類樣本數(shù)量平衡和SMOTE 等算法沒有明確采樣率的問題，并且算法具有較好的效率。

1 相關(guān)工作

1.1 類不平衡問題

實際應(yīng)用中，將多數(shù)類錯誤分類為少數(shù)類產(chǎn)生的損失與將少數(shù)類錯誤分類為多數(shù)類產(chǎn)生的損失可能會有所不同。如在醫(yī)療領(lǐng)域中，將存在疾病的患者錯誤判斷為健康的人造成的損失顯然遠大于將健康的人錯誤判斷為存在疾病造成的損失。健康的人可以視為多數(shù)類，疾病患者可以視為少數(shù)類，生活中通常關(guān)注的重點也是類不平衡問題中的少數(shù)類。如果不考慮類不平衡問題，分類學(xué)習(xí)算法構(gòu)建的模型可能會對多數(shù)類過擬合，而忽略少數(shù)類?？紤]一個失衡比例為99%的二分類數(shù)據(jù)集，其中，多數(shù)類樣本占數(shù)據(jù)集的99%，少數(shù)類樣本僅為1%。為了使錯誤率最小化，學(xué)習(xí)算法以相同的錯誤分類損失將所有樣本歸為多數(shù)類[28]，模型的分類錯誤率僅為1%。但是這顯然是沒有意義的。

在數(shù)據(jù)分布不規(guī)則的數(shù)據(jù)集中，類不平衡是其中的一種表現(xiàn)。該問題具有以下特征[29]：

（1）樣本量小：在不平衡問題中，少數(shù)類樣本往往缺失，而多數(shù)類包含大量樣本，導(dǎo)致構(gòu)建的分類器的分類結(jié)果嚴(yán)重傾向多數(shù)類。最根本的解決方案就是通過增加少數(shù)類樣本或減少多數(shù)類樣本從而降低不平衡率。

（2）類別重疊：當(dāng)屬于不同類樣本在數(shù)據(jù)空間中發(fā)生重疊時，分類器很難有效區(qū)分不同類別。如果數(shù)據(jù)沒有類別重疊問題，那么任何簡單分類器可以通過適當(dāng)?shù)膶W(xué)習(xí)達到不錯的效果，如圖1 所示。

圖1 類別重疊示例Fig.1 Example of class overlapping

（3）小分裂群：當(dāng)少數(shù)類樣本分裂狀地分布在多個特征空間中，在分類任務(wù)中，這種情況會增加問題的復(fù)雜度，如圖2 所示。

圖2 小分裂群示例Fig.2 Example of small disjuncts

類不平衡問題包含以上三種特征，這些特征也是許多真實的類不平衡數(shù)據(jù)集在樣本空間上分布的特點，通過以上二維不平衡數(shù)據(jù)分布示意圖可以類比高維數(shù)據(jù)，解決類不平衡問題的關(guān)鍵是需要考慮重采樣樣本點的空間分布的合理性。

1.2 數(shù)據(jù)級采樣方法

不平衡數(shù)據(jù)集的分類問題已經(jīng)研究了很多年，現(xiàn)有的數(shù)據(jù)級解決方式也有很多，這些方法都有各自的優(yōu)點，都解決了不同方面的相關(guān)問題。并且數(shù)據(jù)級方法的使用也更加通用，可以獨立于基本的分類器[29]。

1.2.1 基于聚類的欠采樣算法

Lin 等人提出的基于聚類的欠采樣算法是用于解決類不平衡問題的一種數(shù)據(jù)級采樣算法[26]。該方法的主要思想是，通過聚類方式對多數(shù)類樣本進行聚類，將聚類簇的數(shù)量設(shè)置為少數(shù)類樣本數(shù)量，通過選取簇的中心點作為欠采樣樣本點，以欠采樣的樣本點代替原始多數(shù)類訓(xùn)練數(shù)據(jù)，從而達到兩類樣本數(shù)量相等的目的。該方法的缺點是它盲目追求兩類樣本數(shù)量平衡，但是當(dāng)失衡率高的情況下，欠采樣會丟失大量數(shù)據(jù)信息，使得采樣點發(fā)生類別重疊與小分類群的問題。

1.2.2 SMOTE 算法

由Chawla 等人提出的綜合少數(shù)類過采樣技術(shù)（SMOTE）被認(rèn)為是最有影響力的數(shù)據(jù)過采樣算法[15]。其基本思想是在少數(shù)類樣本連線之間進行隨機插值過采樣，該算法增加了少數(shù)類樣本數(shù)量以提高分類器的性能。

1.2.3 Cluster-SMOTE 算法

由Georgios 等人提出的Cluster-SMOTE 算法是基于SMOTE 算法改進的解決類不平衡問題的數(shù)據(jù)級算法[24]。該方法的主要思想是，首先通過K-means聚類將輸入空間聚類為k個組，保留含有較多少數(shù)類樣本的簇，對這些保留的簇采取SMOTE 算法對少數(shù)類過采樣，將過采樣數(shù)據(jù)添加到訓(xùn)練集從而達到降低失衡率的目的。該方法的缺點是無法確定k的大小，k的大小直接影響過采樣的質(zhì)量，并且聚類空間沒有限制，聚類后的簇中會包含多數(shù)類樣本，這將產(chǎn)生一定程度噪聲點。

總而言之，最近有很多旨在解決類不平衡問題的數(shù)據(jù)級算法，并且取得了很多方面的成功。但是這些算法都存在自身的問題，雖然解決了類別數(shù)量不平衡問題，但是產(chǎn)生的新樣本存在類別重疊問題，以及許多技術(shù)以高復(fù)雜度的代價來解決現(xiàn)有問題，使得這些技術(shù)難以實現(xiàn)與使用[24]。

2 EM 聚類過采樣算法

本文提出基于EM聚類的過采樣算法OEMC（oversampling based on EM-clustering）。算法采用聚類技術(shù)對樣本過采樣，從而得到更有意義的樣本點。聚類過程中，過采樣得到的新樣本可視為隱變量，而最大期望算法的思想正是求解隱變量的方法，通過逐步迭代，使聚類中心點不斷調(diào)優(yōu)，最后得到最有代表性的樣本點。所提出的方法首先劃分少數(shù)類樣本空間與多數(shù)類樣本空間，然后基于OEMC 算法在少數(shù)類樣本空間生成新樣本，最后得到新的數(shù)據(jù)集。該算法包含的劃分類別空間與過采樣步驟目的在于解決上述的不平衡問題包含的三類子問題，其中劃分類別空間的目的是為了避免過采樣產(chǎn)生的樣本發(fā)生類別重疊以及小分裂群的問題，使用聚類過采樣是為了降低類別不平衡問題。

為了說明SMOTE過采樣算法、Cluster-SMOTE過采樣算法、Cluster欠采樣算法以及本文提出的EM聚類的過采樣算法解決具體的不平衡問題時的采樣合理性，列舉了四種算法的采樣效果示意圖，如圖3所示。

圖3 四種采樣算法示意圖Fig.3 Schematic diagram of four sampling algorithms

從圖3 可看出,線性插值法SMOTE 算法以及Kmeans-SMOTE 算法在某些情況產(chǎn)生的過采樣樣本點會分布于多數(shù)類樣本空間中；而基于Cluster 的欠采樣算法由于將重采樣樣本點代替原多數(shù)類樣本點，導(dǎo)致多數(shù)類與少數(shù)類樣本邊界發(fā)生偏離，產(chǎn)生類別重疊情況；而本文提出的EM 聚類過采樣算法通過對少數(shù)類樣本空間聚類，選取中心點作為過采樣點，可以很好地解決新增樣本的空間分布問題。

2.1 算法描述

EM 聚類過采樣算法主要分為以下步驟：首先將原始數(shù)據(jù)通過分層隨機采樣劃分為80%的訓(xùn)練集與20%的測試集，分層采樣可保持?jǐn)?shù)據(jù)集的不平衡率，具體的做法是分別從兩個類別中抽取各自的80%后組成訓(xùn)練集，剩余的作為測試集；然后從訓(xùn)練集按照類別標(biāo)簽劃分多數(shù)類樣本空間與少數(shù)類樣本空間；在少數(shù)類樣本空間中按照一定的采樣率用基于EM聚類算法的過采樣產(chǎn)生新樣本，采樣率需要通過實驗調(diào)整；將新樣本與訓(xùn)練集組合，得到不平衡率降低的訓(xùn)練集。OEMC 算法的數(shù)據(jù)處理流程為圖4 所示。

圖4 OEMC 算法過采樣流程Fig.4 Data oversampling procedure of OEMC

所提出的方法與之前提到的相關(guān)技術(shù)的不同之處在于，該方法不必考慮整個樣本空間，直接針對劃分類別空間后的少數(shù)類樣本空間進行過采樣。而且通過對過采樣率的調(diào)整，可以很大程度上防止算法產(chǎn)生不具代表性的樣本與噪聲點，最大程度地提高分類器對數(shù)據(jù)的泛化能力。該算法的過采樣步驟不盲目追求類別間樣本數(shù)量相近，在越高維的數(shù)據(jù)與不平衡率越高的數(shù)據(jù)集上的效果越好。

2.2 EM 算法

EM 算法又稱為期望最大化算法，該算法受到缺失思想影響，最初是為了解決數(shù)據(jù)缺失情況下的參數(shù)估計問題，其算法基礎(chǔ)和收斂有效性等問題由Dempster給出了詳細的闡述[30]。EM 算法是最常見的隱變量估計方法，在機器學(xué)習(xí)中有廣泛的用途，是一種迭代優(yōu)化策略算法。該算法的思想分為兩步，即E（期望）步與M（極大化）步。首先根據(jù)己經(jīng)給出的觀測數(shù)據(jù)，估計出模型參數(shù)的值；然后依據(jù)上一步估計出的參數(shù)值估計缺失數(shù)據(jù)的值；再根據(jù)估計出的缺失數(shù)據(jù)加上之前己經(jīng)觀測到的數(shù)據(jù)重新對參數(shù)值進行估計，反復(fù)迭代，直至最后收斂，迭代結(jié)束。

算法1EM 算法

2.3 Cluster_EM 算法

該算法采用最大期望化思想求解聚類中心點。

算法2EM 聚類算法（Cluster_EM）流程

2.4 OEMC 算法

本文提出的EM 聚類過采樣技術(shù)（OEMC）通過聚類算法增加符合真實數(shù)據(jù)分布的樣本點數(shù)量解決類不平衡問題。

式（1）與式（2）給出樣本相似度衡量的兩種方式：

算法3OEMC 算法流程

輸入：不平衡數(shù)據(jù)集D，聚類算法Cluster_EM，過采樣率OversamplingRate，隨機采樣策略stratifiedSampling，相似度衡量標(biāo)準(zhǔn)Standard=Similarity_European。

輸出：過采樣后的數(shù)據(jù)集D′。

1.data_train,data_test←stratifiedSampling(D)

2.minority,majority←Classify(data_train)

3.k←OversamplingRate×Num(minority)

4.while average_similarity(minority,K_center)＞0.8 do

5.K_center←initializeCenter(minority,k)

6.K_center←Cluster_EM(minority,k,Standard)

7.end while

8.D′←D+K_center

9.end

3 實驗

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

本文使用兩類真實的失衡二分類數(shù)據(jù)集進行實驗：第一類數(shù)據(jù)集是Galar 等人使用的22 個小型數(shù)據(jù)集[29]，這些數(shù)據(jù)集的不平衡比率（多數(shù)類樣本數(shù)量與少數(shù)類樣本數(shù)量的比值）在1.8～129，數(shù)據(jù)的特征數(shù)量在3～19，采集的數(shù)據(jù)樣本數(shù)量在130～5 500；第二類數(shù)據(jù)集使用了Knowledge Discovery 和Data Mining Cup兩個大型數(shù)據(jù)集，即乳腺癌和蛋白質(zhì)同源性預(yù)測數(shù)據(jù)集，分別包含102 294 和145 751 個數(shù)據(jù)樣本以及117 和74 個特征數(shù)量，兩個數(shù)據(jù)集的不平衡比率分別約為163 和111。數(shù)據(jù)集信息描述見表1。

表1 數(shù)據(jù)集信息Table 1 Dataset information

3.2 實驗設(shè)計

為了證明本文算法的有效性，將本文算法與目前現(xiàn)有的3 種解決不平衡數(shù)據(jù)集的算法進行比較。針對24 個數(shù)據(jù)集，采用原始數(shù)據(jù)集、基于聚類的欠采樣、SMOTE 算法、Cluster-SMOTE 算法和EM 聚類過采樣算法分別處理的數(shù)據(jù)集作為實驗數(shù)據(jù)集，在C4.5 決策樹算法上進行分類性能實驗。為了減小實驗誤差，體現(xiàn)算法的真實性能，采用5 折交叉驗證將所有數(shù)據(jù)集分為80%的訓(xùn)練集和20%的測試集，所有實驗進行10 次實驗后取平均值。

3.2.1 評價指標(biāo)

傳統(tǒng)分類通常用分類精度作為衡量算法有效性的指標(biāo)，但分類精度可以反映分類器整體的分類效果，而不能反映少數(shù)類的分類精度。不平衡數(shù)據(jù)集中，少數(shù)類別的識別精度通常更為重要，因此分類精度不適用于不平衡數(shù)據(jù)。針對不平衡數(shù)據(jù)集的分類性能評估，目前尚沒有公認(rèn)的度量標(biāo)準(zhǔn)。而且，選擇不同的評估指標(biāo)，可以觀察到非常不同的結(jié)果。

混淆矩陣又稱為誤差矩陣，是用于計算精度的工具，其中記錄了每個類被正確和錯誤識別的數(shù)量，混淆矩陣在分類任務(wù)中被廣泛使用，在各種不平衡數(shù)據(jù)集實驗中都被采用[29]，可以更有意義地對實驗結(jié)果進行評價?；煜仃嚾绫? 所示。

表2 二分類混淆矩陣Table 2 Confusion matrix of binary classification

表2 中，TP 為正確分類的正樣本數(shù)量，TN 為正確分類的負樣本數(shù)量，F(xiàn)P 為分類錯誤的正樣本數(shù)量，F(xiàn)N 為錯誤分類的負樣本數(shù)量?；谝陨隙x，可以定義幾個基本性能指標(biāo)。

3.2.2 分類算法

為了評估過采樣算法，需要選擇分類算法來構(gòu)建分類器，以確保該算法的有效性。通過構(gòu)建機器學(xué)習(xí)分類模型，驗證模型對數(shù)據(jù)的擬合能力。本研究選擇被廣泛用于處理不平衡數(shù)據(jù)的C4.5 決策樹作為分類器[31-32]，原因如下：首先，決策樹模型經(jīng)常被作為驗證分類結(jié)果的首選模型，決策樹模型具有良好的數(shù)據(jù)泛化能力和快速的訓(xùn)練速度，并且決策樹模型可作為基線分類模型；其次，上文已經(jīng)提到數(shù)據(jù)級的分類方法不受限于具體的分類模型；最后，在Georgios等人[24]、Lin 等人[26]的相關(guān)實驗中都使用了決策樹模型。

3.3 實驗結(jié)果與分析

為了選擇適合普遍數(shù)據(jù)集的最佳采樣率，實驗選取一個不平衡率為111.46 的大型數(shù)據(jù)集和4 個不平衡率分別為10.29、8.11、5.46、1.90 的小型數(shù)據(jù)集代表不同程度的不平衡數(shù)據(jù)集，用本文提出的OEMC算法進行不同采樣率下的分類性能敏感測試。不同采樣率下的各個數(shù)據(jù)集的分類性能變化如圖5 所示，從中可看出，0.30 的采樣率在各個不平衡程度的數(shù)據(jù)集上效果都較優(yōu)，因此本文選取30%的采樣率作為適合OEMC 算法的最佳采樣率。

圖5 采樣率敏感測試Fig.5 Sampling rate sensitivity test

表3 顯示了使用原始不處理的數(shù)據(jù)、基于聚類的欠采樣算法處理的數(shù)據(jù)集、SMOTE 算法處理的數(shù)據(jù)集、K-means-SMOTE 算法處理的數(shù)據(jù)集以及本文提出的OEMC 算法處理的數(shù)據(jù)集在C4.5 分類器下的分類性能。表中精確度Accuracy 分為L 與M 列，分別代表少數(shù)類和多數(shù)類的Accuracy 指標(biāo)。

從表3 可看出，本文提出的OEMC 算法與C4.5分類器結(jié)合在22 個數(shù)據(jù)集上都取得了最佳表現(xiàn)，特別是對少數(shù)類Accuracy 指標(biāo)的提升明顯超過3 種現(xiàn)有采樣方法。該結(jié)果可以驗證EM 聚類過采樣算法可以增加少數(shù)類樣本數(shù)量，從根本上解決類不平衡問題。通過結(jié)果可以看出，以歐氏距離作為樣本相似度衡量標(biāo)準(zhǔn)的EM 算法產(chǎn)生了更有意義的樣本點，并且證明了EM 聚類過采樣算法對多種數(shù)據(jù)的普遍適用性，該方法可以有效解決數(shù)據(jù)不平衡帶來的分類器性能低下的問題。

表3 C4.5 分類器與5 種數(shù)據(jù)處理方式結(jié)合的分類性能Table 3 Classification performance of five approaches with C4.5

圖6 是5 種重采樣方法在5 個小型數(shù)據(jù)集上的平均精確率的表現(xiàn)，平均精確率可反映分類器對數(shù)據(jù)的整體分類性能。Glass1、Yeast3 等5 種小型數(shù)據(jù)集是從上文提到的22 種小型數(shù)據(jù)集中按照不平衡率依次遞減選取的有代表性的5 個數(shù)據(jù)集，每個數(shù)據(jù)集上統(tǒng)計了5 種方法的平均精確度。

從圖6 可以看出，本文提出的EM 聚類過采樣算法（oversampling based on EM-clustering）在5 個不平衡率依次遞減的小型數(shù)據(jù)集上的表現(xiàn)最佳，并且獲得的分?jǐn)?shù)均在0.8 以上，同樣采用了聚類方法的Kmeans-SMOTE 方法在小型數(shù)據(jù)集上的表現(xiàn)同樣理想，再次證明了聚類方法對生成采樣點有重要作用。

圖6 5 種方法在5 個代表性小型數(shù)據(jù)集上的分類精確率Fig.6 Classification accuracy of five methods on five representative small datasets

圖7 顯示了對應(yīng)上述表格中的5 種數(shù)據(jù)重采樣方式在兩個大型數(shù)據(jù)集上的實驗結(jié)果，其中包含未處理的數(shù)據(jù)集（UD）、基于聚類的欠采樣（UC）、SMOTE、K-means-SMOTE（KS）以及本文提出的OEMC 算法處理的數(shù)據(jù)與決策樹分類器相結(jié)合在分類中得到的兩個類別的精確率。

圖7 5 種方法在兩個大型數(shù)據(jù)集上的分類精確率Fig.7 Classification accuracy of five methods on two large datasets

從圖7 可以看出，本文提出的EM 聚類過采樣算法在平均精確率方面取得了最佳表現(xiàn)。從圖中看出，基于聚類的欠采樣以及SMOTE 算法過采樣在蛋白質(zhì)同源性預(yù)測數(shù)據(jù)集上都會導(dǎo)致類別重疊問題，類別邊界偏移使得兩類別特征模糊，最終分類器的性能下降。同樣結(jié)合了聚類方法的K-means-SMOTE過采樣算法在蛋白質(zhì)同源性預(yù)測數(shù)據(jù)集上的精確率與本文算法的精確率相近。從圖中可看出，K-means-SMOTE 算法在乳腺癌數(shù)據(jù)集上的精確率也僅略低于本文算法。因此將聚類方法結(jié)合到過采樣算法中是十分重要的。

圖8 比較了5 種重采樣方法在兩個大型數(shù)據(jù)集上的時間消耗實驗結(jié)果。

圖8 5 種方法在兩個大型數(shù)據(jù)集上的時間消耗Fig.8 Time consumption of five methods on two large datasets

從圖8 可看出，由于本文提出的OEMC 算法設(shè)定的30%采樣率，在時間消耗上僅次于未經(jīng)數(shù)據(jù)重采樣的方法，該結(jié)果表明選取最佳采樣率不僅利于分類性能的提升，并且可以有效降低時間消耗。OEMC 的時間復(fù)雜度為O(m×n×d×e)，其中m為過采樣數(shù)量，n為少數(shù)類樣本數(shù)量，d為數(shù)據(jù)維度，e為算法迭代次數(shù)。

4 結(jié)束語

當(dāng)今數(shù)據(jù)不平衡問題給許多領(lǐng)域帶來了困難，給許多分類算法帶來了困難。

首先，對訓(xùn)練數(shù)據(jù)進行過采樣以使其分布更均勻是在數(shù)據(jù)處理級別解決此問題的有效方法。一方面，隨機過采樣會導(dǎo)致過度擬合，從而降低模型在不可見數(shù)據(jù)上的分類性能；另一方面，如果不控制所生成的數(shù)據(jù),則經(jīng)常會生成帶有噪聲的樣本，這會模糊樣本邊界并阻礙樣本類型的確定。本文方法使用EM 聚類算法對初始少數(shù)類樣本進行聚類，可以使得過采樣樣本點分布均勻，并能代表原始數(shù)據(jù)信息，可以防止由于過采樣階段中存在噪聲樣本而導(dǎo)致引入新的噪聲。生成新樣本時，根據(jù)采樣率生成相應(yīng)數(shù)量的少數(shù)類別樣本。因為每個新生成的樣本都與原始的少數(shù)類樣本相關(guān)，所以不會生成異常值。

其次，在不平衡數(shù)據(jù)集的分類問題下，不平衡數(shù)據(jù)集不同類別的樣本數(shù)量失衡比例過高，導(dǎo)致對分類器的訓(xùn)練過程中對少數(shù)類的擬合能力太差，對少數(shù)類的預(yù)測準(zhǔn)確率低。本文方法可以降低不同類別樣本數(shù)量的失衡比例，使得構(gòu)造的分類器分類性能在24 個數(shù)據(jù)集上表現(xiàn)良好。

今后可以考慮兩個問題：首先，由于原始數(shù)據(jù)存在噪聲，多余的噪聲導(dǎo)致分類器的性能不佳，今后可對本文提出的EM 聚類過采樣算法的步驟中增加去噪步驟，例如通過支持向量機對初始數(shù)據(jù)進行去噪和初步分類。其次，可采取不同相似度衡量標(biāo)準(zhǔn)。采用不同的相似空間對數(shù)據(jù)過采樣產(chǎn)生的結(jié)果會有明顯差別。