基于密度峰值聚類的不平衡數(shù)據(jù)過抽樣方法

張智駒

（重慶航天職業(yè)技術(shù)學(xué)院 智能信息工程學(xué)院，重慶 400021）

0 引言

數(shù)據(jù)分類是數(shù)據(jù)挖掘、機器學(xué)習(xí)的主要任務(wù)[1]。數(shù)據(jù)分類的基本思想是用一個數(shù)據(jù)挖掘模型，通過學(xué)習(xí)帶標(biāo)記的數(shù)據(jù)，對未帶標(biāo)記的數(shù)據(jù)進行類別識別。然而，在實際應(yīng)用中，數(shù)據(jù)類別的分布通常是不均衡的。其中一個類別的樣本數(shù)量會遠(yuǎn)小于其他類別的樣本數(shù)量。學(xué)者們通常把類別分布不均衡的數(shù)據(jù)集稱為不平衡數(shù)據(jù)集，并且把對不平衡數(shù)據(jù)集的分類任務(wù)稱為不平衡分類[2]。

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

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

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

1 理論基礎(chǔ)

1.1 主要符號和術(shù)語

本文使用的主要符號和術(shù)語如下：

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

函數(shù)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代表子簇或子簇中心個數(shù)。

1.2 密度峰值聚類

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

假設(shè)1：聚類中心應(yīng)該是一些高密度樣本。

假設(shè)2：聚類中心之間的距離應(yīng)該盡可能大。

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

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

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

如果樣本xi具有一個較大的偏移距離δ(xi)，那么樣本xi離其他高密度樣本較遠(yuǎn)?；诩僭O(shè)1和假設(shè)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（密度峰值聚類）算法。

輸入：輸入數(shù)據(jù)X，聚類數(shù)目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值所對應(yīng)的樣本，并把他們作為聚類中心U={u1,u2,…,uc}，形成初始簇SubCluster={sc1,sc2,…,scc}；

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

步驟9：return SubCluster，U。

DPC 需要設(shè)置1 個參數(shù)，即聚類數(shù)目c。依據(jù)文獻(xiàn)[16]的分析，DPC 算法的時間復(fù)雜度為O(n2)。更多的關(guān)于DPC的細(xì)節(jié)，可參考文獻(xiàn)[16]。

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

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

圖1 OVMEDPC的流程圖

2.1 用密度峰值聚類發(fā)現(xiàn)不平衡數(shù)據(jù)的空間結(jié)構(gòu)

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

圖2 用一個人工例子來說明OVMEDPC如何用DPC去發(fā)現(xiàn)不平衡數(shù)據(jù)集的空間結(jié)構(gòu)（c=2）

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

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

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

基于被DPC發(fā)現(xiàn)的空間結(jié)構(gòu)（見圖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 是噪聲樣本，這是因為他們與周圍的大多數(shù)樣本有不同的類標(biāo)簽。

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

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

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

2.3 基于密度峰值聚類的插值技術(shù)

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

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

2.4 OVMEDPC的偽代碼和特性分析

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

算法2：OVMEDPC

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

輸出：少數(shù)類的合成樣本集合SyntheticSamples。

步驟1：Ximb=Xmin∪Xmaj；

步驟2：SyntheticSamples=?；

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

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

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

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

步驟7：Num=nmaj-nmin;

步驟8：N=1；

步驟9：whileN≤Num；

步驟10：for ?sci?SubCluster；

步驟11：發(fā)現(xiàn)簇sci的簇中心ui；

步驟12：for ?xj?sci；

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

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

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

圖4 用人工數(shù)據(jù)集來展示OVMEDPC的算法過程

3 仿真實驗

3.1 實驗設(shè)置

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

表1 實驗的數(shù)據(jù)集

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

表2 用于對比的過抽樣技術(shù)

3.2 實驗指標(biāo)

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

3.3 真實數(shù)據(jù)集實驗

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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