基于聚類的快速支持向量機訓練算法

(1.廈門理工學院 計算機科學與技術系，福建 廈門 361012； 2. 浙江大學 計算機科學與技術系， 杭州 310027)

摘 要：

支持向量機(support vector machine， SVM)具有良好的泛化性能而被廣泛應用于機器學習及模式識別領域。然而，當訓練集較大時，訓練SVM需要極大的時間及空間開銷。另一方面，SVM訓練所得的判定函數取決于支持向量，使用支持向量集取代訓練樣本集進行學習，可以在不影響結果分類器分類精度的同時縮短訓練時間。采用混合方法來削減訓練數據集，實現潛在支持向量的選擇，從而降低SVM訓練所需的時間及空間復雜度。實驗結果表明，該算法在極大提高SVM訓練速度的同時，基本維持了原始分類器的泛化性能。

關鍵詞：二次規劃; 無監督聚類; 權值; 距離閾值; 潛在支持向量

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

文章編號：1001-3695(2009)04-1253-04

Fast training support vector machine based on clustering

ZENG Zhi-qiang1， GAO Ji2， XIE Yan-qi1

(1.Dept. of Computer Science Technology， Xiamen University of Technology， Xiamen Fujian 361012， China; 2.Dept. of Computer Science Technology， Zhejiang University， Hangzhou 310027， China)

Abstract:

SVM is a well-known method used for pattern recognition and machine learning. However， training a SVM is very costly in terms of time and memory consumption when the data set is large. In contrast， the SVM decision function is fully determined by a small subset of the training data， called support vectors. Therefore， removing any training samples that are not relevant to support vectors might have no effect on building the proper decision function. This paper proposed a hybrid method to remove from the training set the data that was irrelevant to the final decision function， and thus the number of vectors for SVM training became small and the training time could be decreased greatly. Experimental results show that a significant amount of training time can be reduced by the method without compromising the generalization capability of SVM.

Key words：quadratic programming(QP); unsupervised clustering; weight; distance threshold; potential support vector

0 引言

訓練SVM[1]本質上就是求解一個等式約束的二次規劃(QP)問題。 最優化理論中的許多成熟算法，例如牛頓法、共軛梯度法及內點法需要利用整個赫賽(Hessian)矩陣，所以受普通計算機內存容量的限制， 只適用于樣本較少的情況，根本無法處理大量數據的問題。

SVM訓練所得的判定函數取決于一訓練樣本子集，該子集稱為支持向量集，支持向量集中的元素稱為支持向量。支持向量集能夠充分描述整個訓練樣本集的特征，并且在大多數情況下，支持向量只占訓練樣本集的很少一部分，因此可以使用支持向量集取代訓練樣本集進行學習，在不影響分類精度的同時縮短訓練時間。研究者們提出了各種方法對訓練集進行預處理來尋找潛在支持向量，減小QP問題的規模。這些方法包括隨機選擇[2，3]、Bagging[4]和Rocchio Bundling[5]等。然而，這些方法都存在一定的缺陷，隨機選擇和Rocchio Bundling過分簡化了訓練集，影響了結果分類器的分類精度[6]；Bagging方法雖然提高了SVM的訓練速度，但也增加了結果分類器分類的時間復雜度。本文提出一種新的預處理類型的SVM訓練算法——ClusterSVM，它通過創建一相對粗糙的分類超平面來實現潛在支持向量的選擇，從而減小SVM對應QP問題的規模。ClusterSVM不僅適用于對大規模數據集進行SVM訓練，而且克服了上述算法存在的缺陷。實驗結果表明，該算法在基本保持結果分類器分類精度的同時，極大提高了SVM在大規模數據集上的訓練速度，并且訓練完畢后具有較少的支持向量，因此對應的結果分類器具有較快的分類速度。

1 SVM簡介

