基于核魯棒k—均值的模糊支持向量機算法

王孝彤　程遠志

摘 要：支持向量機對訓練數據中的噪聲敏感，為了解決這一問題，本文提出基于核魯棒k-均值算法的模糊支持向量機算法。算法首先在每類訓練樣本上應用核魯棒k-均值算法，得到每個樣本的模糊隸屬度，將該隸屬度賦予訓練樣本，得到模糊訓練集，然后在模糊訓練集上訓練模糊支持向量機，得到分類決策函數。實驗表明，對于帶噪聲的訓練樣本，本文的算法能夠為噪聲樣本賦予小的隸屬度，提高分類準確率。

關鍵詞：模糊支持向量機；核魯棒k-均值；模糊訓練集；噪聲

中圖分類號：TP391.41 文獻標識號：A 文章編號：2095-2163（2015）03-

Fuzzy Support Vector Machine based on Kernel Robust k-means

WANG Xiaotong， CHENG Yuanzhi

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： The support vector machine （SVM） is sensitive to noises in the training set. In order to deal with this problem， a fuzzy support vector machine （FSVM） based on kernel robust k-means is proposed in this paper. Kernel robust k-means is applied to samples of each class respectively， and all samples are given membership degrees， which is combined with the original training set to yield a fuzzy training set. FSVM is then trained on the fuzzy training set to get a decision function. The experiment result shows that noises obtain small membership degrees， and the classification accuracy is improved when the training set is polluted with noises.

Keywords： Fuzzy Support Vector Machine； Kernel Robust k-means； Fuzzy Training Set； Noise

0 引 言

支持向量機是模式識別和機器學習領域中解決分類問題[1]以及非線性函數估計問題[2]的一種重要方法。針對二類分類問題，支持向量機在高維特征空間中構建最大化兩類分類間隔的分類超平面，通過核函數，可以學習非線性支持向量機[3]。

分類問題中通常存在一部分輸入訓練樣本的類別標錯的情況，這種錯誤的類別標號稱為錯誤類別噪聲[4]，簡稱噪聲。錯誤類別噪聲經常出現在兩類樣本具有相似的特征的時候。由于擬合這些樣本，支持向量機學習的最優分類面與不存在錯誤類別噪聲時的最優分類面產生偏差，從而降低了支持向量機的準確性。也就是說，支持向量機的訓練過程對訓練集中的錯誤類別噪聲敏感[5]。

支持向量機對于錯誤類別噪聲的敏感性主要是由于在支持向量機理論中，所有的訓練樣本均同等對待[6]，而支持向量機的分類決策面則依賴于在訓練集中占少數的支持向量。由于錯誤類別噪聲樣本與其他訓練樣本具有相同的重要性，但卻更容易被分類器錯分，從而成為支持向量，為了減小錯分懲罰，支持向量機將擬合這些樣本，因而對分類超平面產生較大影響。

為了減少噪聲對分類決策的影響，研究者提出了模糊支持向量機（FSVM）算法[6][7]，作為標準支持向量機的推廣。通過為噪聲賦予更小的隸屬度權重，就減少了其對分類決策的影響，同時也提高了支持向量機的抗噪性。基于此，如何為訓練集設置合理的隸屬度即已隨之而成為模糊支持向量機的一個關鍵研究問題。

本文提出了一種基于核魯棒k-均值的模糊支持向量機算法，對兩類訓練樣本分別應用核魯棒K-均值聚類算法，得到每個樣本的隸屬度，與原始的訓練樣本結合得到模糊訓練樣本集，而后通過模糊支持向量機算法訓練分類器，提高了支持向量機的抗噪性。

1 核魯棒K-均值算法

1.1 魯棒k-均值算法

魯棒k-均值算法（Rkmeans）是k-均值算法的推廣。給定樣本集合以及聚類數目 ，魯棒k-均值算法尋找 個聚類，并將每個樣本劃分給一個聚類。與k-均值算法不同的是，每個樣本對于其所屬聚類均有一個隸屬度，作為其對于整個類的隸屬度，代表了各樣本隸屬于整個類的程度，其中，隸屬度小于給定閾值的樣本即可判定為是噪聲[8]。

