MKDSIF—FCM算法及其性能分析

高宏娟

摘 要：模糊C-均值聚類（FCM）是一種最常用的聚類算法，其性能因直接采用了歐氏距離而受到限制。針對該問題，提出了一種FCM的改進算法，命名為MKDSIF-FCM。MKDSIF-FCM算法提出了帶影響因子的距離權重系數的概念，將其運用到歐氏距離的計算中；同時，MKDSIF-FCM算法中采用了多核學習的技巧，增加了樣本之間的差異性，能夠有效地提高FCM算法的聚類效果。實驗結果表明，在Iris數據集和Wine數據集上，相比經典的FCM算法，MKDSIF-FCM算法的分類精度有顯著的提高；相比其他的FCM改進算法，MKDSIF-FCM算法分類性能更優。

關鍵詞：模糊C-均值聚類；歐氏距離；權重系數；核函數；分類精度

中圖分類號：TP311 文獻標志碼：A 文章編號：2095-2945（2018）34-0010-04

Abstract： Fuzzy C-means Clustering （FCM） is one of the most commonly used clustering algorithms， and its performance is limited by adopting Euclidean Distance directly. To solve this problem， an improved FCM algorithm named MKDSIF-FCM is proposed. MKDSIF-FCM algorithm puts forward the concept of distance weight coefficient with influence factor， and applies it to the calculation of Euclidean Distance； at the same time， MKDSIF-FCM algorithm adopts multi-kernel learning technique， which increases the difference between samples. It can effectively improve the clustering effect of FCM algorithm. The experimental results show that the classification accuracy of the MKDSIF-FCM algorithm is significantly improved， compared with the classical FCM algorithm on the Iris data set and the Wine data set， and the classification performance of the MKDSIF-FCM algorithm is better than other FCM improved algorithms.

Keywords： Fuzzy C-means Clustering （FCM）； Euclidean Distance； weight coefficient； kernel function； classification accuracy

引言

聚類分析是一種無監督的分類方法，它能夠把無類別標簽的樣本集按照類別劃分成若干個子集。經典的模糊C-均值聚類（FCM）算法作為一種重要的模式識別方法和數據挖掘工具，最早是由Dunn[1]在1974年提出。

經典的FCM算法忽略了同一樣本的不同屬性對聚類效果的貢獻，而且對初始聚類中心的依賴程度高，易受孤立點和樣本分布不均衡的影響。針對這些問題，很多學者利用數據加權策略對FCM算法進行了改進。而且，經典的FCM算法沒有對樣本數據的特征進行優化，這種直接采用歐氏距離計算目標函數的方式使得分類效果的好壞受樣本的分布情況影響較大。針對這一問題，很多學者引進核函數的概念對FCM聚類算法進行了改進。

本文將“對數據進行加權的策略”和“多核學習”的思想結合起來，對經典的FCM算法進行了改進，改進后的算法被命名為MKDSIF-FCM。

1 MKDSIF-FCM算法

模糊C-均值聚類算法使用迭代優化策略求目標函數JS的近似極小值。

1.1 帶影響因子的距離權重系數

在FCM算法中，uik是從第k個樣本xk到第i個聚類中心vi的隸屬度函數，而且滿足（1）式，它反映的是同一個樣本到不同聚類中心的隸屬程度，通過比較同一樣本到不同聚類中心的隸屬程度來決定樣本到底屬于哪一類。但經典的FCM算法中，不同的樣本到同一個聚類中心的并沒有被比較和分析，而這種比較和分析對于提高模糊聚類精度是有貢獻的。因此，我們提出了一種新的概念——帶影響因子的距離權重系數（Distance weighting coefficient with IF），它反映的是不同的樣本到同一個聚類中心的遠近程度。帶影響因子的距離權重系數的定義如下：

其中，wik是第k個樣本xk到第k個聚類中心vi的距離權重系數。wik會對xk和vi之間的距離dik產生一定的影響，但是對于不同類型的樣本集，距離dik受wik的影響是不同的，為了使算法能夠廣泛的用于不同的數據集并具有穩定的聚類效果，我們給wik加一個影響因子，記為？茁。

1.2 基于帶影響因子的距離權重的歐氏距離

在模式識別和聚類分析中，距離是一個非常重要的概念，它反映了不同數據之間的相似程度。經典的FCM算法是用公式（5）來定義第k個樣本xk到第i個聚類中心vi的歐式距離。引入了帶影響因子的距離權重系數后，我們將第k個樣本xk到第i個聚類中心vi的歐氏距離定義為：

1.3 引入多核函數

本文借鑒了多核學習的思想并將其運用到MKDSIF-FCM算法中，用不同子核函數構造多核函數，不但將原樣本的非線性問題轉化為線性問題進行處理，而且利用了全局性核函數和局部性核函數互補性，進一步增大了類別樣本之間的差異度，從而有效地提高了分類精度。常用的核函數有高斯核函數（Gaussian kernel）、多項式核函數（Polynomial kernel）和雙曲正切核函數（hyperbolic tangent kernel）。

任一函數只要滿足Mercer條件，就可以看作是一種核函數。將K個核函數按照不同權重系數組合起來仍然是一個核函數，記為：

2 MKDSIF-FCM算法的性能分析

2.1 實驗環境

本文實驗所使用的臺式機主要配置如下：CPU參數為 3.40GHZ Core（TM） I7-3770，內存大小為4GB。本文中所有的程序在MATLAB 2015a環境下運行。為了測試算法的有效性，我們選取了聚類算法中最常用的兩個數據集進行實驗，即UCI數據集中的Iris數據集和Wine數據集，數據集的基本信息如表1所示。

