Data Mining Cluster Analysis: Basic Concepts and Algorithms Lecture Notes for Chapter 7 Introduction to Data Mining, 2nd Edition by Tan, Steinbach, Karpatne, Kumar 02/14/2018 Introduction to Data Mining, 2nd Edition 1 Strengths of Hierarchical Clustering Do not have to assume any particular number of clusters Any desired number of clusters can be obtained by cutting the dendrogram at the proper level They may correspond to meaningful taxonomies Example in biological sciences (e.g., animal kingdom, phylogeny reconstruction, ) 02/14/2018 Introduction to Data Mining, 2nd Edition 2 Hierarchical Clustering Two main types of hierarchical clustering Agglomerative: Start with the points as individual clusters

At each step, merge the closest pair of clusters until only one cluster (or k clusters) left Divisive: Start with one, all-inclusive cluster At each step, split a cluster until each cluster contains an individual point (or there are k clusters) Traditional hierarchical algorithms use a similarity or distance matrix Merge or split one cluster at a time 02/14/2018 Introduction to Data Mining, 2nd Edition 3 Agglomerative Clustering Algorithm Most popular hierarchical clustering technique Basic algorithm is straightforward 1. 2. 3. 4. 5. 6.

Compute the proximity matrix Let each data point be a cluster Repeat Merge the two closest clusters Update the proximity matrix Until only a single cluster remains Key operation is the computation of the proximity of two clusters 02/14/2018 Different approaches to defining the distance between clusters distinguish the different algorithms Introduction to Data Mining, 2nd Edition 4 Starting Situation Start with clusters of individual points and a proximity matrix p1 p2 p3 p4 p5 ... p1 p2 p3 p4 p5 . . Proximity Matrix

. ... p1 02/14/2018 p2 Introduction to Data Mining, 2nd Edition p3 p4 p9 p10 5 p11 p12 Intermediate Situation After some merging steps, we have some clusters C1 C2 C3 C4 C5 C1 C2 C3

C3 C4 C4 C5 Proximity Matrix C1 C2 C5 ... p1 02/14/2018 p2 Introduction to Data Mining, 2nd Edition p3 p4 p9 p10 6 p11 p12 Intermediate Situation We want to merge the two closest clusters (C2 and C5) and update the proximity matrix.

C1 C2 C3 C4 C5 C1 C2 C3 C3 C4 C4 C5 Proximity Matrix C1 C2 C5 ... p1 02/14/2018 p2 Introduction to Data Mining, 2nd Edition p3 p4 p9 p10 7 p11

p12 After Merging The question is How do we update the proximity matrix? C1 C1 C4 C3 C4 ? ? ? ? C2 U C5 C3 C2 U C5 ? C3 ? C4 ? Proximity Matrix C1

C2 U C5 ... p1 02/14/2018 p2 Introduction to Data Mining, 2nd Edition p3 p4 p9 p10 8 p11 p12 How to Define Inter-Cluster Distance p1 Similarity? p2 p3 p4 p5 p1 p2 p3 p4

p5 MIN . MAX . Group Average . Proximity Matrix Distance Between Centroids Other methods driven by an objective function Wards Method uses squared error 02/14/2018 Introduction to Data Mining, 2nd Edition 9 ... How to Define Inter-Cluster Similarity p1 p2 p3 p4 p5 p1 p2 p3 p4

p5 MIN . MAX . Group Average . Proximity Matrix Distance Between Centroids Other methods driven by an objective function Wards Method uses squared error 02/14/2018 Introduction to Data Mining, 2nd Edition 10 ... How to Define Inter-Cluster Similarity p1 p2 p3 p4 p5 p1 p2 p3 p4

p5 MIN . MAX . Group Average . Proximity Matrix Distance Between Centroids Other methods driven by an objective function Wards Method uses squared error 02/14/2018 Introduction to Data Mining, 2nd Edition 11 ... How to Define Inter-Cluster Similarity p1 p2 p3 p4 p5 p1 p2 p3 p4