設樣本集合為 ，其中 ，聚類數目 滿足 。設 個聚類中心為 ，樣本 對于類的模糊隸屬度為 ，其中 ， 是 作為噪聲的程度。記 為 中樣本下標的集合， 為屬于第 個聚類的樣本的下標構成的集合。

魯棒k-均值算法的優化目標如下：

（1）

上述目標函數的優化變量包括 個聚類中心 ，每個樣本所屬的聚類，及每個樣本的隸屬度 。類似于k-均值聚類算法，每個樣本只是屬于 個聚類中的一個，不同點在于，（1）式的目標函數通過隸屬度對k-均值聚類的距離求和項進行了加權，并加入了噪聲項 。其中，參數 控制隸屬度模糊程度，可取 或 ， 是用于控制噪聲敏感性的懲罰項，一般設為 ，參數 一般設為 [8] 。

將必要條件

（2）

代入（1）式的目標函數得到：

（3）

上述優化問題直接求解較難，可以通過迭代方法求得其松弛問題的解析解，作為原問題的近似解[8]，進一步，通過近似，可以得到聚類的硬劃分。

1.2 核魯棒k-均值算法

核魯棒k-均值算法（KRkmeans）在魯棒k-均值算法的基礎上引入了核函數。首先將原始空間中的向量映射到高維空間，然后在高維空間尋找合適的聚類和隸屬度。

對原始空間進行非線性映射 ，則高維空間中的樣本可表示為 。那么高維空間中的魯棒k-均值目標函數為：

（4）

令 為核函數，則目標函數可表示為：

（5）

由此，不需要知道映射 的具體形式，只需定義合適的核函數 ，即可實現高維空間的聚類。

2 模糊支持向量機算法

給定訓練樣本集

其中， 是原始輸入空間的樣本， 是 所屬的二元類別標號， 是 對于 類的模糊隸屬度。

模糊支持向量機（FSVM）的目標是尋找兩類樣本的最優分類面 ，其優化問題如下[7]：

（6）

其中， 是高維特征空間中分類超平面的法向量， 是偏置項， 是松弛變量， 。 是控制分類間隔和錯分代價兩者之間折中的懲罰參數。

通過引入Lagrange乘子向量 ， 得到對偶問題：

（7）

求解對偶問題得到最優的Lagrange乘子，并求解 ：

（8）

其中， 是滿足 的樣本的數目。

樣本 的類別可由分類決策函數 預測：

（9）

3 基于核魯棒K-均值的模糊支持向量機算法

給定訓練樣本集合：

首先應用核魯棒k-均值算法為其設置隸屬度。對于兩類訓練樣本 和 ，分別獨立地應用核魯棒k-均值算法進行聚類，得到每一類中的樣本 對于其所屬類的模糊隸屬度 ，將該隸屬度賦予訓練集 中的樣本 ，得到模糊樣本 ，進而得到模糊訓練集：

然后在模糊訓練集 上訓練模糊支持向量機得到分類器。這種用核魯棒k-均值算法為模糊支持向量機設置隸屬度并求解最優分類面的算法稱為基于核魯棒k-均值的模糊支持向量算法，簡記為KRkmeans-FSVM。

由于錯誤類別噪聲通常與其所標類的樣本特征差距較大，即離總體較遠，因而在核魯棒k-均值聚類階段，會獲得較小的隸屬度。因此聚類得到的隸屬度降低了錯誤類別噪聲在訓練FSVM過程中的重要性，使得FSVM更傾向于擬合隸屬度較大的正常樣本，從而降低了FSVM對錯誤類別噪聲的敏感性，FSVM的抗噪性也隨即得到了提高。

KRkmeans-FSVM算法步驟如下：

Step 1：設置參數，包括KRkmeans的模糊控制參數 ，噪聲敏感性參數 ，兩類聚類數目 和 ，以及KRkmeans和FSVM的核函數及相應參數等。

