K-Means Clustering Presentation Slides for Machine Learning Course

KMeans Lecture Slides.

1. DTS304TC: Machine Learning Lecture 7: K-Means Clustering Dr Kang Dang D-5032, Taicang Campus [email protected] Tel: [phone]

2. Acknowledges This set of lecture notes has been adapted from materials originally provided by Christopher M. Bishop’s and Xin Chen. 2

3. Overview. K-means clustering Application of K-means clustering in image segmentation

4. Q&A What is clustering? What is one application of the clustering? 4

5. Old Faithful Data Set Duration of eruption (minutes) Time between eruptions (minutes)

6. K-means Algorithm Goal: represent a data set in terms of K clusters each of which is summarized by a prototype Initialize prototypes, then iterate between two phases: E-step (Cluster Assignment) : assign each data point to nearest prototype M-step(Prototype update): update prototypes to be the cluster means Simplest version is based on Euclidean distance

7. Responsibilities Responsibilities assign data points to clusters such that Example: 5 data points and 3 clusters n: data point index k: cluster index

8. Q&A We know What does mean? 17

9. K-means Cost Function prototypes responsibilities data

10. Minimizing the Cost Function E-step: minimize w.r.t. assigns each data point to nearest prototype M-step: minimize w.r.t gives each prototype set to the mean of points in that cluster

11. Convergence of K-means Algorithm 20 Will K-Means objective oscillate?

12. Convergence of K-means Algorithm 21 Will K-Means objective oscillate?. The answer is NO. Each iteration of K-means algorithm decrease the objective. Both E step and M step decrease the objective for each data point

13. Convergence of K-means Algorithm 22 Will K-Means objective oscillate?. The answer is NO. Each iteration of K-means algorithm decrease the objective. Both E step and M step decrease the objective for each data point The minimum value of the objective is finite. The minimal value of objective is simply 0

14. Convergence of K-means Algorithm 23 Will K-Means objective oscillate?. The answer is NO. Each iteration of K-means algorithm decrease the objective. Both E step and M step decrease the objective for each data point The minimum value of the objective is finite. The minimal value of objective is simply 0 Therefore K-means algorithm will converge with sufficiently large number of iterations.

15. How to choose K? Plot the within-cluster sum of squares (WCSS) against the number of clusters (k). The WCSS decreases as k increases, but the rate of decrease sharply changes at a certain point, creating an "elbow" in the graph.

16. Application of K-Means Algorithm to Image Segmentation First, we convert all the image pixels to the HSV color space. We then proceed to cluster the image pixels based on their HSV color intensities. Finally, we replace each pixel with the color of its corresponding cluster center.

17. Application of K-Means Algorithm to Image Segmentation Nice Artistic Effects!

18. Limitations of K-means Sensitivity to Initial Centroids: The final results of k-means clustering are sensitive to the initial random selection of cluster centers. This can lead to different results each time k-means is run. For certain initialization, k-means clustering will perform badly. Q&A: How to handle the bad initialization issue?

19. Limitations of K-means Sensitivity to Initial Centroids: The final results of k-means clustering are sensitive to the initial random selection of cluster centers. This can lead to different results each time k-means is run. For certain initialization, k-means clustering will perform badly. Q&A: How to handle the bad initialization issue? Run k-means several times with different random initializations and choose the clustering result with the lowest objective score (lowest within-cluster sum of squares (WCSS))

20. Limitations of K-means Assumption of Spherical Clusters and Equal Variance of Clusters: K-means assumes that clusters are spherical and isotropic, which means all clusters are of the same size (variance) and density Difficulty with Non-convex Shapes

21. Limitations of K means Other limitations: Not clear how to choose the value of K Sensitivity to Outliers Scalability with High Dimensionality GMM can resolve some but not all the above issues. 30