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

　　關鍵詞： 不平衡數據集；權值；支持向量機；聚類；集成

0 引言

　　不平衡數據[1-2]分類問題一直備受關注，已成為機器學習領域中的研究熱點?，F實生活中，存在著許多不平衡數據的例子。如：醫療診斷、故障檢測等。目前，不平衡數據分類問題的處理方法主要分為兩類：

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

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

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

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模型的目標函數為：

　　其中?孜i為松弛變量，C為懲罰參數，建立拉格朗日函數，式（1）轉化為其對偶問題：

　　則其決策函數為：

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

　　其決策函數為：

　　2 本文提出的算法

　　2.1 加權支持向量機（WSVM）

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

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

　　式（6）的對偶問題為:

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

　　2.2 權值的定義

　　權值W需滿足以下條件：

　　（1）少類數據的權值大于多類數據的權值，即Wshao>Wduo；

　?。?）Wi∈（0，1），且，C為數據的類別數。

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

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

　　2.3 FCM-ENWSVM

　　模糊C均值聚類算法（Fuzzy C-means，FCM）[10]于1981年被Bezdek提出。它的思想是將數據集劃分為不同的簇，要求同一簇的對象之間的相似度盡可能的大，而不同簇的對象之間的相似度盡可能的小。

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

　?。?）計算訓練集的多類數據和少類數據的個數，并將其個數比記為M；

　?。?）利用FCM算法將多類數據集分為M個子集；

　?。?）M個子集分別和少類數據構成新的訓練集，訓練M個WSVM分類器；

　?。?）分別用M個分類器對測試集進行測試。

　　最終結果通過投票原則決定。

3 實驗結果及分析

　　3.1 人造數據

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

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

　　3.2 UCI數據實驗

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

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

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

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

4 結論

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

參考文獻

　　[1] JAPKOW I， STEPHEN S. The class imbalance problem： a systermatic studay[J]. Intelligent Data Analysis Journal，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： synthetic minority over-sampling Technique[J]. Journal of Artificial Intelligence Resaerch， 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] 趙相彬，梁永全，陳雪.基于支持向機的不平衡數據分類研究[J].計算機與數字工程，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.