基于密度峰值聚類的不平衡數據過抽樣方法

張智駒

（重慶航天職業技術學院 智能信息工程學院，重慶 400021）

0 引言

數據分類是數據挖掘、機器學習的主要任務[1]。數據分類的基本思想是用一個數據挖掘模型，通過學習帶標記的數據，對未帶標記的數據進行類別識別。然而，在實際應用中，數據類別的分布通常是不均衡的。其中一個類別的樣本數量會遠小于其他類別的樣本數量。學者們通常把類別分布不均衡的數據集稱為不平衡數據集，并且把對不平衡數據集的分類任務稱為不平衡分類[2]。

Chawla 等（2002）[3]把處理不平衡分類的方法歸為兩類：算法水平方法[4]和數據水平方法[5]。在算法水平方法中，學者們通常依據不平衡數據集的特性來改進分類算法的目標函數。IFROWANN[4]是一個相對較新的算法水平方法。相比于算法水平方法，數據水平方法由于是更簡單有效的數據預處理技術，因此受到了學者們的青睞并得到廣泛應用。欠抽樣技術[5]和過抽樣技術[6]是兩個最主要的數據水平方法。本文主要關注過抽樣技術。

SMOTE[6]是最經典的過抽樣技術。Cluster-SMOTE[7]是SMOTE的改進，其用k-means聚類[8]算法把不平衡數據集劃分為k個子簇，然后在每個子簇上執行SMOTE，從而生成少數類的合成樣本。DBSMOTE[9]是基于DBSCAN 聚類[10]的過抽樣技術，其在不平衡數據集上構造一個密度可達圖，然后用密度可達圖來生成少數類合成樣本。MWMOTE[11]和NI-MWMOTE[12]是基于凝聚層次聚類（Agglomerative Hierarchical Clustering，AHC）的過抽樣技術，其用AHC 把不平衡數據集劃分為多個子簇，然后利用近鄰規則在邊界區域上生成更多的少數類合成樣本。RSMOTE[13]和Adaptive-SMOTE[14]是較新的過抽樣技術，RSMOTE利用k-means 聚類和相對密度在高密度區域上生成少數類合成樣本；Adaptive-SMOTE 利用近鄰規則來計算“inner”子集和“danger”子集，然后利用這兩個子集來生成靠近邊界區域的少數類合成樣本。SMOTE-NaN-DE[15]是一個基于差分進化的過抽樣技術，其利用差分進化技術去優化合成樣本的屬性，目的是防止噪聲生成。雖然大量實驗證明了上述過抽樣技術的有效性，但是他們仍然存在以下問題：（1）大多數過抽樣技術依賴于2個或2個以上的參數，導致應用困難。（2）大多數過抽樣技術容易生成噪聲，并且不能移除不平衡數據集中的噪聲。（3）大多數過抽樣技術難以處理流形（非球形）數據集。

為了改進不平衡分類和解決現有過抽樣技術的缺陷，本文提出了一種基于密度峰值聚類的不平衡數據過抽樣方法（Oversampling Method based on Density Peaks Clustering，OVMEDPC）。OVMEDPC包含三個主要步驟：首先，用密度峰值聚類（DPC）[16]來發現不平衡數據集的空間結構；其次，設計一種基于DPC的噪聲過濾方法來移除噪聲；最后，設計一種基于DPC的插值技術來生成少數類的合成樣本。OVMEDPC 的優勢如下：（1）OVMEDPC 僅需要一個參數；（2）OVMEDPC能夠移除不平衡數據中的噪聲，從而防止噪聲生成；（3）OVMEDPC能夠處理球形或者非球形（流形）的數據集。本文使用11個來自各個領域的真實數據集，通過與5個先進的過抽樣技術的對比來證明OVMEDPC的有效性。經仿真實驗證明，在改進隨機森林分類器的F-measure和G-mean上，OVMEDPC在廣泛的真實數據集上優于對比方法。

1 理論基礎

1.1 主要符號和術語

本文使用的主要符號和術語如下：

設Ximb={x1,x2,…,xn}為不平衡數據集的樣本集合。并設n為Ximb中的樣本個數，D為Ximb中的樣本屬性個數。Ximb=Xmin∪Xmaj。設Xmin={x1,x2,…,xnmin}為少數類的樣本集合，nmin為Xmin中的樣本個數。設Xmaj={x1,x2,…,xnmaj}為多數類的樣本集合，nmaj為Xmaj中的樣本個數。n=nmin+nmaj。本文關注不平衡二分類問題。在不平衡數據集中，nmin遠小于nmaj。設L={Lmin,Lmaj}為類標簽集合，Lmin為少數類的類標簽，Lmaj為多數類的類標簽。

