You can add the labels (1 and 2) to the points on the chart shown in Figure 3 as follows. Here cell K4 contains the formula =MIN(L4:M4) and cell O4 contains the formula =IF(L4 Charts|Scatter. Since the squared distance to the second cluster is 12.24 (cell M4) is higher we see that the first data element is closer to cluster 1 and so we keep that point in cluster 1 (cell O4). the squared distance of the first data element to the first centroid is 7.72 (cell L4) as calculated by =(B4-H4)^2+(C4-H5)^2 or equivalently =SUMXMY2($B4:$C4,H$4:H$5). We next calculate the squared distance of each of the ten data elements to each centroid. The centroid for the second cluster (3.2, 3.0) is calculated in a similar way. The centroid of the first cluster is (2.6, 1.4) where the X value (in cell H4) is calculated by the formula =AVERAGEIF(E4:E13,1,B4:B13) and the Y value (in cell H5) is calculated by the worksheet formula =AVERAGEIF(E4:E13,1,C4:C13). We now set the centroids of each cluster to be the mean of all the elements in that cluster. Since there are two clusters, we start by assigning the first element to cluster 1, the second to cluster 2, the third to cluster 1, etc. The data consists of 10 data elements which can be viewed as two-dimensional points (see Figure 3 for a graphical representation). ExampleĮxample 1: Apply the second version of the k-means clustering algorithm to the data in range B3:C13 of Figure 1 with k = 2.įigure 1 – K-means cluster analysis (part 1) By best choice, we mean the choice that minimizes SSE.Ĭlick here for a proof of this property (using calculus). Property 1: The best choice for the centroids c 1, …, c k are the n-tuples which are the means of the C 1, …, C k. There is no guarantee that we will find centroids c 1, …, c k that minimize SSE and a lot depends on our initial choices for the centroids in step 2. If we think of the distance squared between any data element in S and its nearest centroid as an error value (between a data element and its prototype) then across the system we are trying to minimize Where m j is the number of data elements in C j. If we don’t require that the centroids belong to the data set S, then we typically define the new centroid c j for cluster C j in step 4 to be the mean of all the elements in that cluster, i.e. If there are k clusters C 1, …, C k with corresponding centroids c 1, …, c k, then for each data element x in S, step 3 of the k-means algorithm consists of finding the value j which minimizes dist 2( x, c j) i.e. Since minimizing the distance is equivalent to minimizing the square of the distance, we will instead look at dist 2( x, y) = ( dist( x, y)) 2. There are a number of ways to define the distance between two n-tuples in the data set S, but we will focus on the Euclidean measure, namely, if x = ( x 1, …, x n) and y = (y 1, …, y n) then the distance between x and y is defined by Step 4: Based on centroids make a new assignment of data elements to the k clusters.Step 3: For each cluster select its centroid.Step 2: Make an initial assignment of the data elements to the k clusters.There are various choices available for each step in the process.Īn alternative version of the algorithm is as follows: Step 5: Go back to step 3, repeating the process until the centroids don’t change (or some other convergence criterion is met).Step 4: For each cluster make a new selection of its centroid.Step 3: Assign each data element to its nearest centroid (in this way k clusters are formed one for each centroid, where each cluster consists of all the data elements assigned to that centroid).Step 2: Make an initial selection of k centroids.Step 1: Choose the number of clusters k.For each cluster C j, one element c j is chosen from that cluster called a centroid.ĭefinition 1: The basic k-means clustering algorithm is defined as follows: The objective of this algorithm is to partition a data set S consisting of n-tuples of real numbers into k clusters C 1, …, C k in an efficient way.

Find probability using xlstat