一種基于SOM 改進(jìn)的PCM 聚類方法

蘭雁寧，鄭陳達(dá)

（1.上海電力大學(xué)，上海 200090；2.國網(wǎng)福建省電力有限公司電力科學(xué)研究院，福建 福州 350007）

在大數(shù)據(jù)背景下，數(shù)據(jù)挖掘技術(shù)逐漸成為當(dāng)今熱門的研究課題。聚類算法作為一類重要的數(shù)據(jù)挖掘方法，被廣泛地運(yùn)用于無標(biāo)簽數(shù)據(jù)處理問題中。在機(jī)器學(xué)習(xí)領(lǐng)域，聚類算法是各類無監(jiān)督學(xué)習(xí)方法的基礎(chǔ)。目前已有許多不同的聚類方法被相繼提出，包括順序聚類法、層次聚類法、k 均值聚類法、模糊c 均值聚類法等。其中模糊c 均值聚類法（FCM）不同于以往聚類方法采用的“硬劃分”手段，而考慮了大多數(shù)聚類對(duì)象在類屬方面存在的中介性，及對(duì)象的類別劃分界限并非嚴(yán)格分明的。模糊c 均值聚類將模糊理論引入聚類算法，聚類過程中體現(xiàn)了數(shù)據(jù)類別不確定的描述，從而使聚類結(jié)果更為客觀。

為克服傳統(tǒng)的模糊c 均值算法易受樣本噪聲影響，聚類結(jié)果具有隨機(jī)性的缺點(diǎn)，有學(xué)者提出了可能性c 均值聚類算法（PCM）。PCM 算法在一定程度上解決了聚類過程易受樣本奇異值影響的缺點(diǎn)，但算法本身對(duì)初始聚類中心的選取非常敏感。為此，本文借助自組織映射（SOM）網(wǎng)絡(luò)對(duì)數(shù)據(jù)樣本進(jìn)行原始聚類，將得到的網(wǎng)絡(luò)權(quán)值分布作為PCM 初始聚類中心，有效增強(qiáng)了聚類效果及算法效率。

1 PCM 聚類

假設(shè)有數(shù)據(jù)集X={X1，X2，...，XN}，N 為數(shù)據(jù)集樣本數(shù)量。數(shù)據(jù)集中任一樣本xj為包含n維數(shù)據(jù)的向量，xj=[x1，x2，...，xn]。聚類算法即根據(jù)事物之間的相似度進(jìn)行類別劃分，被劃分到同一類的對(duì)象在某一方面的相似度最大。若數(shù)據(jù)集X 表示描述某一對(duì)象的N 個(gè)樣本，每一樣本包含該對(duì)象的n 個(gè)屬性。那么模糊c 均值聚類算法就是根據(jù)數(shù)據(jù)集X 進(jìn)行C 劃分，從而將聚類對(duì)象劃分進(jìn)C 個(gè)類別中。隸屬度μij表示聚類對(duì)象各樣本與類的隸屬關(guān)系，其滿足的條件如式（1）所示。

模糊c 均值聚類（FCM）算法采用隸屬度衡量樣本數(shù)據(jù)對(duì)某個(gè)聚類的隸屬程度，并將其作為權(quán)值，通過加權(quán)迭代計(jì)算使數(shù)據(jù)到聚類中心的距離最短，算法的目標(biāo)函數(shù)如式（2）。式中，m為加權(quán)指數(shù)，其取值大小將影響聚類效果，通常取2；dij表示樣本j到第i類聚類中心的距離；μij是樣本j對(duì)聚類i的隸屬度。

對(duì)目標(biāo)函數(shù)求偏導(dǎo)，結(jié)合式（1）中的約束條件，利用拉格朗日系數(shù)法可分別得到隸屬度與聚類中心的迭代公式如式（3）。

不難看出，F(xiàn)CM 算法的核心在于聚類中心和隸屬函數(shù)反復(fù)迭代運(yùn)算的過程，從給定的初始聚類中心逐步收斂至最終的聚類中心。這種迭代實(shí)質(zhì)上是一種局部尋優(yōu)的過程，因此計(jì)算過程可能陷入局部最優(yōu)解。在工程實(shí)踐中，待處理的數(shù)據(jù)樣本中往往含有一定量的孤立點(diǎn)或噪聲。根據(jù)模糊理論中針對(duì)隸屬度的典型性原理，樣本中的噪聲等都是屬于代表性較差的點(diǎn)，應(yīng)該降低這類點(diǎn)對(duì)隸屬度的影響以提高聚類效果。PCM 算法在模糊c 均值聚類基礎(chǔ)上進(jìn)行改進(jìn)，在目標(biāo)函數(shù)中引入懲罰項(xiàng)，同時(shí)放松了約束限制，提高了算法抗噪能力，其目標(biāo)函數(shù)及約束條件為如式（4）。

