摘  要： 針對極端學習機算法對不平衡數(shù)據(jù)分類問題的處理效果不夠理想，提出了一種基于聚類欠采樣的極端學習機算法。新算法首先對訓練集的負類樣本進行聚類生成不同的簇，然后在各簇中按規(guī)定的采樣率對其進行欠采樣，取出的樣本組成新的負類數(shù)據(jù)集，從而使訓練集正負類數(shù)據(jù)個數(shù)達到相對平衡，最后訓練分類器對測試集進行測試。實驗結(jié)果表明，新算法有效地降低了數(shù)據(jù)的不平衡對分類準確率的影響，具有更好的分類性能。

　　關(guān)鍵詞： 極端學習機；聚類；不平衡數(shù)據(jù)；欠采樣；數(shù)據(jù)挖掘

0 引言

　　不平衡數(shù)據(jù)[1]是指在包含許多類別的大數(shù)據(jù)中，某些類別的數(shù)據(jù)個數(shù)遠遠小于其他類別的數(shù)據(jù)個數(shù)，即各類別數(shù)據(jù)的個數(shù)存在著不平衡性的數(shù)據(jù)。通常稱樣本數(shù)量少的類別為少類，也稱為正類；樣本數(shù)量多的類別為多類，也稱為負類。在現(xiàn)實生活中，存在著許多不平衡數(shù)據(jù)的例子，如醫(yī)療診斷病變信息、垃圾信息過濾、故障檢測等。正如這些實例，少數(shù)類數(shù)據(jù)所包含的信息往往是我們所需要的。因此，怎樣更好地提取這部分數(shù)據(jù)，已成為數(shù)據(jù)挖掘研究中的一個熱點話題。

　　目前，不平衡數(shù)據(jù)的分類問題的處理方法[2]主要可分為兩類：數(shù)據(jù)層面上，主要是對原始數(shù)據(jù)集進行處理，利用少數(shù)類過采樣、多數(shù)類欠采樣、混合采樣等方法使得原始數(shù)據(jù)集各類別數(shù)據(jù)個數(shù)達到相對平衡，主要方法有過采樣技術(shù)（Synthetic Minority Oversampling Technique，SMOTE）[3]、單邊選擇欠采樣技術(shù)（One-sided Selection）[4]等；算法層面上，主要是對已有分類算法進行改進或是設(shè)計新算法使其有效地解決不平衡數(shù)據(jù)分類問題，主要算法有支持向量機（Support Vector Machine，SVM）[5]、Bagging算法[6-7]等。

　　極端學習機作為一種分類算法，具有訓練速度快、泛化性能好等特點，但其對不平衡數(shù)據(jù)分類問題的處理效果并不理想。本文提出了一種基于聚類欠采樣的極端學習機分類算法。為方便起見，本文主要考慮數(shù)據(jù)二分類的問題。算法首先利用聚類原理對訓練集中的負類樣本進行聚類生成不同的簇，并計算各簇數(shù)據(jù)與簇中心的距離并排序，然后在每個簇中按規(guī)定的采樣率取出距離中心近的數(shù)據(jù)，與訓練集的正類一起組成類別相對平衡的數(shù)據(jù)集，最后訓練分類器，預測測試集數(shù)據(jù)所屬類別。新算法有效地解決了數(shù)據(jù)的不平衡性對分類器性能的影響，具有較強的實用性，并在實例數(shù)據(jù)實驗中得到了證實。

1 理論分析

　　1.1 極端學習機算法（ELM）

　　極端學習機（Extreme Learning Machine，ELM）[8-9]是一種快速的單隱層前饋神經(jīng)網(wǎng)絡(luò)訓練算法。該算法的特點是隨機選取輸入權(quán)值向量及隱層神經(jīng)元的偏置，在訓練的過程中，只需要設(shè)置隱層節(jié)點的個數(shù)，便可通過一個簡單的線性系統(tǒng)求出唯一的最優(yōu)解。

　　對于N個不同的訓練集數(shù)據(jù)（xi，ti）∈Rn·Rm，其中xi=（xi1，xi2，…，xin）T為數(shù)據(jù)樣本點，ti=（ti1，ti2，…，tim）T為類別標簽，隱層節(jié)點數(shù)為M，激活函數(shù)為g（x）的單隱層前饋神經(jīng)網(wǎng)絡(luò)的輸出函數(shù)表達式為：

　　其中，j=1，2，…，N，ai=（ai1，ai2，…，ain）T表示連接輸入節(jié)點和第i個隱層節(jié)點的輸入權(quán)值向量，i=（i1，i2，…，im）表示連接第i個隱層節(jié)點和輸出節(jié)點的輸出權(quán)值向量，bi表示第i個隱層節(jié)點的偏置。g：R→R為激活函數(shù)，ai·xj表示輸入權(quán)值向量ai和樣本xj在Rn中的內(nèi)積。

