基于模糊支持向量機(jī)的非平衡數(shù)據(jù)分類

陳輝輝，白治江

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

基于模糊支持向量機(jī)的非平衡數(shù)據(jù)分類

陳輝輝，白治江

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

支持向量機(jī)(SVM)作為一種有效的機(jī)器學(xué)習(xí)技術(shù)可以很好地處理平衡數(shù)據(jù)集，然而除了對(duì)噪聲點(diǎn)和野點(diǎn)敏感以外，SVM在非平衡數(shù)據(jù)分類時(shí)會(huì)偏向多數(shù)類(負(fù)類)樣本，從而導(dǎo)致少數(shù)類(正類)的分類精度變差。為了克服以上問題，提出了一種改進(jìn)的模糊支持向量機(jī)(FSVM)算法。新算法在設(shè)計(jì)模糊隸屬度時(shí)，不僅考慮樣本到其所在類中心的距離，還考慮了樣本的緊密度特征。實(shí)驗(yàn)結(jié)果表明，相對(duì)于標(biāo)準(zhǔn)SVM及已有的FSVM模型，新方法對(duì)于非平衡且含有噪聲的數(shù)據(jù)集有更好的分類效果。

非平衡數(shù)據(jù)集；模糊支持向量機(jī)；模糊隸屬度；樣本緊密度

0 引言

支持向量機(jī)(SVM)是建立在統(tǒng)計(jì)學(xué)習(xí)中的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則基礎(chǔ)上的一種機(jī)器學(xué)習(xí)方法，因其在解決局部極小、維數(shù)災(zāi)難以及實(shí)現(xiàn)全局最優(yōu)等問題上具有較好的泛化能力，已被普遍應(yīng)用于各種樣本集的分類問題中[1-2]。然而，標(biāo)準(zhǔn)的SVM不僅對(duì)噪聲點(diǎn)或野點(diǎn)敏感，而且在處理非平衡數(shù)據(jù)集時(shí)，其決策面往往會(huì)向少數(shù)類(正類)偏移，從而導(dǎo)致對(duì)少數(shù)類(正類)的識(shí)別精確率降低。

目前，用SVM對(duì)非平衡數(shù)據(jù)集分類問題的研究主要集中在算法和數(shù)據(jù)兩個(gè)層面。在算法層面，主要是對(duì)SVM訓(xùn)練模型進(jìn)行改進(jìn)以提高少數(shù)類的分類精度。VEROPOULOS K[3]提出了一種Biased支持向量機(jī)(BSVM)算法，在對(duì)樣本的訓(xùn)練過程中賦予少數(shù)類(正類)較大的懲罰參數(shù)來保證少數(shù)類(正類)樣本盡可能被分對(duì)，從而提高少數(shù)類(正類)的分類精度。FREUND Y和SCHAPIRE R E[4]在Boosting算法的基礎(chǔ)上提出了一種改進(jìn)的Adaboost算法，該算法在前一次分類結(jié)果的基礎(chǔ)之上更新樣本的權(quán)值，減少已被正確分類的權(quán)值，同時(shí)增加錯(cuò)分樣本的權(quán)值，從而提高對(duì)不平衡數(shù)據(jù)集的分類性能。在數(shù)據(jù)層面，主要利用過采樣技術(shù)和欠采樣技術(shù)對(duì)數(shù)據(jù)集進(jìn)行重采樣。過采樣主要包括隨機(jī)過采樣、SMOTE[5]算法等。文獻(xiàn)[6]在SMOTE算法的基礎(chǔ)之上，提出了一種基于混合重采樣的SMOTE算法——HB_SMOTE算法。過采樣方法雖然能夠提高分類精確率，但是有可能增加算法復(fù)雜度。欠采樣方法主要有隨機(jī)欠采樣、聚類欠采樣等。采用欠采樣雖然可以降低算法復(fù)雜度，但在刪除樣本時(shí)會(huì)造成樣本信息缺失從而影響分類的精確性。

1 支持向量機(jī)簡(jiǎn)介

