基于層次聚類(lèi)的支持向量機(jī)分類(lèi)算法

李兵 田元 趙明華 李劍波

摘要

針對(duì)支持向量機(jī)在大規(guī)模樣本學(xué)習(xí)時(shí)，學(xué)習(xí)速度慢，需要存儲(chǔ)空間大等問(wèn)題，提出了一種基于層次聚類(lèi)的支持向量機(jī)訓(xùn)練算法，即在標(biāo)準(zhǔn)SVM向量算法中加入CURE聚類(lèi)算法。該方法首先通過(guò)聚類(lèi)方法從簇中選擇分散的對(duì)象，根據(jù)一個(gè)收縮因子收縮或移動(dòng)它們，從而產(chǎn)生最有可能成為支持向量的一組向量組成訓(xùn)練子集，接下來(lái)再用SVM訓(xùn)練方法構(gòu)建一個(gè)最優(yōu)SVM分類(lèi)器。實(shí)驗(yàn)證明，該算法使SVM訓(xùn)練時(shí)間大為縮短，在不影響精確度的前提下使算法的效率得到大幅度的提高。

【關(guān)鍵詞】支持向量機(jī) 聚類(lèi) CURE聚類(lèi)算法

1 引言

支持向量機(jī)理論最早由Vapnik[1]提出，是一種基于統(tǒng)計(jì)學(xué)習(xí)理論中VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小理論的通用學(xué)習(xí)方法。它可以解決小樣本學(xué)習(xí)問(wèn)題，而且對(duì)數(shù)據(jù)的維數(shù)、多變性不敏感，可以實(shí)現(xiàn)多種傳統(tǒng)分類(lèi)方法，能夠較好地進(jìn)行模型選擇，并具有較好的推廣能力。目前已經(jīng)在許多智能信息獲取與處理領(lǐng)域都取得了成功的應(yīng)用[2]。

支持向量機(jī)的算法實(shí)現(xiàn)有賴(lài)于解決一個(gè)二次規(guī)劃問(wèn)題，當(dāng)樣本數(shù)目較多時(shí)，傳統(tǒng)的二次規(guī)劃方法及其軟件在計(jì)算時(shí)間、占用內(nèi)存和計(jì)算精度上都出現(xiàn)問(wèn)題[3]。為了解決這些問(wèn)題，國(guó)內(nèi)外許多科研工作者投入很多的精力來(lái)解決如何快速有效的提高SVM的訓(xùn)練方法。

實(shí)際應(yīng)用中支持向量在樣本訓(xùn)練集中只占一小部分[4]，據(jù)此本文借用聚類(lèi)算法能夠有效減少非支持向量的特點(diǎn)，在分析其它類(lèi)似算法的基礎(chǔ)上，提出了基于層次聚類(lèi)的支持向量機(jī)分類(lèi)算法SVM-HC。該算法同傳統(tǒng)的SVM訓(xùn)練算法相比不僅保持了SVM的訓(xùn)練精度，同時(shí)縮短了訓(xùn)練時(shí)間。

本文第一部分闡述支持向量機(jī)的基本原理;第二部分詳細(xì)介紹基于層次聚類(lèi)的支持向量機(jī)分類(lèi)算法SVM-HC;第三部分介紹實(shí)驗(yàn)結(jié)果;第四部分為結(jié)論。

2 支持向量機(jī)原理

支持向量機(jī)最初用于數(shù)據(jù)分類(lèi)問(wèn)題的處理。下面針對(duì)訓(xùn)練樣本集：兩類(lèi)線性、兩類(lèi)非線性?xún)煞N情況分別加以討論。

對(duì)于兩類(lèi)線性可分問(wèn)題，已知：訓(xùn)練集包含1個(gè)樣本點(diǎn)：

其中x_i是輸入指標(biāo)向量，或稱(chēng)輸入、模式，其分量稱(chēng)為特征，或?qū)傩?、或輸入指?biāo);Y是輸出指標(biāo)，或稱(chēng)輸出。支持向量就是尋求一個(gè)平面ω·x+b=0，使得訓(xùn)練數(shù)據(jù)點(diǎn)距離這個(gè)平面盡量的遠(yuǎn)。這種極大化“間隔”的思想導(dǎo)致求解下列對(duì)變量ω和b的最優(yōu)問(wèn)題：

