王 霞，董永權(quán)，于 巧，耿 娜

1.江蘇師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116

2.江蘇師范大學(xué) 電氣工程及自動(dòng)化學(xué)院，江蘇 徐州 221116

1 引言

作為一種強(qiáng)有力的分類(lèi)和回歸方法，支持向量機(jī)（Support Vector Machine，SVM）已經(jīng)取得非常顯著的研究成果，并廣泛應(yīng)用于許多領(lǐng)域[1-7]。支持向量機(jī)基于統(tǒng)計(jì)學(xué)的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則[8]，通過(guò)軟間隔最大化獲得正類(lèi)和負(fù)類(lèi)間最優(yōu)劃分超平面。對(duì)于非線性情形，可以使用核技巧[9-11]，將低維空間的數(shù)據(jù)映射到高維空間，使用二次規(guī)劃（Quadratic Programming，QP[12]）技術(shù)完美解決原始問(wèn)題的對(duì)偶問(wèn)題，從而獲得劃分超平面。

然而，傳統(tǒng)支持向量機(jī)存在兩個(gè)顯著弱點(diǎn)，嚴(yán)重制約其發(fā)展。其一，在處理復(fù)雜結(jié)構(gòu)數(shù)據(jù)時(shí)，計(jì)算復(fù)雜度高、實(shí)現(xiàn)難度大。其二，劃分超平面不偏不倚，處于兩個(gè)類(lèi)的平行超平面的正中間，丟失了數(shù)據(jù)內(nèi)在的幾何結(jié)構(gòu)信息。針對(duì)上述弱點(diǎn)，許多學(xué)者提出諸多改進(jìn)方法。這些方法也相應(yīng)地分為兩類(lèi)：一類(lèi)是建立更為高效算法，諸如分解算法[13]、分塊算法[14]、序列最小化優(yōu)化算法[15]等；另一類(lèi)則將單個(gè)最優(yōu)超平面延伸為多個(gè)超平面（即非平行超平面），如此一來(lái)，各類(lèi)數(shù)據(jù)點(diǎn)就能靠近各自的超平面，而遠(yuǎn)離其他超平面，例如廣義支持向量機(jī)（Generalized Eigenvalue Proximal Support Vector Machine，GEPSVM[14]）、孿生支持向量機(jī)（Twin Support Vector Machine，TWSVM[16）]、雙邊界支持向量機(jī)（Twin Bounded Support Vector Machines，TBSVM[17]）、非平行支持向量機(jī)（Nonparallel Support Vector Machine，NPSVM[18]）等。

上述對(duì)SVM 的改進(jìn)方法，盡管從一定程度上改善了SVM 的性能；但是，這些方法都局限于分解數(shù)據(jù)本身，忽略了數(shù)據(jù)內(nèi)在的結(jié)構(gòu)緊密性。不僅導(dǎo)致算法的復(fù)雜度較高，而且非常容易產(chǎn)生噪聲數(shù)據(jù)處理上的失誤，嚴(yán)重影響分類(lèi)的準(zhǔn)確性。

鑒于此，學(xué)者們提出結(jié)構(gòu)化支持向量機(jī)（Structural Support Vector Machine，SSVM）。SSVM的分類(lèi)過(guò)程分為兩步：首先采用無(wú)監(jiān)督學(xué)習(xí)的聚類(lèi)方法，諸如KNN[19]、最鄰近聚類(lèi)[20]、模糊聚類(lèi)[21-22]、系統(tǒng)聚類(lèi)[23]等，提取數(shù)據(jù)樣本內(nèi)在的結(jié)構(gòu)化信息；然后，以協(xié)方差矩陣的形式，將結(jié)構(gòu)化信息嵌入到原始問(wèn)題的目標(biāo)函數(shù)或約束條件中，再對(duì)原始問(wèn)題進(jìn)行常規(guī)化訓(xùn)練。典型代表有：結(jié)構(gòu)化最大邊界機(jī)（Structured Large Margin Machine，SLMM[24]）、最小最大概率機(jī)（Minimax Probability Machine，MPM[25）]、最大最小邊界機(jī)（Maximin Margin Machine，M4[26]）、結(jié)構(gòu)正則化支持向量機(jī)（Structural Regularized Support Vector Machine，SRSVM[27-28]）、結(jié)構(gòu)化孿生支持向量機(jī)（Structural Twin Support Vector Machine，STWSVM[29-30）]、結(jié)構(gòu)化非平行支持向量機(jī)（Structural Nonparallel Support Vector Machine，SNPSVM[31-32]）等。