　　假設(shè)這個函數(shù)可以以零誤差逼近這個不同的數(shù)據(jù)樣本，也就是說，存在參數(shù)（ai，bi）和?茁i使得：

　　那么問題就轉(zhuǎn)化為求H=T的最小二乘解。當M≥N時，矩陣H可直接求逆；當M<<N時，由Moore-Penrose廣義逆可以得到：

　　其中H+=（HTH）-1HT為H的廣義逆矩陣。

　　最小二乘解即為輸出權(quán)值，所求解問題最終轉(zhuǎn)化為求解一個矩陣的廣義逆問題。與傳統(tǒng)的分類算法相比，ELM算法能一次性求出輸出權(quán)值，不需要任何迭代過程，減少了調(diào)節(jié)參數(shù)的時間，從而提高了運算速度。

　　ELM算法的主要步驟：

　　（1）輸入訓練集（xi，ti）∈Rm×Rn，激活函數(shù)為g（x），隱層節(jié)點個數(shù)為M；

　　（2）隨機生成輸入權(quán)值向量ai和偏置bi；

　　（3）計算隱層輸出矩陣H；

　　（4）由=H+T，計算輸出權(quán)值；

　　（5）輸入測試集Y={yi}，激活函數(shù)為g（x），隱層節(jié)點個數(shù)M；

　　（6）調(diào)用輸入權(quán)值向量ai和偏置bi，隱層輸出矩陣H，輸出權(quán)值，由=H+TY，計算測試集的標簽TYT。

　　1.2 模糊聚類算法（FCM）

　　模糊C均值聚類算法（Fuzzy C-Means，F(xiàn)CM）[10-11]于1981年被Bezdek提出，是一種柔性的模糊劃分。它的思想是將數(shù)據(jù)集劃分為不同的簇，用值在0，1間的隸屬度來確定每個數(shù)據(jù)屬于某個簇的程度，要求同一簇的對象之間相似度盡可能大，而不同簇的對象之間相似度盡可能小。

　　給定有限數(shù)據(jù)集X={x1，x2，…，xn}，F(xiàn)CM算法將n個數(shù)據(jù)xi（i=1，2，…，n）分為C個簇，并求每個簇的聚類中心，使目標函數(shù)達到最小。其目標函數(shù)如下：

