基于密度峰值聚類算法的自適應(yīng)加權(quán)過(guò)采樣算法

穆偉蒙，宋 燕，竇 軍

（1 上海理工大學(xué) 理學(xué)院，上海 200093；2 上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引言

數(shù)據(jù)不平衡問(wèn)題在許多應(yīng)用，如醫(yī)療診斷、人臉識(shí)別和網(wǎng)絡(luò)詐騙等領(lǐng)域都受到了廣泛關(guān)注。不平衡問(wèn)題是指不同類別的樣本數(shù)量差距很大，樣本數(shù)量多的類別稱為多數(shù)類，樣本數(shù)量少的類別稱為少數(shù)類。一般來(lái)說(shuō)，少數(shù)類樣本包含很多有用的信息，如果沒(méi)有很好的分類，可能會(huì)付出很大的代價(jià)。因此，提高少數(shù)類的識(shí)別精度至關(guān)重要。

解決不平衡問(wèn)題的方法可以分為2 類：基于數(shù)據(jù)的和基于算法的。其中，算法層面的策略包括代價(jià)敏感學(xué)習(xí)、單類學(xué)習(xí)、集成學(xué)習(xí)等，主要通過(guò)修改現(xiàn)有算法來(lái)提高對(duì)少數(shù)類樣本的分類精度。數(shù)據(jù)層面的策略包括過(guò)采樣技術(shù)和欠采樣技術(shù)，通過(guò)調(diào)節(jié)多數(shù)類或者少數(shù)類的樣本數(shù)量使不同類別的樣本趨于平衡?？偟卣f(shuō)來(lái)，欠采樣技術(shù)能夠減少多數(shù)類樣本來(lái)使類趨于平衡，容易實(shí)現(xiàn)，但易造成有用信息的丟失。而過(guò)采樣技術(shù)既能使不同類別樣本達(dá)到平衡，又能保留原始數(shù)據(jù)的分布特點(diǎn)，所以過(guò)采樣在處理不平衡數(shù)據(jù)分類方面得到了更多的關(guān)注。

由于過(guò)采樣技術(shù)應(yīng)用更為廣泛，因此有學(xué)者提出了許多過(guò)采樣方法，如，為了解決隨機(jī)過(guò)采樣技術(shù)可能會(huì)造成的過(guò)擬合問(wèn)題，Chawla 等人提出了合成少數(shù)類過(guò)采樣技術(shù)（Synthetic minority oversampling technique，SMOTE），其原理為：對(duì)于任意一個(gè)目標(biāo)少數(shù)類樣本x，利用歐式距離隨機(jī)選取x的其中一個(gè)近鄰樣本x，通過(guò)線性插值，人工合成樣本x，即：

其中，∈ [0，1] 。

雖然SMOTE 在一定程度上克服了過(guò)擬合問(wèn)題，并解決了類間不平衡，但是SMOTE 合成樣本時(shí)，對(duì)于所有的少數(shù)類樣本，采用統(tǒng)一的樣本分配策略合成新的樣本，很容易造成類內(nèi)不平衡，改變?cè)紨?shù)據(jù)的分布。

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

針對(duì)上述問(wèn)題，本文提出了一種基于密度峰值聚類算法的自適應(yīng)加權(quán)過(guò)采樣算法（DPCOTE）來(lái)解決不平衡分類問(wèn)題。該方法核心思想為：

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

（2）基于密度峰值聚類算法中的重要因子，為每個(gè)少數(shù)類樣本賦予采樣權(quán)重，以此來(lái)為少數(shù)類樣本合成不同數(shù)量的新樣本。

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

1 基于密度峰值加權(quán)過(guò)采樣方法

1.1 馬氏距離

馬氏距離是由印度統(tǒng)計(jì)學(xué)家Mahalanobis 提出的，馬氏距離考慮了各個(gè)特征變量之間的聯(lián)系，且不受特征量綱不一致的干擾。馬氏距離與歐氏距離的關(guān)系示意如圖1 所示。由圖1 可知，在計(jì)算歐式距離時(shí)，與距離最近，但是在馬氏距離中，與距離最近，因?yàn)樵紨?shù)據(jù)呈現(xiàn)橢圓分布，歐氏距離沒(méi)有考慮數(shù)據(jù)分布。馬氏距離除以協(xié)方差矩陣，可以把各個(gè)分量之間的方差都除掉，消除了量綱性，詳見(jiàn)圖1（b）。

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

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

1.2 密度峰值聚類算法

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

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

（2）密度較高的點(diǎn)之間的距離相對(duì)較大。

基于這2 個(gè)假設(shè)，DPC 引入了2 個(gè)重要因子，即目標(biāo)樣本的局部密度ρ和相對(duì)距離δ。對(duì)于第一個(gè)假設(shè)，利用高斯核函數(shù)計(jì)算任一樣本點(diǎn)x的局部密度ρ，其值可由如下公式計(jì)算得出：