Step 2：對訓練集 的兩類樣本分別應用核魯棒k-均值算法聚類，得到每個樣本 的模糊隸屬度 ，與 構成帶有模糊隸屬度的訓練集 。

Step 3：在模糊訓練集 上應用FSVM算法，訓練得到分類器。

Step 4：樣本的類別標號由（9）式預測。

4 實驗結果與結論分析

為了驗證算法的效果，比較KRkmeans-FSVM與標準的SVM算法訓練得到的分類器在測試集上的平均分類準確率，其中訓練集分別采用了標準的訓練集和帶5%隨機錯誤類別噪聲的訓練集。實驗數據來自UCI標準數據集（http：//archive.ics.uci.edu/ml/datasets.html）。實驗參數采用 ， ，核函數選擇高斯核函數 。聚類數目 和 以及高斯核函數的參數 由交叉驗證確定。

兩種方法對于測試集的分類準確率如表1和表2所示。

表1 兩種算法在標準數據集上的分類準確率

Tab.1 The classification accuracy of the two methods on standard datasets

算法 數據集 Banana Ripley Monk Haberman Waveform

SVM 0.9016 0.9080 0.9514 0.7628 0.9013

KRkmeans-FSVM 0.8816 0.9090 0.9537 0.7814 0.9050

表2 兩種算法在5%噪聲數據集上的分類準確率

Tab.2 The classification accuracy of the two methods on datasets with 5% noises

算法 數據集 Banana Ripley Monk Haberman Waveform

SVM 0.8882 0.9080 0.9468 0.7767 0.8954

KRkmeans-FSVM 0.8922 0.9140 0.9560 0.7814 0.9026

由表1可知，對于標準的數據集，KRkmeans-FSVM在五組數據中的四組上的分類準確率優于標準的支持向量機（SVM）。由表2知，對于帶5%錯誤類別噪聲的樣本，KRkmeans-FSVM對于五組數據的分類準確率均優于SVM。這說明KRkmeans算法為FSVM設計的隸屬度是合理的。

由表1和表2對比發現，SVM對于帶噪聲的樣本，準確率下降較為明顯，而KRkmeans-FSVM在各組數據集上總體的表現并沒有因為噪聲的加入而變差。由此說明，KRkmeans-FSVM有較好的抗噪性。

5 結束語

為了解決標準支持向量機對噪聲敏感的問題，本文提出了一種基于核魯棒k-均值的模糊支持向量機算法，通過核魯棒k-均值聚類為訓練樣本設置隸屬度，然后用得到的模糊訓練集訓練模糊支持向量機，得到最優分類面。實驗表明本文的算法對支持向量機的準確率有所提高，特別是對于存在錯誤類別噪聲的數據集，具有更好的抗噪性。

參考文獻：

[1] CORTES C， VAPNIK V. Support-vector networks [J]. Machine learning， 1995， 20（3）： 273-297.

[2] HONG D H， HWANG C. Interval regression analysis using quadratic loss support vector machine [J]. Fuzzy Systems， IEEE Transactions on， 2005， 13（2）： 229-237.

[3] 李航. 統計學習方法[M]. 北京：清華大學出版社，2012.

[4] YANG X， ZHANG G， LU J， et al. A kernel fuzzy c-means clustering-based fuzzy support vector machine algorithm for classification problems with outliers or noises [J]. Fuzzy Systems， IEEE Transactions on， 2011， 19（1）： 105-115.

[5] 張瑞，馬逸塵，段現報. 面向分類去噪問題的模糊支持向量機新算法[J]. 西安交通大學學報，2008， 41（12）： 1414-1417.

[6] HUANG H P， LIU Y H. Fuzzy support vector machines for pattern recognition and data mining[J]. International Journal of Fuzzy System， 2002，4（3）：826-835

[7] LIN C F， WANG S D. Fuzzy support vector machines [J]. Neural Networks， IEEE Transactions on， 2002， 13（2）： 464-471.

[8] HONDA K， NOTSU A， ICHIHASHI H. Fuzzy PCA-Guided Robust-Means Clustering [J]. Fuzzy Systems， IEEE Transactions on， 2010， 18（1）： 67-79.