基于DBSCAN改進(jìn)的SMOTE算法

邱燦華 吳杰

摘要：針對(duì)傳統(tǒng)的合成少數(shù)類過(guò)采樣技術(shù)（Synthetic Minority Oversampling Technique，SMOTE）中存在的忽略類間不平衡、類內(nèi)不平衡、無(wú)法控制合成樣本的噪聲等問(wèn)題，結(jié)合DBSCAN聚類算法，提出了一種基于DBSCAN改進(jìn)的SMOTE算法：使用DBSCAN算法對(duì)少數(shù)類樣本進(jìn)行聚類，計(jì)算少數(shù)類密度系數(shù)和采用權(quán)重為每個(gè)簇分配采樣數(shù)量，將每個(gè)簇中樣本點(diǎn)按照到簇質(zhì)心的距離分為2類，對(duì)每類中的樣本點(diǎn)分配不同的隨機(jī)系數(shù)進(jìn)行過(guò)采樣，得到新的較為平衡的數(shù)據(jù)集。根據(jù)獲取的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)表明，改進(jìn)的算法可以很好地改善分類器的分類性能。

關(guān)鍵詞：SMOTE算法；DBSCAN算法；不平衡數(shù)據(jù)集；過(guò)采樣

中圖分類號(hào)：TP181文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2022）07-62-5

0引言

旅游在線評(píng)論是文本情感分析的一種重要的信息來(lái)源，對(duì)游客選擇旅游目的地以及幫助旅游地改善其旅游產(chǎn)品或服務(wù)都有非常好的現(xiàn)實(shí)意義[1]。然而在實(shí)際研究中，評(píng)論數(shù)據(jù)集大多是不平衡的。不平衡數(shù)據(jù)是指類分布不平均的數(shù)據(jù)，樣本數(shù)目多的類被稱為多數(shù)類，數(shù)目少的被稱為少數(shù)類[2]。在分類算法中，數(shù)據(jù)集的不平衡會(huì)導(dǎo)致傳統(tǒng)分類器的準(zhǔn)確率偏向于多數(shù)類，而在不平衡類中，少數(shù)類包含更多有用的信息，對(duì)分析結(jié)果會(huì)產(chǎn)生更大影響[3]。在現(xiàn)實(shí)中，少數(shù)類樣本的預(yù)測(cè)結(jié)果往往才是人們關(guān)注的重點(diǎn)，如旅游評(píng)論分析中，少數(shù)的差評(píng)比多數(shù)的好評(píng)更有研究意義[4]。

為了解決數(shù)據(jù)集不平衡問(wèn)題，Chawla[5]于2022年提出少數(shù)類過(guò)采樣技術(shù)（Synthetic Minority Oversampling Technique，SMOTE），通過(guò)在數(shù)據(jù)集中增加人工合成的少數(shù)類樣本，使數(shù)據(jù)集趨于平衡，同時(shí)減少了過(guò)擬合的可能性，有效地平衡了數(shù)據(jù)集。近些年，很多學(xué)者也在SMOTE算法的基礎(chǔ)上進(jìn)行改進(jìn)，Han[6]提出的Borderline-SMOTE算法將數(shù)據(jù)集的少數(shù)類分成3類，選擇其中一類樣本作為根樣本進(jìn)行過(guò)采樣，確保了新合成的樣本不會(huì)成為噪聲。古平[7]提出AdaBoost-SVM-MSA算法，將分類錯(cuò)誤的樣本分成3類，對(duì)每一類樣本采用不同的方式進(jìn)行處理，實(shí)驗(yàn)表明算法能有效地提高少數(shù)類的分類準(zhǔn)確率。Barua[8]將聚類算法與SMOTE結(jié)合，采用聚類算法從加權(quán)的少數(shù)類樣本中合成樣本，保證生成的新樣本位于少數(shù)類區(qū)域內(nèi)。Douzas[9]將K-means聚類算法同SMOTE相結(jié)合，實(shí)驗(yàn)證明該方法能有效避免噪聲的生成，改善了SMOTE造成的類間不平衡問(wèn)題。

