一種改進(jìn)密度峰值聚類的欠采樣算法

李鑫

（首都經(jīng)濟(jì)貿(mào)易大學(xué)，北京 100026）

0 引言

作為數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一，分類問(wèn)題的研究已發(fā)展得非常成熟，諸多的分類算法被提出，如：決策樹(shù)、支持向量機(jī)、邏輯回歸等。這些算法在傳統(tǒng)的分類問(wèn)題中通常都具有良好的表現(xiàn)效果。在實(shí)際應(yīng)用中，數(shù)據(jù)不平衡現(xiàn)象出現(xiàn)的頻率越來(lái)越高，很多情況下少數(shù)類樣本具有更高的研究?jī)r(jià)值。比如在癌細(xì)胞檢測(cè)、信用卡欺詐檢測(cè)、網(wǎng)絡(luò)入侵檢測(cè)等領(lǐng)域都存在著數(shù)據(jù)不平衡問(wèn)題，如果錯(cuò)分少數(shù)類將帶來(lái)嚴(yán)重的后果。而傳統(tǒng)的分類方法很少顧及少數(shù)類的分類精度。因此，針對(duì)不平衡數(shù)據(jù)研究如何提高少數(shù)類樣本的分類精度具有重要的意義。目前，針對(duì)不平衡數(shù)據(jù)分類問(wèn)題的研究主要分為數(shù)據(jù)層面和算法層面兩大方向。數(shù)據(jù)層面是通過(guò)對(duì)數(shù)據(jù)集進(jìn)行重抽樣來(lái)構(gòu)建平衡數(shù)據(jù)集，主要有欠采樣和過(guò)采樣兩大類。算法層面主要是通過(guò)改變少數(shù)類樣本的權(quán)重來(lái)提高分類器對(duì)少數(shù)類樣本預(yù)測(cè)的精度。本文基于數(shù)據(jù)層面的欠采樣方法開(kāi)展研究，提出了一種新穎的平衡數(shù)據(jù)集獲取方法以提高分類器對(duì)少數(shù)類的預(yù)測(cè)精度。

最簡(jiǎn)單的欠采樣方法是隨機(jī)欠采樣（RUS），它是在多數(shù)類數(shù)據(jù)集中隨機(jī)地刪除一部分樣本。編輯最近鄰規(guī)則（ENN）考慮了樣本重要性，在少數(shù)類的鄰近樣本中刪除一部分多數(shù)類；壓縮最近鄰規(guī)則（CNN）在ENN 的基礎(chǔ)上對(duì)決策邊界上的樣本點(diǎn)給予了更多地關(guān)注。后來(lái)又有學(xué)者提出TomekLinks算法，利用Tomek 對(duì)來(lái)識(shí)別數(shù)據(jù)集中對(duì)分類造成干擾的噪聲點(diǎn)。聚類算法能夠根據(jù)相似性對(duì)樣本進(jìn)行劃分，YEN 等將K-means 聚類算法應(yīng)用到欠采樣中，先對(duì)多數(shù)類樣本進(jìn)行聚類，再?gòu)拿總€(gè)簇中按照一定比例進(jìn)行抽樣，從而減少冗余樣本。由于K-means 算法假設(shè)較強(qiáng)，僅適用于超球形簇，并且對(duì)異常值敏感，崔彩霞等將密度峰值聚類應(yīng)用到欠采樣并取得了良好的效果。密度峰值聚類算法是一種基于密度的聚類方法，它根據(jù)樣本的密度分布來(lái)進(jìn)行聚類，不僅可以檢測(cè)到噪聲點(diǎn)而且適用于任意形狀的簇。

基于以上研究，本文提出一種改進(jìn)密度峰值聚類的欠采樣算法（Udersamp lingbasedon Density Peak Entropy Clustering,DPEC），首先利用信息熵對(duì)密度峰值聚類算法進(jìn)行改進(jìn)，優(yōu)化聚類效果；然后用改進(jìn)算法對(duì)多數(shù)類聚類，將少數(shù)類樣本數(shù)量作為聚類中心數(shù)，并選取密度距離較大的樣本點(diǎn)作為聚類中心；最后用所有聚類中心代替原始多數(shù)類數(shù)據(jù)集，既保留了樣本重要信息又可以消除噪聲樣本從而提高數(shù)據(jù)集的質(zhì)量，優(yōu)化不平衡數(shù)據(jù)的分類性能。

1 改進(jìn)密度峰值聚類的欠采樣方法

1.1 密度峰值聚類

