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

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

0 引言

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

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

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

　?。?）計(jì)算隱層輸出矩陣H；

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

　?。?）輸入測(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 模糊聚類算法（FCM）

　　模糊C均值聚類算法（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è)簇的聚類中心,，使目標(biāo)函數(shù)達(dá)到最小。其目標(biāo)函數(shù)如下：

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

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

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

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

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

　　本文算法的主要步驟：

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

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

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

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

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

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

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

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

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

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

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

　　本文實(shí)驗(yàn)所用的8個(gè)數(shù)據(jù)集均來(lái)自于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù),，每個(gè)數(shù)據(jù)集多類與少類樣本數(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)中，聚類中心個(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)聚類中心個(gè)數(shù)C取不同的值時(shí),，F(xiàn)CM-ELM算法的實(shí)驗(yàn)結(jié)果相差較小,，相對(duì)比較穩(wěn)定。

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

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

　　參考文獻(xiàn)

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

　　[2] 王和勇,，樊泓坤,，姚正安,，等.不平衡數(shù)據(jù)集的分類方法研究[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ù)分類方法[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] 肖景春,，張敏.基于減法聚類與模糊C-均值的模糊聚類的研究[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ù)分類方法綜述[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.