段林珊,劉培玉,謝方方
(1.山東師范大學 信息科學與工程學院,山東 濟南250014;2.山東省分布式計算機軟件新技術(shù)重點實驗室,山東 濟南250014)
聚類是人類最基本的認識活動之一,也是圖像處理、模式識別、數(shù)據(jù)挖掘等眾多研究領(lǐng)域的一項重要研究內(nèi)容。所謂聚類,就是按照事物所具有的某些特征和屬性,把具有相似特征和屬性的事物聚集成同一類,屬性特征差別大的另分一類,最終聚類結(jié)果使得各個類之間的屬性和特性等相似度盡可能小,而聚類結(jié)果中已經(jīng)聚好的類與類之間相似度盡可能大。聚類分析應(yīng)用領(lǐng)域很廣泛,近年來隨著其不斷發(fā)展,已經(jīng)被卓有成效地應(yīng)用在數(shù)據(jù)挖掘及分析、圖像處理、模式識別等領(lǐng)域的聚類分析當中[1]。
傳統(tǒng)的聚類分析,在進行聚類分類之時,會有一個明確的分類界限沒有模糊性信息在其中,并且是按照事先設(shè)定好的原則和要求來將事物進行分類的,但在實際應(yīng)用中,有大量的聚類問題在進行聚類分析的時候并沒有完全明確的分類界限,即所謂的模棱兩可,比如對移動客服回訪滿意程度進行評價,有非常滿意、比較滿意、滿意、不滿意等類別,諸如此類的事物,它們的特征和屬性在進行分類時存在著一定的中介性和模糊不確定性,即事物之間沒有明確的分類界限。
鑒于此類問題,模糊性理論由美國計算機與控制專家扎德教授提出來了,之后對于其研究迅速展開,并被應(yīng)用于聚類問題,形成了模糊聚類分析方法。模糊聚類分析,就是用模糊理論對海量以及重要數(shù)據(jù)進行分析,建立樣本屬性類別的不確定性描述,已經(jīng)被廣泛并且有效地應(yīng)用于海量數(shù)據(jù)挖掘、數(shù)據(jù)建模、模式識別、圖像處理等重要領(lǐng)域 具有重要的理論與實際應(yīng)用價值,完全可以比較客觀地反映現(xiàn)實世界。隨著各種應(yīng)用的不斷發(fā)展,由于模糊聚類算法具有廣泛的適用性,因此對其研究與日俱增并取得了一定的理論成果和實踐成效,其中,模糊C均值聚類[2,3]算法是目前的聚類算法當中應(yīng)用領(lǐng)域最為廣泛的,它是一種無導師即無監(jiān)督學習的一種聚類算法,也是一種基于目標函數(shù)的聚類分析法[4]。已廣泛應(yīng)用于生命科學、醫(yī)學、農(nóng)業(yè)、目標識別、地理等領(lǐng)域。該算法針對聚類中心設(shè)定隸屬度函數(shù)、目標函數(shù)和相關(guān)閾值,通過計算樣本點對于各個聚類中心的隸屬度函數(shù)自動對樣本進行分類。
模糊C均值聚類 (FCM)算法具有應(yīng)用范圍廣泛、使用方便、設(shè)計簡單等優(yōu)點,可以用于解決尋求全局最優(yōu)解問題,但是它也存在不足之處:該算法無法自動確定初始聚類數(shù),需要根據(jù)先驗知識進行人為確定輸入,并且在進行確定之時還沒有明確的準則可以遵循,具有盲目性,這樣,初始聚類數(shù)過大或過小都會影響算法產(chǎn)生聚類的效果;此外,傳統(tǒng)的FCM算法忽略了不同樣本分類貢獻的不均衡性,把樣本屬性貢獻視為等同的,因而可能會影響分類結(jié)果準確度。FCM的這些不足之處會使算法陷入局部最優(yōu),降低算法收斂速度。
針對上文提到的FCM的不足之處,國內(nèi)外研究學者已經(jīng)對其進行了相關(guān)的改進和研究,很多學者將進化理論中的思想運用到FCM中,以期得到全局最優(yōu)。文獻 [5]運用人工免疫細胞模型來生成聚類初始值,文獻 [6]將遺傳算法結(jié)合到FCM算法中解決局部最優(yōu)問題,文獻 [7]運用粒子群優(yōu)化算法解決此弊端。
本文利用模擬退火算法具有與初始值和初始狀態(tài)無關(guān)以及全局最優(yōu)的特點,運用模擬退火算法來確定FCM初始聚類數(shù),并根據(jù)樣本屬性對分類貢獻差異設(shè)定加權(quán)值,提出一種基于模擬退火算法的樣本加權(quán)FCM算法 (SASWFCM),并經(jīng)過實驗驗證了該算法的有效性和優(yōu)越性。
模糊C均值聚類算法是根據(jù)隸屬度大小來確定一個事物是否屬于一個類別,與傳統(tǒng)的沒有明確分類界限的硬劃分方法大不相同,它采用模糊隸屬度來劃分,具有比較可觀的聚類效果。它是針對聚類中心設(shè)定隸屬度函數(shù)、目標函數(shù)和相關(guān)閾值,通過計算樣本點對于各個聚類中心的隸屬度函數(shù)自動對樣本進行分類。
文獻 [8]中對模糊C均值聚類算法有一個詳細的描述,算法具體過程如下:假設(shè)一個樣本空間為X={x1,x2,……xn},將此樣本空間X分成m類,m需是大于1的一個正整數(shù) ,隸屬度函數(shù)用一個模糊矩陣來表示,矩陣中u=(uij),uij為第i個樣本屬于第j類的隸屬度大小。為此定義
其中,第j個聚類的中心點用cj來表示,xi-cj稱為樣本xi到某一個聚類中心cj的歐式距離。從式 (1)可以分析出,如果樣本點xi到第j個聚類中心的距離越近,則相對應(yīng)的那個隸屬度就越小,即uij越小。其中=1,i=1,2,3……n,j=1,2,……m 。FCM 的目標函數(shù)F(U,c)定義為
其中b稱為一個模糊度指數(shù),隨著它的數(shù)值的增大,整個聚類的模糊性就越大。從式 (2)可以看出,xi-cj如果越小,則uij就會越小,則目標函數(shù)值F就會越小。FCM聚類算法執(zhí)行過程中,需要對聚類中心值進行多次嘗試性修改,每一次修改后進行計算對應(yīng)的目標函數(shù)值F(U,c),直至最終達到滿意的聚類效果。因此,F(xiàn)CM算法可以稱之為是一個不斷優(yōu)化迭代目標函數(shù)F(U,c),尋找最佳目標函數(shù)值的一個過程。在算法中需要不斷修改聚類中心值,所以定義聚類中心點函數(shù)如下
根據(jù)以上描述內(nèi)容,確定模糊C均值聚類算法的迭代過程如下:
步驟1 事先設(shè)定模糊度數(shù)b和一個聚類類數(shù)的初始值。
步驟2 隨機性地產(chǎn)生m個聚類中心,其中0代表此時算法的迭代次數(shù)是0。
步驟3 根據(jù)式 (1)和每一次迭代產(chǎn)生的聚類中心函數(shù)來計算目標函數(shù),再根據(jù)每一次迭代產(chǎn)生的隸屬度函數(shù)uij,進一步更新聚類中心函數(shù)cj的值,反復(fù)進行步驟3算法過程,直至目標函數(shù)達到最終理想的目標函數(shù)最小值,或者等目標函數(shù)值達到低于預(yù)先給定的較小的一個閾值ε時再停止算法執(zhí)行。
從上述算法描述可以看出,傳統(tǒng)的模糊C均值聚類算法,設(shè)定初始簇的數(shù)目也就是聚類個數(shù)和確定模糊指數(shù)之時,并沒有一個合理明確的準則可以遵循,而是需要人為或者專家根據(jù)先驗知識來輸入初始值,然后算法繼續(xù)執(zhí)行。這樣處理,不可避免地會造成各種誤差,會使算法收斂度和準確度受到影響,甚至使算法陷入局部最優(yōu)。
同時,上述算法描述中目標函數(shù)和聚類中心函數(shù)在處理各種樣本各維屬性特征或者數(shù)據(jù)屬性時并無區(qū)別,即將樣本各屬性特征或者數(shù)據(jù)屬性對最終聚類結(jié)果的貢獻程度視為等同的,這樣處理,可能會夸大某些孤立點或者噪聲數(shù)據(jù)對分類的作用,也會縮小對某些重要屬性的貢獻,也會導致聚類準確度有所下降。
模擬退火算法[9-11]是一種很好的求解大規(guī)模組合優(yōu)化問題的算法,基于求解全局最優(yōu)問題與物理固體退火具有相似性,該算法參數(shù)設(shè)計上采用的是物理領(lǐng)域的參數(shù),假設(shè)溫度T時粒子趨于平衡的概率是e-ΔE/(kT),其中,k是波爾茲曼常數(shù),內(nèi)能改變量用ΔE來表示,E代表溫度T時刻的內(nèi)能,該算法基于Metropolis準則,可以進行控制溫度由高到低的過程,
模擬退火算法原型進行演變應(yīng)用在實際問題當中時,把內(nèi)能變量E模擬為求解問題當中的目標函數(shù)值f,在實際問題當中找到一個變量來對應(yīng)原型當中的控制參數(shù),即溫度T,按照上述方法和過程,就可以運用模擬退火算法來解決各種大小規(guī)模的組合優(yōu)化問題:在算法開始迭代時,事先確定一個初始解、確定一個控制參數(shù)的初始值記為T,然后對每一次迭代過程的當前狀態(tài)解進行隨機擾動,以產(chǎn)生一個新的解,然后計算這兩次迭代最終的目標函數(shù)差值,根據(jù)此差值與預(yù)先設(shè)定的很小的閾值比較情況,再判斷是否接受該新解,這樣逐次進行迭代計算分析,并逐步衰減控制參數(shù)T的值,直到滿足算法終止條件,再輸出當前狀態(tài)解為問題所尋求的最優(yōu)解。
模擬退火算法是基于金屬退火的機理而建立起來的一種隨機算法,它能夠通過控制溫度的變化過程來實現(xiàn)大范圍的粗略搜索與局部的精細搜索[12]。它是近年來發(fā)展起來的一種新的隨機搜索方法,與傳統(tǒng)隨機搜索策略相比而言,它具有很多優(yōu)勢:第一,它在算法過程中是對每一次迭代當前狀態(tài)解進行隨機擾動來產(chǎn)生新解,并以一定的概率接受或者舍棄新解,同時模擬退火算法利用實際物理固體退火過程的自然機理進行隨機搜索。這樣在迭代過程中使得目標函數(shù)值變 “好”,由于模擬退火算法是在整個解的鄰域范圍內(nèi)取值的隨機性,可以避免使算法陷入局部最優(yōu)解而最終獲得全局最優(yōu)解,使得獲得全局最優(yōu)解的可能性增大。第二,模擬退火算法輸入輸出的耦合程度較低。在利用該算法求解優(yōu)化問題時,求得的最優(yōu)解與算法的初始值和迭代次數(shù)無關(guān)。此外,模擬退火算法是一種具有較好的收斂性的全局優(yōu)化算法,已被理論上證明,該算法收斂于全局最優(yōu)解的概率可以達到 “1”[13]。
基于模擬退火算法具有描述簡單、使用靈活、運用廣泛、運行效率高和較少受到初始條件約束等優(yōu)點,是用來解決大規(guī)模組合優(yōu)化問題通用而又行之有效的算法之一,已經(jīng)被廣泛應(yīng)用于大量需要優(yōu)化的場合,比如決策控制、神經(jīng)網(wǎng)絡(luò)、機器學習等算法中的局部最優(yōu)問題都用到了模擬退火算法。模糊C均值聚類算法實際可以看作是一個優(yōu)化問題,也可以采用模擬退火算法對其進行優(yōu)化。模糊C均值聚類算法需要人為根據(jù)先驗知識輸入初始聚類數(shù),這樣會導致結(jié)果陷入局部最優(yōu),使最終聚類效果受影響。鑒于此,本文采用模擬退火算法來求得FCM算法初始的聚類類數(shù),改進算法的局限性,從而使算法跳出局部最優(yōu)解,達到全局最優(yōu)解。用模擬退火算法確定FCM聚類算法初始聚類數(shù)的具體步驟描述如下:
步驟1 假定初始目標函數(shù)值為F,F(xiàn)CM算法在進行聚類初始時對其聚類數(shù)目賦予一個初始解為S,每一個目標函數(shù)值F值的迭代次數(shù)記為P;
步驟2 對于r=1,2……r,P每迭代一次都按照步驟(3)~步驟 (6)順序執(zhí)行一次;
步驟3 對每一次迭代過程中產(chǎn)生的解S進行隨機擾動處理,產(chǎn)生的新的狀態(tài)解記為S′;
步驟4 用當前解S作為FCM算法中的初始聚類數(shù)生成聚類中心;
步驟5 定義目標函數(shù)為
式中:vi、vj——第i類第j類的聚類中心。計算增量Δf′=f(S′)-f(S);
步驟6 若Δf′>0,則將S′作為當前狀態(tài)下的新解,否則 就 以e(-Δf′/F)大 小 的 概 率 接 受 S′ 作 為 當 前 狀 態(tài) 下得新解;
步驟7 如果兩次迭代過程中目標函數(shù)差值小于預(yù)先設(shè)定的閾值,即滿足了最終算法的終止條件,則將當前狀態(tài)下得解輸出作為問題最終的最優(yōu)解,算法結(jié)束。
傳統(tǒng)的FCM算法在進行聚類分析時,把每一個樣本的各種屬性特征對最終聚類結(jié)果的貢獻視為等同的或者均勻的,而這在實際應(yīng)用中是有很大的局限性的。因為實際生活中樣本各維屬性特征對聚類貢獻不可能等同。
傳統(tǒng)FCM聚類算法這樣處理,必然會導致有些重要的樣本屬性特征結(jié)構(gòu)就很難被發(fā)現(xiàn),另外樣本中的噪聲點以及孤立點對分類的貢獻就被夸大化了。
為解決此問題,本文擬對FCM聚類算法中目標函數(shù)和聚類中心函數(shù)根據(jù)樣本屬 性特征對分類貢獻程度進行合理加權(quán)處理,盡可能使得算法在分類準確數(shù)和準確度上有更大的提高。
受熱力學中熵定義的啟發(fā),它是表示信息的無序度,熵值越大,信息越有效。在這里定義類似于熵的一個量Ei來衡量uij即第i個樣本屬于第j類的隸屬度的有效度。定義權(quán)重wi來表示第i個樣本點對聚類數(shù)據(jù)評價的影響和貢獻程度
其中定義FCM目標函數(shù)為
聚類中心函數(shù)變?yōu)?/p>
式 (7)和式 (8)是進行加權(quán)處理后的目標函數(shù)和聚類中心函數(shù),將其應(yīng)用于FCM聚類算法中。
模糊C均值聚類算法初始聚類數(shù)需要人為根據(jù)先驗知識確定的問題通過使用模擬退火算法來確定一個最優(yōu)解,改進了算法,避免算法陷入局部最優(yōu)。
對于樣本或者數(shù)據(jù)的屬性特征對分類貢獻存在差異的問題,本文對其進行加權(quán)處理應(yīng)用于模糊C均值聚類算法中。
基于模擬退火的樣本加權(quán)FCM算法 (SASWFCM)的步驟描述如下:
步驟1 利用模擬退火算法按照3.1中所描述的步驟確定FCM算法中初始聚類數(shù),初始化聚類中心、權(quán)重指數(shù)wi和閾值ε,t=0。
步驟2 根據(jù)式 (1)計算第i個樣本在第j個聚類中的隸屬度函數(shù)uij。
步驟3 根據(jù)式 (8)更新聚類中心,記錄t時刻的隸屬度,t=t+1。
步驟4 根據(jù)式 (7)更新目標函數(shù)值F(U,c),如果相對于上次的目標函數(shù)值改變量小于閾值ε,則算法停止,否則轉(zhuǎn)到步驟3。
該算法中閾值ε需要事先確定為很小很小的正整數(shù)。
為驗證本文提出的SASWFCM算法的有效性,實驗采用UCI數(shù)據(jù)集作為測試對象,在Matlab實驗環(huán)境下進行相關(guān)實驗分析,對傳統(tǒng)FCM算法、普通樣本加權(quán)FCM算法以及本文提出的基于模擬退火的樣本加權(quán)模糊-C均值聚類算法在聚類準確數(shù)和聚類準確度上進行了比較。實驗結(jié)果表明本文提出的SASWFCM算法在聚類準確數(shù)和準確率上比傳統(tǒng)FCM算法及普通樣本加權(quán)FCM聚類算法都要高,具有更好的效果。
本文是采用 UCI數(shù)據(jù)集中的Diabetes、Horse colic、Glass數(shù)據(jù)集來進行算法性能的比較。數(shù)據(jù)源信息見表1。
表1 數(shù)據(jù)源信息
表2給出了在UCI的3個數(shù)據(jù)集上,模糊C-均值(fuzzy C-means,F(xiàn)CM)聚類算法[14],普通樣本加權(quán) FCM聚類算法以及SASWFCM算法在聚類準確數(shù)目方面效果對比情況。
表2 FCM、樣本加權(quán)FCM、SASWFCM聚類準確數(shù)比較
從表2實驗結(jié)果可以看出,SASWFCM算法較之FCM以及普通樣本加權(quán)FCM算法,聚類準確數(shù)目更多一些。在Diabetes數(shù)據(jù)集上SASWFCM算法的準確數(shù)531比傳統(tǒng)FCM算法多很多,與普通樣本加權(quán)FCM算法基本等同高出一點點。在Horse colic、Glass上情況也類似。
表3給出了在UCI的3個數(shù)據(jù)集上,模糊C-均值(fuzzy C-means,F(xiàn)CM)聚類算法,普通樣本加權(quán)FCM聚類算法以及SASWFCM算法聚類準確度效果對比情況。
表3 FCM、樣本加權(quán)FCM、SASWFCM聚類準確度比較
從表3實驗數(shù)據(jù)可以看出本文提出的SASWFCM算法在聚類準確度方面較之FCM算法和普通樣本加權(quán)FCM算法都有所提高,具有實際應(yīng)用價值。
本文以模糊C均值聚類算法為研究背景,利用模擬退火算法實現(xiàn)簡單、求最優(yōu)解可靠性高的優(yōu)點,來解決FCM初始聚類數(shù)需要根據(jù)先驗知識人為確定的不足。根據(jù)不同樣本對聚類貢獻不等的情況,對FCM算法中目標函數(shù)和聚類中心函數(shù)進行相應(yīng)合理加權(quán)處理,提出一種基于模擬退火的樣本加權(quán)FCM算法 (SASWFCM)。通過相關(guān)實驗分析表明該算法能夠避免人為確定初始聚類數(shù)帶來的誤差,不會使算法陷入局部最優(yōu),且在樣本正確聚類數(shù)和正確聚類度方面較傳統(tǒng)FCM以及普通樣本加權(quán)FCM算法具有一定的優(yōu)越性,是一種有效地具有實際價值的聚類算法。
:
[1]LIU Qiang,XIA Shixiong,ZHOU Yong,et al.Fuzzy clustering algorithm using two methods [J].Application Research of Computers,2011,28 (12):4437-4438 (in Chinese).[劉強,夏士熊,周勇,等.基于兩種加權(quán)方式的模糊聚類算法[J].計算機應(yīng)用研究,2011,28 (12):4437-4438.]
[2]GUAN Qing,DENG Zhaohong,WANG Shitong.Improved fuzzy C-means clustering algorithm [J].Computer Engineering and Applications,2011,47 (10):27-29 (in Chinese). [關(guān)慶,鄧趙紅,王士同.改進的模糊C均值聚類算法 [J].計算機工程與應(yīng)用,2011,47 (10):27-29.]
[3]ZENG Shan,TONG Xiaojun,SANG Nong,et al.Study of multi-prototype fuzzy C-means clustering algorithm using correspondence analysis [J].Huazhong University of Science and Technology (Natural Science Edition),2012,40 (2):107-111(in Chinese).[曾山,同小軍,桑農(nóng),等.基于對應(yīng)分析的冗余模糊C均值聚類算法研究 [J].華中科技大學學報 (自然科學版),2012,40 (2):107-111.]
[4]HE Zhenghong,LEI Yingjie.Reaearch on intuitionistic fuzzy C-means clustering algorithm [J].Control and Decision,2011,26 (6):847-850 (in Chinese). [賀正洪,雷英杰.直覺模糊C均值聚類算法研究 [J].控制與決策,2011,26(6):847-850.]
[5]WANG Wei,WANG Lei,LI Yuxiang.Fuzzy clustering algorithm based on artificial immune cell model [J].Computering Engineering,2011,37 (5):13-15 (in Chinese). [王偉,王磊,李玉祥.基于人工免疫細胞模型的模糊聚類算法 [J].計算機工程,2011,37 (5):13-15.]
[6]HUANG Minming,LIN Bogang.Fuzzy clustering method based on genetic algorithm in intrusion detection study [J].Journal on Communications,2009,30 (11A):140-145 (in Chinese).[黃敏明,林柏鋼.基于遺傳算法的模糊聚類入侵檢測研究 [J].通信學報,2009,30 (11A):140-145.]
[7]PU Pengbo,WANG Ge,LIU Tai’an.Research of improved fuzzy C-means algorithm based on particle swarm optimization[J].Computer Engineering and Design,2008,29 (16):4277-4299 (in Chinese). [蒲蓬勃,王鴿,劉太安.基于粒子群優(yōu)化的模糊C-均值聚類改進算法 [J].計算機工程與設(shè)計,2008,29 (16):4277-4279.]
[8]LIU Kunpeng,LUO Ke.Improved fuzzy C-means clustering algorithm [J].Computer Engineering and Applications,2009,45(21):97-98 (in Chinese).[劉坤朋,羅可.改進的模糊 C均值聚類算法 [J].計算機工程與應(yīng)用,2009,45 (21):97-98.]
[9]ZHU Jingwei,RUI Ting,JIANG Xinsheng,et al.Simulated annealing ant colony algorithm for QAP [J].Computer Engineering and Applications,2011,47 (14):34-36 (in Chinese).[朱 經(jīng)緯,芮挺,蔣新勝,等.模擬退火蟻群算法求解二次分配問題[J].計算機工程與應(yīng)用,2011,47 (14):34-36.]
[10]ZHU Haodong,ZHONG Yong.An improved simulated annealing algorithm [J].Computer Technology and Development,2009,19 (6):32-35 (in Chinese). [朱顥東,鐘勇.一種改進的模擬退火算法 [J].計算機技術(shù)與發(fā)展,2009,19 (6):32-35.]
[11]LI Fangfang,WANG Jing.A best clustering scheme based on simulated annealing algorithm in wireless sensor networks[J].Chinese Journal of Sensors and Actuatorsl,2011,24(6):900-904 (in Chinese).[李芳芳,王靖.一種基于模擬退火算法的無線傳感器網(wǎng)絡(luò)最優(yōu)簇類求解方案 [J].傳感技術(shù)學報,2011,24 (6):900-904.]
[12]LI Zhengwei,TAN Guojun.Research and application of improved simulated annealing genetic strategy [J].Computer Engineering and Applications,2010,46 (4):245-248 (in Chinese).[李政偉,譚國俊.改進的退火遺傳優(yōu)化策略應(yīng)用 研 究 [J]. 計 算 機 工 程 與 應(yīng) 用,2010,46 (4):245-248.]
[13]LIU Jia,LIU Lina,LI Jing,et al.Research of improved artificial fish swarm algorithm based on simulated annealing algorithm [J].Computer Simulation,2010,28 (10):195-198(in Chinese).[劉佳,劉麗娜,李靖,等.基于模擬退火算法的改進人工魚群算法 [J].計算機仿真,2010,28(10):195-198.]
[14]ZHANG Guosuo, ZHOU Chuangming, LEI Yingjie.Improved FCM clustering algorithm and its application in intrusion detection [J].Computer Applications,2009,29(5):1336-1338 (in Chinese). [張國鎖,周創(chuàng)明,雷英杰.改進FCM聚類算法及其在入侵檢測中的應(yīng)用 [J].計算機應(yīng)用,2009,29 (5):1336-1338.]