核極化的多核LSSVM及其在分類(lèi)中的應(yīng)用

劉文婧，陳肖潔

（內(nèi)蒙古科技大學(xué) 機(jī)械工程學(xué)院，內(nèi)蒙古 包頭 014010）

1 引言

支持向量機(jī)（support vector machine，SVM）[1]是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化，以統(tǒng)計(jì)學(xué)習(xí)理論為基礎(chǔ)。SVM善于處理小樣本、高維和非線(xiàn)性等問(wèn)題。然而，SVM的最優(yōu)分類(lèi)超平面參數(shù)的獲取是通過(guò)求解計(jì)算量復(fù)雜的二次規(guī)劃，為減小SVM的計(jì)算花銷(xiāo)，文獻(xiàn)[2]提出了最小二乘支持向量機(jī)（leastsquaressupportvectormachine，LSSVM）。LSSVM的優(yōu)勢(shì)是求解一組線(xiàn)性方程組來(lái)得到最優(yōu)分類(lèi)面參數(shù)，極大地減少了計(jì)算復(fù)雜度。近年來(lái)，為增強(qiáng)決策函數(shù)的可理解性和可解釋性，以便獲取更優(yōu)的泛化性能，多核學(xué)習(xí)（multiple kernel learning，MKL）[3]吸引了廣大研究者們的眼眸。多核學(xué)習(xí)，顧名思義，就是多個(gè)基本核函數(shù)依據(jù)某種規(guī)則組合成新的核函數(shù)進(jìn)行學(xué)習(xí)。在MKL框架下，通常需要考慮的問(wèn)題是如何確定多個(gè)基本核函數(shù)的權(quán)系數(shù)（組合系數(shù)）問(wèn)題。目前，關(guān)于多核權(quán)系數(shù)的求解問(wèn)題，依分類(lèi)器為劃分標(biāo)準(zhǔn)，有如下兩種方法：

（1）以SVM為分類(lèi)器的MKL模型，多核權(quán)系數(shù)的求解方法有：采用核排列思想[4]和核極化思想[5]，即利用核排列或核極化確定每個(gè)基本核函數(shù)的權(quán)系數(shù)，無(wú)須反復(fù)訓(xùn)練SVM分類(lèi)器，計(jì)算高效；文獻(xiàn)[6]提出的局部多核學(xué)習(xí)，文獻(xiàn)[7]提出的SimpleMKL算法，權(quán)系數(shù)的優(yōu)化需要多次訓(xùn)練SVM分類(lèi)器，計(jì)算量較大；

（2）以L(fǎng)SSVM為分類(lèi)器的MKL模型[8-9]，循環(huán)迭代LSSVM分類(lèi)器進(jìn)行權(quán)系數(shù)優(yōu)化。為了最小化計(jì)算開(kāi)銷(xiāo)，我們采用方法（1）中獨(dú)立于分類(lèi)器的核極化來(lái)確定多核的權(quán)系數(shù)和選用方法（2）的LSSVM為分類(lèi)器。因此，將LSSVM、多核學(xué)習(xí)與核極化結(jié)合起來(lái)考慮，解決了盲目地選擇核函數(shù)的問(wèn)題，提出一種基于核極化的多核LSSVM算法模型，并將該算法模型應(yīng)用于二分類(lèi)和多分類(lèi)中以觀(guān)察所提出算法的有效性。

2 最小二乘支持向量機(jī)

二分類(lèi)時(shí)，給定一組樣本個(gè)數(shù)為L(zhǎng)的訓(xùn)練集｛xk，yk｝∈Rn×｛+1，-1｝，在非線(xiàn)性分類(lèi)的情形下，通過(guò)核函數(shù)的隱式定義 k（xi，yj）=（φ（xi），φ（yj）），φ（xi）：Rn→Rs，將樣本數(shù)據(jù)從輸入 n 維空間映射到更高維的S空間，目的是在高維的S空間中以線(xiàn)性的方式解決輸入n空間的非線(xiàn)性分類(lèi)問(wèn)題。綜合考慮函數(shù)復(fù)雜度和分類(lèi)允許誤差，二分類(lèi)問(wèn)題的數(shù)學(xué)語(yǔ)言可表述如下：

式中：γ—正則化參數(shù)；ei—松弛變量；b—偏置量。

構(gòu)建Lagrange方程求解式（1）：

L（ω，e，b，α）=J（ω，e，b）-

式（2），由 Karush-Kuhn-Tucker（KKT）條件可得：

整理式（3），可得一組線(xiàn)性方程組，如下所示：

式中：Y=（y1，…，yl）T；Ωij=yiyjk（xi，xj）；I—與 Ω 同階的單位矩陣；I1=（1，…，1）T的全 1 列矩陣，與 Ω 同行；拉格朗日乘子Y=（α1，…，αl）T。

