可拓支持向量分類機

陳曉華，劉大蓮，田英杰，李興森

（1. 北京聯(lián)合大學(xué) 教務(wù)處，北京 100101; 2. 北京聯(lián)合大學(xué) 基礎(chǔ)部，北京 100101; 3. 中國科學(xué)院 虛擬經(jīng)濟與數(shù)據(jù)科學(xué)研究中心，北京 100190; 4. 浙江大學(xué)寧波理工學(xué)院 管理學(xué)院，浙江 寧波 315100）

隨著社會的進(jìn)步，科學(xué)技術(shù)的飛速發(fā)展，當(dāng)今各種社會生產(chǎn)活動中每時每刻都在產(chǎn)生大量的數(shù)據(jù)信息，而隨著計算機技術(shù)的不斷進(jìn)步，互聯(lián)網(wǎng)的出現(xiàn)使得全球數(shù)據(jù)共享成為現(xiàn)實，從而全面進(jìn)入了大數(shù)據(jù)時代。因此如何將海量數(shù)據(jù)進(jìn)行充分有效地挖掘和利用從而指導(dǎo)社會生產(chǎn)是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的核心任務(wù)。數(shù)據(jù)挖掘是20世紀(jì)80年代后期出現(xiàn)的一類數(shù)學(xué)、計算機和管理等多學(xué)科相結(jié)合的交叉科學(xué)。其旨在從海量數(shù)據(jù)中識別、提取有效的、新穎的甚至潛在有用的以及最終可被識別、理解的知識，從而作為管理決策者進(jìn)行決策的科學(xué)決策依據(jù)。數(shù)據(jù)挖掘作為一個熱門研究領(lǐng)域，涉及的新方法有神經(jīng)網(wǎng)絡(luò)、決策樹、隨機森林、支持向量機、深度學(xué)習(xí)等。

可拓數(shù)據(jù)挖掘[1-6]是將可拓學(xué)的理論和方法[7-8]與挖掘數(shù)據(jù)的方法、技術(shù)相結(jié)合的一門新技術(shù)。它在發(fā)現(xiàn)事物的類別轉(zhuǎn)化以及識別潛在的變換知識等方面有著廣闊的應(yīng)用前景。

本文吸取了可拓學(xué)尋找變換知識的思想，考慮事物的某種性質(zhì)的變化所帶來的問題轉(zhuǎn)化，結(jié)合當(dāng)前已經(jīng)非常成熟的支持向量機模型，從而提出了可拓支持向量機這一新的可拓數(shù)據(jù)挖掘新方法。

1 支持向量機

支持向量機(support vector machine, SVM)[9-18]是一種通用的、有效的機器學(xué)習(xí)算法，主要建立在統(tǒng)計理論(statistical learning theory, SLT)、最優(yōu)化理論及核理論的三大理論基礎(chǔ)之上。以分類問題為例，SVM首先把輸入映射到某一個高維的特征空間中，利用統(tǒng)計學(xué)習(xí)理論中的結(jié)構(gòu)風(fēng)險最小化原則把分類問題轉(zhuǎn)化為一個凸二次規(guī)劃問題來解決；然后利用最優(yōu)化理論中的對偶理論，得到該凸規(guī)劃的對偶問題，使得引入核函數(shù)成為可能；最后再利用核理論來處理非線性分類的情況。與數(shù)據(jù)挖掘中的其他方法相比，SVM理論相對完備，較好地解決了其他方法中經(jīng)常出現(xiàn)的一些棘手問題。隨著科學(xué)技術(shù)的進(jìn)步和完善，支持向量機的研究也更為深入廣泛，許多新的理論、算法層出不窮，應(yīng)用領(lǐng)域更為廣闊。

標(biāo)準(zhǔn)的兩類分類問題為：給定訓(xùn)練集

以便推斷任意x對應(yīng)的輸出y。若 g(x)是線性函數(shù)g(x)=(w·x)+b ，則式(2)對應(yīng)著用超平面(w·x)+b=0將空間 Rn分成兩部分，稱為線性分類機。

基于結(jié)構(gòu)風(fēng)險最小化原則，SVM構(gòu)造出的線性分類機的原始最優(yōu)化問題為

算法1 SVM

輸入 輸入訓(xùn)練集(見(1)式)；

輸出 分劃超平面以及決策函數(shù)。

2) 構(gòu)造并求解凸二次規(guī)劃問題：