針對(duì)SMOTE算法存在的一些問(wèn)題，本文將DBSCAN聚類算法同改進(jìn)的SMOTE算法相結(jié)合，提出DBS-DTCSMOTE算法。使用DBSCAN算法進(jìn)行聚類，有效剔除噪聲樣本，改善傳統(tǒng)SMOTE算法無(wú)法控制樣本噪聲的問(wèn)題。根據(jù)本文提出的類不平衡率和采樣權(quán)重，對(duì)于聚類產(chǎn)生的不同的簇合成不同數(shù)量的新樣本，很好地改善傳統(tǒng)SMOTE算法存在的類間不平衡問(wèn)題；改進(jìn)的SMOTE算法按照簇內(nèi)樣本到質(zhì)心的距離設(shè)置不同的隨機(jī)系數(shù)，使合成后的簇內(nèi)部分布更加合理，一定程度上緩解了傳統(tǒng)SMOTE算法造成的類內(nèi)不平衡問(wèn)題。

1基本原理

1.1 SMOTE算法

SMOTE是一種基于特征空間的過(guò)采樣方法，通過(guò)在少數(shù)類樣本及其近鄰樣本之間采用線性插值的方法合成新的少數(shù)類樣本，通過(guò)人工合成新樣本有效緩解了隨機(jī)復(fù)制少數(shù)類樣本引起的過(guò)擬合問(wèn)題，是目前主要的應(yīng)用于不平衡問(wèn)題的數(shù)據(jù)預(yù)處理技術(shù)。SMOTE基本原理如圖1所示。

③將生成的新樣本加入原始的數(shù)據(jù)集中，增加少數(shù)類樣本數(shù)量，降低數(shù)據(jù)集的不平衡性。

SMOTE算法依然存在著很多問(wèn)題，如合成樣本的質(zhì)量問(wèn)題、類邊界模糊的問(wèn)題以及少數(shù)類樣本的分布問(wèn)題等[9]。如果選擇的少數(shù)類樣本或者其近鄰樣本存在噪聲，則合成的樣本極有可能成為噪聲；如果選擇的少數(shù)類樣本位于邊緣地區(qū)，那么生成的新樣本也大概率位于邊緣地區(qū)，會(huì)造成類邊界模糊。由于少數(shù)類樣本內(nèi)部分布不均，SMOTE在進(jìn)行線性插值的過(guò)程中，根據(jù)近鄰原則會(huì)在根樣本以及輔助樣本附近位置生成新樣本，這樣就會(huì)導(dǎo)致少數(shù)類中相對(duì)密集的區(qū)域更密集，相對(duì)稀疏的區(qū)域更稀疏，分類算法不易識(shí)別稀疏區(qū)的少數(shù)類樣本，進(jìn)而會(huì)影響分類的準(zhǔn)確性[10]。

1.2 DBSCAN聚類算法

DBSCAN是一種基于密度的空間聚類算法，該算法將具有足夠密度的區(qū)域劃分為簇，可以在具有噪聲的數(shù)據(jù)集中識(shí)別出任意形狀的簇。與K-means算法不同，它不需要確定聚類的數(shù)量，而是基于數(shù)據(jù)推測(cè)聚類的數(shù)目，能夠針對(duì)任意形狀產(chǎn)生聚類。

DBSCAN算法存在以下2個(gè)關(guān)鍵參數(shù)：Epsilon表示在一個(gè)點(diǎn)周圍鄰近區(qū)域的半徑；MinPts表示鄰近區(qū)域內(nèi)至少包含點(diǎn)的個(gè)數(shù)[11]。

DBSCAN聚類算法與K-means聚類算法相比，最大優(yōu)勢(shì)是能夠識(shí)別任意形狀的聚類簇，并且可以在聚類時(shí)發(fā)現(xiàn)異常點(diǎn)，過(guò)濾噪聲點(diǎn)，同時(shí)聚類結(jié)果沒(méi)有大的偏差，K-means聚類算法的結(jié)果與初始值有很大的關(guān)系[12]。

2基于DBSCAN改進(jìn)的SMOTE算法

針對(duì)SMOTE過(guò)采樣算法存在的不足，如無(wú)法控制合成樣本的質(zhì)量、容易導(dǎo)致類邊界的模糊等問(wèn)題，本文結(jié)合DBSCAN算法良好的聚類性能，對(duì)傳統(tǒng)的SMOTE算法進(jìn)行一定的改進(jìn)，提出一種基于DBSCAN的改進(jìn)的SMOTE算法。

2.1類不平衡率與采用樣重

