史 娜，薛 暉+，汪云云

1.東南大學 計算機科學與工程學院，南京 211189

2.東南大學 計算機網(wǎng)絡和信息集成教育部重點實驗室，南京 211189

3.南京郵電大學 計算機學院，南京 210023

1 引言

支持向量機（support vector machine，SVM）作為一種有效的分類技術，已經(jīng)在實際應用中取得了非常好的效果。尤其在引入核技巧后，SVM 的性能進一步提高[1]。在經(jīng)典的核SVM（kernel SVM，KSVM）算法中，通常要求核矩陣正定，即核函數(shù)滿足Mercer定理。但是近年來，在計算機視覺和生物信息等領域，出現(xiàn)了越來越多的非正定度量手段[2-5]，例如：利用最長公共子序列，度量兩個基因序列相似性；利用BLAST 評分函數(shù)，度量兩個蛋白質序列相似性；利用集合操作的交、并等，度量兩個事務的相似性；利用人類先驗知識，判斷兩個概念或者單詞之間的相似性；計算機視覺領域中的利用正切距離和形狀匹配等，度量兩個圖形的相似性。上述的度量手段往往導致核矩陣的不定，進而使得經(jīng)典的KSVM 算法無法對這些問題進行有效的求解[6-7]。針對上述問題，越來越多的學者對不定核支持向量機（indefinite kernel support vector machine，IKSVM）展開了廣泛的研究。目前IKSVM 的求解算法主要分為兩大類：（1）基于核矩陣修正的求解；（2）基于原始不定核矩陣的求解。第一類算法是將不定核矩陣修正為正定矩陣，從而使得經(jīng)典的KSVM 算法仍然適用。例如，將核矩陣的所有負特征值置零的“Clip”算法、將核矩陣的所有負特征值取絕對值的“Flip”算法、將核矩陣的特征值加上一個正常數(shù)以使得所有特征值大于零的“Shift”算法，以及將所有特征值取平方的“Squared”算法等[8]。除了上述將矩陣修正和KSVM 問題求解分開進行的做法外，另一種比較常見的做法就是將矩陣修正和經(jīng)典KSVM 分類進行聯(lián)合求解。Chen 等人[9]將原始的不定核矩陣視作一個未知正定矩陣的帶噪聲形式，并將該正定矩陣的擬合和經(jīng)典KSVM 分類聯(lián)合起來作為最終的優(yōu)化目標。Gu 等人[10]認為不定核矩陣具有低秩的正定近似，從而將核矩陣的低秩正定近似求解和經(jīng)典KSVM 問題求解聯(lián)系起來，并進行迭代優(yōu)化。然而，上述基于核矩陣的正定近似進行IKSVM 問題求解的算法，會使得不定核矩陣的一些有用信息丟失，因此在實際應用中效果并不理想[11-12]。第二類算法直接利用不定核矩陣進行求解，從而解決矩陣的修正過程帶來的信息丟失問題。Alabdulmohsin 等人[7]將核矩陣K的每一行看作樣本的特征，從而將IKSVM 問題轉化成普通的線性規(guī)劃問題進行求解。Hochreiter 等人[13]將KKT的行看作特征，從而可以利用現(xiàn)有的凸優(yōu)化算法進行求解。Loosli等人[12]通過探究再生核Kre?n 空間（reproducing kernel Kre?n space，RKKS）和再生核Hilbert 空間（reproducing kernel Hilbert spaces，RKHS）之間的關系，提出可以將IKSVM的解與KSVM 的解通過一個映射矩陣聯(lián)系起來，從而達到IKSVM問題的間接求解。Xu等人[14]從IKSVM優(yōu)化的主問題出發(fā)，提出可以將IKSVM 問題刻畫成一個凸差規(guī)劃問題，從而能夠利用現(xiàn)有相關的凸差算法進行求解。Oglic 等人[15]將IKSVM 問題轉化成一個約束特征值問題，從而可以利用特征值方程進行問題的求解。然而，上述的IKSVM 算法，均不能較好地解決高維數(shù)據(jù)所帶來的信息冗余和樣本稀疏問題。因此，在實際處理高維數(shù)據(jù)時，通常會采用主成分分析（principal component analysis，PCA）作為數(shù)據(jù)的預處理方式，然后再進行IKSVM 的處理。但是，這種處理方式也有其局限性，即處理的數(shù)據(jù)必須是樣本的向量表示形式，若給定度量矩陣的結構化數(shù)據(jù)集，該種處理方式將無法應用。

