作者(Alex Rodriguez, Alessandro Laio)提出了一種很簡(jiǎn)潔優(yōu)美的聚類算法, 可以識(shí)別各種形狀的類簇, 并且其超參數(shù)很容易確定.

算法思想

該算法的假設(shè)是類簇的中心由一些局部密度比較低的點(diǎn)圍繞, 并且這些點(diǎn)距離其他有高局部密度的點(diǎn)的距離都比較大. 首先定義兩個(gè)值: 局部密度ρi以及到高局部密度點(diǎn)的距離δi:

其中

dc是一個(gè)截?cái)嗑嚯x, 是一個(gè)超參數(shù). 所以ρi相當(dāng)于距離點(diǎn)i的距離小于dc的點(diǎn)的個(gè)數(shù). 由于該算法只對(duì)ρi的相對(duì)值敏感, 所以對(duì)dc的選擇比較魯棒, 一種推薦做法是選擇dc使得平均每個(gè)點(diǎn)的鄰居數(shù)為所有點(diǎn)的1%-2%.

對(duì)于密度***的點(diǎn), 設(shè)置. 注意只有那些密度是局部或者全局***的點(diǎn)才會(huì)有遠(yuǎn)大于正常的相鄰點(diǎn)間距.

聚類過(guò)程

那些有著比較大的局部密度ρi和很大的δi的點(diǎn)被認(rèn)為是類簇的中心. 局部密度較小但是δi較大的點(diǎn)是異常點(diǎn).在確定了類簇中心之后, 所有其他點(diǎn)屬于距離其最近的類簇中心所代表的類簇. 圖例如下:

左圖是所有點(diǎn)在二維空間的分布, 右圖是以ρ為橫坐標(biāo), 以δ為縱坐標(biāo), 這種圖稱作決策圖(decision tree). 可以看到, 1和10兩個(gè)點(diǎn)的ρi和δi都比較大, 作為類簇的中心點(diǎn). 26, 27, 28三個(gè)點(diǎn)的δi也比較大, 但是ρi較小, 所以是異常點(diǎn).

聚類分析

在聚類分析中, 通常需要確定每個(gè)點(diǎn)劃分給某個(gè)類簇的可靠性. 在該算法中, 可以首先為每個(gè)類簇定義一個(gè)邊界區(qū)域(border region), 亦即劃分給該類簇但是距離其他類簇的點(diǎn)的距離小于dc的點(diǎn). 然后為每個(gè)類簇找到其邊界區(qū)域的局部密度***的點(diǎn), 令其局部密度為ρh. 該類簇中所有局部密度大于ρh的點(diǎn)被認(rèn)為是類簇核心的一部分(亦即將該點(diǎn)劃分給該類簇的可靠性很大), 其余的點(diǎn)被認(rèn)為是該類簇的光暈(halo), 亦即可以認(rèn)為是噪音. 圖例如下

A圖為生成數(shù)據(jù)的概率分布, B, C二圖為分別從該分布中生成了4000, 1000個(gè)點(diǎn). D, E分別是B, C兩組數(shù)據(jù)的決策圖(decision tree), 可以看到兩組數(shù)據(jù)都只有五個(gè)點(diǎn)有比較大的ρi和很大的δi. 這些點(diǎn)作為類簇的中心, 在確定了類簇的中心之后, 每個(gè)點(diǎn)被劃分到各個(gè)類簇(彩色點(diǎn)), 或者是劃分到類簇光暈(黑色點(diǎn)). F圖展示的是隨著抽樣點(diǎn)數(shù)量的增多, 聚類的錯(cuò)誤率在逐漸下降, 說(shuō)明該算法是魯棒的.

***展示一下該算法在各種數(shù)據(jù)分布上的聚類效果, 非常贊.

參考文獻(xiàn):

[1]. Clustering by fast search and find of density peak. Alex Rodriguez, Alessandro Laio

本文出自：Kemaswill's Blog