k-Means Clustering We'll talk about the cluster analysis algorithm k-means clustering in this course. By the end of this lesson, you should be able to identify the cluster centroid, describe the steps in the k-means method, and explain what the k in k-means stands for. Cluster analysis is a technique that divides samples in a data set into groups or clusters. The goal of cluster analysis is to group similar items in the same cluster where "similar" is defined by some metric that measures the similarity between data samples. The idea is to divide data samples such that samples within a cluster are as close together as possible, and samples from different clusters are as far apart as possible. K-means is a classic algorithm used for cluster analysis. The algorithm is very simple. The first step is to select k initial centroids. A centroid is simply the center of a cluster as you see in the diagram here. Secondly, give each sample in a data set a centroid that is the closest to it. In other words, you measure the separation between each cluster's center and the sample, then you place it in the cluster with the closest centroid. Next, find a new centroid by calculating the mean or average of each cluster. Until a stopping point is achieved, these two stages are repeated. Below is an example showing how k-means functions. A in the diagram shows the original data set with some samples. In b, initial centroids are randomly selected. C shows the first iteration. Here, samples are assigned to the closest centroid. In d, the centroids are re-calculated. E shows the second iteration where samples are assigned to the closest centroid. Notice some samples changed cluster assignments during this step. In f, the centroids are re-calculated again. Cluster assignments and centroid re-calculation are repeated until some stopping criterion is reached, and you get your final clusters as shown in f. Yet, how are the initial centroids chosen? The problem is that initial centroids can affect eventual clusters. As a result, cluster results obtained with one set of initial centroids may not be the same as those obtained with a different set of starting centroids. There are numerous methods with varied degrees of sophistication for choosing the first centroids for k-means. Using k-means repeatedly with various initial centroids chosen at random to cluster your data set is the simplest and most popular strategy. From there, you can choose the centroids that produce the best clustering outcomes. A measure of error called the Within-Cluster Sum of Squared Error (WSSE) can be used to assess the cluster results. The distance between a sample and the cluster centroid determines the error associated with that sample inside the cluster. The square of that distance is thus the sample's squared error. To determine the squared error for a cluster, we add up all the squared errors for all samples in that cluster. In order to obtain the final computation for the Within-Cluster Sum of Squared Error for all clusters in the outcomes of a cluster analysis run, we then repeat the process for all clusters. When two clustering results are shown, the one with the smaller WSSE offers the best numerical answer. However, as we've discussed before, there's no ground truth to mathematically determine which set of clusters is more correct than the other. In addition, note that increasing the number of clusters, that is a value for k, always reduces the WSSE. So WSSE should be used with caution. It only makes sense to use WSSE to compare two sets of clusters with the same value for k and generated from the same data set. Also, the set of clusters with the smallest WSSE may not always be the best solution for the application at hand. Again, interpretation and domain knowledge about what the cluster should represent and how they will be used are crucial in determining which clustering results are best.