式中的ηi為懲罰參數(shù)，其取值可通過式（5）計(jì)算得到。

類似于式（3）中模糊c均值的迭代公式，此時(shí)隸屬度以及聚類中心可由式（6）得到。

相較于FCM 聚類，PCM 聚類方法可以受噪聲數(shù)據(jù)影響小，算法魯棒性更強(qiáng)，聚類結(jié)果更為合理，但是，它的缺點(diǎn)也很明顯。傳統(tǒng)的FCM 算法迭代過程中聚類中心位置是動(dòng)態(tài)變化的，各聚類中心之間互相影響從而相互重合的概率極小。但是PCM 算法中，由于放松了限制條件，各聚類中心之間不存在耦合關(guān)系，彼此相互獨(dú)立故可能產(chǎn)生重合的聚類中心。

2 改進(jìn)的聚類算法

SOM 網(wǎng)絡(luò)屬于競爭型神經(jīng)網(wǎng)絡(luò)，是一種基于無監(jiān)督學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)重要類型。SOM 網(wǎng)絡(luò)能夠通過輸入樣本學(xué)會(huì)其規(guī)律性，并且根據(jù)輸入樣本相互之間的關(guān)系逐步調(diào)整節(jié)點(diǎn)連接權(quán)值，使網(wǎng)絡(luò)結(jié)構(gòu)與輸入樣本相適應(yīng)。訓(xùn)練好的SOM 網(wǎng)絡(luò)具有識(shí)別輸入向量，并將相似向量靠近排列的功能。SOM 網(wǎng)絡(luò)通過競爭層中互相靠近的神經(jīng)元對(duì)相似的輸入向量產(chǎn)生響應(yīng)，并將響應(yīng)結(jié)果反映在一維或二維空間上。因此，SOM 網(wǎng)絡(luò)不但能學(xué)習(xí)輸入向量的分布情況，還可以表示輸入向量的拓?fù)浣Y(jié)構(gòu)，同時(shí)將具有相似性的數(shù)據(jù)映射到低維空間中的內(nèi)鄰近的區(qū)域內(nèi)，實(shí)現(xiàn)了高維可視化功能。

SOM 網(wǎng)絡(luò)由輸入層和競爭層構(gòu)成，輸入層神經(jīng)元與競爭層神經(jīng)元全連接，負(fù)責(zé)將輸入數(shù)據(jù)經(jīng)連接權(quán)值傳送至競爭層神經(jīng)元；競爭層神經(jīng)元之間兩兩互聯(lián)，其連接權(quán)值隨輸入數(shù)據(jù)不斷調(diào)整。輸入層神經(jīng)元個(gè)數(shù)由輸入向量維數(shù)確定，競爭層神經(jīng)元個(gè)數(shù)可人為設(shè)定。網(wǎng)絡(luò)學(xué)習(xí)的基本思想是，比較輸入向量與網(wǎng)絡(luò)連接權(quán)值之間的距離（通常是歐氏距離），找到距離最近的競爭層神經(jīng)元作為“優(yōu)勝”神經(jīng)元。調(diào)整“優(yōu)勝”神經(jīng)元及其附件的神經(jīng)元的連接權(quán)值，使其更接近輸入數(shù)據(jù)，不斷重復(fù)以上過程直至訓(xùn)練結(jié)束。整個(gè)訓(xùn)練過程可以看成通過無監(jiān)督學(xué)習(xí)發(fā)現(xiàn)輸入數(shù)據(jù)間的相似模式并進(jìn)行聚類。一個(gè)SOM 網(wǎng)絡(luò)的競爭層神經(jīng)元多被設(shè)置成六邊形網(wǎng)格，輸入網(wǎng)絡(luò)的高維向量被映射到六邊形網(wǎng)格組成的二維平面上，故所輸入的高維數(shù)據(jù)間的距離可以通過其在二維平面上的遠(yuǎn)近直觀展現(xiàn)出來。通常與同一個(gè)神經(jīng)元毗鄰的其他神經(jīng)元總數(shù)越多，可以認(rèn)為SOM 網(wǎng)絡(luò)的性能越好。

