海平面聚類算法

馬 杰，楊 磊，徐 建

（1江蘇師范大學(xué) 智慧教育學(xué)院（計算機(jī)科學(xué)與技術(shù)學(xué)院），江蘇 徐州221116；2中國礦業(yè)大學(xué)徐海學(xué)院 計算機(jī)系，江蘇 徐州221008）

0 引 言

本文算法不是一個獨立的聚類算法，是用來輔助其它聚類算法更好、更有效地聚類的輔助算法。與其它聚類算法結(jié)合使用，能有效地改善聚類算法的聚類效果。

1 問題的提出

有些算法聚類的結(jié)果與自然分類有出入，有些算法對某些情況不能正確的分類。比如：Affinity Propagation（AP）聚類算法，是基于數(shù)據(jù)點間的“信息傳遞”的一種聚類算法。算法的基本思想是：將全部樣本看作網(wǎng)絡(luò)節(jié)點，通過網(wǎng)絡(luò)中各條邊的消息傳遞 計算出各樣本的聚類中心。聚類過程中，共有兩種消息在各節(jié)點間傳遞，分別是吸引度（responsibility）和歸屬度（availability）。通過在點之間不斷地傳遞信息，最終選出代表元以完成聚類。AP算法通過迭代過程不斷更新每一個點的吸引度和歸屬度值，直到產(chǎn)生m個高質(zhì)量的Exemplar（類似于質(zhì)心），同時將其余的數(shù)據(jù)點分配到相應(yīng)的聚類中。其特點如下：

（1）不需要制定最終聚類個數(shù)。

（2）將已有數(shù)據(jù)點作為最終的聚類中心，而不是新生成聚類中心。

（3）模型對數(shù)據(jù)的初始值不敏感，多次執(zhí)行AP聚類算法，得到的結(jié)果是完全一樣的，即不需要進(jìn)行隨機(jī)選取初值步驟。

（4）對初始相似度矩陣數(shù)據(jù)的對稱性沒有要求。

（5）與k中心聚類方法相比，其結(jié)果的平方差誤差較小，相比于K-means算法，魯棒性強(qiáng)、準(zhǔn)確度較高，但算法復(fù)雜度高、運算消耗時間多。

在實際的使用中，AP有兩個重要參數(shù)：preference（定義聚類數(shù)量）和damping factor（控制算法的收斂效果）。

聚類就是個不斷迭代的過程，迭代的過程主要是更新兩個矩陣：

吸引度矩陣R：［r（i，k）］N×N

歸屬度矩陣A：［a（i，k）］N×N

在不斷交替更新a和r值，達(dá)到一定的次數(shù)或收斂后，選取使得r（i，k）+a（i，k）最大的那個k作為i的代表元。其中s（i，k）表示similarity，可以翻譯為相似度或度量。是指點k作為點i的聚類中心的相似度，一般使用歐氏距離來計算。相似度值越大說明點與點的距離越近，這在幾乎所有的聚類分析中都是最基礎(chǔ)的量。

AP算法（參見參考文獻(xiàn)［1］）是一個很好的聚類算法。但當(dāng)有大類靠近小類時，往往會把大類的一些邊緣點錯分給小類。如對圖1中的數(shù)據(jù)，其AP算法的聚類結(jié)果如圖2所示。顯然，沒有分成左邊兩個小類，右邊一個大類。而是小類占了大類的幾個點。另外，還有一些算法（本文選定一種密度算法，本文稱MD算法）對有些數(shù)據(jù)不能正確的分開。如圖3的數(shù)據(jù)，右邊兩類中間有兩行點連接在一起，很多聚類算法就無法將這兩類分開。

圖1 AP算法數(shù)據(jù)準(zhǔn)備 Fig.1 AP algorithm data preparation

圖2 AP算法分類結(jié)果Fig.2 AP algorithm classificationresults

2 問題分析

由上述分析可以看出，問題都出在類的邊緣點上。AP算法的問題是大類的幾個邊緣點離大類的中心點過遠(yuǎn)，而離靠近其小類中心點更近。另外一些算法無法將圖3右邊兩個類分開，是因為靠近兩個類的共同邊緣的點連接在了一起。

圖3 MD算法數(shù)據(jù)準(zhǔn)備Fig.3 MD algorithm data preparation

3 解決方法

如果能把這些出問題的邊緣點先0拿掉（拿掉的點最后還要歸類到分好的類中）再進(jìn)行分類，就不會有上面的問題了。那么，一個問題是解決如何區(qū)分邊緣點，其二是如何將拿掉的點歸類。

首先，對每個點定義一個密度函數(shù)，使得類的邊緣點的密度小，越靠近中心的點密度越大，這樣就解決了第一個問題。再定義每個點的歸屬點為離此點最近的密度大于自己的點，這樣第二個問題就解決了。判斷邊緣點時，不是直接用密度函數(shù)的密度值判斷，而是用傳導(dǎo)歸屬點數(shù)（既A點到其歸屬點B點，B點再到其歸屬點C點，等等，一直傳導(dǎo)下去所經(jīng)歷的點叫A點的傳導(dǎo)歸屬點，這個過程叫傳導(dǎo)歸屬。而傳導(dǎo)歸屬數(shù)是所有能傳導(dǎo)歸屬到此點的點的個數(shù)），傳導(dǎo)歸屬點數(shù)越小越邊緣，反之越中心。引進(jìn)一個參數(shù)k，傳導(dǎo)歸屬數(shù)小于其則為邊緣點。先剔除邊緣點，然后根據(jù)某聚類算法聚類，最后將邊緣點傳導(dǎo)歸屬到已分好的類中。

本文定義密度函數(shù)：

（1）此點密度為，此點到所有點的距離的倒數(shù)之和。

（2）數(shù)據(jù)的個數(shù)為n，每一點為其它各點打分。離此點最遠(yuǎn)的點得1分，次遠(yuǎn)點得2分，以此類推。最近的點得n-1分。定義每個點得密度為此點得分的總和。

第一個密度函數(shù)要求數(shù)據(jù)先要剔除相同的數(shù)據(jù)點。

4 應(yīng)用效果

本算法與AP算法結(jié)合（以下密度函數(shù)均選擇第一種），采用聚類圖1的數(shù)據(jù)，選擇K為2，邊緣點如圖4所示（方形空心為邊緣點），聚類結(jié)果如圖5所示。本文算法與MD算法結(jié)合，采用聚類圖3的數(shù)據(jù)，選擇k為3，邊緣點如圖6所示（圓形空心為邊緣點），聚類結(jié)果如圖7所示。

圖4 AP算法結(jié)合海平面算法的邊緣圖Fig.4 Edge map of AP algorithm combined with sea level algorithm

圖5 AP算法結(jié)合海平面算法結(jié)果Fig.5 Results of AP algorithm combined with sea level algorithm

圖6 MD算法結(jié)合海平面算法的邊緣圖Fig.6 Edge map of MD algorithm combined with sea level algorithm

圖7 MD算法結(jié)合海平面算法的結(jié)果圖Fig.7 Result chart of MD algorithm combined with sea level algorithm

5 結(jié)束語

本算法之所以叫海平面聚類算法，是因為k參數(shù)相當(dāng)于設(shè)置海平面，邊緣點都淹沒在海水里，只對陸地進(jìn)行聚類，因此得名。本算法與其它聚類算法結(jié)合可以明顯改善聚類結(jié)果，經(jīng)實驗證明，本算法是有效的。