通過(guò)解方程式（4），解得b和α，對(duì)未來(lái)輸入樣本x，LSSVM的輸出決策函數(shù)為：

多分類(lèi)時(shí)，目前，在實(shí)際應(yīng)用中，多分類(lèi)問(wèn)題的求解方法主要有兩種，一種為一次性多目標(biāo)優(yōu)化方法，另一種為將多分類(lèi)問(wèn)題轉(zhuǎn)化為二分類(lèi)問(wèn)題。所謂一次性多目標(biāo)優(yōu)化，就是將所有的優(yōu)化參數(shù)在一次的運(yùn)算中均獲得最優(yōu)解，在求解過(guò)程中，由于變量數(shù)目多導(dǎo)致運(yùn)算復(fù)雜，且最終的預(yù)測(cè)精度也不盡如意。第二種方法便于理解和實(shí)現(xiàn)，因此，我們將多分類(lèi)問(wèn)題轉(zhuǎn)化為多個(gè)二分類(lèi)問(wèn)題進(jìn)行多分類(lèi)的求解，具體轉(zhuǎn)化方式有一對(duì)多和一對(duì)一，前者易造成樣本數(shù)據(jù)的失衡，為了使樣本數(shù)據(jù)保持平衡，選用一對(duì)一方式。

3 多核最小二乘支持向量機(jī)

多核最小二乘支持向量機(jī)（least squares support vector machinewithmultiplekernels，MK_LSSVM）算法的核心理念就是將M個(gè)類(lèi)型不同的或類(lèi)型相同參數(shù)不同的基本核函數(shù)k1，…，km進(jìn)行線(xiàn)性的或非線(xiàn)性的加權(quán)組合，構(gòu)造新的核函數(shù)，并用于LSSVM分類(lèi)器的學(xué)習(xí)和預(yù)測(cè)。根據(jù)多核學(xué)習(xí)MKL[3，9]的原理，MK_LSSVM的決策函數(shù)為：

式中：μi—第i個(gè)基本核函數(shù)的權(quán)系數(shù)；M—基本核函數(shù)的總個(gè)數(shù)。

基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，MK_LSSVM的原始優(yōu)化問(wèn)題表述為：

式（7），構(gòu)建拉格朗日函數(shù)進(jìn)行求解：

由KKT條件，分別對(duì)式（8）的各參數(shù)ωi，ek，b，αk求偏導(dǎo)，可得：

將式（10）整理為矩陣的形式如下：

Ωij=y—第 k 個(gè)核函數(shù)的權(quán)系數(shù)，其 μi值的確定，我們采用獨(dú)立于分類(lèi)器算法的核度量標(biāo)準(zhǔn)—核極化。

4 核極化的MK_LSSVM

4.1 核極化

2005 年，文獻(xiàn)[10]提出了核極化（kernel polarization，KP）的概念，并給出了其定義式為：

式中：k—核矩陣；

yyT—理想核矩陣。

Baram指出P的幾何意義為當(dāng)同類(lèi)樣本點(diǎn)相互靠近，異類(lèi)樣本點(diǎn)相互遠(yuǎn)離時(shí)，P值越大。在MKL框架下，可以這樣理解，當(dāng)某一核函數(shù)對(duì)樣本正確分類(lèi)的貢獻(xiàn)率越大時(shí)，該核函數(shù)相對(duì)應(yīng)的P值越大。因此，我們可以利用每一基本核函數(shù)的核極化值的大小來(lái)確定其權(quán)系數(shù)的大小，即

4.2 核函數(shù)

目前，使用廣泛的基本核函數(shù)有：高斯核、多項(xiàng)式核、線(xiàn)性核等。我們選用全局性核函數(shù)—多項(xiàng)式核和局部性核函數(shù)—高斯核作為多核組合的基本核函數(shù)，高斯核和多項(xiàng)式核的表達(dá)式為：

為了減小不同核函數(shù)之間的差異性，我們對(duì)核函數(shù)進(jìn)行球形標(biāo)準(zhǔn)化處理，具體公式為：

4.3 核極化的MK_LSSVM算法步驟

Step 1：二分類(lèi)時(shí)，樣本類(lèi)別為｛+1，-1｝；多分類(lèi)時(shí)，按一對(duì)一方式，將多分類(lèi)轉(zhuǎn)化為多個(gè)二分類(lèi)；Step 2：選擇基本核函數(shù)：高斯核和多項(xiàng)式核，并設(shè)置相應(yīng)的核參數(shù)值σ和q；Step 3：基本核函數(shù)的標(biāo)準(zhǔn)化處理（見(jiàn)式（17））；Step 4：計(jì)算每個(gè)基本核函數(shù)的核極化值Pi，并按式（14）確定核函數(shù)的權(quán)系數(shù)μi；Step5：建立MK_LSSVM分類(lèi)器算法模型，由式（12）確定a和b；Step 6：MK_LSSVM模型預(yù)測(cè)，根據(jù)式（6）預(yù)測(cè)新輸入的樣本x的類(lèi)別。