利用SOM 網(wǎng)絡(luò)將數(shù)據(jù)集X={X1，X2，...，XN} 劃分為C個(gè)聚類，可以生成一個(gè)輸入神經(jīng)元數(shù)為n，競爭層神經(jīng)元數(shù)為C的網(wǎng)絡(luò)。網(wǎng)絡(luò)將自動(dòng)把數(shù)據(jù)集X 中相近的向量映射到同一個(gè)競爭層神經(jīng)元上，實(shí)現(xiàn)對(duì)數(shù)據(jù)的初步聚類，聚類中心可以通過輸入層與競爭層間的連接權(quán)值獲得。故通過SOM 網(wǎng)絡(luò)改進(jìn)PCM 聚類算法的步驟如下：

（1）根據(jù)待處理的數(shù)據(jù)結(jié)構(gòu)和聚類數(shù)初始化SOM 網(wǎng)絡(luò)，包括生成網(wǎng)絡(luò)的初始連接權(quán)值、初始學(xué)習(xí)效率值以及最大迭代次數(shù)等。

（2）訓(xùn)練SOM 網(wǎng)絡(luò)。計(jì)算輸入向量與每個(gè)競爭層神經(jīng)元之間的歐式距離，得到與輸入向量具有最近距離的神經(jīng)元作為獲勝神經(jīng)元。同時(shí)修正獲勝神經(jīng)元及其鄰近神經(jīng)元的連接權(quán)值，重復(fù)訓(xùn)練過程直至達(dá)到預(yù)設(shè)的迭代次數(shù)。

（3）提取訓(xùn)練好的SOM 網(wǎng)絡(luò)連接權(quán)值作為PCM 算法的初始聚類中心，設(shè)置PCM 聚類的最大迭代次數(shù)、聚類數(shù)以及容許誤差值。

（4）根據(jù)公式（5）、（6）迭代計(jì)算隸屬度及聚類中心，至運(yùn)算達(dá)到最大迭代次數(shù)或目標(biāo)函數(shù)值小于容許誤差值后停止運(yùn)算，輸出并展示聚類結(jié)果。

3 算例分析

按照隨機(jī)等隔分布規(guī)律生成50 個(gè)向量構(gòu)成數(shù)據(jù)集，向量維度為3，數(shù)據(jù)分布如圖1 所示。現(xiàn)需將其劃分為5 個(gè)聚類，采用前文所述的算法步驟，生成3 輸入神經(jīng)元，5 競爭層神經(jīng)元的SOM 網(wǎng)絡(luò)。使用MATLAB 工具箱中的聚類分析模塊初始化SOM 網(wǎng)絡(luò)模型。由于SOM網(wǎng)絡(luò)的聚類效果和設(shè)定的迭代次數(shù)直接相關(guān)，故采取逐步增加迭代次數(shù)的訓(xùn)練策略。當(dāng)繼續(xù)增加迭代次數(shù)而競爭層神經(jīng)元權(quán)值不再發(fā)生變化時(shí)，認(rèn)為訓(xùn)練的SOM 網(wǎng)絡(luò)已經(jīng)收斂，此時(shí)得到的權(quán)值即為PCM 算法的初始聚類中心。

圖1 數(shù)據(jù)樣本分布情況

數(shù)據(jù)劃分結(jié)果以及競爭層神經(jīng)元拓?fù)浞謩e如圖2、圖3 所示，由圖可見數(shù)據(jù)集按照預(yù)設(shè)的聚類數(shù)被均勻地劃分進(jìn)5 個(gè)聚類中，且競爭層神經(jīng)元間的距離如實(shí)體現(xiàn)了數(shù)據(jù)集的結(jié)構(gòu)特征。圖4 展示了聚類算法的最終結(jié)果，其中U 符號(hào)標(biāo)記的是SOM 網(wǎng)絡(luò)得到的初始聚類中心位置?符號(hào)標(biāo)記的是最終的聚類中心。不難看出，初始聚類中心已十分接近最終的聚類中心，經(jīng)改進(jìn)后的PCM 聚類效率將大幅增加。

圖2 SOM 聚類效果

圖3 SOM 拓?fù)涫疽?/p>

圖4 聚類算法最終結(jié)果

4 結(jié)束語

聚類結(jié)果的不確定性是限制PCM 聚類算法應(yīng)用的主要原因之一，本文提出基于SOM 網(wǎng)絡(luò)改進(jìn)PCM 聚類的方法，改善了PCM 算法的聚類效果，加快了計(jì)算速度，為算法的后續(xù)改進(jìn)提供了新思路。