基于密度峰值聚類算法的自適應加權過采樣算法

穆偉蒙，宋 燕，竇 軍

（1 上海理工大學 理學院，上海 200093；2 上海理工大學 光電信息與計算機工程學院，上海 200093）

0 引言

數據不平衡問題在許多應用，如醫療診斷、人臉識別和網絡詐騙等領域都受到了廣泛關注。不平衡問題是指不同類別的樣本數量差距很大，樣本數量多的類別稱為多數類，樣本數量少的類別稱為少數類。一般來說，少數類樣本包含很多有用的信息，如果沒有很好的分類，可能會付出很大的代價。因此，提高少數類的識別精度至關重要。

解決不平衡問題的方法可以分為2 類：基于數據的和基于算法的。其中，算法層面的策略包括代價敏感學習、單類學習、集成學習等，主要通過修改現有算法來提高對少數類樣本的分類精度。數據層面的策略包括過采樣技術和欠采樣技術，通過調節多數類或者少數類的樣本數量使不同類別的樣本趨于平衡。總地說來，欠采樣技術能夠減少多數類樣本來使類趨于平衡，容易實現，但易造成有用信息的丟失。而過采樣技術既能使不同類別樣本達到平衡，又能保留原始數據的分布特點，所以過采樣在處理不平衡數據分類方面得到了更多的關注。

由于過采樣技術應用更為廣泛，因此有學者提出了許多過采樣方法，如，為了解決隨機過采樣技術可能會造成的過擬合問題，Chawla 等人提出了合成少數類過采樣技術（Synthetic minority oversampling technique，SMOTE），其原理為：對于任意一個目標少數類樣本x，利用歐式距離隨機選取x的其中一個近鄰樣本x，通過線性插值，人工合成樣本x，即：

其中，∈ [0，1] 。

雖然SMOTE 在一定程度上克服了過擬合問題，并解決了類間不平衡，但是SMOTE 合成樣本時，對于所有的少數類樣本，采用統一的樣本分配策略合成新的樣本，很容易造成類內不平衡，改變原始數據的分布。

為了解決上述問題，學者提出了加權過采樣方法，為不同的子簇或者樣本分配不同的權重，來解決類間不平衡和類內不平衡問題。He 等人提出了自適應合成過采樣（ADASYN）方法，來對每個少數類樣本賦予不同的權值，而權值越大，學習難度就越大。Nekooeimehr 等人提出自適應半無監督加權過采樣方法（A-SUWO），通過利用分類復雜度和交叉驗證來自適應地確定每個子簇的過采樣大小。Douzas 等人提出基于K 近鄰（KNN）過采樣算法（SMOM）來給每個目標樣本的近鄰分配選擇權重，對可能會產生過度泛化的方向賦予較小的選擇權重。此外，為了增強邊界少數類樣本的學習，安全水平過采樣（Safe-Level-SMOTE）算法、邊界過采樣（Borderline-SMOTE）算法和多數加權少數的過采樣（MWMOTE）即已陸續提出。雖然如上研究通過不同的方法對少數類樣本賦予一定的權重，但卻沒有充分考慮少數類樣本權重分配所必須的因素，如樣本間的相似性、樣本分布特點等，這也是本文的主要研究背景。

針對上述問題，本文提出了一種基于密度峰值聚類算法的自適應加權過采樣算法（DPCOTE）來解決不平衡分類問題。該方法核心思想為：

（1）利用k 近鄰算法去除多數類和少數類噪聲樣本。

（2）基于密度峰值聚類算法中的重要因子，為每個少數類樣本賦予采樣權重，以此來為少數類樣本合成不同數量的新樣本。

（3）在DPC 算法中，引入馬氏距離，來消除樣本特征間量綱不一致的問題。

1 基于密度峰值加權過采樣方法

1.1 馬氏距離

馬氏距離是由印度統計學家Mahalanobis 提出的，馬氏距離考慮了各個特征變量之間的聯系，且不受特征量綱不一致的干擾。馬氏距離與歐氏距離的關系示意如圖1 所示。由圖1 可知，在計算歐式距離時，與距離最近，但是在馬氏距離中，與距離最近，因為原始數據呈現橢圓分布，歐氏距離沒有考慮數據分布。馬氏距離除以協方差矩陣，可以把各個分量之間的方差都除掉，消除了量綱性，詳見圖1（b）。

圖1 馬氏距離與歐氏距離示意圖Fig.1 The schematic diagram of Mahalanobis distance and Euclidean distance

如果協方差矩陣是單位矩陣，則馬氏距離等同于歐氏距離。

1.2 密度峰值聚類算法

