基于PSO自動確定聚類數目的FCM算法

肖劍文 周亦敏

摘要：模糊C均值聚類是聚類分析中應用最廣泛的算法之一，但是聚類數目需要人為預先設定，在實際應用中有極大的局限性。提出一種自動確定聚類數目的基于粒子群的模糊C均值聚類算法，通過對不同聚類數目進行試驗，利用添加粒子閾值向量自動確定最佳的聚類數目。在預設的最大聚類數目內隨機分割數據集，利用重構準則重新構建初始值，以此克服需要事先設置聚類數目的模糊C均值缺點。利用有效性函數評估算法性能，試驗結果表明，該算法能自動找到最優聚類數目，聚類效果很好。

關鍵詞：模糊C均值;粒子群;粒子閾值;重構準則;有效性函數

FCM Algorithm Based on PSO for Automatically Determining the Number of Clusters

XIAO Jiao?wen，ZHOU Yi?min

（School of Optical?electrical and Computer Engineering，University of Shaghai

for Science and Technology， Shanghai 20093， China）

Abstract：Fuzzy C?means clustering is one of the most widely used algorithms in cluster analysis. However， the number of clusters needs to be preset manually， which has great limitations in practical applications. In this paper， a particle swarm optimization fuzzy C?means clustering algorithm is proposed to automatically determine the number of clusters. This algorithm uses the additive particle threshold vector to automatically determine the optimal number of clusters by experimenting with different cluster numbers. The algorithm firstly randomly divides the data set within the preset maximum number of clusters， reconstructs the initial value by using the reconstruction criterion， and overcomes the shortcomings of the fuzzy C?means that need to set the number of clusters in advance， and uses the validity function to evaluate the algorithm. The experimental results show that the algorithm can automatically find the optimal number of clusters and achieve a good clustering effect.

Key Words：fuzzy C?means ;particle swarm optimization; particle threshold ;reconstruction criterion;validity function

0?引言

與分類[1]的監督算法不同，聚類[2]屬于無監督算法，指在沒有先驗知識的情況下將數據分為多個類或簇，同一類中的數據具有較高的相似性[3]，不同類之間的數據相似性盡可能低。傳統的聚類分析都是把數據硬性地劃分到某一類中，而現實的事物大都具有模糊性，即事物之間的劃分界限不明顯。模糊聚類[4]方法中每個樣本與聚類中心點之間存在著隸屬關系，展示了類屬的模糊性，能更好反映現實世界。

聚類分析是無監督模式識別[5]的重要研究課題之一。模糊聚類能更客觀地反映現實世界，因為它建立了樣本到類的不確定性描述。傳統模糊聚類算法的主要缺點是無法自動確定最優排序的聚類數，為了準確完成聚類需要事先確定聚類數目。但是對于一些線性不可分的數據、分布較為復雜的數據，即使給定了最優的聚類數目也很難得到理想的聚類效果，作為模糊聚類典型代表的模糊C均值聚類（FCM）[6]也有此缺點。

當前通常采用有效性函數[7]分析聚類結果以此確定群集的最佳數目，其中有效性函數分為兩類：①基于數據集分區的模糊方法;②通過基于數據集的幾何圖元。其中具有代表意義的方法有以下4種：

（1）Bedzek[8]提出的分區系數（Partition Coefficient），它的目的是測量群集之間的重疊程度，其值越大代表聚類效果越好。

（2）香農[9]提出的分類概念熵，索引值越小代表聚類效果越好。

（3）Win[10]提出的有效性函數?V?kwon，是對謝本尼Xie-Beni指數的一種改進。它能有效抑制指數值的下降使其不再為0，其值越小代表聚類效果越好。

（4）Bensay[11]提出的有效性函數?V?bsand，其值越小代表聚類效果越好。

但是通過分析結果確定聚類的最佳數目使計算開銷大大增加，對此本文提出了一種新的自動確定聚類數目的基于粒子群（PSO）的模糊C均值聚類算法（FCM），該算法能自動確定最優聚類數，并通過重構函數大大降低計算開銷。為證明該算法的有效性，通過在UCI機器學習庫[12]的5個數據集上進行MATLAB仿真模擬實驗，同時通過有效性函數對聚類結果進行驗證。結果表明，自動確定聚類數目的基于PSO的FCM算法能夠自動確定最優聚類數目，聚類效果很好。

1?粒子群算法與模糊C均值聚類

1.1?粒子群算法（PSO）

粒子群算法（PSO）由Eberhart和Kennedy[13]設計的一種群搜索算法。該算法通過模擬鳥群捕食行為進行設計。假設區域里只有一塊食物（即優化問題中所講的最優解），鳥群的任務是找到這個食物源。鳥群在整個搜尋過程中通過相互傳遞信息告知其它鳥自己的位置，通過這樣的協作判斷找到的是不是最優解，同時也將最優解信息傳遞給整個鳥群，最終整個鳥群都聚集在食物源周圍，即找到最優解，問題收斂。

在下一次迭代中，粒子的速度和位置更新公式如下：