給定訓(xùn)練集(X,Y)={(xi,yi),i=1,2,…,n},其中xi表示樣本，yi表示樣本xi的標(biāo)簽，yi∈{1,-1}。針對(duì)非線性可分的數(shù)據(jù)，引入了非線性映射Φ:xi→Φ(xi)，將訓(xùn)練樣本xi映入高維空間。選取適當(dāng)?shù)暮撕瘮?shù)k(xi,yj)=Φ(xi)·Φ(xj)。引入松弛變量ξi≥0,i=1,2,…,n以及懲罰因子C。標(biāo)準(zhǔn)支持向量機(jī)(SVM)以如下形式表示：

s.t.yi(ωTΦ(xi)+b)≥1-ξi,ξi≥0,i=1,2,…,n

(1)

求解優(yōu)化問題(1)的對(duì)偶問題：

(2)

假設(shè)對(duì)偶問題(2)最優(yōu)解為α*，則最優(yōu)超平面的法向量為:

(3)

(4)

由此可以得到?jīng)Q策函數(shù)為:

(5)

2 模糊隸屬度的設(shè)計(jì)

在模糊支持向量機(jī)中模糊隸屬度有著至關(guān)重要的作用，因?yàn)樗鼪Q定了樣本點(diǎn)對(duì)超平面的貢獻(xiàn)度。目前，有很多方法來設(shè)計(jì)模糊隸屬度函數(shù)，但是至今為止也沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)。文獻(xiàn)[11]采用了根據(jù)距離來設(shè)計(jì)模糊隸屬度的方法，把樣本到其所屬類的中心距離作為依據(jù)。文獻(xiàn)[12]采用了S型模糊隸屬度函數(shù)，把樣本到其所屬類的中心距離看做是一種非線性的關(guān)系。Lin Chunfu等人[6-7]學(xué)者提出了一個(gè)依據(jù)類中心來設(shè)計(jì)模糊隸屬度的方案，使樣本點(diǎn)對(duì)分類的影響隨著樣本點(diǎn)到其類中心距離的增大而減小，從而來降低噪聲點(diǎn)或野點(diǎn)的影響。在文獻(xiàn)[13]中模糊隸屬度被定義為：

(6)

但是，這些設(shè)計(jì)方法都僅僅是將樣本到其所在類中心的距離作為設(shè)計(jì)模糊隸屬度的主要依據(jù)，對(duì)處于類中心的樣本點(diǎn)賦予較大值的模糊隸屬度，但是對(duì)于不平衡的數(shù)據(jù)集，這些設(shè)計(jì)仍存在把噪聲樣本作為正常樣本來處理的可能性，從而導(dǎo)致分類結(jié)果的精確度降低。文獻(xiàn)[14-15]提出了一種根據(jù)樣本緊密度特征來設(shè)計(jì)模糊隸屬度的方法，采用基于K近鄰原則來設(shè)計(jì)樣本緊密度，對(duì)于每一個(gè)訓(xùn)練樣本xi，找到距離其最鄰近的K個(gè)點(diǎn)，對(duì)于一個(gè)正類樣本定義其樣本的緊密度為：

(7)

同理，針對(duì)一個(gè)負(fù)類樣本xi，它的緊密度可以定義為：

(8)

本文給出了一種設(shè)計(jì)模糊隸屬度的新方案，在設(shè)計(jì)模糊隸屬度時(shí)，不僅考慮樣本到其所在類中心的距離，還考慮了樣本的緊密度特征。結(jié)合樣本到類中心的距離(公式(6))以及樣本的緊密度(公式(7)、(8))來設(shè)計(jì)模糊隸屬度,本文定義模糊隸屬度如下：

(9)

其中，α∈[0,1],在本文中k的取值設(shè)為5。

3 懲罰因子的設(shè)計(jì)

4 基于非平衡數(shù)據(jù)分類的模糊支持向量機(jī)算法

