洪年松，范　淵，郭華峰

（浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，浙江溫州325003）

基于Bootstrap的加權(quán)FCM改進(jìn)算法*

洪年松，范淵，郭華峰

（浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，浙江溫州325003）

為了提高模糊C-均值聚類算法的收斂速度，Yang等引入截斷因子，提出了截斷閾值模糊C-均值（FCMα）聚類算法，加快了算法的收斂。然而該算法也存在著聚類效果不佳的問題。針對該問題，使用Bootstrap統(tǒng)計(jì)方法進(jìn)行特征加權(quán)，提出了基于Bootstrap的加權(quán)模糊C-均值聚類改進(jìn)算法。實(shí)驗(yàn)表明，該算法具有更高的聚類準(zhǔn)確率，也更有效。

FCM；截斷閾值；Bootstrap；特征加權(quán)

0　引言

為了改善模糊C-均值（FCM）聚類算法的聚類效果，學(xué)者做了多方面的研究，包括特征加權(quán)和樣本加權(quán)等幾個方面。特征加權(quán)方面，袁正午等通過ReliefF算法實(shí)現(xiàn)特征權(quán)值的自動確定，提出了一種特征加權(quán)自適應(yīng)FCM算法［1］，提高了算法的聚類精度。蔡靜穎等則引入自適應(yīng)馬氏距離對特征加權(quán)進(jìn)行處理，提出了一種基于馬氏距離特征加權(quán)的模糊聚類算法［2］，提升了分類的有效性。樣本加權(quán)方面，劉兵等提出了一種基于樣本加權(quán)的可能性模糊聚類算法［3］，該算法具有更快的收斂速度和更強(qiáng)的魯棒性。段林珊等則受熱力學(xué)中熵定義的啟發(fā)，提出了一種基于模擬退火的樣本加權(quán)FCM算法［4］，提高了分類的準(zhǔn)確數(shù)和準(zhǔn)確率。與FCM算法類似，F(xiàn)CM的改進(jìn)算法——FCMα算法［5］也存在著聚類效果不佳的問題。為了解決這個問題，本文將引入Bootstrap統(tǒng)計(jì)方法，對數(shù)據(jù)進(jìn)行特征加權(quán)，改善FCMα算法的收斂效果。

1　截斷閾值模糊C-均值聚類算法

為了改善FCM算法收斂速度慢的問題，YANG等引入截斷因子，提出了截斷閾值模糊C-均值（FCMα）聚類算法［5］，加快了算法的收斂。FCMα算法步驟如下：

①設(shè)定模糊指數(shù)1＜m＜∞，分類數(shù)2≤c≤n，迭代次數(shù)l=0，迭代終止閾值ε＞0，截斷閾值0.5≤α≤1，初始化中心點(diǎn)起始值Z（0）。

②根據(jù)公式（1）計(jì)算隸屬值μij。

③使用以下方法更新μij，i=1，...，n，j=1，...，c：如果μis=max1≤j≤cμij＞α，那么μis=1，μis'=0，s'≠s。

④根據(jù)公式（2）計(jì)算中心點(diǎn)Z（l+1）。

否則l=l+1，并回到步驟②。

FCMα算法雖然收斂速度得到了提升，但其聚類效果仍有改善的空間，下面將在該算法中引入Bootstrap特征加權(quán)方法。

2　截斷閾值FCM算法的特征加權(quán)

2.1基于Bootstrap的特征加權(quán)方法

Bootstrap統(tǒng)計(jì)方法是現(xiàn)代統(tǒng)計(jì)學(xué)較為流行的一種統(tǒng)計(jì)方法，在小樣本統(tǒng)計(jì)時效果很好。Bootstrap方法由B.Efron提出［6］，其主要思想是從原始數(shù)據(jù)中重復(fù)抽樣以幫助我們認(rèn)識樣本特征，從而進(jìn)一步認(rèn)識母體特征。其基本步驟為：①采用重復(fù)抽樣技術(shù)從原始樣本中抽取給定數(shù)量的樣本。②根據(jù)抽出的樣本計(jì)算給定的統(tǒng)計(jì)量T。③重復(fù)上述B次，得到B個統(tǒng)計(jì)量T。④計(jì)算上述B個統(tǒng)計(jì)量T的樣本方差。

