呂卓，謝松云，趙金，趙海濤

（1.西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安710129；2.第四軍醫(yī)大學(xué)第一附屬醫(yī)院放射科，陜西西安710032）

支持向量機的優(yōu)點是在處理小樣本學(xué)習(xí)問題上具有獨到的優(yōu)越性[1]，與人工神經(jīng)網(wǎng)絡(luò)相比，支持向量機避免了“維數(shù)災(zāi)難”。然而，SVM研究的過程中，對于大規(guī)模問題，當(dāng)樣本數(shù)很大時[2]，一般的二次規(guī)劃求解方法已不再適用，除了對大規(guī)模數(shù)據(jù)進行有效的預(yù)處理外，許多學(xué)者對算法本身進行了改進，從而加快了訓(xùn)練速度，減少了對內(nèi)存的需求，同時提高了分類精度和泛化能力。fMRI技術(shù)能實時跟蹤信號的改變，例如在僅幾秒鐘內(nèi)發(fā)生的思維活動，或認(rèn)知實驗中信號的變化，時間分辨率達到1 s。fMRI具有非常好的空間分辨率和時間分辨率。這些特性為對人腦進行多種新穎的認(rèn)知神經(jīng)科學(xué)的實驗提供了有利條件，并可進行腦病理的研究，具有相當(dāng)大的臨床意義。

1 支持向量機（SVM）基本算法

1.1 簡單兩類線性可分分類問題

給定訓(xùn)練樣本集（x，y），y=1或-1兩類假設(shè)分類面H的方程為wx+b=0。如果y=1，則wx+b＞0，否則wx+b＜0任意樣分類面就是尋找最大的D以及相關(guān)的權(quán)系數(shù)向量w和偏置b，這一問題可以描述為以下的優(yōu)化問題為如下的拉格朗日函數(shù)：

求拉格朗日函數(shù)關(guān)于w和b的最小值和關(guān)于α的最大值問題。α的最大值問題的Wolfe對偶形式：

而且最優(yōu)解必須滿足Karush-Kuhn-Tucher（KKT）條件。

1.2 復(fù)雜兩類線性不可分分類問題

對于復(fù)雜兩類線性不可分問題，首先通過一非線性映射φ將輸入空間映射到高維特征空間F：x→φ（x）=（φ1（x），φ2（x），…φn（x）…），原空間中的對偶優(yōu)化問題變?yōu)椋?/p>

拉格朗日乘子法求得的最優(yōu)分類判別函數(shù)為：

式中，對于高維空間的運算，靠的是內(nèi)積運算來實現(xiàn)：

式中內(nèi)積函數(shù)K（xi，x）為核函數(shù)，且必須滿足Mercer條件。

2 支持向量機（SVM）改進算法

2.1 SSVM（Smooth SVM）[4-5]

標(biāo)準(zhǔn)的SVM是一個凸二次規(guī)劃問題，求解復(fù)雜，可以通過一定的變形技巧，使其轉(zhuǎn)化為光滑的無約束問題，再利用經(jīng)典的最優(yōu)化方法求解。取（n+1）維空間中的間距為去掉約束條件γ≥0。其最優(yōu)化問題變?yōu)椋?/p>

利用光滑技術(shù)，得到變形后光滑的無約束最優(yōu)化問題：

2.2 PSVM（Proximal SVM）[5]

將SVM中不等式約束變成等式約束，邊界超平面變成最鄰近超平面，兩類點在兩超平面附近聚類，同時整合了松弛因子的作用，最后求解。改進后的分類優(yōu)化問題為：

2.3 LPSVM（Linear programming SVM）[6]

2.4 NSVM（Newton SVM）[7]

將最優(yōu)性條件用于原問題解的對偶問題，得對偶變量u的迭代公式，再得到隱式的Lagrangian無約束最小問題，最后用有窮Newton方法求解該無約束最小問題Qu/2-eu得到變量u的迭代公式：ui+1=Q-1（e+（（Qui-e）-αui）+）i=1，2…0 p α p 2/v得到隱式Lagrangian無約束最小問題：

最后用有窮Newton方法解該問題。

3 基于SVM的fMRI圖像分類方法及性能比較

本實驗所用數(shù)據(jù)來自西安市第四軍醫(yī)大學(xué)西京醫(yī)院核磁共振室，選取右利手的健康人為受試者進行腦功能核磁共振圖像的測試。

實驗選取fMRI部分?jǐn)?shù)據(jù)：選取靠近中心的6層圖像數(shù)據(jù)，分前后兩組測試，每組3層數(shù)據(jù)，60幅圖像，所測得的部分原始圖像如圖1所示。分類矩陣中，以每幅fMRI圖像作為

圖1 功能核磁共振fMRI圖像Fig.1 fMRI images

分類矩陣中，以每幅fMRI圖像作為行向量，送入分類器后，隨機打亂樣本順序，前50%數(shù)樣本據(jù)為訓(xùn)練樣本，其余為檢驗樣本。

3.1 分類時間比較

