截集型特征加權模糊C-均值聚類算法

摘 要:已有的特征加權型模糊C-均值(WFCM)聚類算法可以有效地提取數據的相關特征，WFCM存在的主要問題是收斂速度慢和對噪聲敏感。借助模糊集的截集方式對WFCM的隸屬度值進行修改，提出截集型特征加權模糊C-均值聚類算法:SWFCM。SWFCM不僅具有良好的特征提取能力，而且具有收斂速度快和對噪聲穩健的優點。實驗結果表明，SWFCM的總體性能優于原有的WFCM聚類算法和截集模糊C-均值聚類算法。

關鍵詞:特征加權; 穩健聚類; 截集; 特征提取

中圖分類號:TP181文獻標識碼:A

文章編號:1004-373X(2010)08-0123-04

Clustering Algorithm of Sectional Set Feature-weighted Fuzzy C-means

ZHI Xiao-bin， FAN Jiu-lun

(Xi’ an Institute of Post and Telecommunications， Xi’an 710121， China)

Abstract:Although the clustering algorithm offeature-weighted fuzzy C-means(WFCM)can effecively extract the related features of data， it still has some shortages such as slow convergence and sensitive to noise. The clustering algorithm of sectional set feature-weighted fuzzy C-means (SWFCM)is presented by revising the membership function of WFCM by sectional set. In comparison with WFCM， SWFCM not only can extract the features of data set， but also has the advantages of fast convergence and robust to noise. The experimental results show that SWFCM has super performance over original WFCM clustering algorithm and sectional set fuzzy C-means clustering algorithm.

Keywords:feature weighting; robust clustering; sectional set; features extraction

0 引 言

在模糊聚類算法中，模糊C-均值(FCM)聚類算法是最著名和應用最廣泛的聚類算法，盡管FCM得到了廣泛的應用，卻存在如下缺點:收斂速度慢，對噪聲敏感，不能自動選取特征。

針對傳統聚類算法對數據的各個特征平等對待，不能自動選擇數據相關特征的問題，眾多學者提出了基于特征加權的聚類算法[1-2]。Wang等人首先[3]提出了特征加權型FCM(WFCM)，Hichem等人[4]詳細討論了WFCM聚類算法，通過用類似于FCM聚類算法中隸屬函數的求解方法來計算特征權值，并將所得的WFCM算法應用于彩色圖像分割和監督分類問題;李潔[5]，Hung[6]和陳新泉[7]等人也從不同角度研究了特征加權的FCM聚類算法。由于WFCM算法是在原FCM算法的基礎上加入特征權重的迭代計算，這便使得WFCM運行時間比FCM更長，不便于實際應用。另外，實際工程應用過程中不可避免地會出現噪聲，但上述的特征加權FCM聚類算法都沒有考慮噪聲問題，這使得所提算法在實際應用過程中很難達到預期的效果。

為了進一步提高FCM的收斂速度，裴繼紅等人[8]基于模糊集理論中的截集概念，提出了截集模糊C-均值(SFCM)聚類算法，SFCM符合人類思維的分類習慣，能夠極大地提高算法的收斂速度。Yang等人[9]進一步深入分析了SFCM，不僅證明SFCM的收斂性，并且指出SFCM能產生“聚類核”，當選取較大的模糊參數時，SFCM具有良好的對噪聲不敏感性。盡管SFCM具有收斂速度快和對噪聲不敏感的優點，但SFCM與FCM一樣，不能自動選取特征。

鑒于WFCM能夠自動選擇特征，SFCM收斂速度快并對噪聲不敏感，本文考慮將二者的優點相結合，提出截集型WFCM聚類 (或者特征加權型SFCM聚類)。為了方便，本文采用術語:截集型WFCM聚類(SWFCM)。在WFCM算法基礎上，用截集思想對WFCM產生的隸屬度函數值進行修改。與SFCM和WFCM相比較，SWFCM既具有自動特征選取能力，又具有較快的收斂速度和良好的噪聲穩健性，是一個有效的聚類算法。

1 截集FCM算法和特征加權FCM聚類算法

眾所周知，對于歐式空間RM數據集X={x1，x2，…，xN}，FCM的目標函數為:

JFCM(U，V)=∑Ni=1∑Cj=1umij‖xi-vj‖2(1)

滿足:

∑Cj=1uij=1，1≤i≤N

uij∈[0，1]，1≤i≤N，1≤j≤C

運用拉格朗日乘子法可求得JFCM(U，V)最小化的必要條件為:

vj=(∑Ni=1umijxi)/∑Ni=1umij(2)

uij=(1/‖xi-vj‖2)/∑cl=1‖Xi-Vl‖2(3)

FCM通過交替迭代計算式(2)和式(3)來最小化JFCM(U，V)。

截集FCM(SFCM)的基本思想較為簡單，就是在原FCM算法的基礎上，在FCM對隸屬度的每一次迭代求解過程中加一步對隸屬度值的修改:對于給定的0<α<1，如果uij=max1≤l≤c uil>α，則令uij=1，uij′=0(j′≠j);否則隸屬度函數仍按式(3)計算。

