基于層次聚類改進(jìn)SMOTE的過采樣方法

王圓方

摘 ?要： 針對SMOTE算法在合成少數(shù)類新樣本時存在的不足，提出了一種基于層次聚類算法改進(jìn)的SMOTE過采樣法H-SMOTE。該算法首先對少數(shù)類樣本進(jìn)行層次聚類，其次根據(jù)提出的簇密度分布函數(shù)，計算各個簇的簇密度，最后在各個簇中利用改進(jìn)的SMOTE算法進(jìn)行過采樣，提高合成樣本的多樣性，得到新的平衡數(shù)據(jù)集。通過對UCI數(shù)據(jù)集的實驗表明，H-SMOTE算法的分類效果得到明顯的提升。

關(guān)鍵詞：?過采樣;少數(shù)類;層次聚類;SMOTE

中圖分類號： TP301.6????文獻(xiàn)標(biāo)識碼：?A????DOI：10.3969/j.issn.1003-6970.2020.02.044

【Abstract】： For conventional oversampling algorithms， for example， SMOTE， there are several problems such as ignoring within-class imbalances. Based in the comprehensive consideration of within-class imbalance， an oversampling algorithm， which is a hybrid of Aggregation hierarchy clustering?and improved SMOTE（H-SMOTE）， is proposed.Firstly， it utilizes the hierarchy clustering?to cluster minority class samples. Secondly， according to the proposed cluster density distribution function， the cluster density of each cluster are calculated. Finally， the H-SMOTE algorithm is adopted to oversample on the lines of the location-distant minority class samples in each cluster， the diversity of synthetic samples is improved and a new balanced data set between and within classes is obtained. Experiments on the UCI data sets show that H-SMOTE can effectively improve the classification performance of the classifier for the minority class samples.

【Key words】： Oversampling; Minority class; Aggregation hierarchy clustering; SMOTE

0??引言

不平衡數(shù)據(jù)集是指數(shù)據(jù)集中某些類的樣本個數(shù)明顯小于其他類的數(shù)據(jù)集[1]。在二分類問題中，定義擁有較多樣本數(shù)量的類別為負(fù)類，將樣本數(shù)量少的類別成為正類[2]。在類不平衡數(shù)據(jù)集的分類問題中，由于少數(shù)類樣本的誤分代價更大，所以少數(shù)類樣本比其他類別數(shù)據(jù)更重要[3]。樣本不平衡會帶來樣本點的空間分布并不能符合真實分布，因此使用SMOTE擴(kuò)充樣本集合時，并不能改變原有樣本的分布的外圍輪廓特征，這就意味著對分類問題中分類邊界的影響比較小。因此，如何有效的解決不平衡數(shù)據(jù)集的分類問題成為了數(shù)據(jù)挖掘領(lǐng)域中的重要研究內(nèi)容。

SMOTE算法[4]是目前常用的過采樣方法，可以有效的平衡數(shù)據(jù)集。但也存在一些問題：該算法無法克服非平衡數(shù)據(jù)集的數(shù)據(jù)分布問題，容易產(chǎn)生分布邊緣化的問題。由于負(fù)類樣本的分布決定了其可選擇的近鄰，如果一個負(fù)類樣本處在負(fù)類樣本的邊緣，則由這個負(fù)類樣本和近鄰產(chǎn)生的新樣本也在邊緣，從而無法確定正負(fù)類的邊界[5]。

對于SMOTE算法存在的問題，Han[6]等人提出了Borderline-SMOTE算法，該算法是對位于分類邊界的少數(shù)類樣本進(jìn)行過采樣，加強(qiáng)對分類邊界樣本的學(xué)習(xí)。He[7]等人提出的ADASYN算法根據(jù)數(shù)據(jù)分布自動確定每個少數(shù)類樣本需要生成新樣本的數(shù)量，擁有越多多數(shù)類鄰居的少數(shù)類樣本生成更多的新樣本。相比于SMOTE算法，Borderline-?SMOTE和ADASYN算法只對樣本的分布進(jìn)行了細(xì)致劃分，因此依然存在SMOTE算法出現(xiàn)的問題[8]。

針對以上過采樣算法存在的問題，本文提出了H-SMOTE算法。首先，對少數(shù)類樣本使用層次聚類算法進(jìn)行聚類;其次，根據(jù)本文提出的密度函數(shù)計算簇密度;最后，在每個簇中使用改進(jìn)的 SMOTE 算法（H-SMOTE）進(jìn)行過采樣，得到類間和類內(nèi)均達(dá)到平衡的新數(shù)據(jù)集，并且合成的少數(shù)類樣本具有多樣性。

1??理論知識

1.1 ?SMOTE算法

