最近做了一個和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.
- 我的做法是用hierarchy clustering,一開始每筆資料自成一個 cluster,看合併那兩個 cluster 可以達到最佳的silhouette coefficient,就選那兩個合併。全部併完後,會有 n 種可能分法(全部一群、兩群、...、 n 群),選silhouette coefficient值最高的 k 個cluster當結果。