由于SVM分類時間179.53 s，與其他分類算法運行時間相差多個數(shù)量級，所以比較時間時不加入SVM運行時間的比較。如圖2所示。

原始SVM算法計算方式主要是將原問題最終轉(zhuǎn)化為一個二次凸規(guī)劃優(yōu)化問題來解。本實驗所用的數(shù)據(jù)是fMRI圖像，每一幅圖像由128×128個像素點組成，分類器所用分類矩陣為120維，訓(xùn)練集的規(guī)模比較大，支持向量很多。這樣解二次凸規(guī)劃優(yōu)化問題時，即解下式：

圖2 運行時間比較圖（單位/s）Fig.2 Runtime comparison（s）

計算代價比較大，支持向量機的學(xué)習(xí)過程需要占用大量的內(nèi)存，尋優(yōu)速度非常緩慢。原始SVM算法運行時間問題的主要癥結(jié)在于求解二次凸規(guī)劃優(yōu)化問題計算代價太大。

PSVM算法：由于PSVM算法將SVM中不等式約束變成等式約束，邊界超平面變成最鄰近超平面，兩類點在兩超平面附近聚類。相對于原始算法，求解問題變成下式：

不再是計算復(fù)雜的二次凸規(guī)劃優(yōu)化問題，而只需求解一組線性等式。所以PSVM運算速度極快，實驗數(shù)據(jù)120維的計算代價相比較原始SVM算法小得多。

NSVM算法：分析發(fā)現(xiàn)，NSVM算法對于計算速度的提升方式與PSVM相同，但思路不同。PSVM直接對二次凸規(guī)劃優(yōu)化問題進行改進，而NSVM算法從SVM算法的最優(yōu)解所必須滿足的條件——KKT條件出發(fā)，尋求出了另一種巧妙的逆向思路。需要求解的：

所得到的最優(yōu)解必須滿足Karush-Kuhn-Tucher（KKT）條件。

找到KKT條件的必要充分最優(yōu)條件，得對偶變量u的迭代公式，也就是解的循環(huán)公式。同時得到隱式的Lagrangian無約束最小問題，并用有窮Newton方法求解該問題，且能在很少的次數(shù)內(nèi)達到全局最優(yōu)解。

同樣的，NSVM也并不是直接求解對偶問題，避免了計算代價過大，速度得到了極大的提升。

SSVM算法：與PSVM、NSVM類似，SSVM算法也將二次凸規(guī)劃問題回避，但是使用的方式、思路都不同。SSVM的計算方式是通過一定的變形技巧，利用光滑技術(shù)，將求解二次凸規(guī)劃問題中的不等式約束問題，轉(zhuǎn)化為光滑的等式約束問題：

這個轉(zhuǎn)化后光滑的等式約束問題可以用快速Newton-Armijo算法求解，這是一種成熟的光滑算法。同時，這種算法能保證全局收斂到唯一解，速度較快，但比PSVM、NSVM略慢。

LPSVM算法：與以上改進算法不同，LPSVM算法沒有在解二次凸規(guī)劃優(yōu)化問題上尋求改進，而是引入一種處理輸入空間特征的方法求解。這種方法的思路是：首先處理輸入空間中的數(shù)據(jù)集，將對支持向量沒有做貢獻的輸入特征進行篩除。

由原始SVM算法的原理可知，最優(yōu)分類平面的確定只取決于支持向量（SV），如果輸入的訓(xùn)練集中，較多特征對確定特征沒有貢獻，將會擾亂訓(xùn)練過程，拖延學(xué)習(xí)時間，最終使尋優(yōu)時間過長。LPSVM即是采用一種選擇性抑制輸入空間特征的快速牛頓算法，用于SVM分類器的線性規(guī)劃方程，使尋優(yōu)時間縮短，同時也從另一種意義上降低了求解二次凸規(guī)劃優(yōu)化問題的復(fù)雜度。對于改善分類速度有顯著的功效。

3.2 分類精確度比較

5種分類算法的分類精度均不高，僅50～60%。如圖3所示。

對于SVM算法，訓(xùn)練集的樣本點不能過多或者過少，需要包括求解問題的不同狀態(tài)和反映求解問題的重要特征。輸入中所含的特征應(yīng)該只與求解問題有關(guān)，無關(guān)的輸入會干擾支持向量（SV）的選取，即噪聲干擾。各種SVM算法對噪聲干擾十分敏感。

圖3 原始數(shù)據(jù)分類精度比較圖（單位/正識率）Fig.3 Comparison of data classification accuracy upon the original data（percents）

因為本次實驗的數(shù)據(jù)是未經(jīng)過預(yù)處理的醫(yī)學(xué)圖像fMRI圖像，在fMRI圖像采集過程中，各種形式的運動都是引起信號波動的噪聲源，例如受試者頭部在實驗過程中未完全固定而發(fā)生的的剛體運動、心跳和呼吸周期引起頭部的節(jié)律性運動等。這些噪聲的特點是低頻或?qū)拵Х秶?，干擾了SVM及其改進算法算法找到最佳的決策函數(shù)，從而降低了總體的分類精確度。

