海平面聚類算法

馬 杰，楊 磊，徐 建

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

0 引 言

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

1 問題的提出

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

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

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

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

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

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

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