董宏成，趙學(xué)華，趙 成，劉 穎，解如風(fēng)

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶市質(zhì)量和標(biāo)準(zhǔn)化研究院，重慶 400023；3.重慶信科設(shè)計有限公司，重慶 401121)

0 引 言

近年來有很多旨在改善不平衡學(xué)習(xí)問題[1-5]的研究，如隨機過采樣Random Oversampling[6]是隨機復(fù)制少數(shù)類樣本使類分布達(dá)到平衡，該方法可有效提高分類器的分類性能，但容易導(dǎo)致過擬合。José等提出了一種改進型的SMOTE過采樣方法[7]，該方法簡單有效但其合成樣本機制是盲目的。Annisa等采用一種改進型的自適應(yīng)過采樣方法ADNSYN[8]來重新平衡數(shù)據(jù)集。該算法雖然可有效提升分類器的分類性能，但忽略了類內(nèi)不平衡問題。為了解決類內(nèi)不平衡，Georgios等[9]提出一種K-SMOTE算法，該算法采用K-means聚類方法先對整個輸入空間進行聚類，然后對過濾的集群進行隨機過采樣。該方法可同時解決類間和類內(nèi)不平衡問題，但其無法加強分類器對一些重要少數(shù)類樣本的學(xué)習(xí)。

綜上所述，雖然大多數(shù)算法都能克服現(xiàn)有過采樣算法的一些缺點，但很少有算法能夠避免產(chǎn)生噪聲并同時減輕類間和類內(nèi)不平衡問題。此外，許多技術(shù)都是比較盲目地合成新的樣本，并不能根據(jù)數(shù)據(jù)的分布特征進行合理的抽樣處理。因此，本文提出一種自適應(yīng)過采樣方法HD-SMOTE，該方法旨在更加合理地解決不平衡數(shù)據(jù)中的噪聲、內(nèi)類和類間不平衡等問題。

1 HDBSCAN聚類和SMOTE過采樣算法

1.1 HDBSCAN聚類

HDBSCAN[10]是由Campello等開發(fā)的一種基于密度的聚類算法，它是DBSCAN聚類方法的一種變體。該算法會執(zhí)行不同半徑Eps值的DBSCAN，并集成所有結(jié)果以找到最佳的聚類解決方案。在聚類過程中，HDBSCAN首先根據(jù)密度對數(shù)據(jù)空間進行變換，求出所有樣本點的最小生成樹，然后對變換后的空間進行單連鎖聚類。HDBSCAN不以單個Eps值作為樹狀圖的分割線，而是在不同高度對樹進行切割，根據(jù)集群的穩(wěn)定性選擇不同密度的集群。

HDBSCAN聚類方法相比K-means、均值漂移、層次聚類、DBSCAN等聚類方法有以下幾點優(yōu)勢：①可以發(fā)現(xiàn)任意形狀和不同密度的集群；②不用預(yù)先知道數(shù)據(jù)集的聚類數(shù)量和聚類中心；③對用戶所設(shè)定的參數(shù)不敏感，其主要涉及的參數(shù)是min_cluster_size(集群的最小數(shù)量)和min_samples(集群中樣本的最小數(shù)量);④可以為每個樣本分配一個0.0到1.0的集群成員隸屬度，若樣本點的隸屬度為0.0表示該點為離群點或者噪聲樣本，而隸屬度為1.0則表示集群中心的樣本。

1.2 SMOTE過采樣方法

(1)

但是，在很多情況下，基于k-NN的方法可能會產(chǎn)生錯誤的少數(shù)類樣本，為了說明原因考慮圖1合成樣本的情況。

圖1 類內(nèi)不平衡下SMOTE合成樣本

