核機器學習方法及其在生物信息學中的應用

王 蕊，牟少敏，曹學成，蘇 平

(1.山東農業大學機械電子與工程學院，山東 泰安 271018;2.山東農業大學信息科學與工程學院，山東 泰安 271018)

機器學習(Machine Learning)是根據訓練樣本找出輸入/輸出數據之間的相互依賴關系估計，對未知的輸出樣本做出盡可能準確的預測或分類［1］。目前，隨著計算機技術的飛速發展，數據的采集速度和存儲技術都有了極大的提高，產生了各種大量的數據信息，需要人們對其進行合理的預測或分類，為科學決策提供有力的依據。因此，機器學習的研究具有非常重要的意義。而基于核的機器學習方法(簡稱:核方法)則以其優越的性能吸引了眾多研究人員的關注，成為機器學習領域的研究熱點之一。

核方法理論的研究工作可以追溯到1909年，Mercer首先在泛函分析中提出了再生核(Mercer核)和再生核Hilbert空間［2］。1950年，Aronszajn等人對其進行了進一步研究和完善［3］。1964年，Aizerman等人將再生核技術用于學習理論的證明［4］。1995年，統計學習理論的創始人Vapnik利用“核技巧”(Kernel trick)，即通過在特征空間中引入核函數代替內積，構建了一種基于統計學習理論的核方法—支持向量機(Support Vector Machine，SVM)［1，5］。該方法廣泛地應用于圖像處理、文本分類和網絡安全等領域［49］，推動了核理論和核機器學習研究工作進一步地深入開展。

近年來，國內外研究人員相繼提出了許多不同的核方法以及針對支持向量機的改進算法，使得核理論不斷地完善，核方法的應用領域不斷拓展。1998年，Sch·lkopf等人對線性主成分分析(Linear Principal Component Analysis，LPCA)方法進行核化，得到了相應的核主成分分析(Kernel Principal Component Analysis，KPCA)方法［6］。核典型相關分析(Kernel Canonical Correlation Analysis，KCCA)則是由 Mika等人于1999年提出的［7］，是模式識別中進行特征提取的重要技術。核聚類(Kernel Clustering，KC)［8］是基于核的聚類方法。其利用非線性映射，把輸入空間的樣本通過一個非線性變換映射到一個高維特征空間中，對變換后的樣本再進行聚類分析。

而對支持向量機的研究工作主要集中在以下幾個方面，降低支持向量機的計算復雜度、直推式學習、多類問題的分類、增量學習和核函數的研究，不少的研究人員提出了許多改進的算法。

1998年，Vapnik提出了一種半監督機器學習的方法，即直推式支持向量機［9］。它是將無標號和有標號數據作為訓練集，而訓練集中僅含有少量有標號和多數無標號的樣本點，大大減少了對有標號樣本的需求。

支持向量機最初是針對二類分類問題提出的，不能直接應用到多類分類問題中［10，11］。因此，如何將二類分類方法有效地推廣到多類問題，特別是大類別的分類問題，也是支持向量機理論研究的重要內容之一。

當訓練樣本數據過大，無法一次性讀入內存或在線學習情況下，訓練開始時無法得到所需要的全部數據時，可以采用支持向量機的增量學習算法(Incremental Learning)。將訓練集分成幾個獨立的子集，依次在各個子集上作增量學習，這樣不僅可以舍去無用的樣本，節省內存空間，縮短訓練時間，而且可以充分地利用以前的學習結果，使得學習結果具有延續性［12］。

支持向量機的應用受到限制的一個很重要的原因就是需要求解凸二次優化問題，對于大規模樣本的數據集，其計算具有較高的時間和空間復雜度。因此，如何在不影響分類性能的前提下，降低計算復雜度，提高學習速度，建立高效的求解支持向量機中的最優化問題算法，成了支持向量機一個很重要的研究方向。常用的算法有選塊算法(Chunking Method)［13］，分解算法(Decomposition Method)［14－15］，序列最小最優化算法(Sequential Minimal Optimization，SMO)［16］。