SMOTE算法[4]的基本原理是在近鄰少數(shù)列樣本之間進(jìn)行線性差值，合成新的少數(shù)類樣本。具體步驟如下：

（3）將生成的新樣本全部加入原始訓(xùn)練數(shù)據(jù)?中，消除訓(xùn)練數(shù)據(jù)集的不平衡度。

1.2??層次聚類算法

層次聚類[9]（hierarchical clustering）是一種基于原型的聚類算法，試圖在不同層次對數(shù)據(jù)集進(jìn)行劃分，從而形成樹形的聚類結(jié)構(gòu)。數(shù)據(jù)集的劃分可采用“自底向上”的聚合策略，也可以采用“自頂向下”的分拆策略。層次聚類算法的優(yōu)勢在于，可以通過繪制樹狀圖（dendrogram），幫助我們使用可視化的方式來解釋聚類結(jié)果。

層次聚類[10]可以分為凝聚（agglomerative）層次聚類和分裂（divsive）層次聚類。分裂層次聚類采用的就是“自頂而下”的思想，先將所有的樣本都看作是同一個簇，然后通過迭代將簇劃分為更小的簇，直到每個簇中只有一個樣本為止。凝聚層次聚類采用的是“自底向上”的思想，先將每一個樣本都看成是一個不同的簇，通過重復(fù)將最近的一對簇進(jìn)行合并，直到最后所有的樣本都屬于同一個簇??為止。

在文本中我們選用的是凝聚層次聚類，在凝聚層次聚類[11]中，判定簇間距離的兩個標(biāo)準(zhǔn)方法就是單連接（single linkage）和全連接（complete linkage）。單連接，是計算每一對簇中最相似兩個樣本的距離，并合并距離最近的兩個樣本所屬簇。全連接，通過比較找到分布于兩個簇中最不相似的樣本（距離最遠(yuǎn)），從而來完成簇的合并。

凝聚層次聚類除了通過單連接和全連接來判斷兩個簇之間的距離之外，還可以通過平均連接（average linkage）和ward連接。使用平均連接時，合并兩個簇所有成員間平均距離最小的兩個簇。使用ward連接，合并的是使得SSE增量最小的兩個簇。

給定要聚類的N的對象以及N*N的距離矩??陣（或者是相似性矩陣）， 層次聚類方法的基本步驟如下：

（1）將每個對象歸為一類， 共得到N類，每類僅包含一個對象。類與類之間的距離就是它們所包含的對象之間的距離，這里使用歐氏距離，即

（2）找到最接近的兩個類并合并成一類，于是總的類數(shù)少了一個。

（3）重新計算新的類與所有舊類之間的距離。

（4）重復(fù)第2步和第3步，直到最后合并成一個類為止（此類包含了N個對象）。

2??基于層次聚類改進(jìn)SMOTE的過采樣方法

針對SMOTE等傳統(tǒng)過采樣算法存在的問題，本文先將SMOTE算法進(jìn)行改進(jìn)，并結(jié)合層次聚類算法，提出了H-SMOTE過采樣算法。

2.1??簇密度分布函數(shù)

相比于SMOTE等傳統(tǒng)算法，H-SMOTE算法引入簇密度分布函數(shù)的定義，因此該算法可以有效解決少數(shù)類樣本類內(nèi)不平衡的問題。H-SMOTE 算法在兩個相距較遠(yuǎn)的樣本點的連線上不斷合成新樣本，可以提高合成少數(shù)類樣本的多樣性，為分類器提供更多有效的分類信息。

3 ?實驗設(shè)計與結(jié)果分析

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

本實驗采用UCI數(shù)據(jù)庫中的五個數(shù)據(jù)集作為實驗數(shù)據(jù)，5個數(shù)據(jù)集的特征如表1所示：

3.2??評價指標(biāo)

傳統(tǒng)的分類學(xué)習(xí)方法中，一般采用分類精度作為評價指標(biāo)，然而對于不平衡數(shù)據(jù)集，用分類精度來評價分類器的性能是不合理的[13-14]。所以對于不平衡數(shù)據(jù)集，有新的評價指標(biāo)，F(xiàn)-value、G-mean等，基本上都是建立在混淆矩陣基礎(chǔ)上的。

二分類問題的混淆矩陣如表2所示。其中，TP表示少數(shù)類樣本判為少數(shù)類的數(shù)目，TN表示多數(shù)類樣本判為多數(shù)類的數(shù)目，F(xiàn)N、FP分別表示判決錯誤的實際少數(shù)類和多數(shù)類樣本數(shù)目。

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

本文實現(xiàn)了SMOTE、Borderline-SMOTE、ASMOTE、KM-SMOTE、H-SMOTE和SVM算法。將SMOTE、Borderline-SMOTE、ASMOTE、Random-?SMOTE算法中的上采樣倍數(shù)設(shè)為同一數(shù)值，使用SVM算法[15]進(jìn)行分類。實驗結(jié)果如表3、表4所示。