圖1展示了在類內(nèi)不平衡和小分離(缺乏代表樣本，如集群C2)的情況下，SMOTE過采樣技術(shù)合成樣本的示意圖，其中星型表示多數(shù)類樣本，圓型表示少數(shù)類樣本。這里假設(shè)樣本A被選中且參數(shù)k=5，在A的5個少數(shù)類最近鄰中樣本B被選中，根據(jù)式(1)在樣本A和B之間插值合成新的樣本P。從圖中明顯可以看出，樣本P是一個錯誤的樣本，因為該樣本和多數(shù)類樣本重疊。若少數(shù)類樣本中出現(xiàn)小規(guī)模的集群時，上述問題將被放大。如果集群C2中的一個樣本被選中而該樣本的一個近鄰樣本C(樣本C分布在集群C3中)被選中，這時合成的樣本R將分布在多數(shù)類樣本中，這會使學(xué)習(xí)變得困難。若噪聲樣本D被選中用來合成樣本，這種情況下將合成樣本Q，若樣本Q位于多數(shù)類區(qū)域?qū)⒓哟蠓诸惼鞯膶W(xué)習(xí)難度。SMOTE方法雖然可以有效地解決類之間的不平衡問題，但是類內(nèi)部的不平衡、小分離物、噪聲等問題都被忽略了。由于該方法選擇的樣本是隨機的，這可能使樣本空間中比較密集的區(qū)域中的樣本進一步增多如集群C1，而比較稀疏的區(qū)域可能仍然保持稀疏如集群C2和C3。在這種情況下會放大不平衡數(shù)據(jù)的類內(nèi)不平衡問題，增加分類器的學(xué)習(xí)難度。

2 HD-SMOTE自適應(yīng)過采樣算法

2.1 HD-SMOTE框架

為了克服1.2節(jié)中所探討的SMOTE過采樣方法的諸多缺陷，本文提出一種基于HDBSCAN聚類和SMOTE的HD-SMOTE過采樣算法，HD-SMOTE算法框架如圖2所示。首先利用HDBSCAN聚類算法對所有少數(shù)類樣本D+進行聚類，得到m個互不相交且不同規(guī)模的集群cm和噪聲集群N，這些噪聲樣本在下一步將被刪除。隨后HD-SMOTE算法根據(jù)每個集群cm的稀疏度合成新的樣本，在稀疏度越高的集群合成更多的少數(shù)類樣本，相應(yīng)地在密集集群中合成較少的樣本，以此克服數(shù)據(jù)的類內(nèi)不平衡和小分離問題。在合成樣本時，會選擇集群中隸屬度高的樣本進行插值合成新的樣本，這樣合成的樣本會靠近每個集群中心，可以保證新的樣本點在安全區(qū)域合成，避免噪聲的產(chǎn)生。

圖2 HD-SMOTE過采樣框架

2.2 改進的SMOTE過采樣方法

為了確定每個集群需要合成的樣本數(shù)量，給每個集群分配一個0到1之間的采樣權(quán)重。采樣權(quán)重越高的表示集群越稀疏，相應(yīng)的集群合成的樣本數(shù)更多；采樣權(quán)重越小的表示集群越稠密，相應(yīng)的集群合成較少的樣本。為了確定每個集群的采樣權(quán)重與合成的樣本數(shù)目可以根據(jù)下面的步驟進行計算。

步驟1 對于每個集群f的歐式距離矩陣

(2)

其中，Dk為每個少數(shù)類集群ck的歐式距離矩陣，1≤k≤m，dij表示集群中少數(shù)類樣本xi到xj的歐式距離。

步驟2 計算每個集群ck的平均距離

(3)

其中，n為每個集群的樣本總個數(shù)，這里只需要用到距離矩陣Dk中的下對角線元素，因為dij和dji表示的距離是一樣的。

步驟3 計算每個集群ck的稀疏度

(4)

n為集群的總樣本數(shù)，從式(4)中可以發(fā)現(xiàn)，若集群的平均距離越小(集群中樣本越密集)，其對應(yīng)的稀疏度就越小，反之則越大。

步驟4 計算所有集群的稀疏度之和Sparsitysum

(5)

其中，numf表示集群的數(shù)量。

步驟5 計算每個集群的采樣權(quán)重

(6)

從式(6)中可以發(fā)現(xiàn)，若集群的稀疏度越大其采樣權(quán)重越大。

步驟6 計算要合成的樣本總數(shù)

N=Nmaj-Nmin

(7)

其中，Nmaj為多數(shù)類樣本數(shù)，Nmin為少數(shù)類樣本數(shù)。

