一種新的模糊支持向量機多分類算法

266510；3.泰山學院 數學與系統科學系， 山東 泰安 271021）

摘 要：在模糊多分類問題中，由于訓練樣本在訓練過程中所起的作用不同，對所有數據包括異常數據賦予一個隸屬度。針對模糊支持向量機（fuzzy support vector machines，FSVM）的第一種形式，引入類中心的概念，結合一對多1aa(oneagainstall)組合分類方法，提出了一種基于一對多組合的模糊支持向量機多分類算法，并與1a1(oneagainstone)組合和1aa組合的分類算法比較。數值實驗表明，該算法是有效的，有較高的分類準確率，有更好的泛化能力。

關鍵詞：支持向量機；模糊支持向量機；一對多組合；隸屬函數；多分類算法

中圖分類號：TP391 文獻標志碼：A

文章編號：1001-3695(2008)07-2041-02



New multiclassification algorithm based on fuzzy support vector machines



LIU Taian1，LIANG Yongquan2，XUE Xin3

（1.Dept. of Information Engineering， Shandong University of Science Technology， Tai’an Shandong 271019， China；2.College of Information Science Engineering， Shandong University of Science Technology， Qingdao Shandong 266510， China；3.Dept. of Mathematics System Science， Taishan University， Tai’an Shandong 271021， China）

Abstract:In the fuzzy multiclassification problem，gave a degree of membership to all the data including abnormal data as the training samples played different affections in the training procession. Facing to the first form of fuzzy support vector machines，used the concept of the class center. Considered with the oneagainstall association assorting method，put out a new fuzzy support vector machines multiclassification model based on oneagainstall association，and compared with oneagainstone and oneagainstall association assorting method. The numerical test has improved that the algorithm is effective， and it has higher accurate rate of classification，also better ability of generalization.

Key words:support vector machines(SVM);fuzzy support vector machines(FSVM);oneagainstall;membership function;multiclassification algorithm

0 引言

模糊支持向量機(FSVM)是一種改進的支持向量機SVM。FSVM有兩種表現形式：a)2002年由臺灣學者Lin Chunfu等人提出的，根據訓練樣本在訓練過程中所起的作用不同，對所有數據包括異常數據賦予一個隸屬度，加大對容易錯分樣本的懲罰，以改進SVM性能的模糊支持向量機^[1]；b)2001和2002年由日本學者Takuga與Shigeo提出的，針對兩類問題推廣到多分類問題時，決策過程中存在不可分區域，構造隸屬函數，以減少不可分區域的模糊支持向量機^[2，3]。目前對FSVM的理論以及應用的研究是SVM領域研究的一個熱點，對解決模糊分類問題有重要的理論意義和應用價值。

1 模糊支持向量機FSVM

在機器學習的訓練過程中，每個訓練數據對支持向量機所起的作用是不同的。邊緣數據是最容易錯分的且成為支持向量的機會多一些，而中間的數據成為支持向量的可能性要小一些，甚至根本不可能成為支持向量。文獻[1，4]根據訓練樣本在訓練過程中的不同作用，對所有數據包括異常數據賦予一個隸屬度。

對于最簡單的兩分類問題，首先對數據進行預處理：事先選擇一個適當的隸屬函數，對所有樣本進行模糊化，得到每一個樣本xi隸屬度si，于是訓練集合便成為模糊訓練集：

其中:xi∈Rm；yi∈{+1，-1}；0≤si≤1。

對于上述新的訓練集，為了得到最優分類超平面，需要解決以下優化問題：

其中：C為常量；將xi從Rm映射到高維空間，將隸屬度si引入決策函數的生成過程，求解式(1)(2)的優化問題，可由以下Lagrange函數的鞍點給出： 

其中:α=(α1，α2，…，αn)；β=(β1，β2，…，βn)為Lagrange乘子，將式(3)分別對ω、b、ξ求導并置為0，則有

將式(4)代入(3)可將式(1)(2)轉換為

通過解決優化問題式（5）（6），構造出最優分類超平面，得到決策函數。

對于多分類問題，目前使用較多的方法有1aa方法^[5]、1a1方法^[6]和DDAG方法^[7，8]。S.Abe等人提出的解決多分類問題的FSVM是在這些方法的基礎上，構造隸屬函數以減少不可分區域，達到解決問題的目的。

基于同樣的思想方法，將其推廣到FSVM的第一種形式，便得到了筆者提出的基于一對多組合的模糊支持向量機多分類算法。

