Clustering by k-means

應用在生物資訊的分群(clustering)的方法中，k-means演算法可以算是最普遍且簡單的趨近方法了，像是開放原始碼的資料探勘與機器學習的套件weka就有實作了簡單的k-means演算法，另外舉個顯而易見的例子，作微陣列分析(microarray analysis)時，通常就是使用k-means演算法來將基因作初步的分群。

k-means詳細的演算法如下：首先起始條件是輸入欲分類的資料n個樣本，以及需求的中心數c。便能起產生c個所需求中心數。接著將n指配給距離最近的中心，當全部的n都分完後，再重新計算各個中心，也就是取歸在該樣本群中的平均值，即為新的中心點，如此反覆做下去，直到滿足收斂條件為止。此外，樣本與分群中心的距離有相當多種的算法，最基本的作法就是計算歐幾里得度量(Euclidean distance)。

由上述的作法可以理解到k-means演算法是種Unsupervised learning的方法，他的作法簡單的說就是將資料集中的每個樣本分給離該樣本距離最近的中心(center or centroid)，每個中心即為距離該中心最近的樣本的平均所組成，而且可以藉由改良衡量距離的函式就可以達到改善的效果。k-means有著簡單的計算與快速收斂的優點，但缺點是分群的中心相當易受起始點的影響，也就是通常只能尋找到區域的最佳解，但這點可以藉由引入模糊(fuzzy)的概念來加以改善。

參考文獻

K-means algorithm From Wikipedia, the free encyclopedia

Pattern Classification (2nd Edition) p562-p568

--

這是最近某個作業所寫的報告的一部份，主題是介紹k-means演算法並完成了一個實作k-means的C++程式，就將內文摘錄的一部份改修了一下並貼了上來，應該不會有人想要我的程式碼來看吧XD。