為了解決高維數(shù)據(jù)所帶來的信息冗余和樣本稀疏等問題，本文基于Loosli 等人[12]對IKSVM 穩(wěn)定化問題的定義，從理論上證明了IKSVM 問題的求解等價為IKPCA（indefinite kernel principal component analysis）和SVM 的依次執(zhí)行，并提出了一種求解IKSVM問題的新型學習框架：TP-IKSVM（two-phase indefinite kernel support vector machine）。該學習框架將IKSVM 問題的求解分為兩個階段：第一階段應用IKPCA 技術進行非線性降維以提取數(shù)據(jù)的主要信息，同時緩解信息冗余和樣本稀疏等問題[16]；第二階段在降維后的特征空間進行SVM，從而進一步挖掘低維空間中判別信息。另外，由于本學習框架不涉及樣本的原始向量表示形式，因此TP-IKSVM 的應用更加靈活。在真實數(shù)據(jù)集上的實驗表明，TP-IKSVM在分類性能上優(yōu)于現(xiàn)有的IKSVM 算法。

2 相關工作

2.1 Kre?n 空間和RKKS

Kre?n 空間K 是由兩個Hilbert 空間(H+,H-)張成的內積空間，并且滿足[12，15]：

（1）?f∈K,f=f++f-

（2）?f,g∈K,

其中，f+，g+∈H+，f-，g-∈H-。

如果這里的H+、H-均為RKHS，那么Kre?n 空間K 就是一個RKKS，可以看出RKKS 是Kre?n 空間的特例。假設實值對稱函數(shù)k可以對應到一個RKKS，那么滿足k=k+-k-，其中k+和k-是可以分別對應到H+和H-的實值函數(shù)。

為后續(xù)描述的方便，這里將Kre?n 空間限定為有限維空間，并用pE表示（有限維的Kre?n 空間又稱偽歐空間，用pE表示）。具體地，pE可以表示為兩個歐式空間的直和R(p,q)=Rp⊕Rq，其中Rp和Rq均為Hilbert 空間，相應的內積操作為。引入J=diag(1p′-1q)，則pE空間中的內積可以進一步表示為，其中運算符“*”代表pE空間的內積操作，J代表了pE空間的維度特性，并且滿足J=JT=J-1[17]。

2.2 IKPCA

IKPCA[16]是一種非線性降維技術，旨在RKKS 中尋找一組投影方向，使得樣本投影點之間的差異最大化。

假設樣本在RKKS 中可以表示為Φ={φ(x1),φ(x2),…,φ(xn)}，其中φ為映射函數(shù)；特征均值為μ=。設Φ已經(jīng)中心化，即φ(xi)=φ(xi)-μ。定義RKKS 中全散度矩陣Sκ：

其中，S|κ|=ΦΦT為與RKKS 相應的RKHS 中的全散度矩陣。

因此，IKPCA 的目標函數(shù)可表示為：

最后，對K進行特征分解，得到式（3）的最優(yōu)解：

3 TP-IKSVM

為了引出求解IKSVM 問題的新型學習框架TPIKSVM，本章首先對IKSVM 問題進行形式化的定義，然后基于該定義給出TP-IKSVM 的證明。

3.1 IKSVM

Loosli 等人[12]的研究表明，IKSVM 的求解可以表示成RKKS 中的穩(wěn)定化問題，即：

將式（6）的極大化部分等價轉換為負的極小化問題，得到：

最后，將上述約束最小化問題轉換成等價的無約束問題，得到：

上式記為IKSVM 問題的主問題P-IKSVM。

根據(jù)表示定理，得到相應的對偶問題，并記為DIKSVM：

其中，K是不定核矩陣，Ki代表核矩陣的第i行，K+、K-是根據(jù)核函數(shù)k+、k-所得到的正定核矩陣，并且滿足k=k+-k-，K=K+-K-。

3.2 TP-IKSVM 的證明

