基于商空間粒度理論的大規模ＳＶＭ分類算法

摘 要：利用商空間粒度理論對已有的SVM分類算法進行改進，給出了一種新的SVM分類算法——SVM-G。該算法將SVM分類問題劃分成兩個或多個子問題，從而降低了SVM分類復雜度。實驗表明，改進的算法適用于處理大數據量的樣本，能在保持分類精度的情況下有效地提高支持向量機的學習和分類速度。

關鍵詞：粒度； 商空間； 支持向量機; 分類; 機器學習

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695(2008)08-2299-03

Large-scale SVM classification algorithm

based on granularity of quotient space theory

WEN Gui-huaa， XIANG Junb， DING Yue-huab

(a.School of Computer Science Engineering， b.Research Institute of Computer Application Engineering， South China University of Technology， Guangzhou 510641， China)

Abstract:This paper improved the existing SVM algorithm with the granularity of the quotient space theory， proposed a new SVM algorithm（SVM-G）. The improved algorithm divided SVM classification problem into two or more sub-issues， thereby reducing the computation complexity of SVM classification. Experimental results indicate that the improved algorithm is suitable for processing large number of observations and can effectively accelerate the speeds of SVM learning and classifying while keeping the classification precision.

Key words：granularity； quotient space； SVM(support vector machine); classification; machine learning

粒度計算是信息處理的一種新的概念和計算范式^[1]。目前，研究得較多且較成熟的一種粒度計算理論是商空間理論^[2]。文獻[2]提出了基于商空間的問題求解理論，商空間將問題表述成不同的粒度世界，進而進行相應的粒度計算。粒度計算的優點在于使對問題的解決擺脫了一些繁瑣且非關鍵的過程，抓住問題的關鍵或本質，從適當的層次（粒度）來研究問題，最終可快速獲得問題的精確解或近似解^[3~5]。

支持向量機（SVM）是由Vapnik^[6]于20世紀90年代初提出的一種新的機器學習方法。SVM算法利用凸二次規劃（quadratic programming，QP）、Mercer核、稀疏解和松弛向量等多項技術，具有結構簡單、訓練誤差低和泛化能力好等優點，因而被廣泛地應用于分類學習問題中。但是當樣本規模較大時，SVM算法在二次尋優過程中需要存儲核矩陣和進行大量矩陣運算，使得運算時間過長。目前，改進算法主要有Vapnik等人^[7]提出的選塊算法、Osuna等人^[8]提出的分解算法、Platt^[9]提出的序列最小最優化法(sequential minimal optimization，SMO)等。

以上幾種改進算法，雖然有效地改進了SVM分類速度，但仍是對原始樣本集進行處理，也即一直是在較精的粒度上進行運算。基于問題求解的商空間理論用可用空間結構來表示樣本的結構。本文依據這個理論，將商空間粒度計算應用于SVM分類，采用距離度量空間的手段來解決大規模樣本集的SVM分類問題。據此，提出一種基于商空間理論的SVM分類算法（SVM-G），該算法用空間距離表示信息粒度，采用分層遞階的方法，由粗到精地處理樣本點。實驗表明，該算法對大樣本集的分類能在保持訓練精度的同時進一步提高訓練和分類的速度，具有降低計算復雜度和空間復雜度、適于處理樣本數較多的SVM分類問題等優點。

1 理論準備

1.1 商空間理論

在實際問題求解過程中，隨著求解問題的不同，需要不同粒度的世界描述。有時解決某一問題時，同時需要若干不同粒度的世界。商空間理論用三元組(X，f，T)描述一個問題。其中：x表示問題的論域； f(·)是論域屬性；T是論域的結構，指論域X中各元素的相互關系。分析或求解問題(X， f， T)是指對論域X及其有關的結構、屬性進行分析、研究。可以對X的大小粒度進行簡化，產生一個新的較大粒度的論域[X]，那么把原問題(X， f， T)變成新的層次上的問題([X]，[f]，[T])，即從較粗粒度[X]去考察問題。

1.1.1 不同粒度世界的描述

