陳素根 吳小俊

?

基于特征值分解的中心支持向量機(jī)算法

陳素根①②吳小俊*①

①(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院 無錫 214122)②(安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 安慶 246133)

針對(duì)廣義特征值中心支持向量機(jī)(GEPSVM)訓(xùn)練和決策過程不一致問題，該文提出一類改進(jìn)的基于特征值分解的中心支持向量機(jī)，簡稱為IGEPSVM。首先針對(duì)二分類問題提出了基于特征值分解的中心支持向量機(jī)，然后基于“一類對(duì)余類”策略將其推廣到多類分類問題。將GEPSVM求解廣義特征值問題轉(zhuǎn)化為求解標(biāo)準(zhǔn)特征值問題，降低了計(jì)算復(fù)雜度。引入了一個(gè)新的參數(shù)，可以調(diào)節(jié)模型的性能，提高了GEPSVM的分類精度。提出了基于IGEPSVM的多類分類算法。實(shí)驗(yàn)結(jié)果表明，與GEPSVM算法相比較，IGEPSVM不僅提高了分類精度，而且縮短了訓(xùn)練時(shí)間。

支持向量機(jī)；廣義特征值中心支持向量機(jī)；兩類分類；多類分類；特征值分解

1 引言

支持向量機(jī)(SVM)算法是經(jīng)典的分類算法[1]，鑒于其堅(jiān)實(shí)的理論基礎(chǔ)和良好的泛化性能而被廣泛使用于各個(gè)領(lǐng)域中[2,3]。SVM在解決小樣本、非線性和高維模式問題中表現(xiàn)出了許多特有的優(yōu)勢(shì)，標(biāo)準(zhǔn)的SVM算法問題可歸結(jié)為求解一個(gè)受約束的二次規(guī)劃(QP)問題，對(duì)于小規(guī)模的QP問題，它表現(xiàn)出了非常優(yōu)秀的學(xué)習(xí)能力，但當(dāng)訓(xùn)練集樣本規(guī)模巨大時(shí)，就會(huì)出現(xiàn)訓(xùn)練速度慢、算法復(fù)雜和效率低下等問題。為了解決這些問題，一方面，許多學(xué)者對(duì)SVM求解算法進(jìn)行了廣泛研究，并取得了很多優(yōu)秀成果，如Chunking算法[4]、分解算法[5]、SMO算法[6]和FD- SVM[7]等；另一方面，新型的SVM算法被大量研究，其中非平行平面支持向量機(jī)算法是代表性成果之一。關(guān)于非平行平面支持向量機(jī)算法的研究開始于2006年，文獻(xiàn)[8]提出了廣義特征值中心支持向量機(jī)算法(GEPSVM)來處理兩類分類問題，考慮了最大化類間距離和最小化類內(nèi)距離，對(duì)每一類樣本訓(xùn)練一個(gè)分類超平面，開辟了新的決策思路。2007年，文獻(xiàn)[9]在GEPSVM算法的基礎(chǔ)上提出了孿生支持向量機(jī)算法(TWSVM)，與GEPSVM求解兩個(gè)規(guī)模較小的廣義特征值問題有所不同，TWSVM求解兩個(gè)規(guī)模較小的QP問題，訓(xùn)練速度相當(dāng)于傳統(tǒng)SVM的1/4。然而，許多實(shí)際問題都可歸結(jié)為多類分類問題，傳統(tǒng)SVM的多類分類算法大致分為“分解重構(gòu)法”和“整體法”兩大類，代表性研究成果有：“一類對(duì)余類”[17]、“一類對(duì)一類”[18]和C&S (Crammer and Singer)方法[19]等。近年來，非平行平面支持向量機(jī)多類分類算法也開始受到很多學(xué)者的關(guān)注，涌現(xiàn)了一些優(yōu)秀成果[20,21]。

