基于支持向量數(shù)據(jù)描述算法的ＳＶＭ多分類新方法

摘要：提出一種基于支持向量數(shù)據(jù)描述算法(SVDD)的多分類方法（S－MSVM）。受SVDD的啟發(fā)，該方法對每類樣本建立一個超球來界定，但訓練好的超球在所有情況下都是相交的。選擇相交區(qū)域的樣本單獨建立超球，重復該步驟，直到相交區(qū)域消失或相交區(qū)域內沒有樣本點。給出了該方法的時間復雜度分析，并通過實驗驗證了該方法具有相對較好的訓練精度。

關鍵詞：支持向量數(shù)據(jù)描述算法； 支持向量機多分類； 分類器

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)11-0046-03

支持向量機[1](support vector machine，SVM)最初是針對兩分類問題的，不能直接用于多分類問題。實際的模式識別問題絕大多數(shù)都是多分類問題，所以需要進行推廣和改進。近些年來很多研究人員也提出了一些解決多分類問題的方法，包括一對多方法及一對一方法、層（樹）分類方法、k類SVM方法和DDAG(決策有向無環(huán)圖)方法。這些方法各有利弊。一對多方法的訓練時間與類別數(shù)量成正比，存在不可分區(qū)域；一對一方法需要建立k(k-1)/2個分類器，計算量龐大；層分類方法同樣需要求解很多二次規(guī)劃問題；k類SVM方法要一次處理所有的數(shù)據(jù)，約束條件急劇增加，進行分類的二次規(guī)劃十分龐大，數(shù)據(jù)的規(guī)模受限；DDAG方法未考慮樣本不平衡數(shù)據(jù)對分類速度的影響而且沒有考慮分類錯誤傳遞對后續(xù)產生的影響。這幾種多分類方法的對比可參看文獻[2]。

數(shù)據(jù)描述是學習機根據(jù)目標集的數(shù)據(jù)獲得關于目標集的描述，主要用來檢測新的樣本是否與目標集的描述相似。如果相似則被目標集接受；否則該樣本就是outlier或novelty。D. Tax等人[3]以支持向量分類器為基礎提出了支持向量數(shù)據(jù)描述算法(support vector data description)。這種方法能夠圍繞目標類數(shù)據(jù)建立支持向量描述模型——包含目標類數(shù)據(jù)的超球體，將目標類與所有離群類分開。

受到SVDD思想的啟發(fā)，對每一類樣本單獨使用SVDD算法，得到各個類別樣本的超球，并以此超球作為分類邊界。但訓練好的SVM超球的間隙寬度在所有情況下均為0，而SVM的基本思想就是要最大化間隙寬度，SVDD的目標函數(shù)中也沒有出現(xiàn)間隔最大這個條件，所以不能保證其具有良好的推廣能力。本文通過對相交區(qū)域的樣本點重復使用SVDD算法來提高其訓練精度，也通過理論和實驗證明了其時間復雜度并不比其他方法高。

1SVDD簡介

1．1SVDD算法

SVDD[3]的基本思想（圖1）是把要描述的對象作為一個整體，建立一個封閉而緊湊的超球體，使得描述的對象全部或盡可能多地包在這個球體內，而非該類對象沒有或盡可能少地落入該球體內。

假設訓練樣本中包含N個目標樣本{xi，i=1，…，N}。SVDD的思想是尋找一個能夠包含所有樣本的最小邊界球，并以此超球作為其分類邊界。所尋找的最小邊界球S用半徑R和球心a來描述。需要解決如下這個約束優(yōu)化問題：

事實上，訓練好的M個超球在所有情況下都是相交的，即總有部分點處于相交區(qū)域。如果測試樣本落入相交區(qū)域，如何判斷這個點處于哪個類別就是一個非常關鍵的問題。基本的決策是落入相交區(qū)域的點到哪個類別球的相對距離(即到該球球心的距離與該球半徑的比值)較小就分到哪個類別。這種決策規(guī)則考慮了球的大小，但忽略了樣本分布的稀疏程度，因為大球不一定囊括更多的樣本點；若決策規(guī)則將靠近超球球心的更多的測試樣本分給密度更大的超球，雖然考慮到超球內樣本分布的稀疏程度，但仍然都是依據(jù)直觀的想象來進行分類，而未考慮相交區(qū)域內的樣本分布。

本文提出的多分類方法針對相交區(qū)域的樣本點，單獨考慮這些點，重新使用SVDD算法建立不同類別的超球。若這些超球仍然相交，重復此過程，直到相交區(qū)域消失或相交區(qū)域內沒有樣本點。這種方法避免了對相交區(qū)域內樣本點的盲目決策，解決了由于對相交區(qū)域內樣本點化分錯誤引起的泛化能力低的問題。該方法簡稱為S－MSVM(基于SVDD的SVM多分類算法)。具體的算法步驟如下：

a)對各類樣本單獨使用SVDD算法，得到各類樣本的球心和半徑；

b)選擇不同類別超球之間相交區(qū)域的點；

c)對相交區(qū)域的各類點單獨再次使用SVDD算法；

d)重復步驟b) c)直到?jīng)]有點在相交區(qū)域或者相交區(qū)域不存在。

通過這種方法，測試樣本能夠被很好地劃分，而且該方法的時間復雜度并不比一對一方法高(下面有證明)。對一個給定的多分類問題，相交區(qū)域的樣本點經(jīng)過有限步驟之后有下面兩種情況：

（a）相交區(qū)域沒有或者只有一類樣本點。這時把落入相交區(qū)域的樣本點全部歸為一類。

（b）相交區(qū)域有兩類或者更多類別的樣本點。相交區(qū)域的點使用SVDD算法建立超球，重復此過程直到相交區(qū)域沒有樣本點或任意兩個超球不相交。

3S－MSVM的時間復雜度分析

SVDD算法解決一個二次規(guī)劃問題，具有重要的計算優(yōu)勢，其時間復雜度為O(N3)。這里N為訓練樣本的數(shù)目。對一個M類（M>2）分類問題，l為樣本的總數(shù)目。假設不同類別的訓練樣本數(shù)目是均衡的。用T來表示時間復雜度。

5結束語

S－MSVM的學習思想與仿生模式識別類似，都是一類分別訓練“認識”的，對新增加樣本的訓練不會影響原有識別知識。S－MSVM的決策方法在不增加計算量的情況下解決了各類超球相交區(qū)域的樣本識別問題，已經(jīng)通過實驗來證明了這一點。但這種方法沒有在理論上給出泛化誤差的上界，這方面的研究有待于進一步深入。

參考文獻：

［1］VAPNIK V N. The nature of statistical learning theory[M]. New York: Wiley，1998.

［2］HSU C W， LIN C J. A comparison of methods for multiclass support vector machines[J]. IEEE Trans on Neural Networks， 2002，13(2):415-425.

［3］TAX D， DUIN R. Data domain description using support vectors[C]//Proc of the European Symposium on Artifical Neural Networks. 1999:251-256.

［4］TAX D M J， DUIN R P W. Support vector domain description[J].Pattern Recognition Letters，1999，20(11－13):1191－1199.

［5］BURGES C J C. A tutorial on support vector machines for pattern recognition[J]. Data Mining and Knowledge Discovery，1998，2(2):121－167.

［6］BLAKE C L，MERZ C J. UCI machine learning repository［EB/OL］. [2006-05-01].http://www.ics.uci.edu/~mlearn/MLRepository.html.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”