p5 MIN . MAX . Group Average . Proximity Matrix Distance Between Centroids Other methods driven by an objective function Wards Method uses squared error 02/14/2018 Introduction to Data Mining, 2nd Edition 12 ... How to Define Inter-Cluster Similarity p1 p2 p3 p4 p5 p1 p2 p3 p4

p5 MIN . MAX . Group Average . Proximity Matrix Distance Between Centroids Other methods driven by an objective function Wards Method uses squared error 02/14/2018 Introduction to Data Mining, 2nd Edition 13 ... MIN or Single Link Proximity of two clusters is based on the two closest points in the different clusters Determined by one pair of points, i.e., by one link in the proximity graph Example: Distance Matrix: 02/14/2018 Introduction to Data Mining, 2nd Edition

14 Hierarchical Clustering: MIN 1 3 5 5 0.2 2 1 2 3 4 4 0.15 6 0.1 0.05 0 3 Nested Clusters 02/14/2018 Introduction to Data Mining, 2nd Edition

6 2 5 4 Dendrogram 15 1 Strength of MIN Original Points Six Clusters Can handle non-elliptical shapes 02/14/2018 Introduction to Data Mining, 2nd Edition 16 Limitations of MIN Two Clusters Original Points Sensitive to noise and outliers 02/14/2018 Three Clusters Introduction to Data Mining, 2nd Edition 17 MAX or Complete Linkage

Proximity of two clusters is based on the two most distant points in the different clusters Determined by all pairs of points in the two clusters Distance Matrix: 02/14/2018 Introduction to Data Mining, 2nd Edition 18 Hierarchical Clustering: MAX 4 1 2 5 0.4 0.35 5 2 0.3 0.25 3 3 6 1 4 0.2

0.15 0.1 0.05 0 Nested Clusters 02/14/2018 Introduction to Data Mining, 2nd Edition 3 6 4 1 2 Dendrogram 19 5 Strength of MAX Original Points Two Clusters Less susceptible to noise and outliers 02/14/2018 Introduction to Data Mining, 2nd Edition 20 Limitations of MAX Original Points

Two Clusters Tends to break large clusters Biased towards globular clusters 02/14/2018 Introduction to Data Mining, 2nd Edition 21 Group Average Proximity of two clusters is the average of pairwise proximity between points in the two clusters. proximity(p ,p ) i j piClusteri pjClusterj proximity( Cluster i , Cluster j) |Clusteri | |Clusterj | Need to use average connectivity for scalability since total proximity favors large clusters Distance Matrix: 02/14/2018 Introduction to Data Mining, 2nd Edition 22 Hierarchical Clustering: Group

Average 5 4 1 2 5 0.25 0.2 2 0.15 3 6 1 4 3 0.1 0.05 0 3 Nested Clusters 02/14/2018 Introduction to Data Mining, 2nd Edition 6 4

1 2 5 Dendrogram 23 Hierarchical Clustering: Group Average Compromise between Single and Complete Link Strengths Less susceptible to noise and outliers Limitations Biased towards globular clusters 02/14/2018 Introduction to Data Mining, 2nd Edition 24 Cluster Similarity: Wards Method Similarity of two clusters is based on the increase in squared error when two clusters are merged Similar to group average if distance between points is distance squared

Less susceptible to noise and outliers Biased towards globular clusters Hierarchical analogue of K-means Can be used to initialize K-means 02/14/2018 Introduction to Data Mining, 2nd Edition 25 Hierarchical Clustering: Comparison 1 3 5 5 1 2 3 6 MIN MAX 5 02/14/2018 2 6

1 4 5 5 Wards Method 2 3 3 3 3 2 4 5 4 1 5 1 2 2 4 4 6 4 1

2 5 2 Group Average 3 1 1 4 4 Introduction to Data Mining, 2nd Edition 6 3 26 MST: Divisive Hierarchical Clustering Build MST (Minimum Spanning Tree) https://en.wikipedia.org/wiki/Minimum_spanning_tree Start with a tree that consists of any point Create subclusters by breaking links in the minimum spanning tree 02/14/2018 Introduction to Data Mining, 2nd Edition 27 MST: Divisive Hierarchical