密度峰值聚類算法（Density peaks clustering algorithm，DPC）由Rodriguez 等人于2014 年提出。該算法無須迭代就可確定聚類中心，且能夠識別任意形狀的類簇，目前已經得到了廣泛的應用。DPC 算法的核心思想建立在2 個基本假設上：

（1）聚類中心被局部密度較低的鄰域點包圍。

（2）密度較高的點之間的距離相對較大。

基于這2 個假設，DPC 引入了2 個重要因子，即目標樣本的局部密度ρ和相對距離δ。對于第一個假設，利用高斯核函數計算任一樣本點x的局部密度ρ，其值可由如下公式計算得出：

其中，d為樣本x和x之間的距離，d為截斷距離，通常將其設為距離降序排列的1%～2%。

DPC 算法示意如圖2 所示。在確定了截斷距離后，就可以得到目標樣本的局部密度，如樣本點，，。對于第二個假設，通過計算相對距離，即對于任一樣本點x，其局部密度比其更大、且距離最近的樣本點x的距離δ可表示為：

圖2 DPC 算法示意圖Fig.2 The schematic diagram of DPC

在計算出所有樣本的因子后，如果樣本的ρ和δ足夠大，其附近樣本分布較為密集，則將其視為密度峰值。

1.3 DPCOTE 方法

在本節，提出了新的基于密度峰值聚類算法的過采樣算法（DPCOTE）。該算法中，使用馬氏距離代替DPC 算法涉及到的歐氏距離。該算法主要步驟可闡釋分述如下：

（1）去噪。在數據預處理階段，使用k 近鄰算法去除噪聲樣本。在此階段中，對所有的樣本使用k 近鄰算法。先是計算目標樣本與近鄰樣本的距離，找到目標樣本的個近鄰。如果目標樣本的個近鄰樣本的類標簽與目標樣本的類標簽都不一樣，則將目標樣本歸為噪聲樣本，并刪除。

（2）合成樣本。利用DPC 算法對所有少數類樣本賦予采樣權重，來確定每個少數類樣本需要合成的樣本數，并使用k 近鄰算法和線性插值來對每個少數類樣本合成新樣本。

和傳統的DPC 算法不同的是，本文在計算任意2 個樣本的距離時，使用馬氏距離代替歐氏距離，這樣就解決了特征間量綱不一問題。所以，利用上述描述的DPC 算法，基于馬氏距離，可以得到每個少數類樣本的局部密度ρ和到局部密度較高的最近鄰的距離δ（1，2，…，），此處的表示少數類樣本數。

下面，利用ρ和δ來確定每個少數類樣本的采樣權重。為此，先對這2 個因子做歸一化，即：

綜合上述2 個因子，考慮到每個少數類樣本的密度信息和相對距離信息，為此構造一個新的因子，即：

事實上，如果樣本的密度較大，基于該樣本合成新樣本時，會生成較多重復的樣本，導致模型過擬合。所以，每個少數類樣本需要合成的樣本數與密度成反比，具體數學公式如下：

將其標準化來確定第個少數類樣本的采樣權重為：

若給定為需要合成的少數類樣本總數，則第個少數類樣本需要合成的樣本數可以通過下式得到：

確定每個少數類樣本的合成數后，利用k 近鄰算法和線性插值來合成新的樣本，使少數類樣本與多數類樣本達到相對平衡。圖3 為ADASYN 算法和本文提出DPCOTE 算法生成的樣本分布示意圖。圖3 中，表示多數類樣本，表示少數類樣本，表示新合成的少數類樣本。由于ADASYN 算法對于學習難度高的樣本賦予更高的權重，所以其在邊界附近合成了更多的樣本，容易模糊類邊界，DPCOTE 算法考慮每個少數類樣本的分布情況，在不改變原始數據分布的情況下，生成更多有用的新樣本。圖4 給出了DPCOTE 算法的流程圖，相應算法的偽代碼設計表述具體如下。

圖3 合成樣本分布示意圖Fig.3 The schematic diagram of synthetic sample distribution

圖4 DPCOTE 算法流程圖Fig.4 Flow chart of DPCOTE

2 實驗結果及分析

2.1 數據集

為了更加全面地驗證DPCOTE 算法的性能，本文從UCI 機器學習庫中選取了12 組二類不平衡數據集，這些數據集樣本數量和特征數量都不同，且不平衡率的范圍為2.78～22.7。表1 為本文選用的數據集。

表1 數據集信息Tab.1 Information of the datasets

2.2 評價指標

在不平衡分類問題中，分類器通常偏向多數類樣本，不能反映少數類的分類精度，而少數類的識別精度往往很重要，因此分類精度不適用于不平衡數據。和通常用來評價模型的性能，此處需涉及的數學公式可寫為：