為求解原始問(wèn)題，根據(jù)最優(yōu)化理論，轉(zhuǎn)化為對(duì)偶問(wèn)題來(lái)求解：解上述問(wèn)題后得到的分類(lèi)規(guī)則函數(shù)是：

對(duì)于兩類(lèi)線性不可分問(wèn)題，為第i個(gè)訓(xùn)練點(diǎn)（x_i，y_i）引入松弛變量（Slack Variable）ξ_i≥0，把約束條件放松到y(tǒng)_i{（ω·x_i）+b}+ξ_i≥1，i=1，…n（即“軟化”約束條件）。顯然ξ_i可以描述為訓(xùn)練集錯(cuò)劃的程度?，F(xiàn)在就有兩個(gè)目標(biāo)：希望超平面間隔最大，即（最大），又希望訓(xùn)練集錯(cuò)劃程度盡可能小，所以引入懲罰參數(shù)C。在實(shí)際使用時(shí)，我們可以選擇C來(lái)修改這兩個(gè)目標(biāo)的權(quán)重。這樣新的目標(biāo)函數(shù)成為：體現(xiàn)了經(jīng)驗(yàn)風(fēng)險(xiǎn)，而‖w‖則體現(xiàn)了表達(dá)能力。所以懲罰參數(shù)C實(shí)質(zhì)上是財(cái)經(jīng)驗(yàn)風(fēng)險(xiǎn)和表達(dá)能力匹配一個(gè)裁決。當(dāng)C→∞時(shí)，線性不可分的原始問(wèn)題退化為線性可分。

對(duì)于非線性分類(lèi)，通過(guò)引入核函數(shù)，將原空間樣本數(shù)據(jù)通過(guò)非線性變換映射到高維特征空間H：Φ：R^d→H。在這高維空間中求最優(yōu)或廣義最優(yōu)分類(lèi)面。

常用的核函數(shù)為：

2.1 多項(xiàng)式核函數(shù)

2.2 RBF（徑向基radial basis function）核函數(shù)

2.3 Sigmoid核函數(shù)

K（x，x_i）=tanh（b（x·x_i）-c），式中b，c為常數(shù)。

這樣對(duì)于非線性分類(lèi)問(wèn)題，最終歸結(jié)為一個(gè)二次規(guī)劃問(wèn)題：

3 基于層次聚類(lèi)的支持向量機(jī)分類(lèi)算法

目前，已經(jīng)提出了很多基于聚類(lèi)的算法的。文獻(xiàn)[5]提出的算法可以有效減少訓(xùn)練次數(shù)，但對(duì)于出現(xiàn)兩類(lèi)點(diǎn)集交叉情況較多的時(shí)候，這種方法就會(huì)顯示出它的缺陷[6]。文獻(xiàn)[6]、[7]提出的算法可以有效解決該問(wèn)題并且具有收斂速度快的優(yōu)點(diǎn)。

上面提到算法擅長(zhǎng)處理凸形分布、大小相近、密度相近的聚類(lèi)，但對(duì)于處理形狀比較復(fù)雜的簇還存在不足。另外，初始聚類(lèi)中心的選擇和噪聲數(shù)據(jù)會(huì)對(duì)這些算法產(chǎn)生很大的影響。同時(shí)[6]、[7]的方法為了達(dá)到全局最優(yōu)，會(huì)要求窮舉所有的訓(xùn)練點(diǎn)，對(duì)于大數(shù)據(jù)量的訓(xùn)練集來(lái)說(shuō)將是一個(gè)非常耗時(shí)的過(guò)程。本文受到這些算法的啟發(fā)，借用CURE聚類(lèi)算法[8]的思想提出了基于層次聚類(lèi)支持向量機(jī)。

該算法的核心思想是：首先借用CURE聚類(lèi)算法對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)，通過(guò)聚類(lèi)算法減少非支持向量，從而提高支持向量的訓(xùn)練速度。關(guān)于CRUE聚類(lèi)算法的原理，文獻(xiàn)[8]有詳細(xì)論述，本文不再敘述.

