一種改進的多尺度可能性聚類算法

胡雅婷，曲福恒

（1.吉林農業(yè)大學 信息技術學院，長春 130118；2.長春理工大學 計算機科學與技術學院 長春 130022）

一種改進的多尺度可能性聚類算法

胡雅婷1，曲福恒2

（1.吉林農業(yè)大學 信息技術學院，長春 130118；2.長春理工大學 計算機科學與技術學院 長春 130022）

針對多尺度可能性聚類算法（MPCM）計算復雜度較高的問題，提出一種改進的多尺度可能性聚類算法（IMPCM）。算法利用k-均值聚類的收斂點來作為MPCM的初始點，在繼承了MPCM優(yōu)點的同時，解決了原始MPCM中無效初始點過多以及初始點位置不理想造成的迭代次數(shù)過高的問題。對比實驗結果表明，算法具有良好的聚類效果與更高的計算效率。

k-均值聚類；可能性聚類；均值漂移

1996年，Krishnapuram與Keller提出了可能性模糊c-均值聚類（PCM）算法［1］，PCM放松了模糊c-均值聚類（FCM）算法［2］的概率型約束條件，能夠解決FCM算法受噪聲影響的問題。但PCM算法模型本身固有的模式也引發(fā)了新的問題，即算法對初始化參數(shù)敏感，且容易產生重合的聚類［3］。為此，有多種改進的可能性聚類算法被提出［4-7］。Yang與Wu同時考慮到FCM的目標函數(shù)和兩個聚類有效性指標［4］，使其提出的算法適用于無監(jiān)督聚類。Pal等人綜合考察模糊聚類和可能性聚類算法，先后提出兩種混合聚類模型［8］。為了解決PCM對MPCM算法的時間復雜度主要取決于均值漂移聚類的初始點個數(shù)和迭代次數(shù)，算法的初始初始化敏感及發(fā)現(xiàn)數(shù)據(jù)集的不同尺度聚類結構問題，Hu等于2010年提出MPCM算法［9］。點是通過網(wǎng)格剖分方法獲得的，這種方法首先對數(shù)據(jù)空間的進行網(wǎng)格剖分，再在每個剖分的網(wǎng)格內選擇一些（個）特征點作為MSC的初始迭代點。這種方法雖然可以將MSC的計算量降低到O(nl)（n是數(shù)據(jù)的個數(shù)，l是網(wǎng)格剖分后特征點的個數(shù)），但在實驗中發(fā)現(xiàn)，由于在每個網(wǎng)格中都必須選擇一些（個）特征點作為MSC的初始迭代點，而其中的很多特征點與聚類中心的相距較遠，需要通過均值漂移聚類一步步迭代才能收斂到聚類中心。這樣，均值漂移聚類的初始點個數(shù)遠高于實際的聚類中心數(shù)目，而這些初始點收斂到真實聚類中心進行迭代的次數(shù)也是非常高的。為了解決MPCM算法的計算復雜度問題，本文采用k-均值聚類算法代替網(wǎng)格剖分技術進行初始點的選取。k-均值聚類算法是目前應用最為廣泛的硬聚類算法，具有計算簡單，適合處理大數(shù)據(jù)集等優(yōu)點［10］。

本文采用k-均值聚類算法獲取均值漂移聚類的初始點，提出一種改進的多尺度可能性聚類算法。算法在保留MPCM算法優(yōu)點的同時，有效解決了MPCM時間復雜度過高的問題。

1 聚類算法

給定數(shù)據(jù)集合X={x1,x2,…,xn}?RS，n為樣本個數(shù)，將樣本集X劃分為c(2≤c≤n)類。設數(shù)據(jù)集合X的c-劃分表示為矩陣U=[uij]，對應X的可能性c-劃分、模糊c-劃分和硬c-劃分空間分別為:

對于硬劃分或模糊劃分矩陣U，uij表示xj關于X的第i個聚類的隸屬度，二者的區(qū)別是硬劃分的隸屬度只取0與1兩個值，模糊劃分取值在[0,1]區(qū)間上。而對于可能性劃分矩陣U，uij表示xj屬于第i類的可能性。

1.1 k-均值聚類

k-均值聚類算法是一種基于劃分的聚類算法，其計算簡單、實現(xiàn)效率高的特點使其適合處理大數(shù)據(jù)集，是目前應用最為廣泛的聚類算法之一。k-均值聚類算法通過最小化誤差平方和函數(shù)獲得聚類劃分，具體步驟為:

步驟1:隨機初始化聚類中心:

步驟2:將每個樣本xj分配到與之距離最近的聚類中心；

步驟3:重新計算各類的聚類中心:

步驟5:如果J值收斂，則return(v1,v2,…,vc)，算法終止；否則，轉步驟2。

1.2 可能性聚類算法

