王建國，張鑫禮，張文興

（內(nèi)蒙古科技大學(xué)機械工程學(xué)院，內(nèi)蒙古包頭014010）

?

核模糊C均值聚類粒度支持向量機方法研究

王建國，張鑫禮，張文興

（內(nèi)蒙古科技大學(xué)機械工程學(xué)院，內(nèi)蒙古包頭014010）

摘要：針對傳統(tǒng)粒度支持向量機（granular support vector machine，GSVM）在處理大規(guī)模數(shù)據(jù)集時劃分方法的隨機性嚴(yán)重影響模型訓(xùn)練效能的情況，提出一種基于核模糊C均值聚類的粒度支持向量機（granular support vector machine based on kernel-based fuzzy c-means cluster, GSVM-KFCM）的方法。首先利用核映射將數(shù)據(jù)映射到高維空間進(jìn)行聚類劃分得到若干個信息粒，然后在每個信息粒中進(jìn)行支持向量機的訓(xùn)練，提取出關(guān)鍵信息并融合建立最終決策模型。實驗結(jié)果表明：該方法可以降低大規(guī)模數(shù)據(jù)集的訓(xùn)練時間，同時也能提高算法的準(zhǔn)確度。

關(guān)鍵詞：支持向量機；模糊C均值聚類；粒度計算；粒度支持向量機；核方法

0　引言

由Vapnik、Gokowich等[1]于1992年將基于支持向量機（support vector machine，SVM）引入到機器學(xué)習(xí)領(lǐng)域后，由于其特別適用于有限樣本、非線性問題，得到的學(xué)習(xí)模型也具有較好的推廣性，所以成為眾多機器學(xué)習(xí)方法中的熱點。但是，由于SVM針對大規(guī)模樣本數(shù)據(jù)時其處理能力的有限性也阻礙了支持向量機的廣泛應(yīng)用。

Yuchun Tang[2]提出了將粒度計算理論和支持向量機相結(jié)合的機器學(xué)習(xí)模型，稱為粒度支持向量機。它不但有效地克服傳統(tǒng)支持向量機對于大規(guī)模數(shù)據(jù)集以及不平衡數(shù)據(jù)集的訓(xùn)練效率低下的問題，而且可以獲得較好的泛化性能[3-4]。

雖然目前關(guān)于GSVM的研究還處于起步階段，但是粒度計算與支持向量機相結(jié)合的研究工作取得了一些進(jìn)展。Tang Y C[5]提出了基于關(guān)聯(lián)規(guī)則的粒度支持向量機，王文劍等[6]提出了核粒度支持向量機，Ke等[7]提出了遺傳算法與SVM決策樹相結(jié)合的混合學(xué)習(xí)策略。此外，不少學(xué)者研究基于粗糙集[8]、神經(jīng)網(wǎng)絡(luò)[9]以及商空間[10]的GSVM學(xué)習(xí)方法。

1　粒度支持向量機

支持向量機是針對整體樣本集構(gòu)造最優(yōu)超平面，而粒度支持向量機的主要思想是首先通過一定的方法將樣本空間劃分成為若干個子空間，得到一系列的信息粒（或者稱為信息類，信息簇），然后在每個信息粒上進(jìn)行支持向量機的學(xué)習(xí)，最后通過信息粒上的信息或者規(guī)則等獲得最終的支持向量機決策函數(shù)。

如圖1所示，GSVM將樣本空間劃分為若干個粒，構(gòu)建出比傳統(tǒng)支持向量機更加優(yōu)越的間隔寬度，從而提高模型的泛化能力。

其次，如圖2所示，GSVM還可以將一個典型的X-OR線性不可分問題，通過合理的劃分機制，將其轉(zhuǎn)化為兩個線性可分問題，從而得到多個決策函數(shù)。

因此，選擇何種?；椒ā澐至５膫€數(shù)確定以及如何劃分出更多的純粒等這些問題對于粒度支持向量機建模尤為重要，而這些因素也恰恰直接影響了其模型的訓(xùn)練時間、訓(xùn)練成本以及泛化能力。

