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

王圓方

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

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

中圖分類號(hào)： TP301.6????文獻(xiàn)標(biāo)識(shí)碼：?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ù)集中某些類的樣本個(gè)數(shù)明顯小于其他類的數(shù)據(jù)集[1]。在二分類問(wèn)題中，定義擁有較多樣本數(shù)量的類別為負(fù)類，將樣本數(shù)量少的類別成為正類[2]。在類不平衡數(shù)據(jù)集的分類問(wèn)題中，由于少數(shù)類樣本的誤分代價(jià)更大，所以少數(shù)類樣本比其他類別數(shù)據(jù)更重要[3]。樣本不平衡會(huì)帶來(lái)樣本點(diǎn)的空間分布并不能符合真實(shí)分布，因此使用SMOTE擴(kuò)充樣本集合時(shí)，并不能改變?cè)袠颖镜姆植嫉耐鈬喞卣鳎@就意味著對(duì)分類問(wèn)題中分類邊界的影響比較小。因此，如何有效的解決不平衡數(shù)據(jù)集的分類問(wèn)題成為了數(shù)據(jù)挖掘領(lǐng)域中的重要研究?jī)?nèi)容。

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

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

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

1??理論知識(shí)

1.1 ?SMOTE算法

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

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

1.2??層次聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

3 ?實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

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

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

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

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

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

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

4??結(jié)論

本文針對(duì)SMOTE算法合成少數(shù)類新樣本存在的不足，引入了層次聚類算法，提出一種基于層次聚類改進(jìn)的SMOTE算法。該算法首先使用層次聚類算法對(duì)少數(shù)類樣本聚類;其次，利用簇密度分布函數(shù)計(jì)算各個(gè)簇的采樣權(quán)重，最后，使用改進(jìn)的SMOTE算法合成新的少數(shù)類樣本。實(shí)驗(yàn)結(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ì)算機(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]. 長(zhǎng)春： 吉林大學(xué)， 2011.

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

王韞燁， 孔珊. 一種基于檢測(cè)器集層次聚類的免疫否定選擇算法[J/OL]. 計(jì)算機(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的過(guò)采樣算法[J/OL]. 計(jì)算機(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ì)算機(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ì)算機(jī)科學(xué)， 2008， 35（5）： 174-176.