GEPSVM算法是最早被提出的非平行平面支持向量機(jī)算法，雖然它開辟了新的決策思路，但它依然有一些不足之處。首先，GEPSVM在訓(xùn)練過程和決策過程中出現(xiàn)了不一致性，即：在訓(xùn)練過程中，是通過比較每一個(gè)超平面和兩類訓(xùn)練樣本之間的距離來尋求每一類的最優(yōu)超平面的；在決策過程中，是通過比較測(cè)試樣本和兩個(gè)超平面的距離來實(shí)現(xiàn)分類的。因此，這一種不一致性，在一定程度上可能會(huì)影響GEPSVM的性能。其次，GEPSVM算法是通過求解兩個(gè)廣義特征值問題來實(shí)現(xiàn)的，但求解廣義特征值問題的算法復(fù)雜度是，從而可能會(huì)影響模型的訓(xùn)練速度。最后，GEPSVM算法本身是針對(duì)兩類分類問題提出的，不能直接處理多類分類問題。針對(duì)以上問題，本文首先針對(duì)兩類分類問題提出一類改進(jìn)的基于特征分解的中心支持向量機(jī)算法(Improved GEPSVM, IGEPSVM)；然后在IGEPSVM的基礎(chǔ)上進(jìn)一步研究多類分類問題，提出多類分類IGEPSVM算法。與GEPSVM算法相比較，IGEPSVM有如下優(yōu)點(diǎn)：(1)將求解廣義特征值問題轉(zhuǎn)化為求解標(biāo)準(zhǔn)特征值問題，降低了算法的復(fù)雜度；(2)引入一個(gè)新的參數(shù)，可以更好地調(diào)節(jié)模型的性能，提高了GEPSVM算法的分類精度。最后，在標(biāo)準(zhǔn)的UCI分類數(shù)據(jù)集上驗(yàn)證了本文算法的有效性。

2 廣義特征值中心支持向量機(jī)(GEPSVM)

對(duì)于兩類分類問題，給定訓(xùn)練樣本集：

顯然，問題式(4)的目標(biāo)函數(shù)是Rayleigh商。故，優(yōu)化問題式(4)的最優(yōu)解就是廣義特征值問題：

3 基于特征值分解的中心支持向量機(jī)(IGEPSVM)

仔細(xì)分析GEPSVM算法，我們不難發(fā)現(xiàn)，GEPSVM算法在訓(xùn)練過程和決策過程具有一定的不一致性，這可能會(huì)影響GEPSVM算法的性能。為此，我們提出一種改進(jìn)的基于特征值分解的中心支持向量機(jī)算法。

3.1 兩類分類IGEPSVM

首先考慮線性情形，對(duì)于訓(xùn)練樣本集式(1)，我們考察優(yōu)化模型[13]：

顯然，直接觀察式(7)是比較難以理解的。然而，式(7)有很好的幾何解釋。假設(shè)IGEPSVM尋求的兩個(gè)非平行超平面也為式(2)，那么在空間中訓(xùn)練樣本點(diǎn)到超平面的距離為

這樣，結(jié)合式(8)，我們分別定義正類和負(fù)類訓(xùn)練樣本點(diǎn)到正類和負(fù)類兩個(gè)超平面的4個(gè)距離：

于是，優(yōu)化模型式(7)轉(zhuǎn)化為

通過構(gòu)造Lagrange函數(shù)并結(jié)合KKT條件，求解模型式(12)可以轉(zhuǎn)化為求解標(biāo)準(zhǔn)特征值問題式(13)：

因此，優(yōu)化問題式(12)的第1部分可表示為

由Rayleigh定理[22]可知，當(dāng)且僅當(dāng)是矩陣最小特征值時(shí)，優(yōu)化問題式(12)的第1部分的目標(biāo)函數(shù)取得全局極小值。此時(shí)，最小特征值對(duì)應(yīng)的單位特征向量是優(yōu)化問題式(12)的第1部分的最優(yōu)解。同理可證，優(yōu)化問題式(12)的第2部分的最優(yōu)解是矩陣的最小特征值所對(duì)應(yīng)的單位特征向量。 證畢于是，當(dāng)被求出后，對(duì)于新的測(cè)試樣本，它將根據(jù)式(16)，被分類到正類或負(fù)類。即

類似地，我們也可以分別定義正類和負(fù)類訓(xùn)練樣本點(diǎn)到正類和負(fù)類兩個(gè)非線性超曲面的4個(gè)距離：

于是，建立非線性情形的優(yōu)化模型為

類似于線性情形，求解模型式(18)可以轉(zhuǎn)化為求解模型式(19)：

