MKDSIF—FCM算法及其性能分析

高宏娟

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

關(guān)鍵詞：模糊C-均值聚類；歐氏距離；權(quán)重系數(shù)；核函數(shù)；分類精度

中圖分類號：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

引言

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

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

本文將“對數(shù)據(jù)進行加權(quán)的策略”和“多核學(xué)習”的思想結(jié)合起來，對經(jīng)典的FCM算法進行了改進，改進后的算法被命名為MKDSIF-FCM。

1 MKDSIF-FCM算法

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

1.1 帶影響因子的距離權(quán)重系數(shù)

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

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

1.2 基于帶影響因子的距離權(quán)重的歐氏距離

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

1.3 引入多核函數(shù)

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

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

2 MKDSIF-FCM算法的性能分析

2.1 實驗環(huán)境

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

2.2 實驗結(jié)果和分析

2.2.1 MKDSIF-FCM算法和傳統(tǒng)FCM算法的性能對比

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

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

實驗結(jié)果表明，就分類精度而言，MKDSIF-FCM算法的性能要優(yōu)于傳統(tǒng)的FCM算法，分類精度提高了近6個百分點。本文實驗中的參數(shù)，以經(jīng)驗獲取為主，從表中可以看出，當選擇合適的參數(shù)時，進行多次實驗，MKDSIF-FCM算法能夠獲得非常穩(wěn)定的分類結(jié)果，其結(jié)果具有可再現(xiàn)性。

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

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

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

表3的實驗結(jié)果表明，MKDSIF-FCM算法的分類精度要高于傳統(tǒng)的FCM算法[1]，SAWFCM算法[2]，F(xiàn)KCM算法[6]，Multiple-kernel FCM算法[10]，SWFCM算法[3]，MF-FCM算法[4]，F(xiàn)W-FCM算法[5]，KFCM算法[7]，F(xiàn)KWCM算法[8]，DWFCM算法[12]和IWFCM算法[11]。MKDSIF-FCM算法的分類精度和POKFCM算法[12]相同，均達到了96%。

表4中的實驗結(jié)果表明：相比傳統(tǒng)的FCM算法，MKDSIF-FCM算法將Wine數(shù)據(jù)集的分類精度從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算法的穩(wěn)定性分析

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

3 結(jié)束語

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

參考文獻：

[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]任麗娜，秦永彬，許道云.基于自適應(yīng)權(quán)重的模糊C-均值聚類算法[J].計算機應(yīng)用研究，2012，29（8）：2849-2851.

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

[4]蔡靜穎，謝福鼎，張永.基于馬氏距離特征加權(quán)的模糊聚類新算法[J].計算機工程與應(yīng)用，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]. 西安電子科技大學(xué)學(xué)報（自然科學(xué)版），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]趙春暉，齊濱.基于模糊核加權(quán)C-均值聚類的高光譜圖像分類[J].儀器儀表學(xué)報，2012，33（9）：2016-2021.

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

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

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

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