定義1 設X、Y是兩個集合，X×Y是X與Y的積集，RX×Y。設(x，y)∈X×Y，有(x，y)∈R，則稱X與Y有關系R，記為xRy。稱R為X×Y上的一個關系。

定義2 x∈X ，令[x]={y|x~y}，稱為x的等價類。

定義3 令[X]={[x]|x∈X}，稱[X]是關于R的商集。

故商集是將等價類[X]看成新元素而構成的新空間，是原空間粗粒度的論域。

商空間理論將不同粒度的世界與數學上的商集概念統一起來，或者說以商集作為不同粒度世界的數學模型。

1.1.2(X，T)拓撲空間

對于一個具體對象(X， f，T)，結構也很重要。當一個論域被劃分，其結構也發生了變化。一般講結構T很廣泛、很復雜，商空間理論有詳細討論。這里只引用其中(X，T)對拓撲空間的部分結論。

定義4 設X是一集合，T是X的一個子集族。若T滿足：a)，X∈T;b)若u1，u2∈T，則(u1∩u2)∈T;c)若uα，α∈I∈T，則∪α∈Iuα∈T。其中：I是指標集，I的勢可以是任意的。稱T是X上的一個拓撲，稱(X，T)為一拓撲空間；uX稱u是開集u∈T。

在一個集合X上給定一個拓撲，就給出X中各元素之間的一個互相關系的結構。

設R是X上的一個等價關系。對R可以得到對應的商集，記為[X]。在[X]上定義由T誘導出的拓撲，記為[T]，其表示為[T]={u|p-1(u)∈T，u[X]}。稱[T]為商拓撲，([X]，[T])為商拓撲空間。

構造了拓撲空間，有以下拓撲學的命題：

命題1 p:(X，T)→([X]，[T])是自然投影，故p是連續的。若AX且A是X中的連通集，則p(A)是[X]的連通集。

這表明，若一個問題在原論域中有解(是連通的)，在適當的粗粒度論域上[X]有解。也就是說，對于SVM分類問題而言，在其所對應的商空間X(λ)(λ=1，2，…，p)上的SVM分類同樣有效。

1.2 SVM分類原理

SVM來源于線性可分問題的最優分類超平面，尋找一個滿足分類要求的最優分割超平面，以最大間隔將數據分開。對于線性不可分問題，通過選擇某種非線性映射，將輸入空間映射到一個維數更高的特征空間，在這個空間構造最優分類超平面。可以證明， 如果選用適當的映射函數， 大多數輸入空間線性不可分問題在屬性空間可以轉換為線性可分問題。

給定訓練集(xi，yi)，i=1，2，…，l。其中：xi∈Rn且yi∈{-1，1}，最優分割超平面的計算問題可以描述為一個條件極值問題。Vapnik通過求解下列Lagrange函數的鞍點來獲得其最優解:

Lp=‖w‖2/2+C∑iξi-∑iα{yi（Φ(xi)w+b)-1+ξi}-

∑iμiξi（1）

其中：w和b分別為屬性空間最優超平面的法向量和閾值；ξi和μi分別為非負的Lagrange 乘數； C為非負的誤差控制參數；Φ(xi)為核函數。

由Karush-Kuhn-Tucker 定理可知， 最優解滿足以下條件:

w=∑iαyiΦ(xi)(2)

0≤α≤C，∑iαyi=0(3)

可得到分類器函數為

f(x)=sgn(∑i∈SVyiαiΦ(xi)-b)(4)

一般情況下， 在式(2)的展開式中， 大多數系數α為零值，并不影響分類的結果。對w的確定有貢獻的僅僅是非零值的α所對應的xi， 這就是SV(support vector， 支持向量)。 因此，SV集充分描述了整個訓練數據集數據的特征， 對SV 集的劃分等價于對整個數據集的分割。

在大多數情況下， 訓練集中SV 的數量只占訓練樣本集的很少一部分， 即NSV<

2 改進算法SVM-G

