核向量機(jī)算法研究及應(yīng)用

許 敏

（無錫職業(yè)技術(shù)學(xué)院電子與信息技術(shù)學(xué)院，江蘇 無錫 214121）

核向量機(jī)算法研究及應(yīng)用

許 敏

（無錫職業(yè)技術(shù)學(xué)院電子與信息技術(shù)學(xué)院，江蘇 無錫 214121）

對訓(xùn)練樣本規(guī)模為m的標(biāo)準(zhǔn)支持向量機(jī)（Support Vector Machine，SVM）進(jìn)行訓(xùn)練，時間復(fù)雜度為O（m3），空間復(fù)雜度為O（m2）。文章研究將其轉(zhuǎn)換成等價的最小包含球（Minimum Enclosing Ball，MEB）形式，使用核心集向量機(jī)（Core Vector Machine，CVM）高效獲得近似最優(yōu)解。CVM的優(yōu)點(diǎn)是時間復(fù)雜度與訓(xùn)練樣本規(guī)模m呈線性關(guān)系，空間復(fù)雜度與m無關(guān)。實(shí)驗(yàn)證明，CVM可以對大規(guī)模數(shù)據(jù)集進(jìn)行高效的分類。

核向量機(jī)；支持向量機(jī)；最小包含球；核函數(shù)

在各種機(jī)器學(xué)習(xí)中，核方法是最成功的算法之一，其最著名的例子就是在支持向量機(jī)中的應(yīng)用。許多核方法都能轉(zhuǎn)換成標(biāo)準(zhǔn)二次規(guī)劃（Quadratic Programming，QP）問題。當(dāng)標(biāo)準(zhǔn)樣本集大小為m時，使用標(biāo)準(zhǔn)支持向量機(jī)（Support Vector Machine，SVM）進(jìn)行樣本訓(xùn)練需要O（m3）的時間復(fù)雜度和O（m2）的空間復(fù)雜度。因此數(shù)據(jù)挖掘應(yīng)用中，如何快速解決大樣本問題是亟待解決的問題。

為了降低時間和空間復(fù)雜度，Tsang等人2005年提出大樣本數(shù)據(jù)快速分類算法——核向量機(jī)（Core Vector Machine，CVM）［1］。CVM結(jié)合計(jì)算幾何學(xué)和SVM訓(xùn)練算法，將QP問題轉(zhuǎn)換成最小包含球（Minimum Enclosing Ball，MEB）問題，然后使用一種有效的（1＋ε）近似算法，從而獲得一個近似的SVM最優(yōu)解。

1 CVM理論

1.1 計(jì)算幾何意義下的最小包含球

考慮m個D維樣本，記作S＝｛x1，x2，…，xm｝，計(jì)算幾何意義下的最小包含球是指包含S中所有樣本的最小球。下面就討論基于核心集的近似最小包含球。定義B（c，R）表示圓心為c，半徑為R的球。設(shè)ε＞0，若R≤rMEB（S）且SB（c，（1＋ε）R），則球B（c，（1＋ε）R）是MEB（S）的（1＋ε）逼近，如圖1所示，內(nèi)圓是包含方塊點(diǎn)的最小包含球，外圓是內(nèi)圓的（1＋ε）擴(kuò)展，且包含所有點(diǎn)，方塊點(diǎn)為核心集.從許多擬合問題中發(fā)現(xiàn)，如果把整個數(shù)據(jù)集S的求解轉(zhuǎn)化成對S的一個子集Q的求解，會得到一個精確有效的近似解，其中Q被稱為核心集。更精確的定義：若B（c，R）＝MEB（X），且SB（c，（1＋ε）R），則子集XS是S的一個核心集。

圖1 幾何意義下最小包含球示例Fig.1 The geometric meaning of the smallest enclosing ball

