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

陳輝輝，白治江

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

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

陳輝輝，白治江

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

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

非平衡數(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)等問(wèn)題上具有較好的泛化能力，已被普遍應(yīng)用于各種樣本集的分類(lèi)問(wèn)題中[1-2]。然而，標(biāo)準(zhǔn)的SVM不僅對(duì)噪聲點(diǎn)或野點(diǎn)敏感，而且在處理非平衡數(shù)據(jù)集時(shí)，其決策面往往會(huì)向少數(shù)類(lèi)(正類(lèi))偏移，從而導(dǎo)致對(duì)少數(shù)類(lèi)(正類(lèi))的識(shí)別精確率降低。

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

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

給定訓(xùn)練集(X,Y)={(xi,yi),i=1,2,…,n},其中xi表示樣本，yi表示樣本xi的標(biāo)簽，yi∈{1,-1}。針對(duì)非線(xiàn)性可分的數(shù)據(jù)，引入了非線(xiàn)性映射Φ: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)化問(wèn)題(1)的對(duì)偶問(wèn)題：

(2)

假設(shè)對(duì)偶問(wèn)題(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)度。目前，有很多方法來(lái)設(shè)計(jì)模糊隸屬度函數(shù)，但是至今為止也沒(méi)有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)。文獻(xiàn)[11]采用了根據(jù)距離來(lái)設(shè)計(jì)模糊隸屬度的方法，把樣本到其所屬類(lèi)的中心距離作為依據(jù)。文獻(xiàn)[12]采用了S型模糊隸屬度函數(shù)，把樣本到其所屬類(lèi)的中心距離看做是一種非線(xiàn)性的關(guān)系。Lin Chunfu等人[6-7]學(xué)者提出了一個(gè)依據(jù)類(lèi)中心來(lái)設(shè)計(jì)模糊隸屬度的方案，使樣本點(diǎn)對(duì)分類(lèi)的影響隨著樣本點(diǎn)到其類(lèi)中心距離的增大而減小，從而來(lái)降低噪聲點(diǎn)或野點(diǎn)的影響。在文獻(xiàn)[13]中模糊隸屬度被定義為：

(6)

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

(7)

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

(8)

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

(9)

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

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

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

模糊支持向量機(jī)是在支持向量機(jī)的基礎(chǔ)之上，依據(jù)樣本在分類(lèi)過(guò)程中的作用不同，為不同的樣本賦予不同的模糊隸屬度，以此來(lái)增大算法對(duì)噪聲點(diǎn)或者野點(diǎn)的消除作用，提升分類(lèi)結(jié)果的精確度。對(duì)于二分類(lèi)問(wèn)題，給定的訓(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)

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

(11)

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

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

表1 混淆矩陣

矩陣[13]如表1所示。

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

針對(duì)不平衡數(shù)據(jù)集的分類(lèi)，本文提出了一種改良的模糊支持向量機(jī)算法，在設(shè)計(jì)模糊隸屬度時(shí)，不僅考慮樣本到其所在類(lèi)中心的距離，還考慮了樣本的緊密度特征，以此來(lái)降低噪聲點(diǎn)對(duì)分類(lèi)結(jié)果的影響，同時(shí)結(jié)合DEC算法，從而更好地解決不平衡數(shù)據(jù)集的分類(lèi)問(wèn)題。最后，通過(guò)對(duì)5種不同數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證了該算法的有效性。但是該算法在提高不平衡數(shù)據(jù)集分類(lèi)精度的同時(shí)，也在一定程度上增加了算法的復(fù)雜度，如何在提高分類(lèi)精度的同時(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] 練秋生，張偉.基于圖像塊分類(lèi)稀疏表示的超分辨率重構(gòu)算法[J].電子學(xué)報(bào)，2012，40(5)：920-925.

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

[13] 秦傳東，劉三陽(yáng)，張市芳.基于不平衡數(shù)據(jù)分類(lèi)的一種平衡模糊支持向量機(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ù)分類(lèi)[J].微型機(jī)與應(yīng)用，2017,36(16)：56-59.

2017-02-20)

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

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