Cluster Analysis I Presidency University
September,2016
Classication
I Aim of any multivariate study is to learn about the nature of some object.
Classication
I Aim of any multivariate study is to learn about the nature of some object.
I One way of learning about the nature is to nd out which class the object belongs .
Classication
I Aim of any multivariate study is to learn about the nature of some object.
I One way of learning about the nature is to nd out which class the object belongs .
I For example, a candidate is asked many questions in examination to classify him as either pass or fail.
Classication
I Aim of any multivariate study is to learn about the nature of some object.
I One way of learning about the nature is to nd out which class the object belongs .
I For example, a candidate is asked many questions in examination to classify him as either pass or fail.
I Hence classifying a object is one of the most important issue in multivariate statistics.
Types of classication
Classification
Types of classication
Classification
Supervised
Types of classication
Classification
Supervised
Unsupervised
Supervised vs Unsupervised Learning I Kid trying to learn alphabets.
Supervised vs Unsupervised Learning I Kid trying to learn alphabets. I The english letters are only pictures for him.
Supervised vs Unsupervised Learning I Kid trying to learn alphabets. I The english letters are only pictures for him.
I Teacher tells him the name of each letter.
Supervised vs Unsupervised Learning I Kid trying to learn alphabets. I The english letters are only pictures for him.
I Teacher tells him the name of each letter. I This is supervised classication.
Supervised vs Unsupervised Learning I Suppose the same kid grows up and visits china rst time.
Supervised vs Unsupervised Learning I Suppose the same kid grows up and visits china rst time. I At some place he sees
Supervised vs Unsupervised Learning I Suppose the same kid grows up and visits china rst time. I At some place he sees
I Even now, he cannot read the alphabets.
Supervised vs Unsupervised Learning I Suppose the same kid grows up and visits china rst time. I At some place he sees
I Even now, he cannot read the alphabets. I But at least can identify that some are repeated.
Supervised vs Unsupervised Learning I Suppose the same kid grows up and visits china rst time. I At some place he sees
I Even now, he cannot read the alphabets. I But at least can identify that some are repeated. I Can pick the unique ones.
Supervised vs Unsupervised Learning I Suppose the same kid grows up and visits china rst time. I At some place he sees
I Even now, he cannot read the alphabets. I But at least can identify that some are repeated. I Can pick the unique ones. I This is unsupervised classication.
Supervised vs Unsupervised Learning I Given data x1 , x2 , ....., xn with labels (i.e. group tag)
,
y1 y2
, ....., yn
we learn to predict the label associated with new
input xnew .
Chair
Duck
What is this?
Supervised vs Unsupervised Learning I Given only x1 , x2 , ....., xn , we try to infer some underlying structure (i.e. nd similarities and identifying groups).
Group these items according to common features
Supervised vs Unsupervised Learning
I Discriminant Analysis is supervised classication. I Clustering is Unsupervised classication.
What is clustering? And why?
I Clustering is the task of dividing up data into groups (clusters), so that points in any one group are more similar to each other than to points outside the group
What is clustering? And why?
I Clustering is the task of dividing up data into groups (clusters), so that points in any one group are more similar to each other than to points outside the group Two main uses are :
I Summary: deriving a reduced representation of the full data set.
I Discovery: looking for new insights into the structure of the data. e.g., nding groups of students that commit similar mistakes, or groups of 80's songs that sound alike
Example I Lets have a look at a satellite image
Example I Lets have a look at a satellite image
I The image shows a blue ocean and two land masses with green vegetation.
Example I Lets have a look at a satellite image
I The image shows a blue ocean and two land masses with green vegetation.
I Our human eye can detect large regions of similar colour in an image.
Example I Lets have a look at a satellite image
I The image shows a blue ocean and two land masses with green vegetation.
I Our human eye can detect large regions of similar colour in an image.
I Our brain is performing a simple clustering I It groups the pixels into two clusters: land and sea.
Proximity Measures I Cluster Analysis is the art of grouping similar items.
Proximity Measures I Cluster Analysis is the art of grouping similar items. I How to dene similarity of items?
Proximity Measures I Cluster Analysis is the art of grouping similar items. I How to dene similarity of items? I Usually we dene a dissimilarity measure measure
sij
between xi and xj .
dij
or a similarity
Proximity Measures I Cluster Analysis is the art of grouping similar items. I How to dene similarity of items? I Usually we dene a dissimilarity measure measure
sij
between xi and xj .
dij
or a similarity
dij is taken to be any distance measure, e.g. dij = ||xi − xj ||2
I Generally
Proximity Measures I Cluster Analysis is the art of grouping similar items. I How to dene similarity of items? I Usually we dene a dissimilarity measure measure
sij
between xi and xj .
dij
or a similarity
dij is taken to be any distance measure, e.g. dij = ||xi − xj ||2
I Generally
I This holds good if we are working with variables. I For categorical data, we will discuss the proximity measures later.
Types of Clustering
Clustering
Hierarchical Clustering
Agglomerative
NonHierarchical Clustering
Divisive
Hierarchical Clustering
Consider the four shapes Suppose we want to group the similar objects together.
Hierarchical Clustering
I Possibly put the two cubes in one cluster and the sphere and cone in the other as both have round surfaces.
I So the two clusters are now (sphere, cone) and (small cube, large cube)
Hierarchical Clustering
I Suppose we further split these clusters.
I Then we shall split the (sphere, cone) cluster into (sphere) and (cone) clusters.
Hierarchical Clustering
I If we are to further increase the number we will split the second cluster.
Hierarchical Clustering This step by step clustering process can be expressed using the following diagram:
Agglomerative vs divisive
Agglomerative (i.e., bottom-up):
I Start with all points in their own group I Until there is only one cluster, repeatedly: merge the two groups that have the smallest dissimilarity
Agglomerative vs divisive
Agglomerative (i.e., bottom-up):
I Start with all points in their own group I Until there is only one cluster, repeatedly: merge the two groups that have the smallest dissimilarity Divisive (i.e., top-down):
I Start with all points in one cluster I Until all points are in their own cluster, repeatedly split the group into two resulting in the biggest dissimilarity
Simple Example
Step 1: {1}, {2}, {3}, {4}, {5}, {6}, {7}
Simple Example
Step 2: {1}, {2, 3}, {4}, {5}, {6}, {7};
Simple Example
Step 3: {1, 7}, {2, 3}, {4}, {5}, {6}
Simple Example
Step 4: {1, 7}, {2, 3}, {4, 5}, {6}
Simple Example
Step 5: {1, 7}, {2, 3, 6}, {4, 5}
Simple Example
Step 6: {1, 7}, {2, 3, 6,4, 5}
Simple Example
Step 7: {1, 2, 3, 4, 5, 6, 7}
Simple Example We can simply represent this sequence of clustering assignments in a tree called dendogram.
What's a dendrogram? I Dendrogram is a convenient graphic to display a hierarchical sequence of clustering assignments.
What's a dendrogram? I Dendrogram is a convenient graphic to display a hierarchical sequence of clustering assignments. This is simply a tree where:
I Each node represents a group
What's a dendrogram? I Dendrogram is a convenient graphic to display a hierarchical sequence of clustering assignments. This is simply a tree where:
I Each node represents a group I Each leaf node is a singleton (i.e., a group containing a single data point)
What's a dendrogram? I Dendrogram is a convenient graphic to display a hierarchical sequence of clustering assignments. This is simply a tree where:
I Each node represents a group I Each leaf node is a singleton (i.e., a group containing a single data point)
I Root node is the group containing the whole data set
What's a dendrogram? I Dendrogram is a convenient graphic to display a hierarchical sequence of clustering assignments. This is simply a tree where:
I Each node represents a group I Each leaf node is a singleton (i.e., a group containing a single data point)
I Root node is the group containing the whole data set I Each internal node has two daughter nodes (children), representing the the groups that were merged to form it
What's a dendrogram? I Dendrogram is a convenient graphic to display a hierarchical sequence of clustering assignments. This is simply a tree where:
I Each node represents a group I Each leaf node is a singleton (i.e., a group containing a single data point)
I Root node is the group containing the whole data set I Each internal node has two daughter nodes (children), representing the the groups that were merged to form it
I If we x the leaf nodes at height zero, then each internal node is drawn at a height proportional to the dissmilarity between its two daughter nodes
Cutting a dendogram I Dendogram represents clustering allowing all possible clusters.
Cutting a dendogram I Dendogram represents clustering allowing all possible clusters. I In order to use it, we have to cut it at a particular height.
Cutting a dendogram I Dendogram represents clustering allowing all possible clusters. I In order to use it, we have to cut it at a particular height.
Cutting a dendogram I Dendogram represents clustering allowing all possible clusters. I In order to use it, we have to cut it at a particular height.
I The height at which we cut the dendogram represents the distance which we choose to call dissimilar and practically depends on the number of clusters we want.
Cutting a dendogram I Dendogram represents clustering allowing all possible clusters. I In order to use it, we have to cut it at a particular height.
I The height at which we cut the dendogram represents the distance which we choose to call dissimilar and practically depends on the number of clusters we want.
I Depending on the linkage we use, this cut has its own interpretation, which we will study.
Linkage
I We have studied distances between two data points xi and xj .
Linkage
I We have studied distances between two data points xi and xj . I While performing hierarchical clustering we need to merge the clusters which are similar.
Linkage
I We have studied distances between two data points xi and xj . I While performing hierarchical clustering we need to merge the clusters which are similar.
I This requires a idea of distance among the clusters, what is known as linkage.
Linkage I We are given the data points x1 , x2 , ......, xn and the distance between any pairs xi and xj as
dij .
Linkage I We are given the data points x1 , x2 , ......, xn and the distance between any pairs xi and xj as
dij .
I At any level, clustering assignments can be expressed by sets
G
= {i1 , i2 , ...., inG }
to that group.
giving the indices (
ir ) of points belonging
Linkage I We are given the data points x1 , x2 , ......, xn and the distance between any pairs xi and xj as
dij .
I At any level, clustering assignments can be expressed by sets
G
= {i1 , i2 , ...., inG }
giving the indices (
ir ) of points belonging
to that group.
I At the bottom level the groups are singleton, i.e.
G
= {i }
Linkage I We are given the data points x1 , x2 , ......, xn and the distance between any pairs xi and xj as
dij .
I At any level, clustering assignments can be expressed by sets
G
= {i1 , i2 , ...., inG }
giving the indices (
ir ) of points belonging
to that group.
I At the bottom level the groups are singleton, i.e. I At the topmost level the only one group is
G
= {1, 2, 3, ....., n}.
G
= {i }
Linkage I We are given the data points x1 , x2 , ......, xn and the distance between any pairs xi and xj as
dij .
I At any level, clustering assignments can be expressed by sets
G
= {i1 , i2 , ...., inG }
giving the indices (
ir ) of points belonging
to that group.
I At the bottom level the groups are singleton, i.e.
G
= {i }
I At the topmost level the only one group is
G
= {1, 2, 3, ....., n}.
I Linkage is a function
d (G , H ) that takes two groups G , H
returns a dissimilarity score between them
and
Linkage I We are given the data points x1 , x2 , ......, xn and the distance between any pairs xi and xj as
dij .
I At any level, clustering assignments can be expressed by sets
G
= {i1 , i2 , ...., inG }
giving the indices (
ir ) of points belonging
to that group.
I At the bottom level the groups are singleton, i.e.
G
= {i }
I At the topmost level the only one group is
G
= {1, 2, 3, ....., n}.
I Linkage is a function
d (G , H ) that takes two groups G , H
and
returns a dissimilarity score between them
I Remember: the choice of linkage determines how we measure dissimilarity between groups of points.
Agglomerative Clustering
Given the linkage, agglomerative clustering algorithm consists of the following steps:
Agglomerative Clustering
Given the linkage, agglomerative clustering algorithm consists of the following steps:
I Start with all points in their own group
Agglomerative Clustering
Given the linkage, agglomerative clustering algorithm consists of the following steps:
I Start with all points in their own group I Until there is only one cluster, repeatedly: merge the two groups
G, H
such that
d (G , H ) is smallest
Single Linkage I In single linkage (i.e., nearest-neighbor linkage), the dissimilarity between G, H is the smallest dissimilarity between two points in opposite groups:
dsingle (G , H ) =
min
i ∈G ,j ∈H
dij
Single Linkage
I Single linkage score
dsingle (G , H ) is the distance of the closest
pair.
I Cut interpretation: If we cut the denddogram at height 0.9, then we can say, for each point xi , there is another point xj in its cluster with
dij ≤ 0.9
Complete Linkage I In complete linkage (i.e., farthest-neighbor linkage), dissimilarity between G, H is the largest dissimilarity between two points in opposite groups:
dcomplete (G , H ) =
max
i ∈ G ,j ∈ H
dij
Complete Linkage
I Complete linkage score
dcomplete (G , H ) is the distance of the
farthest pair.
I Cut interpretation: for each point xi , every other point xj in its cluster satises
dij ≤ 0.9
Average Linkage
I In average linkage, the dissimilarity between G, H is the average dissimilarity over all points in opposite groups:
daverage (G , H ) =
1
nH nG
X
i ∈G ,j ∈H
dij
Average Linkage
I In average linkage, the dissimilarity between G, H is the average dissimilarity over all points in opposite groups:
daverage (G , H ) = I average linkage score across all pairs
1
nH nG
X
i ∈G ,j ∈H
dij
daverage (G , H ) is the average distance
Average Linkage
I In average linkage, the dissimilarity between G, H is the average dissimilarity over all points in opposite groups:
daverage (G , H ) = I average linkage score
1
nH nG
X
i ∈G ,j ∈H
dij
daverage (G , H ) is the average distance
across all pairs
I There is not really any good cut interpretation.
Common Properties Single, complete, average linkage share the following properties:
Common Properties Single, complete, average linkage share the following properties:
I These linkages operate on dissimilarities
dij
, and don't need
the points x1 , x2 , .....xn to be in Euclidean space
Common Properties Single, complete, average linkage share the following properties:
I These linkages operate on dissimilarities
dij
, and don't need
the points x1 , x2 , .....xn to be in Euclidean space
I Running agglomerative clustering with any of these linkages produces a dendrogram with no inversions
Common Properties Single, complete, average linkage share the following properties:
I These linkages operate on dissimilarities
dij
, and don't need
the points x1 , x2 , .....xn to be in Euclidean space
I Running agglomerative clustering with any of these linkages produces a dendrogram with no inversions
I Second property can be stated as : disimilarity scores between merged clusers only increases as we run the algorithm
Common Properties Single, complete, average linkage share the following properties:
I These linkages operate on dissimilarities
dij
, and don't need
the points x1 , x2 , .....xn to be in Euclidean space
I Running agglomerative clustering with any of these linkages produces a dendrogram with no inversions
I Second property can be stated as : disimilarity scores between merged clusers only increases as we run the algorithm
I This means that we can draw a proper dendrogram, where the height of a parent is always higher than height of its daughters
Shortcomings of single, complete linkage Single and complete linkage can have some practical problems:
Shortcomings of single, complete linkage Single and complete linkage can have some practical problems:
I Single linkage suers from chaining. In order to merge two groups, only need one pair of points to be close, irrespective of all others. Therefore clusters can be too spread out, and not compact enough
Shortcomings of single, complete linkage Single and complete linkage can have some practical problems:
I Single linkage suers from chaining. In order to merge two groups, only need one pair of points to be close, irrespective of all others. Therefore clusters can be too spread out, and not compact enough
I Complete linkage avoids chaining, but suers from crowding. Because its score is based on the worst-case dissimilarity between pairs, a point can be closer to points in other clusters than to points in its own cluster. Clusters are compact, but not far enough apart
Shortcomings of single, complete linkage Single and complete linkage can have some practical problems:
I Single linkage suers from chaining. In order to merge two groups, only need one pair of points to be close, irrespective of all others. Therefore clusters can be too spread out, and not compact enough
I Complete linkage avoids chaining, but suers from crowding. Because its score is based on the worst-case dissimilarity between pairs, a point can be closer to points in other clusters than to points in its own cluster. Clusters are compact, but not far enough apart
I Average linkage tries to strike a balance. It uses average pairwise dissimilarity, so clusters tend to be relatively compact and relatively far apart
Shortcomings of average linkage
Average linkage isn't perfect, it has its own problems:
Shortcomings of average linkage
Average linkage isn't perfect, it has its own problems:
I It is not clear what properties the resulting clusters have when we cut an average linkage tree at given height
h.
Single and
complete linkage trees each had simple interpretations
Shortcomings of average linkage
Average linkage isn't perfect, it has its own problems:
I It is not clear what properties the resulting clusters have when we cut an average linkage tree at given height
h.
Single and
complete linkage trees each had simple interpretations
I Results of average linkage clustering can change with a
dij . If g g (x ) ≤ g (y ) whenever x ≤ y , and we used dissimilarites h (dij ) instead of dij , then we could get dierent
monotone increasing transformation of dissimilarities is such that
answers
Centroid Linkage I Centroid linkage is commonly used. Let x ¯G , x ¯H denote group averages for
G , H.
Then
dcentroid (G , H ) = d¯xG ¯xH
Centroid Linkage
I Centroid linkage score
dcentroid (G , H ) is the distance between
the group cen- troids (i.e., group averages)
I There is not really any good cut interpretation.
Shortcomings of centroid linkage
I Can produce dendrograms with inversions, which really messes up the visualization
Shortcomings of centroid linkage
I Can produce dendrograms with inversions, which really messes up the visualization
I Even if were we lucky enough to have no inversions, still no interpretation for the clusters resulting from cutting the tree
Shortcomings of centroid linkage
I Can produce dendrograms with inversions, which really messes up the visualization
I Even if were we lucky enough to have no inversions, still no interpretation for the clusters resulting from cutting the tree
I Answers change with a monotone transformation of the dissimilarity measure
Linkages in a nutshell
Linkage
No Inversions?
Single
X X X ×
Complete Average Centroid
Unchanged with monotone transformations?
X X × ×
Cut Interpretation?
Note
X X × ×
Chaining
Crowding
Simple
Linkages in a nutshell
Linkage
No Inversions?
Single
X X X ×
Complete Average Centroid
Unchanged with monotone transformations?
X X × ×
I This doesn't tell us what best linkage is
Cut Interpretation?
Note
X X × ×
Chaining
Crowding
Simple
Linkages in a nutshell
Linkage
No Inversions?
Single
X X X ×
Complete Average Centroid
Unchanged with monotone transformations?
Cut Interpretation?
Note
X X × ×
Chaining
X X × ×
I This doesn't tell us what best linkage is I choosing a linkage can be very situation dependent
Crowding
Simple