K-means slides, K-means annotated, GMM slides, GMM annotated.pdf

K-means clustering

1. CS229: Machine Learning
Clustering:
Grouping
Related Docs
©2022 Carlos Guestrin
CS229: Machine LearningCarlos GuestrinStanford University
Slides include content developed by and co-developed with Emily Fox

2. CS229: Machine Learning
Motivating clustering approaches
©2022 Carlos Guestrin

3. CS229: Machine Learning3
Goal:Structure documents by topic
Discover groups (clusters) of related articles
©2022 Carlos Guestrin
SPORTSWORLD NEWS

4. CS229: Machine Learning4
Why might clustering be useful?
©2022 Carlos Guestrin
I don’t just
like sports!
00.10.20.30.40.50.6
Sports
World NewsEntertainment
Science

5. CS229: Machine Learning
Learn user preferences
©2022 Carlos Guestrin
Cluster 1
Cluster 3Cluster 4
Cluster 2Use feedback
to learn user preferences
over topics
Set of clustered documents read by user

6. CS229: Machine Learning
Clustering: An unsupervised learning task
©2022 Carlos Guestrin

7. CS229: Machine Learning
What if some of the labels are known?
Training set of labeled docs
©2022 Carlos Guestrin
SPORTSWORLD NEWS
ENTERTAINMENTSCIENCE

8. CS229: Machine Learning8
Clustering
No labels provided
…uncover cluster structure
from input alone
Input:docs as vectors xi
Output:cluster labels zi
©2022 Carlos Guestrin
An unsupervised
learning task

9. CS229: Machine Learning9
What defines a cluster?
Assign observation xi(doc) to cluster k (topic label) if
-Score under cluster k is higher than under others
-For simplicity, often define score as distance to cluster center(ignoring shape)
©2022 Carlos Guestrin
Cluster defined by center& shape/spread

10. CS229: Machine Learning10
Hope for unsupervised learning
Easy
Impossible
In between
©2022 Carlos Guestrin

11. CS229: Machine Learning11
Other (challenging!) clusters to discover…
©2022 Carlos Guestrin

12. CS229: Machine Learning12
Other (challenging!) clusters to discover…
©2022 Carlos Guestrin

13. CS229: Machine Learning
k-means: A clustering algorithm
©2022 Carlos Guestrin

14. CS229: Machine Learning14
k-means
Assume
-Score= distance to
cluster center
(smaller better)
©2022 Carlos Guestrin
DATA
to
CLUSTER

15. CS229: Machine Learning15
k-means algorithm
0. Initialize cluster centers
1.Assign observations to
closest cluster center
2.Revise cluster centers as
mean of assigned
observations
3.Repeat 1.+2. until
convergence
©2022 Carlos Guestrin
µ1,µ2,...,µk

16. CS229: Machine Learning16
k-means algorithm
0. Initialize cluster centers
1.Assign observations to
closest cluster center
2.Revise cluster centers as
mean of assigned
observations
3.Repeat 1.+2. until
convergence
©2022 Carlos Guestrin
zi arg min
j
||µj"xi||
2
2
Inferred label for obsi, whereas
supervised learning has given label yi

17. CS229: Machine Learning17
k-means algorithm
0. Initialize cluster centers
1.Assign observations to
closest cluster center
2.Revise cluster centers
as mean of assigned
observations
3.Repeat 1.+2. until
convergence
©2022 Carlos Guestrin
µj=
1
nj
X
i:zi=j
xi

18. CS229: Machine Learning18
k-means algorithm
0. Initialize cluster centers
1.Assign observations to
closest cluster center
2.Revise cluster centers
as mean of assigned
observations
3.Repeat 1.+2. until
convergence
©2022 Carlos Guestrin

19. CS229: Machine Learning20
Why does K-means work???
•What’s k-means optimizing?
•Does it always converge?
©2022 Carlos Guestrin

20. CS229: Machine Learning21
What is k-means optimizing?
•Potential function F(µ,z) of centers µand point
allocations z:
•Optimal k-means:
©2022 Carlos Guestrin

21. CS229: Machine Learning22
Does K-means converge??? Part 1
•Optimize potential function:
min!min"$(&,()=min!min"+
#$%
&
&'!−-()
)
•Fix µand minimize z:
©2022 Carlos Guestrin

22. CS229: Machine Learning23
Does K-means converge??? Part 2
•Optimize potential function:
min!min"$(&,()=min!min"+
#$%
&
&'!−-()
)
•Fix zand minimize µ:
©2022 Carlos Guestrin

23. CS229: Machine Learning24
Coordinate descent algorithms
•Want: minaminbF(a,b)
•Coordinate descent:
-fix a, minimize b
-fix b, minimize a
-repeat
•Converges!!!
-if F is bounded
-to a (often good) local optimum
•as we saw in applet (play with it!)
-(For LASSO it converged to the global
optimum, because of convexity)
•K-means is a coordinate descent algorithm!
©2022 Carlos Guestrin
min!min"$(&,()=min!min"+
#$%
&
&'!−-()
)

24. CS229: Machine Learning
Summary for k-means
©2022 Carlos Guestrin

25. CS229: Machine Learning56
Clustering images
•For search, group as:
-Ocean
-Pink flower
-Dog
-Sunset
-Clouds
-…
©2022 Carlos Guestrin

26. CS229: Machine Learning
Limitations of k-means
©2022 Carlos Guestrin
Assign observations to closest cluster center
Revise cluster centers as mean of assigned
observatvergence
zi arg min
j
||µj"xi||
2
2
Can use weighted Euclidean,
but requires knownweights
Equivalent to assuming
spherically symmetric clusters
Still assumes all clusters have
the same axis-aligned ellipses
Only center matters

27. CS229: Machine Learning
Failure modes of k-means
©2022 Carlos Guestrin
disparate cluster sizesoverlapping clustersdifferent
shaped/oriented
clusters

28. CS229: Machine Learning59
What you can do now…
•Describe the input (unlabeled observations) and output (labels)
of a clustering algorithm
•Determine whether a task is supervised or unsupervised
•Cluster documents using k-means
•Describe potential applications of clustering
©2022 Carlos Guestrin