跳去內容

DBSCAN

出自維基百科,自由嘅百科全書

DBSCAN 可以話係最多人用嘅基於密度聚類法之一[1][2],係Density-based spatial clustering of applications with noise嘅縮寫,喺1996年由Martin Ester、Hans-Peter Kriegel、Jörg Sander 同 Xiaowei Xu 提出。

步驟

[編輯]

步驟如下:

  • 想像有一點 ,如果佢周圍半徑 嘅範圍內超過咗 咁多點,噉佢就算係核心點(core);
  • 想像有兩點 ,如果 (兩點之間嘅距離) ,噉 算係可以由 直接去到(directly reachable from );順帶一提, 一定要係核心點。
  • 想像有兩點 ,如果有條路徑 ,當中 而且 ,期間每點( 等)都可以由打前嗰點直接去到嘅,噉 算係可以由 去到(reachable from );
  • 所有「唔能夠由第啲點度去到」嘅點,冚唪唥當係雜訊

如果 係核心點,噉佢同所有由佢度去到嘅點成一個聚類。

用圖像表示嘅話,可以想像下圖:下圖 ,A 等嘅紅色點全部都係核心點,因為佢哋全部都有「周圍 咁遠嘅範圍(啲圓圈)內有超過 咁多點」呢種特性,黃色點 B 同 C 唔係核心點,但可以由 A 去到,於是啲紅色點加埋 B 同 C,就成一個聚類;藍色點 N 唔能夠由任何一點度去到,所以當係雜訊忽視。

睇埋

[編輯]

參考資料

[編輯]
  1. Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011-04-05). "Density-based Clustering". WIREs Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30.
  2. Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (編). A density-based algorithm for discovering clusters in large spatial databases with noise (PDF). Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. 原著 (PDF)喺2022年7月9號歸檔. 喺2022年9月26號搵到.