2.2 實驗結果和分析

2.2.1 MKDSIF-FCM算法和傳統FCM算法的性能對比

本文選用Iris數據集，對MKDSIF-FCM算法和傳統FCM算法在分類精度、運行時間和迭代次數3個方面做了對比分析，實驗結果如表2所示。

表2中的參數s代表了模糊指數，p1和p2代表了兩個核函數的系數，σ1和σ2代表了兩個核函數的參數，β代表了影響因子。在這里需要說明的是，本文實驗中的“多核”指的是對兩個高斯核函數按照不同權重系數組合，但前后兩個高斯核函數的參數σ1和σ2的值是不同的。因為，對Iris和Wine數據集而言，當兩個核函數都選高斯核函數時，聚類效果最好。

實驗結果表明，就分類精度而言，MKDSIF-FCM算法的性能要優于傳統的FCM算法，分類精度提高了近6個百分點。本文實驗中的參數，以經驗獲取為主，從表中可以看出，當選擇合適的參數時，進行多次實驗，MKDSIF-FCM算法能夠獲得非常穩定的分類結果，其結果具有可再現性。

實驗結果表明，就運行時間而言，MKDSIF-FCM算法所需的運行時間和FCM算法差不多；就迭代次數而言，MKDSIF-FCM算法的迭代次數和FCM算法幾乎相當。

2.2.2 MKDSIF-FCM算法和其他改進算法的精度對比

近些年，針對傳統FCM算法的不足，文獻[1-12]提出了一些改進算法。本文在Iris數據集和Wine數據集上，對比了MKDSIF-FCM算法和這些改進算法的分類精度，實驗結果如表3和表4所示。

表3的實驗結果表明，MKDSIF-FCM算法的分類精度要高于傳統的FCM算法[1]，SAWFCM算法[2]，FKCM算法[6]，Multiple-kernel FCM算法[10]，SWFCM算法[3]，MF-FCM算法[4]，FW-FCM算法[5]，KFCM算法[7]，FKWCM算法[8]，DWFCM算法[12]和IWFCM算法[11]。MKDSIF-FCM算法的分類精度和POKFCM算法[12]相同，均達到了96%。

表4中的實驗結果表明：相比傳統的FCM算法，MKDSIF-FCM算法將Wine數據集的分類精度從68.54%提高到了94.84%，模糊聚類性能得到了顯著的提高；相比其他改進算法，MKDSIF-FCM算法能夠達到較好的聚類效果，其分類精度高于DWFCM算法[9]，Multiple-kernel FCM算法[10]和POKFCM[12]算法，遠遠高于MF-FCM算法[4]， FKCM算法[6]和FKWCM算法[8]。

2.2.3 MKDSIF-FCM算法的穩定性分析

為了驗證算法的穩定性，我們分別在Iris和Wine數據集上重復執行MKDSIF-FCM算法50次，結果如圖1所示。結果表明，不管是Iris數據集還是Wine數據集，本文算法均獲得了一致的識別精度，穩定性非常好。

3 結束語

針對傳統的FCM算法的不足，本文提出了改進的FCM算法，即MKDSIF-FCM。為了驗證算法的有效性，在Iris數據集和Wine數據集上，對MKDSIF-FCM算法、FCM以及其他改進算法[2-12]進行對比分析。結果表明，MKDSIF-FCM算法能夠有效地提高數據的聚類效果，其性能優于其他改進算法，并且具有非常高的穩定性。

參考文獻：

[1]Dunn J C. Some Recent Investigations of a New Fuzzy Partitioning Algorithm and its Application to Pattern Classification Problems[J]. Journal of Cybernetics， 1974，4（2）：1-15.

[2]任麗娜，秦永彬，許道云.基于自適應權重的模糊C-均值聚類算法[J].計算機應用研究，2012，29（8）：2849-2851.

[3]齊淼，張化祥.改進的模糊C-均值聚類算法研究[J].計算機工程與應用，2009，45（20）：133-135.

[4]蔡靜穎，謝福鼎，張永.基于馬氏距離特征加權的模糊聚類新算法[J].計算機工程與應用，2012，48（5）：198-200.

[5]Yue Y， Zeng D， Lei H. Improving Fuzzy C-Means Clustering by a Novel Feature-Weight Learning[C]// Computational Intelligence and Industrial Application， 2008. PACIIA '08. Pacific-Asia Workshop on. IEEE，2009：173-177.

[6]伍忠東，高新波，謝維信.基于核方法的模糊聚類算法[J]. 西安電子科技大學學報（自然科學版），2004，31（4）：533-537.

[7]Yang A， Jiang L， Zhou Y. A KFCM-Based Fuzzy Classifier[C]//International Conference on Fuzzy Systems and Knowledge Discovery. IEEE， 2007：80-84.

[8]趙春暉，齊濱.基于模糊核加權C-均值聚類的高光譜圖像分類[J].儀器儀表學報，2012，33（9）：2016-2021.

[9]王行甫，程用遠，覃啟賢.一種改進的密度加權的模糊C聚類算法[J].計算機系統應用，2012，21（9）：220-223.

[10]趙犁豐，李新，王棟.多核模糊聚類算法的研究[J].中國海洋大學學報：自然科學版，2009，39（5）：1047-1050.

[11]劉強，夏士雄，周勇，等.基于兩種加權方式的模糊聚類算法[J].計算機應用研究，2011，28（12）：4437-4439.

[12]劉云，劉富，侯濤，等.優化核參數的模糊C均值聚類算法[J].吉林大學學報（工學版），2016，46（1）：246-251.