　　其中，uij∈（0，1），ci為第i簇的聚類中心，dij=‖ci-xj‖，表示第i個聚類中心與第j個數(shù)據(jù)點間的歐氏距離，m∈[1，∞）是一個加權(quán)指數(shù)。其約束條件為一個數(shù)據(jù)集的隸屬度的和等于1，即：

　　由拉格朗日乘子法，構(gòu)造新的目標函數(shù)：

　　由條件極值，使式（7）達到最小的必要條件為：

2 基于聚類欠采樣的極端學習機算法（FCM-ELM）

　　定義1 設(shè)訓練集的正負類樣本個數(shù)分別為P、F，聚類個數(shù)為C，聚類后各簇的樣本個數(shù)為p1，p2，…，pc，則規(guī)定第i簇的采樣率為：

　　本文算法的主要步驟：

　　（1）計算訓練集的正負類樣本個數(shù)，分別記為P、F，利用FCM算法對訓練集的負類樣本進行聚類，生成C個簇；

　　（2）聚類后各簇的數(shù)據(jù)按到各自聚類中心的距離由小到大排序，并且輸出按順序排列的各簇數(shù)據(jù)集；

　　（3）對各簇按規(guī)定的采樣率ni進行欠采樣處理，每個簇中取出離聚類中心最近的ni個樣本，取出的C×ni個樣本組成新的負類數(shù)據(jù)集；

　　（4）將新的負類數(shù)據(jù)集和正類數(shù)據(jù)集合并作為新的訓練集，訓練極端學習機分類器，最后預測測試集的標簽。

3 不平衡數(shù)據(jù)分類性能的評價指標

　　表1是數(shù)據(jù)二分類問題的混淆矩陣，TP、TN分別為分類正確的少數(shù)類和多數(shù)類的樣本個數(shù)，F(xiàn)N、FP分別為分類錯誤的少數(shù)類和多數(shù)類的樣本個數(shù)。

　　不平衡數(shù)據(jù)分類性能評價指標的相關(guān)定義如下：

　　定義2 正類樣本的查準率（Precision）：

　　（3）ROC曲線（Receiver Operating Chara-cteristic）[14]：

　　ROC曲線是分類器整體分類性能的評價標準，該曲線能很好地反應兩類數(shù)據(jù)分類錯誤率之間的關(guān)系。但ROC曲線不能定量地評價分類器的性能，所以利用ROC曲線下的面積AUC（Area Under the Curve）來評估分類器性能。AUC值越大，分類器性能越好，反之越差。

4 實驗結(jié)果及分析

　　本文實驗所用的8個數(shù)據(jù)集均來自于UCI機器學習數(shù)據(jù)庫，每個數(shù)據(jù)集多類與少類樣本數(shù)量的比例失衡程度不同，具體信息如表2所示。

　　實驗中，采用十折交叉驗證方法將數(shù)據(jù)集分為訓練集和測試集，選用ELM算法、FCM-ELM算法進行對比實驗。兩種算法的激活函數(shù)均選擇Sigmoid函數(shù)，隱層節(jié)點數(shù)設(shè)為200。訓練集、測試集的劃分存在一定的隨機性，為了充分證明算法的有效性，實驗結(jié)果均取循環(huán)100次后的平均值。此外，F(xiàn)CM-ELM算法實驗中，聚類中心個數(shù)C分別取3、5、9、15。以上算法均在MATLAB R2012a上實現(xiàn)。在G-means、F-measure、AUC三種評價指標下，兩種算法的實驗結(jié)果對比如表3~表5所示。

　　從表3~表5可以看出，F(xiàn)CM-ELM算法的準確率明顯優(yōu)于ELM算法。在前六個比例失衡程度較小的數(shù)據(jù)集中，準確率最多提高了20%，最后兩個比例失衡程度較大的數(shù)據(jù)集中，準確率最多提高了63%。而且，當聚類中心個數(shù)C取不同的值時，F(xiàn)CM-ELM算法的實驗結(jié)果相差較小，相對比較穩(wěn)定。

5 結(jié)束語

　　本文針對不平衡數(shù)據(jù)的分類問題，提出了一種基于聚類欠采樣的極端學習機算法。該方法首先對訓練集的負類樣本進行聚類，然后按規(guī)定的采樣率進行欠采樣，使得訓練集正負類樣本個數(shù)達到近似平衡，有效地解決了原始的極端學習機算法對不平衡數(shù)據(jù)分類的錯分問題。將新算法用于實例數(shù)據(jù)集的分類問題中，其有效性和優(yōu)越性得到了證明。

　　參考文獻

　　[1] Han Jiawei， KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2001.

　　[2] 王和勇，樊泓坤，姚正安，等.不平衡數(shù)據(jù)集的分類方法研究[J].計算機應用研究，2008，25（5）：1301-1308.

　　[3] CHAWLA N V， BOWYER K B， HALL L Q， et al. SMOTE： Synthetic minority over-sampling technique[J].Journal of Artificial Intelligence Research， 2002（16）：321-357.

　　[4] KUBAT M， MATWIN S. Addressing the curse of  imbalanced training sets： one-sided selection[C]. Proceedings of the 14th International Conference on Machine Learning， San Francisco， 1997：179-186.

　　[5] VAPNIK V. The nature of statistical learning theory[M].New York： Springer-Verlag， 2000.

　　[6] 秦姣龍，王蔚.Bagging組合的不平衡數(shù)據(jù)分類方法[J].計算機工程，2011，37（14）：178-182.

　　[7] 李明方，張化祥.針對不平衡數(shù)據(jù)的Bagging改進算法[J].計算機工程與應用，2013，49（2）：40-42.

　　[8] HUANG G B， ZHOU H， DING X， et al. Extreme learning machine for regression and multiclass classification[J]. IEEE Trans. Syst. Man Cybern， 2012，42（2）：513-529.

　　[9] HUANG G B. An insight into extreme learning machines random neurons， random features and kernels[J]. Cognitive Computation， 2014，6（3）：376-390.

　　[10] BEZDEK J. Pattern recognition with fuzzy objec-tive function algorithms[M]. New York： Plenum Plenum Press，1981.

　　[11] 肖景春，張敏.基于減法聚類與模糊C-均值的模糊聚類的研究[J].計算機工程，2005，31（Z1）：135-137.

　　[12] 林智勇，郝志峰，楊曉偉.若干評價準則對不平衡數(shù)據(jù)學習的影響[J].華南理工大學學報，2010，38（4）：126-135.

　　[13] 楊明，尹軍梅，吉銀林.不平衡數(shù)據(jù)分類方法綜述[J].南京師范大學學報：工程技術(shù)版，2008，8（4）：7-12.

　　[14] BRADLEY A P. The use of the area under the ROC curve in the evaluation of machine learning algorithms[J].Pattern Recognition， 1997，30（7）： 1145-1159.