雖然SFCM是FCM經上述簡單改動的算法，但是與FCM相比較，SFCM卻具有更快的收斂速度和更好的對噪聲穩健性。文獻[8]比較了SFCM與FCM的收斂速度;文獻[9]詳細討論了SFCM的穩健性，指出SFCM不但能夠產生“聚類核”，而且當模糊因子取較大值時，SFCM具有良好的噪聲不敏感性。

特征加權FCM(WFCM)有眾多版本，這里以Hichem [4]提出的WFCM為基本算法進行討論。Hichem運用類似FCM中隸屬函數的求解方法給出特征加權FCM聚類算法中權函數的一種迭代求解算法，該算法在特征權重的計算過程中賦予不同聚類以不同特征權重，是一種局部特征加權聚類算法。用JWFCM(U，V，W)表示WFCM的目標函數，該算法的目標函數為:

JWFCM(U，V，W)=∑Ni=1∑Cj=1∑Mk=1umijwβjkd(xik，vjk)(4)

滿足:

∑Cj=1uij=1，uij∈[0，1]，1≤i≤N，1≤j≤C

∑Mk=1wjk=1， 1≤j≤C，1≤k≤M

WFCM通過迭代計算式(5)~式(7)來最小化式(4)。

vjk=(∑Ni=1umijxik)/∑Ni=1umij(5)

uij=\\Mk=1wβjkd(xik，vjk)\\〗-1m-1∑Ck=1\\Mk=1wβjkd(xik，vlk)\\〗-1m-1(6)

wjk = 1∑Ml = 1(Djk/Djl)1β-1(7)

式中:Djk=∑Ni=1umijd(xik，vjk)。交替迭代優化式(5)~式(7)可實現最小化式(4)。

2 截集型特征加權FCM聚類算法

雖然WFCM具有自動特征選取的優點，但是由于它是在原FCM算法的基礎上加了特征權值的迭代計算，所以WFCM的收斂速度較慢，不便于實際應用。而SFCM算法具有收斂速度快和噪聲穩健的優點，為此，結合二者的優點，用截集方式對WFCM算法的隸屬度值進行修改，提出截集型特征加權FCM(SWFCM)算法。在WFCM算法的基礎上，對由式(6)計算所得的隸屬度值做如下修改:

對于給定的0<α<1，如果uij=max1≤l≤c uil>α，則令uij=1，uij′=0(j′≠j);否則隸屬度值仍按式(6)計算。

SWFCM算法的描述如下:

(1)選擇聚類數C，ε>0，參數β<0 或β>1，參數0<α<1;選擇初始聚類中心矩陣V，特征權重W;

(2) 用式(6)更新隸屬度矩陣U′;

(3) 對給定的0<α<1，用截集方式修改隸屬度矩陣得到新的隸屬度矩陣U″;

(4) 用式(7)更新特征權矩陣W′;

(5) 用式(5)更新聚類中心矩陣V′，如果‖V′-V‖<ε，則停止;否則轉到(2)。

3 實驗結果及分析

為了驗證本文提出SWFCM算法的有效性，這里對SFCM，WFCM和SWFCM進行對比仿真實驗。在實驗中，初始權重取為w(0)jk=1/M，j=1，2，…，C，k=1，2，…，M，最大迭代次數設為200。

3.1 人造數據

人造數據來自文獻[10]， 記為data1。data1是一個四維空間{X1，X2，X3，X4}中的4類{C1，C2，C3，C4}數據，其中每一類包括100個數據點。類C1和類C2在由特征X1和特征X2構成的子空間中以正態分布的形式形成兩類，而特征X3和特征X4是C1和C2的白噪聲特征，類C1和類C2在每一維特征上的均值分別為μC1=[0.5，-0.5，0，0]和μC2=[-0.5，-0.5，0，0]，標準差為σC1=[0.1，0.2，0.4，0.4]和σC2=[0.1，0.2，0.4，0.4];類似地，類C3和類C4在由特征X2和特征X3構成的子空間以正態分布的形式形成兩類，而X1和X4是類C3和類C4的白噪聲特征，類C3和類C4在每一維特征上的均值分別為μC3=[0，0.5，0.5，0]和μC4=[0，0.5，-0.5，0]，標準差為σC3=[0.4，0.2，0.1，0.4]和σC4=[0.4，0.2，0.1，0.4]。data1在不同特征維數空間上的投影如圖1所示。其中圖1(a)為data在由特征X1和特征X2構成的子空間中的投影;圖1(b)為data1在由特征X2和X3特征構成的子空間中的投影;圖1(c)為data1在由特征X1和X3特征構成的子空間中的投影。

圖1 在不同特征維數空間中的數據data1