目前，針對(duì)SSVM 的理論研究成果已經(jīng)非常豐碩，并成功用于解決圖像識(shí)別、文字處理、控制管理等實(shí)際問(wèn)題?？梢?jiàn)，對(duì)SSVM進(jìn)行系統(tǒng)性的闡述和評(píng)價(jià)是非常必要的；需要說(shuō)明的是，盡管對(duì)非結(jié)構(gòu)化SVM 的綜述研究較多，例如安悅瑄[33]、Ding S[34-35]、Huang H 等[36]對(duì)TWSVM的綜述，Ding S等[37]對(duì)NPSVM的綜述；然而迄今為止，對(duì)于SSVM的綜述研究，仍非常少見(jiàn)。為此，本文分析各種SSVM模型，并對(duì)部分代表性成果進(jìn)行對(duì)比分析，從而揭示各種方法的優(yōu)缺點(diǎn)、改進(jìn)分析，從而為后續(xù)研究指明方向。

2 相關(guān)理論基礎(chǔ)

2.1 結(jié)構(gòu)粒度

定義1[23]對(duì)于給定的數(shù)據(jù)集，設(shè)S1,S2,…,St是根據(jù)某關(guān)系測(cè)度對(duì)數(shù)據(jù)集T的劃分，且S1?S2?…?St=T，那么，則稱(chēng)該劃分是以聚類(lèi)結(jié)構(gòu)表示的數(shù)據(jù)集，Si(i=1,2,…,t)為結(jié)構(gòu)粒度。

依據(jù)實(shí)際問(wèn)題對(duì)數(shù)據(jù)的處理需求，結(jié)構(gòu)粒度可以分為四類(lèi)：全局粒度，類(lèi)粒度，聚類(lèi)粒度和點(diǎn)粒度，如圖1所示。圖1中，“○”和“△”分別表示兩類(lèi)。

圖1 結(jié)構(gòu)粒度示意圖

2.2 結(jié)構(gòu)化支持向量機(jī)

其中，Σ=ΣP1+ΣP2+…+ΣPCP+ΣN1+ΣN2+…+ΣNCN，用分別表示正類(lèi)樣本和負(fù)類(lèi)樣本的聚類(lèi)協(xié)方差矩陣；c ＞0 為懲罰參數(shù)，一般由應(yīng)用問(wèn)題決定。c值大（小）時(shí)，對(duì)誤分類(lèi)的懲罰增大（減?。?；ξi≥0為松弛變量，主要用于解決某些樣本點(diǎn)不能滿足硬間隔要求；λ≥0 為聚類(lèi)內(nèi)結(jié)構(gòu)信息權(quán)重的正則項(xiàng)。

3 結(jié)構(gòu)化支持向量機(jī)的研究進(jìn)展

SVM 的優(yōu)點(diǎn)明顯，包括具有稀疏性、能用同一目標(biāo)函數(shù)處理線性和非線性問(wèn)題等；但是，SVM 只關(guān)注數(shù)據(jù)類(lèi)別本身，沒(méi)有挖掘數(shù)據(jù)內(nèi)在緊密性信息。結(jié)構(gòu)粒度恰好能夠反映實(shí)際分類(lèi)算法中需要考慮的數(shù)據(jù)內(nèi)在結(jié)構(gòu)信息，因此，結(jié)合類(lèi)間的離散性和類(lèi)內(nèi)的緊密性，從縱向（結(jié)構(gòu)粒度）和橫向（典型的支持向量機(jī)訓(xùn)練算法）討論結(jié)構(gòu)化支持向量機(jī)的現(xiàn)有研究成果，是十分必要的。接下來(lái)，縱橫結(jié)合，探討SSVM 的發(fā)展歷程和優(yōu)缺點(diǎn)。

3.1 結(jié)構(gòu)化支持向量機(jī)

3.1.1 全局粒度支持向量機(jī)

2007 年，Shivaswamy 等首次提出橢球形核機(jī)器（Ellipsoidal Kernel Machines，EKM[38]）模型。EKM 從全局粒度出發(fā)，基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，采用橢球有界容錯(cuò)分類(lèi)器來(lái)提高泛化能力。EKM不需要額外的領(lǐng)域知識(shí)、規(guī)范，在VC 維上尋找更緊密的邊界，以改進(jìn)SVM 的線性決策邊界；但僅僅按照全局粒度提取結(jié)構(gòu)化信息、粒度過(guò)粗、性能差。

3.1.2 類(lèi)粒度支持向量機(jī)

Lanckriet 等人用已知的均值和協(xié)方差矩陣，表示類(lèi)內(nèi)數(shù)據(jù)間的結(jié)構(gòu)化信息，并提出最大最小概率機(jī)（MPM[25]）。MPM能夠最小化最壞情況下未分類(lèi)數(shù)據(jù)錯(cuò)分的概率，為分類(lèi)的準(zhǔn)確率提供一個(gè)下邊界，同時(shí)通過(guò)控制錯(cuò)分率達(dá)到分類(lèi)最大化的目的。

