英文原文：César Souza 本文由@Thomas花園 翻譯并投遞于伯樂在線
K-均值聚類是流行、經(jīng)典、簡單的聚類方法之一。聚類是非監(jiān)督學習的一種方法，也是常用的統(tǒng)計數(shù)據(jù)分析技術(shù)，應用領域很廣，涉及機器學習、數(shù)據(jù)挖掘、模式識別、圖像分析和生物信息學等。
●下載源碼
●下載樣例程序
上面的源碼是Accord.NET Framework的一部分.Accord.NET Framework是一個開發(fā)機器學習，計算機視覺，計算機音頻，統(tǒng)計和數(shù)學應用的框架.它是基于已有的強大AForge.NET Framework開發(fā)的.請參考starting guide了解更多細節(jié).最新的框架包擴了最新的下載源碼并帶有很多其他的統(tǒng)計和機器學習工具(statistics and machine learning tools.).
介紹
在統(tǒng)計和機器學習中， K-均值算法是一種聚類分析方法，它將n個觀察對象分類到k個聚類，每個觀察對象將被分到與均值最接近的聚類中.在其最常見的形式中.K-均值是一種通過反復迭代直至收斂到確定值的迭迭代貪婪算法.
圖解K-均值算法
算法如下:
1)首先為聚類任意選出k個初始化的的質(zhì)心.每個個觀察對象被分類到與質(zhì)心最近的聚類中，
2)接著使用委派的觀察對象聚類的均值重新計算質(zhì)心.
3)用新計算出的質(zhì)心對觀察對象重新聚類如1)那樣分派到與質(zhì)心最近的聚類中.
4)重復2) ， 3)步驟直至聚類質(zhì)心不再變化，或者小于給定的閾值.
(注:意譯，本意請參考原文)
上面是K-均值聚類算法常見的形式。還有其他的改進和拓展的算法，稱作勞合社的算法Lloyd’s algorithm.
勞合社算法
1.把k個點表示被聚類的對象位置，這些點表示相應初始組質(zhì)心
2.分配每個對象到離質(zhì)心最近的組里
3.當所有的對象被分配完后，重新計算k個質(zhì)心的位置
4.重復2，3步驟直到質(zhì)心不再移動.
這些過程將對象分類到不同組，組間的最小化度量可以計算出來
源碼
源碼使用了Accord.NET，而且是框架的一部分.在當前本版(2.1.2) ，如和k-均值算法相關的類在theAccord. MachineLearning空間里
K-均值算法的類圖
KMeans類k-均值算法的主類，算法在用Compute(double[][] data， double threshold)方法實現(xiàn)，Compute輸入是一系列的觀察對象和一個用來決定方法如何結(jié)束的收斂閾值
現(xiàn)實是直接明朗的，沒有使用特別的技術(shù)來避免收斂難題.以后更多的技術(shù)會加入實現(xiàn).所以請為最新修訂的算法源碼下載最新的Accord.NET框架 使用源碼為了使用源碼，創(chuàng)建一個KMeans類新實例，傳遞期望的聚類給構(gòu)造器.另外，你可能傳遞一個距離函數(shù)用來聚類距離度量.默認使用的是平方歐氏距離(square Euclidean distance).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | // Declare some observationsdouble[][] observations ={ new double[] { -5， -2， -1 }，new double[] { -5， -5， -6 }，new double[] { 2， 1， 1 }，new double[] { 1， 1， 2 }，new double[] { 1， 2， 2 }，new double[] { 3， 1， 2 }，new double[] { 11， 5， 4 }，new double[] { 15， 5， 6 }，new double[] { 10， 5， 6 }， };// Create a new K-Means algorithm with 3 clustersKMeans kmeans = new KMeans(3);// Compute the algorithm， retrieving an integer array// containing the labels for each of the observationsint[] labels = kmeans.Compute(observations);// As a result， the first two observations should belong to the// same cluster (thus having the same label). The same should// happen to the next four observations and to the last three. |
樣例應用
在計算機視覺中， K-均值聚類算法通常被用在圖像分割(image segmentation).分割結(jié)果被用來邊界檢測(border detection) 和目標識別(object recognition).樣品應用使用標準平方歐氏距離度量RGB像素顏色空間來分割圖像.然而還有其他更好的距離度量方法來處理圖像分割，如加權(quán)距離其他顏色空間.這里就不列舉在應用中.
原圖(來自Ossi Petruska Flickr page*)
為了展示圖像分割，首先將圖片變換成像素值數(shù)組.圖片會被一個個像素的逐步讀進一個不規(guī)則數(shù)組，數(shù)組的類型的一個長度為三的雙精度浮點數(shù)數(shù)組.每個雙精度浮點數(shù)數(shù)組儲存著范圍在[-1， 1]的3個RGB值.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | ////// Divides the input data into K clusters.///public int[] Compute(double[][] data， double threshold){int k = this.K; int rows = data.Length;int cols = data[0].Length;// pick K unique random indexes in the range 0..n-1int[] idx = Accord.Statistics.Tools.Random(rows， k);// assign centroids from data setthis.centroids = data.Submatrix(idx);// initial variablesint[] count = new int[k]; int[] labels = new int[rows];double[][] newCentroids;do // main loop{ // Reset the centroids and the// cluster member counters'newCentroids = new double[k][];for (int i = 0; i < k; i++) { newCentroids[i] = new double[cols]; count[i] = 0; }// First we will accumulate the data points// into their nearest clusters， storing this// information into the newClusters variable.// For each point in the data set，for (int i = 0; i < data.Length; i++) {// Get the pointdouble[] point = data[i]; // Compute the nearest cluster centroidint c = labels[i] = Nearest(data[i]);// Increase the cluster's sample counter count[c]++;// Accumulate in the corresponding centroiddouble[] centroid = newCentroids[c];for (int j = 0; j < centroid.Length; j++) centroid[j] += point[j]; }// Next we will compute each cluster's new centroid// by dividing the accumulated sums by the number of// samples in each cluster， thus averaging its members.for (int i = 0; i < k; i++) { double[] mean = newCentroids[i];double clusterCount = count[i];for (int j = 0; j < cols; j++) mean[j] /= clusterCount; }// The algorithm stops when there is no further change in// the centroids (difference is less than the threshold).if (centroids.IsEqual(newCentroids， threshold)) break;// go to next generation centroids = newCentroids; } while (true);// Compute cluster information (optional) for (int i = 0; i < k; i++) {// Extract the data for the current clusterdouble[][] sub = data.Submatrix(labels.Find(x => x == i));// Compute the current cluster variancecovariances[i] = Statistics.Tools.Covariance(sub， centroids[i]);// Compute the proportion of samples in the clusterproportions[i] = (double)sub.Length / data.Length; }// Return the classification result return labels;} |
在那個數(shù)組像素值進行聚類后，每個像素有個相關的聚類標簽.標簽的值將會被其相應的聚類質(zhì)心交換.當應用程序的Run按鈕被點擊時，下面的代碼就會被調(diào)用.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | private void btnRun_Click(object sender， EventArgs e){// Retrieve the number of clustersint k = (int)numClusters.Value;// Load original imageBitmap image = Properties.Resources.leaf;// Transform the image into an array of pixel valuesdouble[][] pixels = image.ToDoubleArray();// Create a K-Means algorithm using given k and a// square euclidean distance as distance metric.KMeans kmeans = new KMeans(k， Distance.SquareEuclidean);// Compute the K-Means algorithm until the difference in// cluster centroids between two iterations is below 0.05int[] idx = kmeans.Compute(pixels， 0.05);// Replace every pixel with its corresponding centroidpixels.ApplyInPlace((x， i) => kmeans.Clusters.Centroids[idx[i]]);// Show resulting image in the picture boxpictureBox.Image = pixels.ToBitmap(image.Width， image.Height);} |
在分割后，獲得如下圖片結(jié)果:
圖像標本，在k = 5的K-均值聚類處理后
圖像在k = 10的K-均值聚類處理后
以上樣本圖像已經(jīng)Ossi Petruska的Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Generic授權(quán)
總結(jié)
K-均值聚類是一種非常簡單，流行的聚類方法，.這里展現(xiàn)的樣品實現(xiàn)使用了in Accord.NET框架.就如所見.隨著通過代理函數(shù)或lambda表達式實現(xiàn)的自定義函數(shù)，聚類函數(shù)很容易被拓展.可以用到不同環(huán)境，如圖像分割，而不用過多修改.一個關于改進的建議:正如Charles Elkan.的論文《使用三角不等式加速K-均值算法》（“Using the triangle inequality to accelerate k-means”）所建議聚類方法可以變得更快.
在下一篇文章中，我們將會看到在高斯混合模型怎樣使用K-均值算法來初始化期望-最大算法來評估高斯混合密度.這些文章將會成為連續(xù)致密隱馬爾可夫模型的基礎.
致謝
感謝Antonino Porcino提供了第一個版本的代碼和其有價值的他算法和方法。
參考文獻
●[1] Matteo Matteucci. “Tutorial on Clustering Algorithms，” Politecnico di Milano，http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/kmeans.html(acessed October 4， 2010).
●[2] Teknomo， Kardi. “K-Means Clustering Tutorials，”http://people.revoledu.com/kardi/ tutorial/kMean/(acessed October 6， 2010).
●[3] Wikipedia contributors， “Cluster analysis，”Wikipedia， The Free Encyclopedia，http://en.wikipedia.org/wiki/Cluster_analysis(accessed October 4， 2010).
●[4] Wikipedia contributors， “K-means clustering，”Wikipedia， The Free Encyclopedia，http://en.wikipedia.org/wiki/K-means_clustering(accessed October 4， 2010).
英文原文：César Souza 本文由@Thomas花園 翻譯并投遞于伯樂在線