函數dist(xi,xj)代表樣本xi和樣本xj之間的歐氏距離，p(xi)代表樣本xi的密度，δ(xi)代表樣本xi的偏移距離，R(xi)代表樣本xi的決策值，LN(xi)代表樣本xi的局部鄰域，Noise={xi,…}代表噪聲樣本的集合，SubCluster={sc1,sc2,…,scc}代表被DPC劃分的子簇集合，U={u1,u2,…,uc}代表每個子簇的簇中心集合，c代表子簇或子簇中心個數。

1.2 密度峰值聚類

Rodriguez 和Laio（2014）[16]提出了密度峰值聚類DPC（Density Peaks Clustering）算法。與凝聚層次聚類AHC 和k-means 聚類相比，DPC 能夠處理球形和非球形數據集。DPC基于如下兩個假設來發現聚類中心：

假設1：聚類中心應該是一些高密度樣本。

假設2：聚類中心之間的距離應該盡可能大。

DPC用式（1）和式（2）來計算每個樣本的密度：

在式（1）中，函數dist(xi,xj)代表樣本xi和樣本xj之間的歐氏距離。從式（1）和式（2）可以看出，樣本xi的密度p(xi)是與樣本xi的距離小于dc的樣本個數。dc是一個截距值，學者們通常用式（3）來計算dc。

在式（3）中，n為樣本個數。接下來，DPC 用式（4）來計算每個樣本的偏移距離：

如果樣本xi具有一個較大的偏移距離δ(xi)，那么樣本xi離其他高密度樣本較遠。基于假設1和假設2，以及式（1）至式（4），DPC把具有高密度且具有高偏移距離的樣本作為聚類中心。DPC定義樣本xi的決策值R(xi)為：

R(xi)=p(xi)×δ(xi) （5）

樣本xi的R(xi)是密度p(xi)和偏移距離δ(xi)的綜合值。如果樣本xi具有一個較大的決策值R(xi)，那么這個樣本xi具有較高的密度p(xi)或較高的偏移距離δ(xi)。最后，DPC把剩余樣本分配到離它最近且密度更高的樣本的所屬簇中。DPC算法的偽代碼如算法1所示。

算法1：DPC（密度峰值聚類）算法。

輸入：輸入數據X，聚類數目c。

輸出：子簇的集合SubCluster={sc1,sc2,…,scc}，簇中心集合U={u1,u2,…,uc}。

步驟1：fori=1 to |X|；

步驟2：用式（1）至式（3）來計算p(xi)；

步驟3：用式（4）來計算偏移距離δ(xi)；

步驟4：用式（5）來計算R(xi)；

步驟5：end for；

步驟6：從大到小對決策值R={R(x1),R(x2),…,R(x|X|)}排序；

步驟7：選取前c個R值所對應的樣本，并把他們作為聚類中心U={u1,u2,…,uc}，形成初始簇SubCluster={sc1,sc2,…,scc}；

步驟8：把非中心樣本分配到離它最近且密度更高的樣本的所屬簇中；

步驟9：return SubCluster，U。

DPC 需要設置1 個參數，即聚類數目c。依據文獻[16]的分析，DPC 算法的時間復雜度為O(n2)。更多的關于DPC的細節，可參考文獻[16]。

2 基于密度峰值聚類的不平衡數據過抽樣方法

本文提出OVMEDPC 的目的是生成少數類的合成樣本，從而改進不平衡分類。并且它能解決現有過抽樣技術的缺陷：（1）依賴于太多參數；（2）容易生成噪聲；（3）難以處理流形數據集。OVMEDPC 包含三個主要步驟：（1）用DPC 來發現不平衡數據集的空間結構；（2）設計一種基于DPC 的噪聲過濾方法來移除噪聲；（3）設計一種基于DPC的插值技術來生成少數類的合成樣本。此外，OVMEDPC能用少數類的合成樣本來改進不平衡數據集的類別分布，并能用改進的數據集來提高不平衡分類的性能。OVMEDPC的流程圖如下頁圖1所示。

圖1 OVMEDPC的流程圖