訓練SVM的本質就是求解一個最優分類超平面問題，給定訓練樣本(xi，yi)(i=1，…，l）。其中：xi∈Rn，yi∈{-1，1}。求解最優分類超平面可以轉換為優化一個二次規劃問題[1]：

min w，b，ξ1/2wTw+C∑li=1ξi

subject toyi(wT(xi)+b)≥1-ξi，ξi≥0（i=1，…，l）(1)

其中：ξi（i=1，…，l）為松弛因子；C>0為懲罰算子，采用Lagrange乘子法可以獲得式(1)的對偶問題：

minαi，i=1，…，l 1/2∑li，j=1αiαjyiyjk(xi，xj)-∑li=1αisubject to0≤αi≤C（i=1，…，l），yTα=0(2)

其中：αi(i=1，…，l)為Lagrange乘子；k(xi，xj)=(xi)T(xj)為核函數，它對應于采用非線性映射:Rn|→ F將訓練樣本從輸入空間映射到某一特征空間F，在該特征空間中，樣本是線性可分的。SVM訓練所得分類超平面的函數形式如下：

f(x)=∑Nsvi=1αiyik(xi，x)+b(3)

根據KKT[1]條件可知，樣本點(xi，yi)，(i = 1，…，l) 滿足

αi=0yif(xi)≥1，0＜αi＜Cyif(xi)=1αi=Cyif(xi)≤1(4)

即訓練完畢后，所有訓練樣本分為三類：αi=0對應的樣本點分布在分類間隔之外；0＜αi＜C的樣本在分類間隔之上；αi=C的樣本在分類間隔之內(圖1)。根據式(3)可知，最優分類超平面僅由支持向量，即αi≠0所對應的樣本點來確定。換句話說，分類超平面是由分類間隔之上和之內的樣本點來確定，分類間隔之外的樣本點對超平面的形成沒有影響，僅僅訓練支持向量和整個數據集將獲得一致的分類超平面。因此，如果能夠預先確定支持向量并僅對這部分數據進行訓練，將大大減小SVM學習問題的規模，從而在保持結果分類器分類精度的同時，極大地降低SVM訓練所需的時間及空間復雜度。

根據圖1可以看出，樣本點越靠近最優分類超平面，越有可能成為支持向量。這些靠近最優分類超平面的樣本點被稱為潛在支持向量。

2 基于聚類的預處理算法

ClusterSVM算法的基本框架可描述如下：首先對正負兩類樣本點分別進行聚類；接著采用聚類所得的簇質心代表整個訓練樣本集進行SVM訓練，獲得一過渡性的分類超平面；然后計算各個樣本點到此分類超平面的距離，如果樣本點到分類超平面的距離大于一定的閾值，則認為這個樣本點是非支持向量，將它從訓練集中刪除；最后，訓練集中剩下的樣本點都可看做潛在支持向量，對這些潛在支持向量進行SVM訓練以獲得最優分類超平面。

2.1 無監督聚類法

筆者采用一種簡單的無監督聚類(unsupervised clustering， UC)算法[7]來對正負兩類數據分別進行聚類。與傳統的K-means算法預先指定類別數不同，UC算法根據預先給定的聚類半徑來對數據進行聚類，具有較高的聚類速度。假設待聚類數據集為X={x1，x2，…，xm}，xi∈Rd（i=1，…，m），聚類半徑設為R， 則UC算法描述如下：

a)C1={x1}，O1=x1，cluster_num=1，Z={x2，…，xm}。

b)如果 Z=， 則 stop。

c)選擇樣本 xi∈Z， 從已有的質心中尋找與xi距離最近的質心Oj， 即

Oj=argj mincluster_numk=1 d(xi，Ok)(5)

d) 如果d(xi，Oj)≤R， 則將xi加入類Cj， 即Cj=Cj∪{xi}， 類Cj的質心調整為

Oj=(nj×Oj+xi)/(nj+1)(6)

其中:nj為類Cj所包含的樣本數目。調整 nj = nj + 1， 轉f)。

e) 如果d(xi，Oj)＞R，增加一個新類 cluster_num=cluster_num+1， Ccluster_num={xi}， Ocluster_num=xi。

f) Z=Z-{xi}，轉b）。

UC算法的最大時間開銷為O(cluster_num×m)，因此具有較高的效率。

2.2 構造中間分類超平面

采用UC算法對正負兩類樣本集分別進行聚類后，得到一系列的簇及相應的簇質心。將所有的簇質心作為訓練樣本進行SVM訓練，獲得一過渡性的分類超平面，稱此超平面為中間分類超平面。由于簇質心反映了各個簇的相對位置，從而概括了訓練樣本在空間中的分布狀況，中間分類超平面在很大程度上接近最優分類超平面。然而，必須考慮到每個簇所包含的樣本點數目各不相同，即每個簇質心分別代表不同數量的樣本，如果將各個簇質心同等對待進行SVM訓練，將降低中間分類超平面和最優分類超平面的相似度，從而影響潛在支持向量的選擇。為了使中間分類超平面盡可能接近最優分類超平面，筆者對標準SVM二次式進行修改以反映不同簇質心的影響力。修改后的SVM二次式如下：