5 實(shí)例仿真

為了驗(yàn)證所提的基于核極化的MK_LSSVM算法模型的有效性，我們從UCI標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中選取6組數(shù)據(jù)集，分別為Breast、Heart、Banknote、Wine、Iris和 Glass，前三個(gè)為二分類(lèi)數(shù)據(jù)集，后三個(gè)為多分類(lèi)數(shù)據(jù)集，數(shù)據(jù)集的基本屬性，如表1所示。

表1 試驗(yàn)的數(shù)據(jù)集簡(jiǎn)介T(mén)ab.1 The Data Set of Experiments

Breast為二分類(lèi)，包含良性（Benign）和惡性（Malignant）兩類(lèi)，數(shù)據(jù)集的全稱(chēng)為WisconsinBreastCancerDatabase。Breast數(shù)據(jù)原有樣本699個(gè)，因缺失16個(gè)樣本數(shù)據(jù)，故實(shí)驗(yàn)中采用的樣本為683個(gè)，每個(gè)樣本含有9個(gè)輸入特征Heart數(shù)據(jù)集二分類(lèi)，包含270個(gè)樣本，每個(gè)樣本含有13個(gè)特征分量，具體特征屬性為：年齡、性別、胸部疼痛類(lèi)型、靜息血壓值、血清類(lèi)固醇、空腹血糖值、靜息心電圖、最大心率值、運(yùn)動(dòng)性心絞痛、抑郁癥、運(yùn)動(dòng)斜率、血管數(shù)和病患類(lèi)型。Banknote為鈔票數(shù)據(jù)集，二元分類(lèi)問(wèn)題（0為真鈔，1為假鈔），共含有的觀(guān)察值1372個(gè)，4個(gè)連續(xù)的輸入特征變量，分別為：小波變換圖像、小波偏斜變換圖像、小波峰度變換圖像和圖像熵。BanknoteDataset是依據(jù)給定鈔票的特征預(yù)測(cè)是鈔票的真假。Iris是IrisPlantsDatabase的簡(jiǎn)稱(chēng)，包含150個(gè)樣本觀(guān)察值，每個(gè)樣本含有4個(gè)屬性特征：萼片長(zhǎng)度、花瓣長(zhǎng)度、萼片寬度、花瓣寬度。3 類(lèi) setosa、versicolor、virginica，每個(gè)類(lèi)的觀(guān)察值均等，均為50個(gè)樣本。WineRecognitionData數(shù)據(jù)集，多分類(lèi)。Wine數(shù)據(jù)完整，無(wú)缺失，大小為178×13：樣本數(shù)為178個(gè)，每個(gè)樣本的輸入特征為13個(gè)。數(shù)據(jù)來(lái)源自意大利同一地區(qū)三類(lèi)不同品種酒的大量研究和分析。在數(shù)據(jù)“wine.data”中，178行，行代表酒的樣本，其中，第1類(lèi)：59個(gè)樣本，第2類(lèi)：71個(gè)樣本，第3類(lèi)：48個(gè)樣本，即共有178個(gè)樣本；14列，第一列：類(lèi)標(biāo)志屬性，標(biāo)記為“1”，“2”，“3”等三類(lèi)；第2列至第14列為樣本輸入特征值。

試驗(yàn)前，所有樣本數(shù)據(jù)集均經(jīng)過(guò)平均值為0，方差為1的數(shù)據(jù)預(yù)處理，即

試驗(yàn)時(shí)，對(duì)于每個(gè)數(shù)據(jù)集，選取總樣本個(gè)數(shù)的50%為訓(xùn)練集，剩余樣本為測(cè)試集。按照第四部分的4.3的算法步驟，選取高斯核和多項(xiàng)式核作為組合多核的基本核函數(shù)，核參數(shù)分別取σ＝2、σ＝3 和 q＝2、q＝3。為證明所提算法的正確性，具體的 MK_LSSVM算法形式有：（1）高斯核（σ＝2）和多項(xiàng)式核（q＝3）組合的多核，簡(jiǎn)記為 MK_LSSVM_g2+p3；（2）高斯核（σ＝2）、多項(xiàng)式核（q＝3）和多項(xiàng)式核（q＝2）組合的多核，簡(jiǎn)記為 MK_LSSVM_g2+p3+p2；（3）高斯核（σ＝2）、多項(xiàng)式核（q＝2）和高斯核（σ＝3）組合的多核，簡(jiǎn)記為MK_LSSVM_g2+p3+g3。

