結(jié)構(gòu)化支持向量機(jī)研究綜述

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

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

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

1 引言

作為一種強(qiáng)有力的分類和回歸方法，支持向量機(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]，通過軟間隔最大化獲得正類和負(fù)類間最優(yōu)劃分超平面。對于非線性情形，可以使用核技巧[9-11]，將低維空間的數(shù)據(jù)映射到高維空間，使用二次規(guī)劃（Quadratic Programming，QP[12]）技術(shù)完美解決原始問題的對偶問題，從而獲得劃分超平面。

然而，傳統(tǒng)支持向量機(jī)存在兩個顯著弱點(diǎn)，嚴(yán)重制約其發(fā)展。其一，在處理復(fù)雜結(jié)構(gòu)數(shù)據(jù)時，計(jì)算復(fù)雜度高、實(shí)現(xiàn)難度大。其二，劃分超平面不偏不倚，處于兩個類的平行超平面的正中間，丟失了數(shù)據(jù)內(nèi)在的幾何結(jié)構(gòu)信息。針對上述弱點(diǎn)，許多學(xué)者提出諸多改進(jìn)方法。這些方法也相應(yīng)地分為兩類：一類是建立更為高效算法，諸如分解算法[13]、分塊算法[14]、序列最小化優(yōu)化算法[15]等；另一類則將單個最優(yōu)超平面延伸為多個超平面（即非平行超平面），如此一來，各類數(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]）等。

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

鑒于此，學(xué)者們提出結(jié)構(gòu)化支持向量機(jī)（Structural Support Vector Machine，SSVM）。SSVM的分類過程分為兩步：首先采用無監(jiān)督學(xué)習(xí)的聚類方法，諸如KNN[19]、最鄰近聚類[20]、模糊聚類[21-22]、系統(tǒng)聚類[23]等，提取數(shù)據(jù)樣本內(nèi)在的結(jié)構(gòu)化信息；然后，以協(xié)方差矩陣的形式，將結(jié)構(gòu)化信息嵌入到原始問題的目標(biāo)函數(shù)或約束條件中，再對原始問題進(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]）等。

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

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

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

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

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

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

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

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

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

SVM 的優(yōu)點(diǎn)明顯，包括具有稀疏性、能用同一目標(biāo)函數(shù)處理線性和非線性問題等；但是，SVM 只關(guān)注數(shù)據(jù)類別本身，沒有挖掘數(shù)據(jù)內(nèi)在緊密性信息。結(jié)構(gòu)粒度恰好能夠反映實(shí)際分類算法中需要考慮的數(shù)據(jù)內(nèi)在結(jié)構(gòu)信息，因此，結(jié)合類間的離散性和類內(nèi)的緊密性，從縱向（結(jié)構(gòu)粒度）和橫向（典型的支持向量機(jī)訓(xùn)練算法）討論結(jié)構(gòu)化支持向量機(jī)的現(xiàn)有研究成果，是十分必要的。接下來，縱橫結(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)最小化原則，采用橢球有界容錯分類器來提高泛化能力。EKM不需要額外的領(lǐng)域知識、規(guī)范，在VC 維上尋找更緊密的邊界，以改進(jìn)SVM 的線性決策邊界；但僅僅按照全局粒度提取結(jié)構(gòu)化信息、粒度過粗、性能差。

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

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

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

針對既有模型不能預(yù)先對數(shù)據(jù)作出有效預(yù)測，Yoshiyama 等提出流形正則最小最大概率機(jī)（Manifold-Regularized MPM，MRMPM[43]）。MRMPM 在目標(biāo)函數(shù)中增加流形正則項(xiàng)，以提取數(shù)據(jù)樣本內(nè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ù)時，對非標(biāo)記樣本關(guān)注不夠。為此，王曉初等提出基于數(shù)據(jù)分布一致性最小最大概率機(jī)（MPM with Concensus Regularization between Data Distributions，DCMPM[46]）。通過最小化有標(biāo)簽樣本和無標(biāo)簽樣本在決策超平面所在空間概率分布差距，充分利用無標(biāo)簽樣本來修正最小最大概率機(jī)的誤差。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了進(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ù)雜度降低。

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

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

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

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

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

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

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

鑒于TWSVM 的非平行超平面不能刻畫數(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ǔ)上，用馬氏距離取代歐氏距離，分別考慮兩類數(shù)據(jù)中聚類的協(xié)方差矩陣。這種策略可以充分利用不同類型數(shù)據(jù)中的信息，從而達(dá)到更好的泛化性能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 三種模型分類準(zhǔn)確率和運(yùn)行時間對比圖

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

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

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

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

5 總結(jié)和展望

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

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

（2）結(jié)構(gòu)化支持向量機(jī)雖然已被運(yùn)用于多標(biāo)簽分類中，但仍存在準(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í)際問題，是今后研究的方向。