over 2 years ago

Clustering可以說是三大常見統計問題之一
(另外兩個是regression還有classification)
簡單來說 clustering就是當給定一群資料後
靠資料點之間的相似性 把資料點分成幾個群


(上圖是mean shift clustering)

而進行clustering的方法也有好幾種
常見的有 k-means clustering, spectral clustering, mean shift clustering, hierachical clustering ...等等

如果你讀統計文獻 談到clustering總會覺得跟一般統計問題不太一樣
因為一般統計文獻很重視"統計收斂性"
也就是當樣本數越來越大時 會有怎樣的表現
但clustering比較少文獻探討統計收斂性

這個關鍵在於
"描述clustering的收斂性並不容易"

一般來說clustering就是把資料點分群
但收斂性探討的是當資料點的數量n趨近於無限大時的表現性
在這情況下clustering會變成要把"無限多個點分群"
有限的點很好探討分群
但無限多個點 要怎麼分群 並不是一個好操作的事情

這篇我簡單談一下三個常見的clustering方法的收斂性:
k-means clustering, spectral clustering, 以及mean shift clustering
有趣的是 這三個方法用了不同的方式來刻劃收斂性

1. k-means clustering--

Pollard, David. "Strong consistency of $ k $-means clustering." The Annals of Statistics 9, no. 1 (1981): 135-140.

k-means的特性是 clustering的成果完全由那k個中心所決定
所以只要能夠證明根據樣本的k個中心 會收斂到 根據"真實分配函數"定義出來的k個中心
就能夠描述收斂性 而這正是Pollard[1981]裡面談的方法

2. Spectral clustering--

Von Luxburg, Ulrike, Mikhail Belkin, and Olivier Bousquet. "Consistency of spectral clustering." The Annals of Statistics (2008): 555-586.

Spectral clustering利用的是資料點與資料點之間的距離矩陣
(這個矩陣的[i,j]元素即是資料點i與資料點j的距離)
適當的重整劃過後 進行eigen-decomposition然後用最大的幾個eigenvectors來進行k-means clustering
(最大的幾個eigenvectors: 大小是根據對應的eigenvalues)

Von Luxburg et. al.[2008]證明收斂性的方式很優雅
因為整個關鍵是前面幾個eigenvectors
所以他們把問題從linear operator的角度出發
(類似把距離矩陣看成一個linear operator)
而linear operator本身就俱有eigenvectors
因此前面幾個eigenvectors可以看成一個基於"樣本"所產生的linear operator
接著定義一個根據"真實資料分配(母體)"所建構出來的linear operator
最後只要證明樣本的operator的前面幾個eigenvectors會收斂到母體的對應量即可

3. Mean shift clustering--

Chen, Yen-Chi, Christopher R. Genovese, and Larry Wasserman. "Statistical Inference using the Morse-Smale Complex." arXiv preprint arXiv:1506.08826 (2015).

Mean shift clustering的收斂性是最近才剛剛被證出來
Mean sfhit的特色是: 他完全是靠著kernel density estimator來估計密度 然後用mode clustering去做分群
因此 比較的對象非常明確--即是mode clustering基於母體的資料密度函數

Chen et. al.[2015]描述收斂性的方法很直接--靠著clusters彼此的邊界來探討
在母體密度函數下 我們clusters會有邊界D
根據樣本 我們會產生clusters邊界E
我們只要說明邊界E收斂到邊界D即可說明mean shift會收斂
而這篇文章的重點也在於如何證明邊界E會收斂到邊界D
(他們其實證明了廣義上的mode clustering的收斂性)

---

雖然這三個方法收斂性的描繪不盡相同
他們其實都俱有下列的性質

  1. 定義一個母體的clustering結構 (k-means是靠k個中心; spectral是靠前面幾個eigenvectors; mean shift靠clusters的邊界)
  2. 說明如何在這樣的結構下定義"收斂" (數學上就是找一個metric 讓這些可能的結構成為一個metric space)
  3. 證明樣本的clustering結構收斂到母體的結構

基本上 上述這三個性質就是要把clustering的問題轉換成估計(estimation)的問題
因此可以探討所謂的收斂性

做實務的人可能會問 為什麼我們在乎clustering的收斂性?
除了這個問題理論上本身有趣之外
收斂性會告訴我們當我們收集到越來越多樣本後 我們clustering的結果是穩定的
此外 收斂的對象(母體的clustering結構)多半告訴我們這套clustering背後再運用的是怎樣的數學/統計模型
這在詮釋clustering上非常好用
而證明收斂性的定理往往需要一些假設
當今天一筆資料某個clustering方法失敗 我們就能知道某些假設是不滿足的--這往往能夠引導我們往後的處理

← 常見的三大類型統計理論 淺談變數獨立性 →
 
comments powered by Disqus