采用的對(duì)比試驗(yàn)方法有：

（1）經(jīng)典的5-折交叉驗(yàn)證的SVM，用臺(tái)灣大學(xué)林智仁編寫(xiě)的工具箱Libsvm實(shí)現(xiàn)，選用高斯核，并C和高斯參數(shù)范圍均為，［2-5，25］迭代步長(zhǎng)為；（2）LSSVM 模型，選用高斯核，其核參數(shù)，記為L(zhǎng)SSVM_g2；（3）基于核排列的多核SVM算法，選用高斯核（σ＝2）和多項(xiàng)式核（q＝3），即 MK_AlignmentSVM_g2+p3；（4）局部多核學(xué)習(xí)的SVM算法，即MK_LocalizedSVM_g2+p3；（5）廣義化的多核 SVM 算法，即 MK_GeneralizedSVM_g2+p3；（6）GroupLasso多核SVM算法，即 MK_GroupLassoSVM_g2+p3；（7）Simple多核 SVM算法，即MK_SimpleSVM_g2+p3；（8）核極化的多核SVM算法，即MK_PolarizationSVM_g2+p3。

為了體現(xiàn)實(shí)驗(yàn)算法的客觀(guān)性，選用分類(lèi)準(zhǔn)確率為算法評(píng)價(jià)指標(biāo)，其中，為分類(lèi)正確的樣本個(gè)數(shù)，為總預(yù)測(cè)的樣本個(gè)數(shù)。為了體現(xiàn)算法中公正性，我們采用10次獨(dú)立試驗(yàn)的平均值。所有算法的試驗(yàn)結(jié)果，如表2所示。

表2中的粗體數(shù)值表示在該試驗(yàn)參數(shù)下最好的結(jié)果值，觀(guān)察表2的試驗(yàn)結(jié)果，我們可以知道，就分類(lèi)準(zhǔn)確率而言，數(shù)據(jù)集Breast和Glass分別在算法MK_LSSVM_g2+p3和MK_LSSVM_g2+p3+p2上取得了最優(yōu)的結(jié)果；數(shù)據(jù)集Banknote和Iris同樣在所提出的MK_LSSVM算法上取得最優(yōu)的分類(lèi)準(zhǔn)確率；在Heart和Wine數(shù)據(jù)集上，傳統(tǒng)經(jīng)典的5折SVM得到了最好的分類(lèi)結(jié)果，所提出的MK_LSSVM的結(jié)果僅次于SVM。綜上所述，試驗(yàn)結(jié)果說(shuō)明了所提出的基于核極化的多核最小二乘算法是有效性。

表2 試驗(yàn)結(jié)果Tab.2 The Results of Experiments

6 結(jié)語(yǔ)

在多核學(xué)習(xí)原理的指導(dǎo)下，引入了核極化，提出了基于核極化的多核最小二乘支持向量機(jī)算法模型，解決了LSSVM核函數(shù)選擇盲目性的問(wèn)題。UCI數(shù)據(jù)集上的試驗(yàn)結(jié)果表明MK_LSSVM算法的有效性。

［1］Vapnik V N.The Nature of Statistical Learning Theory［M］.New York：Springer Verlag，1995.

［2］Suykens J A K，Vandewalle J.Least squares support vector machines classifiers［J］.Neural Processing Letters，1999，9（3）：293-300.

［3］Mehmet Gonen，Ethem Alpaydin.Multiple kernel learning algorithms［J］.Journal of Machine Learning Research，2011（12）：2211-2268.

［4］He Junfeng，Chang Shih-Fu，Xie Lexing.Fast kernel learning for spatial pyramid matching［C］.In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2008.

［5］Wang Tinghua，Zhao Dongyan，F(xiàn)eng Yansong.Two-stage multiple kernel learning with multiclass kernel polarization［J］.Knowledge-Based Systems，2013，48（2）：10-16.

［6］Mehmet Gonen，Ethem Alpaydin.Localized multiple kernel learning［C］.In Proceedings of the 25th International Conference on Machine Learning，2008.

［7］Rakotomamonjy A，Bach F R，Canu S.SimpleMKL［J］.Journal of Machine Learning Research，2008（9）：2491-2521.

［8］Jian L，Xia Z，Liang X.Design of a multiple kernel learning algorithm for LS-SVM by convex programming［J］.Neural Networks，2011，24（5）：476-483.

［9］Chen X，Guo N，Ma Y.More efficient sparse multi-kernel based least square support vector machine［C］.Communications and Information Processing，Berlin：Springer-Heidelberg，2012：70-78.

［10］Baram Y.Learnning by kernel polarization［J］.Neural Computation，2005，17（6）：1264-1275.