Hierachical clustering

Hierachical clustering

1. Tilani Gunawardena Algorithms: Clustering

2. Grouping of records ,observations or cases into classes of similar objects. A cluster is a collection of records, Similar to one another Dissimilar to records in other clusters What is Clustering?

3. Clustering

4. Clustering

5. There is no target variable for clustering Clustering does not try to classify or predict the values of a target variable. Instead, clustering algorithms seek to segment the entire data set into relatively homogeneous subgroups or clusters, Where the similarity of the records within the cluster is maximized , and Similarity to records outside this cluster is minimized . Difference between Clustering and Classification

6. Identification of groups f records such that similarity within a group is very high while the similarity to records in other groups is very low. group data points that are close (or similar ) to each other identify such groupings (or clusters) in an unsupervised manner Unsupervised: no information is provided to the algorithm on which data points belong to which clusters In other words, Clustering algorithm seeks to construct clusters of records such that the between-cluster variation (BCV) is large compared to the within-cluster variation (WCV) Goal of Clustering

7. Between-cluster variation: Within-cluster variation: Goal of Clustering between-cluster variation (BCV) is large compared to the within-cluster variation (WCV) (Intra-cluster distance) the sum of distances between objects in the same cluster are minimized ( Inter-cluster distance) while the distances between different clusters are maximized

8. Clustering techniques apply when there is no class to be predicted As we've seen clusters can be: disjoint vs. overlapping deterministic vs. probabilistic flat vs. hierarchical k - means Algorithm k -means clusters are disjoint, deterministic, and flat Clustering

9. Inter/Intra Cluster Distances Intra-cluster distance (Sum/Min/Max/Avg) the (absolute/squared) distance between All pairs of points in the cluster OR Between the centroid and all points in the cluster OR Between the “ medoid ” and all points in the cluster Inter-cluster distance Sum the (squared) distance between all pairs of clusters Where distance between two clusters is defined as: distance between their centroids/medoids (Spherical clusters) Distance between the closest pair of points belonging to the clusters (Chain shaped clusters)

10. Issues Related to Clustering How to measure similarity Euclidian Distance City -block Distance Minkowski Distance How to recode categorical variables ? How to standardize or normalize numerical variables? Min -Max Normalization Z -score standardization ( ) How many clusters we expect to uncover?

11. Type of Clustering Partitional clustering: Partitional algorithms determine all clusters at once. They include: K -Means Clustering Fuzzy c-means clustering QT clustering Hierarchical Clustering: Agglomerative ( "bottom-up" ): Agglomerative algorithms begin with each element as a separate cluster and merge them into successively larger clusters. Divisive ( "top-down" ): Divisive algorithms begin with the whole set and proceed to divide it into successively smaller clusters.

12. K-means Clustering

13. k-Means Clustering Input: n objects (or points) and a number k Algorithm Randomly assign K records to be the initial cluster center locations Assign each object to the group that has the closest centroid When all objects have been assigned, recalculate the positions of the K centroids Repeat steps 2 to 3 until convergence or termination

14. K -Mean Clustering

15. Termination Conditions The algorithm terminates when the centroids no longer change . The SSE( sum of squared errors ) value is less than some small threshold value  Where p є C i represents each data point in cluster i and m i represent the centroid of cluster i .

16. Example 1: Lets s suppose the following points are the delivery locations for pizza

17. Lets locate three cluster centers randomly

18. Find the distance of points as shown

19. Assign the points to the nearest cluster center based on the distance between each center and the point

20. Re-assign the cluster centres and locate nearest points

21. Re-assign the cluster centres and locate nearest points, calculate the distance

22. Form the three clusters

23. Example 2: Suppose that we have eight data points in two -dimensional space as follows And suppose that we are interested in uncovering k =2 clusters.

24. Point Distance from m1 Distance from m2 Cluster membership a b c d e f g h

25. Point Distance from m1 Distance from m2 Cluster membership a 2.00 2.24 b 2.83 2.24 c 3.61 2.83 d 4.47 3.61 e 1.00 1.41 f 3.16 2.24 g 0.00 1.00 h 1.00 0.00

