基于模糊核聚類?；牧６戎С窒蛄繖C(jī)

黃華娟，韋修喜，周永權(quán),2

（1.廣西民族大學(xué) 信息科學(xué)與工程學(xué)院，廣西 南寧 530006; 2.廣西民族大學(xué) 廣西高校復(fù)雜系統(tǒng)與智能計(jì)算重點(diǎn)實(shí)驗(yàn)室，廣西 南寧 530006）

支 持 向量 機(jī)(support vector machine, SVM)自1995 年由Vapnik 提出以來就受到理論研究和工程應(yīng)用2 方面的重視，是機(jī)器學(xué)習(xí)的一個(gè)研究方向和熱點(diǎn)，已經(jīng)成功應(yīng)用到很多領(lǐng)域中[1-3]。SVM 的基本算法是一個(gè)含有不等式約束條件的二次規(guī)劃(quadratic programming problem, QPP)問題，然而，如果直接求解QPP 問題，當(dāng)數(shù)據(jù)集較大時(shí)，算法的效率將會(huì)下降，所需內(nèi)存量也會(huì)增大[4-8]。因此，如何克服SVM 在處理大規(guī)模數(shù)據(jù)集時(shí)的效率低下問題，一直是學(xué)者們研究的熱點(diǎn)。

為了更好地解決大規(guī)模樣本的分類問題，基于粒度計(jì)算理論[9-10]和統(tǒng)計(jì)學(xué)習(xí)理論的思想，Tang 等于2004 年首次提出粒度支持向量機(jī)(granular support vector machine, GSVM)這個(gè)術(shù)語。GSVM 的總體思想是在原始空間將數(shù)據(jù)集進(jìn)行劃分，得到數(shù)據(jù)粒。然后提取出有用的數(shù)據(jù)粒，并對(duì)其進(jìn)行SVM 訓(xùn)練[11-12]。與傳統(tǒng)支持向量機(jī)相比，GSVM 學(xué)習(xí)機(jī)制具有以下優(yōu)點(diǎn)：針對(duì)大樣本數(shù)據(jù)，通過數(shù)據(jù)粒化和對(duì)有用粒子(支持向量粒)的提取，剔除了無用冗余的樣本，減少了樣本數(shù)量，提高了訓(xùn)練效率。然而，Tang 只是給出了GSVM 學(xué)習(xí)模型的一些設(shè)想，沒有給出具體的學(xué)習(xí)算法。2009 年，張?chǎng)蝃13]在 Tang 提出的GSVM 思想的基礎(chǔ)上，構(gòu)建了一個(gè)粒度支持向量機(jī)的模型，并對(duì)其學(xué)習(xí)機(jī)制進(jìn)行了探討。此后，許多學(xué)者對(duì)支持向量機(jī)和粒度計(jì)算相結(jié)合的具體模型進(jìn)行了研究，比如模糊支持向量機(jī)[13]、粗糙集支持向量機(jī)[14]、決策樹支持向量機(jī)[15]和商空間支持向量機(jī)[16]等。但這些模型的共同點(diǎn)都是在原始空間直接劃分?jǐn)?shù)據(jù)集，然后再映射到高維空間進(jìn)行SVM 學(xué)習(xí)。然而，這種做法很有可能丟失了大量包含有用信息的數(shù)據(jù)粒，其學(xué)習(xí)算法的性能會(huì)受到影響。為此，本文采用模糊核聚類的方法將樣本直接在核空間進(jìn)行粒的劃分和提取，然后在相同的核空間進(jìn)行GSVM 訓(xùn)練，這樣保證了數(shù)據(jù)分布的一致性，提高了算法的泛化能力。最后，在標(biāo)準(zhǔn)UCI 數(shù)據(jù)集和NDC大數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果表明，本文算法是可行的且效果更好。

1 粒度支持向量機(jī)

張?chǎng)蝃17]在Tang 提出的GSVM 思想的基礎(chǔ)上，構(gòu)建了一個(gè)粒度支持向量機(jī)的模型。