本文結構安排如下:第1節介紹了核方法及其分類，闡述了核函數的性質和構造高效核函數的方法。第2節是以生物信息技術為背景，對序列數據核函數在生物信息學中的應用進展作了詳細介紹。第3節對全文進行總結。

1 核方法

核方法的基本原理是采用非線性變換把輸入空間的樣本映射到高維的特征空間，從而達到線性可分的目的，對實際應用具有重要的意義。其簡單的核函數對應著“復雜”的映射。

通過核方法的基本原理可以看出，設計新的核方法主要有兩個關鍵問題:一是與核函數有關的問題。二是采用何種學習算法和改進學習算法的問題。采用不同的學習算法可以構成不同的核方法，如前面提到的將核函數引入聚類方法可以構成核聚類方法。

1.1 常用核方法的分類

機器學習可分為有監督和無監督的學習。有監督學習所處理訓練樣本的類別是事先已經標號的，而無監督學習所處理訓練樣本的類別則是未事先標號的。由于核方法的實質就是將核函數引入到一些模式分類或回歸方法中，因此可以將核分類方法也相應地分為有監督分類學習和無監督分類學習兩大類。支持向量機主要用于有監督的學習。而常用的無監督核方法有核主成分分析(Kernel Principal Component Analysis，KPCA)［17］、核聚類(Kernel Clustering，KC)、核獨立成分分析(Kernel Independent Component Analysis，KICA)［18］等。

另外，與前兩種學習方式不同的直推式學習是利用少量有標號的數據和大量無標號的數據進行訓練，通常稱為半監督學習方法。其相應的核方法可以作為第三類核方法。

1.2 核函數

核函數的思想在現實世界中有著廣泛的應用。實際上，如果一個分類或回歸問題，涉及到點積運算，那么就可以通過引入核函數將問題映射到高維空間中去解決。核函數(Kernel Function)定義為特征空間的一個點積K(x，y)=φ(x)·φ(y)。由于特征空間的維數一般很高，因此φ(x)的計算較為復雜。支持向量機的一個主要的技巧在于它與一般的降維技術不同，它是利用核函數將特征空間的非線性可分的數據映射高維的希爾伯特空間，達到線性可分的目的，而且不必明確知道映射函數φ，只須在輸入空間計算核函數K(x，y)即可，從而大大簡化了計算量。目前，核函數的研究工作主要集中在兩個方面:一是研究已有核函數的參數如何選取，即核參數選取的優化問題。核參數的選擇或優化是能否取得理想的預測結果的重要因素之一，其研究又以高斯核函數為主的較多;二是根據實際應用問題提供的數據，構造新的高效核函數。關于核參數的選擇與核函數的構造等問題的研究雖然已經取得了一些進展，但是仍不能令人滿意［19－21］。核函數的構造與應用的背景知識有著密切的關系，因為核函數反映的是樣本之間的相似性量測，所以在許多研究當中，研究者經常是根據研究領域中找尋其物理、化學、生物意義的相似性，構造一個特殊的核函數。如:結合文本分類［22］和入侵檢測技術［23］，可以設計出高效的核函數，提高支持向量機的分類性能，如何構造與實際問題有關的核函數，一直是SVM研究的重要課題。本文主要介紹的是核函數在生物信息領域中的應用。

目前，常用的核函數主要有4種，詳見表1。實際應用中采用和研究最多的是高斯核函數。

表1 常用核函數Table 1 Usually kernal function

核矩陣(Gram矩陣)則是表示在高維特征空間中，任意一對樣本的點積，與核函數有著密切的關系。

如果核函數是有效的，核矩陣則是對稱和半正定的［24］。

