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

　　關(guān)鍵詞： 極端學(xué)習(xí)機(jī)；聚類(lèi)；不平衡數(shù)據(jù)；欠采樣；數(shù)據(jù)挖掘

0 引言

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

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

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

1 理論分析

　　1.1 極端學(xué)習(xí)機(jī)算法（ELM）

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

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

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

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

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

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

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

　　ELM算法的主要步驟：

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

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

　　（3）計(jì)算隱層輸出矩陣H；

　?。?）由=H+T，計(jì)算輸出權(quán)值；

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

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

　　1.2 模糊聚類(lèi)算法（FCM）

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

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

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

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

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

2 基于聚類(lèi)欠采樣的極端學(xué)習(xí)機(jī)算法（FCM-ELM）

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

　　本文算法的主要步驟：

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

　?。?）聚類(lèi)后各簇的數(shù)據(jù)按到各自聚類(lèi)中心的距離由小到大排序，并且輸出按順序排列的各簇?cái)?shù)據(jù)集；

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

　?。?）將新的負(fù)類(lèi)數(shù)據(jù)集和正類(lèi)數(shù)據(jù)集合并作為新的訓(xùn)練集，訓(xùn)練極端學(xué)習(xí)機(jī)分類(lèi)器，最后預(yù)測(cè)測(cè)試集的標(biāo)簽。

3 不平衡數(shù)據(jù)分類(lèi)性能的評(píng)價(jià)指標(biāo)

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

　　不平衡數(shù)據(jù)分類(lèi)性能評(píng)價(jià)指標(biāo)的相關(guān)定義如下：

　　定義2 正類(lèi)樣本的查準(zhǔn)率（Precision）：

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

　　ROC曲線是分類(lèi)器整體分類(lèi)性能的評(píng)價(jià)標(biāo)準(zhǔn)，該曲線能很好地反應(yīng)兩類(lèi)數(shù)據(jù)分類(lèi)錯(cuò)誤率之間的關(guān)系。但ROC曲線不能定量地評(píng)價(jià)分類(lèi)器的性能，所以利用ROC曲線下的面積AUC（Area Under the Curve）來(lái)評(píng)估分類(lèi)器性能。AUC值越大，分類(lèi)器性能越好，反之越差。

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

　　本文實(shí)驗(yàn)所用的8個(gè)數(shù)據(jù)集均來(lái)自于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)，每個(gè)數(shù)據(jù)集多類(lèi)與少類(lèi)樣本數(shù)量的比例失衡程度不同，具體信息如表2所示。

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

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

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

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

　　參考文獻(xiàn)

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

　　[2] 王和勇，樊泓坤，姚正安，等.不平衡數(shù)據(jù)集的分類(lèi)方法研究[J].計(jì)算機(jī)應(yīng)用研究，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ù)分類(lèi)方法[J].計(jì)算機(jī)工程，2011，37（14）：178-182.

　　[7] 李明方，張化祥.針對(duì)不平衡數(shù)據(jù)的Bagging改進(jìn)算法[J].計(jì)算機(jī)工程與應(yīng)用，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] 肖景春，張敏.基于減法聚類(lèi)與模糊C-均值的模糊聚類(lèi)的研究[J].計(jì)算機(jī)工程，2005，31（Z1）：135-137.

　　[12] 林智勇，郝志峰，楊曉偉.若干評(píng)價(jià)準(zhǔn)則對(duì)不平衡數(shù)據(jù)學(xué)習(xí)的影響[J].華南理工大學(xué)學(xué)報(bào)，2010，38（4）：126-135.

　　[13] 楊明，尹軍梅，吉銀林.不平衡數(shù)據(jù)分類(lèi)方法綜述[J].南京師范大學(xué)學(xué)報(bào)：工程技術(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.