基于K-means 和改進MaxDistance 規則的集成非均衡數據分類方法?

于 滟 胡廣朋

（江蘇科技大學計算機學院 鎮江 212000）

1 引言

近年來，隨著計算機、通信行業的發展，大數據時代已全面來臨。針對的數據價值的挖掘在人類生活、企業發展、國家戰略等各個領域中起到了越來越重要的作用［1］。然而這些數據都有一個共同的特性，即數據的類別的數量不均衡。非均衡數據處理方法的出現，使得數據挖掘技術向前邁進了一大步的同時也極大地推動了大數據的發展，提高了大數據的市場價值［2］。因此，非均衡數據的研究成了眾多專家學者的關注對象，也是近幾年熾手火熱的研究領域之一［3］。

非均衡數據的非均衡性一般表現在兩個方面：1）類間不均衡，即某類樣本數量明顯少于其他樣本數量；2）類內不均衡，即某一類樣本分布較為分散，與其他類區分開的識別度不高［2］。目前對非均衡數據的處理方法，主要有兩大方面：1）基于數據的策略，通過欠采樣或者過采樣等方法，對原始數據增加或者減少，使非均衡數據轉化為均衡數據，如Synthetic Minority Over Sampling Technique（SMOTE）等［4～5］；2）基于算法的策略，通過改進傳統機器學習算法，從而提高對少數類樣本的分類精度和判別能力，主要有集成方法和代價敏感方法［2］。現有的基于數據策略的方法通常存在以下問題：1）通常會引入新的噪音數據；2）改變原始數據的分布，因而這類方法會大大降低分類器的分類性能。現有的基于算法策略中的代價敏感算法也通常會有計算復雜度高、實際中應用困難等問題，難以適應大數據量下的數據分析［6］。

數據建模部分，本文采用支持向量分類器作為基分類器，原因是：1）SVC 算法比較適合少數量的樣本，其計算復雜度取決于支持向量的數目，而不是樣本空間的維數，魯棒性強；2）支持向量機利用內積核函數代替向高維空間的非線性映射，可以很好地解決非線性引起的問題，而常見的非均衡數據集往往具有多數類與少數類數據的特征值很相近的特點，很難找到其決策線或者決策平面，所以對于大部分的非均衡數據集來說都很適合用支持向量分類來處理；3）雖然SVM 的計算復雜度相對來說較高，涉及到多維矩陣的運算，但一旦其訓練完畢，找到決策平面后，很容易得到決策結果，所以比較適合實時分析。

目前處理二類非均衡數據效果比較好且應用較廣的是集成方法。21 世紀以來，集成方法被機器學習界的權威T.G.Dietterich 列為機器學習四大方向之首，代表性的集成方法有Bagging、隨機森林、Boosting［7］。但是現存的集成方法中的集成規則如Max rule、Min rule、Product rule、Sum rule 以及MaxDistance［8］等仍存在許多問題，比如丟失有用的數據信息，未能很好地解決類內不均衡的問題等。所以如何針對非均衡數據集提出一種新的集成方法，并獲得更好的分類性能且為未來的大數據發展提供更扎實的基礎，是一個亟待解決的問題。

2 集成方法相關內容

近些年來對非均衡數據中集成方法的研究主要集中在二類非均衡數據上。傳統的集成方法的集成規則主要有Max rule、Min rule、Product rule 以及Sum rule 等，這些集成方法較為簡單，分類性能并不是很理想［8］。文獻［8］提出了一種基于距離的集成方法，取得了一定的分類效果，但是它在數據預處理部分只是簡單地使用了隨機分裂方法，未能考慮到類內不均衡的問題。文獻［9］提出一種基于SB-SVM 的集成方法，取得了很好的分類效果，但是它是通過SMOTE 的方法人為構造數據，一定程度上改變了原始數據的分布特性，容易造成過擬合等問題。文獻［10］提出了一種用K-means 方法代替抽樣方法的策略，很好地解決了類不均衡的問題，但是它也是通過SMOTE 的方法，引入了人造數據，在一定程度上也會導致過擬合等問題。文獻［11～13］都是采用了集成方法來處理非均衡問題，但是它們都并沒有涉及到類內不均衡問題的解決方法，一定程度上影響了分類性能。上述的這些方法雖然一定程度上都解決了非均衡數據的不均衡問題，取得了一定的效果，但是它們都沒有很好地解決類內不均衡問題，即沒有考慮到多數類數據的分布問題。

所以，基于上述內容的介紹，本文提出了基于K-means 算法改進的Ak-means 算法的集成方法。其核心思想是利用數據的空間分布特性，將多數類數據通過Ak-means 算法分成多個數據集，每個數據集的數目等于少數類數據集的數目，即本文的主要創新點之一。整個二類非均衡數據處理的流程是：首先將數據利用Ak-means 方法分為多個數據集；然后用基分類算法對每個簇與少數類組成的均衡數據集進行分類；最后結合本文優化的基于空間距離的集成規則AdmaxDistance rule 進行集成處理。

3 提出的方法

本文提出的方法主要由四部分組成：數據預處理過程、數據均衡過程、模型建立過程以及優化基分類器分類結果過程即集成過程。

圖1 是本文數據處理方法的框架圖。具體來說，本文首先使用改進的K-means聚類算法將多數類數據分為k 個數量為M（少數類的數量）的多數類數據集和1 個數量不為M 的多數類數據集；然后將這k個數據集分別和少數類數據集組和成k個均衡數據集和1 個非均衡數據集；接著本文使用SVC作為基分類器建模；然后使用集成規則對基分類器分類結果進行優化處理。本文重點介紹的是數據預處理過程以及優化基分類器分類結果過程。