設(shè)給定數(shù)據(jù)集為X={(xi,yi),i=1,2,···,n} ，n為樣本的個(gè)數(shù)；yi為xi所屬類的標(biāo)簽。采用粒度劃分的方法(聚類、粗糙集、關(guān)聯(lián)規(guī)則等)劃分X，若數(shù)據(jù)集有l(wèi)個(gè)類，則將X分成l個(gè)粒，表示為：

若每 個(gè)粒包含li個(gè)點(diǎn) ，Yi表示第i個(gè)粒的類別，則有：

其中：

則在GSVM 中，最優(yōu)化問題變?yōu)椋?/p>

將上述問題根據(jù)最優(yōu)化理論轉(zhuǎn)化為其對(duì)偶問題：

當(dāng)數(shù)據(jù)集是線性不可分時(shí)，GSVM 不是在原始空間構(gòu)造最優(yōu)分類面，而是映射到高維特征空間，然后再進(jìn)行構(gòu)造，具體為：

將X從 Rn變換到 Φ：

以特征向量 Φ (X) 代替輸入向量X，則可以得到最優(yōu)分類函數(shù)為：

利用核函數(shù)來求解向量的內(nèi)積，則最優(yōu)分類函數(shù)變?yōu)椋?/p>

其中，k(Xi,X) 為粒度核函數(shù)。當(dāng)ai＞0，根據(jù)以上分析，可知Xi是支持向量。顯然地，式(5)的形式和SVM 的最優(yōu)分類函數(shù)很一致，確保了最優(yōu)解的唯一性。

2 基于模糊核聚類?；牧６戎С窒蛄繖C(jī)

2.1 問題的提出

在研究中發(fā)現(xiàn)，只有支持向量才對(duì)SVM 的訓(xùn)練起積極作用，它們是非常重要的，對(duì)于SVM 是不可或缺的，而其余的非支持向量對(duì)于分類超平面是不起作用的，甚至可能產(chǎn)生負(fù)面影響，比如增加了核矩陣的容量，降低了SVM 的效率。GSVM 也存在同樣的問題，只有支持向量粒才對(duì)GSVM 的訓(xùn)練起決定性作用?？梢酝ㄟ^理論證明來說明這個(gè)觀點(diǎn)的正確性。

定理1粒度支持向量機(jī)的訓(xùn)練過程和訓(xùn)練結(jié)果與非支持向量粒無關(guān)。

證明定義Isv={i|al＞0} 和Insv={i|al=0} 分別為支持向量粒和非支持向量粒對(duì)應(yīng)樣本序號(hào)的索引集，支持向量粒的個(gè)數(shù)記為l′。引入只優(yōu)化支持向量粒對(duì)應(yīng)樣本的問題

要證明定理1，只需要證明式(2)和式(6)同解。用反正法，假設(shè)式(6)存在一個(gè)最優(yōu)解a′使得g(a′)＞g(a?) 。由于a?是式(2)的最優(yōu)解，也即a?是式(6)的可行解，同樣，a′也是式(2)的可行解。由于a?是式(2)的最優(yōu)解，可得w(a?)＞w(a′)。又因?yàn)?/p>

可 得w(a′)=g(a′)＞g(a?)=w(a?) ， 即w(a′)＞w(a?)，這與a?是式(2) 的最優(yōu)解得出的w(a?)＞w(a′) 相矛盾。定理1 得證。注：a′是l′維向量，代入w的時(shí)候拓展為l維向量。

要想迅速地得到支持向量粒，節(jié)省?；臅r(shí)間，首先了解支持向量的特征，文獻(xiàn)[13]對(duì)其特征做了歸納總結(jié)。

1)現(xiàn)實(shí)中，支持向量一般都是稀疏地聚集在訓(xùn)練數(shù)據(jù)集的邊緣。

2)根據(jù)第一個(gè)特征，則每個(gè)類中心附近的數(shù)據(jù)不會(huì)是支持向量，即，離支持向量機(jī)超平面較近的數(shù)據(jù)比較可能是支持向量，這就為支持向量的選取提供了快速的獲取方法。

2.2 問題分析

