核極化的多核LSSVM及其在分類中的應用

劉文婧，陳肖潔

（內蒙古科技大學 機械工程學院，內蒙古 包頭 014010）

1 引言

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

（1）以SVM為分類器的MKL模型，多核權系數的求解方法有：采用核排列思想[4]和核極化思想[5]，即利用核排列或核極化確定每個基本核函數的權系數，無須反復訓練SVM分類器，計算高效；文獻[6]提出的局部多核學習，文獻[7]提出的SimpleMKL算法，權系數的優化需要多次訓練SVM分類器，計算量較大；

（2）以LSSVM為分類器的MKL模型[8-9]，循環迭代LSSVM分類器進行權系數優化。為了最小化計算開銷，我們采用方法（1）中獨立于分類器的核極化來確定多核的權系數和選用方法（2）的LSSVM為分類器。因此，將LSSVM、多核學習與核極化結合起來考慮，解決了盲目地選擇核函數的問題，提出一種基于核極化的多核LSSVM算法模型，并將該算法模型應用于二分類和多分類中以觀察所提出算法的有效性。

2 最小二乘支持向量機

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

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

構建Lagrange方程求解式（1）：

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

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

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

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

通過解方程式（4），解得b和α，對未來輸入樣本x，LSSVM的輸出決策函數為：

多分類時，目前，在實際應用中，多分類問題的求解方法主要有兩種，一種為一次性多目標優化方法，另一種為將多分類問題轉化為二分類問題。所謂一次性多目標優化，就是將所有的優化參數在一次的運算中均獲得最優解，在求解過程中，由于變量數目多導致運算復雜，且最終的預測精度也不盡如意。第二種方法便于理解和實現，因此，我們將多分類問題轉化為多個二分類問題進行多分類的求解，具體轉化方式有一對多和一對一，前者易造成樣本數據的失衡，為了使樣本數據保持平衡，選用一對一方式。

3 多核最小二乘支持向量機

多核最小二乘支持向量機（least squares support vector machinewithmultiplekernels，MK_LSSVM）算法的核心理念就是將M個類型不同的或類型相同參數不同的基本核函數k1，…，km進行線性的或非線性的加權組合，構造新的核函數，并用于LSSVM分類器的學習和預測。根據多核學習MKL[3，9]的原理，MK_LSSVM的決策函數為：

式中：μi—第i個基本核函數的權系數；M—基本核函數的總個數。

基于結構風險最小化原則，MK_LSSVM的原始優化問題表述為：

式（7），構建拉格朗日函數進行求解：

由KKT條件，分別對式（8）的各參數ωi，ek，b，αk求偏導，可得：

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

Ωij=y—第 k 個核函數的權系數，其 μi值的確定，我們采用獨立于分類器算法的核度量標準—核極化。

4 核極化的MK_LSSVM

4.1 核極化

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

式中：k—核矩陣；

yyT—理想核矩陣。

Baram指出P的幾何意義為當同類樣本點相互靠近，異類樣本點相互遠離時，P值越大。在MKL框架下，可以這樣理解，當某一核函數對樣本正確分類的貢獻率越大時，該核函數相對應的P值越大。因此，我們可以利用每一基本核函數的核極化值的大小來確定其權系數的大小，即

4.2 核函數

目前，使用廣泛的基本核函數有：高斯核、多項式核、線性核等。我們選用全局性核函數—多項式核和局部性核函數—高斯核作為多核組合的基本核函數，高斯核和多項式核的表達式為：

為了減小不同核函數之間的差異性，我們對核函數進行球形標準化處理，具體公式為：

4.3 核極化的MK_LSSVM算法步驟

Step 1：二分類時，樣本類別為｛+1，-1｝；多分類時，按一對一方式，將多分類轉化為多個二分類；Step 2：選擇基本核函數：高斯核和多項式核，并設置相應的核參數值σ和q；Step 3：基本核函數的標準化處理（見式（17））；Step 4：計算每個基本核函數的核極化值Pi，并按式（14）確定核函數的權系數μi；Step5：建立MK_LSSVM分類器算法模型，由式（12）確定a和b；Step 6：MK_LSSVM模型預測，根據式（6）預測新輸入的樣本x的類別。

5 實例仿真

為了驗證所提的基于核極化的MK_LSSVM算法模型的有效性，我們從UCI標準數據庫中選取6組數據集，分別為Breast、Heart、Banknote、Wine、Iris和 Glass，前三個為二分類數據集，后三個為多分類數據集，數據集的基本屬性，如表1所示。

表1 試驗的數據集簡介Tab.1 The Data Set of Experiments

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

試驗前，所有樣本數據集均經過平均值為0，方差為1的數據預處理，即

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

采用的對比試驗方法有：

（1）經典的5-折交叉驗證的SVM，用臺灣大學林智仁編寫的工具箱Libsvm實現，選用高斯核，并C和高斯參數范圍均為，［2-5，25］迭代步長為；（2）LSSVM 模型，選用高斯核，其核參數，記為LSSVM_g2；（3）基于核排列的多核SVM算法，選用高斯核（σ＝2）和多項式核（q＝3），即 MK_AlignmentSVM_g2+p3；（4）局部多核學習的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。

為了體現實驗算法的客觀性，選用分類準確率為算法評價指標，其中，為分類正確的樣本個數，為總預測的樣本個數。為了體現算法中公正性，我們采用10次獨立試驗的平均值。所有算法的試驗結果，如表2所示。

表2中的粗體數值表示在該試驗參數下最好的結果值，觀察表2的試驗結果，我們可以知道，就分類準確率而言，數據集Breast和Glass分別在算法MK_LSSVM_g2+p3和MK_LSSVM_g2+p3+p2上取得了最優的結果；數據集Banknote和Iris同樣在所提出的MK_LSSVM算法上取得最優的分類準確率；在Heart和Wine數據集上，傳統經典的5折SVM得到了最好的分類結果，所提出的MK_LSSVM的結果僅次于SVM。綜上所述，試驗結果說明了所提出的基于核極化的多核最小二乘算法是有效性。

表2 試驗結果Tab.2 The Results of Experiments

6 結語

在多核學習原理的指導下，引入了核極化，提出了基于核極化的多核最小二乘支持向量機算法模型，解決了LSSVM核函數選擇盲目性的問題。UCI數據集上的試驗結果表明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，Feng 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.