DTCSMOTE算法主要是將同一聚類簇內(nèi)的少數(shù)類樣本按照到質(zhì)心的距離分為遠(yuǎn)離質(zhì)心類與接近質(zhì)心類，針對(duì)遠(yuǎn)離質(zhì)心類中的樣本，在遠(yuǎn)離質(zhì)心的一端合成新的樣本；針對(duì)接近質(zhì)心類中的樣本，在接近質(zhì)心的一端合成新的樣本，試圖以不同的隨機(jī)數(shù)去改善少數(shù)類的類間不平衡性。

2.3 DB-DTCSMOTE過(guò)采樣算法

DB-DTCSMOTE過(guò)采樣算法由DBSCAN聚類算法以及改進(jìn)的SMOTE過(guò)采樣算法組成，算法主要包括DBSCAN聚類、少數(shù)類樣本密度系數(shù)的計(jì)算、采樣權(quán)重的計(jì)算和DTCSMOTE算法合成新樣本。主要步驟如下：

Input：原始數(shù)據(jù)集，需要合成的新樣本數(shù)量，DBSCAN聚類算法參數(shù)和。

Output：合成的少數(shù)類樣本集。

步驟2：計(jì)算簇的少數(shù)類樣本密度系數(shù)（ ）。

步驟3：計(jì)算簇的采樣權(quán)重（ ），記為。

步驟4：計(jì)算簇需要合成的新樣本數(shù)量=×。

步驟5：在簇中使用DTCSMOTE算法合成新樣本集，并將加入中。

DB-DTCSMOTE與傳統(tǒng)的SMOTE算法相比存在很多優(yōu)勢(shì)，使用DBSCAN算法對(duì)所有數(shù)據(jù)進(jìn)行聚類可以有效剔除噪聲樣本，通過(guò)引入少數(shù)類樣本密度系數(shù)以及采樣權(quán)重，可以有效改善類間不平衡的問(wèn)題；利用改進(jìn)的DTCSMOTE算法合成新樣本，對(duì)遠(yuǎn)離質(zhì)心的樣本點(diǎn)與接近質(zhì)心的樣本點(diǎn)分開(kāi)進(jìn)行合成，有效改善了SMOTE算法任意合成新樣本的弊端。

3實(shí)驗(yàn)與分析

為了驗(yàn)證算法的性能，利用從攜程旅游網(wǎng)站獲取的游客關(guān)于古鎮(zhèn)的評(píng)論作為原始數(shù)據(jù)集，分別使用Random-OverSampling，SMOTE，Borderline-SMOTE，ADASYN，DB-DTCSMOTE五種算法對(duì)原始數(shù)據(jù)集進(jìn)行過(guò)采樣，得到新的較為平衡的數(shù)據(jù)集，并且使用SVM算法和KNN算法對(duì)數(shù)據(jù)進(jìn)行分類，以驗(yàn)證不同算法的性能優(yōu)劣。

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

本文根據(jù)攜程旅游網(wǎng)站對(duì)于古鎮(zhèn)的排名，選擇排名前10的古鎮(zhèn)，基于Python的爬蟲技術(shù)獲取游客關(guān)于古鎮(zhèn)景點(diǎn)的評(píng)論數(shù)據(jù)。原始數(shù)據(jù)集經(jīng)過(guò)去雜去重后，對(duì)所有評(píng)論內(nèi)容進(jìn)行分詞處理，分詞后的數(shù)據(jù)利用Google開(kāi)源的Word2vec算法得到文本的向量表示，基于Tf-idf的文本加權(quán)技術(shù)將文本數(shù)據(jù)轉(zhuǎn)換為向量形式。經(jīng)過(guò)前期的數(shù)據(jù)處理得到原始數(shù)據(jù)集，共包含32 080條數(shù)據(jù)，經(jīng)過(guò)DBSCAN聚類后去除噪聲樣本，剩余數(shù)據(jù)集包含正樣本數(shù)29 720條，負(fù)樣本數(shù)2 359條。

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

機(jī)器學(xué)習(xí)有很多評(píng)價(jià)指標(biāo)，實(shí)際上不同的評(píng)價(jià)指標(biāo)就是用不同的方法來(lái)評(píng)價(jià)算法的好壞。對(duì)于回歸問(wèn)題，通過(guò)mae，mse等指標(biāo)就可以很好地衡量模型的好壞，但針對(duì)分類問(wèn)題，僅僅通過(guò)準(zhǔn)確率并不能很好地衡量模型的優(yōu)劣，這時(shí)就要引入查準(zhǔn)率、查全率、F1值來(lái)評(píng)價(jià)模型的性能[13]。