密度峰值聚類算法（Density Peak Clustering,DPC）是利用樣本的密度分布來(lái)進(jìn)行聚類，適用于任意形狀的簇，該算法的核心思想建立在兩個(gè)假設(shè)上：簇類中心的局部密度大于其鄰近樣本點(diǎn)的局部密度；簇類中心點(diǎn)之間有著相對(duì)較大的距離。通過(guò)計(jì)算每個(gè)樣本的局部密度和偏移距離對(duì)每個(gè)點(diǎn)進(jìn)行簇的劃分，聚類中心的選取通常通過(guò)繪制以局部密度為橫軸，偏移距離為縱軸的決策圖來(lái)人為主觀選取。當(dāng)聚類中心后，剩余樣本點(diǎn)將分配給與其最近且具有更高密度的簇中。假設(shè)數(shù)據(jù)集為={，，…，x}T，其中為數(shù)據(jù)集的樣本數(shù)，對(duì)于每一個(gè)樣本x，其局部密度ρ為：

其中d是樣本x與樣本x的歐氏距離；d為截?cái)嗑嚯x，需要人為事先設(shè)定，通常d設(shè)置為將樣本點(diǎn)間距離進(jìn)行降序后排列在2%的值。

樣本點(diǎn)x的偏移距離δ被定義為該樣本點(diǎn)到具有更高局部密度的點(diǎn)的最小距離：

1.2 信息熵

熵是信息論中量化系統(tǒng)信息含量的指標(biāo)，熵越大，系統(tǒng)的不確定性越大。信息熵通常用來(lái)衡量數(shù)據(jù)所含信息量的大小，事件發(fā)生的概率越高，其攜帶的信息量越低。信息熵定義為：

1.3 改進(jìn)密度峰值聚類的欠采樣算法

聚類算法能夠?qū)⑾嗨茦颖颈M可能地分在同一個(gè)簇，且不同簇的差異性盡可能大。將聚類算法應(yīng)用到不平衡數(shù)據(jù)集的欠采樣中，能夠抽取到更具有代表性的樣本，消除冗余樣本。密度峰值聚類算法利用數(shù)據(jù)集的密度分布進(jìn)行聚類，該算法思想簡(jiǎn)單，算法復(fù)雜度低，并且不易受異常值的干擾。但其截?cái)嗑嚯x和聚類中心都需要人為主觀選取，聚類效果還有待提升。本文對(duì)其進(jìn)行優(yōu)化，使其應(yīng)用在能夠在不平衡數(shù)據(jù)集上取得更好的效果，提出了改進(jìn)密度峰值聚類的過(guò)采樣算法（Udersamplingbasedon Density Peak Entropy Clustering,DPEC）。

本文將信息熵與DPC 算法相結(jié)合，使算法能夠自動(dòng)尋找最優(yōu)截?cái)嗑嚯x。信息熵越大，數(shù)據(jù)分布越混亂，故聚類的效果越差；相反，信息熵越小，聚類效果就越好。因此，使信息熵（d）達(dá)到最小時(shí)的d就是最優(yōu)截?cái)嗑嚯x，此時(shí)的局部密度和偏移距離達(dá)到最優(yōu)值，聚類效果最好。最優(yōu)截?cái)嗑嚯x定義如下：

其 中，ρ和δ是ρ和δ歸一化后的值，

1.4 方法步驟

我們將本文提出的改進(jìn)密度峰值聚類的欠采樣算法（DPEC）的具體步驟總結(jié)為算法1，具體為：

算法1 DPEC

輸入：原始數(shù)據(jù)集；

輸出：新的平衡數(shù)據(jù)集′。

步驟1：將數(shù)據(jù)集分為多數(shù)類和少數(shù)類，計(jì)算少數(shù)類樣本個(gè)數(shù)=||；

步驟2：計(jì)算每個(gè)多數(shù)類樣本點(diǎn)x的局部密度ρ和偏移距離δ；

步驟8：將γ最大的前（=||）個(gè)樣本點(diǎn)作為聚類中心，選取這些樣本作為新的多數(shù)類樣本，并與少數(shù)類數(shù)據(jù)集合并構(gòu)成平衡數(shù)據(jù)集′。

2 對(duì)比實(shí)驗(yàn)

2.1 性能評(píng)估指標(biāo)

對(duì)于二分類問(wèn)題，通常用混淆矩陣來(lái)作為進(jìn)行評(píng)估，其表示如表1所示。

表1 混淆矩陣

對(duì)于不平衡數(shù)據(jù)分類問(wèn)題，將少數(shù)類記為正類，多數(shù)類記為負(fù)類。本文用F1-score和AUC兩個(gè)指標(biāo)來(lái)評(píng)估算法效果。

2.2 實(shí)驗(yàn)設(shè)置與結(jié)果分析