圖1　GSVM劃分粒示意圖

圖2　GSVM非線性-線性轉(zhuǎn)移劃分示意圖

2　GSVM-KFCM算法

2.1核模糊C均值聚類

與模糊聚類算法不同的是，核模糊C均值聚類引入核函數(shù)的概念，將樣本空間映射到高維樣本空間，突出樣本的特性，更能提高樣本劃分簇的準(zhǔn)確性和可靠性[11]。

假設(shè)原空間樣本集為X={x1，x2，…，xn}，xj∈Rd，j= 1，2，…，N。核非線性映射為φ（x），將數(shù)據(jù)分為c個模糊組，并求每組的聚類中心，使得目標(biāo)函數(shù)達(dá)到最小，并利用模糊劃分，使得每個給定數(shù)據(jù)點用值在[0，1]間的隸屬度來反應(yīng)其屬于各個組的程度。一個數(shù)據(jù)集的隸屬度的總和等于1：

那么，KFCM的目標(biāo)函數(shù)就是：

這里uij介于[0，1]間；φ（x）表示該聚類中心在對應(yīng)核空間中的像，其中：

表示第j個聚類中心與第i個數(shù)據(jù)點映射到高維空間的歐氏距離，且m∈[1，+∞）是一個加權(quán)指數(shù)。

通過KFCM的目標(biāo)函數(shù)公式計算目標(biāo)函數(shù)，并利用下式更新隸屬度U矩陣：

由此進(jìn)行迭代更新，直至目標(biāo)函數(shù)值的變化小于閾值或無變化為止。

2.2GSVM-KFCM算法步驟

利用核模糊C均值聚類對樣本點進(jìn)行粒的劃分，通過對每個信息粒進(jìn)行分析，將純粒從信息粒中分離并保留下來，利用SVM對剩余的非純粒（即子空間包含的樣本點類型不一致）進(jìn)行訓(xùn)練并提取出關(guān)鍵支持向量。

由于純粒中的關(guān)鍵支持向量較少甚至沒有，所以利用一定的技術(shù)可以將“冗余點”進(jìn)行刪減，以降低整體SVM訓(xùn)練時間。本文只針對粒的劃分進(jìn)行研究，為了不丟失關(guān)鍵信息，因此對純粒進(jìn)行保留處理。

GSVM-FKCM主要流程圖如圖3所示。

3　實驗

為了驗證GSVM-KFCM方法的有效性，本文選用了4組UCI數(shù)據(jù)集：分別是Wisconsin Breast Cancer （WBC）、Indians Diabetes（ID）、German Credit（GC）Banknote Authentication（BA）以及1組TKH96a的二維數(shù)據(jù)（FourClass（FC）），詳見表1，與傳統(tǒng)SVM方法、傳統(tǒng)的GSVM方法進(jìn)行實驗測試對比。本次試驗環(huán)境為：2.68 GHz的CUP，2GB的內(nèi)存，7.12R（2011a）版的Matlab。

為了更好地闡述GSVM-KFCM的優(yōu)越性，本文首先選取TKH96a的數(shù)據(jù)fourClass（FC）與SVM以及傳統(tǒng)GSVM方法進(jìn)行實驗對比分析。

首先，本文使用歸一化將樣本數(shù)據(jù)縮放至[-1，1]之間。實驗統(tǒng)一采用采用高斯核函數(shù)進(jìn)行SVM訓(xùn)練：

圖3　GSVM-KFCM流程圖

表1　5組實驗數(shù)據(jù)

為了便于比較，兩種方法都將樣本空間點劃分為4個粒。圖4顯示了傳統(tǒng)GSVM對樣本空間的劃分結(jié)果（·號表示負(fù)類樣本點，+號表示正類樣本點），其中4個粒均為混合粒（即粒中包含兩類樣本點），由于傳統(tǒng)GSVM劃分的隨機性而導(dǎo)致子空間中出現(xiàn)了數(shù)據(jù)分布不平衡粒（圖中左起第2個子空間），且并沒有劃分出純粒。

圖5表示GSVM-KFCM對樣本空間劃分4個粒的情況?？梢钥闯?，通過核函數(shù)將原樣本映射到高維空間后進(jìn)行模糊C均值聚類，可以更好地突顯其特征，使得劃分的結(jié)果更適合SVM訓(xùn)練。同時，也可以避免數(shù)據(jù)分布不平衡問題[6]，而且由于將樣本映射到高維空間，使得原本為非線性的樣本集變?yōu)榫€性，從而更容易得到純粒（圖5左上角的樣本子空間）。由于純粒的標(biāo)簽一致，對于在純粒內(nèi)的測試樣本點，無需使用SVM模型即可判斷其標(biāo)簽，這樣大大的提高了整體模型的準(zhǔn)確性，同時也降低了訓(xùn)練時間。