通過構(gòu)造Lagrange函數(shù)并結(jié)合KKT條件，求解模型式(19)可以轉(zhuǎn)化為求解標(biāo)準(zhǔn)特征值問題式(20)：

類似于線性情形，關(guān)于非線性模型，我們可以得定理2。

定理2的證明過程類似于定理1，簡單起見，此處省略。于是，當(dāng)被求出后，對(duì)于新的測(cè)試樣本，它將根據(jù)式(21)，被分類到正類或負(fù)類。即：

總結(jié)上述過程，可以得到兩類分類IGEPSVM算法如下：

算法1 兩類分類IGEPSVM算法

步驟1 給定訓(xùn)練集式(1)；

步驟3 利用模型式(12)或式(19)訓(xùn)練，求解特征值問題式(13)或式(20)得到最小特征值對(duì)應(yīng)的單位特征向量；

步驟4 利用決策函數(shù)式(16)或式(21)進(jìn)行分類。

3.2 多類分類IGEPSVM

這樣，對(duì)于線性多類分類問題，基于線性IGEPSVM就可以構(gòu)造個(gè)相互不平行的超平面：

并構(gòu)造決策函數(shù)如下：

的最小特征值對(duì)應(yīng)的單位特征向量。

對(duì)于非線性多類分類問題，基于非線性IGEPSVM可以構(gòu)造個(gè)超曲面：

并構(gòu)造決策函數(shù)：

的最小特征值對(duì)應(yīng)的單位特征向量。

總結(jié)上述過程，可以得到多類分類IGEPSVM算法如下：

算法2 多類分類IGEPSVM算法

(2)利用模型式(24)或式(28)訓(xùn)練，求解特征值問題式(25)或式(29)得到最小特征值對(duì)應(yīng)的單位特征向量；

End

步驟3 利用決策函數(shù)式(23)或式(27)進(jìn)行分類。

3.3 計(jì)算復(fù)雜度分析

綜上可知，對(duì)于兩類分類問題，線性IGEPSVM僅需要求解兩個(gè)標(biāo)準(zhǔn)的特征值問題，其計(jì)算復(fù)雜度為，其中為訓(xùn)練樣本點(diǎn)的特征維數(shù)，而線性GEPSVM則需要求解兩個(gè)廣義特征值問題，其計(jì)算復(fù)雜度為。對(duì)于非線性情形，我們的非線性IGEPSVM的計(jì)算復(fù)雜度為，其中為訓(xùn)練樣本點(diǎn)的規(guī)模，而非線性GEPSVM的計(jì)算復(fù)雜度為。對(duì)于類多分類問題，IGEPSVM算法無論對(duì)線性還是非線性都需要求解個(gè)特征值問題，它們的計(jì)算復(fù)雜度分別為和。因此，由理論分析可知，IGEPSVM訓(xùn)練速度要比GEPSVM快。

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

為了驗(yàn)證IGEPSVM算法的有效性，分別在8個(gè)兩類分類和6個(gè)多類分類UCI數(shù)據(jù)集上[23]進(jìn)行實(shí)驗(yàn)，并分別與傳統(tǒng)SVM, GEPSVM和TWSVM方法進(jìn)行對(duì)比。所有實(shí)驗(yàn)均以Matlab R2013a為實(shí)驗(yàn)環(huán)境，以Intel P4(3.40 GHz)處理器、4 GB內(nèi)存的PC為硬件平臺(tái)。在實(shí)驗(yàn)過程中，使用LIBSVM工具包[24]實(shí)現(xiàn)傳統(tǒng)SVM，使用逐次超松弛技術(shù)(SOR)[10]來求解TWSVM中的QPP問題，使用Matlab的“eig”函數(shù)求解GEPSVM和IGEPSVM分別對(duì)應(yīng)的廣義特征值問題和標(biāo)準(zhǔn)特征值問題。對(duì)于非線性情形，選擇RBF核為核函數(shù)，其中為核參數(shù)。參數(shù)選擇對(duì)于各算法性能有一定的影響，因此，對(duì)于不同的數(shù)據(jù)集，使用10-折交叉驗(yàn)證方法為算法選擇最優(yōu)參數(shù)，所有算法中的參數(shù)選取范圍均為。

