基于DBSCAN改進的SMOTE算法

邱燦華 吳杰

摘要：針對傳統的合成少數類過采樣技術（Synthetic Minority Oversampling Technique，SMOTE）中存在的忽略類間不平衡、類內不平衡、無法控制合成樣本的噪聲等問題，結合DBSCAN聚類算法，提出了一種基于DBSCAN改進的SMOTE算法：使用DBSCAN算法對少數類樣本進行聚類，計算少數類密度系數和采用權重為每個簇分配采樣數量，將每個簇中樣本點按照到簇質心的距離分為2類，對每類中的樣本點分配不同的隨機系數進行過采樣，得到新的較為平衡的數據集。根據獲取的數據集進行實驗表明，改進的算法可以很好地改善分類器的分類性能。

關鍵詞：SMOTE算法；DBSCAN算法；不平衡數據集；過采樣

中圖分類號：TP181文獻標志碼：A文章編號：1008-1739（2022）07-62-5

0引言

旅游在線評論是文本情感分析的一種重要的信息來源，對游客選擇旅游目的地以及幫助旅游地改善其旅游產品或服務都有非常好的現實意義[1]。然而在實際研究中，評論數據集大多是不平衡的。不平衡數據是指類分布不平均的數據，樣本數目多的類被稱為多數類，數目少的被稱為少數類[2]。在分類算法中，數據集的不平衡會導致傳統分類器的準確率偏向于多數類，而在不平衡類中，少數類包含更多有用的信息，對分析結果會產生更大影響[3]。在現實中，少數類樣本的預測結果往往才是人們關注的重點，如旅游評論分析中，少數的差評比多數的好評更有研究意義[4]。

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

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

1基本原理

1.1 SMOTE算法

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

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

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

1.2 DBSCAN聚類算法

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

DBSCAN算法存在以下2個關鍵參數：Epsilon表示在一個點周圍鄰近區域的半徑；MinPts表示鄰近區域內至少包含點的個數[11]。

DBSCAN聚類算法與K-means聚類算法相比，最大優勢是能夠識別任意形狀的聚類簇，并且可以在聚類時發現異常點，過濾噪聲點，同時聚類結果沒有大的偏差，K-means聚類算法的結果與初始值有很大的關系[12]。

2基于DBSCAN改進的SMOTE算法

針對SMOTE過采樣算法存在的不足，如無法控制合成樣本的質量、容易導致類邊界的模糊等問題，本文結合DBSCAN算法良好的聚類性能，對傳統的SMOTE算法進行一定的改進，提出一種基于DBSCAN的改進的SMOTE算法。

2.1類不平衡率與采用樣重

DTCSMOTE算法主要是將同一聚類簇內的少數類樣本按照到質心的距離分為遠離質心類與接近質心類，針對遠離質心類中的樣本，在遠離質心的一端合成新的樣本；針對接近質心類中的樣本，在接近質心的一端合成新的樣本，試圖以不同的隨機數去改善少數類的類間不平衡性。

2.3 DB-DTCSMOTE過采樣算法

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

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

Output：合成的少數類樣本集。

步驟2：計算簇的少數類樣本密度系數（ ）。

步驟3：計算簇的采樣權重（ ），記為。

步驟4：計算簇需要合成的新樣本數量=×。

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

DB-DTCSMOTE與傳統的SMOTE算法相比存在很多優勢，使用DBSCAN算法對所有數據進行聚類可以有效剔除噪聲樣本，通過引入少數類樣本密度系數以及采樣權重，可以有效改善類間不平衡的問題；利用改進的DTCSMOTE算法合成新樣本，對遠離質心的樣本點與接近質心的樣本點分開進行合成，有效改善了SMOTE算法任意合成新樣本的弊端。

3實驗與分析

為了驗證算法的性能，利用從攜程旅游網站獲取的游客關于古鎮的評論作為原始數據集，分別使用Random-OverSampling，SMOTE，Borderline-SMOTE，ADASYN，DB-DTCSMOTE五種算法對原始數據集進行過采樣，得到新的較為平衡的數據集，并且使用SVM算法和KNN算法對數據進行分類，以驗證不同算法的性能優劣。

3.1原始數據集

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

3.2評價指標

機器學習有很多評價指標，實際上不同的評價指標就是用不同的方法來評價算法的好壞。對于回歸問題，通過mae，mse等指標就可以很好地衡量模型的好壞，但針對分類問題，僅僅通過準確率并不能很好地衡量模型的優劣，這時就要引入查準率、查全率、F1值來評價模型的性能[13]。

機器學習的評價指標建立在混淆矩陣之上，在混淆矩陣中有4個數據，其中，TP和TN分別表示正確分類的正類和負類的樣本數量；FN和FP分別表示錯誤分類的正類和負類的樣本數量[14]。

①準確率：所有正確預測（正類、負類）占總體的比重，準確率越高說明模型分類效果越好，準確率是衡量模型性能的重要指標。

②精確率（查準率）：即正確預測為正的占全部預測為正的比例。

③召回率（查全率）：即正確預測為正的占全部實際為正的比例。

④F1值為查準率和查全率的調和平均數，因為精確率和召回率指標有時候會出現矛盾的情況，就需要綜合考慮，最常見的方法就是F1-score[15]。

3.3實驗結果分析

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

①使用同一數據集，在SVM分類器得出的結果要優于KNN分類器，這歸功于SVM算法中的核函數。核函數的應用使得算法無需知道非線性映射的顯式表達式，由于SVM是在高維特征空間中構建的線性學習機，所以與線性模型相比，幾乎不增加計算的復雜性，而且在某種程度上避免了“維數災難”，使得SVM分類器的性能更加優異。

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

③為了驗證測試集比例對分類結果的影響，將測試集比例設為0.6，0.7，0.8，使用KNN和SVM分類DC-DTCSMOTE算法的性能表現分別如表3和表4所示。實驗數據顯示，對于DC-DTCSMOTE算法，測試集比例越高，無論是KNN還是SVM的分類結果的各項指標都有提升，測試集的比例對最終的分類結果存在一定的影響。

4結束語

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

參考文獻

[1]鄭文英.旅行目的地中文評論的情感分析研究[D].哈爾濱：哈爾濱工業大學，2010.

[2]石洪波，陳雨文，陳鑫.SMOTE過采樣及其改進算法研究綜述[J].智能系統學報，2019，14（6）：1073-1083.

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

[4]陳榮榮.基于GAN-XGBoost的信用卡交易欺詐檢測模型研究[D].杭州：杭州師范大學，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]古平，歐陽源遊.基于混合采樣的非平衡數據集分類研究[J].計算機應用研究，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]于維揚.社交網絡中垃圾內容過濾方法研究[D].大連：大連理工大學，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]李陽，馬驪，樊鎖海.基于動態近鄰的DBSCAN算法[J].計算機工程與應用，2016，52（20）：80-85.

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

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