在該實驗中，為了測試孤立噪聲點對聚類算法的影響，在data1中加入一個孤立噪聲點，坐標為(100，100，100，100)，所構成的數據記為data2。為避免算法陷入局部極值，用從數據中隨機選取聚類中心的方法初始聚類中心100次，三個算法用這相同的100組初始聚類中心各自運行100次選最優結果為最終聚類的結果。在該次實驗中，參數α=0.3，β=3，模糊因子m=5。對加了噪聲數據的分類結果如表1所示，用N，T，A分別表示三個算法迭代次數、運行時間和準確率。其中，準確率A定義為A=(∑Cj=1nj)/n( nj表示第j類正確分類數據的個數)。

由表1可知，WFCM 受噪聲影響不能正確選取特征，分類準確率較低，SFCM 和SWFCM受噪聲影響較小，準確率都高于WFCM，并且SWFCM能夠正確選取數據的相關特征，因此可以獲得很高的準確率。

表1 三個算法對data2數據的運行結果

NTA

SFCM150.422 00.780 0

WFCM491.201 00.725 0

SWFCM120.592 00.985 0

3.2 真實數據

Iris數據和Breast-cancer數據來源于UCI repository of machine learning databases[11]，數據特性如表2所示。

表2 數據描述

樣本數維數類數

Iris15043

Breast-cancer683102

在該實驗中，為避免算法陷入局部極值，用從數據中隨機選取聚類中心的方法初始聚類中心100次，3個算法用這相同的100組初始聚類中心各自運行100次選最優結果作為最終聚類結果。用N，T，A分別表示3個算法迭代次數、運行時間和準確率，參數α取為0.3，β取值為2，模糊因子m取為2。對Iris數據和Breast-cancer數據的分類結果如表3和表4所示。

表3 三個算法對Iris數據的分類結果

TAN

SFCM50.063 00.893 3

WFCM210.218 00.973 3

SWFCM90.172 00.973 3

由表3可知，盡管WFCM和SWFCM的用時多于SFCM，由于具有自動特征選擇能力，WFCM和SWFCM的準確率都高于SFCM;WFCM與SWFCM相比較，SWFCM的迭代次數更少，用時也更少。

表4 三個算法對Breast-cancer數據的分類結果

NTA

SFCM40.156 00.601 8

WFCM290.733 00.787 7

SWFCM70.328 00.944 4

由表4可見，SWFCM的準確率遠遠高于SFCM和WFCM。從迭代次數和用時來看，WSFCM比WFCM要少得多。

4 結 語

基于特征加權的FCM(WFCM)聚類算法是當前聚類算法研究的熱點，WFCM存在的主要缺點是:收斂速度慢，對噪聲敏感。考慮到實際工程應用中不可避免會有噪聲，所使用的聚類算法必須對噪聲不敏感。為此，本文將截集FCM(SFCM)聚類算法和特征加權FCM(WFCM)聚類算法相結合，提出了截集型特征加權模糊C-均值(SWFCM)聚類算法。實驗結果表明，SWFCM不僅具有良好的特征選擇能力和很強的抗噪聲性能，而且具有較高的收斂速度，是一種經濟有效、可供選擇的聚類算法。

參考文獻

[1]CHIEHYUAN Tsai， CHIU Chuang-cheng. Developing a feature weight self-adjustment mechanism for a K-means clustering algorithm[J]. Computational Statistics and Data Analysis， 2008， 52(10): 4658-4672.

[2]JING L， NG M K， HUANG J Z. An Entropy Weighting K-Means Algorithm for Subspace Clustering of High-dimensional Sparse Data[J]. IEEE Trans. on Knowledge and Data Engineering， 2007， 19(8): 1026-1041.

[3]WANG X Z， WANG Y D， WANG L J. Improving fuzzy feature C-means clustering based on feature-weight learning[J]. Pattern Recognition Letters， 2004， 25(10): 1123-1132.

[4]FRIGUIH， NASRAOUI O. Unsupervised learning of pro-totypes and attribute weights[J]. Pattern Recognition， 2004， 37(3): 567-581.

[5]李潔， 高新波， 焦李成. 基于特征加權的模糊聚類新算法[J]. 電子學報， 2006， 34(1): 89-92.

[6]HUNG W L， YANG M S， CHEN D H. Bootstrapping approach to feature-weight selection in fuzzy C-means algorithms with an application in color image segmentation[J]. Pattern Recognition Letters， 2008， 29(9): 1317-1325.

[7]陳新泉. 特征加權的模糊C聚類算法[J]. 計算機工程與設計， 2007， 28(22): 5329-5333.

[8]裴繼紅， 范九倫， 謝維信. 一種新的高效軟聚類算法: 截集模糊C-均值聚類算法[J]. 電子學報，1998， 26(2): 83-86.

[9]YANG Miin-shen， WU Kuo-lung. Alpha-cut implemented fuzzy clustering algorithms and switching regressions[J]. IEEE Trans. on Systems， Man and Cybernetics， Part B， 2008， 38(3): 588-603.

[10]LI Y H， DONG M， HUA J. Localized feature selection for clustering [J]. Pattern Recognition Letters， 2008， 29(1): 10-18.

[11]BLAKE C L， MERZ C J . UCI repository of machine learning Databases[EB/OL]. \\. http: //archive. ics. uci. edu/ml/.