2.1 用密度峰值聚類發現不平衡數據的空間結構

OVMEDPC 用DPC 算法把不平衡數據集劃分為c個子簇，并且發現不平衡數據的空間結構。在每個子簇中，依據DPC 的非中心樣本的分配策略（算法1 的步驟8）[16]，OVMEDPC讓每個樣本指向離它最近且密度更高的樣本，如下頁圖2所示。

圖2 用一個人工例子來說明OVMEDPC如何用DPC去發現不平衡數據集的空間結構（c=2）

圖2顯示，在不平衡數據上，OVMEDPC能利用DPC來形成一個類似于圖的空間結構。在這個空間結構中，每個樣本指向離它最近且密度更高的樣本。本文用Point來代表所有樣本在DPC中的指向結構。例如，在圖2中，樣本A指向樣本B，因此，Point(A)=B。

2.2 基于密度峰值聚類的噪聲過濾方法

OVMEDPC 設計了一種基于DPC 的噪聲過濾方法。OVMEDPC先用式（6）計算樣本xi的局部鄰域LN(xi)。

基于被DPC發現的空間結構（見圖2），樣本xi的局部鄰域包含指向樣本xi的樣本（即{xj|Point(xj)==xi}）、被樣本xi指向的樣本（即{xj|Point(xi)==xj}）和樣本xi。圖3用一個人工例子來說明樣本xi的局部鄰域LN(xi)。樣本A 的局部鄰域包含樣本B、樣本C 和樣本A，這是因為樣本B和樣本C指向樣本A。樣本D的局部鄰域包含樣本E、樣本F和樣本D，這是因為樣本E指向樣本D，并且樣本D指向樣本F。注意，樣本A 和樣本D 是噪聲樣本，這是因為他們與周圍的大多數樣本有不同的類標簽。

圖3 用一個人工例子來說明一個樣本的局部鄰域和基于DPC的噪聲過濾方法

接下來，依據式（6），OVMEDPC用式（7）去識別噪聲。

在式（7）中，l(xi)和l(xj)分別代表樣本xi和樣本xj的類標簽，Noise代表噪聲樣本的集合。依據式（7），如果樣本xi是噪聲，那么樣本xi將會被它的局部鄰域LN(xi)誤分類。顯而易見，式（7）能將圖3中的樣本A和樣本D識別為噪聲。與存在的噪聲過濾方法相比，OVMEDPC中的噪聲過濾技術有如下優勢：（1）它是無參數的；（2）它適用于球形或非球形（流形）數據。這是因為OVMEDPC 用被DPC發現的空間結構（即Point）來識別噪聲。被DPC發現的空間結構能有效地顯示球形或非球形的數據分布。

2.3 基于密度峰值聚類的插值技術

OVMEDPC 設計了一種基于DPC 的插值技術去生成少數類的合成樣本。OVMEDPC把不平衡數據集劃分為c個子簇SubCluster={sc1,sc2,…,scc}，從而得到c個簇中心U={u1,u2,…,uc}。在每個子簇中，OVMEDPC 用式（8）去生成少數類的合成樣本。

在式（8）中，New代表新生成的少數類的合成樣本；ui代表第i個子簇sci的簇中心；xj是子簇sci中的樣本，xj也是被選定的基樣本；rand(0,1)返回0 到1 之間的隨機值；d代表第d個屬性（d=1,2,…,D）。依據式（8），新生成的合成樣本是用選定的基樣本xj和簇中心ui在每個屬性上的隨機插值生成的。與存在的插值方法相比，OVMEDPC 的插值技術有如下優勢：（1）它是無參數的；（2）由于簇中心位于高密度的類中心區域（不是邊界區域）且能代表每個簇的分布，因此OVMEDPC的插值技術能有效地防止噪聲生成和強化每個簇的分布特性（見圖3）。

2.4 OVMEDPC的偽代碼和特性分析

OVMEDPC的偽代碼如算法2所示。

算法2：OVMEDPC

輸入：少數類的樣本集合Xmin，多數類的樣本集合Xmaj，聚類數目c。

輸出：少數類的合成樣本集合SyntheticSamples。

步驟1：Ximb=Xmin∪Xmaj；

步驟2：SyntheticSamples=?；

步驟3：[SubCluster,U]=DPC(Ximb,c)，用DPC把不平衡數據集Ximb劃分為c個子簇；