minw，b，ξ 1/2wTw+C∑li=1λiξi(7)

subject to yi(wT(xi)+b)≥1-ξi，ξi≥0（i=1，…，l）

改進后的二次式采用帶權值的分類誤差項，其中正類簇質心的權值λi定義如下：

λi=(# of points within Ui)/(# of positive training data/k+)(8)

其中:Ui代表某一正類簇;k+表示正類樣本聚類所得簇的數量。負類簇質心的權值可類似定義。根據式(8)可知，簇所包含的樣本數量越多，其簇質心所對應的分類誤差權值就越大。

為了求解式(7)所表示的優化問題，首先定義如下的Lagrange函數：

Γ(w，b，ξi，α，β)=1/2‖w‖2+C∑li=1λiξi-∑li=1αi(yi(wT(xi)+b)-1+ξi)-∑li=1βiξi(9)

其中：αi≥0（i=1，…，l）為Lagrange乘子。式(7)所代表的優化問題可以通過求解其對偶問題來解決，即求解Γ(w，b，ξi，α，β)關于α的最大值。首先求Γ(w，b，ξi，α，β)關于w，b和ξi的偏導數，并令其等于零：

Γ(w，b，ξi，α，β)/w=w-∑li=1αiyi(xi)=0(10)

Γ(w，b，ξi，α，β)/b=-∑li=1αiyi=0(11)

Γ(w，b，ξi，α，β)/ξi=λiC-αi-βi=0(12)

將式(10)~(12)代入(9)，獲得式(7)的對偶問題：

maxα-1/2∑li，j=1αiαjyiyjk(xi，xj)+∑li=1αisubject to ∑li=1αiyi=00≤αi≤λiC(i=1，…，l)(13)

對比標準SVM和改進后SVM二次式的對偶問題可知，兩者只是在Lagrange乘子的約束上有所不同，改進后αi的上限約束多了乘子λi。因此，求解SVM問題的算法經簡單修改后就適用于加權SVM問題。

2.3 確定支持向量簇

獲得中間分類超平面h后，筆者利用h對訓練樣本進行削減。令Ls表示分類間隔，Lj表示任一簇Uj的質心Oj到h的距離，則支持向量簇定義如下[8]：

定義1支持向量簇。如果簇Uj的質心Oj到中間分類超平面h的距離Lj滿足

Lj-R-Ls≤δ(14)

則稱簇Uj為支持向量簇。其中：R為聚類半徑；δ為距離閾值，滿足0＜δ＜1。

根據定義1可知，支持向量簇就是那些靠近中間分類超平面h的簇(圖2中，帶黑色標記的簇就是支持向量簇)。中間分類超平面h在很大程度上近似所求的最優分類超平面h′， 靠近h也就靠近h′，因此，與其他訓練樣本相比，從屬于支持向量簇的樣本點有較大可能成為最優分類超平面h′的支持向量。而其他簇所包含的樣本點由于遠離最優分類超平面h′，它們對h′的生成沒有任何影響，將這些樣本從訓練集中刪除，僅僅保留從屬于支持向量簇的樣本點。



2.4 確定潛在支持向量

在2.3節中，筆者刪除掉那些遠離中間分類超平面h的簇，僅保留離h較近的支持向量簇。從圖2可以看出，雖然支持向量簇從整體上看靠近中間分類超平面h，但是支持向量簇所包含的樣本點并不都靠近h。因此，支持向量簇里的樣本點進一步提純，以確定最終的潛在支持向量集。假設對應于中間分類超平面h的函數為g(x)， 如果樣本點(xi， yi)滿足

Ls-δ≤yig(xi)≤Ls+δ(15)

則該樣本點被視為潛在支持向量，選取該樣本點進入最終的訓練集。式(15)中的Ls和δ與(14)中相同。

上述選取策略可以通過圖3來形象表示。其中：h表示中間分類超平面；h+和h-分別表示正負兩類支持向量所處的超平面。該選取策略就是保留與h+或h-距離小于δ的樣本點，把其他樣本點刪除。注意到，該選取策略不僅刪除與h距離較遠的樣本點，同時也刪除過分靠近h的樣本點。這是因為過分靠近分類超平面的樣本點會導致SVM訓練過程中的過學習，從而降低了結果分類器的分類精度。另外，式(15)對應的選取策略還包括刪除yig(xi)＜0的樣本點，即被h錯分的樣本點，這類樣本點有較大可能是噪聲數據，刪除它們有助于提高結果分類器的分類精度。

2.5 算法描述

確定潛在支持向量集后，采用標準的SVM算法對其進行訓練以獲得最優分類超平面。算法總體框架描述如下：

輸入：正類訓練樣本集D+、負類訓練樣本集D-、距離閾值δ；

輸出：最優分類超平面 b。

函數：

unsupervisedCluster(D，R)——返回對數據集D采用UC算法聚類后所得的簇集合及相應的簇質心集合，其中R為聚類半徑;

getLowerMarginClusters(b′， C)——返回簇集合C中靠近分類超平面b′的支持向量簇的集合(根據式(14));

getClusterData(c)——返回從屬于簇c的樣本點集合；

getPotentialSupportVectorSet(D， h)——返回集合D中與分類超平面h的距離滿足式(15)的樣本點集合。

算法框架：

initialize R+，R-// 初始化正負兩類數據集的聚類半徑

(Cp， D+initial):= unsupervisedCluster(D+，R+);

// Cp為簇集合， D+initial為相應的簇質心集合

(Cn， D-initial):=unsupervisedCluster(D-，R-);

C :=Cp U Cn;

Dinitial:=D+initialU D-initial;

與b′:=SVM.train(Dinitial);

//采用加權SVM二次式創建中間分類超平面b′

C′:=getLowerMarginClusters(b′， C);

for i := 1 to |C′|

 {

D′i:=getClusterData(c′i); //c′i∈C′

Dreduced:=Dreduced U getPotentialSupportVectorSet(D′i，b′);

 }

b := SVM.train(Dreduced);

//采用標準SVM二次式創建最優分類超平面b

return b;

3 實驗結果及分析

筆者在兩個大規模數據集上分別采用ClusterSVM及標準SVM算法進行訓練，比較它們的訓練速度及相應分類器的分類精度，以驗證ClusterSVM算法的高效性。

3.1 實驗數據集及參數設置

LIBSVM[9]被采用作為標準的SVM訓練算法，在其基礎上，采用C++實現了ClusterSVM算法。Adult和forest兩個大規模數據集被選取作為實驗數據集，它們來自UCI機器學習數據庫[10]。原始的forest數據集是個超大數據集，它包含500 000條以上記錄，從中隨機抽取70 000條記錄。其中50 000條作為訓練集，其余作為測試集。Forest數據集是個多類分類問題，筆者將其改為兩類分類問題，即將cover type 5作為一類，其余類別作為另一類。實驗數據集如表1所示。



在所有實驗中，SVM算法的參數C設為100，并且都采用高斯核函數。高斯核函數參數采用LIBSVM的缺省值。實驗所用機器為PC機(P3 1.8 GHz CPU和1 GB RAM)， 操作系統為Windows 2003 Server。

3.2 訓練結果比較

實驗結果如表2所示。其中ClusterSVM的運行時間包括兩部分，即對訓練集進行削減的時間和對最終所得潛在支持向量集進行SVM訓練所需時間。從表2中可以看出，當δ≥0.5時，在兩個實驗數據集上，ClusterSVM算法訓練所得的分類器基本保持了原始分類器的分類精度(原始分類器是指采用標準SVM算法對整個數據集進行訓練所獲得的分類器)。在δ的某些取值下，采用ClusterSVM算法訓練所得分類器的分類精度甚至高于原始分類器的分類精度。這是因為在訓練集削減過程中，部分噪聲數據和某些太靠近分類超平面的樣本點從訓練集中刪除了，避免了訓練過程中的過擬合問題。經過前期的數據預處理，保留下來參與最優分類超平面創建的樣本點大為減少，因此最終的SVM訓練所需時間很少。即使考慮上訓練集削減所花費的時間，ClusterSVM總體消耗的時間仍然遠遠低于采用LIBSVM對整個訓練集進行訓練所需時間。

表2 LIBSVM和不同距離閾值下ClusterSVM的訓練時間及測試準確率的比較



從表2中還可看出，采用ClusterSVM算法訓練所得的支持向量數遠遠少于LIBSVM，這意味著ClusterSVM訓練所得的分類器具有更快的分類速度。

3.3 距離閾值的影響

從表2可以看出，距離閾值δ在ClusterSVM的訓練速度和結果分類器的分類精度間起折中作用，隨著距離閾值的減小，更多的訓練樣本從訓練集中刪除，ClusterSVM的訓練速度隨之提高，與此同時，訓練所得分類器的分類精度降低。值得注意的是，當δ≥0.5時，相對于標準SVM訓練算法的訓練速度而言，不同的δ取值對ClusterSVM的訓練速度影響不是很大。因此，實際應用中選取一個較大的δ值有助于結果分類器保持一個較高的分類精度。

3.4 加權支持向量機的作用

定義h1、 h2分別表示采用標準和加權SVM二次式，對訓練集聚類所得的簇質心進行SVM學習所獲得的中間分類超平面。它們在測試集上的準確率如表3所示。

表3 不同SVM二次式訓練所得中間分類超平面在測試集上的分類準確率比較



datasettesting accuracy：h1/%testing accuracy：h2/%

adult76.1278.04

forest78.2579.57

從表3可以看出，由于加權SVM充分考慮了各個簇質心對分類超平面的不同影響力，與標準SVM相比較，它所創建的中間分類超平面在測試集上具有更高的分類準確率。換句話說，加權SVM所創建的中間分類超平面更接近最優分類超平面，因此，利用它可以更為準確地選擇潛在支持向量集，從而使結果分類器具有更高的分類精度。筆者在ClusterSVM算法的第二階段分別采用標準和加權SVM二次式訓練中間分類超平面，在這兩個中間分類超平面的基礎上推出相應的結果分類器，比較它們在測試集上的準確率。實驗結果如圖4所示。從圖4中可以看出，采用標準和加權SVM二次式訓練中間分類超平面，最后所得到的結果分類器具有更高的分類精度。

4 結束語

本文所提出的ClusterSVM訓練算法通過對訓練數據進行預處理來實現潛在支持向量選擇，減小對應QP問題規模，從而提高SVM的學習速度。與現有預處理類型的SVM訓練算法相比，ClusterSVM算法具有如下優勢：

a)在極大提高SVM訓練速度的同時，基本維持了原始分類器的泛化性能。

