可拓支持向量分類機

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

（1. 北京聯合大學 教務處，北京 100101; 2. 北京聯合大學 基礎部，北京 100101; 3. 中國科學院 虛擬經濟與數據科學研究中心，北京 100190; 4. 浙江大學寧波理工學院 管理學院，浙江 寧波 315100）

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

可拓數據挖掘[1-6]是將可拓學的理論和方法[7-8]與挖掘數據的方法、技術相結合的一門新技術。它在發現事物的類別轉化以及識別潛在的變換知識等方面有著廣闊的應用前景。

本文吸取了可拓學尋找變換知識的思想，考慮事物的某種性質的變化所帶來的問題轉化，結合當前已經非常成熟的支持向量機模型，從而提出了可拓支持向量機這一新的可拓數據挖掘新方法。

1 支持向量機

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

標準的兩類分類問題為：給定訓練集

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

基于結構風險最小化原則，SVM構造出的線性分類機的原始最優化問題為

算法1 SVM

輸入 輸入訓練集(見(1)式)；

輸出 分劃超平面以及決策函數。

2) 構造并求解凸二次規劃問題：

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

2 可拓支持向量機

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

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

可拓變量集合 由全體可拓變量構成的集合則稱為可拓變量集合，記為E。

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

可拓分類問題 給定訓練集

式中： xi∈,[xi]j,j∈ E，可在某個區間內變化， yi∈={1,?1},i=1,2,···,l。 基于此，在空間上尋找一個實值函數，得到決策函數：

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

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

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

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

注意，與標準的兩類分類問題不同，這里除了給出標準的訓練集外，還給出了每個點的可拓變量區間。據此可以構建算法2：可拓SVM1。

算法2 可拓SVM1

輸入 輸入訓練集(見式(1))；

輸出 決策函數。

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

3) 計算最優超平面參數:

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

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

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

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

可以看出，這時候訓練點的輸入就不再是一個點，而是一個集合。如果限定該集合是一個凸集，比如為一個球體，則訓練集變為

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

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

算法3 可拓SVM2

輸入 輸入訓練集(見式(8))；

輸出 決策函數。

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

2) 構造并求解二階錐規劃：

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

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

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

3 結束語

本文提出了一種新的分類方法——可拓支持向量機，可拓支持向量機在進行分類預測時較標準的支持向量分類機有所不同，它更注重于找到那些通過變化特征值而轉換類別的樣本。文中給出了可拓變量和可拓分類問題的定義，并構建了求解可拓分類問題的兩種算法。基于此模型，我們可以在理論和方法上做一系列研究。理論上，包括對其相應的統計學習理論基礎研究，可拓決策函數集的VC維估計，推廣能力的上界估計，可拓結構風險的實現原理等；方法上，包括如何在標準的支持向量機模型中引入關聯函數，構造可拓的核函數，對其相應的大規模最優化問題的快速求解算法，模型參數選擇問題等。

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

[2]楊春燕, 蔡文. 可拓工程[M]. 北京: 科學出版社, 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]李立希, 李鏵汶, 楊春燕. 可拓學在數據挖掘中的應用初探[J]. 中國工程科學, 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]陳文偉, 黃金才. 從數據挖掘到可拓數據挖掘[J]. 智能技術, 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]楊春燕, 蔡文. 可拓數據挖掘研究進展[J]. 數學的實踐與認識, 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]. 北京: 科學出版社,2003.CAI Wen, YANG Chunyan, HE Bin. Extension logic[M].Beijing: Science Press, 2003.

[8]蔡文, 楊春燕, 林偉初. 可拓工程方法[M]. 北京: 科學出版社, 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.