步驟4：在每個子簇sci?SubCluster中，讓每個樣本指向離它最近且密度更高的樣本，從而形成一個類似于圖2或圖3的空間結構，并得到Point；

步驟5：?xi?Ximb，用式（6）和式（7）去識別噪聲Noise；

步驟6：從不平衡數據集Ximb中刪除噪聲Noise，并更新集合Ximb=Ximb-Noise和SubCluster；

步驟7：Num=nmaj-nmin;

步驟8：N=1；

步驟9：whileN≤Num；

步驟10：for ?sci?SubCluster；

步驟11：發現簇sci的簇中心ui；

步驟12：for ?xj?sci；

步驟13：把樣本xj視為一個基樣本；

步驟14：用式（8）去生成少數類的合成樣本New；

步驟15：end for；

步驟16：SyntheticSamples=SyntheticSamples∪{New}；

步驟17：N=N+1;

步驟18：end for；

步驟19：end while；

步驟20：returnSyntheticSamples。

通過算法2的步驟3和步驟4，OVMEDPC用DPC把不平衡數據集劃分為c個子簇，并且形成了一個類似于圖的空間結構（見圖2 和圖3）。通過算法2 的步驟5和步驟6，OVMEDPC用基于DPC的噪聲過濾技術來移除不平衡數據集中的噪聲。通過算法2的步驟7至步驟19，OVMEDPC用簇中心ui和該簇中的基樣本xj（xj?sci）去生成少數類的合成樣本SyntheticSamples。變量Num和變量N控制了合成樣本的數目。由于最耗時的步驟是步驟3（時間復雜度是O(n2)），因此OVMEDPC 的時間復雜度為O(n2)。最后，OVMEDPC 把少數類的合成樣本SyntheticSamples加入無噪聲的不平衡數據集中，從而改進其類別分布。

圖4用人工數據集展示了OVMEDPC的算法過程。圖4和算法2證明，OVMEDPC具有如下優勢：（1）它僅需一個參數c；（2）它能有效地防止噪聲生成，并且能移除原始數據集中的噪聲；（3）它能有效地處理球形和非球形數據集。

圖4 用人工數據集來展示OVMEDPC的算法過程

3 仿真實驗

3.1 實驗設置

為了驗證OVMEDPC 的有效性，本文從UCI（http://archive.ics.uci.edu/ml/index.php）公開數據庫中選取11 個真實數據集來作為實驗的數據集。表1 描述了實驗數據集的特性（屬性數、少數類樣本數、多數類樣本數、不平衡比和應用領域）。

表1 實驗的數據集

本文通過與5 個先進的過抽樣技術進行對比來證明OVMEDPC 的性能。表2 描述了對比算法及其參數。SMOTE[6]和Cluster-SMOTE[7]是經典的過抽樣技術，MW-MOTE[11]、NI-MWMOTE[12]和SMOTE-NaN-DE[15]是相對較新的過抽樣技術。本文把對比算法的參數設置為他們的標準版本。在實驗中，本文建議把OVMEDPC的參數c設置為2～10。從表2可以看出，相比于對比算法，OVMEDPC 依賴于更少的參數。

表2 用于對比的過抽樣技術

3.2 實驗指標

在每個真實數據集上，本文用十折交叉驗證來劃分訓練集和測試集。全部實驗重復十折交叉驗證10 次。另外，本文把F-measure 和G-mean 作為評估指標。F-measure是召回率Recall和精確度Precision的調和平均。召回率Recall 和精確度Precision 的公式如式（9）和式（10）所示。TP 代表被模型預測為正例的正例樣本數，FP 代表被模型預測為正例的負例樣本數，TN和FN分別代表被模型預測為負例的負例樣本數和被模型預測為負例的正例樣本數。本文把少數類樣本視為正例，同時把多數類樣本視為負例。F-measure 和G-mean 的公式如式（11）和式（12）所示。一個算法的F-measure越高，代表該算法能把少數類分類得越準確。一個算法的G-mean越高，代表該算法的總的分類性能越好。本文把隨機森林分類器作為測試的分類器（集成分類器的數目為10）。換句話說，實驗首先用對比的過抽樣技術來改進不平衡數據集，然后用被改進的不平衡數據集來訓練隨機森林分類器，最后用F-measure和G-mean來評估隨機森林分類器。

3.3 真實數據集實驗

表3 展示了對比過抽樣技術在真實數據集上的平均F-measure（10次實驗）。表4展示了對比過抽樣技術在真實數據集上的平均G-mean（10次實驗）。

