畫分勢力範圍的K-means

如果有一組資料，沒有任何事先的分類標記，有辦法對它們進行分群（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的原理雖然簡單，就結果而言是分群沒錯，然而重點在於分析資料是否具備距離的概念，以及分群後各群或群心代表的意義，如此就能衍生出多元化的應用。