為驗(yàn)證DPEC 欠采樣算法效果，本文采UCI 數(shù)據(jù)庫(kù)的Abalone 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。該數(shù)據(jù)集是UCI 數(shù)據(jù)庫(kù)提供的標(biāo)準(zhǔn)機(jī)器學(xué)習(xí)分類問(wèn)題數(shù)據(jù)集，通過(guò)利用鮑魚(yú)的長(zhǎng)度、直徑、內(nèi)臟重量等屬性來(lái)預(yù)測(cè)鮑魚(yú)的性別。該數(shù)據(jù)集共含有4 177 個(gè)樣本，特征數(shù)為8 個(gè)，其中多數(shù)類樣本量為2 870 個(gè)，少數(shù)類樣本量為1 307 個(gè)，不平衡比率為2.2。選擇DPC、K-means、TomekLinks、CNN、NearMiss、RUS 六種欠采樣算法與本文算法進(jìn)行對(duì)比，并在決策樹(shù)（CART）、邏輯回歸、支持向量機(jī)三種單分類器，隨機(jī)森林、Adaboost 兩種集成算法上進(jìn)行實(shí)驗(yàn)測(cè)試其提升效果。本文實(shí)驗(yàn)的運(yùn)行環(huán)境為Jupyter Notebook 軟件，選擇75%為訓(xùn)練集，選擇25%為測(cè)試集進(jìn)行模型訓(xùn)練，參數(shù)均使用默認(rèn)參數(shù)設(shè)置，選擇F1-score 和AUC 值作為評(píng)價(jià)指標(biāo)來(lái)判斷模型效果。表2 是不同欠采樣方法在各個(gè)分類器上模型訓(xùn)練得出的F1-score 和AUC 值。

表2 DPEC 與其他采樣方法在不同分類器上的效果對(duì)比

采樣算法 CART Logistic SVM RF AdaBoost F1 AUC F1 AUC F1 AUC F1 AUC F1 AUC DPEC 0.529 0.634 0.566 0.714 0.569 0.674 0.563 0.709 0.570 0.718 DPC 0.430 0.550 0.496 0.699 0.475 0.617 0.473 0.662 0.483 0.680 K-means 0.403 0.528 0.501 0.694 0.500 0.583 0.508 0.665 0.518 0.659 TomekLinks 0.435 0.581 0.392 0.716 0.125 0.520 0.440 0.708 0.445 0.710 CNN 0.463 0.582 0.556 0.714 0.547 0.638 0.544 0.692 0.557 0.703 NearMiss 0.473 0.576 0.543 0.714 0.527 0.645 0.495 0.664 0.509 0.646 RUS 0.448 0.578 0.545 0.711 0.569 0.672 0.529 0.694 0.557 0.714不采樣 0.387 0.553 0.256 0.715 0.000 0.499 0.373 0.707 0.369 0.721

從表2 可以看出，相比于用原始的密度峰值聚類算法（DPC）進(jìn)行欠采樣，本文改進(jìn)后的算法（DPEC）在F1 和AUC 值上都有明顯提高。相比于不對(duì)數(shù)據(jù)進(jìn)行任何處理，本文提出的欠方法（DPEC）顯著提高了少數(shù)類的F1 值。與K-means、TomekLinks、CNN、NearMiss 和隨機(jī)欠采樣五種常用的欠采樣方法相比，本文算法也有著不錯(cuò)的效果?？傮w而言，DPEC 有效提升了不平衡數(shù)據(jù)集的分類性能。

3 結(jié)論

欠采樣是不平衡數(shù)據(jù)分類常用的重采樣方法之一。本文提出了一種改進(jìn)密度峰值聚類的不平衡數(shù)據(jù)欠采樣算法。該算法利用信息熵確定全局最優(yōu)截?cái)嗑嚯x，為克服量綱影響，對(duì)局部密度和偏移距離進(jìn)行歸一化后相乘并進(jìn)行排序，將少數(shù)類數(shù)據(jù)集的樣本數(shù)量作為多數(shù)類聚類的聚類中心數(shù)，選擇密度距離較大的點(diǎn)作為聚類中心。用這些聚類中心樣本代表整個(gè)多數(shù)類數(shù)據(jù)集，從而去除冗余數(shù)據(jù)保留多數(shù)類數(shù)據(jù)集的重要信息。將本文算法與其他欠采樣算法進(jìn)行對(duì)比實(shí)驗(yàn)，并在決策樹(shù)（CART）、邏輯回歸、支持向量機(jī)三種單分類器，隨機(jī)森林、Adaboost 兩種集成算法上進(jìn)行實(shí)驗(yàn)測(cè)試其提升效果，結(jié)果表明，本文算法在一定程度上提高了少數(shù)類樣本的預(yù)測(cè)精度。后續(xù)可考慮與過(guò)采樣結(jié)合對(duì)不平衡數(shù)據(jù)集的混合采樣展開(kāi)研究。