針對(duì)兩類分類問題，我們選擇了8個(gè)UCI數(shù)據(jù)集來驗(yàn)證本文算法的有效性，表1和表2分別給出了4種算法在線性和非線性情形下的10-折交叉驗(yàn)證結(jié)果和訓(xùn)練時(shí)間。針對(duì)多類分類問題，我們選擇了6個(gè)UCI數(shù)據(jù)集來驗(yàn)證本文算法的有效性，表3和表4分別給出了4種算法在線性和非線性情形下的10-折交叉驗(yàn)證結(jié)果和訓(xùn)練時(shí)間。在表1至表4中，為了更好地體現(xiàn)算法的優(yōu)越性，用黑體數(shù)字代表特定數(shù)據(jù)集下獲得的最高分類精度。同時(shí)，我們?cè)诒淼牡箶?shù)第2行給出了所有算法的平均分類精度和訓(xùn)練時(shí)間，并在表的最后一行用“W-T-L”(win-tie-loss)概括了IGEPSVM算法與其它算法的性能。

對(duì)于兩類分類問題，從表1和表2中可以發(fā)現(xiàn)，從分類精度來說，IGEPSVM算法比GEPSVM和傳統(tǒng)的SVM表現(xiàn)出了更好的性能，同時(shí)也獲得了與TWSVM算法非常類似的性能；但從訓(xùn)練時(shí)間上來說，本文算法表現(xiàn)出了更好的優(yōu)勢(shì)，雖然在非線性情形下SVM也有較好的結(jié)果，那可能是因?yàn)長IBSVM工具包實(shí)現(xiàn)SVM利用了SMO算法的原因。容易看出，本文方法IGEPSVM在絕大多數(shù)的數(shù)據(jù)集上訓(xùn)練時(shí)間相對(duì)較少，尤其與GEPSVM方法相比較，訓(xùn)練時(shí)間明顯減少，進(jìn)一步驗(yàn)證了本文方法是對(duì)GEPSVM方法的一種有效改進(jìn)。

對(duì)于多類分類問題而言，觀察表3和表4不難發(fā)現(xiàn)，一方面，無論在分類精度還是訓(xùn)練時(shí)間，本文IGEPSVM算法比GEPSVM算法都有所提高。另一方面，本文IGEPSVM算法與SVM和TWSVM相比較，從表3和表4的最后兩行看出，本文方法在分類精度上要稍微低一點(diǎn)，但也取得了較好的效果；然而，本文方法在訓(xùn)練時(shí)間上總體上是有一定

表1 線性IGEPSVM與幾種算法在兩類分類UCI數(shù)據(jù)集上性能比較

數(shù)據(jù)集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

Australian(690×14)

86.52±3.21, 3.8563e-04

85.80±4.67, 5.1659e-04

85.51±3.86, 0.0185

86.10±4.55, 0.0381

House votes(435×16)

94.26±2.68, 2.6548e-04

94.03±2.88, 4.4901e-04

94.73±3.77, 0.0033

95.87±3.21, 0.0063

Heart-c(303×14)

84.87±5.85, 2.2177e-04

84.49±7.40, 5.4313e-04

84.83±5.41, 0.0029

85.13±5.07, 0.0277

Heart-Statlog(270×13)

84.70±4.68, 2.2044e-04

84.59±8.20, 3.5033e-04

84.44±4.88, 0.0023

84.81±4.77, 0.0333

Monk3(432×7)

83.47±5.66, 1.3137e-04

80.76±7.00, 2.2355e-04

82.59±6.03, 0.0027

85.91±3.96, 0.0464

Sonar(208×60)

81.98±7.96, 0.0032

79.31±5.59, 0.0052

81.69±6.88, 0.0035

81.93±7.28, 0.0371

Spect(267×44)

80.51±5.78, 0.0016

79.46±7.54, 0.0025

80.45±7.46, 0.0030

80.24±6.21, 0.0691

Wpbc(198×34)

80.32±2.26, 0.0010

78.18±6.88, 0.0015

80.14±6.90, 0.0022

79.89±5.23, 0.0431

平均精度/平均時(shí)間

84.58/0.0009

83.33/0.0014

84.30/0.0048

84.99/0.0376