針對(duì)SVM 只考慮局部數(shù)據(jù)和MPM 僅考慮全局?jǐn)?shù)據(jù)的不足，Huang等人提出了最大最小邊界機(jī)（M4[26]），綜合分析局部和全局?jǐn)?shù)據(jù)，構(gòu)建SVM 和MPM 的統(tǒng)一框架，結(jié)合二者的優(yōu)點(diǎn)解釋和擴(kuò)展線性判別分析。

鑒于MPM 和M4都無(wú)法處理不平衡數(shù)據(jù)的問(wèn)題，Huang 等提出偏置最小最大概率機(jī)（Biased MPM，BMPM[39-40]），和最小錯(cuò)誤最小最大概率機(jī)（Minimum Error MPM，MEMPM[41-42]）。與 MPM 相比，MEMPM 取消了對(duì)兩個(gè)類(lèi)最壞精度的等式約束，在最壞情況下最小化測(cè)試數(shù)據(jù)的貝葉斯分類(lèi)錯(cuò)誤率，從而實(shí)現(xiàn)了最壞情況下的最優(yōu)分類(lèi)器。

針對(duì)既有模型不能預(yù)先對(duì)數(shù)據(jù)作出有效預(yù)測(cè)，Yoshiyama 等提出流形正則最小最大概率機(jī)（Manifold-Regularized MPM，MRMPM[43]）。MRMPM 在目標(biāo)函數(shù)中增加流形正則項(xiàng)，以提取數(shù)據(jù)樣本內(nèi)在的幾何信息，從而提高分類(lèi)的準(zhǔn)確性。

結(jié)合半監(jiān)督學(xué)習(xí)技術(shù)，Yoshiyama 等提出了拉普拉斯最大最小概率機(jī)（Laplacian MPM，Lap-MPM[44]）。Lap-MPM以圖正則[45]平方根的形式，顯式地修正MPM的異常。

MPM、BMPM和MEMPM在訓(xùn)練數(shù)據(jù)時(shí)，對(duì)非標(biāo)記樣本關(guān)注不夠。為此，王曉初等提出基于數(shù)據(jù)分布一致性最小最大概率機(jī)（MPM with Concensus Regularization between Data Distributions，DCMPM[46]）。通過(guò)最小化有標(biāo)簽樣本和無(wú)標(biāo)簽樣本在決策超平面所在空間概率分布差距，充分利用無(wú)標(biāo)簽樣本來(lái)修正最小最大概率機(jī)的誤差。

為修正MPM 和MEMPM 中存在的過(guò)擬合現(xiàn)象，提高泛化性能，Maldonado 等人提出正則化最小最大概率分類(lèi)器（Regularized MPM，RMPM[47]）。在求解時(shí)，將權(quán)重向量的L2范數(shù)與錯(cuò)誤率合并最小化，采用非線性SOCP技術(shù)獲取劃分超平面。

表1列出上述幾種模型優(yōu)缺點(diǎn)的對(duì)比。

3.1.3 聚類(lèi)粒度支持向量機(jī)

這是研究結(jié)構(gòu)化支持向量機(jī)比較成功的一類(lèi)，其代表是SLMM和SSVM。

表1 類(lèi)粒度支持向量機(jī)優(yōu)缺點(diǎn)對(duì)比

2007年，Yeung等提出結(jié)構(gòu)化最大邊界機(jī)（SLMM[24，48）]。SLMM將數(shù)據(jù)結(jié)構(gòu)量化分為兩步：（1）通過(guò)Ward凝聚法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類(lèi)；（2）計(jì)算各聚類(lèi)的協(xié)方差矩陣，進(jìn)一步進(jìn)行距離測(cè)量。盡管SLMM 的分類(lèi)效果較好，但是，計(jì)算復(fù)雜度高，通常需要使用SOCP 求解最優(yōu)化問(wèn)題，實(shí)現(xiàn)難度大。

針對(duì)上述問(wèn)題，Xue等提出結(jié)構(gòu)化支持向量（SSVM[27）]。將結(jié)構(gòu)化信息與標(biāo)準(zhǔn)支持向量機(jī)訓(xùn)練過(guò)程結(jié)合，以協(xié)方差矩陣的形式將結(jié)構(gòu)化信息添加到標(biāo)準(zhǔn)支持向量機(jī)的目標(biāo)函數(shù)中，然后再按照SVM方法求解目標(biāo)函數(shù)，獲得分類(lèi)超平面。SSVM 將數(shù)據(jù)樣本類(lèi)內(nèi)的緊密性和類(lèi)間的離散性結(jié)合考慮，所以無(wú)論從泛化處理能力還是實(shí)際運(yùn)行效率，都高于標(biāo)準(zhǔn)SVM；同時(shí)，從本質(zhì)上解決了SLMM的計(jì)算復(fù)雜度高的問(wèn)題。后續(xù)的有關(guān)結(jié)構(gòu)化支持向量機(jī)的研究，基本上都是SSVM模型為基礎(chǔ)發(fā)展和完善的。