2 基于一對多組合的模糊支持向量機多分類算法

在該算法中，對于一個k分類問題，有如下的訓練樣本：

其中：xi∈Rm；yi∈{1，2，…，k}；0≤si≤1。

首先引入類中心的概念^[9]。

定義1 對于Rm上的一類點{x1，x2，…，xn}，記xc為類中心點，r為類半徑。其中：

結合一對多組合思想進行分類，即訓練k個兩類分類器，且每次訓練過程都是引入模糊性的，即事先為每個樣本xi生成一個模糊隸屬度si。例如現在要將第l類和剩余樣本分開，由以上定義易得第l類的中心點，記為x+，類半徑記為r+；剩余樣本看做一類，其中心點記為x_，類半徑記為r_。給定一個充分小的δ，模糊隸屬度si可定義為

接下來進行模糊支持向量機的訓練過程，每次可得一個兩類分類器。當所有訓練結束時，得到k個兩類分類器：

通過下面的數值實驗，驗證了該算法的有效性。

3 數值實驗

將第2章中提出的算法進行數值實驗。實驗機器配置：奔騰IV 3.0 GHz CPU，256 MB內存，Windows XP操作系統。利用MATLAB 6.5進行編程，所采用的數據是UCI公共數據庫的Iris和Wine數據集^[10]。由于所選用的數據集沒有提供測試數據，將數據集隨機地分成三份，其中兩份作為訓練數據，一份作為測試數據。Iris數據集的主要指標是：3類別、4屬性、150個樣本；Wine數據集的主要指標是：3類別、13屬性、178個樣本。

在實驗中，使用多項式核函數、徑向基核函數（RBF），與經典1a1組合、1aa組合進行性能比較。測試結果如表1所示。

從表1可以看出，新提出的基于一對多組合的模糊支持向量機多分類算法分類正確率較高，相對于1a1組合和1aa組合，它考慮了類別間歸屬的模糊性，因此有更好的泛化能力。

4 結束語

針對FSVM的第一種形式，為了突出數據中各樣本點的重要程度的差異，同時為了減少噪聲數據對分類結果的影響，對所有數據包括異常數據賦予一個隸屬度，結合一對多組合分類方法，提出了一種基于一對多組合的模糊支持向量機多分類算法，并與1a1組合和1aa組合的分類算法比較。數值實驗表明，該算法有較高的分類準確率，有更好的泛化能力，為模糊多分類問題提供了一個有效的分類方法。

參考文獻：

［1］LIN Chunfu，WANG Shengde.Fuzzy support vector machines[J].IEEE Trans on Neural Networks，2002，13(2):464-471.

[2]INOUE T，ABE S.Fuzzy support vector machines for patter classification[C]//Proc of International Joint Conference on Neural Networks.Washington DC:[s.n.]，2001:14491455.

[3]TSUJINISHI D，ABE S.Fuzzy least squares support vector machines for multiclass problems[J].Neural Networks，2003，16(5-6):758792.

[4]HUANG H P，LIU Y H.Fuzzy support vector machines for pattern recognition and data mining[J].International Journal of Fuzzy Systems，2002，4(3):826-835.

[5]ABE S.Analysis of multiclass support vector machines[C]//Proc of International Conference on Computational Intelligence for Modeling Control and Automation.2003:385-396.

[6]HSU C W，LIN C J. A comparison of methods for multiclass support vector machines[J].IEEE Trans on Neural Networks，2002，13(2):415-425.

[7]PLATT J C，CRISTIANINI N.Large margin DAG’s for multiclass classification[C]//Proc of Advances in Neural Information Processing Systems.Cambridge:MIT Press，2002:547-553.

[8]KIJSIRIKUL B，USSIVAKUL N.Multiclass support vector machines using adaptive directed acyclic graph[C]//Proc of International Joint Conference on Neural Networks.2002:980-985.

[9]CRISTANINI N，SHAWER TAYLOR J.支持向量機導論[M].李國正，王猛，曾華軍，譯.北京:電子工業出版社，2004.[10]UCI MLG.UCI common dataset[DB/OL].(2005-06-01)[2007-0216].http://mlearn.ics.uci.edu/MLRepository.html.

[11]張永，遲忠先，閆德勤.一種新的模糊補償多類支持向量[J].計算機科學，2006，33(12):152155.

[12]楊志民，田英杰，鄧乃揚.模糊支持向量分類機[J].計算機工程，2005，31(20):25-26.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”