圖1 中，紅色部分的數(shù)據(jù)是GSVM 的支持向量粒，它們決定了分類超平面。并且從中可以看出，對(duì)于每一類，離類中心越遠(yuǎn)的點(diǎn)，就越有可能是支持向量粒。并且，從圖1 中還可以看出，落在每一個(gè)環(huán)上的樣本，它們離類中心的距離差不多相等。 離類中心越遠(yuǎn)的環(huán)就越有可能含有多的支持向量粒?；谶@個(gè)思想，本文先把樣本映射到核空間，按類標(biāo)簽的個(gè)數(shù)進(jìn)行粗粒劃分，確保相同標(biāo)簽的樣本都在同一個(gè)粗粒中。 然后，對(duì)于每一個(gè)粗粒，采用模糊聚類的方法進(jìn)行?；?，具有相同隸屬度的樣本歸為一個(gè)粒，進(jìn)行細(xì)粒劃分。 每一個(gè)細(xì)粒就對(duì)應(yīng)圖1 中的一個(gè)環(huán)，從圖中可以看出，離粗粒中心越遠(yuǎn)的環(huán)，越靠近分類超平面，其是支持向量粒的可能性越大。而離粗粒中心越遠(yuǎn)的環(huán)，其隸屬度越小。因此，給定一個(gè)閾值，當(dāng)細(xì)粒的隸屬度小于給定的閾值，就說明其處于粗粒的邊緣，是支持向量粒，進(jìn)而提取出支持向量粒.

圖1 支持向量分布圖Fig.1 The distribution of support vectors

2.3 模糊核聚類

模糊核聚類(fuzzy kernel cluster, FKC)的主要思想是先將數(shù)據(jù)集映射到高維空間，然后直接在高維空間進(jìn)行模糊聚類。而一般的聚類算法是直接在原始空間進(jìn)行聚類劃分。與其他的聚類算法相比，模糊核聚類引入了非線性映射，能夠在更大程度上提取到有用的特征，聚類的效果會(huì)更好。

設(shè)原空間樣本集為X=(x1,x2,···,xN)，xj∈Rd，j=1,2,···,N。 核非線性映射為?:x→?(x)，在本文中，采用Euclid 距離作為距離測(cè)量方法，由此得到模糊核C-均值聚類：

式中：C是事先確定的簇?cái)?shù)；m∈(1,∞) 是模糊加權(quán)指數(shù)，對(duì)聚類的模糊程度有重要的調(diào)節(jié)作用；vi為第i類的類中心； ?(vi) 為該中心在相應(yīng)核空間中的像。

按模糊C-均值優(yōu)化方法，隸屬度設(shè)計(jì)為

且有

為了最小化目標(biāo)函數(shù)，需要計(jì)算k(xj,vi) 和k(vi,vi) ，由k(xi,xj)=＜ ?(xi),?(xj)＞ 可得：

把式(9)～(11)代入式(7)，可以求出模糊核C-均值聚類的目標(biāo)函數(shù)值。

模糊核C-均值聚類的算法步驟如下：

1) 初始化參數(shù)： ε、m、T和C；

2) 對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行預(yù)處理；

3) 設(shè)置vi(i=1,2,···,C) 的初始值；

4)計(jì)算隸屬度uij(i=1,2,···,C;j=1,2,···,N)；

5) 計(jì)算新的k(xj,vi) 和k(vi,vi)， 更新隸屬度uij為

2.4 FKC-GSVM 的算法步驟

