almost 3 years ago

談到clustering 一般人直覺反應的就是k-means clustering
本質上k-means clustering背後是一個參數化的model

今天要跟各位介紹一個有趣的clustering方法
叫做mode clustering, 或被稱為"mean shift clustering"
這是一個non-parametric(model-free) clustering的方法
我們不需要假設資料是從什麼常態分配 或是混合型分配之類的產生

這個方法已經在非統計的領域被用了好幾年
但一直到最近才慢慢被統計學家拿來使用

這邊是一個例子:


看到這樣的資料點
一個直覺就是 上下各有一個clusters

所以我們會希望得到像下面這樣個結果


我這個clustering的成果
就是靠mode clustering做出來的

那麼 這個mode clustering到底是怎麼做的呢?
首先 給定一開始的資料點 我們先透過kernel density estimation(KDE)把機率密度重建出來
下面這張圖就是原本的資料點(黑點)還有機率密度的等高線圖

我們可以清楚地看到兩個局部的密度最高點(local modes) 我用紅色的十字表示

現在 對於每一個點 我們都計算他的密度梯度(gradient of density)
然後沿著這個密度梯度上昇 根據一個數學定理(Morse Theory)
只要這個密度函數滿足某些平滑的性質
大部份的點沿著密度梯度前進 最後都會跑到局部的密度最高點
正如下面這張圖所表示的

mode clustering很簡單 我們把資料分成一群群
根據他們沿著這個密度梯度前進的"終點" 也就是他們所抵達的局部密度最高點
下面是另一個例子

在一般使用時 mode clustering基本上可以按照mean shift algorithm快速地計算出來

下面是一個最近的mode clustering的研究成果
一個視覺化8維度mode clustering的方法:


(from Chen, Yen-Chi, Christopher R. Genovese, and Larry Wasserman. "Enhanced Mode Clustering." arXiv preprint arXiv:1406.1780 (2014))

如果對細節有興趣的讀者 可以讀下面幾篇papers
1-3: 經典的方法papers 如果只有時間 我個人推薦讀第三篇 (citation>7,000)
4: 一個有趣的mode clustering延伸版本
5: 一個更快速做mode clustering的方法
6: 一些mode clustering的延伸 包含visualizing多維度的成果

References:

  1. Fukunaga, Keinosuke, and Larry Hostetler. "The estimation of the gradient of a density function, with applications in pattern recognition." Information Theory, IEEE Transactions on 21, no. 1 (1975): 32-40.

  2. Cheng, Yizong. "Mean shift, mode seeking, and clustering." Pattern Analysis and Machine Intelligence, IEEE Transactions on 17, no. 8 (1995): 790-799.

  3. Comaniciu, Dorin, and Peter Meer. "Mean shift: A robust approach toward feature space analysis." Pattern Analysis and Machine Intelligence, IEEE Transactions on 24, no. 5 (2002): 603-619.

  4. Li, Jia, Surajit Ray, and Bruce G. Lindsay. "A Nonparametric Statistical Approach to Clustering via Mode Identification." Journal of Machine Learning Research 8, no. 8 (2007): 1687-1723.

  5. Carreira-Perpiñán, Miguel Á. "Fast nonparametric clustering with Gaussian blurring mean-shift." In Proceedings of the 23rd international conference on Machine learning, pp. 153-160. ACM, 2006.

  6. Chen, Yen-Chi, Christopher R. Genovese, and Larry Wasserman. "Enhanced Mode Clustering." arXiv preprint arXiv:1406.1780 (2014).

← Regressogram: 一種non-parametric視覺化分析方法 預測--Machine Learning優於統計之處 →
 
comments powered by Disqus