26. Point Distance from m1 Distance from m2 Cluster membership a 2.00 2.24 C1 b 2.83 2.24 C2 c 3.61 2.83 C2 d 4.47 3.61 C2 e 1.00 1.41 C1 f 3.16 2.24 C2 g 0.00 1.00 C1 h 1.00 0.00 C2 SSE=2 2 +2.24 2 +2.83 2 +3.61 2 +1 2 +2.24 2 +0 2 +0 2 =36 d (m1,m2)=1

27. Centroid of the cluster 1 is [(1+1+1)/3,(3+2+1)/3] =( 1,2) Centroid of the cluster 2 is [ (3+4+5+4+2)/5, (3 +3+3+2+1)/5] = ( 3.6,2.4)

28. Point Distance from m1 Distance from m2 Cluster membership a b c d e f g h m1= ( 1,2 ) m 2=( 3.6,2.4)

29. Point Distance from m1 Distance from m2 Cluster membership a 1.00 2.67 b 2.24 0.85 c 3.61 0.72 d 4.12 1.52 e 0.00 2.63 f 3.00 0.57 g 1.00 2.95 h 1.41 2.13 m1= ( 1,2 ) m 2=( 3.6,2.4)

30. Point Distance from m1 Distance from m2 Cluster membership a 1.00 2.67 C1 b 2.24 0.85 C2 c 3.61 0.72 C2 d 4.12 1.52 C2 e 0.00 2.63 C1 f 3.00 0.57 C2 g 1.00 2.95 C1 h 1.41 2.13 C1 SSE=1 2 +0.85 2 +0.72 2 +1.52 2 +0 2 +0.57 2 +1 2 +1.41 2 =7.88 d (m1,m2)=2.63 m 1(1,2) m 2(3.6,2.4)

31. Centroid of the cluster 1 is [(1+1+1+2)/4,(3+2+1+1)/4] =( 1.25,1.75) Centroid of the cluster 2 is [ (3+4+5+4)/4, (3 +3+3+2)/4] = ( 4,2.75)

32. Point Distance from m1 Distance from m2 Cluster membership a b c d e f g h m 1(1.25,1.75) m2( 4,2.75)

33. Point Distance from m1 Distance from m2 Cluster membership a 1.27 3.01 b 2.15 1.03 c 3.02 0.25 d 3.95 1.03 e 0.35 3.09 f 2.76 0.75 g 0.79 3.47 h 1.06 2.66 m 1(1.25,1.75) m2( 4,2.75)

34. Point Distance from m1 Distance from m2 Cluster membership a 1.27 3.01 C1 b 2.15 1.03 C2 c 3.02 0.25 C2 d 3.95 1.03 C2 e 0.35 3.09 C1 f 2.76 0.75 C2 g 0.79 3.47 C1 h 1.06 2.66 C1 m 1(1.25,1.75) m2( 4,2.75) SSE=1.27 2 +1.03 2 +0.25 2 +1.03 2 +0.35 2 +0.75 2 +0.79 2 +1.06 2 =6.25 d (m1,m2)=2.93

35. Final Results

36. Example 2:

37. An issue on k-Means Algorithm Algorithm cannot guarantee finding the global minimum SSE, instead often settling at a local minimum. To improve the probability of achieving a global minimum, suggests; Placing the first cluster center on a random data point and Placing the subsequent cluster centers on points as far away from previous center points as possible.

38. How to decide k? Unless the analyst has a prior knowledge of the number of underlying clusters, therefore, Clustering solutions for each value of K is compared The value of K resulting in the smallest SSE being selected

39. Summary K-means algorithm is a simple yet popular method for clustering analysis Low complexity :complexity is O( nkt ), where t = # iterations Its performance is determined by initialisation and appropriate distance measure There are several variants of K -means to overcome its weaknesses K - Medoids : resistance to noise and/or outliers(data that do not comply with the general behaviour or model of the data ) K -Modes: extension to categorical data clustering analysis CLARA: extension to deal with large data sets Gaussian Mixture models ( EM algorithm ): handling uncertainty of clusters

40. Hierarchical Clustering

41. 42 Hierarchical Clustering Build a tree-based hierarchical taxonomy ( dendrogram ) One approach : recursive application of a partitional clustering algorithm. animal vertebrate fish reptile amphib. mammal worm insect crustacean invertebrate