算法1為針對線性分類問題的SVM算法，事實上在很多實際問題中，分類問題并不能被線性分劃。這時需引入從空間到Hilbert空間的變換，將訓(xùn)練集變換到特征空間并在該空間執(zhí)行算 法1， 相 應(yīng) 地 ，轉(zhuǎn) 化 為 (Φ(xi),Φ(xj))， 而(Φ(xi),Φ(xj))的計算可以通過引進(jìn)核函數(shù)K(x,x′)=(Φ(x),Φ(x′))代替計算。通常，常用的核函數(shù)有RBF核函數(shù)、多項式核函數(shù)、B樣條核函數(shù)等。

2 可拓支持向量機

在實際問題中，我們不僅關(guān)注對未知樣本的類別預(yù)測，更關(guān)心已有類別或被預(yù)測了類別的樣本能否轉(zhuǎn)化到相反的類別，在什么條件下會轉(zhuǎn)化，所付出的代價有多大。這些在可拓學(xué)里被稱為變換的知識。挖掘這些變換的知識的一個途徑，就是找到那些可以變換的特征或變量。以疾病的輔助診斷為例，患者患有疾病的相關(guān)特征(變量)有很多，比如性別、年齡、身高、體重、血壓(低壓)、膽固醇、血常規(guī)等，這些變量中，對某個患者來說，其性別就是不可變換的變量，而血壓則可以通過吃藥等治療手段變高或變低。那么在解決疾病輔助診斷的分類問題時，我們一方面希望決策函數(shù)能準(zhǔn)確地預(yù)測未知樣本的類別，另一方面希望這個決策函數(shù)能找到那些可以互相轉(zhuǎn)換類別的樣本，這樣就可以找到更多的變換的知識。首先給出以下定義。

可拓變量 若向量 x=([x]1,···,[x]n)中分量的值可以變化，則稱 [ x]j為可拓變量。

可拓變量集合 由全體可拓變量構(gòu)成的集合則稱為可拓變量集合，記為E。

可拓變量區(qū)間 可拓變量 [x]j的值所變化的區(qū)間 [aj,bj]稱為可拓變量區(qū)間。

可拓分類問題 給定訓(xùn)練集

式中： xi∈,[xi]j,j∈ E，可在某個區(qū)間內(nèi)變化， yi∈={1,?1},i=1,2,···,l。 基于此，在空間上尋找一個實值函數(shù)，得到?jīng)Q策函數(shù)：

以便推斷任意x對應(yīng)的輸出y，并判斷其是否可以變換為相反的輸出–y。

可拓樣本 若樣本點x可以通過改變某個或某些可拓變量的值而改變類別標(biāo)號，則稱x為可拓樣本。

下面給出可拓分類問題示意性的例子。圖1中給出了兩類點，分別用▲和■表示，分量為可拓變量。圖1(a) 所示的是所有點的可拓變量區(qū)間均滿足 [x]2∈[a,b]的情況，即所有點被上下兩條直線[x]2=a 和 [x]2=b所控制；圖1(b) 所示的是每個點的可拓變量區(qū)間不同的情況，即滿足，在圖中就是每個點分別被雙箭頭線段所控制。

圖 1 可拓分類問題Fig. 1 Extension classification problem

注意，與標(biāo)準(zhǔn)的兩類分類問題不同，這里除了給出標(biāo)準(zhǔn)的訓(xùn)練集外，還給出了每個點的可拓變量區(qū)間。據(jù)此可以構(gòu)建算法2：可拓SVM1。

算法2 可拓SVM1

輸入 輸入訓(xùn)練集(見式(1))；

輸出 決策函數(shù)。

1) 輸入訓(xùn)練集(見式(1))，并選擇合適的懲罰參數(shù) C ＞0。

3) 計算最優(yōu)超平面參數(shù):

5) 對輸入 xk, 首先用決策函數(shù) f(xk)得到其對應(yīng)的預(yù)測類別yk，然后用其可拓變量對應(yīng)的可拓區(qū)間和分別代替，這樣對個可拓變量，會得到2|E|個不同的組合值，相應(yīng)的，我們基于xk得到了2|E|個新的輸入，分別用決策函數(shù)來判斷，若有一個被判斷為-yk，則認(rèn)為該輸入是可變換的。

