如果有一組資料,沒有任何事先的分類標記,有辦法對它們進行分群(Clustering)嗎?呃……通靈比較快!想要分群,總是必須指定某些條件作為依據。

而分群演算法有不少,入門時,常會先接觸到K-means分群,因為它概念上容易理解,實作上也不困難,在機器學習的領域,K-means演算被歸類在非監督式(unsupervised)學習,意即無需人類介入標記,也能自動分群。

以距離來衡量勢力

從結果來看,K-means分群時,確實是不需要標記,但它並不是沒有任何假設就能自動分群。

在使用K-means分群時,其實就意謂著,同意了「資料之間有距離的概念」、「群心勢力範圍內的資料屬於同一群」的假設,也就是實際上,你還是已經告訴機器該怎麼做,簡單來說就是,以距離為勢力依據,尋找勢力均衡。

既然是以距離為依據,那麼,我們透過座標資料來理解K-means分群原理,是最為簡單的方式,若有一堆點散落在座標平面,這些點在視覺上顯然構成兩群,若要對這些點自動標記為A、B兩群,由於K-means的假設是「群心勢力範圍內的資料屬於同一群」,首要任務是尋找群心,然而,窮舉出各點間的組合、逐一計算距離,顯然行不通,因為需要的運算過於龐大。

一般而言,K-means尋找群心的方式,是採取最大期望(Expectation-maximization)演算法,先隨機找兩個位置當群心,接著是期望(Expectation)步驟,看其他點距離哪個群心近(通常採取歐式距離),就將該點畫分為與該群心同一群,最後會得到兩群,再接著是最大化(Maximization)步驟,最大化群心與群中各點的距離,針對兩群的資料,各求其幾何中心,作為新群心,也就是每個座標分量的算術平均值(這也就是為何K-means有means 字眼的原因),作為新的群心座標。

如果舊群心與新群心差距太大(未收斂),重複期望步驟與最大化步驟,直到舊群心與新群心變動不大(在某個差距內),或者是超過了指定的迭代次數而結束。以方才兩群座標為例,若能順利收斂,A群資料至A群心的距離,會小於它們至B群心的距離。

以距離加總來衡量群數

直接指定群數依距離分群,是K-means最常的應用之一,特別是透過資料在距離上的區隔,我們可以明顯觀察出一群一群的趨勢時,透過K-means就非常的方便。

座標之間的距離概念容易理解,然而,像分數之類的,也具有距離的概念,像是各學科分數,例如,有人擅長文科、有人擅長理科,此時,若將文科、理科的分數作為資料,可能也會有一群一群的趨勢;另外,像是人與人間的年紀差距、學歷差距、年收入差距、子女差距、居住城市發展指標的差距等,都是具有距離遠近的概念。

有時候手邊的資料,不見得能夠以可視化的方式,來判斷可以分為幾群(特別是高維資料),或者就算能可視化,也看不出群與群之間的分界為何,這時如何能決定該分為幾群呢?

基本上,同一群資料至其群心的距離,應該不會大於至另一群心的距離,既然如此,如果我們將各群資料各自平方距離的加總,應該可以作為分群個數的參考。

然而,隨著群數變大,各群平方距離加總必然會變小,為了尋找適當的平方距離加總,我們可以將群數與距離加總可視化為曲線,找出曲線中突然變和緩處的群數,這表示:更多群數終低平方距離加總的效益不大了,而這個方式稱為手肘法(Elbow method)。

另外,群與群之間的輪廓如果是明顯的,重疊的部份理應比較小。事實上,有一種稱為輪廓係數(Silhouette coefficient)的方式,我們可以用來評估群與群間的輪廓,計算方式為b*a/max(a, b),a是群中各點間的平均距離,b是某群中各點與最接近群中各點間的平均距離,而且,輪廓係數越大,分群的品質就越好。

只不過,找出可能的群數後,各群代表的意義,是必須去思考的,例如,給你一堆圖片,若透過手肘法、輪廓係數分析後,認為可以分為十群,那這十群代表什麼呢?如果圖片其實來自MINST手寫數字圖片資料集,能猜出這些圖片分群後代表著十個數字嗎?

也就是說,K-means可以作為一種分析資料的工具,例如,你手中有一組人們的資料,包含了學歷差距、收入差距、年紀、居住縣市(經緯度、離首都的遠近)等,這些資料會不會有某種群聚性呢?分為三個群,合理嗎?還是要四個、五個?如果這些資料能夠分群了,那麼,這些群個別又代表什麼意義呢?政治取向?消費習慣嗎?

以勢力的中心作為代表

使用K-means分群後,群心勢力範圍內的資料屬於同一群,談到勢力範圍,我們可能會直覺地聯想到Voronoi,其中每個細胞的核心,就相當於分群後的群心,細胞邊界規範的勢力範圍,就畫分了資料屬於哪一群,確實!若視覺化後群與群之間有明顯的群聚,透過沃羅諾伊圖(Voronoi Diagram),我們可以畫分出群與群之間的勢力界線。

群心是勢力範圍的幾何中心,是群中資料的平均值,若使用群心來取代該群中每一筆資料,不就可以是一種壓縮資訊的方式?例如,彩色圖片具有RGB三原色,而RGB的資訊可以當成座標資訊、畫在三維空間,相近的色彩在三維空間中,會有距離上的相近,若將之分群,以群心的RGB來作為同群的顏色,就可以減少色彩資訊。

可能的應用之一是,在印刷一張彩色圖片時,只能使用K個顏色,這時透過K-means來分出K群,找出群心的RGB資訊,使用群心顏色填滿同一群,也就是相近的顏色(不是像素座標上的距離相近)最後都變成同一色,最後圖片的顏色會被壓縮K個(不是像素被壓縮為K個)。

從另一方面來看,使用群心來代表該群資料,代表著n筆資料可以被壓縮為K筆資訊,也就是說,K-means某些程度上也可做為一種降維工具。無論是單純地壓縮資訊,或作為降維,K的選擇是直接視需求而定,跟平方距離加總、輪廓係數等的評估就無關了。

其他形狀的勢力範圍

使用K-means,其實,還有另一個假設,那就是:在採取歐氏距離的情況下,就二維來看,勢力範圍基本上是個圓形,三維來看是個球形,圓或球之間會有受到擠壓的界線;然而,資料不見得會群聚為這類形狀,畢竟你應該也看過群聚為橢圓、狹長形狀等的資料。

有種高斯混合模型(Gaussian mixture models)類似K-means,同樣採用最大期望演算,不過,它增加了權重與高斯機率分佈等,來作為資料分群與尋找群心的依據,如此一來,各群的勢力範圍就不會單純是圓或球之類的形狀,甚至可以進行複雜的非線性分群。

綜合來說,K-means的原理雖然簡單,就結果而言是分群沒錯,然而重點在於分析資料是否具備距離的概念,以及分群後各群或群心代表的意義,如此就能衍生出多元化的應用。

作者簡介


熱門新聞

Advertisement