表3 對比過抽樣技術訓練隨機森林分類器的平均F-measure （單位：%）

表4 對比過抽樣技術訓練隨機森林分類器的平均G-mean （單位：%）

從表3 可以看出，就平均F-measure 而言，OVMEDPC在9個數據集上優于對比方法。從表4可以看出，就平均G-mean 而言，OVMEDPC 在7 個數據集上優于對比方法。此外，表3和表4的“平均值”欄也證明，OVMEDPC能在所有數據集上取得最高的平均F-measure和平均G-mean。

為了進一步證明OVMEDPC 的有效性，本文用Wilcoxon秩和檢驗（顯著性水平為0.05）分析表3和表4。表3和表4 的“Wilcoxon”欄展示了Wilcoxon 秩和檢驗的結果。如果OVMEDPC顯著優于該欄上的對比方法，那么該欄上的值為“+”；如果OVMEDPC顯著差于該欄上的對比方法，那么該欄上的值為“-”；如果OVMEDPC 與該欄上的對比方法無顯著差別，那么該欄上的值為“=”。表3 和表4 的“Wilcoxon”欄證明，OVMEDPC顯著優于對比方法。

表3 和表4 證明，就隨機森林分類器而言，在F-measure和G-mean上，OVMEDPC顯著優于5個先進的過抽樣技術。

3.4 驗證對比方法的平均運行時間

經算法2分析，OVMEDPC的時間復雜度為O(n2)。圖5展示了對比方法在2個真實數據集上的平均運行時間（5次實驗）。從圖5 可以看出，OVMEDPC 快于MWMOTE、NI-MWMOTE 和SMOTE-NaN-DE，慢于SMOTE 和Cluster-SMOTE。原因如下：（1）MWMOTE 和NI-MWMOTE 的時間復雜度至少是O(n3)（因為他們所使用的層次聚類AHC的時間復雜度是O(n3)），且高于OVMEDPC的時間復雜度O(n2)；（2）由于SMOTE-NaN-DE 中的差分進化是一個復雜的迭代算法，因此當迭代次數過高的時候，SMOTE-NaN-DE將相對耗時且慢于OVMEDPC；（3）SMOTE 和Cluster-SMOTE的時間復雜度是O(nlogn)，且優于OVMEDPC的時間復雜度O(n2)。

圖5 對比方法在2個真實數據集上的平均運行時間

盡管OVMEDPC 慢于SMOTE 和Cluster-SMOTE，但考慮到OVMEDPC 能比SMOTE和Cluster-SMOTE得到更高的隨機森林分類器的F-measure 和G-mean，且不平衡數據過抽樣方法主要用于中小型規模的數據集（OVMEDPC 中的時間復雜度O(n2)已經足夠適用于這種數據集），因此OVMEDPC中的時間復雜度O(n2)仍是具有優勢的和可以接受的。

4 結束語

為了改進不平衡分類的性能和克服現有過抽樣技術的缺陷，本文提出了一種基于密度峰值聚類的過抽樣方法（OVMEDPC）。首先，OVMEDPC 用密度峰值聚類算法來發現不平衡數據集的空間結構，并形成若干子簇；其次，OVMEDPC 設計了一個基于密度峰值聚類的噪聲過濾技術來識別和過濾掉不平衡數據集中的噪聲；最后，OVMEDPC 設計了一個基于密度峰值聚類的插值技術來生成少數類的合成樣本。為了驗證OVMEDPC的有效性，本文用2 個人工數據集、11 個來自各個領域的真實數據集，通過與5個先進的過抽樣技術的對比來進行實驗。通過理論，通過與實驗的驗證，OVMEDPC 具有如下優勢：（1）OVMEDPC 僅需要一個參數c；（2）OVMEDPC 能夠移除不平衡數據中的噪聲，從而防止噪聲生成；（3）OVMEDPC能夠處理球形或者非球形（流形）數據集；（4）就隨機森林分類器而言，在F-measure 和G-mean 上，OVMEDPC 顯著 地 優 于SMOTE、Cluster-SMOTE、MWMOTE、NI-MWMOTE和SMOTE-NaN-DE；（5）OVMEDPC擁有這個領域可接受的時間復雜度O(n2)，且在平均運行時間上快于MWMOTE、NI-MWMOTE和SMOTE-NaN-DE。