W-T-L(勝-平-負(fù))

8-0-0

7-0-1

4-0-4

表2 非線性IGEPSVM與幾種算法在兩類分類UCI數(shù)據(jù)集上性能比較

數(shù)據(jù)集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

Australian(690×14)

86.67±5.19, 0.7215

86.10±2.51, 5.2741

86.23±4.70, 0.5162

86.96±4.27, 0.7381

House votes(435×16)

95.42±2.85, 0.1356

94.12±5.05, 0.8937

95.24±4.07, 0.1112

96.32±2.49, 0.1641

Heart-c(303×14)

84.86±5.20, 0.0810

82.52±7.49, 0.2952

83.19±8.27, 0.0652

85.13±2.47, 0.0834

Heart-Statlog(270×13)

84.07±4.64, 0.0165

83.33±7.25, 0.2023

83.59±7.21, 0.0140

84.81±7.08, 0.0184

Monk3(432×7)

98.72±4.80, 0.2135

95.84±3.29, 0.8769

97.25±3.18, 0.1045

98.26±1.32, 0.2450

Sonar(208×60)

87.24±6.33, 0.0153

86.55±8.08, 0.1533

86.10±8.51, 0.0257

89.26±7.19, 0.0289

Spect(267×44)

82.71±8.96, 0.0675

80.48±8.09, 0.3178

82.46±8.54, 0.0549

82.07±5.91, 0.0709

Wpbc(198×34)

82.76±6.33, 0.0353

81.26±8.24, 0.1137

82.56±5.38, 0.0534

82.74±5.23, 0.0504

平均精度/平均時(shí)間

87.81/0.1608

86.28/1.0159

87.08/0.1181

88.19/0.1749

W-T-L(勝-平-負(fù))

8-0-0

8-0-0

3-0-5

表3 線性IGEPSVM與幾種算法在多類分類UCI數(shù)據(jù)集上性能比較

數(shù)據(jù)集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

Iris(150×4×3)

96.67±5.67, 0.0012

95.33±4.66, 0.0028

95.33±4.50, 0.0034

96.53±5.84, 0.0209

Wine(178×13×3)

96.76±5.17, 0.0017

94.71±7.92, 0.0042

97.78±3.88, 0.0028

98.33±2.68, 0.0669

Seeds(210×7×3)

93.71±1.23, 0.0015

89.05±5.96, 0.0018

92.86±5.14, 0.0027

95.71±4.74, 0.0474

Dermatology(358×34×6)

95.03±6.79, 0.0080

94.14±4.97, 0.0099

95.83±3.00, 0.0121

95.25±2.63, 0.2177

Balance(625×4×3)

88.48±3.77, 0.0017

89.69±3.72, 0.0020

87.52±3.54, 0.0031

87.66±3.18, 0.2026

Car(1278×6×4)

77.78±2.85, 0.0045

73.59±2.84, 0.0068

84.78±4.13, 0.0329

77.26±4.27, 2.1232

平均精度/平均時(shí)間

91.41/0.0031

89.42/0.0046

92.35/0.0095

91.79/0.4465

W-T-L(勝-平-負(fù))

5-0-1

3-0-3

3-0-3

表4 非線性IGEPSVM與幾種算法在多類分類UCI數(shù)據(jù)集上性能比較

數(shù)據(jù)集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

精度±方差(%)時(shí)間(s)

Iris(150×4×3)

97.33±3.51, 0.0100

96.67±4.71, 0.0399

96.67±3.51, 0.0121

97.33±3.44, 0.0162

Wine(178×13×3)

97.78±2.87, 0.0444

95.49±5.20, 0.0766

98.30±2.74, 0.0463

99.44±1.76, 0.1237

Seeds(210×7×3)

94.33±6.02, 0.0546

92.38±7.17, 0.1377

93.86±4.63, 0.0510

96.67±3.21, 0.1508

Dermatology(358×34×6)

96.23±4.22, 0.3165

96.39±2.64, 1.0836

96.01±5.19, 0.2205

96.65±4.11, 0.6842

Balance(625×4×3)

94.25±2.26, 0.5918

96.65±2.74, 3.7493

93.97±4.11, 0.3067

99.20±1.13, 1.2449

Car(1278×6×4)