模糊支持向量機(jī)是在支持向量機(jī)的基礎(chǔ)之上，依據(jù)樣本在分類過程中的作用不同，為不同的樣本賦予不同的模糊隸屬度，以此來增大算法對(duì)噪聲點(diǎn)或者野點(diǎn)的消除作用，提升分類結(jié)果的精確度。對(duì)于二分類問題，給定的訓(xùn)練集(X,Y)就轉(zhuǎn)化成為模糊訓(xùn)練樣本集(X,Y,S)={(xi,yi,si),i=1,2,3,…,n}，其中xi是訓(xùn)練樣本集，yi∈{1,-1}是樣本標(biāo)簽，si(0

s.t.yi(ωTΦ(xi)+b)≥1-ξi,ξi≥0,i=1,2,…,n

(10)

于是問題(10)的對(duì)偶問題如下：

(11)

5 實(shí)驗(yàn)與實(shí)驗(yàn)結(jié)果分析

5.1 評(píng)價(jià)指標(biāo)

表1 混淆矩陣

矩陣[13]如表1所示。

表1中的TP、FN、FP和TN分別表示分類正確的正類樣本、不正確的負(fù)類樣本、不正確的正類樣本和正確的負(fù)類樣本的數(shù)目，其中TP+FN=N+，F(xiàn)P+TN=N-。

然而，對(duì)于非平衡數(shù)據(jù)集的分類而言，已經(jīng)不適合使用分類正確率來對(duì)實(shí)驗(yàn)結(jié)果評(píng)定，而是采用非平衡數(shù)據(jù)分類中的敏感性Se、特異性Sp和幾何平均值Gm來進(jìn)行評(píng)價(jià)，它們的定義如下：

其中，Se代表分類器預(yù)測(cè)正類樣本的能力，Sp代表分類器預(yù)測(cè)負(fù)類樣本的能力，Se和Sp的值越大表示分類效果越好。Gm表示分類器在非平衡數(shù)據(jù)集上的性能。

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

為了驗(yàn)證所提算法的合理性和有效性，從UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫選擇了5種不平衡的數(shù)據(jù)集來進(jìn)行實(shí)驗(yàn)。由于數(shù)據(jù)集可能有幾種類別，對(duì)于類別不是兩類的就先把數(shù)據(jù)集都變?yōu)閮深悾x擇其中某類當(dāng)作正類，剩下的所有類合并作為負(fù)類。對(duì)Abanole數(shù)據(jù)集選擇類標(biāo)為15的當(dāng)作正類，對(duì)Yeast數(shù)據(jù)集選擇類標(biāo)為5的當(dāng)作正類，對(duì)Ecoli數(shù)據(jù)集選擇類標(biāo)為2的作為正類，對(duì)Haberman數(shù)據(jù)集選擇類標(biāo)為2的當(dāng)作正類，對(duì)PimaIndians數(shù)據(jù)集選擇類標(biāo)為1的當(dāng)作正類。這5種數(shù)據(jù)集的詳細(xì)描述詳如表2所示。

表2 數(shù)據(jù)集描述

表3 Abanole數(shù)據(jù)集在不同算法下的分類情況

表4 Yeast數(shù)據(jù)集在不同算法下的分類情況

表5 Ecoli數(shù)據(jù)集在不同算法下的分類情況

表6 Haberman數(shù)據(jù)集在不同算法的分類情況

表7 PimaIndians數(shù)據(jù)集在不同算法下的分類情況

6 結(jié)論

針對(duì)不平衡數(shù)據(jù)集的分類，本文提出了一種改良的模糊支持向量機(jī)算法，在設(shè)計(jì)模糊隸屬度時(shí)，不僅考慮樣本到其所在類中心的距離，還考慮了樣本的緊密度特征，以此來降低噪聲點(diǎn)對(duì)分類結(jié)果的影響，同時(shí)結(jié)合DEC算法，從而更好地解決不平衡數(shù)據(jù)集的分類問題。最后，通過對(duì)5種不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了該算法的有效性。但是該算法在提高不平衡數(shù)據(jù)集分類精度的同時(shí)，也在一定程度上增加了算法的復(fù)雜度，如何在提高分類精度的同時(shí)降低算法的復(fù)雜度將是下一步研究的重點(diǎn)。

[1] CORTES C，VAPNIK V.Support-vector networks[J].MachineLearning，1995，20(3)：273-297.