其中，d為樣本x和x之間的距離，d為截?cái)嗑嚯x，通常將其設(shè)為距離降序排列的1%～2%。

DPC 算法示意如圖2 所示。在確定了截?cái)嗑嚯x后，就可以得到目標(biāo)樣本的局部密度，如樣本點(diǎn)，，。對(duì)于第二個(gè)假設(shè)，通過(guò)計(jì)算相對(duì)距離，即對(duì)于任一樣本點(diǎn)x，其局部密度比其更大、且距離最近的樣本點(diǎn)x的距離δ可表示為：

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

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

1.3 DPCOTE 方法

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

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

（2）合成樣本。利用DPC 算法對(duì)所有少數(shù)類樣本賦予采樣權(quán)重，來(lái)確定每個(gè)少數(shù)類樣本需要合成的樣本數(shù)，并使用k 近鄰算法和線性插值來(lái)對(duì)每個(gè)少數(shù)類樣本合成新樣本。

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

下面，利用ρ和δ來(lái)確定每個(gè)少數(shù)類樣本的采樣權(quán)重。為此，先對(duì)這2 個(gè)因子做歸一化，即：

綜合上述2 個(gè)因子，考慮到每個(gè)少數(shù)類樣本的密度信息和相對(duì)距離信息，為此構(gòu)造一個(gè)新的因子，即：

事實(shí)上，如果樣本的密度較大，基于該樣本合成新樣本時(shí)，會(huì)生成較多重復(fù)的樣本，導(dǎo)致模型過(guò)擬合。所以，每個(gè)少數(shù)類樣本需要合成的樣本數(shù)與密度成反比，具體數(shù)學(xué)公式如下：

將其標(biāo)準(zhǔn)化來(lái)確定第個(gè)少數(shù)類樣本的采樣權(quán)重為：

若給定為需要合成的少數(shù)類樣本總數(shù)，則第個(gè)少數(shù)類樣本需要合成的樣本數(shù)可以通過(guò)下式得到：

確定每個(gè)少數(shù)類樣本的合成數(shù)后，利用k 近鄰算法和線性插值來(lái)合成新的樣本，使少數(shù)類樣本與多數(shù)類樣本達(dá)到相對(duì)平衡。圖3 為ADASYN 算法和本文提出DPCOTE 算法生成的樣本分布示意圖。圖3 中，表示多數(shù)類樣本，表示少數(shù)類樣本，表示新合成的少數(shù)類樣本。由于ADASYN 算法對(duì)于學(xué)習(xí)難度高的樣本賦予更高的權(quán)重，所以其在邊界附近合成了更多的樣本，容易模糊類邊界，DPCOTE 算法考慮每個(gè)少數(shù)類樣本的分布情況，在不改變?cè)紨?shù)據(jù)分布的情況下，生成更多有用的新樣本。圖4 給出了DPCOTE 算法的流程圖，相應(yīng)算法的偽代碼設(shè)計(jì)表述具體如下。

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

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

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

2.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集信息Tab.1 Information of the datasets

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

在不平衡分類問(wèn)題中，分類器通常偏向多數(shù)類樣本，不能反映少數(shù)類的分類精度，而少數(shù)類的識(shí)別精度往往很重要，因此分類精度不適用于不平衡數(shù)據(jù)。和通常用來(lái)評(píng)價(jià)模型的性能，此處需涉及的數(shù)學(xué)公式可寫(xiě)為：

其中，表示預(yù)測(cè)和真實(shí)都為少類的樣本數(shù)；表示預(yù)測(cè)與真實(shí)都為多類的樣本數(shù)；表示少類預(yù)測(cè)為多類的樣本數(shù)；表示多類預(yù)測(cè)為少類的樣本數(shù)。

2.3 實(shí)驗(yàn)分析

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

表2 顯示了使用LR 分類器，所提出的DPCOTE算法在和方面與典型對(duì)比算法之間的性能比較。由表2 可知，DPCOTE 算法的表現(xiàn)遠(yuǎn)遠(yuǎn)好于對(duì)比的過(guò)采樣方法。具體來(lái)說(shuō)，在指標(biāo)方面，12 個(gè)數(shù)據(jù)集中，DPCOTE 算法有9 個(gè)數(shù)據(jù)集取得了最好的結(jié)果；在指標(biāo)方面，有7 個(gè)數(shù)據(jù)集取得了最好的結(jié)果。

表2 在LR 分類器上的對(duì)比結(jié)果Tab.2 Comparison results on LR

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

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

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

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

表3 在SVM 分類器上的對(duì)比結(jié)果Tab.3 Comparison results on SVM

表4 使用LR，SVM 分類器的Wilcoxon 實(shí)驗(yàn)結(jié)果Tab.4 Wilcoxon experimental results on LR，SVM

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

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