盡管SSVM 優(yōu)勢(shì)明顯，但是，存在過(guò)擬合現(xiàn)象。為此，Xue 等提出結(jié)構(gòu)化正則支持向量機(jī)（SRSVM[28]）。SRSVM 首次提出“結(jié)構(gòu)粒度”的概念，同時(shí)利用聚類(lèi)技術(shù)提取樣本數(shù)據(jù)內(nèi)在的結(jié)構(gòu)信息，并應(yīng)用于SVM 的學(xué)習(xí)過(guò)程，使用QP技術(shù)和對(duì)偶原則求解。SRSVM不僅降低了計(jì)算的復(fù)雜度，而且提高了分類(lèi)的準(zhǔn)確率。

表2列出上述幾種模型優(yōu)缺點(diǎn)的對(duì)比。

3.1.4 點(diǎn)粒度支持向量機(jī)

2006 年，Belkin M 等提出拉普拉斯支持向量機(jī)（Laplacian SVM，LapSVM[49]）。LapSVM是一種基于流形正則項(xiàng)的半監(jiān)督分類(lèi)算法，主要研究利用少量的有標(biāo)識(shí)的樣本和大量的未標(biāo)識(shí)樣本進(jìn)行訓(xùn)練和分類(lèi)。

表2 聚類(lèi)粒度支持向量機(jī)優(yōu)缺點(diǎn)

從理論上講，LapSVM中引入了包含樣本的固有幾何結(jié)構(gòu)信息的樣本流形正則項(xiàng)，分類(lèi)結(jié)果更準(zhǔn)確。但在實(shí)際問(wèn)題解決過(guò)程中，LapSVM算法涉及許多矩陣運(yùn)算和轉(zhuǎn)換，時(shí)空復(fù)雜度較高。近年來(lái)，為提高LapSVM 算法的運(yùn)行速度和分類(lèi)準(zhǔn)確性，學(xué)者們提出許多新的算法。

Lee S 等提出改進(jìn)的LapSVM（Structural Laplacian SVM，SLapSVM[50]）。這是一種基于方差分解原則的SLapSVM，通過(guò)對(duì)分量引入額外的懲罰因子，產(chǎn)生稀疏矩陣，從而有效提高半監(jiān)督學(xué)習(xí)結(jié)果分類(lèi)器的可解釋性。

為了進(jìn)一步提高LapSVM 性能，Melacci S 等提出加速拉普拉斯支持向量機(jī)（Laplacian SVM Trained in the Primal，PLapSVM[51]），該方法包含兩種加快計(jì)算性能的算法：PLapSVM-Newton和PLapSVM-PCG，分別采用牛頓迭代法和預(yù)處理共軛條件法（Preconditioned Conjugate Gradient，PCG[52]）獲取最優(yōu)解，計(jì)算復(fù)雜度降低。

針對(duì)PLapSVM在無(wú)法直接處理大規(guī)模數(shù)據(jù)問(wèn)題的不足，Qi等提出快速拉普拉斯支持向量機(jī)（Fast Laplacian SVM，F(xiàn)LapSVM[53]）。FLapSVM 無(wú)需處理矩陣或與變量相關(guān)的計(jì)算，因此，更適用于大規(guī)模問(wèn)題的求解，且計(jì)算性能比LapSVM 更好；使用相同的對(duì)偶問(wèn)題處理線性和非線性問(wèn)題，泛化性能好；同時(shí)采用逐次超松弛（Successive Overrelaxation，SOR[54）]技術(shù)獲取問(wèn)題最優(yōu)解。

LapSVM在求解優(yōu)化問(wèn)題時(shí)，只考慮問(wèn)題本身性質(zhì)，而忽略問(wèn)題規(guī)模，從而失去稀疏性。為此，Yang等提出一種有效的基于LapSVM安全篩選規(guī)則（Safe Screening Rule for LapSVM，SSR-LapSVM[55]）。SSR-LapSVM 是一種不丟失最優(yōu)解的快速LapSVM 算法。通過(guò)對(duì)KKT條件和對(duì)偶問(wèn)題可行集的分析構(gòu)造，得出解析規(guī)則。利用解析規(guī)則進(jìn)行篩選，在求解QP問(wèn)題之前，獲取最優(yōu)解的某些分量，大大減少訓(xùn)練樣本的數(shù)量，從而提高優(yōu)化效率和速度。