[2] 程然.最小二乘支持向量機(jī)的研究和應(yīng)用[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

[3] VEROPOULOS K，CAMPBELL C，CRISTIMANINI N.Controlling the sensitivity of support vcetor machines[C].Proceedings of the International Joint Conferences on Artificial Intelligence，1999，4：55-60.

[4] FREUND Y，SHAPIRE R E. A decision theoretic generalization of on line learning and an application to boosting[J].Jounal of Computer and System Sciences， 1997，119-139.

[5] 鄭文昌，陳淑燕，王宣強(qiáng).面向不平衡數(shù)據(jù)集的SMOTE-SVM交通事件檢測(cè)算法[J].武漢理工大學(xué)學(xué)報(bào)，2012，34(11):58-62.

[6] 郭亞偉.基于混合重采樣的非平衡數(shù)據(jù)SVM訓(xùn)練方法[J].微型機(jī)與應(yīng)用，2016，35(12):52-54.

[7] Lin Chunfu，Wang Shengde.Fuzzy support vector machines[J]. IEEE Transactions on Neural Networks，2002，13 (2):464-471.

[8] 趙克楠，李雷，鄧楠.一種構(gòu)造模糊隸屬度的新方法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012，22(8):75-77.

[9] Qin Chuandong，Liu Sanyang，Zhang Shifang.Balanced fuzzy support vector machines based on imbalanced data sets[J].Computer Science, 2012,39(6)：188-212.

[10] BATUWITA R，PALADE V. FSVM-CIL：fuzzy support vector machines for class imbalance learing[J].IEEE Transactions on Fuzzy Systems，2010，18(3)：558-571.

[11] 練秋生，張偉.基于圖像塊分類稀疏表示的超分辨率重構(gòu)算法[J].電子學(xué)報(bào)，2012，40(5)：920-925.

[12] 邊肇祺，張學(xué)工.模式識(shí)別(第2版)[M].北京：清華大學(xué)出版社，2000.

[13] 秦傳東，劉三陽，張市芳.基于不平衡數(shù)據(jù)分類的一種平衡模糊支持向量機(jī)[J].計(jì)算機(jī)科學(xué)，2012，39(6)：188-190.

[14] 周廣千，徐蔚鴻，楊志勇.一種新的模糊支持向量機(jī)算法[J].微計(jì)算機(jī)信息，2010，26(3)：217-218.

[15] 唐浩，廖與禾，孫峰，等.具有模糊隸屬度的模糊支持向量機(jī)算法[J].西安交通大學(xué)學(xué)報(bào)，2009，43(7)：40-43.

[16] VEROPOULOS K，CAMPBELL C，CRISTIANINI N. Controlling the sensitivity of support vector machines[C]. International Joint Couference on Ai,1999：55-60.

Imbalanced data classification based on FSVM

Chen Huihui, Bai Zhijiang

(Information Engineering College, Shanghai Maritime University, Shanghai 201306, China)

As an effective machine learning technology, support vector machine (SVM) can effectively handle the balanced datasets. However, aside from being sensitive to the noise points and outliers, SVM tends to bias towards the majority(negative) class in an imbalanced data set and this leads to a poor classification accuracy of minority(positive) class.In this paper, an improved fuzzy support vector machine (FSVM) algorithm is proposed to deal with these problems. When designing the fuzzy membership in the new algorithm, we take into consideration not only the distance from the sample to the center of its class but also the tightness of the samples. The experimental results show that compared to the standard SVM algorithm and the other FSVM models, the new method has better performance in the imbalanced and noise-containing datasets.

imbalanced datasets; FSVM; fuzzy membership degree; tightness of a sample

TP18

A

10.19358/j.issn.1674- 7720.2017.16.016

陳輝輝，白治江.基于模糊支持向量機(jī)的非平衡數(shù)據(jù)分類[J].微型機(jī)與應(yīng)用，2017,36(16)：56-59.

2017-02-20)

陳輝輝(1992-)，男，碩士，主要研究方向：信息處理與模式識(shí)別。

白治江(1962-)，男，博士，副教授，主要研究方向：模式識(shí)別、人工智能。