圖4　傳統(tǒng)GSVM的劃分結(jié)果

圖5　GSVM-KFCM的劃分結(jié)果

但是，由于劃分粒的個數(shù)不同對其訓(xùn)練時間與準(zhǔn)確率也不盡相同，所以對樣本集進(jìn)行多次試驗，計算并記錄最佳準(zhǔn)確率。

表2　3種方法的實驗對比結(jié)果

對比實驗結(jié)果（見表2），從WBC、BA、GC、FC數(shù)據(jù)結(jié)果可以看出，無論是傳統(tǒng)GSVM還是本文所提出的方法，相對SVM來說，都大大降低了其訓(xùn)練時間，而ID數(shù)據(jù)雖然本文方法訓(xùn)練時間變化不大，但也較SVM有所減少。比較多次實驗結(jié)果以及分析ID、BA、FC數(shù)據(jù)結(jié)果，傳統(tǒng)GSVM準(zhǔn)確率相對較低是由于傳統(tǒng)GSVM劃分方法的隨機性，使得其劃分的信息粒中沒有純粒或者少于本文提出的方法所劃分出純粒的個數(shù)，從而影響該模型的整體準(zhǔn)確率。BA數(shù)據(jù)結(jié)果是因為當(dāng)同樣劃分為4個信息粒時，傳統(tǒng)GSVM沒有純粒，而GSVM-KFCM可以劃出一個純粒，所以時間消耗要低于傳統(tǒng)的GSVM。GC數(shù)據(jù)的對比結(jié)果顯示，3類方法的準(zhǔn)確率都比較接近，但因為GSVM-KFCM與傳統(tǒng)的GSVM一樣，當(dāng)同時劃分4個粒時，兩種方法都沒有得到純粒，所以兩種方法的時間消耗也較為接近。而且從WBC數(shù)據(jù)的對比結(jié)果可以看出，雖然傳統(tǒng)的GSVM與本文提出的方法上準(zhǔn)確率較為接近，但是GSVM-KFCM依然快于傳統(tǒng)的GSVM，這是由于核模糊聚類劃分方法很大程度上可以避免出現(xiàn)數(shù)據(jù)分布不平衡，從而其劃分結(jié)果更適合SVM訓(xùn)練，所以最終模型的時間消耗低于傳統(tǒng)的GSVM。

4　結(jié)束語

本文利用核模糊C均值聚類的優(yōu)勢，結(jié)合了粒度支持向量機的理念，提出了GSVM-KFCM方法，并進(jìn)行了實驗研究。其結(jié)果表明，該方法不但克服傳統(tǒng)粒度支持向量機模型對于大規(guī)模數(shù)據(jù)劃分粒的隨機性，提升了其訓(xùn)練效果，從而降低訓(xùn)練代價，并且進(jìn)一步提高了分類器的泛化能力。但是，由于聚類劃分方法的限制，無法自動計算出信息粒的劃分個數(shù)，而且也可能會出現(xiàn)子空間正分樣本點分布嚴(yán)重不平衡現(xiàn)象，導(dǎo)致最終分類器的準(zhǔn)確率下降。所以，下一步工作將對信息粒個數(shù)的確定以及劃分方式的規(guī)則選取等問題做進(jìn)行進(jìn)一步的研究工作，以探索出更加完善的方法。