為獲得核心集，Badoiu和Clarkson2002年提出一個簡單的計(jì)算近似最小包含球的迭代算法［2］，具體步驟如下：在第t次迭代中，得到最小包含球B（ct，rt），之后每次迭代都是把在近似球B（ct，（1＋ε）rt）之外最遠(yuǎn)點(diǎn)包含進(jìn)來，直到所有點(diǎn)都包含在B（ct，（1＋ε）rt）中，迭代結(jié)束。盡管這個算法簡單，但迭代次數(shù)和核心集的大小依賴與ε，而不是維數(shù)d或者樣本規(guī)模m。維數(shù)d的不相關(guān)性，對于運(yùn)用核方法是非常重要的。樣本數(shù)m的不相關(guān)性，使得算法的時間和空間復(fù)雜性增長緩慢。

1.2 最小包含球理論及其核化方法

在上述特征空間中尋求最小包含球MEB（S）等價為如下優(yōu)化問題：

轉(zhuǎn)換為對偶形式：

或轉(zhuǎn)換成矩陣形式：

若取高斯核k（x，y）＝exp（－‖x－y‖2／2σ2），則

在式（3）中有α＇1＝1的條件，故α＇diag（K）＝k，則式（3）可簡化成如下形式：

只要滿足式（4）和式（5）的QP問題都可看做最小包含球問題，可使用計(jì)算近似最小包含球的迭代算法求解。

1.3 SVM簡介及其與MEB之間的關(guān)系

給定訓(xùn)練集｛Zi＝（xi，yi）｝mi＝1，其中，yi∈｛－1，1｝，SVM優(yōu)化問題如下：

其對應(yīng)的對偶形式為：

其中，﹒為Hadamard乘積，y＝［y1，y2，…，ym］＇，K＝［k（xi，xj）］。

1.4 核心向量機(jī)CVM算法

1.4.1 核算法步驟

將核方法轉(zhuǎn)換成相應(yīng)的MEB問題后，就可使用核向量機(jī)快速求解近似最優(yōu)解。給定訓(xùn)練集｛Zi＝，其中，yi∈｛－1，1｝，因文中采用的是轉(zhuǎn)換后的核，所以下文中的核映射函數(shù)用表示，核向量機(jī)算法如下：

1.初始化S0、c0和R0。

5.迭代次數(shù)t加1，返回步驟2。

1.4.2 具體過程

（1）初始化

（2）距離計(jì)算

步驟2和3都要進(jìn)行距離計(jì)算，求點(diǎn)zl到中心點(diǎn)ct的距離公式為‖ct－φ（zl）‖2，將c＝（zi）帶入上式，得到：

顯然，計(jì)算距離不需要顯式計(jì)算φ～（zi），而使用核函數(shù)進(jìn)行計(jì)算。然而計(jì)算離中心點(diǎn)最遠(yuǎn)的點(diǎn)需要把所有點(diǎn)到中心的距離都計(jì)算一遍，當(dāng)樣本很大時時間花費(fèi)很高。本文CVM采用由Smola與Scholkopf 2000年提出的一種加速方法［3］。該方法指出，在樣本S中隨機(jī)的找一個樣本子集S’，在子集S’中找一個離中心點(diǎn)ct最遠(yuǎn)點(diǎn)來近似代替S中的最遠(yuǎn)點(diǎn)。在Smola與Scholkopf的文中指出，當(dāng)子集大小為59時，最遠(yuǎn)點(diǎn)包含在S’中的可能性為95%，通過這種方法可大大降低時間復(fù)雜度，此方法也可用于初始化步驟。

2 實(shí)驗(yàn)與分析

本節(jié)實(shí)驗(yàn)采用人造香蕉型數(shù)據(jù)集，如圖2所示。CVM需設(shè)置的參數(shù)有三個，分別是逼近參數(shù)ε、核參數(shù)σ和C參數(shù)。設(shè)置方法如下：核參數(shù)在網(wǎng)格｛0.5，1，2，4｝，C參數(shù)在網(wǎng)格｛0.1，0.5，1，10，100，1 000｝中搜索至最優(yōu)。