42. Hierarchical clustering and dendrograms A hierarchical clustering on a set of objects D is a set of nested partitions of D. It is represented by a binary tree such that : The root node is a cluster that contains all data points Each (parent) node is a cluster made of two subclusters ( childs ) Each leaf node represents one data point (singleton ie cluster with only one item) A hierarchical clustering scheme is also called a taxonomy. In data clustering the binary tree is called a dendrogram .

43. 44 Clustering obtained by cutting the dendrogram at a desired level: each connected component forms a cluster. Dendogram : Hierarchical Clustering

44. Hierarchical clustering: forming clusters Forming clusters from dendograms

45. Hierarchical clustering There are two styles of hierarchical clustering algorithms to build a tree from the input set S: Agglomerative (bottom-up) : Beginning with singletons (sets with 1 element) Merging them until S is achieved as the root . In each steps , the two closest clusters are aggregates into a new combined cluster In this way, number of clusters in the data set is reduced at each step Eventually, all records/elements are combined into a single huge cluster It is the most common approach. Divisive (top-down) : All records are combined in to a one big cluster Then the most dissimilar records being split off r ecursively partitioning S until singleton sets are reached . Does not require the number of clusters k in advance

46. Two types of hierarchical clustering algorithms : Agglomerative : “bottom-up” Divisive : “top-down

47. 48 Hierarchical Agglomerative Clustering (HAC) Algorithm Start with all instances in their own cluster. Until there is only one cluster: Among the current clusters, determine the two clusters, c i and c j , that are most similar. Replace c i and c j with a single cluster c i  c j Assumes a similarity function for determining the similarity of two instances. Starts with all instances in a separate cluster and then repeatedly joins the two clusters that are most similar until there is only one cluster.

48. Classification of AHC We can distinguish AHC algorithms according to the type of distance measures used. There are two approaches : Graph methods : Single link method Complete link method Group average method (UPGMA) Weighted group average method (WPGMA) Geometric : Ward’s method Centroid method Median method

49. Lance – W illiams Algorithm Definition( Lance-Williams formula) In AHC algorithms, the Lance-Williams formula [Lance and Williams, 1967] is a recurrence equation used to calculate the dissimilarity between a cluster C k and a cluster formed by merging two other clusters C l ∪ C l ′ where α I , α I’ , β , γ are real numbers

50. AHC methods and the Lance-Williams formula

51. Single link method Also known as the nearest neighbor method, since it employs the nearest neighbor to measure the dissimilarity between two clusters

52. Cluster distance measure Single link Distance between closest elements in clusters Complete link Distance between farthest elements in clusters Centroids Distance between centroids(means) of two clusters

53. Single-link clustering Nested Clusters Dendrogram 1 2 3 4 5 6 1 2 3 4 5

54. Example 1 -Single link method

55. Example 02-Single link method x 1 = (1, 2) x 2 = (1, 2.5 ) x 3 = (3, 1 ) x 4 = (4, 0.5) x 5 = (4, 2)

56. x 1 = (1, 2) x 2 = (1, 2.5 ) x 3 = (3, 1 ) x 4 = (4, 0.5) x 5 = (4, 2) Merge X1 and X2

57. Merge X3 and X4

58. Merge {X3,X4 } and X5

59. Merge {X1,X2} and {X3,X4,X5}

60. x 1 = (1, 2) x 2 = (1, 2.5 ) x 3 = (3, 1 ) x 4 = (4, 0.5) x 5 = (4, 2) Merge X1 and X2 Example 3-Complete link method

61. Merge X3 and X4

62. Merge {X3,X4} and X5

63. Merge {X1,X2} and {X3,X4,X5}

64. The dendrogram :

65. Summary Hierarchical Clustering For a dataset consisting of n points O(n 2 ) space; it requires storing the distance matrix O(n 3 ) time complexity in most of the cases( agglomerative clustering ) Advantages Dendograms are great for visualization Provides hierarchical relations between clusters Disadvantages Not easy to define levels for clusters Can never undo what was done previously Sensitive to cluster distance measures and noise/ outliers Experiments showed that other clustering techniques outperform hierarchical clustering There are several variants to overcome its weaknesses BIRCH : scalable to a large data set ROCK : clustering categorical data CHAMELEON : hierarchical clustering using dynamic modelling