其中，i=1，2，…，N，第i個粒子的速度為V?i=（v?1，v?2，…，v?d），第i個粒子的位置為X?i=（x?1，x?2，…，x?d），r?1，r?2為兩個隨機數，滿足[0，1]之間的隨機均勻分布，并且兩個數之間相互獨立。t為當前迭代的次數，c?1，c?2是學習因子，為兩個非負的常數，w為遞減的慣性因子。

1.2?模糊C均值聚類（FCM）

模糊聚類允許一個數據屬于兩個或多個聚類。 FCM算法是一種迭代分區聚類技術，由Dunn[14]引入并由Bezdek[15]擴展。 FCM是一個非常標準的最小二乘誤差模型，是早期非常流行的非模糊C?means模型的推廣，該模型可以生成硬數據集群。通過加權迭代目標函數的最小化平方誤差組的和得到最優結果。假設?X={x?1，x?2，…，x?n}是要進行聚類的數據集，每個數據具有m個屬性，標準的模糊C均值聚類將每個對象x?i（1≤i≤N）分配給具有ac×N隸屬度矩陣[16]U = {u?ij}的第c個聚類。 u?ij表示屬于第i組的第j個對象的隸屬度。

標準模糊c均值方法由下列等式定義：

因此，標準的模糊C均值聚類算法目標是為了計算隸屬度矩陣以及聚類中心點C={c?i，c?2，…，c?c}。給定數據集X，標準模糊c均值算法隨機初始化隸屬度矩陣，然后通過最小化目標函數J?m更新隸屬度矩陣和聚類中心，其目標函數如下：

其中m為模糊因子，一般取值為2，d?ik表示x?k和v?i之間的距離，通常是歐式距離：

FCM算法步驟如下：

（1）初始化參數，包括初始化模糊因子?m，給定聚類中心點個數c，最大迭代次數T?max以及最小迭代誤差?ε，令初始迭代次數t=1。

（2）初始化隸屬度矩陣U=[u?ij]。

（3）利用隸屬度矩陣Ut計算聚類中心點C，公式如下：

（4）利用下式更新隸屬度矩陣?Ut+1?：

（5）判斷算法是否滿足終止條件，滿足則終止算法輸出結果，否則令?t=t+1?，返回步驟（3）。

2?編碼方式

2.1?粒子編碼

粒子是2×c矩陣，其中c是預定義的最大聚類數目。 第一行代表中心， 第二行中的每個值控制第一行中每個中心的激活。

X?i=x?i?1，1x?i?1，2…x?i?1，c?t?i?2，1t?i?2，2…t?i?2，c

其中，?x?i?1，c?代表粒子在類c中的位置，其范圍在[?x?min，?x?max]之間。?t?i?2，c?為粒子的閾值，范圍為[0，1]。 如果閾值大于0.5則激活聚類中心，否則它將被停用。

2.2?速度編碼

速度矩陣與位置矩陣具有相同大小，設置速度的范圍為[?v?min，?v?max]，速度的所有值都應該在?v?min和?v?max之間，因此粒子的速度表示為：

V?i=v?i?x1，1v?i?x1，2…v?i?x1，c?v?i?t2，1v?i?t2，2…v?i?t2，c

同樣，?c?是最大簇數。 第一行是中心的速度，第二行是閾值的速度。

2.3?解碼

X=（x?1，x?2，…，x?n）是具有d維的數據集， 可用公式（8）將聚類中心解碼為C=（c?1，c?2，…，c?c）?。

2.4?有效性函數

聚類有效性分析目的是為了評估聚類效果以找到最合適的分類數目，因此采用有效性函數評估聚類結果，通過結果分析發現最佳的聚類數目。類內緊湊度和類間分離度是衡量數據聚類效果的兩個常用標準。常規方法是使用不同的聚類數目迭代運行算法，通過有效性函數判斷最佳的聚類數目，下面是常用的模糊聚類中的有效性函數：

（1）最小平方誤差（SE）[17]：

其中，x?i是具有d維屬性的數據點，c?j是第j類數據集的值，‖x?i-c?j‖是x?i和c?j的歐幾里得距離， J?m最小時聚類效果最好。

（2）分區系數（PC）[18]指數：

當PC值越大時聚類效果越好。

（3）分區熵（PE）[19]索引：

其中?b?是對數基數， PE越小聚類效果越好。

（4）XB[20]指標：

XB值越小聚類效果越好。

3?自動確定聚類數目的FCM算法

通過以上分析，基于PSO得到自動確定聚類數目的FCM算法，具體步驟如下：

（1）輸入數據集?X={x?1，x?2，…，x?n}，聚類數目c，模糊因子c。

（2）隨機初始化一個粒子群，設置t=1。

（3）利用式（1）更新每個粒子速度。

（4）利用式（2）更新每個粒子位置。

（5）更新局部最優值和全局最優值。

（6）計算分區矩陣U。

（7）判斷是否滿足算法終止條件。滿足進入步驟（8），否則返回步驟（3），同時令t=t+1。

（8）利用全局最優矩陣重新構造原始數據。