對圖1(a) 所示的例子，可以用算法2得到圖2(a) 所示的分劃線，因該問題的可拓變量區(qū)間為定值，所以可以直接得到兩條垂直的線，在這兩條垂直線中間的點都是可拓樣本(用圓圈標(biāo)注)，并用箭頭表示該樣本在可拓變量的變化方向。對圖1(a)所示的例子，用算法2得到圖2(b) 所示的分劃線，可以看出沒有可拓樣本點，即沒有點可以通過可拓變量的區(qū)間變化來達(dá)到類別標(biāo)號的改變。

圖 2 可拓分類SVMFig. 2 Extention classification SVM

進(jìn)一步，考慮稍微復(fù)雜的情況，若對上述的可拓分類問題，增加了先驗知識。該先驗知識為：在給定的訓(xùn)練集S中，訓(xùn)練點xi的可拓變量

可以看出，這時候訓(xùn)練點的輸入就不再是一個點，而是一個集合。如果限定該集合是一個凸集，比如為一個球體，則訓(xùn)練集變?yōu)?/p>

式中輸入集合Xi是一個以Xi為球心、以ri為半徑的球體,。那么該分類問題就轉(zhuǎn)化為魯棒支持向量機所求解的問題[15]，此時構(gòu)造的原始最優(yōu)化問題為

因為約束式(10)含有無窮多個約束，一般做法是把它轉(zhuǎn)化成一個僅含有有限個約束的問題，并求解相應(yīng)的對偶問題[15]，據(jù)此構(gòu)造可拓SVM2，見算法3。

算法3 可拓SVM2

輸入 輸入訓(xùn)練集(見式(8))；

輸出 決策函數(shù)。

1) 輸入訓(xùn)練集(見式(8))，并選擇合適的懲罰參數(shù) C ＞0。

2) 構(gòu)造并求解二階錐規(guī)劃：

4) 對輸入xk, 首先用決策函數(shù) f(xk)得到其對應(yīng)的預(yù)測類別yk，然后在其可拓變量對應(yīng)的可拓區(qū)間內(nèi)隨機取值m次，這樣對個可拓變量，會得到個不同的組合值，相應(yīng)的，基于xk得到了個新的輸入，分別用決策函數(shù)來判斷，若有一個被判斷為–yk，則認(rèn)為該輸入是可變換的。

如果先驗知識為：在給定的訓(xùn)練集S中，訓(xùn)練點xi的可拓變量在可拓區(qū)間內(nèi)變化時，其 yi產(chǎn)生了變化，如圖 3(b)所示。均為可拓變量，每個點的可拓區(qū)間為不同大小的矩形，白色為正類，黑色為負(fù)類。而黑白相間的矩形則為點在這些區(qū)間內(nèi)變化時，類別發(fā)生了變化。這時問題就變得復(fù)雜，需要引入可拓集的概念和關(guān)聯(lián)函數(shù)來處理，這是進(jìn)一步的研究方向。并且還可以將其拓展到應(yīng)用廣泛的多示例、多標(biāo)簽學(xué)習(xí)等方面[19-22]。

圖 3 可拓分類SVMFig. 3 Extension classification SVM

3 結(jié)束語

本文提出了一種新的分類方法——可拓支持向量機，可拓支持向量機在進(jìn)行分類預(yù)測時較標(biāo)準(zhǔn)的支持向量分類機有所不同，它更注重于找到那些通過變化特征值而轉(zhuǎn)換類別的樣本。文中給出了可拓變量和可拓分類問題的定義，并構(gòu)建了求解可拓分類問題的兩種算法。基于此模型，我們可以在理論和方法上做一系列研究。理論上，包括對其相應(yīng)的統(tǒng)計學(xué)習(xí)理論基礎(chǔ)研究，可拓決策函數(shù)集的VC維估計，推廣能力的上界估計，可拓結(jié)構(gòu)風(fēng)險的實現(xiàn)原理等；方法上，包括如何在標(biāo)準(zhǔn)的支持向量機模型中引入關(guān)聯(lián)函數(shù)，構(gòu)造可拓的核函數(shù)，對其相應(yīng)的大規(guī)模最優(yōu)化問題的快速求解算法，模型參數(shù)選擇問題等。

[1]蔡文, 楊春燕, 陳文偉, 等. 可拓集與可拓數(shù)據(jù)挖掘[M]. 北京: 科學(xué)出版杜, 2008.CAI Wen, YANG Chunyan, CHEN Wenwei, et al. Extension set and extension data mining[M]. Beijing: Science Press, 2008.