根據(jù)Bootstrap方法的以上特點(diǎn)，F(xiàn)CMα算法所處理的數(shù)據(jù)樣本可以使用該方法來計(jì)算特征權(quán)重，其計(jì)算步驟設(shè)計(jì)如下：

①給定重復(fù)抽樣次數(shù)B，使用重復(fù)抽樣技術(shù)從樣本X=（x1，x2，…，xn）?RP中進(jìn)行B次有放回的重復(fù)抽樣，得到樣本，，i=1，2，…，n，b=1，2，…，B，其中P為樣本維數(shù)。

②使用公式（3）計(jì)算各次重復(fù)抽樣的特征權(quán)重：

③使用公式（4）計(jì)算樣本最終的特征權(quán)重：

2.2基于Bootstrap的特征加權(quán)FCM改進(jìn)算法

其中wk表示樣本在第k個特征的加權(quán)，k=1，2，…，P。使用新距離對FCMα算法進(jìn)行推算，就可以得到新的特征加權(quán)FCMα（簡稱WFCMα）算法，其迭代方程更新如下：

則新提出的WFCMα算法步驟如下：

①使用基于Bootstrap的特征加權(quán)方法計(jì)算樣本特征權(quán)重。

②設(shè)定模糊指數(shù)1＜m＜∞，分類數(shù)2≤c≤n，迭代次數(shù)l=0，迭代終止閾值ε＞0，截斷閾值0.5≤α≤1，初始化中心點(diǎn)起始值Z（0）。

③根據(jù)公式（7）計(jì)算隸屬值μij。

④使用以下方法更新μij，i=1，...，n，j=1，...，c：如果μis=max1≤j≤cμij＞α，那么μis=1，μis'=0，s'≠s。

⑤根據(jù)公式（6）計(jì)算中心點(diǎn)Z（l+1）。

否則l=l+1，并回到步驟③。

觀察算法可以發(fā)現(xiàn)，與FCMα算法相比，WFCMα算法多了第一步，即特征權(quán)重的計(jì)算，以及特征權(quán)重到算法的代入。為了驗(yàn)證WFCMα算法的效果，進(jìn)行如下實(shí)驗(yàn)。

3　仿真實(shí)驗(yàn)

3.1數(shù)據(jù)集

采用正態(tài)分布的二維人工數(shù)據(jù)集和真實(shí)的高維數(shù)據(jù)集來驗(yàn)證算法的有效性。其中二維人工數(shù)據(jù)集有兩個。第一個數(shù)據(jù)集分別以（3，4）、（7，4）為期望，單位矩陣I2為協(xié)方差矩陣。隨機(jī)生成2堆正態(tài)分布的數(shù)據(jù)點(diǎn)，每堆100個數(shù)據(jù)，共200個數(shù)據(jù)點(diǎn)，如圖1所示。第二個數(shù)據(jù)集分別以（3，4）為期望，單位矩陣I2為協(xié)方差矩陣，（7，4）為期望，矩陣為協(xié)方差矩陣。隨機(jī)生成2堆正態(tài)分布的數(shù)據(jù)點(diǎn)，每堆100個數(shù)據(jù)，共200個數(shù)據(jù)點(diǎn)，如圖2所示。真實(shí)的高維數(shù)據(jù)集則采用經(jīng)典的Iris數(shù)據(jù)集［7］。

圖1　隨機(jī)生成的正態(tài)分布數(shù)據(jù)集1

圖2　隨機(jī)生成的正態(tài)分布數(shù)據(jù)集2

3.2實(shí)驗(yàn)

在圖1和圖2所示的數(shù)據(jù)集中使用新提出的WFCMα算法和FCMα算法，取模糊度m=2，分類數(shù)c=2，截斷閾值α=0.6，其他的初始條件也設(shè)置相同，執(zhí)行上述兩種算法，得到如表1所示的結(jié)果：

表1　WFCMα算法和FCMα算法對圖1和圖2數(shù)據(jù)集的聚類結(jié)果

從表1的結(jié)果可知，相對于FCMα算法的平均權(quán)重，WFCMα算法給出了更自然的權(quán)重因子，其聚類準(zhǔn)確率也得到了一定的提升。以上是算法在人工數(shù)據(jù)集中的表現(xiàn)，下面進(jìn)行真實(shí)高維數(shù)據(jù)集的實(shí)驗(yàn)。

