田飛，于威威（上海海事大學(xué)，上?！?01306）

支持向量機(jī)與K-均值聚類(lèi)融合算法的研究

田飛，于威威
（上海海事大學(xué)，上海201306）

傳統(tǒng)的支持向量機(jī)分類(lèi)算法隨著樣本規(guī)模增大、支持向量數(shù)量增多時(shí)，其分類(lèi)過(guò)程所消耗的時(shí)間也會(huì)隨之增加。為此，提出一種改進(jìn)算法，將K-均值聚類(lèi)算法與支持向量機(jī)融合。將標(biāo)準(zhǔn)支持向量機(jī)訓(xùn)練后得到的支持向量集進(jìn)行特定比例的K均值聚類(lèi)操作，把聚類(lèi)的中心作為新的支持向量，再用二次規(guī)劃方法求解得到新的分類(lèi)決策函數(shù)。實(shí)驗(yàn)結(jié)果表明，該分類(lèi)算法有效地減少計(jì)算時(shí)間，提高分類(lèi)速度，尤其在訓(xùn)練集規(guī)模龐大、支持向量數(shù)量較多的情況下，效果會(huì)更加明顯。

支持向量機(jī)；支持向量；K均值聚類(lèi)；二次規(guī)劃

0　引言

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

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

1　原理概述

1.1支持向量機(jī)算法

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

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

為了解決約束最優(yōu)化問(wèn)題并轉(zhuǎn)化為其對(duì)偶問(wèn)題，引入式（2）所示的拉格朗日函數(shù)：

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

將公式（3）代入公式（2），那么該問(wèn)題就轉(zhuǎn)化為求最大化下面函數(shù)（尋優(yōu)函數(shù)）：

選取核函數(shù)K（xi，xj）求解最優(yōu)化問(wèn)題：

這是一個(gè)標(biāo)準(zhǔn)的二次規(guī)劃問(wèn)題 （Quadratic Programming，QP），再根據(jù)KKT條件，最優(yōu)解滿(mǎn)足，

其中SV表示支持向量。

最后的決策函數(shù)為：

1.2K-均值聚類(lèi)算法

K-均值聚類(lèi)算法屬于聚類(lèi)方法中一種應(yīng)用最廣泛的劃分算法，它以K為聚類(lèi)類(lèi)別數(shù)，把n個(gè)對(duì)象劃分為k個(gè)簇，從而使類(lèi)內(nèi)間高內(nèi)聚，類(lèi)間低耦合。其主要過(guò)程如下：

（1）給定點(diǎn)集X=｛x1，x2，…，xl｝，X∈Rn，并給定簇?cái)?shù)K，選取精度ε＞0，置m=0。假設(shè)選取前K個(gè)初始聚類(lèi)中心為：。

2　算法設(shè)計(jì)

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

3　實(shí)驗(yàn)結(jié)果及分析

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

從表1的實(shí)驗(yàn)結(jié)果可以看出，相對(duì)于傳統(tǒng)SVM算法，在保持分類(lèi)精度無(wú)顯著差異的前提下，本文改進(jìn)的算法通過(guò)調(diào)節(jié)部分參數(shù)使分類(lèi)函數(shù)中的支持向量數(shù)盡可能達(dá)到最少，從而在分類(lèi)時(shí)間上明顯比標(biāo)準(zhǔn)SVM快；從改進(jìn)前后速度比較來(lái)看，本文提出的方法分類(lèi)速度最高提高了47.03%。

4　結(jié)語(yǔ)

本文從對(duì)標(biāo)準(zhǔn)SVM訓(xùn)練后得到的支持向量集，并按照特定比例壓縮的方法來(lái)減小分類(lèi)的時(shí)間，提高支持向量機(jī)的分類(lèi)速度這一思路出發(fā)。提出了一種新的改進(jìn)的支持向量機(jī)算法，該算法使用K-均值聚類(lèi)算法通過(guò)特定比例對(duì)原始支持向量集進(jìn)行壓縮，以此來(lái)得到新的稀疏化后的支持向量集，然后按照誤差最小原則重新構(gòu)造了一個(gè)新的分類(lèi)決策函數(shù)，從而使計(jì)算量減少到最小，使分類(lèi)速度提高。通過(guò)實(shí)驗(yàn)對(duì)比，本文算法比傳統(tǒng)支持向量機(jī)算法具有更好的實(shí)用性，尤其是在數(shù)據(jù)規(guī)模較大或者是支持向量數(shù)量較多的情況下，其分類(lèi)效果會(huì)更加明顯。

表1　實(shí)驗(yàn)對(duì)比結(jié)果

［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］韓德強(qiáng)，韓崇昭，楊藝.基于K-最近鄰的支持向量預(yù)選取方法.控制與決策，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］劉向東，陳兆乾.一種快速支持向量機(jī)分類(lèi)算法的研究.計(jì)算機(jī)研究與發(fā)展，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-），男，安徽六安人，碩士研究生，研究方向?yàn)閿?shù)字圖像處理，模式識(shí)別

于威威（1978-），女，山東淄博人，博士研究生，副教授，研究方向?yàn)槟Ｊ阶R(shí)別、計(jì)算機(jī)圖像處理、數(shù)據(jù)挖掘等

2016-04-12

2016-07-10