Hands-On Machine Learning with R: Chapter 20 K-means Clustering
https://bradleyboehmke.github.io/HOML/kmeans.html

University of Michigan - Ann Arbor

K-Means Clustering is a form of unsupervised learning that aims to identify distinct categories in data by segmenting the data by Euclidean Distance into 'k' number of clusters.

K-Means Clustering

How might K-means be used in conjunction with supervised methods to predict on an unlabeled data set?

Dhiraj, K. (2019, August 29). Difference between K-Nearest Neighbor(K-NN) and K-Means Clustering. Medium. [medium.com/@dhiraj8899/difference-between-k-nearest-neighbor-k-nn-and-k-means-clustering-d9a44859182f](https://medium.com/@dhiraj8899/difference-between-k-nearest-neighbor-k-nn-and-k-means-clustering-d9a44859182f) 

Medium: Difference between K-Means and KNN

This reference gets into mathmatical ways how KNN and K-Nearest Neighbors are different concepts

Umamaheswaran, Venkatesh. (2018, November 12). Comprehending K-means and KNN Algorithms. Medium. Retrieved From [becominghuman.ai/comprehending-k-means-and-knn-algorithms-c791be90883d](https://becominghuman.ai/comprehending-k-means-and-knn-algorithms-c791be90883d) 

Math/Python Explanation: Difference Between K-Means and KNN

1. Randomly assign a number, from 1 to K, to each of the observations. These serve as initial cluster assignments for the observations.
2. Iterate until the cluster assignments stop changing:
- (a) For each of the K clusters, compute the cluster centroid. The kth cluster centroid is the vector of the p feature means for the observations in the kth cluster.
- (b) Assign each observation to the cluster whose centroid is closest

Algorithm of K-means Clustering

This picture depicts an example of the K-Means Clustering process. Random data points are selected and serve as the initial clusters. How many there are depends on the value of k, which in this picture’s case, k = 2. It then measures the Euclidean distance between the 1st data point and the two initial clusters, and assigns it to whichever cluster is the closest. It repeats this process, calculates the mean values, and reclusters based on that. The process repeats until the cluster no longer changes (seen in final image).


Image of K-Means Clustering Process

1. Choosing K manually
2. Clustering data of varying sizes and density
3. Clustering outliers
4. Scaling with number of dimensions
5. Quantifying how well a data cluster corresponds to reality

Limitations of K-means clustering

1. Relatively simple to implement
2. Scales to large data sets 
3. Guarantees convergence
4. Can warm-start the positions of centroids
5. Easily adapts to new examples
6. Generalizes to clusters of different shapes and sizes, such as elliptical clusters
7. The principle is relatively simple, the implementation is also very easy, and the convergence speed is fast. 
8. The clustering effect is better. 
9. The interpretability of the algorithm is strong. 
10. The main parameter to be adjusted is only the number of clusters K.

Advantages of K-means clustering

One popular way to determine the optimal number of k is by using the elbow method. To use this method, you will run K means n times, each time adding another cluster. After each iteration you graph a score for that number of k. The point in the graph where there is an “elbow” is the point of optimal clusters. The picture below shows an example graph that would be used for determining the number of clusters -- in this example case 3 clusters is optimal


The Elbow Method for Selecting Optimal K

Hands-On Machine Learning with R: Chapter 20 K-means Clustering

There are two main ways to select the optimal number of clusters ($$k$$) for K-means clustering:

1. **Elbow Method**: Plot the explained variation as a function of the number of clusters and pick the "elbow" of the curve as the number of clusters to use.
2. **Silhouette Score**: Calculated using the silhouette coefficient:
$$\frac{x - y}{\max(x, y)}$$
where $$x$$ is the mean distance to the instances of the next closest cluster, and $$y$$ is the mean distance to the other instances in the same cluster. The $$k$$ value with the highest average silhouette score is selected.

Selecting the Optimal Number of Clusters in K-Means Clustering

If the covariance for each cluster in a Gaussian Mixture Model (GMM) is fixed as $$\sigma^2I$$, then as $$\sigma^2 \to 0$$, the update equations converge to those of K-means clustering.

Learn Before

Related