目前，已有的粒度支持向量機(jī)算法模型大都是直接在原始空間對(duì)數(shù)據(jù)集進(jìn)行?；吞崛?，然后映射到核空間進(jìn)行SVM 的訓(xùn)練。然而，不同空間的轉(zhuǎn)換，很有可能丟失了數(shù)據(jù)集的有用信息，降低學(xué)習(xí)器的性能。為了避免因數(shù)據(jù)在不同空間分布不一致而導(dǎo)致泛化能力不高的問題，本文采用模糊核聚類的方法直接在核空間對(duì)數(shù)據(jù)集進(jìn)行?；?、提取和SVM 的訓(xùn)練?；谝陨纤枷耄疚奶岢隽嘶谀：司垲惲；牧６戎С窒蛄繖C(jī)(fuzzy kernel cluster granular support vector machine, FKC-GSVM)。FKC-GSVM 算法包括3 部分：采用模糊核聚類進(jìn)行粒度的劃分；設(shè)定閾值，當(dāng)每個(gè)粒子的隸屬度大于規(guī)定的閾值時(shí)，認(rèn)為這個(gè)粒子為非支持向量粒，丟棄，而剩余的粒子為支持向量粒；在核空間對(duì)支持向量粒進(jìn)行SVM訓(xùn)練。具體的算法步驟如下：

1) 粗粒劃分：以類標(biāo)簽個(gè)數(shù)l為粒子個(gè)數(shù)，對(duì) 訓(xùn)練樣本進(jìn)行粗粒的劃分，得到l個(gè)粒子；

2) 細(xì)粒劃分：采用模糊核聚類分別對(duì)l個(gè)粒子進(jìn)行細(xì)粒劃分，計(jì)算每個(gè)粒子的隸屬度；

3) 支持向量粒的提?。航o定一個(gè)閾值，當(dāng)一個(gè)粒子的隸屬度小于給定的閾值，提取這個(gè)粒子(支持向量粒)，提取出來的支持向量粒組成了一個(gè)新的訓(xùn)練集；

4) 支持向量集的訓(xùn)練：在新的訓(xùn)練樣本集上進(jìn)行GSVM 訓(xùn)練；

5) 泛化能力的測(cè)試：利用測(cè)試集測(cè)試泛化能力。

2.5 FKC-GSVM 算法性能分析

下面，從2 個(gè)方面對(duì)FKC-GSVM 的算法性能進(jìn)行分析：

1) FKC-GSVM 的收斂性分析

與SVM 相比，F(xiàn)KC-GSVM 采用核空間代替原始空間進(jìn)行粒化，提取出支持向量粒后在相同的核空間進(jìn)行GSVM 訓(xùn)練，其訓(xùn)練的核心思想依然是采用支持向量來構(gòu)造分類超平面，這與標(biāo)準(zhǔn)支持向量機(jī)相同。既然標(biāo)準(zhǔn)支持向量機(jī)是收斂的，則FKC-GSVM 也是收斂的。但是由于FKCGSVM 剔除了大量對(duì)訓(xùn)練不起積極作用的非支持向量，直接采用支持向量來訓(xùn)練，所以它的收斂速度要快于標(biāo)準(zhǔn)支持向量機(jī)。

2) FKC-GSVM 的泛化能力分析

評(píng)價(jià)一個(gè)學(xué)習(xí)器性能好壞的重要指標(biāo)是其是否具有較強(qiáng)的泛化能力。眾所周知，由于SVM采用結(jié)構(gòu)風(fēng)險(xiǎn)最小(SRM)歸納原則，因此，與其他學(xué)習(xí)機(jī)器相比，SVM 的泛化能力是很突出的。同樣，F(xiàn)KC-GSVM 也執(zhí)行了SRM 歸納原則，并且直接在核空間選取支持向量，確保了數(shù)據(jù)的一致性，具有更好的泛化性能。

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

3.1 UCI 數(shù)據(jù)集上的實(shí)驗(yàn)

為了驗(yàn)證FKC-GSVM 的學(xué)習(xí)性能，本文在Matlab7.11 的環(huán)境下對(duì)5 個(gè)常用的UCI 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，這5 個(gè)數(shù)據(jù)集的描述如表1 所示。在實(shí)驗(yàn)中，采用的核函數(shù)為高斯核函數(shù)，并且采用交叉驗(yàn)證方法選取懲罰參數(shù)C和核參數(shù) σ ， 聚類數(shù)c設(shè)為20。影響算法表現(xiàn)的主要因素是閾值k的設(shè)定，為此，對(duì)不同的閾值對(duì)算法的影響進(jìn)行了分析。

