胡雅婷,曲福恒
(1.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院,長(zhǎng)春 130118;2.長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 長(zhǎng)春 130022)
一種改進(jìn)的多尺度可能性聚類算法
胡雅婷1,曲福恒2
(1.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院,長(zhǎng)春 130118;2.長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 長(zhǎng)春 130022)
針對(duì)多尺度可能性聚類算法(MPCM)計(jì)算復(fù)雜度較高的問題,提出一種改進(jìn)的多尺度可能性聚類算法(IMPCM)。算法利用k-均值聚類的收斂點(diǎn)來作為MPCM的初始點(diǎn),在繼承了MPCM優(yōu)點(diǎn)的同時(shí),解決了原始MPCM中無效初始點(diǎn)過多以及初始點(diǎn)位置不理想造成的迭代次數(shù)過高的問題。對(duì)比實(shí)驗(yàn)結(jié)果表明,算法具有良好的聚類效果與更高的計(jì)算效率。
k-均值聚類;可能性聚類;均值漂移
1996年,Krishnapuram與Keller提出了可能性模糊c-均值聚類(PCM)算法[1],PCM放松了模糊c-均值聚類(FCM)算法[2]的概率型約束條件,能夠解決FCM算法受噪聲影響的問題。但PCM算法模型本身固有的模式也引發(fā)了新的問題,即算法對(duì)初始化參數(shù)敏感,且容易產(chǎn)生重合的聚類[3]。為此,有多種改進(jìn)的可能性聚類算法被提出[4-7]。Yang與Wu同時(shí)考慮到FCM的目標(biāo)函數(shù)和兩個(gè)聚類有效性指標(biāo)[4],使其提出的算法適用于無監(jiān)督聚類。Pal等人綜合考察模糊聚類和可能性聚類算法,先后提出兩種混合聚類模型[8]。為了解決PCM對(duì)MPCM算法的時(shí)間復(fù)雜度主要取決于均值漂移聚類的初始點(diǎn)個(gè)數(shù)和迭代次數(shù),算法的初始初始化敏感及發(fā)現(xiàn)數(shù)據(jù)集的不同尺度聚類結(jié)構(gòu)問題,Hu等于2010年提出MPCM算法[9]。點(diǎn)是通過網(wǎng)格剖分方法獲得的,這種方法首先對(duì)數(shù)據(jù)空間的進(jìn)行網(wǎng)格剖分,再在每個(gè)剖分的網(wǎng)格內(nèi)選擇一些(個(gè))特征點(diǎn)作為MSC的初始迭代點(diǎn)。這種方法雖然可以將MSC的計(jì)算量降低到O(nl)(n是數(shù)據(jù)的個(gè)數(shù),l是網(wǎng)格剖分后特征點(diǎn)的個(gè)數(shù)),但在實(shí)驗(yàn)中發(fā)現(xiàn),由于在每個(gè)網(wǎng)格中都必須選擇一些(個(gè))特征點(diǎn)作為MSC的初始迭代點(diǎn),而其中的很多特征點(diǎn)與聚類中心的相距較遠(yuǎn),需要通過均值漂移聚類一步步迭代才能收斂到聚類中心。這樣,均值漂移聚類的初始點(diǎn)個(gè)數(shù)遠(yuǎn)高于實(shí)際的聚類中心數(shù)目,而這些初始點(diǎn)收斂到真實(shí)聚類中心進(jìn)行迭代的次數(shù)也是非常高的。為了解決MPCM算法的計(jì)算復(fù)雜度問題,本文采用k-均值聚類算法代替網(wǎng)格剖分技術(shù)進(jìn)行初始點(diǎn)的選取。k-均值聚類算法是目前應(yīng)用最為廣泛的硬聚類算法,具有計(jì)算簡(jiǎn)單,適合處理大數(shù)據(jù)集等優(yōu)點(diǎn)[10]。
本文采用k-均值聚類算法獲取均值漂移聚類的初始點(diǎn),提出一種改進(jìn)的多尺度可能性聚類算法。算法在保留MPCM算法優(yōu)點(diǎn)的同時(shí),有效解決了MPCM時(shí)間復(fù)雜度過高的問題。
給定數(shù)據(jù)集合X={x1,x2,…,xn}?RS,n為樣本個(gè)數(shù),將樣本集X劃分為c(2≤c≤n)類。設(shè)數(shù)據(jù)集合X的c-劃分表示為矩陣U=[uij],對(duì)應(yīng)X的可能性c-劃分、模糊c-劃分和硬c-劃分空間分別為:
對(duì)于硬劃分或模糊劃分矩陣U,uij表示xj關(guān)于X的第i個(gè)聚類的隸屬度,二者的區(qū)別是硬劃分的隸屬度只取0與1兩個(gè)值,模糊劃分取值在[0,1]區(qū)間上。而對(duì)于可能性劃分矩陣U,uij表示xj屬于第i類的可能性。
1.1 k-均值聚類
k-均值聚類算法是一種基于劃分的聚類算法,其計(jì)算簡(jiǎn)單、實(shí)現(xiàn)效率高的特點(diǎn)使其適合處理大數(shù)據(jù)集,是目前應(yīng)用最為廣泛的聚類算法之一。k-均值聚類算法通過最小化誤差平方和函數(shù)獲得聚類劃分,具體步驟為:
步驟1:隨機(jī)初始化聚類中心:
步驟2:將每個(gè)樣本xj分配到與之距離最近的聚類中心;
步驟3:重新計(jì)算各類的聚類中心:
步驟5:如果J值收斂,則return(v1,v2,…,vc),算法終止;否則,轉(zhuǎn)步驟2。
1.2 可能性聚類算法
可能性聚類算法應(yīng)用可能性理論研究聚類問題,放松了模糊聚類算法中對(duì)隸屬度的概率型約束。PCM聚類模型可以通過最小化目標(biāo)函數(shù)Jpcm得到:
將式(2)、(3)迭代直至收斂直至得到滿足目標(biāo)函數(shù)Jpcm的最優(yōu)解。其中m為模糊系數(shù),U=[uij]c×n表示可能性劃分矩陣,uij表示第 j個(gè)樣本點(diǎn)屬于第i類的可能性。
均值漂移算法(MS)最初是用核方法對(duì)非參密度函數(shù)梯度估計(jì)得到的,其良好的特性在圖像分割、目標(biāo)跟蹤、數(shù)據(jù)融合[11-13]等計(jì)算機(jī)視覺領(lǐng)域得到了廣泛地應(yīng)用。給定s維特征空間中的數(shù)據(jù)集合由核函數(shù)K(·)與帶寬參數(shù)h確定的概率密度估計(jì)函數(shù)為:
其中k(·)為核函數(shù)K(·)的輪廓函數(shù),滿足K(x)=αk(‖x‖2),α為歸一化常數(shù)。對(duì) fK(x)求梯度并令其為0,得到均值漂移向量:
其中m(x)是沿著 fK(x)最大速度上升方向,因而達(dá)到概率密度函數(shù)局部極值的均值漂移迭代序列x(k-1)=x(k)+m(x(k)),是沿著函數(shù)值增加方向的。
為了降低均值漂移聚類的計(jì)算復(fù)雜度,采用k-均值聚類算法進(jìn)行初始化。改進(jìn)的多尺度可能性聚類算法(IMPCM)的具體步驟如下:
采用k-均值聚類算法對(duì)數(shù)據(jù)集合進(jìn)行聚類劃分,將得到的聚類中心(v1,v2,…,vc)作為均值漂移聚類的初始點(diǎn);
表1 MPCM與IMPCM各部分對(duì)比
表2 data_A上不同算法的正確率(聚類個(gè)數(shù)c=12)
設(shè)定均值漂移聚類的核函數(shù)K(·),hz,運(yùn)行次數(shù)z=0;
更新z=z+1;
分別以vk,k=1,2,…,c作為初始迭代點(diǎn),迭代式(4)、(5)直至收斂,記為
IMPCM算法采用均值漂移聚類對(duì)PCM進(jìn)行初始化,保留了MPCM算法對(duì)初始化魯棒及能夠發(fā)現(xiàn)數(shù)據(jù)集的不同尺度聚類結(jié)構(gòu)的優(yōu)點(diǎn)。同時(shí),采用k-均值聚類算法對(duì)均值漂移聚類進(jìn)行初始化,將均值漂移聚類的初始點(diǎn)個(gè)數(shù)從O(nl)降為c(k-均值聚類的聚類中心數(shù)目)個(gè),有效降低了均值漂移聚類的初始點(diǎn)個(gè)數(shù)和迭代次數(shù),改善了算法的計(jì)算復(fù)雜度。
為了測(cè)試提出算法的性能,我們?cè)诰哂卸喑叨染垲惤Y(jié)構(gòu)的數(shù)據(jù)集data_A上對(duì)IMPCM與MPCM及PCM的幾種改進(jìn)算法進(jìn)行對(duì)比實(shí)驗(yàn)。
3.1 與MPCM對(duì)比實(shí)驗(yàn)
如圖1所示,data_A數(shù)據(jù)集合是一個(gè)具有12個(gè)聚類的二維數(shù)據(jù)集合,其中每類包含25個(gè)數(shù)據(jù)點(diǎn)。圖1(a)與圖1(b)中的紅色加號(hào)分布為IMPCM與MPCM兩種算法獲得的均值漂移聚類的初始化結(jié)果。從圖中可以看出,利用k均值初始化的點(diǎn)都位于每個(gè)聚類的中心或中心附近,這些點(diǎn)不僅數(shù)目上比MPCM的要少,而且由于距離真實(shí)中心較近,后期的迭代次數(shù)也會(huì)遠(yuǎn)遠(yuǎn)小于MPCM,從而節(jié)省計(jì)算量。而在MPCM算法中,采用網(wǎng)格剖分方法確定的特征點(diǎn)作為均值漂移的初始點(diǎn),這些特征點(diǎn)均勻分布在數(shù)據(jù)所在的空間中,即使在不存在數(shù)據(jù)點(diǎn)的空間內(nèi),也會(huì)按照均勻分布的原則產(chǎn)生出這部分空間的特征點(diǎn),比如中間沒有數(shù)據(jù)的部分,從而在之后的均值漂移聚類中產(chǎn)生無效的冗余計(jì)算量。
圖1 不同方法的初始化結(jié)果
表1為MPCM與IMPCM算法各部分運(yùn)行時(shí)間的對(duì)比。從表中可以看出,在算法的各個(gè)步驟中,包括均值漂移聚類初始化,均值漂移聚類的時(shí)間及迭代次數(shù),PCM算法的運(yùn)行時(shí)間,IMPCM的時(shí)間都有明顯的降低。因而,從總的運(yùn)行時(shí)間來看,IMPCM僅為MPCM算法的三分之一。從實(shí)驗(yàn)的對(duì)比結(jié)果可以看出,k-均值算法解決了網(wǎng)格剖分所帶來多余初始點(diǎn)問題,有效地降低了計(jì)算復(fù)雜度。
3.2 與PCM的幾種改進(jìn)算法的對(duì)比實(shí)驗(yàn)
本實(shí)驗(yàn)中,選取PCM及其幾種改進(jìn)算法(包括IPCM、PFCM、MPCM)、均值漂移聚類(MSC)與提出的IMPCM算法進(jìn)行對(duì)比實(shí)驗(yàn)。表2給出了聚類的準(zhǔn)確率和算法的運(yùn)行時(shí)間兩方面結(jié)果。首先,從聚類準(zhǔn)確度來看,MPCM、MSC及IMPCM都能夠正確地揭示出數(shù)據(jù)集當(dāng)聚類個(gè)數(shù)c=12時(shí)的聚類結(jié)構(gòu)。而其它幾種可能性聚類算法都產(chǎn)生一些誤差,其最高正確率也不足90%,最差的IPCM-u(f)僅為32.07%。其次,從算法的運(yùn)行時(shí)間上看,MPCM與MSC的運(yùn)行時(shí)間較長(zhǎng),都超過了1秒,其他幾種聚類算法都低于1秒。運(yùn)行時(shí)間最短的為PFCM算法,僅為0.0833秒,但這種算法的聚類準(zhǔn)確率較低,僅為88.07%。而剩余的四種算法的運(yùn)算時(shí)間相近,在0.3~0.4秒之間,但只有IMPCM算法的聚類準(zhǔn)確度最高。因此,綜合聚類準(zhǔn)確度和運(yùn)算時(shí)間兩個(gè)方面,本文提出的IMPCM算法的性能最優(yōu)。
本文針對(duì)MPCM中網(wǎng)格剖分選取的初始點(diǎn)帶來的計(jì)算復(fù)雜度問題,采用k-均值聚類進(jìn)行初始化,有效地降低MPCM算法的計(jì)算復(fù)雜度。實(shí)驗(yàn)表明,與MPCM以及均值漂移聚類相比,IMPCM算法在不降低聚類效果的前提下具有更高的計(jì)算效率。與PCM及其改進(jìn)算法相比,在時(shí)間復(fù)雜度略有增加的前提下具有更好的聚類效果。在今后的研究中,如何更大幅度的降低算法的時(shí)間復(fù)雜度使之更適用于大數(shù)據(jù)集聚類,是我們需要進(jìn)一步深入研究的課題。
[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ìn)可能性聚類算法的軸承故障診斷[J].長(zhǎng)春理工大學(xué)學(xué)報(bào):自然科學(xué)版,2011,34(3):58-61.
[7] 胡雅婷.可能性聚類方法研究及應(yīng)用[D].長(zhǎng)春:吉林大學(xué),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].長(zhǎng)春理工大學(xué)學(xué)報(bào):自然科學(xué)版,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
吉林省教育廳“十二五”科學(xué)技術(shù)研究項(xiàng)目(2015201),吉林省教育廳“十三五”科研規(guī)劃重點(diǎn)課題(2016186),吉林省教育科學(xué)規(guī)劃課題(GH150221)
胡雅婷(1979-),女,博士,講師,E-mail:huyating79@163.com
曲福恒(1979-),男,博士,副教授,E-mail:qufuheng@163.com