[2]楊春燕, 蔡文. 可拓工程[M]. 北京: 科學(xué)出版社, 2007.YANG Chunyan, CAI Wen. Extension engineering[M].Beijing: Science Press, 2007.

[3]CAI Wen. Extension theory and its application[J]. Chinese science bulletin, 1999, 44(17): 1538–1548.

[4]李立希, 李鏵汶, 楊春燕. 可拓學(xué)在數(shù)據(jù)挖掘中的應(yīng)用初探[J]. 中國工程科學(xué), 2004, 6(7): 53–59.LI Lixi, LI Huawen, YANG Chunyan. Study on the application of extenics in data mining[J]. Engineering science,2004, 6(7): 53–59.

[5]陳文偉, 黃金才. 從數(shù)據(jù)挖掘到可拓數(shù)據(jù)挖掘[J]. 智能技術(shù), 2006, 1(2): 50–52.CHEN Wenwei, HUANG Jincai. From data mining to extension data mining[J]. Intelligent technology, 2006, 1(2):50–52.

[6]楊春燕, 蔡文. 可拓數(shù)據(jù)挖掘研究進(jìn)展[J]. 數(shù)學(xué)的實踐與認(rèn)識, 2009, 39(4): 136–141.YANG Chunyan, CAI Wen. Recent progress in extension data mining[J]. Mathematics in practice and theory, 2009,39(4): 136–141.

[7]蔡文, 楊春燕, 何斌. 可拓邏輯初步[M]. 北京: 科學(xué)出版社,2003.CAI Wen, YANG Chunyan, HE Bin. Extension logic[M].Beijing: Science Press, 2003.

[8]蔡文, 楊春燕, 林偉初. 可拓工程方法[M]. 北京: 科學(xué)出版社, 1999.CAI Wen, YANG Chunyan, LIN Weichu. Extension engineering methods[M]. Beijing: Science Press, 1999.

[9]CORTES C, VAPNIK V. Support-vector networks[J]. Machine learning, 1995, 20(3): 273–297.

[10]CRISTIANINI N, SHAWE-TAYLOR J. An introduction to support vector machines and other kernel-based learning methods[M]. Cambridge: Cambridge University Press,2000.

[11]VAPNIK V N. Statistical learning theory[M]. New York:John Wiley and Sons, 1998.

[12]NOBLE W S. Support vector machine applications in computational biology[M]//SCH?ELKOPF B, TSUDA K,VERT J P. Kernel Methods in Computational Biology.Cambridge: MIT Press, 2004.

[13]ADANKON M M, CHERIET M. Model selection for the LS-SVM. application to handwriting recognition[J]. Pattern recognition, 2009, 42(12): 3264–3270.

[14]TIAN Yingjie, SHI Yong, LIU Xiaohui. Recent advances on support vector machines research[J]. Technological and economic development of economy, 2012, 18(1): 5–33.

[15]DENG Naiyang, TIAN Yingjie, ZHANG Chunhua. Support vector machines: optimization based theory, algorithms, and extensions[M]. Boca Raton: CRC Press,2013.

[16]HUANG Kaizhu, YANG Haiqin, KING I, et al. Learning large margin classifiers locally and globally[C]//Proceeding of the 21st International Conference on Machine Learning. Banff, Alberta, Canada, 2004.

[17]SHAWE-TAYLOR J, CRISTIANINI N. Kernel methods for pattern analysis[M]. Cambridge: Cambridge University Press, 2004.

[18]BORGWARDT K M. Kernel methods in bioinformatics[M]//LU H H S, SCH?LKOPF B, ZHAO Hongyu. Handbook of Statistical Bioinformatics. Berlin, Heidelberg:Springer, 2011: 317–334.

[19]VAPNIK V, IZMAILOV R. Learning using privileged information: Similarity control and knowledge transfer[J].Journal of machine learning research, 2015, 16: 2023–2049.

[20]SUN S. A survey of multi-view machine learning[J]. Neural computing and applications, 23(7): 2031–2038.

[21]CHEPLYTGINA V, TAX, D M, LOOG M. Multiple instance learning with bag dissimilarities[J]. Pattern recognition, 2015, 48(1): 264–275.

[22]CARBONNEAU M A, GRANGER E, RAYMOND A J, et al. Robust multiple-instance learning ensembles using random subspace instance selection[J]. Pattern recognition,2016, 58: 83–99.