表3列出上述幾種模型優(yōu)缺點(diǎn)的對(duì)比。

表3 點(diǎn)粒度支持向量機(jī)優(yōu)缺點(diǎn)總結(jié)

3.2 結(jié)構(gòu)化孿生支持向量機(jī)

研究發(fā)現(xiàn)，全局粒度、類(lèi)別粒度過(guò)于粗糙，不利于提高分類(lèi)的性能；點(diǎn)粒度過(guò)于精細(xì)，顯著增加計(jì)算的復(fù)雜度，因此，近年來(lái)對(duì)結(jié)構(gòu)粒度的研究，多集中于聚類(lèi)粒度的層次。

結(jié)構(gòu)化孿生支持向量機(jī)（STWSVM[30）]是在TWSVM基礎(chǔ)上，加入結(jié)構(gòu)化信息發(fā)展而來(lái)的。STWSVM 結(jié)合結(jié)構(gòu)粒度和標(biāo)準(zhǔn)支持向量機(jī)的思想，在構(gòu)造TWSVM時(shí)，先利用聚類(lèi)技術(shù)挖掘類(lèi)內(nèi)結(jié)構(gòu)信息，再將數(shù)據(jù)分布信息引入TWSVM模型，從而構(gòu)造出更合理的分類(lèi)器。

鑒于TWSVM 的非平行超平面不能刻畫(huà)數(shù)據(jù)的分布特征，而且計(jì)算復(fù)雜度高的不足，Peng等提出結(jié)構(gòu)雙參數(shù)邊緣支持向量機(jī)[29（]Structural with Parametric-Margin SVM，STPMSVM）。STPMSVM 在標(biāo)準(zhǔn)雙參數(shù)邊緣支持向量機(jī)（Twin Parametric-Margin SVM，TPMSVM[56）]基礎(chǔ)上，用馬氏距離取代歐氏距離，分別考慮兩類(lèi)數(shù)據(jù)中聚類(lèi)的協(xié)方差矩陣。這種策略可以充分利用不同類(lèi)型數(shù)據(jù)中的信息，從而達(dá)到更好的泛化性能。

針對(duì)傳統(tǒng)TWSVM只關(guān)注類(lèi)間數(shù)據(jù)離散性的弊端，Wang Z 等提出孿生支持向量機(jī)聚類(lèi)（TSVM for Clustering，TWSVC[57]）。通過(guò)求解一系列二次規(guī)劃問(wèn)題，確定了k個(gè)聚類(lèi)中心平面。并且提出了一種高效、穩(wěn)定的基于神經(jīng)網(wǎng)絡(luò)的初始化方法。

針對(duì)STWSVM 計(jì)算復(fù)雜度高的不足，Pan X 等提出基于KNN 的孿生支持向量機(jī)（K-Nearest Neighbor based STWSVM，KNN-STSVM[58]）。先使用 KNN 聚類(lèi)技術(shù)提取樣本數(shù)據(jù)內(nèi)在結(jié)構(gòu)信息，并且根據(jù)樣本密度給予不同聚類(lèi)相應(yīng)的權(quán)重，同時(shí)分別使用兩個(gè)最鄰近圖Ws和Wd（類(lèi)內(nèi)和類(lèi)間）來(lái)計(jì)算樣本權(quán)重來(lái)提取相應(yīng)的結(jié)構(gòu)信息；再使用類(lèi)似TSVM 的方式來(lái)訓(xùn)練數(shù)據(jù)，從而獲取兩個(gè)劃分超平面。KNN-STSVM 具有分類(lèi)準(zhǔn)確率高、計(jì)算復(fù)雜度低等優(yōu)點(diǎn)。

使用凝聚層次聚類(lèi)方法的結(jié)構(gòu)化支持向量機(jī)（如SRSVM、STSVM 和KNN-STSVM）在提取結(jié)構(gòu)化幾何信息時(shí)，只考慮類(lèi)內(nèi)局部結(jié)構(gòu)，不考慮類(lèi)間局部結(jié)構(gòu)。為此，Chu M 等提出局部結(jié)構(gòu)信息的孿生支持向量機(jī)（TWSVM with Local Structural Information，LSITSVM[59]）。LSI-TSVM 嵌入了數(shù)據(jù)在類(lèi)內(nèi)和類(lèi)間的局部分布信息，不僅包含了原始的類(lèi)內(nèi)全局聚類(lèi)和類(lèi)間邊緣，而且包含了類(lèi)內(nèi)和類(lèi)間的局部散點(diǎn)。