支持向量機和其它的核方法的研究工作過去主要是基于屬性值的，輸入數據一般是定義在向量空間。常用的核函數如:多項式核函數、RBF核函數等對數值問題的分類取得了較好的效果。但是，核函數并不局限于向量空間，很多模式分類問題涉及結構數據，如圖、樹和序列等，輸入數據往往不是長度相等的向量，各分量往往具有不同的語義，不能同等看待。對于序列數據而言，由于缺乏考慮序列數據信息的相似性，效果不佳。現在有的學者開始研究基于結構數據的核方法，即結構模式識別［24］，取得了較好的結果。如使用鄰域核識別紋理圖象［25］，使用字符串核和詞序列核進行文本分類［26］，使用邊界化核進行蛋白質分類等［27］。什么是結構數據，現在尚沒有統一的定義。一般情況下，文本、圖像、空間數據和蛋白質和基因等都可視為結構數據。常用的結構數據的類型有:串、樹、圖和集合等。如何有效地利用數據的內在的結構信息，構造相應的核函數，對于提高SVM性能，是一項非常有意義的研究工作。

表1的核函數是基于向量空間模型，缺乏利用數據間的結構信息，而且要求向量的長度是固定的。為了克服這一問題，研究人員通常對所專注的領域尋找具有物理、化學和生物意義的相似性，構造一種特殊的核函數即結構化數據核函數。結構化數據核函數常用的類型有字符串核函數、樹核函數和圖核函數。

目前，字符串核函數在生物信息學領域的應用相當活躍。因此，針對具體的應用，根據數據結構定義相應的核函數，能取得更好的識別效果，提高支持向量機的分類性能，擴展其應用領域。

對于結構化數據，要根據數據的結構信息定義反映數據間相似性的合法的核函數，然后再應用某種核方法對這些數據進行處理。定義結構化數據核函數的方法可按如下方式分類［28］:

(1)利用核函數的運算性質。首先定義每個成分的核函數，然后將這些核函數利用某種運算組合成一個合法的核函數，稱為組合核。

主要的代表有卷積核與鄰域核。Barzilay等人在紋理識別中采用了鄰域核(Neighborhood kernel)以利用數據中的結構知識［29］。卷積核(Convolution kernel)由Haussler提出［30］，并應用于字符串核。

(2)直接定義特征空間的一個點積，不需考慮Mercer條件。由于特征空間的維數通常很大，因此需要給出計算核函數的高效算法，稱為句法驅動核。

句法驅動核的主要思想是把對象分解成子結構(如子序列、子樹或子圖)，特征向量則由子結構的計數組成。

Leslie等人在蛋白質分類中提出了系列核(Spectrum kernel)的概念［31］，在長度為l的字符集上，定義長度為k的字符序列的k－系列核。Collins等人在自然語言處理問題中采用了樹核(Tree kernel)［32］。自然語言體現為字符串(句子)，但其中隱含著某種句法結構。

(3)利用描述數據的某種模型(如馬爾可夫模型)將數據轉換成向量空間形式，稱為模型驅動核。

(4)利用指數函數將對稱矩陣轉化成合法的核函數，稱為指數核。

指數核(Exponential kernel)由Kondor等人提出［33］，其主要思想是矩陣的指數運算可以產生符合正定準則的核。

支持向量機等核方法通常采用的是單核學習，即在學習過程中使用一個核函數。在現實世界中，往往存在大量的數據是針對多數據源或異構數據集的，采用單個核函數的效果不是太理想。例如，輸入空間是兩個向量組成的空間，第一個向量服從高斯分布，而第二個向量卻服從多項式分布。這時，如果僅僅采用一種核函數就顯得不足，若用高斯核函數則無法利用第二個向量進行有效劃分，而如果采用多項式核函數則由于第一個向量的存在會給分類造成影響。Sonnenburg等人提出了基于多核學習(Multiple Kernel)的支持向量機以及實現算法［34，35］。與單核學習相比，多核學習可以提高分類精度，魯棒性更強。多核學習用于生物序列數據的分類，也取得了良好的效果［36，37］。目前，如何進一步研究高效的多核學習的方法成為研究核方法的熱點之一。