數(shù)據(jù)集 Abalone Contraceptive Method Choice Pen-Based Recognition of Hand-written Digits NDC-10k NDC-1l#訓(xùn)練集 3 177 1 000 6 280 10 000 100 000#測(cè)試集 1 000 473 3 498 1 000 10 000維度 8 9 16 32 32

為了比較數(shù)據(jù)集在原空間?；驮诤丝臻g?；牟煌Ч疚牟捎没谀：垲惖牧６戎С窒蛄繖C(jī)(FCM-GSVM)、基于模糊核聚類的粒度支持向量機(jī)(FKC-GSVM)和粒度支持向量機(jī)(GSVM)等3 種算法對(duì)5 個(gè)典型的UCI 數(shù)據(jù)集進(jìn)行了 測(cè)試，測(cè)試結(jié)果如表2 所示。為了更直觀地看出FKC-GSVM 在不同閾值條件下的分類效果，給出了Contraceptive Method Choice 數(shù)據(jù)集在不同閾值條件下采用FKC-GSVM 分類的效果圖，如圖2～圖5 所示。

表2 FCM-GSVM 與FKC-GSVM 測(cè)試結(jié)果比較Table 2 Comparison of test results between FCM-GSVM and FKC-GSVM%

FCM-GSVM 和GSVM 是在原空間進(jìn)行粒度劃分和支持向量粒的提取，然后把支持向量粒映射到高維空間進(jìn)行分類，而FKC-GSVM 是直接在核空間進(jìn)行粒度劃分和支持向量粒的提取，然后在相同的核空間進(jìn)行分類。從表2 的測(cè)試結(jié)果可以看出，由于FCM-GSVM 和GSVM 可能導(dǎo)致數(shù)據(jù)在原空間和核空間分布不一致，在相同的閾值條件下，其分類效果要比FKC-GSVM 的分類效果差，這說明FKC-GSVM 的泛化能力比FCM-GSVM 的泛化能力強(qiáng)。

為了分析在不同閾值條件下FKC-GSVM 的泛化性能，本文給出了0.9、0.85、0.8、0.75 四個(gè)不同閾值條件下的實(shí)驗(yàn)。從表2 可以看出，閾值越小，F(xiàn)KC-GSVM 的分類效果越差，這是因?yàn)殚撝翟叫?，選取的支持向量粒就越少，這一過程可能丟失了一些支持向量，影響了分類效果。但是閾值越小，大大壓縮了訓(xùn)練樣本集，算法訓(xùn)練的速度得到了很大的提高。因此，對(duì)于大規(guī)模樣本來說，只要在能接受的分類效果的范圍內(nèi)，選取合適的閾值，采用FKC-GSVM 就能快速地得到需要的分類效果。圖2～5 是Contraceptive Method Choice 數(shù)據(jù)集在不同閾值條件下采用FKC-GSVM 分類的效果圖，從這幾個(gè)圖中可以很直觀地看出，F(xiàn)KC-GSVM 的分類效果還是比較令人滿意的。

圖2 FKC-GSVM 在閾值為0.9 條件下的分類效果Fig.2 The classification results of FKC-GSVM under the threshold 0.9

圖3 FKC-GSVM 在閾值為0.85 條件下的分類效果Fig.3 The classification results of FKC-GSVM under the threshold 0.85

圖4 FKC-GSVM 在閾值為0.8 條件下的分類效果Fig.4 The classification results of FKC-GSVM under the threshold 0.8

圖5 FKC-GSVM 在閾值為0.75 條件下的分類效果Fig.5 The classification results of FKC-GSVM under the threshold 0.75

3.2 NDC 大數(shù)據(jù)集上的實(shí)驗(yàn)