96.20±1.47, 3.8730

94.04±1.07, 18.4988

98.67±1.22, 0.8437

98.44±0.67, 7.8442

平均精度/平均時(shí)間

96.02/0.8150

95.27/3.9310

96.25/0.2467

97.96/1.6773

W-T-L(勝-平-負(fù))

4-0-2

4-0-2

0-1-5

優(yōu)勢(shì)的，只有在與非線性SVM比較時(shí)稍微差一些，主要原因可能是SVM采取了LIBSVM工具包和“一類對(duì)一類”的策略實(shí)現(xiàn)多類分類。總而言之，本文IGEPSVM算法是對(duì)GEPSVM算法的一種改進(jìn)，無論在分類精度還是在訓(xùn)練時(shí)間上都取得了比GEPSVM較好的實(shí)驗(yàn)效果。

5 結(jié)束語

本文針對(duì)兩類分類問題提出了一類改進(jìn)的基于特征值分解的中心支持向量機(jī)算法(IGEPSVM)，并將其推廣到多類分類問題。與GEPSVM算法相比較，本文的主要貢獻(xiàn)在于：首先，解決了GEPSVM模型訓(xùn)練過程和決策過程不一致的問題；其次，將GEPSVM求解廣義特征值問題轉(zhuǎn)化為求解標(biāo)準(zhǔn)的特征值問題，降低了計(jì)算復(fù)雜度；最后，通過引入新的參數(shù)，可以方便調(diào)節(jié)IGEPSVM模型的性能，提高了分類精度。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法比GEPSVM算法更優(yōu)越，但與SVM或TWSVM算法相比較，它們各有優(yōu)勢(shì)。近幾年來，非平行平面支持向量機(jī)已經(jīng)逐漸成為模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域新的研究熱點(diǎn)之一，將已有的針對(duì)兩類分類問題所提出的非平行平面支持向量機(jī)算法推廣到多類分類問題以及在不同領(lǐng)域的應(yīng)用是今后研究的重點(diǎn)。

[1] CORTES C and VAPNIK V N. Support vector machine[J]., 1995, 20(3): 273-297.

[2] OSUNA E, FREUND R, and GIROSI F. Training support vector machines: an application to face detection[C]. Proceedings of Computer Vision and Pattern Recognition, San Juan, 1997: 130-136.

[3] ISA D, LEE L H, KALLIMANI V P,. Text document preprocessing with the Bayes formula for classification using the support vector machine[J]., 2008, 20(9): 1264-1272.

[4] BOSER B, GUYON I, and VAPNIK V N. A training algorithm for optimal margin classifiers[C]. Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, New York, 1992: 144-152.

[5] OSUNA E, FREUND R, and GIROSI F. An improved training algorithm for support vector machines[C]. Proceedings of IEEE Workshop on Neural Networks for Signal Processing, New York, USA, 1997: 276-285.

[6] PLATT J. Fast Training of Support Vector Machines Using Sequential Minimal Optimization[M]. Advances in Kernel Methods: Support Vector Machines, Cambridge, MA, MIT Press, 1998: 41-65.

[7] 張戰(zhàn)成, 王士同, 鄧趙紅, 等. 支持向量機(jī)的一種快速分類算法[J]. 電子與信息學(xué)報(bào), 2011, 33(9): 2181-2186.

ZHANG Zhancheng, WANG Shitong, DENG Zhaohong,. Fast decision using SVM for incoming samples[J].&, 2011, 33(9): 2181-2186.

[8] MANGASARIAN O L and WILD E W. Multisurface proximal support vector machine classification via generalized eigenvalues[J]., 2006, 28(1): 69-74.

[9] JAYADEVA, KHEMCHANDAI R, and CHANDRA S. Twin support vector machine classification for pattern classification [J]., 2007, 29(5): 905-910.

[10] SHAO Y H, ZHANG C H, WANGX B,. Improvements on twin support vector machines[J]., 2011, 22(6): 962-968.

[11] PENG X J. TPMSVM: A novel twin parametric-margin support vector machine for pattern recognition[J]., 2011, 44(10): 2678-2692.

[12] QI Z Q, TIAN Y J, and SHI Y. Robust twin support vector machine for pattern classification[J]., 2013, 46(1): 305-316.