b)訓練完畢后具有較少的支持向量，因此對應的結果分類器具有較快的分類速度。

本文的研究工作立足于分類問題，而回歸SVM也同樣在訓練方面存在著速度問題，如何提高SVM回歸機的訓練效率，并且與分類問題的SVM算法統一起來，拓寬算法的適用范圍，是今后的研究重點。



參考文獻：

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

[2]BALCAZAR J L， DAI Y， WATANABE O. Provably fast training algorithms for support vector machines[C]//Proc of the 1st IEEE International Conference on Data Mining (ICDM01). [S.l.]:IEEE Computer Society， 2001: 43-50.

[3]AGARWAL D K. Shrinkage estimator generalizations of proximal support vector machines[C]//Proc of the 8th ACM SIGKDD Internatio-nal Conference of Knowledge Discovery and Data Mining (SIGKDD02). Edmonton， Canada:[s.n.]， 2002: 173-182.

[4]VALENTINI G， DIETTERICH T G. Low bias bagged support vector machines[C]//Proc of the 20th International Conference on Machine Learning (ICML03). Washington DC:[s.n.]， 2003: 752-759.

[5]SHIH L， RENNIE J D M， CHANG Y H， et al. Text bundling:statistics-based data reduction[C]//Proc of the 20th International Confe-rence on Machine Learning(ICML03). Washington DC:[s.n.]， 2003: 377-387.

[6]DANIAEL B， CAO D. Training support vector machines using adaptive clustering[C]//Proc of SIAM International Conference on Data Mining (SIAM’ 04) . Lake Buena Vista， FL:[s.n.]， 2004: 126-136.

[7]李曉黎，劉繼敏，史忠植. 基于支持向量機和無監督聚類相結合的中文網頁分類器[J].計算機學報，2001，24(1):62-68.

[8]YU H， YANG Jiong， HAN Jia-wei. Classifying large data sets using SVM with hierarchical clusters[C]//Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD’02) . New York: ACM Press，2002: 306-315.

[9]CHANG C C， LIN C J. LIBSVM: a library for support vector machines [EB/OL]. http://www.csie.ntu.edu.tw/ cjlin/libsvm.

[10]MURPHY P M， AHA D W. UCI repository of machine learning databases [EB/OL].(1994). http://www.ics.uci.edu/~mlearn/MLRepository.html.