K

quasiceo 2016-01-16

展開(kāi)全文

K-均值聚類(lèi)分析

2012/04/17 · IT技術(shù) · 來(lái)源：伯樂(lè)在線(xiàn) · K-均值算法, 數(shù)據(jù)挖掘, 算法

分享到： 14

C++遠(yuǎn)征之多態(tài)篇
python進(jìn)階
Android-Volley詳解
CSS3扁平化風(fēng)格博客

英文原文：César Souza 本文由@Thomas花園翻譯并投遞于伯樂(lè)在線(xiàn)

K-均值聚類(lèi)是流行、經(jīng)典、簡(jiǎn)單的聚類(lèi)方法之一。聚類(lèi)是非監(jiān)督學(xué)習(xí)的一種方法，也是常用的統(tǒng)計(jì)數(shù)據(jù)分析技術(shù)，應(yīng)用領(lǐng)域很廣，涉及機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識(shí)別、圖像分析和生物信息學(xué)等。

●下載源碼

●下載樣例程序

上面的源碼是Accord.NET Framework的一部分.Accord.NET Framework是一個(gè)開(kāi)發(fā)機(jī)器學(xué)習(xí)，計(jì)算機(jī)視覺(jué)，計(jì)算機(jī)音頻，統(tǒng)計(jì)和數(shù)學(xué)應(yīng)用的框架.它是基于已有的強(qiáng)大AForge.NET Framework開(kāi)發(fā)的.請(qǐng)參考starting guide了解更多細(xì)節(jié).最新的框架包擴(kuò)了最新的下載源碼并帶有很多其他的統(tǒng)計(jì)和機(jī)器學(xué)習(xí)工具(statistics and machine learning tools.).

介紹

在統(tǒng)計(jì)和機(jī)器學(xué)習(xí)中， K-均值算法是一種聚類(lèi)分析方法，它將n個(gè)觀察對(duì)象分類(lèi)到k個(gè)聚類(lèi)，每個(gè)觀察對(duì)象將被分到與均值最接近的聚類(lèi)中.在其最常見(jiàn)的形式中.K-均值是一種通過(guò)反復(fù)迭代直至收斂到確定值的迭迭代貪婪算法.

kmeans

圖解K-均值算法

算法如下:

1)首先為聚類(lèi)任意選出k個(gè)初始化的的質(zhì)心.每個(gè)個(gè)觀察對(duì)象被分類(lèi)到與質(zhì)心最近的聚類(lèi)中，

2)接著使用委派的觀察對(duì)象聚類(lèi)的均值重新計(jì)算質(zhì)心.

3)用新計(jì)算出的質(zhì)心對(duì)觀察對(duì)象重新聚類(lèi)如1)那樣分派到與質(zhì)心最近的聚類(lèi)中.

4)重復(fù)2) ， 3)步驟直至聚類(lèi)質(zhì)心不再變化，或者小于給定的閾值.

(注:意譯，本意請(qǐng)參考原文)

上面是K-均值聚類(lèi)算法常見(jiàn)的形式。還有其他的改進(jìn)和拓展的算法，稱(chēng)作勞合社的算法Lloyd’s algorithm.

勞合社算法

1.把k個(gè)點(diǎn)表示被聚類(lèi)的對(duì)象位置，這些點(diǎn)表示相應(yīng)初始組質(zhì)心

2.分配每個(gè)對(duì)象到離質(zhì)心最近的組里

3.當(dāng)所有的對(duì)象被分配完后，重新計(jì)算k個(gè)質(zhì)心的位置

4.重復(fù)2，3步驟直到質(zhì)心不再移動(dòng).

這些過(guò)程將對(duì)象分類(lèi)到不同組，組間的最小化度量可以計(jì)算出來(lái)

源碼

源碼使用了Accord.NET，而且是框架的一部分.在當(dāng)前本版(2.1.2) ，如和k-均值算法相關(guān)的類(lèi)在theAccord. MachineLearning空間里

Class diagram for K-Means

K-均值算法的類(lèi)圖

KMeans類(lèi)k-均值算法的主類(lèi)，算法在用Compute(double[][] data， double threshold)方法實(shí)現(xiàn)，Compute輸入是一系列的觀察對(duì)象和一個(gè)用來(lái)決定方法如何結(jié)束的收斂閾值

現(xiàn)實(shí)是直接明朗的，沒(méi)有使用特別的技術(shù)來(lái)避免收斂難題.以后更多的技術(shù)會(huì)加入實(shí)現(xiàn).所以請(qǐng)為最新修訂的算法源碼下載最新的Accord.NET框架 使用源碼為了使用源碼，創(chuàng)建一個(gè)KMeans類(lèi)新實(shí)例，傳遞期望的聚類(lèi)給構(gòu)造器.另外，你可能傳遞一個(gè)距離函數(shù)用來(lái)聚類(lèi)距離度量.默認(rèn)使用的是平方歐氏距離(square Euclidean distance).

// Declare some observations

double[][] 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 clusters

KMeans kmeans = new KMeans(3);

// Compute the algorithm， retrieving an integer array

// containing the labels for each of the observations

int[] 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.

樣例應(yīng)用