Clustering Use MST for constructing hierarchy of clusters 02/14/2018 Introduction to Data Mining, 2nd Edition 28 Hierarchical Clustering: Time and Space requirements O(N2) space since it uses the proximity matrix. N is the number of points. O(N3) time in many cases There are N steps and at each step the size, N2, proximity matrix must be updated and searched Complexity can be reduced to O(N2 log(N) ) time with some cleverness 02/14/2018 Introduction to Data Mining, 2nd Edition 29 Hierarchical Clustering: Problems and Limitations Once a decision is made to combine two clusters, it cannot be undone No global objective function is directly minimized

Different schemes have problems with one or more of the following: Sensitivity to noise and outliers Difficulty handling clusters of different sizes and nonglobular shapes Breaking large clusters 02/14/2018 Introduction to Data Mining, 2nd Edition 30 Measures of Cluster Validity Numerical measures that are applied to judge various aspects of cluster validity, are classified into the following three types. External Index: Used to measure the extent to which cluster labels match externally supplied class labels. Entropy Internal Index: Used to measure the goodness of a clustering structure without respect to external information. Sum of Squared Error (SSE) Relative Index: Used to compare two different clusterings or clusters. Often an external or internal index is used for this function, e.g., SSE or entropy Sometimes these are referred to as criteria instead of indices However, sometimes criterion is the general strategy and index is the numerical measure that implements the criterion.

02/14/2018 Introduction to Data Mining, 2nd Edition 31 Measuring Cluster Validity Via Correlation Two matrices Proximity Matrix measuring distance Ideal Similarity Matrix One row and one column for each data point An entry is 1 if the associated pair of points belong to the same cluster An entry is 0 if the associated pair of points belongs to different clusters Compute the correlation between the two matrices Since the matrices are symmetric, only the correlation between n(n-1) / 2 entries needs to be calculated.

High correlation indicates that points that belong to the same cluster are close to each other. Not a good measure for some density or contiguity based clusters. 02/14/2018 Introduction to Data Mining, 2nd Edition 32 Measuring Cluster Validity Via Correlation Correlation of ideal similarity and proximity matrices for the K-means clusterings of the following two data sets. 1 1 0.9 0.9 0.8 0.8 0.7 0.7 0.6 0.6 0.5 0.5 y y

0.4 0.4 0.3 0.3 0.2 0.2 0.1 0.1 0 0 0.2 0.4 0.6 0.8 1 0 0 0.2 x Corr = -0.9235 02/14/2018

0.4 0.6 0.8 1 x Corr = -0.5810 Introduction to Data Mining, 2nd Edition 33 Using Similarity Matrix for Cluster Validation Order the similarity matrix with respect to cluster labels and inspect visually. 1 1 0.9 0.8 0.7 Points y 0.6 0.5 0.4 0.3 0.2 0.1 0 10

0.9 20 0.8 30 0.7 40 0.6 50 0.5 60 0.4 70 0.3 80 0.2 90 0.1 100 0 0.2 0.4 0.6

0.8 1 20 x 02/14/2018 Introduction to Data Mining, 2nd Edition 40 60 Points 80 0 100 Similarity 34 Using Similarity Matrix for Cluster Validation Clusters in random data are not so crisp 1 10 0.9 0.9 20 0.8

0.8 30 0.7 0.7 40 0.6 0.6 50 0.5 0.5 60 0.4 0.4 70 0.3 0.3 80 0.2 0.2 90 0.1 0.1

100 20 40 60 Points 80 0 100 Similarity y Points 1 0 0 0.2 0.4 0.6 0.8 1 x DBSCAN 02/14/2018 Introduction to Data Mining, 2nd Edition

35 Using Similarity Matrix for Cluster Validation Clusters in random data are not so crisp 1 10 0.9 0.9 20 0.8 0.8 30 0.7 0.7 40 0.6 0.6 50 0.5 0.5 60 0.4

0.4 70 0.3 0.3 80 0.2 0.2 90 0.1 0.1 100 20 40 60 Points 80 0 100 Similarity y Points 1 0