以上方法對于原始采集的fMRI圖像數(shù)據(jù)分類精度均太低，在工程應(yīng)用中達不到應(yīng)用要求，使得對比分類精度失去意義。因此，引入PCA（Principal Components Analysis主成分分析）算法對原始采集數(shù)據(jù)進行預(yù)處理。計算主成分的目的是將高維數(shù)據(jù)投影到較低維空間，進行特征提取的同時剔除了無關(guān)或關(guān)系較少的成分。在SVM及其改進算法進行分類時，偽支持向量（Pseudo Support Vector）減少，提高了總體的分類精度，如圖4所示。

圖4 預(yù)處理數(shù)據(jù)分類精度比較圖（單位/正識率）Fig.4 Comparison of data classification accuracy upon the preprocessed data（percents）

3.2.1 算 法誤差分析

PSVM的改進思路是針對于分類平面的，將最優(yōu)分類平面用最鄰近分類平面代替，作了一定程度上的近似，但對于分類，近似的影響幾乎可忽略。LPSVM算法是首先處理輸入空間中的數(shù)據(jù)集，將對選取支持向量貢獻小的輸入特征數(shù)據(jù)進行篩除，也就是對訓(xùn)練樣本進行帶閾值的分類，這樣就進一步，本實驗數(shù)據(jù)量比較大，閾值以下的訓(xùn)練樣本對支持向量的選擇也有貢獻，篩除了它們后，算法選取的支持向量的準(zhǔn)確度就受到影響。支持向量選取的準(zhǔn)確度直接影響著算法的分類精確度，所以PSVM、LPSVM算法均作了不同程度的近似，分類精確度下降了。NSVM所用的有窮Newton方法、SSVM進行了光滑近似，保留了函數(shù)的嚴(yán)格凸和可微屬性，采用用的快速Newton-Armijo算法都在解優(yōu)化問題時進行一定得近似，出現(xiàn)一定的誤差，也導(dǎo)致了最后分類精度的下降。

3.2.2 各 改進SVM算法適用范圍影響分析

PSVM算法代碼簡單，能處理大規(guī)模問題（幾千個點），分類精度與SVM相當(dāng)，但所需時間急劇減少。PSVM算法的主要優(yōu)勢在于分類速度的極大提高。

NSVM方法采用窮Newton方法求解該無約束最小問題，在很少的次數(shù)內(nèi)達到全局最優(yōu)解；LPSVM將輸入空間進行了有選擇的抑制，也可以看做是進行了預(yù)處理特征提取，它們兩種算法主要優(yōu)勢都在于可以處理極高維數(shù)的數(shù)據(jù)集。

SSVM算法采用光滑技術(shù)進行近似時，保留了函數(shù)的嚴(yán)格凸和可微屬性，應(yīng)用光滑技術(shù)的重要目的是使SSVM算法可以推廣到用完全任意核解決非線性分類問題。

4 結(jié)論

本實驗采用的是fMRI圖像，這4種改進算法在不同方面存在優(yōu)缺點，所以它們在本實驗中的表現(xiàn)必然會存在差異，我們也可以通過這次實驗，尋求到相對適合fMRI圖像分類的算法，即在分類精度與計算速度上都體現(xiàn)出優(yōu)越性的改進算法：PSVM算法。

[1]唐發(fā)明.基于統(tǒng)計學(xué)習(xí)理論的支持向量機算法研究[D].武漢：華中科技大學(xué)，2005.

[2]謝松云，張海軍，趙海濤，等.基于SVM的腦功能分類與識別方法研究[J].中國醫(yī)學(xué)影像技術(shù)，2007（1）：125-128.

XIE Song-yun，ZHANG Hai-jun，ZHAO Hai-tao，et al.Classification and recognition of brain function based on support vector machine[J].China Medical Imaging Technology，2007（1）：125-128.

[3]XIE Song-yun，GUO Rong，LI Ning-fei，et al.Brain fMRI processing and classification based on combination of PCA and SVM[J].IJCNN’09，2009:3384-3389.

[4]熊金志，胡金蓮，袁華強.光滑支持向量機的原理和進展[J].計算機工程，2008，34（13）:172.

XIONG Jin-zhi，HU Jin-lian，YUAN Hua-qiang.Principles and advances of smooth support vector machine[J].Computer Engineering.2008，34（13）：172.

[5]Jye L Y，Mangasarian O L.SSVM:a smooth support vector machine for Classification[J].Computational Optimization and Application，2001，20（1）:5-22.

[6]XIE Song-yun，WANG Peng-wei，ZHANG Hai-jun，et al.Research on the classification of brain function based on SVM[J].The 2nd International Conference on Bioinformatics and Biomedical Engineering.2008（5）:1931-1934.

[7]Fung G，Mangasarian O L.Finite newton method for lagrangian support vector machine classification[J].Neurocomputing，2003，55（1-2）:39-55.

[8]張偉平.行為刺激下腦功能核磁共振圖像處理新方法研[D].西安：西北工業(yè)大學(xué)，2008.