[13] SHAO Y H, DENG N Y, and CHEN W J. A proximal classifier with consistency[J]., 2013, 49: 171-178.

[14] Tian Y J, Qi Z Q, Ju X C,. Nonparallel support vector machines for pattern classification[J]., 2014, 44(7): 1067-1079.

[15] DING S F, HUA X P, and YU J Z. An overview on nonparallel hyperplane support vector machine algorithms[J]., 2014, 25(5): 975-982.

WANG Na and LI Xia. A new dualsupport vector machine based on class-weighted[J].&, 2007, 29(4): 859-862.

[17] BOTTOU L, CORTES C, DENKER J S,. Comparison of classifier methods: a case study in handwritten digit recognition[C]. Proceedings of IEEE International Conference on Pattern Recognition, Paris, 1994: 77-82.

[18] KRE?EL U. Pairwise Classification and Support Vector Machines[M]. Advances in Kernel Methods-Support Vector Learning, Cambridge, MA, MIT Press, 1999: 255-268.

[19] CRAMMER K and SINGER Y. On the learn ability and design of output codes for multi-class problems[J]., 2002, 47(2/3): 201-233.

[20] XU Y T, GUO R, and WANG L S. A twin multi-class classification support vector machine[J]., 2013, 5(4): 580-588.

[21] NASIRI J A, CHARKARI N M, and JALILI S. Least squares twin multi-class classification support vector machine[J]., 2015, 48(3): 984-992.

[22] PARLETT B. The Symmetric Eigenvalue Problem[M]. Upper Saddle River, NJ, USA, SIAM Press, 1998: 61-80.

[23] BLAKE C L and MERZ C J. UCI repository of machine learning databases[R]. Irvine, CA: Department of Information and Computers Science, University of California, 1998.

[24] CHANG C and LIN C. LIBSVM: A library for support vector machine[J]., 2011, 2(3): 1-27.

陳素根： 男，1982年生，副教授，博士生，研究方向?yàn)槟Ｊ阶R(shí)別與智能系統(tǒng).

吳小?。?男，1967年生，教授，博士生導(dǎo)師，研究方向?yàn)槟Ｊ阶R(shí)別、人工智能與計(jì)算機(jī)視覺.

Foundation Items: The National Natural Science Foundation of China (61373055, 61103128), 111 Project of Chinese Ministry of Education (B12018), Industrial Support Program of Jiangsu Province (BE2012031)

Eigenvalue Proximal Support Vector Machine Algorithm Based on Eigenvalue Decoposition

CHEN Sugen①②WU Xiaojun①

①(School of IoT Engineering, Jiangnan University, Wuxi 214122, China)②(School of Mathematics & Computational Science, Anqing Normal University, Anqing 246133, China)

To deal with the consistency problem of training process and decision process in Generalized Eigenvalue Proximal Support Vector Machine (GEPSVM), an improved version of eigenvalue proximal support vector machine, called IGEPSVM for short is proposed. At first, IGEPSVM for binary classification problem is proposed, and then Multi-IGEPSVM is also presented for multi-class classification problem based on “one-versus-rest” strategy. The main contributions of this paper are as follows. The generalized eigenvalue decomposition problems are replaced by the standard eigenvalue decomposition problems, leading to simpler optimization problems. An extra parameter is introduced, which can adjust the performance of the model and improve the classification accuracy of GEPSVM. A corresponding multi-class classification algorithm is proposed, which is not studied in GEPSVM. Experimental results on several datasets illustrate that IGEPSVM is superior to GEPSVM in both classification accuracy and training speed.

Support Vector Machine (SVM); Generalized Eigenvalue Proximal SVM (GEPSVM); Binary classification; Multi-class classification; Eigenvalue decoposition

TP391

A

1009-5896(2016)03-0557-08

10.11999/JEIT150693

2015-06-08；改回日期：2015-09-17；網(wǎng)絡(luò)出版：2015-11-19

吳小俊 wu_xiaojun@jiangnan.edu.cn

國家自然科學(xué)基金(61373055, 61103128), 111引智計(jì)劃項(xiàng)目(B12018)，江蘇省工業(yè)支持計(jì)劃項(xiàng)目(BE2012031)