針對(duì)STWSVM 無(wú)法直接進(jìn)行多分類(lèi)處理的問(wèn)題，Hanifelou Z等提出基于KNN的多標(biāo)簽優(yōu)先級(jí)的TWSVM（KNN-based Multi-Label Twin Support Vector Machine with Priority of Labels，PKNN-MLTSVM[60]）。首先使用K鄰近圖獲取數(shù)據(jù)的局部幾何信息，再利用聚類(lèi)技術(shù)提取樣本的內(nèi)在結(jié)構(gòu)信息，最后結(jié)合結(jié)構(gòu)信息和幾何信息獲取劃分超平面。

KNN-STSVM存在過(guò)擬合的缺點(diǎn)，為此，Xie F等提出正則KNN結(jié)構(gòu)化孿生支持向量機(jī)（Regularized KNNSTSVM，RKNN-STSVM[61]）。通過(guò)在目標(biāo)函數(shù)中增加正則項(xiàng)來(lái)提高算法的泛化能力，從而避免過(guò)擬合，提高計(jì)算性能。

針對(duì)STWSVM 不能直接處理不平衡數(shù)據(jù)的不足，Mohammadi F S 等提出結(jié)構(gòu)化加權(quán)松弛孿生支持向量機(jī)（Twin Structural Weighted Relaxed SVM，TSWRSVM[62]）。TS-WRSVM利用兩個(gè)非平行超平面來(lái)訓(xùn)練數(shù)據(jù)，使得每個(gè)模型只考慮本類(lèi)的結(jié)構(gòu)信息，并且根據(jù)每個(gè)類(lèi)的大小，為每個(gè)模型分配一個(gè)權(quán)重和有限的無(wú)懲罰的松弛變量。TS-WRSVM可以降低異常值和噪聲對(duì)訓(xùn)練邊界的影響，提高分類(lèi)器在處理不平衡分類(lèi)問(wèn)題時(shí)的性能；具有較低的計(jì)算復(fù)雜度、較高分類(lèi)準(zhǔn)確度和泛化能力。

表4列出上述幾種模型優(yōu)缺點(diǎn)的對(duì)比。

3.3 結(jié)構(gòu)化非平行支持向量機(jī)

鑒于TWSVM在求解目標(biāo)函數(shù)時(shí)，其算法整體性能低下，同時(shí)無(wú)法直接將線性問(wèn)題擴(kuò)展為非線性問(wèn)題。為此，Tian 提出非平行支持向量機(jī)NPSVM，NPSVM 不僅沒(méi)有矩陣逆運(yùn)算，而且線性問(wèn)題與非線性問(wèn)題的原始問(wèn)題是統(tǒng)一的。但是，由于NPSVM僅考慮類(lèi)間數(shù)據(jù)的離散性，沒(méi)有考慮類(lèi)內(nèi)數(shù)據(jù)的緊密性，從而分類(lèi)準(zhǔn)確率低。

為此，Chen等將結(jié)構(gòu)化信息同非平行支持向量機(jī)結(jié)合，提出結(jié)構(gòu)化非平行支持向量機(jī)（SNPSVM[31]），以提高分類(lèi)器的準(zhǔn)確性和泛化能力。他們還將改進(jìn)型交替方向乘子法（Alternating Direction Multiplier Method，ADMM[63]）引入SNPSVM，從而提高了模型的訓(xùn)練效率。SNPSVM 的訓(xùn)練過(guò)程分為三步：（1）采用聚類(lèi)挖掘數(shù)據(jù)結(jié)構(gòu)信息；（2）通過(guò)學(xué)習(xí)獲取劃分超平面；（3）采用ADMN優(yōu)化算法性能。

然而，SNPSVM 無(wú)法直接處理大規(guī)模數(shù)據(jù)，針對(duì)這一問(wèn)題，Chen 基于LSH 提出結(jié)構(gòu)化非平行支持向量機(jī)（SNPSVM based on LSH，LSH-SNPSVM[64]）。LSHSNPSVM 在對(duì)分類(lèi)器進(jìn)行訓(xùn)練前，通過(guò)有效的哈希函數(shù)，過(guò)濾多余空間。此外，采用ADMM 對(duì)SNPSVM 進(jìn)行了有效求解。

針對(duì)非并行分類(lèi)器忽略了不同樣本間的判別信息的不足，Hou Q等提出基于判別信息的非平行支持向量機(jī)（Discriminative Information-based NPSVM，DINPSVM[65）]。對(duì)每個(gè)超平面分別構(gòu)造類(lèi)間子圖Gs和類(lèi)內(nèi)子圖Gd，提取數(shù)據(jù)內(nèi)在的空間幾何信息，再將從Gs和Gd得到的兩個(gè)相應(yīng)的權(quán)矩陣Ws和Wd分別賦給類(lèi)內(nèi)判別正則項(xiàng)和類(lèi)間判別正則項(xiàng)，并添加到目標(biāo)函數(shù)中進(jìn)行訓(xùn)練。此外，為降低計(jì)算復(fù)雜度和空間存儲(chǔ)，在類(lèi)間正則化項(xiàng)中只保留潛在支持向量樣本，從而提高NPSVM的執(zhí)行效率和有效性。

