李鑫

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

0 引言

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

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

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

1 改進密度峰值聚類的欠采樣方法

1.1 密度峰值聚類

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

其中d是樣本x與樣本x的歐氏距離；d為截斷距離，需要人為事先設(shè)定，通常d設(shè)置為將樣本點間距離進行降序后排列在2%的值。

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

1.2 信息熵

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

1.3 改進密度峰值聚類的欠采樣算法

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

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

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

1.4 方法步驟

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

算法1 DPEC

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

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

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

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

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

2 對比實驗

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

對于二分類問題，通常用混淆矩陣來作為進行評估，其表示如表1所示。

表1 混淆矩陣

對于不平衡數(shù)據(jù)分類問題，將少數(shù)類記為正類，多數(shù)類記為負類。本文用F1-score和AUC兩個指標(biāo)來評估算法效果。

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

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

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

采樣算法 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）進行欠采樣，本文改進后的算法（DPEC）在F1 和AUC 值上都有明顯提高。相比于不對數(shù)據(jù)進行任何處理，本文提出的欠方法（DPEC）顯著提高了少數(shù)類的F1 值。與K-means、TomekLinks、CNN、NearMiss 和隨機欠采樣五種常用的欠采樣方法相比，本文算法也有著不錯的效果?？傮w而言，DPEC 有效提升了不平衡數(shù)據(jù)集的分類性能。

3 結(jié)論

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