步驟7 計算每個集群要合成的樣本數(shù)

Samples(ck)=N×Sampleweight(ck)

(8)

2.3 HD-SMOTE的算法描述

假設(shè)整個訓(xùn)練數(shù)據(jù)集為T，少數(shù)類集合為P，多數(shù)類集合為N，P={p1,p2,…,ppnum}，N={n1,n2,…nnnum}，其中pnum和nnum分別是少數(shù)類樣本數(shù)量和多數(shù)類樣本數(shù)量。整個算法的流程主要分為4個階段，具體步驟如下：

步驟1 識別少數(shù)類中不同規(guī)模的集群。

(1)HDBCAN對數(shù)據(jù)集P進行聚類，得到不同規(guī)模的集群c1,c2,…,cm和噪聲集群N，并且得到每個集群的成員隸屬度矩陣wij，0

(2)刪除噪聲集群N，計算剩余少數(shù)類樣本總數(shù)，Nmin=pnum-|N|。

步驟2 計算每個集群需要合成的樣本數(shù)Samples(ck)。

(1)遍歷所有的集群c1,c2,…,cm，根據(jù)式(2)、式(3)、式(4)計算出每個集群的稀疏度Sparsity(ck)。

(2)根據(jù)式(4)、式(5)計算所有集群的稀疏度之和Sparsitysum。

(3)根據(jù)式(6)計算每個集群ck的采樣權(quán)重Samplingweight(ck)。

(4)根據(jù)式(7)、式(8)計算每個集群ck需要的合成的樣本數(shù)Samples(ck)。

步驟3 自適應(yīng)地合成新的樣本。

(2)輸出c′k，返回上一步執(zhí)行直到遍歷完所有的集群，最終得到集合c′1,c′2,…,c′m。

步驟4 訓(xùn)練分類器。

(1)少數(shù)類集合c′1,c′2,…,c′m與多數(shù)類N組成訓(xùn)練集，利用這個訓(xùn)練集對K-NN分類器進行訓(xùn)練。

(2)利用測試數(shù)據(jù)集對分類器進行測試。

3 實驗評價指標(biāo)與參數(shù)設(shè)置

3.1 實驗評價指標(biāo)

分類器的性能指標(biāo)通常由一個混淆矩陣來評估，見表1。表1中行表示實際的類，列表示檢測到的類。TP表示分類正確的少數(shù)類樣本的數(shù)量；FN表示分類錯誤的少數(shù)類樣本數(shù)量；FP表示分類錯誤的多數(shù)類樣本的數(shù)量；TN表示分類正確的多數(shù)類樣本數(shù)量

Recall=TP/(TP+FN)

(9)

Precision=TP/(TP+FP)

(10)

表1 查全率、查準(zhǔn)率中的參數(shù)意義

(11)

TNR=TN/(FP+TN)

(12)

TPR=TP/(TP+FN)

(13)

FPR=FP/(TN+FP)

(14)

(15)

Recall(查全率)表示在所有少數(shù)類的樣本中被正確分類的樣本所占的比率；Precision(查準(zhǔn)率)表示在所有被分類器分為少數(shù)類的樣本中正確分類樣本所占的比率；F-value可以衡量分類器對少數(shù)類樣本的每個指標(biāo)性能，F(xiàn)-value越大表示分類器對少數(shù)類的識別精度越高。G-mean是評價分類器整體性能的一個很好的指標(biāo)，因為它結(jié)合了分類器對少數(shù)類和多數(shù)類的精度。另一個非常流行的測量方法是接收機工作特性(ROC)圖的下面積，通常稱為AUC[11]。與G-mean和F-value測量度不同，AUC對多數(shù)類和少數(shù)類樣本的分布不敏感，適合測量分類器對樣本分布不均勻的性能。通過在x軸上繪制假陽性率(FPR)和在y軸上繪制真陽性率(TPR)，通過計算得到的ROC曲線圖的下面積便是AUC值。當(dāng)AUC=0.5時表示分類器相當(dāng)于一個隨機猜測的分類器，AUC=1時表示分類器對所有樣本的分類準(zhǔn)確率為百分之百。AUC值越大表示分類的綜合效果越好。

