[解答] A.R. Clustering

[longlyeagle (長鷹寶寶實驗室)]

題目：

Alex Rodriguez 與 Alessandro Laio 在 2014年的六月

於 Science 上面發表了一個聚類的演算法:

Clustering by fast search and find of density peaks

裡面利用群聚的一些特性還形成一種新的聚類模型

在聚類這種發展多年的領域裡還可以發表 Science 論文真的很不容易


請問該驗算法是如何做到聚類的?
















==============================================================================





                解答在下一頁喔！！！小心不要雷到！！！



★☆★☆★☆★☆本篇解答含18禁、血腥、暴力、獵奇、令人不適之內容，
                可能不適合18歲以下板友觀賞，請自行斟酌，不喜者請左轉★☆★☆★☆


               ((若本題是採擷其他作品內容者，請於解答前註明))

   ((若解答無上述內容者，請出題者自行Ctrl+y刪除★☆部份，保留剩餘防雷頁))





==============================================================================










解答：

不同於過去的演算法注重於"群"的概念

這篇的演算法把model的重心放在"群的中心點" 或是 "clustering center"

先把一個群的中心點該有的特性找出來

再去看看其他點會被歸類到哪個中心點底下

他們列出了兩個重點:

1. 群的中心點有高密度

2. 群的中心點距離比他密度高的點應該有一定的距離

   (否則他就應該只是附屬於另一個群的點 而不是中心點)


計算了所有點的密度 還有距離密度高於他的點的距離之後

我們可以找出群聚中心(clustering center) 單獨點(outlier)

還有群聚的點裡面屬於核心的點跟邊緣的點


相較於現在主流的聚類演算法 DB-SCAN K-Mean

他不需要做iteration

只需要一次linear的運算

在記憶體時間跟空間的運用上都大大的提升

而且在參數有調整好的情況下有極佳的辨識率


出處、作者：
science

備註：
想不到被秒殺
我以為會玩一陣子 (都沒人)

===================注意解答的標題要跟題庫一樣喔！===============================

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.94.182
※ 文章網址: http://www.ptt.cc/bbs/TurtleSoup/M.1417106284.A.EE9.html
※ 編輯: longlyeagle (114.32.94.182), 11/28/2014 00:41:59
推 AlexCYW: 原來如此 先假設群中心點一定會有的特性然後直接挑出來
→ AlexCYW: 之前的方法比較像是各種計算後看有沒有比較突出的
→ longlyeagle: 像是K-Mean他一開始就是假定"群"跟"群"會分的比較開
→ longlyeagle: DB-SCAN也是假定群體之間的點可以互相串連
→ longlyeagle: 跟用"群的中心點"來聚類的想法是有顯著的不同
推 naminono: 圖3D的線範例，是因為三條線的點間距很類似才分的出的?
→ longlyeagle: 跟類似無關 是因為密度比你高又離你最近的點
→ longlyeagle: 大多是在線的上下幾點 最後總會連到密度高的線頭
推 AlexCYW: 原來如此 我忘了其他方法要iteration
推 naminono: 喔喔喔原來如此
→ AlexCYW: 那這樣的確複雜度較低
→ AlexCYW: 不過這樣會有誤差傳遞問題嗎
→ longlyeagle: 那就要看怎麼定義誤差了 如果有確定的答案
→ longlyeagle: 那參數調整的不好是有可能會有不好的分類效果沒錯
推 AlexCYW: 畢竟被分群後就不可逆了
→ longlyeagle: 是的