多核學習有兩層含義:一是可以一次針對不同的屬性選擇參數不同的核函數，如根據不同的屬性可以選擇高斯核函數的不同寬度;二是針對不同的屬性選擇不同種類的核函數，如根據不同的屬性可以在學習過程中同時選擇高斯核函數和多項式核函數。使用多個核函數的組合，即使不知道最優參數，也可以通過調整權值找到最合適的參數，顯然使用多個核函數的組合要比單個核函數的魯棒性更強。

1.3 模型選擇

支持向量機分類和回歸的性能離不開選擇一組好的參數，即模型的選擇。模型選擇包括核函數類型的選擇、懲罰因子C的選擇、損失函數的選擇以及與核函數有關的參數(如RBF核函數的寬度參數，多項式核函數的階)選擇。

目前，參數問題策略主要有兩種:一是通過測試非訓練樣本在某個固定參數上的錯誤率，然后尋找最優的參數。二是確定學習方法錯誤率的上界，根據錯誤率的上界盡可能小來進行參數的選擇。最常用的參數優化方法有交叉驗證技術(Cross－Validation Technique)。k折交叉驗證就是首先將訓練集隨機地分成k個互不相交的子集，每個折的大小大致相等，利用k－1個訓練子集，對給定的一組參數建立模型，利用剩下的最后一個子集的均方差評估參數的性能。重復以上過程k次，然后根據k次迭代后得到的均方差的平均值來估計期望泛化誤差，最后選擇一組最優的參數。

當k等于訓練樣本數時，每次迭代只有一個樣本作為測試，因此稱為留一法(Leave－One－Out)。也有許多研究者提出了許多其它的選擇方法，如核校準方法(Kernel Alignment)［38］。

2 生物信息學中的核方法

生物信息學(Bioinformatics)［39］是一個融合了多個學科的領域，包含了分子生物學(如:生物化學、遺傳學、結構生物學等)、計算機科學(計算機理論、人工智能、機器學習等)、物理化學和數學(算法建模概率論統計學等)。目前，生物信息學已經成為生物醫學、農學、遺傳學、細胞生物學等學科發展的強大推動力量，也是藥物設計、環境監測的重要組成部分。其不僅具有重大的理論價值，而且具有巨大的應用價值［40］。

生物信息學中，常用的數據類型是各種長度的字符串。生物序列通常被表示成由有限的字符組成的字符串。例如:利用它們可以把蛋白質表示成氨基酸序列，把基因組DNA表示成核苷酸序列，近年來，許多研究人員已經對這種類型的數據進行了了大量的研究。

作為最典型的核方法支持向量機在生物信息學中的應用是相當廣泛的，目前主要應用于以下幾個方面:蛋白質分類［41，42］、蛋白質結構的預測［43］和微陣列基因表達數據分析［44］。

在生物信息學中，可結合背景知識設計出高效率的核函數。字符串核(String Kernel)是針對變長序列數據定義核函數。結合生物信息的背景知識，如果兩個序列同時分享共同的子序列，則這兩個序列的相關或相似性高的基本思想，Leslie等人［45，46］定義了一種字符串核(Spectrum Kernel)，可以用于蛋白質的分類，其限制條件是不允許字符串之間有間隔，即其相似性量測長度定義為必須完全相同的共同子區域。費氏核(Fisher kernels)是由Jaakkola等人［47］提出的，其將隱馬可夫模型(Hidden Markov Models)與支持向量機相結合，基于領域內的背景知識所設計的核函數，它允許在部分信息缺損的情況下，可以進行檢測。此法用于蛋白質之間同源相關性的比較，取得了較好的結果。配對比較核 (Pairwise Comparison Kernels)［48］是假設分子的演化主要是通過突變和少量的插入及刪除而來，其通過序列的比對，來衡量兩個類中對象的相似性，求得一個相似分數，用來構造的核稱為配對比較核。

3 結論

本文對核方法的基本原理、常用的核方法和核函數進行了詳細的介紹，同時指出了目前核方法的一些研究熱點。核方法的研究雖然取得了很多成果，廣泛地應用到許多領域。但是仍然存在許多問題需要進一步的深入研究。隨著核理論的不斷完善和核方法的不斷改進，其應用領域也將不斷拓展。

