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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 類不平衡問(wèn)題

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

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

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

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

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

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

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

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

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

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

1.2.1 基于聚類的欠采樣算法

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

1.2.2 SMOTE 算法

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

1.2.3 Cluster-SMOTE 算法

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

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

2 EM 聚類過(guò)采樣算法

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

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

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

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

2.1 算法描述

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

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

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

2.2 EM 算法

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

算法1EM 算法

2.3 Cluster_EM 算法

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

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

2.4 OEMC 算法

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

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

算法3OEMC 算法流程

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

輸出：過(guò)采樣后的數(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 實(shí)驗(yàn)

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

本文使用兩類真實(shí)的失衡二分類數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)：第一類數(shù)據(jù)集是Galar 等人使用的22 個(gè)小型數(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兩個(gè)大型數(shù)據(jù)集，即乳腺癌和蛋白質(zhì)同源性預(yù)測(cè)數(shù)據(jù)集，分別包含102 294 和145 751 個(gè)數(shù)據(jù)樣本以及117 和74 個(gè)特征數(shù)量，兩個(gè)數(shù)據(jù)集的不平衡比率分別約為163 和111。數(shù)據(jù)集信息描述見表1。

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

3.2 實(shí)驗(yàn)設(shè)計(jì)

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

3.2.1 評(píng)價(jià)指標(biāo)

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

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

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

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

3.2.2 分類算法

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

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

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

圖5 采樣率敏感測(cè)試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(zhǎng) 與M 列，分別代表少數(shù)類和多數(shù)類的Accuracy 指標(biāo)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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