實(shí)驗(yàn)二，在Iris數(shù)據(jù)集中分別使用WFCMα算法和FCMα算法，設(shè)定分類數(shù)c=2，截斷閾值α=0.6，其他的初始條件也設(shè)置相同，在模糊指數(shù)m等于1.2，2.0，5.0，10.0的情況下，執(zhí)行上述兩種算法，得到如表2所示的結(jié)果：

表2　WFCMα算法和FCMα算法對Iris數(shù)據(jù)集的聚類結(jié)果

表2的數(shù)據(jù)表明，在真實(shí)的數(shù)據(jù)集中，WFCMα算法的表現(xiàn)非常優(yōu)異，在不同的模糊指數(shù)下都取得了更好的準(zhǔn)確率，聚類精度更高。這說明，相比較FCMα算法的平均特征權(quán)重取值，使用Bootstrap方法得到的特征權(quán)重更符合實(shí)際，基于Bootstrap的WFCMα算法也更有效。

4　結(jié)論

為了提高FCMα算法的聚類效果，在算法中引入Bootstrap統(tǒng)計(jì)方法，提出了基于Bootstrap的特征加權(quán)FCM改進(jìn)（WFCMα）算法。仿真實(shí)驗(yàn)表明，相對于FCMα算法的平均權(quán)重，WFCMα算法得到的樣本特征權(quán)重更自然，更適用于實(shí)際情況，改進(jìn)后的算法也具有更好的聚類效果，更有效。

［1］袁正午，魏榮，葉明星.一種適用于基因表達(dá)數(shù)據(jù)的特征加權(quán)FCM算法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（7）:2483-2485.

［2］蔡靜穎，謝福鼎，張永.基于馬氏距離特征加權(quán)的模糊聚類新算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（5）:198-200.

［3］劉兵，夏士雄，周勇，韓旭東.基于樣本加權(quán)的可能性模糊聚類算法［J］.電子學(xué)報，2012，40（2）:371-375.

［4］段林珊，劉培玉，謝方方.基于模擬退火的樣本加權(quán)FCM算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（6）:2004-2008.

［5］M.S.Yang，K.L.Wu，J.N.Hsieh，etal.Alpha-cut implemented fuzzy clusteringalgorithmsand switching regressions［J］.IEEE Transactionson Systems，Man，and Cybernetics，2008，38（3）:588-603.

［6］B.Efron.Bootstrap Methods--Another Look at the Jackknife［J］.The AnnalsofStatistics，1979，7（1）:1-26.

［7］C.L.Blake，C.J.Merz.UCI repository ofmachine learning databases.［http://archive.ics.uci.edu/m l/］.Irvine，CA:University of California，Departmentof Information and Computer Science，1998.

（責(zé)任編輯：潘修強(qiáng)）

Weighted Im proved Fuzzy C-MeansClustering Algorithm based on Bootstrap

HONGNian-song，F(xiàn)AN Yuan，GUOHua-feng
（Collegeof Information and Communications，Zhejiang Industry&Trade VocationalCollege，Wenzhou，325003，China）

To improve the convergence speed of the fuzzy C-means clustering algorithm，alpha-cut factor is introduced by Yang etal.and thealpha-cut threshold fuzzy C-means（FCMα）clustering algorithm is proposed，which accelerates the convergence.However，the FCMαalgorithm also has the problem of poor clustering effect.To solve the problem，the Bootstrap statisticalmethod isused to carry on the featureweighting，and theweighted im proved fuzzy C-mean clustering algorithm based on Bootstrap is proposed.The experimentsshow that the proposed algorithm hashigher clustering accuracy and beenmoreeffective.

FCM；alpha-cut threshold；Bootstrap；featureweighting

TP301.6

A

1672-0105（2015）03-0057-03

10.3969/j.issn.1672-0105.2015.03.013

2015-07-25

溫州市公益性科技計(jì)劃項(xiàng)目（G20140049），浙江工貿(mào)職業(yè)技術(shù)學(xué)院教師科技創(chuàng)新活動計(jì)劃項(xiàng)目（X140203）

洪年松，碩士，浙江工貿(mào)職業(yè)技術(shù)學(xué)院講師，主要研究方向：模式識別、圖像處理；范淵，碩士，浙江工貿(mào)職業(yè)技術(shù)學(xué)院講師，主要研究方向：圖像處理；郭華峰，碩士，浙江工貿(mào)職業(yè)技術(shù)學(xué)院講師，主要研究方向：圖像處理、模式識別。