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

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

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

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

1 粒度支持向量機

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

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

若每 個粒包含li個點 ，Yi表示第i個粒的類別，則有：

其中：

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

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

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

將X從 Rn變換到 Φ：

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

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

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

2 基于模糊核聚類粒化的粒度支持向量機

2.1 問題的提出

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

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

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

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

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

要想迅速地得到支持向量粒，節(jié)省粒化的時間，首先了解支持向量的特征，文獻[13]對其特征做了歸納總結(jié)。

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

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

2.2 問題分析

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

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

2.3 模糊核聚類

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

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

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

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

且有

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

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

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

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

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

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

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

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

2.4 FKC-GSVM 的算法步驟

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

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

2) 細粒劃分：采用模糊核聚類分別對l個粒子進行細粒劃分，計算每個粒子的隸屬度；

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

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

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

2.5 FKC-GSVM 算法性能分析

下面，從2 個方面對FKC-GSVM 的算法性能進行分析：

1) FKC-GSVM 的收斂性分析

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

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

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

3 實驗結(jié)果及分析

3.1 UCI 數(shù)據(jù)集上的實驗

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

數(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#測試集 1 000 473 3 498 1 000 10 000維度 8 9 16 32 32

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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