在計(jì)算機(jī)視覺(jué)中， K-均值聚類(lèi)算法通常被用在圖像分割(image segmentation).分割結(jié)果被用來(lái)邊界檢測(cè)(border detection) 和目標(biāo)識(shí)別(object recognition).樣品應(yīng)用使用標(biāo)準(zhǔn)平方歐氏距離度量RGB像素顏色空間來(lái)分割圖像.然而還有其他更好的距離度量方法來(lái)處理圖像分割，如加權(quán)距離其他顏色空間.這里就不列舉在應(yīng)用中.

kmeans1

原圖(來(lái)自Ossi Petruska Flickr page*)

為了展示圖像分割，首先將圖片變換成像素值數(shù)組.圖片會(huì)被一個(gè)個(gè)像素的逐步讀進(jìn)一個(gè)不規(guī)則數(shù)組，數(shù)組的類(lèi)型的一個(gè)長(zhǎng)度為三的雙精度浮點(diǎn)數(shù)數(shù)組.每個(gè)雙精度浮點(diǎn)數(shù)數(shù)組儲(chǔ)存著范圍在[-1， 1]的3個(gè)RGB值.

///

/// 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-1

int[] idx = Accord.Statistics.Tools.Random(rows， k);

// assign centroids from data set

this.centroids = data.Submatrix(idx);

// initial variables

int[] 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 point

double[] point = data[i];

// Compute the nearest cluster centroid

int c = labels[i] = Nearest(data[i]);

// Increase the cluster's sample counter

count[c]++;

// Accumulate in the corresponding centroid

double[] 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 cluster

double[][] sub = data.Submatrix(labels.Find(x => x == i));

// Compute the current cluster variance

covariances[i] = Statistics.Tools.Covariance(sub， centroids[i]);

// Compute the proportion of samples in the cluster

proportions[i] = (double)sub.Length / data.Length;

}

// Return the classification result return labels;

}

在那個(gè)數(shù)組像素值進(jìn)行聚類(lèi)后，每個(gè)像素有個(gè)相關(guān)的聚類(lèi)標(biāo)簽.標(biāo)簽的值將會(huì)被其相應(yīng)的聚類(lèi)質(zhì)心交換.當(dāng)應(yīng)用程序的Run按鈕被點(diǎn)擊時(shí)，下面的代碼就會(huì)被調(diào)用.

private void btnRun_Click(object sender， EventArgs e)

{

// Retrieve the number of clusters

int k = (int)numClusters.Value;

// Load original image

Bitmap image = Properties.Resources.leaf;

// Transform the image into an array of pixel values

double[][] 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.05

int[] idx = kmeans.Compute(pixels， 0.05);

// Replace every pixel with its corresponding centroid

pixels.ApplyInPlace((x， i) => kmeans.Clusters.Centroids[idx[i]]);

// Show resulting image in the picture box

pictureBox.Image = pixels.ToBitmap(image.Width， image.Height);

}

在分割后，獲得如下圖片結(jié)果:

kmeans5

圖像標(biāo)本，在k = 5的K-均值聚類(lèi)處理后

kmeans10

圖像在k = 10的K-均值聚類(lèi)處理后

以上樣本圖像已經(jīng)Ossi Petruska的Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Generic授權(quán)

總結(jié)

K-均值聚類(lèi)是一種非常簡(jiǎn)單，流行的聚類(lèi)方法，.這里展現(xiàn)的樣品實(shí)現(xiàn)使用了in Accord.NET框架.就如所見(jiàn).隨著通過(guò)代理函數(shù)或lambda表達(dá)式實(shí)現(xiàn)的自定義函數(shù)，聚類(lèi)函數(shù)很容易被拓展.可以用到不同環(huán)境，如圖像分割，而不用過(guò)多修改.一個(gè)關(guān)于改進(jìn)的建議:正如Charles Elkan.的論文《使用三角不等式加速K-均值算法》（“Using the triangle inequality to accelerate k-means”）所建議聚類(lèi)方法可以變得更快.

在下一篇文章中，我們將會(huì)看到在高斯混合模型怎樣使用K-均值算法來(lái)初始化期望-最大算法來(lái)評(píng)估高斯混合密度.這些文章將會(huì)成為連續(xù)致密隱馬爾可夫模型的基礎(chǔ).

致謝

感謝Antonino Porcino提供了第一個(gè)版本的代碼和其有價(jià)值的他算法和方法。

參考文獻(xiàn)

●[1] Matteo Matteucci. “Tutorial on Clustering Algorithms，” Politecnico di Milano，http://home.dei./matteucc/Clustering/tutorial_html/kmeans.html(acessed October 4， 2010).

●[2] Teknomo， Kardi. “K-Means Clustering Tutorials，”http://people./kardi/ tutorial/kMean/(acessed October 6， 2010).

●[3] Wikipedia contributors， “Cluster analysis，”Wikipedia， The Free Encyclopedia，http://en./wiki/Cluster_analysis(accessed October 4， 2010).

●[4] Wikipedia contributors， “K-means clustering，”Wikipedia， The Free Encyclopedia，http://en./wiki/K-means_clustering(accessed October 4， 2010).

英文原文：César Souza 本文由@Thomas花園翻譯并投遞于伯樂(lè)在線(xiàn)

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶(hù)發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： quasiceo > 《待分類(lèi)1》

舉報(bào)/認(rèn)領(lǐng)