圖2 人造香蕉數(shù)據(jù)集Fig.2 Artificial Banana data set

實(shí)驗(yàn)1 逼近參數(shù)對CVM的影響驗(yàn)證

取banana樣本1 000個進(jìn)行CVM實(shí)驗(yàn)，表1顯示了不同逼近參數(shù)ε對實(shí)驗(yàn)結(jié)果的影響。

表1 逼近參數(shù)ε對CVM的影響（C＝1，σ＝1）Tab.1 Approximation parameters for CVM（C＝1，σ＝1）

文獻(xiàn)［1］中指出，ε越小，分類誤差越大，隨著ε的增大，精度提高的同時訓(xùn)練時間也增加，一般ε取1e－6即可獲得較好的分類精度。從表1可以看出，本例的banana數(shù)據(jù)集，ε取0.5e－3可獲得分類精度與訓(xùn)練時間的最佳協(xié)調(diào)。圖3顯示了ε取0.5e－3時的分類效果圖。

圖3 樣本規(guī)模為1 000時的分類圖Fig.3 Classification map（sample size：1 000）

實(shí)驗(yàn)2 CVM與SVM的比較實(shí)驗(yàn)

下面實(shí)驗(yàn)記錄了不同訓(xùn)練集規(guī)模下，經(jīng)典SVC與CVM算法的訓(xùn)練時間、測試時間及分類精度。每組實(shí)驗(yàn)重復(fù)10次，此外還記錄了CVM算法的核心集規(guī)模。

表2 CVM與SVM比較Tab.2 The Comparison of CVM and SVM

從表2可以看出，對于小樣本數(shù)據(jù)集，SVM算法和CVM算法的分類精確度大致相同，且SVM訓(xùn)練時間與測試時間均少于CVM；而對于大樣本數(shù)據(jù)集合，CVM訓(xùn)練及測試時間短，而分類精度還是與SVM相當(dāng)。使用核心集代替所有樣本，存儲空間也大規(guī)模減小。

3 結(jié)束語

核向量機(jī)是一種新的模式識別方法，它將核方法轉(zhuǎn)換成等價的MEB問題，并與計(jì)算幾何學(xué)相結(jié)合，從而解決了處理大樣本所需大量時間和空間的問題。實(shí)驗(yàn)表明，與SVM相比，CVM在有效節(jié)約運(yùn)行時間和空間的同時，保證了分類精度。

［1］ Tsang I，Kwok J，Cheung P.Core vector machines：Fast SVM training on very large data sets［J］.J of Machine Learning Research，2005，6（4）：363－392.

［2］ Badoiu M，Clarkson K L.Optimal core sets for balls［J］.Computational Geometry：Theory and Applications，2008，40（1）：14－22.

［3］ Smola A，Schlkopf B.Sparse greedy matrix approximation for machine learning［C］.Stanford，CA：Proc.7th Int.Conf.Mach.Learn.，2000：911－918.

Core Vector Machine Algorithm and its Application

XU Min
（School of Electronic and Information Technology，Wuxi Institute of Technology，Wuxi 214121，China）

According to the training set size m，standard SVM training hasO（m3）time andO（m2）space complexities.In this paper，CVM algorithm is discussed.It transforms the kernel method into equivalent MEB problems，and gets the approximately optimal solutions efficiently by core set.CVM has a time complexity that is liner in m and a space complexity that is independent of m.The result shows that CVM algorithm can handle much larger data sets than existing scale up methods.

Core Vector Machine（CVM）；Support Vector Machine（SVM）；Minimum Enclosing Ball（MEB）；kernel function

TP 18

A

1671－7880（2012）04－0073－04

2012－03－06

許敏（1980— ），女，講師，博士研究生，研究方向：人工智能與模式識別。