根據商空間粒度計算理論，信息粒度最先來自整個論域X，然后根據其相似性、不可分性或一致性等原則對論域進行不同的劃分，形成不同粒度。論域的劃分原則上是一個復雜的問題，通常要根據提出的目標而定，且與具體論域有關。本文使用歐氏空間中的間隔分析形成相應粒度（其具體構造見2.1節），提出一種改進的SVM算法——SVM-G。從距離間隔角度來看商空間X(λ)，X(λ)中的元素通過將屬于同一間隔區間的元素看成一個元素，從這個角度理解，X(λ)具有直觀的物理意義。

改進后的算法將在不同的粒度（層次）上進行SVM分類訓練，即在粗粒度上進行SV的粗選，在精粒度上進行SV的精確判定。

2.1 粒度計算

在歐氏空間Rn中，粒度的空間間隔向量[bk]可定義為n個間隔的笛卡爾乘積，表示為

2.2 算法流程

SVM-G分類算法至少包含兩個階段：

a)通過對粒度空間的選擇而粗略地去除對構造最優分類超平面無用的樣本點。具體做法是利用粒度空間中新構建的樣本點，然后利用新樣本點進行SVM訓練，找出支持向量，這些支持向量也就代表了原樣本集中支持向量所在空間。參數d可用來控制粒度大小，d越大表示粒度越大，則新構建的樣本點比原樣本點越少。在該層次上的SVM訓練比原先整個樣本上的SVM訓練復雜度降低。

b)將原始樣本點從第一階段所得的粒度空間中釋放，這些樣本點用來進行最終的SVM訓練。由于在第一階段中很多樣本點已去除，該層進行SVM訓練的樣本點也相對較少，計算復雜度降低。

如果在第二階段中樣本點仍然很多，則可將所得樣本點按照第一階段中的步驟再處理一次，進一步濾除非支持向量所在空間集合。這樣可保證在每一階段中的訓練集不會過大，從而降低整個SVM分類中的空間復雜度和時間復雜度。

SVM-G分類算法描述如下：

訓練集φ0={(xi，yi)|xi∈Rn，yi∈{-1，1}；i=1，2，…，N}

a)將輸入數據xi(i=1，2，…，N)規范化到空間[dmin，dmax]n。

b)按照式（8）和（9）選擇間隔向量[bk]，然后按照式（6）和（7）形成粒度空間中的代表向量(ak，tk)。由其中非零向量構成新的訓練集： φ1={(ak，tk)|ak∈[dmin，dmax]n，tk∈{-1，1}；k=1，2，…，l}。

c)對數據集φ1進行SVM訓練，由支持向量粒度空間構成集合θ，將原訓練樣本從集合θ中釋放出來，形成另一個集合φ2={(xi，yi)|xi∈bk，ak∈θ}。

d)如果集合φ2的大小比M大，則轉b);否則轉e)。M為預先設定的常量。

e)對數據集φ2進行SVM訓練，使用測試集進行測試。

3 實驗結果分析

在本實驗中，所用數據均來源于UCI機器學習庫^[10]。選用其中的satimage、letter和shuttle三種基準數據集，它們的基本信息如表1所示。

表1 基準數據集基本信息數據集satimagelettershuttle訓練樣本數4 43515 00043 500測試樣本數2 0005 00014 500類別數6267輸入維數36169算法通過MATLAB7編程實現，實驗在P4-266的PC機上運行，內存為256 MB。實驗使用了LIBSVM軟件包中的MATLAB接口^[11]，利用該接口中的SVM分解算法實現基本SVM訓練；同時在SVM-G分類的兩個訓練階段也是使用該MATLAB接口中的分解算法來實現；并將本文方法與LIBSVM軟件包中方法的分類效果進行比較。

實驗中所有的訓練和測試數據都歸一化到[-1，1]內，取r=「nN（N為樣本數，n為樣本輸入維數）。分類核函數采用徑向基函數（radial-basis function，RBF），交叉驗證中參數步長分別為C=[212，211，210，…，2-2]和γ=[24，23，22，…，2-10] 。SVM-G與原SVM算法的準確性如表2所示。

表2 算法準確性比較

