k-meansk-means算法的简单示例算法的简单示例K-means Clustering K-means clustering is a sort of clustering algorithm and it is a method of vector quantization, originally from signal processing, that is popular for cluster analysis in data mining. K-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. -From Wikipedia2 2Algorithm Procedure1.Randomly select K points from complete samples as the initial center.(Thats what k means in K-means)2.Each point in the dataset is assigned to the closed cluster,based upon the Euclidean distance between each point and each cluster center.3.Each clusters center is recomputed as the average of the points in that cluster.4.Iterate step 2 or more until the new center of cluster equals to the original center of cluster or less than a specified threshold,then clustering finished.3 3ABCDEFIGJHExampleHow to cluster A,B.H,J into two clusters? 4 4A(1,4)B(2,4)CDEFIGJHRandomly choose A,B as the centre and K=2.Example0111.412.243.614.475.394.245101.41122.833.614.473.614.24 So,we classify A,C as a cluster and B,E,D,F,G,H,I and J as another cluster.Step 1 and 2.ABCDEFGHIJmeans distance AB5 5A(1,4)B(2,4)CDEFIGJHRandomly choose A,B as the centre and K=2.ExampleStep 3. The new centers of the two clusters are (1,4.5) and (3.75,2.875)6 6cluster 1cluster 2new centerABCDEFIGJH(1,4.5)(3.75,2.875)Example0.51.120.51.121.83.914.725.594.615.322.972.083.482.753.580.911.532.411.892.25Step 2 again. , as the centre and K=2. So,we classify A,B,C,D,E as a cluster and F,G,H,I,J as another cluster.ABCDEFGHIJ7 7ABCDEFIGJH(1,4.5)(3.75,2.875)ExampleStep 3 again. , as the centre and K=2. The new centers of the two clusters are P(1.6,4.8) and Q(4.8,1.6)8 8cluster 2cluster 1new centerABCDEFIGJHP(1.6,4.8)Q(4.8,1.6)Example10.890.630.451.263.694.405.224.495.104.493.695.104.45.220.890.451.2610.63Step 2 again. So,we classify A,B,C,D,E as a cluster and F,G,H,I,J as another cluster.ABCDEFGHIJ9 9ABCDEFIGJHP(1.6,4.8)Q(4.8,1.6)ExampleStep 3 again. The new centers of the two clusters are equal to the original P(1.6,4.8) and Q(4.8,1.6)P , Q as the centre and K=2.1010new centercluster 2cluster 1FinalABCDEFIGJHcluster 1cluster 21111Clustering finished !Disadvantages one of the main disadvantages to k-means is the fact that you must specify the number of clusters(K) as an input to the algorithm.As designed,the algorithm is not capable of determining the appropriate number of clusters and depends upon the user to identify this in advance. K=2K=31212Thank you 结束结束