3.2 實驗數(shù)據(jù)

本文的實驗選取了來自機器學(xué)習(xí)數(shù)據(jù)庫UCI[12]Class，Statlandast，Segment，Ecoli和Yeast數(shù)據(jù)庫。表2中的列分別表示數(shù)據(jù)集名稱(Name)、少數(shù)類(MinorityClass)，樣本數(shù)量(Instance)、少數(shù)類樣本數(shù)量(Min)、多數(shù)類樣本數(shù)量(Man)和不平衡比(Ibr)。對于每個數(shù)據(jù)集，目標(biāo)類為少數(shù)類，其余類被合并創(chuàng)建為多數(shù)類。

表2 實驗數(shù)據(jù)的特征與分布

3.3 實驗驗證與算法參數(shù)

為驗證本文所提過采樣方法的有效性，HD-SMOTE算法分別與Random Oversampling、SMOTE和ADASYAN這3個使用最廣泛的算法進行對比，并且和一個最新的 K-SMOTE 算法進行對比。本文中的算法用到的 HDBSCAN 的聚類算法可以在Python庫Scikit-learn[13]調(diào)用。

HDBSCAN中的參數(shù)設(shè)置為min_cluster_size=2，min_samples=3。 分別表示HDBSCAN對少數(shù)類樣本進行聚類所得到的集群的數(shù)量至少有兩個，每個集群中所包含樣本數(shù)量至少有3個。本文中其它對比算法所涉及的SMOTE算法的參數(shù)k均設(shè)置為5(默認(rèn)值)，k近鄰分類器的參數(shù)K也設(shè)置為5。其中新算法K-SMOTE中用到的K-means聚類算法的參數(shù)k∈{2,5,10,20,50}，最終本文中只列出該算法在各個數(shù)據(jù)集中不同k值下分類效果最好的實驗數(shù)據(jù)。實驗中各個算法獲得的F-value值、G-mean值和AUC值均是采用5倍交叉取平均值得到的。

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

表3列出了5種算法分別在6個數(shù)據(jù)集上的F-value值，表中黑色加粗的數(shù)字表示該行的最大數(shù)值。從表中可以發(fā)現(xiàn)HD-SMOTE算法在其中5個數(shù)據(jù)集上獲得的F-value值最高，該算法在Yeast數(shù)據(jù)上的F-value值提升最高，相比RAND算法的F-value值提升了6.9%。這是質(zhì)的提升，因為F-value值是衡量分類器對整個少數(shù)類的分類精確度，對查全率和查準(zhǔn)率取了幾何平均。這充分驗證了HD-SMOTE算法合成樣本的機制是合理有效的，這也說明在靠近集群中心的位置合成樣本可以有效避免噪聲的產(chǎn)生，并且有效提升了分類器對少數(shù)類的F-value值。在Class數(shù)據(jù)集上HD-SMOTE取得的F-value值比ADASYAN低，這是因為ADASYAN算法在類重疊區(qū)域大量合成少數(shù)類樣本，增加了分類器對少數(shù)樣本分類的查全率和查準(zhǔn)率，導(dǎo)致F-value值也隨之增加。在其它5個數(shù)據(jù)集上ADASYAN的F-value值僅次于HD-SMOTE算法，這也很好地驗證了ADASYAN可以獲得高F-value值的原因。

表3 不同算法下的F-value值

表4給出了5個算法分別在6個不同數(shù)據(jù)集上的G-mean值。從表可以看出，本文提出的HD-SMOTE算法在這6個數(shù)據(jù)集上獲得G-mean值均優(yōu)于其它算法，這表明該算法可以有效提升分類器對少數(shù)類和多數(shù)類的分類精度。前面的分析中發(fā)現(xiàn)ADASYAN算法獲得的F-value比 HD-SMOTE 高，而在表4中該算法獲得的G-mean值卻比HD-SMOTE算法低。這是因為ADASYAN算法加強了重疊區(qū)域少數(shù)類的學(xué)習(xí)，雖然提高了F-value值但這也加大了重疊區(qū)域的多數(shù)類樣本誤分為少數(shù)類的幾率，從而降低了分類器對多數(shù)類的分類精度，因此該算法的G-mean值并不比HD-SMOTE高。