借用CURE聚類(lèi)算法是因?yàn)樵撍惴ň哂幸韵聝?yōu)點(diǎn)：

（1）它不用單個(gè)質(zhì)心來(lái)代表一個(gè)簇，而是選擇數(shù)據(jù)空間中固定數(shù)目的具有代表性的點(diǎn)。這些點(diǎn)是邊界點(diǎn)和質(zhì)心點(diǎn)的折衷，也就是說(shuō)在盡可能減少訓(xùn)練點(diǎn)的基礎(chǔ)上盡可能的發(fā)現(xiàn)任意形狀的類(lèi)，同時(shí)可以有效處理孤立點(diǎn)或噪點(diǎn)[9]。

（2）試驗(yàn)和分析表明[8]，適當(dāng)數(shù)量的隨機(jī)樣本具備一定精度的關(guān)于簇的幾何信息，因此該算法開(kāi)始聚類(lèi)時(shí)隨機(jī)抽取一定數(shù)量的樣本而不是所有樣本進(jìn)行聚類(lèi)，這將會(huì)大幅縮短訓(xùn)練時(shí)間。

（3）通過(guò)收縮因子α和代表點(diǎn)的數(shù)量C就可以調(diào)節(jié)該算法的精度。當(dāng)收縮因子α=1時(shí)，該算法就與[5]的算法性質(zhì)相同，即基于聚類(lèi)中心點(diǎn)的支持向量機(jī)算法;當(dāng)收縮因子α趨于0時(shí)，該算法的性質(zhì)接近[6]的算法，即基于聚類(lèi)邊界點(diǎn)的支持向量機(jī)算法。

下面介紹基于層次聚類(lèi)的支持向量機(jī)分類(lèi)算法：

Stepl：設(shè)置收縮因子α參數(shù)、隨即樣本S的數(shù)量以及劃分聚類(lèi)數(shù)量Ko

Step2：隨機(jī)抽取S個(gè)樣本，并將樣本劃分為p個(gè)部分，每個(gè)部分得數(shù)據(jù)量為S/p。

Step3：在每個(gè)劃分中，劃分S/pq？個(gè)局部聚類(lèi)。

Step4通過(guò)隨機(jī)取樣去除孤立點(diǎn)或噪點(diǎn)。如果一個(gè)簇增長(zhǎng)的太慢，去掉這個(gè)簇。

Steps：對(duì)局部聚類(lèi)進(jìn)行合并。對(duì)每個(gè)新生成簇代表點(diǎn)根據(jù)收縮因子收縮或向簇中心移動(dòng)。

Step6：使用標(biāo)準(zhǔn)SVM訓(xùn)練算法尋找最優(yōu)分類(lèi)超平面

通過(guò)上述分析可以看出，如果減少收縮因子α，那么本文提出的SVM-HC算法在聚類(lèi)階段得到的代表點(diǎn)與文獻(xiàn)[6]提出的SVM-DC算法在聚類(lèi)階段得到的邊緣點(diǎn)都能精確反映簇的位置和形狀。另一方面，SVM-DC算法的復(fù)雜度為O（n（mlogm+1¹）），而本文提出的SVM-HC算法復(fù)雜度為O（n（m+1¹））。這樣可以看出，本文提出SVM-HC算法在保持訓(xùn)練精度的同時(shí)能夠大幅縮小訓(xùn)練時(shí)間。

4 試驗(yàn)結(jié)果及分析