［1］Vapnik V.The Nature of Statistical Learning Theory［M］.New York:Springer Veriag，1995

［2］Mecer J.Functions of positive and negative type and their connection with the theory of integral equations［J］.Philos.Trans.，Roy.Soc.，London，1909，20(9):415－446

［3］Aronszajn N.Theory of reproducing kernels［J］.Trans Amer.Math.Soc，2001，12(4):765－775

［4］Aizerman.Theoretical foundations of the potential function method in pattern recognition learning［J］.Automation and remote control，1964，25:821－837

［5］Vapnik V N.An overview of statistical learning theory［J］.IEEE Transactions on Neural Networks，1999，10(5):988－999

［6］Sch.lkopf B.Nonlinear component analysis as a kernel eigenvalue problem［J］.Neural Computation，1998，10(5):1229－1319

［7］Mika S，Ratsch G，Weston J，et al.Fisher discriminant analysis with kernels［M］.Hu，Y.H.et al.editors.Neural Networks for Signal Processing，1999，41－48

［8］Girolami M.Mercer kernel based clustering in feature space［J］.IEEE Transactions on Neural Networks，2002，13(3):780－794

［9］Vapnik V N.Statistical Learning Theory［M］.New York:Join Wiley and Sons，1998

［10］Weston J.Watkins C.Multi－class Support Vector Machines［R］.Technical Report，CSD－TR－98－04，May 1998，Department of Computer Science，Royal Holloway University of London，England

［11］Platt J C，Cristianini N，Shawe－Taylor J.Large margin DAGs for multiclass classification［C］.In:Neural Information Processing Systems，1999

［12］Syed N A，Liu H，Sung K K.Incremental Learning with Support Vector Machines［C］.International Joint Conference on Artificial Intelligence，1999

［13］Cortes C，Vapnik V.Support－vector Networks［J］.Machine Learning，1995，20(3):273－297

［14］Osuna E，Girosi G.Reducing run－time complexity in SVMs［A］.In:Proceedings of the 14th International Conf.On Pattern Recognition，Brisbane，Australia，1998

［15］Osuna E，Freund R，Girosi G.Improving training algorithm for support vector machines［J］.Proc.IEEE NNSP＇97.Amelia Island，1997:24－26

［16］Platt J C.Sequential minimal optimization:A fast algorithm for training support vector machines［R］.Technical Report MSR－TR－98－14，Microsoft Research，1998

［17］Rosipal R，Trejo L J，Cichocki A.Kernel principal component regression with em approach to nonlinear principal components extraction［R］.Technical report，2000

［18］Bach F R，Jordan M I.Kernel Independent Component Analysis［J］.Journal of Machine Learning Research，2002，3:1－48

［19］Carl G，Peter S.Model selection for support vector machine classification［J］.Neurocomputing，2003，55(1－2):221－249

［20］Chapelle O，Vapnik V，Bousquet O，et al.Choosing Multiple Parameters for support vector machines［J］.Machine Learning，2002，46(1－3):131－159

［21］Cristianini N，Shawe－Taylor J，Campbell C.Dynamically adapting kernels in support vector machines［M］.Advances in Neural Information Processing Systems，MIT Press，1998，11

［22］Joachims T.Text categorization with support vector machines［C］.In:Proceedings of European Conference on Machine Learning，1998

［23］Mu S M，Tian S F.Yin C H.Using Length－weighted Once Kernel to Detect Anomalous Process［C］.International Conference on Natural Computation，2007，692－696

［24］G rtner T，Lloyd J W，Flach P A.Kernels and Distances for Structured Data［J］.Machine Learning，2004，57:205－232

［25］Barzilay O，Brailovsky V L.On domain knowledge and feature selection using a support vector machine［J］.Pattern Recognition Letters，1999，20:475－484

［26］Lodhi H，Saunders C，Shawe－Taylor J，et al.Text Classification using String Kernels［J］.Journal of Machine Learning Research，2001，2:419－444

［27］Tsuda K，Kin T，Asai K.Marginalized kernels for biological sequences［J］.Bioinformatics，2002，18:268－275