表4 不同算法下的G-mean值

表5列出了5個算法在6種數(shù)據(jù)集AUC值的比較，可以直觀發(fā)現(xiàn)本文的HD-SMOTE算法在這6個數(shù)據(jù)集上的AUC均優(yōu)于其它算法。在這6個數(shù)據(jù)集上HD-SMOTE相比于其它算法的AUC值平均提升了2.4%、2.2%、2.7%、4.0%、1.0%和3.0%，可見HD-SMOTE算法比其它算法對數(shù)據(jù)集的整體分類的準(zhǔn)確率有較大提升。這也反映了HD-SMOTE算法機制可以有效緩解不平衡數(shù)據(jù)集存在的小分離、類內(nèi)和類間不平衡問題。

縱觀表4和表5，可以發(fā)現(xiàn)K-SMOTE算法在這6個數(shù)據(jù)集上的G-mean和AUC值僅次于HD-SMOTE算法，但相較于RAND，SMOTE和ADASYAN算法均有較大幅度的提升，這說明K-SMOTE算法可以有效提升分類器的整體分類準(zhǔn)確性。K-SMOTE算法利用K-means聚類算法對整個數(shù)據(jù)集進行不分標(biāo)簽地聚類，選擇出滿足失衡比率閾值(集群中多數(shù)類樣本數(shù)量與少數(shù)類樣本數(shù)量的比值)的集群，并且根據(jù)這些集群中少數(shù)類樣本的密度這些集群進行過采樣。因此該算法可以較好地解決不平衡數(shù)據(jù)集的類間和類內(nèi)不平衡問題，這也是該算法取得較高G-mean和F-value值的主要原因。K-SMOTE算法所得到的集群中可能既包含少數(shù)類樣本也包含多數(shù)類樣本，有些集群可能因為不滿足失衡比率閾值而被過濾掉。由于這些集群中少數(shù)類樣本和多數(shù)類樣本數(shù)量差距較大，分類器可能會對多數(shù)類樣本產(chǎn)生偏倚，所以在這些被過濾掉的集群中需要加強分類器對其中少數(shù)類樣本的學(xué)習(xí)。由于K-SMOTE算法過濾掉了不滿足失衡比閾值的集群，因此無法加強分類器對這類集群中少數(shù)類樣本的學(xué)習(xí)，從而降低了分類器對少數(shù)類樣本的精確度。這也是該算法的G-mean和F-value值比DH-SMOTE算法低的主要原因，并且K-SMOTE算法對K-means聚類參數(shù)很敏感因此參數(shù)難以調(diào)優(yōu)。HD-SMOTE算法恰好可以克服這些缺點，HD-SMOTE算法只對少數(shù)類樣本進行聚類，這很好地克服K-SMOTE算法將少數(shù)類和多數(shù)類樣本聚類為同一個集群的缺陷，并且算法對聚類參數(shù)并不敏感，不管在什么情況下HD-SMOTE算法都可以有效加強分類器對少數(shù)類樣本的學(xué)習(xí)，增加了分類器對少數(shù)類樣本和多數(shù)類樣本的分類精度，因此HD-SMOTE相比較于K-SMOTE和其它算法更為合理。

表5 不同算法下的AUC值

5 結(jié)束語

本文提出的方法采用高效的HDBSCA聚類算法結(jié)合SMOTE過采樣來重新平衡傾斜數(shù)據(jù)集。它只在安全地區(qū)進行過采樣，以避免產(chǎn)生噪音。該方法與相關(guān)方法的不同之處在于它的新穎性和有效合成樣本的方法。樣本分布以聚類密度為基礎(chǔ)，在稀疏的少數(shù)類地區(qū)比在稠密的少數(shù)類地區(qū)合成更多的樣本，以克服小分離、類內(nèi)和類間不平衡問題。實驗結(jié)果表明，本文提出的方法HD-SMOTE幾乎在所有數(shù)據(jù)集上的F-value，G-mean，AUC均優(yōu)于其它算法。