可能性聚類算法應用可能性理論研究聚類問題，放松了模糊聚類算法中對隸屬度的概率型約束。PCM聚類模型可以通過最小化目標函數(shù)Jpcm得到:

將式（2）、（3）迭代直至收斂直至得到滿足目標函數(shù)Jpcm的最優(yōu)解。其中m為模糊系數(shù)，U=[uij]c×n表示可能性劃分矩陣，uij表示第 j個樣本點屬于第i類的可能性。

2 改進的可能性聚類算法

均值漂移算法（MS）最初是用核方法對非參密度函數(shù)梯度估計得到的，其良好的特性在圖像分割、目標跟蹤、數(shù)據(jù)融合［11-13］等計算機視覺領域得到了廣泛地應用。給定s維特征空間中的數(shù)據(jù)集合由核函數(shù)K(·)與帶寬參數(shù)h確定的概率密度估計函數(shù)為:

其中k(·)為核函數(shù)K(·)的輪廓函數(shù)，滿足K(x)=αk(‖x‖2)，α為歸一化常數(shù)。對 fK(x)求梯度并令其為0，得到均值漂移向量:

其中m(x)是沿著 fK(x)最大速度上升方向，因而達到概率密度函數(shù)局部極值的均值漂移迭代序列x(k-1)=x(k)+m(x(k))，是沿著函數(shù)值增加方向的。

為了降低均值漂移聚類的計算復雜度，采用k-均值聚類算法進行初始化。改進的多尺度可能性聚類算法（IMPCM）的具體步驟如下:

采用k-均值聚類算法對數(shù)據(jù)集合進行聚類劃分，將得到的聚類中心(v1,v2,…,vc)作為均值漂移聚類的初始點；

表1 MPCM與IMPCM各部分對比

表2 data_A上不同算法的正確率（聚類個數(shù)c=12）

設定均值漂移聚類的核函數(shù)K(·)，hz，運行次數(shù)z=0；

更新z=z+1；

分別以vk，k=1,2,…,c作為初始迭代點，迭代式（4）、（5）直至收斂，記為

IMPCM算法采用均值漂移聚類對PCM進行初始化，保留了MPCM算法對初始化魯棒及能夠發(fā)現(xiàn)數(shù)據(jù)集的不同尺度聚類結構的優(yōu)點。同時，采用k-均值聚類算法對均值漂移聚類進行初始化，將均值漂移聚類的初始點個數(shù)從O(nl)降為c（k-均值聚類的聚類中心數(shù)目）個，有效降低了均值漂移聚類的初始點個數(shù)和迭代次數(shù)，改善了算法的計算復雜度。

3 實驗分析

為了測試提出算法的性能，我們在具有多尺度聚類結構的數(shù)據(jù)集data_A上對IMPCM與MPCM及PCM的幾種改進算法進行對比實驗。

3.1 與MPCM對比實驗

如圖1所示，data_A數(shù)據(jù)集合是一個具有12個聚類的二維數(shù)據(jù)集合，其中每類包含25個數(shù)據(jù)點。圖1（a）與圖1（b）中的紅色加號分布為IMPCM與MPCM兩種算法獲得的均值漂移聚類的初始化結果。從圖中可以看出，利用k均值初始化的點都位于每個聚類的中心或中心附近，這些點不僅數(shù)目上比MPCM的要少，而且由于距離真實中心較近，后期的迭代次數(shù)也會遠遠小于MPCM，從而節(jié)省計算量。而在MPCM算法中，采用網(wǎng)格剖分方法確定的特征點作為均值漂移的初始點，這些特征點均勻分布在數(shù)據(jù)所在的空間中，即使在不存在數(shù)據(jù)點的空間內，也會按照均勻分布的原則產生出這部分空間的特征點，比如中間沒有數(shù)據(jù)的部分，從而在之后的均值漂移聚類中產生無效的冗余計算量。

圖1 不同方法的初始化結果

表1為MPCM與IMPCM算法各部分運行時間的對比。從表中可以看出，在算法的各個步驟中，包括均值漂移聚類初始化，均值漂移聚類的時間及迭代次數(shù)，PCM算法的運行時間，IMPCM的時間都有明顯的降低。因而，從總的運行時間來看，IMPCM僅為MPCM算法的三分之一。從實驗的對比結果可以看出，k-均值算法解決了網(wǎng)格剖分所帶來多余初始點問題，有效地降低了計算復雜度。

3.2 與PCM的幾種改進算法的對比實驗

