近一個半月來的Clustering心得

最近做了一個和clustering有關的研究，基於不要被自己吐糟的考量下，花了一些時間讀clustering相關的東西，發現這領域真是又深又廣，永遠有做不完的題目，呃．．．有沒有意義是另一回事。趁剛結束一個階段的研究，記錄一下心得，不然腦容量有限，一個月後大概就忘了。

clustering的定義是，給定 n 筆資料，每筆資料有 d 個屬性，將資料分成 k 群。特別的是，事先沒有群的定義，只能從屬性判斷兩筆資料是否相似，將相似的資料放到同一群。比方資料是地理位置，那台北市和台北縣就挺像的，應該歸到同一群裡。注意，何謂「相似」是無法明確定義的，這是 clustering 裡一個很大問題，也提高驗證方法正確性的難度。於是，依據分群的特性，就分成許多不同題目，像是centered-based clustering，同一群資料的屬性的變異數 (variance) 要小；或是density-based clustering，同一群資料和「週圍」資料之間的密度要相近。也有將資料以 graph 表示而成的 graph-based clustering。一開始我沒把這些分類弄清楚，以為可以有某種程度的互通使用，但實測後才意識到，其實方法之間差異很大，依要解的題目特性，套錯方法效果會極差，比方資料可以輕易地轉成graph，但這不表示套用graph-based clustering會有用，至少像 graph 難以用 edge weight 表示 centroid (or mean)，所以不適合用來解 centered-based clustering。

除了五花八門的分群目標外，cluster 的數量也是個問題。是要給定 k ，找出 k 個 cluster？還是給定一個範圍？或是根本沒有數量限制？於是各群內部的相似度和分群的數量合起來，就變很複雜的問題，畢竟群的數量愈多，各群的變異數會愈小。很難同時考量兩者給個合理的評估分式，所以大部份的研究先限定 cluster 的數量，再討論如何降低變異數或其它評估值。silhouette coefficient是個有趣的公式，它的概念頗合理的，又能同時考量兩者，但我套用它到centered-based clustering，實測的結果 [1]，計算量頗大，效果也不好。原因不明，我後來沒有仔細測試和探討背後成因。

若再加上一些細項要求，題目可以組合出更多變化，像是利用每個 cluster 內最少要有幾筆資料，可以得到一些良好的數學特性，而有不錯的成果。當然，當這個數量限制難以找到合理值時，這些方法也無用武之地。細項限制帶來的變化在 clustering with constraint 中有更系統化的研究，用這當 keyword 應該會找到一大票研究，有限制不見得是加深題目難度，有時反而變更簡單，可以協助分群；甚至也可以將重心放在如何從既有資料裡生出 constraint。

從分群的反向來看，驗證分群結果也是一大難題，但似乎沒有論文在專門討論這個（吃力不討好？），我也沒仔細去找就是了。對於未知答案的研究來說，有時只要改變評估方式，大壞的結果也可能變成大好。前面提到分群的概念變化多端，加深了評估方法之間優伏的難度。Introduction to Data Mining
的 ch 8.5 有頗詳細的介紹，值得一看。

以上的心得是以該書的 ch8, ch9 和一些零星論文得來，書裡那兩章的內容我也沒全看完，若要看完那兩章並確實理解，一兩個月跑不掉吧，但若有心在這個領域研究的話，個人覺得是必須做，而且很值得做的事。最後補一些雜項，參與 clustering 研究的人，就我個人的主觀分類，可以分成 Data Mining 背景、 Machine Learning 背景和 Statistics 背景的人。依不同背景來看，方法的切入點差異很大。 Data Mining 背景是指像傳統 Computer Science 背景的做法，或是指「比較不數學」的做法。另一方面，是否一定要能處理大量資料，才稱得上有意義的方法，就見仁見智了。

ps.

1. 我的做法是用hierarchy clustering，一開始每筆資料自成一個 cluster，看合併那兩個 cluster 可以達到最佳的silhouette coefficient，就選那兩個合併。全部併完後，會有 n 種可能分法（全部一群、兩群、．．．、 n 群），選silhouette coefficient值最高的 k 個cluster當結果。