不平衡數(shù)據(jù)加權集成學習算法

徐麗麗，閆德勤

（1.遼寧師范大學 數(shù)學學院，遼寧 大連 116029；2.遼寧師范大學 計算機與信息技術學院，遼寧 大連 116081）

不平衡數(shù)據(jù)加權集成學習算法

徐麗麗1，閆德勤2

（1.遼寧師范大學 數(shù)學學院，遼寧 大連 116029；2.遼寧師范大學 計算機與信息技術學院，遼寧 大連 116081）

針對傳統(tǒng)的機器學習算法對不平衡數(shù)據(jù)集的少類分類準確率不高的問題，基于支持向量機和模糊聚類，提出一種不平衡數(shù)據(jù)加權集成學習算法。首先提出加權支持向量機模型（Weighted Support Vector Machine，WSVM），該模型根據(jù)不同類別數(shù)據(jù)所占比例的不同，為各類別分配不同的權重，然后將WSVM與模糊聚類結(jié)合提出一種新的集成學習算法。將本文提出的算法應用于人造數(shù)據(jù)集和UCI數(shù)據(jù)集實驗中，實驗結(jié)果表明，所提出的算法能夠有效地解決不平衡數(shù)據(jù)的分類問題，具有更好的分類性能。

不平衡數(shù)據(jù)集；權值；支持向量機；聚類；集成

0 引言

不平衡數(shù)據(jù)［1-2］分類問題一直備受關注，已成為機器學習領域中的研究熱點。現(xiàn)實生活中，存在著許多不平衡數(shù)據(jù)的例子。 如：醫(yī)療診斷、故障檢測等。 目前，不平衡數(shù)據(jù)分類問題的處理方法主要分為兩類：

數(shù)據(jù)層面上，主要是對原始數(shù)據(jù)集進行處理，利用少數(shù)類過采樣、多數(shù)類欠采樣等方法使原始數(shù)據(jù)集各類別數(shù)據(jù)個數(shù)達到相對平衡。過采樣技術 （Synthetic Minority Ove-rsampling Technique，SMOTE）［3］通過少類樣本和其近鄰樣本的線性關系獲得新的少類樣本，減少了過擬合現(xiàn)象，但在生成新樣本時存在盲目性，容易出現(xiàn)樣本混疊現(xiàn)象， 增加噪音樣本。 單邊選擇欠采樣技術（One-sided Selection）［4］尋找互為最近鄰的異類樣本對，并將其中的多類樣本判斷為噪聲點并刪除，但將噪聲點完全刪除，會丟失重要的數(shù)據(jù)信息。

算法層面上，主要是對已有分類算法進行改進或是設計新算法。趙相彬等人提出基于欠采樣與修正核函數(shù)相結(jié)合的 SVM算法［5］，根據(jù)保角變換修正 SVM的核函數(shù)，有效地提高了分類準確率。Seref等人提出Weighted Relaxed Support Vector Machine（WRSVM）［6］，WRSVM是代價敏感學習和 Relaxed SVM（RSVM）的結(jié)合，減少了離群點的影響。Lin等人提出基于SVM和聚類的不平衡數(shù)據(jù)分類算法［7］，該算法利用模糊聚類（FCM）將訓練集的多類數(shù)據(jù)集分成幾個子集，然后用每個子集和訓練集的少類分別訓練子分類器，最后通過投票原則確定最終分類結(jié)果。但 FCM并不是對數(shù)據(jù)集平均分組。例如，設多類數(shù)據(jù)個數(shù)為 100個，少類數(shù)據(jù)個數(shù)為 30個，則需將100個多類數(shù)據(jù)分為 3個子集，各子集個數(shù)可能為（24，36，40）、（10，25，65），當子集個數(shù)為 65時，和少類數(shù)據(jù)個數(shù) 30相比，兩類數(shù)據(jù)個數(shù)依然是不平衡的。

因此，針對這一問題，本文提出一種加權集成學習算法——Ensemble Weighted Sup-portVectorMachine based on FCM（FCM-EN WSVM）。首先提出加權支持向量機模型，該模型根據(jù)不同類別數(shù)據(jù)所占比例不同，為各類別分配不同的權重。然后利用 FCM將訓練集的多類數(shù)據(jù)分為若干子集，每個子集分別和訓練集的少類作為新的訓練集訓練多個WSVM分類器，最后對測試集進行測試，通過投票原則確定最終分類結(jié)果。新算法有效地解決了不平衡數(shù)據(jù)的分類問題。

1 支持向量機

支持向量機 （Support Vector Machine，SVM）［8-9］是Corinna Cortes和 Vapnik等人于 1995年首先提出的，其基本原理：假設給定帶有標簽的訓練集 S=｛（x1，y1），…，（xn，yn）｝，其中，xi∈RN表示樣本點，yi∈｛-1，1｝表示所屬類別標簽，i=1，…，n。則SVM模型的目標函數(shù)為：

其中 ξi為松弛變量，C為懲罰參數(shù)，建立拉格朗日函數(shù)，式（1）轉(zhuǎn)化為其對偶問題：