［28］G rtner T.A survey of kernels for structured data［J］.SIGKDD Explorations，2003

［29］Barzilay O，Brailovsky V L.On domain knowledge and feature selection using a support vector machine［J］.Pattern Recognition Letters，1999，20:475－484

［30］Haussler D.Convolution kernels on discrete structures［R］.Technical Report，Department of Computer Science，University of California at Santa Cruz，1999

［31］Leslic C，Eskin E，Noble W S.The spectrum kernel:a string kernel for SVM protein classification［C］.In:Proceedings of the Pacific Symposium on Biocomputing，2002，564－575

［32］Collins M.Duffy N.Convolution kernels for natural language［C］.In:Neural Information rocessing stems，NIPS 14，2001，http://citeseer.nj.nec.com/542061.html

［33］Kondor R I，Lafferty J.Diffusion kernels on graphs and other discrete structures［C］.In:Sammut，C.＆ Hoffmann，A.editors.Proceedings of the 19th International Conference on Machine Learning，Morgan Kaufmann，2002，315－322

［34］Sonnenburg S，Ratsch G，Schafer C.A general and efficient multiple kernel learning algorithm［C］.In:Advances in Neural Information Processing Systems，2006

［35］Sonnenburg S，R tsch G，Sch fer C，et al.Large Scale Multiple Kernel Learning［J］.Journal of Machine Learning Research，2006，7:1531－1565

［36］Ratsch G，Sonnenburg S.Learning Interpretable SVMs forBiologicalSequenceClassification［J］.BCM Bioinformatics，2004，7(1):S9

［37］Theodoros Damoulas and Mark A.Probabilistic multi－class multi－kernel learning on protein fold recognition and remote homology detection［J］.Bioinformatics，2008，24:1264－1270

［38］Cristianini N，Shawe Taylor J，Kandola J，et al.On kernel target alignment［C］.In:Proc.Neural Information Processing Systems.Cambridge，A:MIT Press，2002:367－373

［39］周海廷.信息與控制［J］.機器學習與生物信息學，2003，32(4):352－357

［40］張春霆.生物信息學的現狀與進展［J］.世界科技研究與發展，2000，22(6):20－23

［41］劉 青，楊小濤.基于支持向量機的微陣列基因表達數據分析方法［J］.小型微型計算機系統，2005，26(3):363－366

［42］C Leslie，E.Eskin and W S Noble.The spectrum kernel:a string kernel for svm protein classi_cation.Russ B.Altman，A.Keith Dunker，Lawrence Hunter，Kevin Lauerdale，Teri E.Klein，Proceedings of the Paci_c Symposium on Biocomputing，2002，564－575

［43］S Hua and Z Sun.A novel method of protein secondary structure prediction with high segment overlap measure:Support vector machine approach［J］.Journal of Molecular Biology，2001，308(2):397－407

［44］LIUQing，YANG Xiao－tao.Microarray Gene Expression Data Anlysis Based on Support Vector machine［J］，Mini－Micro Systems，2005，26(3):363－366

［45］Leslie C，E Eskin，J Weston，et al.Mismatch string kernels for SVM protein classification，Advances in Neural Information Processing Systems［C］.MIT Press，2003

［46］Leslie，C.，E Eskin.The spectrum kernel:A string kernel for SVM protein classiffiation.In:Proceedings of the Paciffic Symposium on Biocomputing.Noble，2002

［47］Jaakkola T，M Diekhans，D Haussler.A discrimitive framework for detecting remote protein homologies［J］.Journal of Computational Biology，2000，7(1):95－114

［48］Liao L，W S Noble.Combining pairwise sequence similarity and support vector machines for remote protein homology detection［C］.In:Proceedings of the Sixth Annual International Conference on Computational Molecular Biology，2002，225－232

［49］Guanghui Song，Xiaogang Jin，Genlang Chen.Multiple Kernel Learning Method for Network Anomaly Detection International Conference of Intelligent systems and knowledge Engineering，2010，296－299