本實驗中，選取PCM及其幾種改進算法（包括IPCM、PFCM、MPCM）、均值漂移聚類（MSC）與提出的IMPCM算法進行對比實驗。表2給出了聚類的準確率和算法的運行時間兩方面結果。首先，從聚類準確度來看，MPCM、MSC及IMPCM都能夠正確地揭示出數(shù)據(jù)集當聚類個數(shù)c=12時的聚類結構。而其它幾種可能性聚類算法都產生一些誤差，其最高正確率也不足90%，最差的IPCM-u（f）僅為32.07%。其次，從算法的運行時間上看，MPCM與MSC的運行時間較長，都超過了1秒，其他幾種聚類算法都低于1秒。運行時間最短的為PFCM算法，僅為0.0833秒，但這種算法的聚類準確率較低，僅為88.07%。而剩余的四種算法的運算時間相近，在0.3～0.4秒之間，但只有IMPCM算法的聚類準確度最高。因此，綜合聚類準確度和運算時間兩個方面，本文提出的IMPCM算法的性能最優(yōu)。

4 結論

本文針對MPCM中網(wǎng)格剖分選取的初始點帶來的計算復雜度問題，采用k-均值聚類進行初始化，有效地降低MPCM算法的計算復雜度。實驗表明，與MPCM以及均值漂移聚類相比，IMPCM算法在不降低聚類效果的前提下具有更高的計算效率。與PCM及其改進算法相比，在時間復雜度略有增加的前提下具有更好的聚類效果。在今后的研究中，如何更大幅度的降低算法的時間復雜度使之更適用于大數(shù)據(jù)集聚類，是我們需要進一步深入研究的課題。

［1］ Krishnapuram R，KellerJM.A possibilisticapproach to clustering［J］.IEEE Transactions on Fuzzy Systems，1993，1（2）:98-110.

［2］ Bezdek JC.Pattern recognition with fuzzy objective function algorithms［M］.New York:Plenum Press，1981.

［3］ Barni M，Cappellini V，Mecocci A.Comments on“A possibilisticapproachtoclustering”［J］.IEEE Transactions on Fuzzy Systems，1996，4（3）:393-396.

［4］ Yang MS，Wu KL.Unsupervised possibilistic clustering［J］.Pattern Recognition，2006，39（1）:5-21.

［5］ Hu Y，Qu F，Yang Y，et al.An Improved Possibilistic Clustering Based on Differential Algorithm［C］//2010 2nd International Workshop on Intelligent Systems and Applications，2010:1-4.

［6］ 胡雅婷，左春檉，曲福恒，等.基于改進可能性聚類算法的軸承故障診斷［J］.長春理工大學學報:自然科學版，2011，34（3）:58-61.

［7］ 胡雅婷.可能性聚類方法研究及應用［D］.長春:吉林大學，2012.

［8］ Pal NR，Pal K，Keller JM，et al.A possibilistic fuzzy c-means clustering algorithm［J］.IEEE Transactions on Fuzzy Systems，2005，13（4）:517-530.

［9］ 胡雅婷，左春檉，曲福恒，等.多尺度可能性聚類算法［J］.長春理工大學學報:自然科學版，2010，33（4）: 124-127.

［10］ Forgy E W.Cluster analysis of multivariate data: efficiency versus interpretability of classifications［J］.Biometrics，1965，21:768-769.

［11］ Comaniciu D，Ramesh V，Meer P.Kernel-based object tracking［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25（5）: 564-575.

［12］ Debeir O，Van Ham P，Kiss R，et al.Tracking of migrating cells under phase-contrast video microscopy with combined mean-shift processes［J］. Medical Imaging，IEEE Transactions on，2005，24（6）:697-711.

［13］ Chen H，Meer P.Robust fusion of uncertain information［J］.Systems，Man，and Cybernetics，Part B: Cybernetics，IEEE Transactions on，2005，35（3）: 578-586.

An Improved Multi-scale Possibilistic Clustering Algorithm

HU Yating1，QU Fuheng2
（1.School of Information and Technology，Jilin Agriculture University，Changchun 130118；2.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022）

To overcome the problems of having a high computation of multi-scale possibilistic clustering algorithm（MPCM），an improved algorithm is proposed in this paper.IMPCM uses the convergent points of k-means to initialize MPCM.IMPCM inherits the merits of the MPCM.In the meanwhile，IMPCM solves the problem of MPCM that the initialization points are superfluous and the position is not ideal which make MPCM has too many iteration times. The contrast experiments show that IMPCM has a good clustering results and high computational efficiency.

K-means clustering；possibilistic clustering；mean shift

TP391.4

A

1672-9870（2016）05-0115-04

2016-06-15

吉林省教育廳“十二五”科學技術研究項目（2015201），吉林省教育廳“十三五”科研規(guī)劃重點課題（2016186），吉林省教育科學規(guī)劃課題（GH150221）

胡雅婷（1979-），女，博士，講師，E-mail:huyating79@163.com

曲福恒（1979-），男，博士，副教授，E-mail:qufuheng@163.com