則其決策函數(shù)為：

在非線性可分情況下，輸入樣本空間找不到最優(yōu)分類超平面，因此將數(shù)據(jù)通過核函數(shù)映射到高維特征空間中，此時：

其決策函數(shù)為：

2 本文提出的算法

2.1 加權支持向量機（WSVM）

為了減小數(shù)據(jù)類別不平衡對SVM訓練模型的影響，根據(jù)每個類別數(shù)據(jù)對分類貢獻的不同，區(qū)別對待每一類別數(shù)據(jù)，為其分配不同的權值，則 WSVM模型的目標函數(shù)為：

其中W為各類別的權值矩陣。

式（6）的對偶問題為:

那么，映射到高維空間的決策函數(shù)為：

2.2 權值的定義

權值W需滿足以下條件：

（1）少類數(shù)據(jù)的權值大于多類數(shù)據(jù)的權值，即 Wshao＞W(wǎng)duo；

（2）Wi∈（0，1），且，C為數(shù)據(jù)的類別數(shù)。

設訓練集的樣本數(shù)為 N，類別數(shù)為 C，各類別的樣本數(shù)從小到大排序依次為 n1，n2，…，nC，則第 i類數(shù)據(jù)的權值定義為：

根據(jù)不同類別樣本個數(shù)所占的比例為其分配不同的權重，多類數(shù)據(jù)的權重大，少類數(shù)據(jù)的權重小，從而使各類別數(shù)據(jù)比例趨于平衡。

2.3 FCM-ENWSVM

模糊 C均值聚類算法 （Fuzzy C-means，F(xiàn)CM）［10］于1981年被 Bezdek提出。它的思想是將數(shù)據(jù)集劃分為不同的簇，要求同一簇的對象之間的相似度盡可能的大，而不同簇的對象之間的相似度盡可能的小。

FCM-ENWSVM算法 （基于支持向量機和聚類的不平衡數(shù)據(jù)加權集成學習算法）：

（1）計算訓練集的多類數(shù)據(jù)和少類數(shù)據(jù)的個數(shù)，并將其個數(shù)比記為M；

（2）利用FCM算法將多類數(shù)據(jù)集分為M個子集；

（3）M個子集分別和少類數(shù)據(jù)構(gòu)成新的訓練集，訓練M個WSVM分類器；

（4）分別用M個分類器對測試集進行測試。最終結(jié)果通過投票原則決定。

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

3.1 人造數(shù)據(jù)

隨機生成一個300×2的數(shù)據(jù)集，按3∶1的比例隨機分為訓練集和測試集。實驗中，分別用訓練集訓練SVM、WSVM兩種分類器，核函數(shù)選擇文獻［11］中的Linear、RBF。圖1、圖2分別表示兩種核函數(shù)的條件下，兩種分類器對測試集的測試結(jié)果，其中每幅圖中 Original表示測試集真實的類別分布，SVM、WSVM表示用SVM、WSVM兩種分類器分類后的測試集類別分布，加號表示正類 （少類）1，點表示負類（多類）0，圈表示錯分的數(shù)據(jù)點 F。

圖1 核函數(shù)為Linear時，SVM和WSVM對測試集預測前后的類別分布

圖2 核函數(shù)為RBF時，SVM和WSVM對測試集預測前后的類別分布

從圖1、圖2可以看出，在兩種核函數(shù)下，WSVM的分類正確數(shù)都明顯高于SVM的。WSVM考慮了不同類別數(shù)對分類準確率的貢獻多少，權值起到了平衡的作用，有效地提高了分類器的性能。

3.2 UCI數(shù)據(jù)實驗

從 UCI數(shù)據(jù)庫中選取了 6個數(shù)據(jù)集，分別為 wine、glass、housing、pima、breast、bupa，各數(shù)據(jù)集的基本信息如表1所示。

表1 6個數(shù)據(jù)集的基本信息

實驗中，將表1中的數(shù)據(jù)集按 3∶1的比例隨機分為訓練集和測試集，分類方法選擇SVM、FSVM［12］、RSVM［11］、FCM-SVM［7］、FCM-ENWSVM（本文算法），評價準則選擇文獻［13］中的G-means、F-measure［13］。為了充分驗證本文算法的有效性，圖3、圖4分別為 glass、wine數(shù)據(jù)的訓練集打亂順序進行8次實驗的結(jié)果折線圖，表2～表5為其他 4個數(shù)據(jù)集的實驗結(jié)果，均取循環(huán) 20次的平均值。

圖3 不同核函數(shù)下，glass的G-means和F-measure變化情況

圖4 不同核函數(shù)下，wine的G-means和F-measure變化情況

從圖3、圖4可以看出，本文提出的算法 FCM-ENWSVM的 G-means和 F-measure明顯高于其他方法。FCM-ENWSVM的變化比較穩(wěn)定，而SVM、FSVM、RSVM的變化較大，F(xiàn)CM-SVM雖然比較穩(wěn)定，但是準確率低，沒有考慮到 FCM不是對數(shù)據(jù)集進行平均分組，訓練集的多類、少類個數(shù)依然是不平衡的。然而，F(xiàn)CM-ENWSVM改進了這些算法的不足之處，通過FCM和權值改善了數(shù)據(jù)的不平衡性，具有更好的分類效果。

