海平面聚類算法

馬 杰，楊 磊，徐 建

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

0 引 言

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

1 問(wèn)題的提出

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

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

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

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

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

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

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

聚類就是個(gè)不斷迭代的過(guò)程，迭代的過(guò)程主要是更新兩個(gè)矩陣：

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

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

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

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

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

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

2 問(wèn)題分析

由上述分析可以看出，問(wèn)題都出在類的邊緣點(diǎn)上。AP算法的問(wèn)題是大類的幾個(gè)邊緣點(diǎn)離大類的中心點(diǎn)過(guò)遠(yuǎn)，而離靠近其小類中心點(diǎn)更近。另外一些算法無(wú)法將圖3右邊兩個(gè)類分開(kāi)，是因?yàn)榭拷鼉蓚€(gè)類的共同邊緣的點(diǎn)連接在了一起。

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

3 解決方法

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

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

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

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

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

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

4 應(yīng)用效果

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

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