TP-IKSVM 學習框架是一種解決IKSVM 問題的新型求解思路。TP-IKSVM 將IKSVM 的求解拆分為IKPCA 和線性SVM 兩個階段。其中第一階段的IKPCA 作為一種經(jīng)典的降維技術首先將原始的高維樣本數(shù)據(jù)投影到一個低維空間，從而緩解由于樣本維度與樣本個數(shù)比值較小產(chǎn)生的樣本稀疏問題，然后在降維后的空間中進行第二階段SVM，能夠更好地挖掘低維數(shù)據(jù)的分類信息。為了說明TP-IKSVM學習框架的合理性，引入下面的定理1。

定理1 設α為原始pE空間中D-IKSVM 問題的解，為樣本經(jīng)過IKPCA 降維后pE1空間中的SVM問題的解，則。

證明 記經(jīng)過IKPCA 降維后，特征空間由原始的pE∈(p,q) 變?yōu)閜E1∈(p1,q1)，樣本特征由Φ(xi) 變?yōu)?，即?/p>

在pE1空間進行SVM，可以表示為如下優(yōu)化問題：

將式（12）等價變換為無約束的優(yōu)化問題：

通過定理1，可以發(fā)現(xiàn)分兩階段求解的TPIKSVM 和直接求解IKSVM 等價。但是，考慮率到pE1空間的未知，因此求解相對復雜，為了簡化第二階段問題的求解，引入命題1。

證明 在pE1空間對應的Hilbert 空間中進行SVM，等價于下述問題的求解：

根據(jù)Hilbert空間的性質可知：

由命題1 可知TP-IKSVM 第二階段的pE1空間SVM 可以簡化為對應Hilbert空間中的SVM。

結合定理1 和命題1，可以看出IKSVM 的求解本質是在IKPCA 降維后的空間中進行SVM。另外，通過IKPCA 階段的降維，可以很好地處理高維數(shù)據(jù)中的信息冗余，并且也一定程度地緩解了樣本稀疏的問題。基于該結論，設計出求解IKSVM 問題的新型學習框架TP-IKSVM，具體算法的描述如下：

輸入：K，不定核矩陣；Y，類別標簽；p1+q1，IKPCA 所要降到的維度；λ，規(guī)則化參數(shù)；k(·,x*)，所有訓練樣本與測試樣本x*核相似性度量。

輸出：y*，x*的預測標簽。

（1）利用式（4）計算Q，并保留對應特征值前(p1+q1)大的特征向量。

（4）計算x*的低維映射特征。

4 實驗及結果分析

本章通過在兩種數(shù)據(jù)類型向量形式的數(shù)據(jù)、結構化的數(shù)據(jù)上的實驗，檢驗所提TP-IKSVM 算法的性能。實驗選擇如下主流IKSVM 方法作為對比算法：

（1）1-normIKSVM[7]：通過特征空間的嵌入，將IKSVM 問題轉化成線性規(guī)劃問題進行求解。

（2）ESVM[12]：首先求解相應的正定核支持向量機問題，然后通過映射矩陣P將KSVM 的解映射到IKSVM 問題的解。

（3）IKSVM-DC[14]：通過非凸優(yōu)化算法——凸差規(guī)劃進行求解。

（4）Kre?n[15]：將IKSVM 的學習問題轉化成帶約束的特征值問題進行求解。

4.1 向量形式的數(shù)據(jù)集上的實驗

本組實驗采用6個向量形式的高維數(shù)據(jù)集（http://featureselection.asu.edu/datasets.php）:Leukemia、ALLAML、Colon、Prostate_GE、TOX_171 和CLL_SUB_111_2，數(shù)據(jù)集的詳細統(tǒng)計信息如表1 所示。

Table 1 Description of 6 vectorial datasets表1 6 個向量形式的數(shù)據(jù)集描述

由于本組實驗數(shù)據(jù)集是向量形式的樣本，因此這里需要手動構造不定核矩陣。這里選用最常用的“sigmoid”核作為相似性度量核函數(shù)：

其中，核參數(shù)η的設置參照文獻[15]的選取方式，即:

本組的TOX_171 數(shù)據(jù)集是一個四分類問題，而IKSVM 本身是處理二分類問題的技術，因此本節(jié)將類別標簽為1、2 的樣本作為正例樣本，標簽為3、4 的作為負例樣本。相關參數(shù)的取值范圍設置為C∈{20,21,…,26},λ∈{2-6,2-5,…,26}。將數(shù)據(jù)集隨機劃分為數(shù)量大致相等的訓練數(shù)據(jù)集和測試數(shù)據(jù)集，并且進行10 輪的隨機劃分，實驗結果取自10 輪實驗的平均值。實驗結果見表2。