為了測(cè)試FKC-GSVM 處理大數(shù)據(jù)集的性能，在實(shí)驗(yàn)中，采用的數(shù)據(jù)集是NDC 大數(shù)據(jù)集[20]，是由David Musicant’s NDC 數(shù)據(jù)產(chǎn)生器產(chǎn)生的，NDC 數(shù)據(jù)集的描述如表3 所示。在實(shí)驗(yàn)中，F(xiàn)KCGSVM 的測(cè)試結(jié)果將與現(xiàn)在比較流行的孿生支持向量機(jī)(twin support vector machines, TWSVM)的測(cè)試結(jié)果[20]從測(cè)試精度和運(yùn)行時(shí)間2 方面進(jìn)行對(duì)比。其中，F(xiàn)KC-GSVM 的運(yùn)行環(huán)境、參數(shù)設(shè)置方法和實(shí)驗(yàn)3.1 一樣，閾值k= 0.9；TWSVM 的懲罰參數(shù)和核參數(shù)的選取都是從 {2-8,2-7,···,27} 這個(gè)范圍內(nèi)采用網(wǎng)格搜索算法進(jìn)行選擇。表4 顯示的是FKC-GSVM 和TWSVM 兩種算法的運(yùn)行結(jié)果。

表3 實(shí)驗(yàn)采用的NDC 數(shù)據(jù)集Table 3 NDC datasets used in experiments

表4 2 種算法對(duì)NDC 數(shù)據(jù)集的測(cè)試結(jié)果Table 4 Comparison of two algorithms on NDC datasets

從表3 中可以看出，本實(shí)驗(yàn)測(cè)試的對(duì)象為5 種數(shù)據(jù)集，NDC-3L 的訓(xùn)練樣本數(shù)為300 000 個(gè)，而NDC-1m 的樣本增加到了1 000 000 個(gè)，同樣，測(cè)試樣本也從30 000 增加到了100 000，特征數(shù)都是32 維。這3 個(gè)數(shù)據(jù)集主要是為了測(cè)試算法在處理維度一樣而數(shù)據(jù)量不斷增加時(shí)候的學(xué)習(xí)性能。為了進(jìn)一步測(cè)試學(xué)習(xí)算法處理高維樣本的性能，NDC1 和NDC2 這2 個(gè)數(shù)據(jù)集的維數(shù)分別是100 和1 000，設(shè)置他們的訓(xùn)練樣本量和測(cè)試樣本量都一樣，都是5 000。

實(shí)驗(yàn)結(jié)果如表4 所示，從中可以看出，當(dāng)數(shù)據(jù)集為NDC-1m 時(shí)，由于訓(xùn)練時(shí)間過高，采用TWSVM 算法無法將實(shí)驗(yàn)進(jìn)行下去。然而，F(xiàn)KC-GSVM 在處理NDC-1m 數(shù)據(jù)集時(shí)能夠在合理的運(yùn)行時(shí)間內(nèi)得到較滿意的精度解，這表明了FKC-GSVM 在處理大數(shù)據(jù)時(shí)是具有優(yōu)勢(shì)的。同樣，在處理NDC1 和NDC2 這2 個(gè)高維數(shù)據(jù)集時(shí)，從表4可以明顯看出，F(xiàn)KC-GSVM 處理高維數(shù)據(jù)的效果也是不錯(cuò)的。實(shí)驗(yàn)結(jié)果充分說明了FKC-GSVM 的學(xué)習(xí)能力比TWSVM 的強(qiáng)，更適合于處理大數(shù)據(jù)集。

4 結(jié)束語

GSVM 是將訓(xùn)練樣本在原空間?；笤儆成涞胶丝臻g，這將導(dǎo)致數(shù)據(jù)與原空間的分布不一致，從而降低了GSVM 的泛化能力。為了解決這個(gè)問題，本文提出了一種基于模糊核聚類?；牧６戎С窒蛄繖C(jī)方法(FKC-GSVM)。FKC-GSVM 通過利用模糊核聚類直接在核空間對(duì)數(shù)據(jù)進(jìn)行粒的劃分和支持向量粒的選取，然后在相同的核空間中進(jìn)行支持向量粒的GSVM 訓(xùn)練，在標(biāo)準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)說明了FKC-GSVM 算法的有效性。但是閾值參數(shù)的選取仍具有一定的隨意性，影響了FKC-GSVM 的性能。如何自適應(yīng)地調(diào)整合適的閾值，將是下一步要研究的工作內(nèi)容。