其中，表示預測和真實都為少類的樣本數；表示預測與真實都為多類的樣本數；表示少類預測為多類的樣本數；表示多類預測為少類的樣本數。

2.3 實驗分析

為了驗證本文提出的采樣方法的有效性，將SMOTE、Safe-Level-SMOTE（SLS）、Borderline-SMOTE（BS）、ADASYN、CBSO 與本文提出的DPCOTE 算法進行了對比實驗。此外，使用邏輯回歸（LR）和支持向量機（SVM）兩個分類器來驗證DPCOTE 算法的泛化能力。所描述的實驗均采用5折交叉驗證，每組數據重復5 次，記錄每個評估指標的平均值，以消除數據隨機分組時可能出現的偏差。最好的結果以粗體字突出顯示。每次實驗都在2.9 GHz CPU、8 GB 內存的電腦上進行，軟件環境是Python 3.7。其中，，是和的縮寫。

表2 顯示了使用LR 分類器，所提出的DPCOTE算法在和方面與典型對比算法之間的性能比較。由表2 可知，DPCOTE 算法的表現遠遠好于對比的過采樣方法。具體來說，在指標方面，12 個數據集中，DPCOTE 算法有9 個數據集取得了最好的結果；在指標方面，有7 個數據集取得了最好的結果。

表2 在LR 分類器上的對比結果Tab.2 Comparison results on LR

圖5 為使用LR 分類器，數據yeast4 在指標和上的箱線圖結果，箱線圖包括一個矩形箱體和上下2 條線，箱體中間的線為中位線，上、下限分別為數據的上四分位數和下四分位數，箱子的寬度可以體現數據的波動程度，箱體的上、下方各有一條線是數據的最大、最小值，超出最大、最小值線的數據為異常數據。從圖5（a）中可以看出，雖然DPCOTE 算法數據波動較大，但數據的中值和上、下四分位數是優于對比算法的。在圖5（b）中，DPCOTE 算法的中值和上、下四分位數是相對較好的，在箱體寬度方面，除了ADASYN 算法，DPCOTE 算法的數據波動優于其它方法，但是ADASYN 算法存在異常值。圖6 為使用SVM 的可視化，結果顯示DPCOTE 算法的中值和上、下四分位數是大于對比算法的。

圖5 使用LR 分類器數據yeast4 的箱線圖Fig.5 A boxplot using LR on yeast4

圖6 使用SVM 分類器數據yeast4 的箱線圖Fig.6 A boxplot using SVM on yeast4

為了全面對比本文提出的算法與其他采樣方法在性能上的有效性，研究中使用了Wilcoxon 符號秩檢驗來評估DPCOTE 算法與對比算法之間是否有顯著性差異。表3 為使用LR，SVM 分類器，在和的Wilcoxon 符號秩檢驗的結果，其中表示DPCOTE 算法的秩和，-表示相應對比方法的秩和。從表3 中可以觀察到，在使用LR 分類器、顯著性水平為0.05 的情況時，除了DPCOTE 算法與Borderline-SMOTE 在對比的值大于0.05 以外，大部分原假設都被拒絕，而且的值遠大于-，說明DPCOTE 算法和其他采樣方法相比有顯著性差異。從表3 可以看出，在使用SVM 分類器時，DPCOTE 算法在和方面的表現好于對比算法。使用LR，SVM 分類器的Wilcoxon 實驗結果見表4。使用SVM 分類器的Wilcoxon 檢驗的結果顯示，除了DPCOTE 算法與Borderline-SMOTE 在下接受原假設外，所有的原假設都被拒絕，表明DPCOTE 算法顯著優于其他對比算法。

表3 在SVM 分類器上的對比結果Tab.3 Comparison results on SVM

表4 使用LR，SVM 分類器的Wilcoxon 實驗結果Tab.4 Wilcoxon experimental results on LR，SVM

3 結束語

本文提出了一種基于密度峰值聚類算法的自適應加權過采樣算法、即DPCOTE 算法來解決不平衡分類問題。DPCOTE 算法的基本思想為：考慮了類內不平衡問題，利用密度峰值聚類算法中的2 個重要因子，為每個少數類樣本賦予采樣權重，從而使每個少數類樣本合成不同數量的新樣本。同時，在DPC 算法中，引入馬氏距離代替歐氏距離，消除特征間量綱不一致的問題。為了驗證該算法的有效性，在和指標下，使用LR 和SVM 分類器進行了對比試驗，且使用Wilcoxon 檢驗對結果進行分析。試驗結果表明，DPCOTE 算法在12 個大小、不平衡率不同的數據集上取得了較好的結果。