表5列出上述幾種模型優(yōu)缺點(diǎn)的對(duì)比。

表4 結(jié)構(gòu)化孿生支持向量機(jī)優(yōu)缺點(diǎn)對(duì)比

表5 結(jié)構(gòu)化非平行支持向量機(jī)優(yōu)缺點(diǎn)總結(jié)

4 各種結(jié)構(gòu)化支持向量機(jī)實(shí)驗(yàn)比較

為了對(duì)比分析各種結(jié)構(gòu)化支持向量機(jī)的性能，驗(yàn)證其優(yōu)點(diǎn)，進(jìn)一步尋找算法改進(jìn)的方向。結(jié)合前面論述，從聚類(lèi)層次結(jié)合結(jié)構(gòu)化支持向量機(jī)的發(fā)展歷程，選取三組比較有代表性的SVM-SRSVM、TWSVM-STWSVM、NPSVM-SNPSVM 進(jìn)行對(duì)比實(shí)驗(yàn)；并選用自制數(shù)據(jù)（100×2）和UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中八個(gè)常用的數(shù)據(jù)集（見(jiàn)表6），以測(cè)試上述算法。為了保證實(shí)驗(yàn)的可靠性，將80%的數(shù)據(jù)樣本作為訓(xùn)練數(shù)據(jù)，20%的數(shù)據(jù)樣本作為測(cè)試數(shù)據(jù)，對(duì)訓(xùn)練數(shù)據(jù)，參數(shù)c和λ從{2-10,2-9,…,29,210}范圍采用十字交叉驗(yàn)證法選擇最優(yōu)值；同時(shí)使用無(wú)監(jiān)督聚類(lèi)學(xué)習(xí)方式，先對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行聚類(lèi)，聚類(lèi)數(shù)目依據(jù)肘部法則[66]自動(dòng)選??；接下來(lái)用選取的最優(yōu)值對(duì)測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，評(píng)價(jià)算法的分類(lèi)準(zhǔn)確率。實(shí)驗(yàn)基于Matlab R2016b進(jìn)行，硬件配置為8 GB內(nèi)存，Intel?Core? i5處理器和3.30 GHz 主頻。表7、表8 分別列出三組模型在八個(gè)數(shù)據(jù)集中的分類(lèi)準(zhǔn)確率和運(yùn)行時(shí)間。圖2～4 分別為SVM與SRSVM、TWSVM與STWSVM和NPSVM與SNPSVM 在自制數(shù)據(jù)集上運(yùn)行結(jié)果對(duì)比圖。圖5（a）～（f）為三種模型分類(lèi)準(zhǔn)確率和運(yùn)行時(shí)間對(duì)比圖。

表6 UCI數(shù)據(jù)集的信息

從圖2 可以看出，SRSVM 與SVM 所獲取的支持向量機(jī)個(gè)數(shù)基本相等，前者分類(lèi)準(zhǔn)確率較高，運(yùn)行時(shí)間短。即使在SRSVM訓(xùn)練數(shù)據(jù)前要對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)提取結(jié)構(gòu)化信息，并以協(xié)方差的形式嵌入到目標(biāo)函數(shù)中進(jìn)行訓(xùn)練，理論上增長(zhǎng)運(yùn)行時(shí)間，但所需時(shí)間比求解優(yōu)化問(wèn)題所需要的時(shí)間要短得多，所以整體運(yùn)行時(shí)間較短。

表7 三組模型的分類(lèi)準(zhǔn)確率比較（運(yùn)行十次的平均值）%

表8 三組模型的運(yùn)行時(shí)間比較（運(yùn)行十次的平均值）s

圖2 SVM與SRSVM運(yùn)行結(jié)果對(duì)比圖

圖3 TWSVM與STWSVM運(yùn)行結(jié)果對(duì)比圖

從圖3可以看出，TWSVM與STWSVM都生成一對(duì)平行超平面；由于后者首先使用聚類(lèi)技術(shù)提取結(jié)構(gòu)化信息，消除了多余支持向量機(jī)對(duì)分類(lèi)結(jié)果的影響，只保留潛在且合理的支持向量，故STWSVM 支持向量機(jī)數(shù)目減少，但是分類(lèi)準(zhǔn)確率提高。雖然在STWSVM 中也要在目標(biāo)函數(shù)中嵌入表示結(jié)構(gòu)化信息的協(xié)方差矩陣，但是由于TWSVM本身的優(yōu)勢(shì)，故運(yùn)行時(shí)間也沒(méi)有增加。

