{"id":366,"date":"2013-12-06T15:11:23","date_gmt":"2013-12-06T20:11:23","guid":{"rendered":"http:\/\/homepages.uc.edu\/~yaozo\/wordpress\/?p=366"},"modified":"2013-12-06T15:11:23","modified_gmt":"2013-12-06T20:11:23","slug":"hierarchical-clustering-algorithms","status":"publish","type":"post","link":"https:\/\/zhuoyao.net\/index.php\/2013\/12\/06\/hierarchical-clustering-algorithms\/","title":{"rendered":"Hierarchical Clustering Algorithms"},"content":{"rendered":"

How They Work<\/em><\/span>
\nGiven a set of N items to be clustered, and an N*N distance (or similarity) matrix, the basic process of hierarchical clustering (defined by\u00a0S.C. Johnson in 1967<\/a>) is this:<\/span><\/p>\n

    \n
  1. Start by assigning each item to a cluster, so that if you have N items, you now have N clusters, each containing just one item. Let the distances (similarities) between the clusters the same as the distances (similarities) between the items they contain.<\/span><\/li>\n
  2. Find the closest (most similar) pair of clusters and merge them into a single cluster, so that now you have one cluster less.<\/span><\/li>\n
  3. Compute distances (similarities) between the new cluster and each of the old clusters.<\/span><\/li>\n
  4. Repeat steps 2 and 3 until all items are clustered into a single cluster of size N. (*)<\/span><\/li>\n<\/ol>\n

    Step 3 can be done in different ways, which is what distinguishes\u00a0single-linkage<\/em>\u00a0from\u00a0complete-linkage<\/em>\u00a0and\u00a0average-linkage<\/em>\u00a0clustering.
    \nIn\u00a0single-linkage<\/em>\u00a0clustering (also called the\u00a0connectedness<\/em>\u00a0or\u00a0minimum<\/em>\u00a0method), we consider the distance between one cluster and another cluster to be equal to the\u00a0shortest<\/span>\u00a0distance from any member of one cluster to any member of the other cluster. If the data consist of similarities, we consider the similarity between one cluster and another cluster to be equal to the\u00a0greatest<\/span>\u00a0similarity from any member of one cluster to any member of the other cluster.
    \nIn\u00a0complete-linkage<\/em>\u00a0clustering (also called the\u00a0diameter<\/em>\u00a0or\u00a0maximum<\/em>\u00a0method), we consider the distance between one cluster and another cluster to be equal to the\u00a0greatest<\/span>\u00a0distance from any member of one cluster to any member of the other cluster.
    \nIn\u00a0average-linkage<\/em>\u00a0clustering, we consider the distance between one cluster and another cluster to be equal to the\u00a0average<\/span>\u00a0distance from any member of one cluster to any member of the other cluster.
    \nA variation on average-link clustering is the UCLUS method of\u00a0    R. D’Andrade (1978)<\/a>\u00a0which uses the\u00a0median<\/span>\u00a0distance, which is much more outlier-proof than the average distance.<\/span><\/p>\n

    This kind of hierarchical clustering is called\u00a0agglomerative<\/em>\u00a0because it merges clusters iteratively. There is also a\u00a0divisive<\/em>\u00a0hierarchical clustering which does the reverse by starting with all objects in one cluster and subdividing them into smaller pieces. Divisive methods are not generally available, and rarely have been applied.<\/span><\/p>\n

    (*) Of course there is no point in having all the N items grouped in a single cluster but, once you have got the complete hierarchical tree, if you want k clusters you just have to cut the k-1 longest links.<\/span><\/p>\n

     <\/p>\n

    Single-Linkage Clustering: The Algorithm<\/em><\/span>
    \nLet\u2019s now take a deeper look at how Johnson\u2019s algorithm works in the case of single-linkage clustering.
    \nThe algorithm is an agglomerative scheme that erases rows and columns in the proximity matrix as old clusters are merged into new ones.<\/span><\/p>\n

    The N*N proximity matrix is D = [d(i,j)]. The clusterings are assigned sequence numbers 0,1,……, (n-1) and L(k) is the level of the kth clustering. A cluster with sequence number m is denoted (m) and the proximity between clusters (r) and (s) is denoted d [(r),(s)].<\/span><\/p>\n

    The algorithm is composed of the following steps:<\/span><\/p>\n\n\n\n
    \n
      \n
    1. Begin with the disjoint clustering having level L(0) = 0 and sequence number m = 0.
      \n<\/span><\/em><\/li>\n
    2. Find the least dissimilar pair of clusters in the current clustering, say pair (r), (s), according to<\/span>
      \n
      \nd[(r),(s)] = min d[(i),(j)]<\/span>
      \n
      \nwhere the minimum is over all pairs of clusters in the current clustering.
      \n<\/span><\/em><\/li>\n
    3. Increment the sequence number : m = m +1. Merge clusters (r) and (s) into a single cluster to form the next clustering m. Set the level of this clustering to<\/span>
      \n
      \nL(m) = d[(r),(s)]
      \n<\/span><\/em><\/li>\n
    4. Update the proximity matrix, D, by deleting the rows and columns corresponding to clusters (r) and (s) and adding a row and column corresponding to the newly formed cluster. The proximity between the new cluster, denoted (r,s) and old cluster (k) is defined in this way:<\/span>
      \n
      \nd[(k), (r,s)] = min d[(k),(r)], d[(k),(s)]
      \n<\/span><\/em><\/li>\n
    5. If all objects are in one cluster, stop. Else, go to step 2.<\/span><\/em><\/li>\n<\/ol>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      \n

      An Example<\/em><\/span>
      \nLet\u2019s now see a simple example: a hierarchical clustering of distances in kilometers between some Italian cities. The method used is single-linkage.<\/span><\/p>\n

      Input distance matrix<\/strong>\u00a0(L = 0 for all the clusters):<\/span><\/p>\n\n\n\n\n\n\n\n\n\n
      <\/td>\n\n
      BA<\/strong><\/div>\n<\/td>\n
      		\n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      MI<\/strong><\/div>\n<\/td>\n
      		\n
      NA<\/strong><\/div>\n<\/td>\n
      		\n
      RM<\/strong><\/div>\n<\/td>\n
      		\n
      TO<\/strong><\/div>\n<\/td>\n<\/tr>\n
      \n
      BA<\/strong><\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      662<\/div>\n<\/td>\n
      		\n
      877<\/div>\n<\/td>\n
      		\n
      255<\/div>\n<\/td>\n
      		\n
      412<\/div>\n<\/td>\n
      		\n
      996<\/div>\n<\/td>\n<\/tr>\n
      \n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      662<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      468<\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n
      		\n
      400<\/div>\n<\/td>\n<\/tr>\n
      \n
      MI<\/strong><\/div>\n<\/td>\n
      		\n
      877<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      754<\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n
      		\n
      138<\/div>\n<\/td>\n<\/tr>\n
      \n
      NA<\/strong><\/div>\n<\/td>\n
      		\n
      255<\/div>\n<\/td>\n
      		\n
      468<\/div>\n<\/td>\n
      		\n
      754<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      219<\/div>\n<\/td>\n
      		\n
      869<\/div>\n<\/td>\n<\/tr>\n
      \n
      RM<\/strong><\/div>\n<\/td>\n
      		\n
      412<\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n
      		\n
      219<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      669<\/div>\n<\/td>\n<\/tr>\n
      \n
      TO<\/strong><\/div>\n<\/td>\n
      		\n
      996<\/div>\n<\/td>\n
      		\n
      400<\/div>\n<\/td>\n
      		\n
      138<\/div>\n<\/td>\n
      		\n
      869<\/div>\n<\/td>\n
      		\n
      669<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      \"\"<\/p>\n

      The nearest pair of cities is MI and TO, at distance 138. These are merged into a single cluster called “MI\/TO”. The level of the new cluster is L(MI\/TO) = 138 and the new sequence number is m = 1.
      \n<\/span>Then we compute the distance from this new compound object to all other objects. In single link clustering the rule is that the distance from the compound object to another object is equal to the shortest distance from any member of the cluster to the outside object. So the distance from “MI\/TO” to RM is chosen to be 564, which is the distance from MI to RM, and so on.<\/span><\/p>\n

      After merging MI with TO we obtain the following matrix:<\/span><\/p>\n

      \n\n\n\n\n\n\n\n\n
      <\/td>\n\n
      BA<\/strong><\/div>\n<\/td>\n
      		\n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      MI\/TO<\/strong><\/div>\n<\/td>\n
      		\n
      NA<\/strong><\/div>\n<\/td>\n
      		\n
      RM<\/strong><\/div>\n<\/td>\n<\/tr>\n
      \n
      BA<\/strong><\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      662<\/div>\n<\/td>\n
      		\n
      877<\/div>\n<\/td>\n
      		\n
      255<\/div>\n<\/td>\n
      		\n
      412<\/div>\n<\/td>\n<\/tr>\n
      \n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      662<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      468<\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n<\/tr>\n
      \n
      MI\/TO<\/strong><\/div>\n<\/td>\n
      		\n
      877<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      754<\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n<\/tr>\n
      \n
      NA<\/strong><\/div>\n<\/td>\n
      		\n
      255<\/div>\n<\/td>\n
      		\n
      468<\/div>\n<\/td>\n
      		\n
      754<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      219<\/div>\n<\/td>\n<\/tr>\n
      \n
      RM<\/strong><\/div>\n<\/td>\n
      		\n
      412<\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n
      		\n
      219<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      \"\"<\/p>\n

      min d(i,j) = d(NA,RM) = 219 => merge NA and RM into a new cluster called NA\/RM
      \nL(NA\/RM) = 219
      \nm = 2<\/span><\/p>\n

       <\/p>\n\n\n\n\n\n\n\n
      <\/td>\n\n
      BA<\/strong><\/div>\n<\/td>\n
      		\n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      MI\/TO<\/strong><\/div>\n<\/td>\n
      		\n
      NA\/RM<\/strong><\/div>\n<\/td>\n<\/tr>\n
      \n
      BA<\/strong><\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      662<\/div>\n<\/td>\n
      		\n
      877<\/div>\n<\/td>\n
      		\n
      255<\/div>\n<\/td>\n<\/tr>\n
      \n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      662<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n<\/tr>\n
      \n
      MI\/TO<\/strong><\/div>\n<\/td>\n
      		\n
      877<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n<\/tr>\n
      \n
      NA\/RM<\/strong><\/div>\n<\/td>\n
      		\n
      255<\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      \"\"<\/p>\n

      min d(i,j) = d(BA,NA\/RM) = 255 => merge BA and NA\/RM into a new cluster called BA\/NA\/RM
      \nL(BA\/NA\/RM) = 255
      \nm = 3<\/span><\/p>\n

       <\/p>\n\n\n\n\n\n\n
      <\/td>\n\n
      BA\/NA\/RM<\/strong><\/div>\n<\/td>\n
      		\n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      MI\/TO<\/strong><\/div>\n<\/td>\n<\/tr>\n
      \n
      BA\/NA\/RM<\/strong><\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n<\/tr>\n
      \n
      FI<\/strong><\/div>\n<\/td>\n
      		\n
      268<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n<\/tr>\n
      \n
      MI\/TO<\/strong><\/div>\n<\/td>\n
      		\n
      564<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      \"\"<\/p>\n

      min d(i,j) = d(BA\/NA\/RM,FI) = 268 => merge BA\/NA\/RM and FI into a new cluster called BA\/FI\/NA\/RM
      \nL(BA\/FI\/NA\/RM) = 268
      \nm = 4<\/span><\/p>\n

       <\/p>\n\n\n\n\n\n
      <\/td>\n\n
      BA\/FI\/NA\/RM<\/strong><\/div>\n<\/td>\n
      		\n
      MI\/TO<\/strong><\/div>\n<\/td>\n<\/tr>\n
      \n
      BA\/FI\/NA\/RM<\/strong><\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n<\/tr>\n
      \n
      MI\/TO<\/strong><\/div>\n<\/td>\n
      		\n
      295<\/div>\n<\/td>\n
      		\n
      0<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

      \"\"<\/p>\n

      Finally, we merge the last two clusters at level 295.<\/span><\/p>\n

      The process is summarized by the following hierarchical tree:<\/span><\/p>\n

      \"\"<\/p>\n

       <\/p>\n

      Problems<\/span><\/em>
      \nThe main weaknesses of agglomerative clustering methods are:<\/span><\/p>\n