3.1 數據預處理部分

首先，我們使用二分K-均值算法找到多數類數據的k 個質心，然后根據每個多數類數據距離每個質心的距離，將多數類數據劃分成k+1 個子數據集。如圖1所示，此時假設共有5個簇，則經過二分K-means算法處理后共能找到五個質心c1，c2，c3，c4，c5。然后在多數類數據集中分別找到距離每一個質心空間距離最近的M（少數類的個數）個數據（注：此時的空間距離指歐氏距離），因此我們可以得到k 個數量為M 的多數類的子數據集和一個數量不確定的多數類的子數據集。如圖2 所示，圖中共有五個（k）質心，以每個質心為中心，各找出十個（M）距離每個質心最近的數據，共有五個數據集；圖中可以看出有部分數據可以同時歸屬于多個數據集，同時有部分數據不屬于任何數據集，這部分數據單獨列為一個數據集。則圖3 中就可以分成六個多數類的子數據集。

圖2 二分K均值算法找到的5個質心

圖3 基于質心所劃分的出的數據

3.2 優化基分類器分類結果過程

在建立模型之后，我們會從每一個基分類器中獲得一個分類結果。然后我們通過本文的集成規則AdmaxDistance rule 對這些基分類的結果進行優化處理。我們假設有K+1個基分類器，每一個數據集都分為兩類C1，C2。對于ith(1 ≤i ≤(K+1))基分類器來說，它把測試數據分類為C1的概率是Pi1，分為C2的概率是Pi2。在最終的集成規則的分類結果中R1和R2分別代表類別標簽C1和C2。在文獻［8］中五種傳統的集成規則如表1 所示。本文優化 的［8］中的集成規則MaxDistance 中Dij(1 ≤i ≤K+1,1 ≤j ≤2) 代 表 在ith(1 ≤i ≤(K+1)) 基 分 類 器中，測試數據與訓練數據中類別標簽為Cj的平均歐式距離。average(Pil)代表基分類器中所得到的分類結果Pi1和Pi2的平均值。表2 中展示了本文優化的集成規則的細節。在表2 中可以看出有個變量α，這個值我們在本文中定為0.6，具體原因請看實驗部分。在最終的集成規則中，如果R1≥R2，那么測試的數據就會被分類為C1，相反，測試的數據會被分為C2。

表1 現存的集成規則的策略

表2 優化后的集成規則的策略

表3 38個標準二類非均衡數據集

4 實驗數據及分析

4.1 實驗數據集介紹

本文采用的數據集是標準數據集，共38 個數據集七種類別。每個數據集都有各自的屬性和非均衡比，關于數據集的具體的情況請看表3 或者http：//sci2s.ugr.es/keel/imbalanced.php。 本 文 實 驗中，為了得到更加準確的實驗數據和結果，對所有數據集都采用了五折交叉驗證策略［8］。本文實驗的分類性能評估方法采用的是AUC［14］，因為與傳統的F-measure 和G-mean 相比，AUC 評估指標更加偏向于少數類，一定程度彌補了在非均衡數據中傳統的評估方法未能很好地關注少數類的正確性這一缺點。

4.2 實驗分析

本文主要由兩部分實驗組成。第一部分是判斷α 取何值時本文提出的方法能夠取得最好的效果；第二部分是將本文提出的方法跟現存的集成方法對比。

實驗一：為了能夠使本文優化的集成規則跟本文提出的Ak-means方法結合后能夠獲得更好的分類效果，我們選擇了三個代表性的數據集包括：ecoli3、yeast2vs4、glass015vs2 作為測試數據集，判斷當α 取何值時本文提出的方法能夠獲得最好的分類效果。如圖4 所示，當 α 取0.6 時，AUC 的平均值最大，為0.9240。所以本文接下來的實驗中，對于所有的數據集，我們優化后的集成規則中的α 值均默認取值為0.6。

圖4 α取不同值時獲得的AUC值

實驗二：本部分實驗是基于基算法是SVC［15］，將本文提出的非均衡數據處理方法跟現存的處理非均衡數據的集成方法相對比。如圖5 所示。上述這些方法共同點是基算法都是SVC。其中，SVC的懲罰參數C 默認值是1.0；核函數采用的是rbf；probability 采用概率估計，其他參數均為默認值。從圖5 中可以看出本文提出的基于Ak-means算法的二類非均衡數據集成算法相同現存的多種同類型的二類非均衡數據處理方法相比具有更好的分類性能（注：圖中縱坐標代表每種方法處理38個非均衡數據集后所取得的平均的AUC值）。

圖5 不同方法的實驗結果對比圖（所有數據集的平均結果）

5 結語

為了在處理非均衡數據時不引進新的數據雜質從而保持原有的數據的特性并解決類內不均衡的條件下獲得更好的分類性能，本文基于K-means方法的改進提出了Ak-means方法。它能夠根據原始數據本身的特征將原始多數類數據聚成多個數量上與少數類數目相等的多數類簇，從而將非均衡數據分類問題轉化成均衡數據分類問題，很好地解決了類內不均衡的問題。實驗結果表明本文提出的Ak-mean 方法同優化后的集成規則AdmaxDistance rule 相結合的二類非均衡數據處理方法同現存的多種同類型的二類非均衡數據處理方法相比具有更好的分類性能。