基于聚類欠采樣的極端學習機

徐麗麗，閆德勤，高晴（.遼寧師范大學數學學院，遼寧大連609；.遼寧師范大學計算機與信息技術學院，遼寧大連608）

基于聚類欠采樣的極端學習機

徐麗麗1，閆德勤2，高晴1
（1.遼寧師范大學數學學院，遼寧大連116029；2.遼寧師范大學計算機與信息技術學院，遼寧大連116081）

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

極端學習機；聚類；不平衡數據；欠采樣；數據挖掘

0 引言

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

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

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

1 理論分析

1.1 極端學習機算法（ELM）

極端學習機（Extreme Learning Machine，ELM）[8-9]是一種快速的單隱層前饋神經網絡訓練算法。該算法的特點是隨機選取輸入權值向量及隱層神經元的偏置，在訓練的過程中，只需要設置隱層節點的個數，便可通過一個簡單的線性系統求出唯一的最優解。

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

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

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

簡記為：

ELM算法意在找到最優的β^，使得：

那么問題就轉化為求Hβ=T的最小二乘解β^。當M≥N時，矩陣H可直接求逆；當M<

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

最小二乘解β^即為輸出權值，所求解問題最終轉化為求解一個矩陣的廣義逆問題。與傳統的分類算法相比，ELM算法能一次性求出輸出權值，不需要任何迭代過程，減少了調節參數的時間，從而提高了運算速度。

ELM算法的主要步驟：

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

（2）隨機生成輸入權值向量ai和偏置bi；

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

（4）由β=H+T，計算輸出權值β；

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

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

1.2 模糊聚類算法（FCM）

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

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

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

由拉格朗日乘子法，構造新的目標函數：

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

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

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

本文算法的主要步驟：

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

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

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

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

3 不平衡數據分類性能的評價指標

表1是數據二分類問題的混淆矩陣，TP、TN分別為分類正確的少數類和多數類的樣本個數，FN、FP分別為分類錯誤的少數類和多數類的樣本個數。

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

不平衡數據分類性能評價指標的相關定義如下：

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

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

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

定義5負類樣本的正確率（Specificity）：

不平衡數據分類性能的評價指標一般有以下幾個[12-13]：

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

（3）ROC曲線（Receiver Operating Characteristic）[14]：

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

4 實驗結果及分析

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

表2 各個數據集的基本信息

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

表3 ELM算法和不同C值的FCM-ELM算法的G-means

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

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

從表3～表5可以看出，FCM-ELM算法的準確率明顯優于ELM算法。在前六個比例失衡程度較小的數據集中，準確率最多提高了20%，最后兩個比例失衡程度較大的數據集中，準確率最多提高了63%。而且，當聚類中心個數C取不同的值時，FCM-ELM算法的實驗結果相差較小，相對比較穩定。

5 結束語

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

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

[2]王和勇，樊泓坤，姚正安，等.不平衡數據集的分類方法研究[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組合的不平衡數據分類方法[J].計算機工程，2011，37（14）：178-182.

[7]李明方，張化祥.針對不平衡數據的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]林智勇，郝志峰，楊曉偉.若干評價準則對不平衡數據學習的影響[J].華南理工大學學報，2010，38（4）：126-135.

[13]楊明，尹軍梅，吉銀林.不平衡數據分類方法綜述[J].南京師范大學學報：工程技術版，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

徐麗麗，閆德勤，高晴.基于聚類欠采樣的極端學習機[J].微型機與應用，2015，34（17）：81-84.

2015-04-13）

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

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

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