由表3和表4可知，Pima和Ionosphere兩個數(shù)據(jù)集的不平衡程度較高，H-SMOTE和SVM組合算法較其他算法在F-value和G-mean上提升效果明顯。主要是數(shù)據(jù)集不平衡程度較高，存在較多的孤立少數(shù)類樣本，H-SMOTE算法通過接近度能夠選擇這些孤立樣本，避免孤立點被噪聲淹沒。Ecoli1和Segment兩個數(shù)據(jù)集的不平衡程度較低，本文改進(jìn)的算法較其它算法相比，F(xiàn)-value和G-mean也有明顯的提升。

以上結(jié)果總體來看，本文提出的H-SMOTE過???采樣算法可以有效提升分類器對少數(shù)類樣本的分類?性能。

4??結(jié)論

本文針對SMOTE算法合成少數(shù)類新樣本存在的不足，引入了層次聚類算法，提出一種基于層次聚類改進(jìn)的SMOTE算法。該算法首先使用層次聚類算法對少數(shù)類樣本聚類;其次，利用簇密度分布函數(shù)計算各個簇的采樣權(quán)重，最后，使用改進(jìn)的SMOTE算法合成新的少數(shù)類樣本。實驗結(jié)果表明，H-SMOTE算法可以有效地提高分類器的分類性能。

參考文獻(xiàn)

Li J， Fong S， Wong R K， et al. Adaptive multi-objective swarm fusion for imbalanced data classification[J]. In-formation Fusion， 2018， 39： 1-24.

Cao Peng， Liu Xiaoli， Zhang Jian， et al. ?2， 1 norm regu-larized multi-kernel based joint nonlinear feature selec-?tion and over-sampling for imbalanced data classifica-tion[J]. Neurocomputing， 2017， 234： 38-57.

Bahnsen A C， Aouada D， Stojanovic A， et al. Feature engineering strategies for credit card fraud detection[J]. Expert?Systems with Applications An International Jour-nal， 2016， 51（C）： 134-142.

Chawlan， V.， Bowyer， K. W. and Hall， L. O. （2002） SMOTE： Synthetie minority over-sampling technique. Journal of Aflificial Intelligence Research， 16（1）， 321- 357.

向鴻鑫， 楊云. 不平衡數(shù)據(jù)挖掘方法綜述[J]. 計算機(jī)工程與應(yīng)用， 2019， 55（4）： 6-21.

Han Hui， Wang Wenyuan， Mao Binghuan. Border-line-?SMOTE： A new over-sampling method in imbal-anced data sets learning[C]//International Conference on Intelligent Computing， 2005： 878-887.

He Haibo， Bai Yang， Garcia E A， et al. ADASYN： Adap-tive Synthetic Sampling Approach for Imbalanced Learn-ing[C]//?IEEE International Joint Conference on Neural Networks， 2008： 1322-1328.

李軍. 不平衡數(shù)據(jù)學(xué)習(xí)的研究[D]. 長春： 吉林大學(xué)， 2011.

代翔， 黃細(xì)鳳， 唐瑞， 蔣夢婷， 陳興蜀， 王海舟， 羅梁. 基于層次聚類的子話題檢測算法[J]. 華南理工大學(xué)學(xué)報（自然科學(xué)版）， 2019， 47（08）： 84-95.

王韞燁， 孔珊. 一種基于檢測器集層次聚類的免疫否定選擇算法[J/OL]. 計算機(jī)工程： 1-6[2019-10-23]. http：//kns.?cnki.net/kcms/detail/31.1289.TP.20190814.0950.006.html.

鐘俊坤. 幾種新聚類算法的研究[D]. 西安： 西安電子科技大學(xué)， 2014.

王亮， 冶繼民. 整合DBSCAN和改進(jìn)SMOTE的過采樣算法[J/OL]. 計算機(jī)工程與應(yīng)用： 1-10[2019-10-23]. http：//kns.?cnki.net/kcms/detail/11.2127.TP.20190925.1044.010.html.

Yaxiang G U， Shifei D， 顧亞祥， et al. Advances of Support Vector Machines（SVM）支持向量機(jī)研究進(jìn)展[J]. 計算機(jī)科學(xué)， 2011， 38（2）： 14-17.

Yang Y， Shan-Ping L I. Instance Importance Based SVM for Solving Imbalanced Data Classification[J]. Pattern Recognition & Artificial Intelligence， 2009.

王和勇， 樊泓坤， 姚正安. SMOTE和Biased-SVM相結(jié)合的不平衡數(shù)據(jù)分類方法[J]. 計算機(jī)科學(xué)， 2008， 35（5）： 174-176.