0 0.2 0.4 0.6 0.8 1 x K-means 02/14/2018 Introduction to Data Mining, 2nd Edition 36 Using Similarity Matrix for Cluster Validation Clusters in random data are not so crisp 1 10 0.9 0.9 20 0.8 0.8 30

0.7 0.7 40 0.6 0.6 50 0.5 0.5 60 0.4 0.4 70 0.3 0.3 80 0.2 0.2 90 0.1 0.1 100

20 40 60 Points 80 0 100 Similarity y Points 1 0 0 0.2 0.4 0.6 0.8 1 x Complete Link 02/14/2018 Introduction to Data Mining, 2nd Edition 37

Using Similarity Matrix for Cluster Validation 1 0.9 500 1 2 0.8 6 0.7 1000 4 3 0.6 1500 0.5 0.4 2000 0.3 5 0.2 2500 0.1 7 3000

500 1000 1500 2000 2500 DBSCAN 02/14/2018 Introduction to Data Mining, 2nd Edition 38 3000 0 Internal Measures: SSE Clusters in more complicated figures arent well separated Internal Index: Used to measure the goodness of a clustering structure without respect to external information SSE SSE is good for comparing two clusterings or two clusters (average SSE). Can also be used to estimate the number of clusters 10 9

6 8 4 7 6 SSE 2 0 5 4 -2 3 2 -4 1 -6 0 5 02/14/2018 10 15 Introduction to Data Mining, 2nd Edition 2 5 10

15 20 25 K 39 30 Internal Measures: Cohesion and Separation Cluster Cohesion: Measures how closely related are objects in a cluster Example: SSE Cluster Separation: Measure how distinct or wellseparated a cluster is from other clusters Example: Squared Error Cohesion is measured by the within cluster sum of squares (SSE) SSE WSS ( x mi ) 2 i xCi Separation is measured by the between cluster sum of squares BSS Ci (m mi ) 2 i 02/14/2018 Introduction Where |Ci| istothe

size of cluster i Data Mining, 2nd Edition 40 Internal Measures: Cohesion and Separation Example: SSE BSS + WSS = constant m 1 m1 K=1 cluster: 2 3 4 m2 5 SSE WSS(1 3) 2 ( 2 3) 2 ( 4 3) 2 (5 3) 2 10 BSS4 (3 3) 2 0 Total 10 0 10 K=2 clusters: SSE WSS(1 1.5) 2 (2 1.5) 2 ( 4 4.5)2 (5 4.5) 2 1 BSS2 (3 1.5)2 2 (4.5 3)2 9

Total 1 9 10 02/14/2018 Introduction to Data Mining, 2nd Edition 41 Internal Measures: Cohesion and Separation A proximity graph based approach can also be used for cohesion and separation. Cluster cohesion is the sum of the weight of all links within a cluster. Cluster separation is the sum of the weights between nodes in the cluster and nodes outside the cluster. cohesion 02/14/2018 separation Introduction to Data Mining, 2nd Edition 42 Quite popular! Internal Measures: Silhouette Coefficient Silhouette coefficient combines ideas of both cohesion and separation, but for individual points, as well as clusters and clusterings For an individual point, i Calculate a = average distance of i to the points in its cluster Calculate b = min (average distance of i to points in another cluster) The silhouette coefficient for a point is then given by s = (b a) / max(a,b) i Typically between 0 and 1. The closer to 1 the better.

Distances used to calculate b Distances used to calculate a Can calculate the average silhouette coefficient for a cluster or a clustering 02/14/2018 Introduction to Data Mining, 2nd Edition 43 External Measures of Cluster Validity: Entropy and Purity 02/14/2018 Introduction to Data Mining, 2nd Edition 44 Final Comment on Cluster Validity The validation of clustering structures is the most difficult and frustrating part of cluster analysis. Without a strong effort in this direction, cluster analysis will remain a black art accessible only to those true believers who have experience and great courage. Algorithms for Clustering Data, Jain and Dubes 02/14/2018 Introduction to Data Mining, 2nd Edition 45