圖4 NPSVM與SNPSVM運(yùn)行結(jié)果對(duì)比圖

圖5 三種模型分類(lèi)準(zhǔn)確率和運(yùn)行時(shí)間對(duì)比圖

從圖4 可以看出，NPSVM 與 SNPSVM 都生成一對(duì)非平行超平面；由于后者首先使用聚類(lèi)技術(shù)提取結(jié)構(gòu)化信息，不僅減少了支持向量機(jī)數(shù)目，而且分類(lèi)超平面更加貼合數(shù)據(jù)集本身的幾何表示，分類(lèi)準(zhǔn)確率高。

從圖2～圖4還可以發(fā)現(xiàn)，結(jié)構(gòu)化比非結(jié)構(gòu)化的準(zhǔn)確率高，運(yùn)行時(shí)間有高有低，且結(jié)構(gòu)化非平行支持向量機(jī)的分類(lèi)準(zhǔn)率最高，這也成功驗(yàn)證了學(xué)者對(duì)支持向量機(jī)的研究方向和成果。

圖5（a）～（c）分別為三種模型（SVM 與 SRSVM、TWSVM 和STWSVM、NPSVM 與SNPSVM）分類(lèi)準(zhǔn)確率的折線對(duì)比圖，藍(lán)色實(shí)線表示相應(yīng)的結(jié)構(gòu)化支持向量機(jī)的分類(lèi)準(zhǔn)確率，紅色虛線表示的是非結(jié)構(gòu)化支持向量機(jī)的分類(lèi)準(zhǔn)確率。（d）～（f）分別為三種模型運(yùn)行時(shí)間折線圖，藍(lán)色實(shí)線表示相應(yīng)的結(jié)構(gòu)化支持向量機(jī)的運(yùn)行時(shí)間，紅色虛線表示的是非結(jié)構(gòu)化支持向量機(jī)的運(yùn)行時(shí)間。

非常直觀，非結(jié)構(gòu)化支持向量機(jī)表現(xiàn)相對(duì)穩(wěn)定，結(jié)構(gòu)化支持向量機(jī)結(jié)果存在不穩(wěn)定現(xiàn)象，原因在于數(shù)據(jù)集的特征數(shù)和類(lèi)別數(shù)目不同，特征數(shù)越多，提取的結(jié)構(gòu)化信息越不完備，分類(lèi)結(jié)果就不甚理想。所以說(shuō)，現(xiàn)有的結(jié)構(gòu)化支持向量機(jī)不太適合處理多特征大規(guī)模問(wèn)題。

5 總結(jié)和展望

本文深入討論了結(jié)構(gòu)化支持向量機(jī)，并對(duì)近年來(lái)多種類(lèi)型的支持向量機(jī)結(jié)構(gòu)化研究成果進(jìn)行分析和比較。結(jié)構(gòu)化支持向量機(jī)是采用無(wú)監(jiān)督聚類(lèi)，獲取樣本數(shù)據(jù)內(nèi)在的幾何結(jié)構(gòu)信息，通常以協(xié)方差或均值的形式，嵌入到支持向量原始問(wèn)題的目標(biāo)函數(shù)或約束條件中進(jìn)行訓(xùn)練，從而將類(lèi)內(nèi)的結(jié)構(gòu)性和類(lèi)間的離散性結(jié)合考慮，大大提高了分類(lèi)器的準(zhǔn)確性，并增加了算法的泛化性能。近年來(lái)，人們針對(duì)結(jié)構(gòu)粒度、參數(shù)選擇、優(yōu)化方法等多方面提出許多結(jié)構(gòu)化模型；在聚類(lèi)方法的選擇上，大多集中于使用系統(tǒng)聚類(lèi)、肘部法則進(jìn)行聚粒度選擇。在實(shí)際應(yīng)用中，結(jié)構(gòu)化支持向量機(jī)仍需要在以下方面進(jìn)行改進(jìn)：

（1）更加有效的智能算法提取結(jié)構(gòu)化信息，提高模型的計(jì)算效率，從而使分類(lèi)器具有更好的性能。

（2）結(jié)構(gòu)化支持向量機(jī)雖然已被運(yùn)用于多標(biāo)簽分類(lèi)中，但仍存在準(zhǔn)確度較低、計(jì)算復(fù)雜度高等缺點(diǎn)。

（3）結(jié)構(gòu)化支持向量機(jī)應(yīng)用于大數(shù)據(jù)也面臨許多挑戰(zhàn)。

（4）標(biāo)準(zhǔn)支持向量機(jī)的應(yīng)用比較廣泛，但是結(jié)構(gòu)化支持向量機(jī)的應(yīng)用不多，如何將結(jié)構(gòu)化支持向量機(jī)應(yīng)用解決實(shí)際問(wèn)題，是今后研究的方向。