徐麗麗，閆德勤，高晴（.遼寧師范大學(xué)數(shù)學(xué)學(xué)院，遼寧大連609；.遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧大連608）

基于聚類欠采樣的極端學(xué)習(xí)機(jī)

徐麗麗1，閆德勤2，高晴1
（1.遼寧師范大學(xué)數(shù)學(xué)學(xué)院，遼寧大連116029；2.遼寧師范大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，遼寧大連116081）

針對(duì)極端學(xué)習(xí)機(jī)算法對(duì)不平衡數(shù)據(jù)分類問題的處理效果不夠理想，提出了一種基于聚類欠采樣的極端學(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ì)測試集進(jìn)行測試。實(shí)驗(yàn)結(jié)果表明，新算法有效地降低了數(shù)據(jù)的不平衡對(duì)分類準(zhǔ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ī)療診斷病變信息、垃圾信息過濾、故障檢測等。正如這些實(shí)例，少數(shù)類數(shù)據(jù)所包含的信息往往是我們所需要的。因此，怎樣更好地提取這部分?jǐn)?shù)據(jù)，已成為數(shù)據(jù)挖掘研究中的一個(gè)熱點(diǎn)話題。

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

極端學(xué)習(xí)機(jī)作為一種分類算法，具有訓(xùn)練速度快、泛化性能好等特點(diǎn)，但其對(duì)不平衡數(shù)據(jù)分類問題的處理效果并不理想。本文提出了一種基于聚類欠采樣的極端學(xué)習(xí)機(jī)分類算法。為方便起見，本文主要考慮數(shù)據(jù)二分類的問題。算法首先利用聚類原理對(duì)訓(xùn)練集中的負(fù)類樣本進(jìn)行聚類生成不同的簇，并計(jì)算各簇?cái)?shù)據(jù)與簇中心的距離并排序，然后在每個(gè)簇中按規(guī)定的采樣率取出距離中心近的數(shù)據(jù)，與訓(xùn)練集的正類一起組成類別相對(duì)平衡的數(shù)據(jù)集，最后訓(xùn)練分類器，預(yù)測測試集數(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)練的過程中，只需要設(shè)置隱層節(jié)點(diǎn)的個(gè)數(shù)，便可通過一個(gè)簡單的線性系統(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ù)樣本，也就是說，存在參數(shù)（ai，bi）和βi使得：

簡記為：

ELM算法意在找到最優(yōu)的β^，使得：

那么問題就轉(zhuǎn)化為求Hβ=T的最小二乘解β^。當(dāng)M≥N時(shí)，矩陣H可直接求逆；當(dāng)M<

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

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

ELM算法的主要步驟：

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

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

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

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

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

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

1.2 模糊聚類算法（FCM）

模糊C均值聚類算法（Fuzzy C-Means，F(xiàn)CM）[10-11]于1981年被Bezdek提出，是一種柔性的模糊劃分。它的思想是將數(shù)據(jù)集劃分為不同的簇，用值在0，1間的隸屬度來確定每個(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簇的采樣率為：

本文算法的主要步驟：

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

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

（3）對(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ù)測測試集的標(biāo)簽。

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

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

表1 二分類問題的混淆矩陣

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

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

定義3正類樣本的查全率（Recall）：

定義4正類樣本的正確率（Sensitivity）：

定義5負(fù)類樣本的正確率（Specificity）：

不平衡數(shù)據(jù)分類性能的評(píng)價(jià)指標(biāo)一般有以下幾個(gè)[12-13]：

（1）幾何平均值（G-means）：

（3）ROC曲線（Receiver Operating Characteristic）[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）來評(píng)估分類器性能。AUC值越大，分類器性能越好，反之越差。

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

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

表2 各個(gè)數(shù)據(jù)集的基本信息

實(shí)驗(yàn)中，采用十折交叉驗(yàn)證方法將數(shù)據(jù)集分為訓(xùn)練集和測試集，選用ELM算法、FCM-ELM算法進(jìn)行對(duì)比實(shí)驗(yàn)。兩種算法的激活函數(shù)均選擇Sigmoid函數(shù)，隱層節(jié)點(diǎn)數(shù)設(shè)為200。訓(xùn)練集、測試集的劃分存在一定的隨機(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 ELM算法和不同C值的FCM-ELM算法的G-means

表4 ELM算法和不同C值的FCM-ELM算法的F-measure

表5 ELM算法和不同C值的FCM-ELM算法的AUC

從表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é)束語

本文針對(duì)不平衡數(shù)據(jù)的分類問題，提出了一種基于聚類欠采樣的極端學(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ò)分問題。將新算法用于實(shí)例數(shù)據(jù)集的分類問題中，其有效性和優(yōu)越性得到了證明。

[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.

Extreme learning machine based on clustering and under-sam p ling

Xu Lili1，Yan Deqin2，Gao Qing1
（1.School of Mathematics，Liaoning Normal University，Dalian 116029，China；2.School of Computer and Information Technology，Liaoning Normal University，Dalian 116081，China）

Aiming at the problem that Extreme Learning Machine（ELM）is unsatisfying in dealing with imbalanced data set，an ELM algorithm based on clustering and under-sampling is proposed.Firstly，the new algorithm clusters the negative samples of training set and generates different clusters.Secondly，it takes samples in every cluster according the specified sampling rate，the data sampled make up a new negative data set，which can make the positive and negative data balanced in training set.Lastly，it trains the classifier and predicts the test set.The experimental results show that the new algorithm can effectively reduce the influence of imbalanced data for classification accuracy and has better classification performance.

extreme learning machine；clustering；imbalanced data；under-sampling；data mining

TP18

A

1674-7720（2015）17-0081-04

徐麗麗，閆德勤，高晴.基于聚類欠采樣的極端學(xué)習(xí)機(jī)[J].微型機(jī)與應(yīng)用，2015，34（17）：81-84.

2015-04-13）

徐麗麗（1990-），通信作者，女，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、圖像處理等。E-mail：xulili0419@126.com。

閆德勤（1962-），男，博士，教授，主要研究方向：模式識(shí)別、數(shù)據(jù)挖掘等。

高晴（1990-），女，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、圖像處理等。