機(jī)器學(xué)習(xí)的評(píng)價(jià)指標(biāo)建立在混淆矩陣之上，在混淆矩陣中有4個(gè)數(shù)據(jù)，其中，TP和TN分別表示正確分類的正類和負(fù)類的樣本數(shù)量；FN和FP分別表示錯(cuò)誤分類的正類和負(fù)類的樣本數(shù)量[14]。

①準(zhǔn)確率：所有正確預(yù)測(cè)（正類、負(fù)類）占總體的比重，準(zhǔn)確率越高說(shuō)明模型分類效果越好，準(zhǔn)確率是衡量模型性能的重要指標(biāo)。

②精確率（查準(zhǔn)率）：即正確預(yù)測(cè)為正的占全部預(yù)測(cè)為正的比例。

③召回率（查全率）：即正確預(yù)測(cè)為正的占全部實(shí)際為正的比例。

④F1值為查準(zhǔn)率和查全率的調(diào)和平均數(shù)，因?yàn)榫_率和召回率指標(biāo)有時(shí)候會(huì)出現(xiàn)矛盾的情況，就需要綜合考慮，最常見(jiàn)的方法就是F1-score[15]。

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

本文基于Python實(shí)現(xiàn)原始數(shù)據(jù)獲取、數(shù)據(jù)整理、過(guò)采樣、SVM分類以及KNN分類。訓(xùn)練集與測(cè)試集的比例為6：4，隨機(jī)種子值設(shè)為1；DB-DTCSMOTE算法中DBSCAN聚類算法的=3，Min=5；SVM算法的核函數(shù)為高斯核函數(shù)，Gamma值設(shè)置為0.1，懲罰因子設(shè)置為0.8；經(jīng)過(guò)數(shù)據(jù)預(yù)處理設(shè)置KNN算法的近鄰數(shù)為20，步長(zhǎng)為0.2。通過(guò)數(shù)據(jù)的比較可以得出以下結(jié)論：

①使用同一數(shù)據(jù)集，在SVM分類器得出的結(jié)果要優(yōu)于KNN分類器，這歸功于SVM算法中的核函數(shù)。核函數(shù)的應(yīng)用使得算法無(wú)需知道非線性映射的顯式表達(dá)式，由于SVM是在高維特征空間中構(gòu)建的線性學(xué)習(xí)機(jī)，所以與線性模型相比，幾乎不增加計(jì)算的復(fù)雜性，而且在某種程度上避免了“維數(shù)災(zāi)難”，使得SVM分類器的性能更加優(yōu)異。

②使用KNN和SVM分類測(cè)試集比例為0.6，不同過(guò)采樣算法的性能表現(xiàn)分別如表1和表2所示，相對(duì)于原始數(shù)據(jù)集來(lái)說(shuō)，應(yīng)用Random-Oversampling，SMOTE，Borderline-Smote，ADASYN，DC-DTCSMOTE這些過(guò)采樣算法對(duì)數(shù)據(jù)集進(jìn)行過(guò)采樣，可以不同程度地提高分類器對(duì)數(shù)據(jù)集的分類效果。相對(duì)于其他4種過(guò)采樣算法，DC-DTCSMOTE過(guò)采樣算法對(duì)分類器分類效果的提高效果更明顯，可以很好地提高分類器分類的各項(xiàng)評(píng)估系數(shù)。這是因?yàn)镈C-DTCSMOTE在過(guò)采樣之前先對(duì)原始數(shù)據(jù)集進(jìn)行了聚類，可以保證聚類同時(shí)去除噪聲數(shù)據(jù)，同時(shí)可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類。按照簇內(nèi)密度對(duì)每一簇分配不同的采樣權(quán)重，可以很好地克服原始數(shù)據(jù)集的類間分布不均；同時(shí)，改進(jìn)的SMOTE算法可以一定程度緩解簇內(nèi)的分布不平衡。

③為了驗(yàn)證測(cè)試集比例對(duì)分類結(jié)果的影響，將測(cè)試集比例設(shè)為0.6，0.7，0.8，使用KNN和SVM分類DC-DTCSMOTE算法的性能表現(xiàn)分別如表3和表4所示。實(shí)驗(yàn)數(shù)據(jù)顯示，對(duì)于DC-DTCSMOTE算法，測(cè)試集比例越高，無(wú)論是KNN還是SVM的分類結(jié)果的各項(xiàng)指標(biāo)都有提升，測(cè)試集的比例對(duì)最終的分類結(jié)果存在一定的影響。

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