由表2 可知，本文算法在本組數(shù)據(jù)集上的分類精度性能均優(yōu)于其他對比算法，并且算法執(zhí)行速度和1-normIKSVM、Kre?n 大致相當。本組實驗的數(shù)據(jù)集樣本數(shù)量較少而特征維度較大，并且包含較多冗余信息，使得現(xiàn)有IKSVM 算法的性能表現(xiàn)不佳。而TP-IKSVM 通過兩階段的學習框架，能夠充分發(fā)揮IKPCA 在處理高維數(shù)據(jù)方面的優(yōu)勢，使得數(shù)據(jù)的冗余信息得到削弱。同時，經(jīng)過IKPCA 的操作使得樣本點分布在一個較低維的空間，使得樣本稀疏問題得到了一定程度的緩解，從而使得本文算法的性能得到進一步提升。

4.2 結構化的數(shù)據(jù)集上的實驗

本節(jié)實驗數(shù)據(jù)集是由代爾夫特理工大學模式識別實驗提供的給定不定性度量矩陣[18]的結構化數(shù)據(jù)，并且本組數(shù)據(jù)集主要涉及生物信息和計算機視覺等領域的高維特征度量問題。數(shù)據(jù)集的詳細統(tǒng)計信息見表3。

Table 2 Performance comparison of vectorial datasets表2 向量形式的數(shù)據(jù)集性能對比

Table 3 Description of 7 structured datasets表3 7 個結構化數(shù)據(jù)集描述

通過表3 的描述可知，本組數(shù)據(jù)集包含多分類問題，因此需要將多分類問題改為二分類問題，本文參照文獻[14]的設置方式，即選取一半的類別標簽作為正類，余下類別標簽作為負類。比如將DelftGestures數(shù)據(jù)集中標簽為1～10 的樣本作為正類，11～20 的作為負類。其余相關參數(shù)設置同4.1 節(jié)。將核矩陣隨機選取一半的行及相應的列所組成的子矩陣作為訓練數(shù)據(jù)集，用余下列與之前選取的行所組成的子矩陣構成測試數(shù)據(jù)集，并將數(shù)據(jù)集隨機進行10 輪劃分，并取10 輪實驗結果平均值作為最終的結果度量。實驗結果見表4。

從表4 可以看出，TP-IKSVM 算法的分類精度優(yōu)于所有對比算法，Kre?n 算法次優(yōu)，并且本文算法的運行速度明顯高于IKSVM-DC。在Zongker、Catcortex 和Chickenpieces數(shù)據(jù)集上的分類精度分別提高了4.5%、4.1%和14.9%左右。分析可知Zongker、Catcortex和Chickenpieces等數(shù)據(jù)集所提供的數(shù)據(jù)可能包含較多的冗余或者噪聲信息，使得普通的IKSVM 算法性能受限，而TP-IKSVM 通過將IKSVM 問題拆分為IKPCA 和SVM 兩個階段進行，使得信息冗余問題得到緩解，進一步使模型精度得到改善。同時，本組實驗也驗證了本文所提模型不僅在處理高維數(shù)據(jù)本身的冗余信息時有效，在處理由核的引入而導致的潛在高維特征空間中的信息冗余和樣本稀疏問題仍然有效。

Table 4 Performance comparison of structured datasets表4 結構化數(shù)據(jù)集性能對比

5 結束語

鑒于現(xiàn)有IKSVM 算法無法較好地處理高維數(shù)據(jù)的研究現(xiàn)狀，本文首先基于RKKS 中對IKSVM 的穩(wěn)定化問題的定義，證明了IKSVM 問題的求解可以等價為IKPCA 和SVM 的依次執(zhí)行，并且進一步提出了一種求解IKSVM 問題的新型學習框架TP-IKSVM。TP-IKSVM 將IKSVM 問題的求解分解為IKPCA 和SVM 兩個階段。TP-IKSVM 不僅發(fā)揮了SVM 在分類問題上良好泛化性能的優(yōu)勢，而且結合了IKPCA在處理高維數(shù)據(jù)方面的降低冗余信息和緩解樣本稀疏的優(yōu)勢。最后，真實數(shù)據(jù)集上的實驗驗證了本文所提算法能夠有效改善IKSVM 的實際泛化性能。