Foundations of Machine Learning
CentraleSupélec — Fall 2017
12. Clustering
Chloé-Agathe Azencot
Centre for Computational Biology, Mines ParisTech
[Link]@[Link]
Learning objectives
● Explain what clustering algorithms can be used for.
● Explain and implement three different ways to
evaluate clustering algorithms.
● Implement hierarchical clustering, discuss its
various flavors.
● Implement k-means clustering, discuss its
advantages and drawbacks.
● Sketch out a density-based clustering algorithm.
2
Goals of clustering
Group objects that are similar into clusters: classes
that are unknown beforehand.
3
Goals of clustering
Group objects that are similar into clusters: classes
that are unknown beforehand.
4
Goals of clustering
Group objects that are similar into clusters: classes
that are unknown beforehand.
E.g.
– group genes that are similarly affected by a disease
– group patients whose genes respond similarly to a
disease
– group pixels in an image that belong to the same object
(image segmentation).
5
Applications of clustering
● Understand general characteristics of the data
● Visualize the data
● Infer some properties of a data point based on how
it relates to other data points
E.g.
– find subtypes of diseases
– visualize protein families
– find categories among images
– find patterns in financial transactions
– detect communities in social networks
6
Distances and similarities
7
Distances & similarities
● Assess how close / far
– data points are from each other
– a data point is from a cluster
– two clusters are from each other
● Distance metric
8
Distances & similarities
● Assess how close / far
– data points are from each other
– a data point is from a cluster
– two clusters are from each other
● Distance metric
symmetry
triangle inequality
● E.g. Lq distances
9
Distance & similarities
● How do we get similarities?
10
Distance & similarities
● Transform distances into similarities?
● Kernels define similarities
For a given mapping
from the space of objects X to some Hilbert space H, the
kernel between two objects x and x' is the inner product
of their images in the feature spaces.
11
Pearson's correlation
● Measure of the linear correlation
between two variables
● If the features are centered: ?
12
Pearson's correlation
● Measure of the linear correlation
between two variables
● If the features are centered:
● Normalized dot product = cosine
13
Pearson vs Euclide
● Pearson's coefficient
Profiles of similar shapes will be close to each other,
even if they differ in magnitude.
● Euclidean distance
Magnitude is taken into account.
14
Pearson vs Euclide
15
Evaluating clusters
16
Evaluating clusters
● Clustering is unsupervised.
● There is no ground truth. How do we evaluate the
quality of a clustering algorithm?
17
Evaluating clusters
● Clustering is unsupervised.
● There is no ground truth. How do we evaluate the
quality of a clustering algorithm?
● 1) Based on the shape of the clusters:
Points within the same cluster should be nearby/similar
and points far from each other should belong to
different clusters.
● Based on the stability of the clusters:
We should get the same results if we remove some data
points, add noise, etc.
● Based on domain knowledge:
The clusters should “make sense”.
18
Evaluating clusters
● Clustering is unsupervised.
● There is no ground truth. How do we evaluate the
quality of a clustering algorithm?
● 1) Based on the shape of the clusters:
Points within the same cluster should be nearby/similar
and points far from each other should belong to
different clusters.
● Based on the stability of the clusters:
We should get the same results if we remove some data
points, add noise, etc.
● Based on domain knowledge:
The clusters should “make sense”.
19
Centroids and medoids
● Centroid: mean of the points in the cluster.
● Medoid: point in the cluster that is closest to the
centroid.
20
Cluster shape: Tightness
vs
21
Cluster shape: Tightness
Tk
22
Cluster shape: Separability
vs
23
Cluster shape: Separability
Skl
24
Clusters shape: Davies-Bouldin
● Cluster tightness (homogeneity)
Tk
● Cluster separation
Skl
● Davies-Bouldin index
25
Clusters shape: Silhouete coefficient
● how well x fits in its
cluster:
● how well x would fit in
another cluster:
● if x is very close to the other
points of its cluster: s(x) = 1
● if x is very close to the points
in another cluster: s(x) = -1
26
Evaluating clusters
● Clustering is unsupervised.
● There is no ground truth. How do we evaluate the
quality of a clustering algorithm?
● 1) Based on the shape of the clusters:
Points within the same cluster should be nearby/similar
and points far from each other should belong to
different clusters.
● 2) Based on the stability of the clusters:
We should get the same results if we remove some data
points, add noise, etc.
● Based on domain knowledge:
The clusters should “make sense”.
27
Cluster stability
● How many clusters?
28
Cluster stability
● K=2
● K=3
29
Cluster stability
● K=2
● K=3
30
Evaluating clusters
● Clustering is unsupervised.
● There is no ground truth. How do we evaluate the
quality of a clustering algorithm?
● 1) Based on the shape of the clusters:
Points within the same cluster should be nearby/similar
and points far from each other should belong to
different clusters.
● 2) Based on the stability of the clusters:
We should get the same results if we remove some data
points, add noise, etc.
● 3) Based on domain knowledge:
The clusters should “make sense”.
31
Domain knowledge
● Do the cluster match natural categories?
– Check with human expertise
32
Ontology enrichment analysis
● Ontology:
Entities may be grouped, related within a hierarchy, and
subdivided according to similarities and differences.
Build by human experts
● E.g.: The Gene Ontology
[Link]
– Describe genes with a common vocabulary, organized in
categories
E.g. cellular process > cell death > programmed cell death >
apoptotic process > execution phase of apoptosis
33
Ontology enrichment analysis
● Enrichment analysis:
Are there more data points from ontology category G in
cluster C than expected by chance?
● TANGO [Tanay et al., 2003]
– Assume data points sampled from a hypergeometric
distribution
– The probability for the intersection of G and C to contain
more than t points is:
34
Ontology enrichment analysis
● Enrichment analysis:
Are there more data points from ontology category G in
cluster C than expected by chance?
● TANGO [Tanay et al., 2003]
– Assume data points sampled from a hypergeometric
distribution
– The probability for the intersection of G and C to contain
more than t points is:
Probability of getting i points from G
when drawing |C| points from a
total of n samples.
35
Hierarchical clustering
36
Hierachical clustering
Group data over a variety of possible scales, in a
multi-level hierarchy.
37
Construction
● Agglomerative approach (botom-up)
Start with each element in its own cluster
Iteratively join neighboring clusters.
● Divisive approach (top-down)
Start with all elements in the same cluster
Iteratively separate into smaller clusters.
38
Dendogram
● The results of a hierarchical clustering algorithm are
presented in a dendogram.
● Branch length = cluster distance.
39
Dendogram
● The results of a hierarchical clustering algorithm are
presented in a dendogram.
● U height = distance.
How many clusters?
?
40
Dendogram
● The results of a hierarchical clustering algorithm are
presented in a dendogram.
● U height = distance.
1 2 3 4
41
Linkage: connecting two clusters
● Single linkage
42
Linkage: connecting two clusters
● Complete linkage
43
Linkage: connecting two clusters
● Average linkage
44
Linkage: connecting two clusters
● Centroid linkage
45
Linkage: connecting two clusters
● Ward
Join clusters so as to minimize within-cluster variance
46
Example: Gene expression clustering
Breast cancer survival signature
[Bergamashi et al. 2011]
1
genes
1 patients 2
47
Hierarchical clustering
● Advantages
– No need to pre-define the number of clusters
– Interpretability
● Drawbacks
– Computational complexity ?
48
Hierarchical clustering
● Advantages
– No need to pre-define the number of clusters
– Interpretability
● Drawbacks
– Computational complexity
E.g. Single/complete linkage (naive):
At least O(pn²) to compute all pairwise distances.
– Must decide at which level of the hierarchy to split
– Lack of robustness (unstable)
49
K-means
50
K-means clustering
● Minimize the intra-cluster variance
● What will this partition of the space look like?
51
K-means clustering
● Minimize the intra-cluster variance
● For each cluster, the points in that cluster are those
that are closest to its centroid than to any other
centroid
52
K-means clustering
● Minimize the intra-cluster variance
● Voronoi tesselation
53
Lloyd's algorithm
● K-means cannot be easily optimized
● We adopt a greedy strategy.
– Partition the data into K clusters at random
– Compute the centroid of each cluster
– Assign each point to the cluster whose centroid it is
closest to
– Repeat until cluster membership converges.
54
K-means
● Advantages
– What is the computational time of k-means?
55
K-means
● Advantages
– What is the computational time of k-means?
number of iterations
compute kn distances
in p dimensions Can be small if there's
indeed a cluster
structure in the data
56
K-means
● Advantages
– Computational time is linear
– Easily implementable
● Drawbacks
– Need to set up K ahead of time
– What happens when there are outliers?
57
K-means
● Advantages
– Computational time is linear
– Easily implementable
● Drawbacks
– Need to set up K ahead of time
– Sensitive to noise and outliers
– Stochastic (different solutions with each iteration)
– The clusters are forced to have convex shapes
58
K-means variants
● K-means++
– Seeding algorithm to initialize clusters with centroids
“spread-out” throughout the data.
– Deterministic
● K-medoids
● Kernel k-means
Find clusters in feature space
k-means kernel k-means
59
Density-based clustering
60
Density-based clustering
61
Hierarchical clustering:
[Link](linkage='average',
n_clusters=3)
62
k-means clustering
[Link](n_clusters=3)
63
DBSCAN
● Density-based clustering: clusters are made of
dense neighborhoods of points
64
DBSCAN
● ε-neighborhood:
● core points:
● x and z are density-connected:
core points such that
●
65
Summary
● Clustering: unsupervised approach to group similar data
points together.
● Evaluate clustering algorithms based on
– the shape of the cluster
– the stability of the results
– the consistency with domain knowledge.
● Hierarchical clustering
– top-down / bottom-up
– various linkage functions.
● k-means clustering tries to minimize intra-cluster variance
● density-based clustering clusters dense neighborhoods
together.
66
References
● Introduction to Data Mining
P. Tang, M. Steinbach, V. Kumar
Chap. 8: Cluster analysis
[Link]
67