支持向量機與K-均值聚類融合算法的研究

田飛，于威威（上海海事大學，上?！?01306）

支持向量機與K-均值聚類融合算法的研究

田飛，于威威
（上海海事大學，上海201306）

傳統的支持向量機分類算法隨著樣本規模增大、支持向量數量增多時，其分類過程所消耗的時間也會隨之增加。為此，提出一種改進算法，將K-均值聚類算法與支持向量機融合。將標準支持向量機訓練后得到的支持向量集進行特定比例的K均值聚類操作，把聚類的中心作為新的支持向量，再用二次規劃方法求解得到新的分類決策函數。實驗結果表明，該分類算法有效地減少計算時間，提高分類速度，尤其在訓練集規模龐大、支持向量數量較多的情況下，效果會更加明顯。

支持向量機；支持向量；K均值聚類；二次規劃

0　引言

支持向量機（Support Vector Machine，SVM）算法是在統計學習理論［1］的基礎上提出的，在處理小樣本分類問題是具有其他分類算法不具備的優勢。它最初于20世紀90年代由Vapnik提出，是近幾年來機器學習的一項重大研究成果，SVM在很大程度上解決了過學習、高維數和局部極小點等傳統困難。此外，由于其優秀的性能以及其優良的范化能力，使其在很多領域中得到長足的發展，并被廣泛應用于網絡入侵檢測、文本識別、人臉表情圖像識別等領域。人們對于支持向量機算法的研究已經相當成熟，在加速訓練過程方面近年來已經取得了一定的研究成果：如Platt提出的 SMO （Sequential Minimal Optimization）方法［2］、以及Suykens等人提出的最小二乘支持向量機［3］（Least Squares Support Vector Machines，LS-SVM）和Osuna等的Chunking方法［4］以及文獻［5］使用KNN預選取樣本的方法等，這些方法對分類速度的提高沒有任何影響。文獻［6］提出的RSVM（Reduced Support Vector Machines）算法是基于隨機地選取樣本集中的一個子集進行訓練，該方法在一定程度上減少SVM訓練時間、加快訓練速度。但是由于樣本規模減小而損失了部分支持向量，導致其分類精度有所下降。所以，研究如何在盡量減小分類精度損失的前提下，將原始支持向量的數量盡量減少是本文需要解決的一個問題。

在提高SVM分類速度這個方向，許多研究人員也提出了相應的減少支持向量算法：如Burges等人提出的一種提高分類速度方法［7］，該方法中的向量集既不是訓練樣本也不是支持向量，而是經過變換得到的特殊向量。文獻［8］提出了ν-SVM，并指出參數ν是支持向量的個數和訓練樣本個數的比率（支持向量率）的下界。劉向東、陳兆乾等人提出的快速的支持向量機分類算法 FCSVM［9］（Fast Classification for Support Vector Machines）是通過變換矩陣的方式來減少分類函數中的支持向量，但是該變換方式需要通過不斷的迭代來找出合適的支持向量劃分集。本文提出了一種減小支持向量，提高分類速度的算法：即將K均值聚類算法引入SVM中，將標準的SVM訓練得到的支持向量集通過聚類算法按照特定的比例壓縮，再根據求解二次規劃問題來求解出新的稀疏后的支持向量對應的權重系數，最終得到精簡后的新的SVM快速決策函數。

1　原理概述

1.1支持向量機算法

設樣本及其值表示為 （xi，yi），其中 i=1，2，…，l，xi∈Rn，yi∈｛-1，1｝，在線性不可分的情況下，SVM將數據映射到一個特征高維空間?（x）=（φ1（x），φ2（x），…，φN（x））中，并且構造出最優超平面y（x）=sgn［w·（x）+b］。以此來實現非線性分類到高維特征空間中的線性分類的一個轉化，即在約束條件為yi［?（xi）·w+b］≥1-ξ的情況下，使‖w‖最小化的問題。也就是：

其中ξi≥0，i=1，2，…，l，c為給定常量

為了解決約束最優化問題并轉化為其對偶問題，引入式（2）所示的拉格朗日函數：

其中ai，γi是拉格朗日乘子ai≥0，γi≥0，i=1，2，…，l。由于該優化問題存在不等式約束，因此，對w，b，ξ求偏導并令其等于零，得：

將公式（3）代入公式（2），那么該問題就轉化為求最大化下面函數（尋優函數）：

選取核函數K（xi，xj）求解最優化問題：

這是一個標準的二次規劃問題 （Quadratic Programming，QP），再根據KKT條件，最優解滿足，

其中SV表示支持向量。

最后的決策函數為：

1.2K-均值聚類算法

K-均值聚類算法屬于聚類方法中一種應用最廣泛的劃分算法，它以K為聚類類別數，把n個對象劃分為k個簇，從而使類內間高內聚，類間低耦合。其主要過程如下：

（1）給定點集X=｛x1，x2，…，xl｝，X∈Rn，并給定簇數K，選取精度ε＞0，置m=0。假設選取前K個初始聚類中心為：。

2　算法設計

從上述公式（7）可以直觀地看出，支持向量的多少將決定SVM分類過程的計算量的大小。傳統的SVM分類函數中包含了全部的支持向量，以致于其分類速度必然較慢，所以提高分類速度的關鍵就在于減少SV的數量。那么該如何減少SV的數量？因此，本文提出將K-均值聚類算法引入支持向量機算法中，其基本思想如下：

