1 of 30

Clustering: K-means

2 of 30

Supervised vs. Unsupervised Learning

2

Supervised Learning

Unsupervised Learning

Building a model from labeled data

Clustering from unlabeled data

​

​

​

​

3 of 30

Data Clustering

  •  

3

4 of 30

Data Clustering: Similarity

​

​

​

​

​

​

​

​

  • The only information clustering uses is the mutual similarity between samples

​

  • A good clustering is one that achieves:
    • high within-cluster similarity
    • low inter-cluster similarity

​

​

4

5 of 30

K-means: (Iterative) Algorithm

  •  

5

6 of 30

K-means: (Iterative) Algorithm

2) Iteration

​

​

​

​

​

​

​

​

  • Repeat until convergence
    • A possible convergence criteria: cluster centers do not change anymore

6

7 of 30

K-means: (Iterative) Algorithm

  •  

7

8 of 30

 

8

9 of 30

Assigning Points

9

10 of 30

Recomputing the Cluster Centers

10

11 of 30

Assigning Points

11

12 of 30

Recomputing the Cluster Centers

12

13 of 30

Assigning Points

13

14 of 30

Recomputing the Cluster Centers

14

15 of 30

Assigning Points

15

16 of 30

Recomputing the Cluster Centers

16

17 of 30

Summary: K-means Clustering

  • (Iterative) Algorithm

​

17

18 of 30

K-means: Optimization Point of View (Optional)

  •  

18

19 of 30

Expectation Maximization (EM) Algorithm

  •  

19

20 of 30

Python: Data Generation

20

21 of 30

Python: Data Generation and Random Initialization

21

22 of 30

Python: K-Means

22

23 of 30

Python: K-Means in Scikit-learn

23

24 of 30

Initialization Issues

  • k-means is extremely sensitive to cluster center initialization

​

  • Bad initialization can lead to
    • Poor convergence speed
    • Bad overall clustering

​

  • Safeguarding measures:
    • Choose first center as one of the examples, second which is the farthest from the first, third which is the farthest from both, and so on.
    • Try multiple initialization and choose the best result

​

24

25 of 30

Choosing the Number of Clusters

  •  

25

26 of 30

Choosing the Number of Clusters

26

27 of 30

K-means: Limitations

  • Make hard assignments of points to clusters
    • A point either completely belongs to a cluster or not belongs at all
    • No notion of a soft assignment (i.e., probability of being assigned to each cluster)
    • Gaussian mixture model (we will study later) and Fuzzy K-means allow soft assignments

​

  • Sensitive to outlier examples
    • K-medians algorithm is a more robust alternative for data with outliers�

27

28 of 30

K-means: Limitations

  • Works well only for round shaped, and of roughly equal sizes/density cluster

​

  • Does badly if the cluster have non-convex shapes
    • Spectral clustering (we will study later) and Kernelized K-means can be an alternative�

28

29 of 30

K-means: Limitations

  •  

29

30 of 30

K-means: Limitations

  • Clusters with different densities

​

30