本文試圖解決SMOTE算法中存在的不足，利用DBSCAN聚類算法的優(yōu)勢(shì)，提出了一種基于DBSCAN改進(jìn)的SMOTE算法。算法首先使用DBSCAN算法對(duì)原始數(shù)據(jù)集中的少數(shù)類數(shù)據(jù)進(jìn)行聚類；隨后按照不同聚類簇的密度分布，為不同簇分配不同的采樣權(quán)重，根據(jù)每個(gè)簇的權(quán)重確定該簇需合成樣本的數(shù)量；最后，對(duì)SMOTE算法做出改進(jìn)，將同一簇內(nèi)樣本按照到質(zhì)心的距離分成兩類，對(duì)每一類數(shù)據(jù)設(shè)置不同的隨機(jī)數(shù)產(chǎn)生范圍，合成新的少數(shù)類樣本。根據(jù)從攜程旅游獲取的旅游評(píng)論數(shù)據(jù)，經(jīng)實(shí)驗(yàn)驗(yàn)證，本文提出的基于DBSCAN改進(jìn)的SMOTE算法可以有效緩解傳統(tǒng)SMOTE算法存在的類間不平衡與類內(nèi)不平衡問(wèn)題，增強(qiáng)分類器的分類性能。

參考文獻(xiàn)

[1]鄭文英.旅行目的地中文評(píng)論的情感分析研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2010.

[2]石洪波，陳雨文，陳鑫.SMOTE過(guò)采樣及其改進(jìn)算法研究綜述[J].智能系統(tǒng)學(xué)報(bào)，2019，14（6）：1073-1083.

[3]馬琳，張莎莎，宋姝雨，等.基于SDN的智能入侵檢測(cè)系統(tǒng)模型與算法[J].高技術(shù)通訊，2020，30（5）：533-537.

[4]陳榮榮.基于GAN-XGBoost的信用卡交易欺詐檢測(cè)模型研究[D].杭州：杭州師范大學(xué)，2019.

[5] CHAWLA N V， BOWYER K W， HALL L O， et al. SMOTE： Synthetic Minority Over-sampling Technique[J]. Journal of Artificial Intelligence Research， 2002， 16（1）： 321-357

[6] HAN H， WANG W， MAO B. Borderline-SMOTE： A New Over-sampling Method in Imbalanced Data Sets Learning[C]// International Conference on Intelligent Computing. Hefei： Springer， 2005： 878-887.

[7]古平，歐陽(yáng)源遊.基于混合采樣的非平衡數(shù)據(jù)集分類研究[J].計(jì)算機(jī)應(yīng)用研究，2015，32（2）：379-381，418.

[8] BARUA S， ISLAM M， YAO X， et al. MWMOTE Majority Weighted Minority Oversampling Technique for Imbalanced Data Set Learning[J]. IEEE Transactions on Knowledge and Data Engineering，2014， 26（2）： 405-425.

[9] DOUZAS G， BACAO F， LAST F. Improving Imbalanced Learning through a Heuristic Oversampling Method Based on k-means and SMOTE[J]. Information Sciences， 2018，465：1-20.[10] BLAGUS R， LUSA L. SMOTE for High-dimensional Class-imbalanced Data[J].BMC Bioinformatics， 2013，14（1）：106.

[11]于維揚(yáng).社交網(wǎng)絡(luò)中垃圾內(nèi)容過(guò)濾方法研究[D].大連：大連理工大學(xué)，2016.

[12] ESTER M， KRIEGEL H P， SANDER J， et al. A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[C]// 2nd International Conference on Knowledge Discovery and Data Mining. Portland： AAAI， 1996： 226-231.

[13]李陽(yáng)，馬驪，樊鎖海.基于動(dòng)態(tài)近鄰的DBSCAN算法[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（20）：80-85.

[14]顧亞祥，丁世飛.支持向量機(jī)研究進(jìn)展[J].計(jì)算機(jī)科學(xué)， 2011，38（2）：14-17.

[15]楊揚(yáng)，李善平.基于實(shí)例重要性的SVM解不平衡數(shù)據(jù)分類[J].模式識(shí)別與人工智能，2009，22（6）：913-918.