參考文獻(xiàn)

[1] VAPNIK V. The nature of statistical learning theory[M]. New York：Springer-Verlay Press，1995：156.

[2] TANG Y H，JIN B，SUN Y，et al. Granular support vector machines for medical binary classification problems[M].Computational Intelligence in Bioinformatics and Computational Biology，2004（4）：73-78.

[3]張麗娟，李舟軍，陳火旺.粒度計算及其在數(shù)據(jù)挖掘中的應(yīng)用[J].計算機科學(xué)，2005，32（12）：178-180.

[4] DING S F，QI B J. Research of granular support vector machine[J]. Artif Intell Rev，2012，38（5）：1-7.

[5] TANGY C，JINB，ZHANGY Q. Granular support vector machines with association rules mining for protein homology prediction[J]. Artificial Intelligence in Medicine，2005（35）：121-134.

[6]王文劍，郭虎升.粒度支持向量機學(xué)習(xí)模型[J].山西大學(xué)學(xué)報（自然科學(xué)版），2009，32（4）：535-540.

[7] KE L，HUANG J. Study on a GA-based SVMdecision tree multi-classiflcation strategy[J]. Acta Electron Sinica，2008，36（8）：1502-1507.

[8]段丹青，陳松喬，楊偉軍，等.使用粗糙集和支持向量機檢測入侵[J].小型微型計算機系統(tǒng)，2008，29（4）：627-630.

[9]郭虎升，王文劍.基于神經(jīng)網(wǎng)絡(luò)的SVM學(xué)習(xí)算法[J].計算機工程與應(yīng)用，2009，45（2）：51-54.

[10]文貴華，向君，丁月華.基于商空間粒度理論的大規(guī)模分類算法[J].計算機應(yīng)用研究，2008，25（8）：2299-2301.

[11] MARK G. Mercer kernel-based clustering in feature space[J]. IEEE Transactions on Neural Networks，2002，13（3）：780-784.

（編輯：李剛）

Granular support vector machine based on kernel-based fuzzy C-means cluster

WANG Jianguo，ZHANG Xinli，ZHANG Wenxing
（School of Mechanical Engineering，Inner Mongolia University of Science and Technology，Baotou 014010，China）

Abstract:The training efficiency of models is often seriously affected by the granulating randomness of traditional granular support vector machines（GSVM）when computing with largescale data sets. A new GSVM based on Kernel-based Fuzzy C-Means Cluster（GSVM-KFCM）has been proposed to solve this problem. First，GSVM-KFCM was used to map the original data into a high dimension space and then split them into several information granules，each of which was trained with the support vector machine（SVM），and crucial information were extracted and combined to build up a final decision-making model. The experimental results have proved that this new method can reduce the training time of large-scale data sets and can also improve the accuracy to some extent.

Keywords:support vector machine；fuzzy C-means cluster；granular computation；granular support vector machine；kernel-based method

作者簡介：王建國（1958-），男，內(nèi)蒙古呼和浩特市人，教授，碩士生導(dǎo)師，博士，研究方向為機電系統(tǒng)智能診斷與復(fù)雜工業(yè)過程建模、優(yōu)化及故障診斷制。

基金項目：國家自然科學(xué)基金（21366017）內(nèi)蒙古自然科學(xué)基金重大項目（2011ZD08）

收稿日期：2015-02-17；收到修改稿日期：2015-04-25

doi：10.11857/j.issn.1674-5124.2016.02.022

文獻(xiàn)標(biāo)志碼：A

文章編號：1674-5124（2016）02-0096-04