數據集SVM-GSVMC，γ正確率/％C，γ正確率/％satimage23，2-1/ 23，2091.0524，2091.78letter26，21/25，2197.8824，2297.90shuttle211，20/29，2199.84211，2399.92實驗結果表明，SVM-G分類法的準確度比SVM分類稍有降低。其原因主要是在第一階段中可能會濾除掉部分支持向量樣本點，造成測試準確性比傳統SVM有所下降。但從實驗結果可以看出，準確性只是百分比小數位的改變，所以對分類效果的影響很小。

表3給出了SVM-G和SVM的訓練樣本數量、支持向量數目和計算時間；對于SVM-G分別給出了第一階段和第二階段訓練中的樣本數量和相應的支持向量數目。表中的運行時間包括訓練時間和測試時間。雖然訓練時間會受參數設置的影響，但從實驗結果可以清楚看到，SVM-G算法的運行時間均有所下降，并且可以注意到對于shuttle數據集來說，改進算法的運行速度是原SVM算法的5倍多。這也表明當樣本集中的支持向量數目少時，第一階段中就可移除掉大量訓練樣本點，第二階段中訓練的樣本點就比原樣本集大為減少，從而縮短整個計算時間。

表3 測試結果比較數據集算法樣本數量SVs時間/ssatimageSVM-G3 436/1 868396/86415.89SVM4 4351 61325.19letterSVM-G1 474/14 50913 24/7 574341.33SVM15 0007 742438.40shuttleSVM-G316/1 258116/1359.84SVM43 50027848.064 結束語

本文針對SVM算法在大樣本集應用中訓練和分類速度慢的問題，將商空間粒度理論應用于SVM分類問題，并對已有的SVM算法進行改進，提出了一種新的改進算法——SVM-G。該算法將分類樣本空間進行由粗到細的劃分，即采用分層遞階的方法，將SVM分類中QP求解問題分解成兩個或更多個子QP問題，使得問題求解過程中Q矩陣的階由N×N階轉換為(l1×l1+l2×l2+…+lp×lp)階（其中：l1、l2和lp分別為第1、第2和第p階段訓練樣本）。改進的算法能在保持分類精度上減少分類運算時間。實驗表明，SVM-G算法實現了比原SVM分解算法更快的運行速度；尤其對于支持向量數目相對較少的大規模SVM分類問題來說，該方法非常有效。

參考文獻：

[1]YAO Y Y， ZHONG Ning. Potential applications of granular computing in knowledge discovery and data mining[C]//Proc of World Multi-Conference on Systemics， Cybernetics and Informatics.[S.l.]:Computer Science and Engineering，1999:573-580.

[2]張鈸，張鈴. 問題求解理論及應用[M].北京:清華大學出版社，1990.

[3]張燕平，張鈴，吳濤. 不同粒度世界的描述法——商空間法[J].計算機學報，2004，27(3)：328-333.

[4]高平安，蒙祖強，蔡自興.基于粒度計算的數據分類建模研究[J].計算機應用研究，2007，24(3):37-40.

[5]卜東波，白碩，李國杰. 聚類/分類中的粒度原理[J]. 計算機學報，2002， 25(8):810-816.

[6]VAPNIK V N. The nature of statistical learning theory[M]. New York: Springer-Verlag， 1995.

[7]VAPNIK V， GOLOWICH S， SMOLA A. Support vector method for function approximate，regression estimation， and signal processing[M]. Cambridge: MIT Press， 1997:281-287.

[8]OSUNA E， FREUND R， GIRROSI F. Improved training algorithm for support vector machines[C]//PRINCIPLE J， GILES L， MONGAN N， et al. Proc of IEEE Workshop on Neural Networks and Signal Processing. Amelia Island: IEEE Press，1997:276-285.

[9]PLATT J C. Fast training of support vector machines using sequential minimal optimization[M]// SCHOLKOPF B， BURGES C J C， SMOLA A J. Advances in kernel methods: support vector learning. Cambridge: MIT Press， 1999: 185-208.

[10] ASUNCION A，NWEMAN D J.UCI machine learning repository [D]. California: Department of Information and Computer Science， University of California， 2007.

[11]CHANG C C， LIN C J. LIBSVM: a library for support vector machines[EB/OL]. (2006-11-17) [2007-01-07]. http://www.csie. ntu.edu.tw/cjlin/libsvm.

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