3　實驗結果及分析

為了驗證本文算法的分類性能，選取UCI標準數據集［10］上的The Insurance Company Benchmark（COIL 2000）作為實驗所用的數據。該數據集包含了7822個保險公司客戶的記錄，每個記錄由86個屬性組成，包含社會人口數據（屬性1-43）和產品的所有關系（屬性44-86）。社會人口數據是由派生郵政編碼派生而來的，生活在具有相同郵政編碼地區的所有客戶都具有相同的社會人口屬性。其中5822個客戶的記錄作為訓練樣本集，2000個客戶的記錄作為測試樣本集，將本文算法與標準SVM算法進行了對比。實驗中選擇了徑向基函數（RBF）作為分類器的核函數，支持向量機的懲罰因子C=500，訓練后得到的支持向量個數為1333。并且重復10折交叉驗證法［11］對比實驗：在標準SVM訓練得到支持向量的基礎上，調節本文算法中的壓縮比l2/l1及相關系數，使得該算法在保持分類精度差異較原始SVM不明顯的前提下，盡量減少支持向量，加快分類速度。對比實驗結果參見表1。

從表1的實驗結果可以看出，相對于傳統SVM算法，在保持分類精度無顯著差異的前提下，本文改進的算法通過調節部分參數使分類函數中的支持向量數盡可能達到最少，從而在分類時間上明顯比標準SVM快；從改進前后速度比較來看，本文提出的方法分類速度最高提高了47.03%。

4　結語

本文從對標準SVM訓練后得到的支持向量集，并按照特定比例壓縮的方法來減小分類的時間，提高支持向量機的分類速度這一思路出發。提出了一種新的改進的支持向量機算法，該算法使用K-均值聚類算法通過特定比例對原始支持向量集進行壓縮，以此來得到新的稀疏化后的支持向量集，然后按照誤差最小原則重新構造了一個新的分類決策函數，從而使計算量減少到最小，使分類速度提高。通過實驗對比，本文算法比傳統支持向量機算法具有更好的實用性，尤其是在數據規模較大或者是支持向量數量較多的情況下，其分類效果會更加明顯。

表1　實驗對比結果

［1］Vapnik V.The Nature of Statistical Learning Theory［M］.New York：Springer-Verlag，1995.

［2］Platt J C.Fast training of Support Vector Machines Using Sequential Minimal Optimization.Advances in Kernel Methods Support Vector Learning，California，USA，1999∶185-208.

［3］Suykens J A K，Vandewalle J.Least Squares Support Vector Machine Classifiers.Neural Processing Letters，1999，9（3）∶293-300.

［4］KEERT HIS，GILBERTE.Convergence of a Generalized SMO Algorithm for SVM Classifier Design［J］.Machine Learning，2002，46（1 /3）∶3 51-36 0

［5］韓德強，韓崇昭，楊藝.基于K-最近鄰的支持向量預選取方法.控制與決策，2009，24（4）∶494-498

［6］LEE Y J，MANGASARIAN O L.RSVM∶Reduced Support Vector Machines［R］.Wisconsin∶Data Mining Institute，Computer Sciences Department，University of Wisconsin，2000.

［7］Burges C J C and Sch？lkopf B.Simplified Support Vector Decision Rules.In 13th International Conference on Machine Learning，Bari，Italy 1996∶71-77.

［8］Sch?lkopf B，Smola A J，Williamson R C，et al.New Support Vector Algorithms.Neural Computation，2000，12（5）∶1207-1245.

［9］劉向東，陳兆乾.一種快速支持向量機分類算法的研究.計算機研究與發展，2004，41（8）∶1327-1332.

［10］Frank A，Asuncion A.UCI Machine Learning Repository.Http∶//www.ics.uci.edu.html，2007.

［11］Kohavi R.A study of Cross-Validation and Bootstrap Foraccuracy Estimation and Model Selection［C］.Proc 14th Joint Int.Conf.Artificial Intelligence.San Mateo，CA：Morgan Kaufmann，1995：1137-1145.

Support Vector Machine；Support Vectors；K-Means Clustering；Quadratic Programming（QP）

Research on Support Vector Machine and K-means Clustering Fusion Algorithm

TIAN Fei，YU Wei-wei
（Shanghai Maritime University，Shanghai 201306）

The traditional classification algorithm of support vector machine（SVM）as the sample size increases，the increase in the number of support vectors（SVs），the classification process consumes time will also increase.Therefore，proposes an improved algorithm K-mean clustering algorithm and SVM fusion.The standard SVM training support vector specific proportion of the K-means clustering and the cluster center as a new support vector，uses quadratic programming method to solve the obtained new support vector coefficients.Experimental results show that the classification algorithm can effectively reduce the computing time and improve the classification speed，especially in the case of large training set size and the number of support vectors，the effect is more obvious.

1007-1423（2016）20-0035-04

10.3969/j.issn.1007-1423.2016.20.007

田飛（1990-），男，安徽六安人，碩士研究生，研究方向為數字圖像處理，模式識別

于威威（1978-），女，山東淄博人，博士研究生，副教授，研究方向為模式識別、計算機圖像處理、數據挖掘等

2016-04-12

2016-07-10