Clustering

2020-12-22T09:48:43+08:00

分群 Clustering 分群就是在做分組,使分組後組別裡個體與其他組別裡個體比起組別內個體跟組別外個體之間有較高的相似度。 若是在圖像上做分群,就可以做到圖像分割。(圖像分割是電腦視覺裡面一個很重要的一環。圖像分割是依據像素的特性辨識出物體和邊界把圖像區分成不同的區域,以簡化圖形的複雜度,以求能做更有效的分析。)因為同一個物體裡面的像素跟背景和其他物體的像素相比,顏色,亮度,和質地會相似度比較高,可以有效的應用分群法把相似度較高的像素圈選在同一組裡,達成圖像分割。 有很多不同的分群方式。以下簡單介紹其中的三種方法。這三種方法都是透過不斷的迭代運算,反覆試驗,直到成功的收斂,有可能會成功的收斂在總體最小值,但也有可能收斂在局部最小值。 圖一 第一種方法是聚合式階層分群法 Hierarchical Agglomerative Clustering (HAC) - 階層分群法就是在一層一層的分群。共有兩種階層分群法。一種是由下而上的聚合式分群法 Agglomerative Clustering。它又被稱為AGglomerative NESting (AGNES)。另一種是由上而下的分裂式分群法 Divisive clustering,或是DIvisive ANAlysis (DIANA)。一開始,演算法把每個點都識別成一個獨立的群,接著會檢視所有的群,把最相似的群兩個兩個合併成一個更大的群。一直重複的合併直到所有的點都分群到了單一的大群中。整個流程就像圖一的樹狀圖。以圖一為例,在最下面的每個點都代表一個物體,在圖像中就代表像素。樹狀圖向上移動,點跟點之間做連結。連結點越低,兩個點的相似度越高。連結點越高,相似度越低。只要在相對應的樹狀圖高度切割,就可以決定會分幾群。如圖一,在框框的上緣做切割,就會分成四群。 圖二 第二種方法是k-平均演算法 K means。k-平均演算法使用的是最大期望演算法 Expectation-maximization algorithm。基本上是分成四個步驟:1,隨機選取一個點為群中心。2,接著重複步驟三和步驟四直到完成收斂。3,E-step 把群中心旁邊的點跟群中心歸類到同一群。4,M-step 計算平均值,把平均值設成新的群中心(圖二)。每一次重複E-step和M-step,都會調整群中心,更準確的分群。這個方法有幾個問題。一,他可能不是在總體最小值收斂,而是在局部最小值收斂。二,必須事先決定k的值,讓演算法知道要分幾群。若選的k值不適合,分群的結果就不會理想。三,只能線性的分群。四,速度有可能會很慢。因為所有的點都要讀取,點太多的時候,跑的速度就會慢。 圖三 第三種方法是均值漂移演算法 Mean Shift(圖三) - 這個方法跟第二種方法k-平均演算法相似。一開使都是隨機選點。接著,在點的外圍畫出一個圈做為過濾窗。在過濾窗中求平均值成為新的中心點。一樣是通過不斷的迭代運算,持續的把中心點往更密集處做移動。中心點會收斂在最密集的地方,無法再做移動,因為無論往哪個方向移動,點的數量都比較少,較不密集。 參考文獻: https://www.datanovia.com/en/lessons/agglomerative-hierarchical-clustering/ https://ai.stanford.edu/~syyeung/cvweb/tutorial3.html https://en.wikipedia.org/wiki/Cluster_analysis#Medicine https://jakevdp.github.io/PythonDataScienceHandbook/05.11-k-means.html https://en.wikipedia.org/wiki/Mean_shift#Clustering