為了驗(yàn)證本文對(duì)基于聚類(lèi)的支持向量機(jī)算法改進(jìn)的有效性，在公共測(cè)試數(shù)據(jù)庫(kù)UCIAdult和Web數(shù)據(jù)集上對(duì)SVM-DC算法、SVM-HC算法進(jìn)行了五組測(cè)試。試驗(yàn)中SVM-HC算法的參數(shù)按照[8]的建議，即抽樣數(shù)s=1，220;分區(qū)數(shù)p=50，代表樣本點(diǎn)數(shù)c=10。綜合考慮訓(xùn)練速度和訓(xùn)練精度，把SVM-DC算法中的參數(shù)設(shè)置為：ε=0.2，0=8，η=0.8。表1給出試驗(yàn)結(jié)果。兩種算法均采用標(biāo)準(zhǔn)C++實(shí)現(xiàn)，使用RBF核函數(shù)：，用Microsott VisualC++6.0，缺省編譯器優(yōu)化選項(xiàng)進(jìn)行編譯。系統(tǒng)平臺(tái)為2.66GHZ Pentium4處理器，Windows2000標(biāo)準(zhǔn)版，256MBRAM。所有算法均沒(méi)有采取任何其它優(yōu)化措施，核函數(shù)均為RBF核函數(shù)：其核參數(shù)的設(shè)置為：σ¹=10，C=1。

如表I所示，從試驗(yàn)結(jié)果可以看出，對(duì)于同一個(gè)樣本數(shù)據(jù)集， SVM-HC利用尋找代表點(diǎn)時(shí)間短的優(yōu)點(diǎn)，有效提高了支持向量機(jī)的訓(xùn)練速度，同時(shí)訓(xùn)練的精確度基本沒(méi)有改變。SVM-HC訓(xùn)練精確度基本在SVM-DC精確度上下小幅浮動(dòng)。根據(jù)理論分析和試驗(yàn)結(jié)果，可以得出SVM-HC的可行性和有效性：即該算法充分利用了CURE聚類(lèi)算法的優(yōu)點(diǎn)，在保證支持向量機(jī)訓(xùn)練算法精度沒(méi)有降低的情況下，有效提高了支持向量機(jī)訓(xùn)練速度。

5 結(jié)論

本文首先介紹了目前幾種基于聚類(lèi)支持向量算法的優(yōu)缺點(diǎn)。分析CRUE聚類(lèi)算法的優(yōu)點(diǎn)，通過(guò)借用其思想提出了SVM-HC算法。實(shí)驗(yàn)表明，這種方法在保持支持向量機(jī)訓(xùn)練精度不改變的情況下明顯縮短學(xué)習(xí)時(shí)間。

參考文獻(xiàn)

[1]Vladimir N.Vapnik.The Nature ofStatistical Learning Theory.Springer，New York，1995.

[2]SANCHEZ A D.Advanced support vectormachines and kernel methods[J].Neurocomput ing，2003，55（01）：5-20

[3]吳翔，譚李.提高大規(guī)模SVM訓(xùn)練計(jì)算速度的研究[J].模式識(shí)別與人工智能，2003，16（01）：46-49.

[4]Joachims T.Making Large-scale SupportVector Machine Learning Practical[A].B Scholkoph，C B urges，A Smola.Advances in Kernel Methods SupportVector Learning[C].Cambridge.MA：MITPress，1999，169-184.

[5]李曉黎，劉繼敏，史忠植.基于支持向量機(jī)與無(wú)監(jiān)督聚類(lèi)相結(jié)合的中文網(wǎng)頁(yè)分類(lèi)器[J].計(jì)算機(jī)學(xué)報(bào)，2002，24（01）：62-68.

[6]武方方，趙銀亮，蔣澤飛.基于密度聚類(lèi)的支持向量機(jī)分類(lèi)算法[J].西安交通大學(xué)學(xué)報(bào)，2005（12）.

[7]孔波，劉小茂，張鈞.基于中心距離比值的增量支持向量機(jī)[J].計(jì)算機(jī)應(yīng)用，2006（06）.

[8]Guha S，Rastogi R，Shim K.CURE：AnEfficient Clustering Algorithmfor Large Databases[C].Seattle：Proceedings of the ACM SIGMODConference，1998：73-84.

[9]Jiawei Ha n，Micheline Kamber.DateMining：concepts and Techniques [M].Copyright 2001 by Morgan KaufmannPublishers，Inc.，2001.

[10]Murphy P M，Aha Irvine D W.CA：University of California，Departmentof Information and ComputerScience[EB/OL].http：//www.ics.uci.edu/～mlearn/MLRepository.html，1994.