基于HDBACAN聚類的自適應過采樣技術

董宏成，趙學華，趙 成，劉 穎，解如風

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶市質量和標準化研究院，重慶 400023；3.重慶信科設計有限公司，重慶 401121)

0 引 言

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

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

1 HDBSCAN聚類和SMOTE過采樣算法

1.1 HDBSCAN聚類

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

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

1.2 SMOTE過采樣方法

(1)

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

圖1 類內不平衡下SMOTE合成樣本

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

2 HD-SMOTE自適應過采樣算法

2.1 HD-SMOTE框架

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

圖2 HD-SMOTE過采樣框架

2.2 改進的SMOTE過采樣方法

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

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

其中，numf表示集群的數量。

步驟5 計算每個集群的采樣權重

(6)

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

步驟6 計算要合成的樣本總數

N=Nmaj-Nmin

(7)

其中，Nmaj為多數類樣本數，Nmin為少數類樣本數。

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

Samples(ck)=N×Sampleweight(ck)

(8)

2.3 HD-SMOTE的算法描述

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

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

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

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

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

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

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

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

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

步驟3 自適應地合成新的樣本。

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

步驟4 訓練分類器。

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

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

3 實驗評價指標與參數設置

3.1 實驗評價指標

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

Recall=TP/(TP+FN)

(9)

Precision=TP/(TP+FP)

(10)

表1 查全率、查準率中的參數意義

(11)

TNR=TN/(FP+TN)

(12)

TPR=TP/(TP+FN)

(13)

FPR=FP/(TN+FP)

(14)

(15)

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

3.2 實驗數據

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

表2 實驗數據的特征與分布

3.3 實驗驗證與算法參數

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

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

4 實驗結果及分析

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

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

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

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

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

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

表5 不同算法下的AUC值

5 結束語

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