表2 核函數(shù)為Linear時的G-means

表3 核函數(shù)為Linear時的F-measure

表4 核函數(shù)為RBF時的G-means

從表2～表5中可以看出， 在不同的核函數(shù)下，F(xiàn)CM-ENWSVM的 G-means、F-measure都高于其他方法。特別地，對于 housing數(shù)據(jù)，當核函數(shù)為 Linear時，SVM、FSVM的 G-means、F-measure都為 0，而 FCMENWSVM的準確率相對較高。還可以發(fā)現(xiàn)，當多類少類的不平衡性差時，如bupa數(shù)據(jù)，SVM和 FCM-SVM的結(jié)果相同，說明在FCM-SVM中，F(xiàn)CM并沒有起到作用，準確率依然不高，而FCM-ENWSVM的卻相對較高。FCMENWSVM利用了FCM算法，并考慮到用權值來改善數(shù)據(jù)的類別不平衡度，從而解決了FCM不平均分組再次造成數(shù)據(jù)不平衡的問題，有效地提高了分類準確率。

4 結(jié)論

本文針對傳統(tǒng)分類算法對不平衡數(shù)據(jù)的分類準確率低的問題，基于支持向量機和模糊聚類，提出了一種不平衡數(shù)據(jù)加權集成學習算法。該算法根據(jù)不同類別樣本對分類貢獻的不同為每個類別分配不同的權重，提出加權支持向量機模型，并且利用模糊聚類算法對訓練集的多類數(shù)據(jù)進行聚類，聚類后的每個子集分別和訓練集的少類數(shù)據(jù)作為訓練集，訓練加權支持向量機子分類器。最后通過投票原則決定最終分類結(jié)果。將新算法應用于實例數(shù)據(jù)集的分類問題中，有效性和優(yōu)越性得到了證明。

［1］JAPKOW I，STEPHEN S.The class imbalance problem：a systermatic studay［J］.IntelligentData AnalysisJournal，2002，6（5）：429-450.

［2］YANG Q，WU X.10 challenging problems in data mining research［J］.International Journal of Info-rmation Technology&Decision Making，2006，5（4）：597-604.

［3］CHAWLA N V，BOWYER K W，HALL L O，et al. SMOTE： syntheticminorityover-samplingTechnique［J］. Journal of Artificial Intelligence Resaerch，2002（16）：321-357.

［4］KUBATm，MATWIN S.Addressing the curse of imbalanced training sets：one-sided selection［C］.Proceedings of the 14thInternational Conference on Machine Learning，San Francisco，1997：179-186.

［5］趙相彬，梁永全，陳雪.基于支持向機的不平衡數(shù)據(jù)分類研究［J］.計算機與數(shù)字工程，2013，41（2）：241-243.

［6］SEREF O，RAZZAGHI T，XANTHOPOULOS P.Weighted relaxed support vector machines［J］.Annals of Opearations Research，Springer US，2014（9）：1-37.

［7］Lin Kaibiao，Weng Wei，ROBERT K，et al.Imbalance data classification algorithm based on SVM and clustering function［C］.The 9th International Conference on Computer Science&Education，2014：544-548.

［8］CORTES C，VAPNIK V.Support-vector networks［J］.Machine Learning，1995，20（3）：237-297.

［9］VAPNIK V.Statistical learning theory［M］.New York：J.Wiley，1998.

［10］BEZDEK J.Pattern recognition with fuzzy objec-tive function algorithms［M］.New York：Plenum press，1981.

［11］梁紅霞，閆德勤.粗糙支持向量機 ［J］.計算機科學，2009，36（4）：208-210.

［12］Huang Hanpang，Liu Yihung.Fuzzy support vector machines for pattern recognition and data mining［J］.International Journal of Fuzzy Systems，2002，4（3）：826-835.

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

Weighted ensemble learning algorithm for imbalanced data sets

Xu Lili1，Yan Deqin2
（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 traditional machine learning algorithms didn′t get a high classification accuracy for the minority of unbalanced data sets，weighted ensemble learning algorithm for imbalanced data is proposed based on support vector machine and clustering.We propose weighted support vector machine model，which assign different weights for different classes data，according to the proportion of different categories of data.Then we combine WSVM with clustering into a new ensemble learning algorithms.The proposed algorithm is applied to the experiments of artificial data set and UCI data sets.The experimental results show that the proposed algorithm can effectively solve the problem of classification，and has better classification performance.

imbalanced data；weight；support vector machine；clustering；ensemble

TP18

A

1674-7720（2015）23-0007-04

徐麗麗，閆德勤.不平衡數(shù)據(jù)加權集成學習算法［J］.微型機與應用，2015，34（23）：7-10.

2015-08-07）

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

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