（9）計算重構誤差。為了使用一致的方法評估4個不同的有效性函數，這里使用RC重構標準[21]，使用簇原型和分區矩陣重建原始數據，?X={x?1，x?2，…，x?n}?計算公式如下：

重構完成后，使用式（15）評判重構值和原始值之間的平方誤差：

（10）選擇重構誤差最小的分區矩陣和中心。

4?試驗結果與分析

本試驗測試的仿真環境如下：CPU為AMD 四核 FX 7500 up to 3.3GHz，8G內存，MATLAB2010編程環境，表1列出了算法參數。

為驗證算法性能，選擇來自機器學習數據庫UCI中的數據集進行試驗，數據集的詳細描述信息見表2。

使用上面提到的4種有效性指標驗證試驗結果，通過式（10）-式（13）使用所提算法計算數據集的重構誤差，聚類數目的取值范圍為2-9，粗體值是每個度量具有不同簇編號的最小重建誤差。8組試驗中的6組表明?c?=2是最佳聚類數目，試驗結果見表3。

對提出的算法進行驗證，在50次運行中測試所提算法并計算表4列出的平均最佳數據數目，括號中的值是標準誤差。結果表明，本文提出的算法可獲得最優的聚類數目，實驗結果如表4所示。

5?結語

本文提出了一種自動確定聚類數目的基于PSO的FCM算法，以克服傳統聚類算法中需要人為輸入聚類數目的缺陷。利用閾值向量控制聚類的數量，同時通過迭代模糊分區的方法解決聚類問題。使用來自UCI機器學習庫的5個數據集進行模擬仿真實驗，結果表明本文所提出的算法能夠找到最優的聚類數目，得到很好的聚類結果。

本文不足之處：由于引入了粒子閾值向量控制聚類數目，而算法初始聚類中心是隨機選取的，在一定程度上影響算法的執行效率。為了避免最佳聚類數目不在所設定的范圍內，需要設定較大的最大聚類數目以保證最佳聚類數目包含其中，這需要一定的先驗知識作為基礎，這都是有待進一步研究與完善的地方。

參考文獻：

[1]?劉紅巖，陳劍，陳國青.數據挖掘中的數據分類算法綜述[J].清華大學學報：自然科學版，2002，42（6）：727?730.

[2]?伍育紅.聚類算法綜述[J].計算機科學，2015，42（6）：491?524.

[3]?GRAVES D，PEDRYCZ W.Kernel?based fuzzy clustering and fuzzy clustering：a comparative experimental study[J].Fuzzy Sets and Systems，2010，161（4）：522?543.

[4]?王春花.基于模糊C?均值聚類的圖像分割技術研究[D].大連：遼寧師范大學，2008.

[5]?程于潔，肖華瓶.模式識別發展及現狀綜述[J].好家長，2018（84）：68?69.

[6]?BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York： Plenum， 1981.

[7]?邱學芹.模糊聚類算法及其聚類有效性的研究[D].青島：青島理工大學，2010.

[8]?BEDZEK J C. Cluster validity with fuzzy sets [J]. Journal of Cybernetics ，1973，3 （3）：58?72.

[9]?SHANNON C E. A mat hematical theory of communication[J] .Bell Syst Tech ，1948，XXVII（3）：379?423.

[10]?KWON S H.Cluster validity index for fuzzy clustering[J] .Elect ronics Letters ，1998，34（22）：2176?2177.

[11]?BENSAID A M.Validity?guided（re） clustering with applications to imgae segmentation[J].IEEE Transaction on Fuzzy Systems ，1996 ，4（2） ：112?123.

[12]?ASUNCION A， NEWMAN D J. UCI machine learning repository[EB/OL]. http：//www.ics.uci.edu/mleamlMLRepository.html.

[13]?EBERHART R C，KENNEDY J. A new optimizer using particle swarm theory[C].Proceedings of?6th Symp of Micro Machine and Human Science 1995： 29?43.

[14]?DUNN J C.A fuzzy relative of the ISODATA process and its use in detecting compact well?separated clusters[J].Journal of Cybernetics ，1973（3）：32?57.

[15]?BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M]. New York：Plenum Press，1981.

[16]?朱書偉.基于群體智能的多目標聚類算法研究[D].無錫：江南大學，2016.

[17]?BEZDEK J C. Cluster validity with fuzzy sets[M]. New York：Plenum Press ，1973：58?73

[18]?BEZDEK J C .Pattern recognition with fuzzy objective function algorithms[M]. New York：Plenum Press， 1981.

[19]?BEZDEK J C， CORAY C， GUNDERSON R，etal.Detection and characterization of cluster substructure I. linear structure： fuzzy c?lines[J].SIAM Journal on Applied Mathematics， 2006：40（2）， 339?357.

[20]?PAL N R， BEZDEK J C.On cluster validity for the fuzzy c?means model[C]. IEEE Transactions on Fuzzy Systems， 1995， 3（3）：370?379.

[21]?PEDRYCZ W ， DE OLIVEIRA J V.A development of fuzzy encoding and decoding through fuzzy clustering[J].IEEE Transactions on Intrumentation and Measurement， 2008，57（4）：829?837.