Efficent density-based clustering algorightms
title: Design of computationally efficient density-based clustering algorithms ---- pdf download
code: None
abstract
本文針對基于密度的聚類方法劫瞳，提出了優(yōu)化策略格带，能夠大幅度降低計算復雜度雪情。針對DBSCAN聚類策略，首先通過快速融合策略來降低初始化階段的計算復雜度糊秆，然后考慮到相似性度量時候的相關系數(shù)虐秋，通過相關性來判斷兩個點是否屬于同一個類摊唇。
proposed algorithm
DBSCAN算法一共分為兩步：初始化核心對象和合并小的類兩個步驟，該方法和傳統(tǒng)的DBSCAN的方法有所不同授帕，傳統(tǒng)的DBSCAN中提到的兩階段方法如下：
- 第一步，計算所有的核心對象浮梢，得到核心對象集合
- 第二步跛十，隨機從核心對象集合中間取一個樣本，計算該核心對象所有密度直達的點秕硝，依次判斷這些點是否是核心對象芥映，如果是的話，就加入到該核心對象的cluster中远豺，否則（邊界點）跳過該點奈偏。其中每個點只能被訪問一次，也就是說每個點一旦被某個cluster吸收進去了躯护，就不會在被其他cluster進行吸收惊来，因此DBSCAN的最終分類的結果和樣本的訪問順序是有關的，即DBSCAN是一種不穩(wěn)定的聚類方法榛做。
針對DBSCAN的方法唁盏，本文在第二步的時候，沒有依次判斷核心對象的所有密度直達的點是否是核心對象检眯，而是在第一步計算完所有的核心對象之后厘擂，得到每個核心對象的small cluster之后，對這些small cluster進行合并锰瘸，并且采用了一種很巧妙的方法極大的降低了計算復雜度刽严。
合并策略如下
（1）基于距離度量的快速合并算法
對于兩個cluster A 和 B，兩個cluster的距離計算如下：
其中y和z分別是 和
的邊界點避凝，因此（1）的計算復雜度應為
加速策略：
但是考慮到每個cluster在高維空間是一個球形舞萄，因此我們先計算cluster A 和 cluster B的點，分別為和
管削，如果
和
之前的距離大于
倒脓， 則A和B的最小點的距離必然大于
，根據(jù)這個條件含思，我們可以判斷兩個類是否進行合并崎弃。
（2）基于相關系數(shù)的度量
對于兩個cluster A 和 B甘晤，兩個cluster的距離通過皮爾遜相關系數(shù)來確定，相關系數(shù)的值為-1到1之間饲做，計算如下：
的值具有如下兩個特性：
- 對稱性：
- 位置和尺度不變性：
該種方法要求在DBSCAN的第一步的尋找核心對象的時候线婚，采用相關系數(shù)來判斷一個類是否為核心對象：
因此，兩個cluster是否合并盆均，取決于兩個cluster的最大相關系數(shù)是否大于給定的閾值塞弊，公式如下：
加速策略：
采用相關系數(shù)來替代空間密度的方法，最后聚的類不能采用球形那種判斷策略泪姨，因此采用兩個cluster的均值來代替游沿。
