Agglomerative Clustering

A clustering scheme is called as agglomerative if new clusters are formed one at a time from the existing clusters. An agglomerative clustering algorithm begins with a n-way clustering solution viz. = and iteratively constructs solution from as follows :

1. Choose two clusters and from .
2. Construct from by removing and and adding merged cluster .

The selection of these two clusters viz. and is usually done based on improving some objective function. The criterion for choosing the clusters and is what distinguishes among the agglomerative variants. The various agglomerative schemes that were studied are described below :

1. Scheme 1

   This scheme is due to Steven Johnson [9]. As described in the paper, the scheme starts with the initial clustering solution where each vertex belongs to its own cluster. The scheme is iterative in nature. At any iteration k, two clusters are namely and are chosen from the clustering solution at that level and are merged together.The selection criterion for clusters and for this scheme is
   

   Minimize = Diameter(C) where .

   Diameter(C) is defined as follows.

   where P(x,y) represents a path from vertex x to vertex y.

   Thus those clusters are selected for merging which yield the minimum diameter of resultant cluster. After this selection is done, the clusters and are removed from the clustering solution and a new cluster named is added to generate the next clustering solution . The process is repeated till the desired number of clusters are obtained or till the clusters become "strong" enough.

     
   Figure: A Scenario For Clustering
   

   Comments:

   1. Here the objective function is the minimization of the diameter of the resultant cluster as defined above. This however does not seem to be a very good objective function. Consider the scenario in Fig . Here minimization of the diameter would yield no preference between both the situations. However clearly, clustering nodes in Fig.8.a is more desirable than to cluster the nodes in Fig.8.b. Thus this objective function fails to capture the degree by means of which the nodes are connected within a cluster. It merely captures the fact that they are connected which does not seem particularly useful.
   2. The clustering objective clearly does not seem particularly useful in the context of multilevel formulation. As in Fig  if the tie is broken in a random fashion at very top level, then at the next levels the scheme may lose important connectivity information, thereby giving rise to pretty bad clusters.
   3. However it is quite clear that the diameter is an attractive choice as one of the parameters for the objective function. Clearly an objective which is a function of the size of the cluster, the number of edges inside the cluster and the diameter could be a very good choice for the sake of being considered as an objective function. i.e.
      

      Where |C| = size of cluster (C), and
      = size of the set of edges completely contained within C.

      could be a very good function for the sake of clustering. As an example

      could serve as a good objective function. One needs to experiment with these parameters to find out a good objective function. Such a function would be very useful for multilevel formulation as it would capture all the necessary information about the connectivity and the degree of connectivity as well in the whole graph, as well as graph at each level.

2. Scheme 2

   This scheme is due to Karger[10]. The scheme mainly talks about a graph bisection problem with the min-cut formulation.The scheme begins with claiming all the vertices as isolated clusters i.e, the starting solution is . Iteratively a random edge is chosen and its incident clusters are contracted into a single cluster. The process is repeated till two "meta" vertices are obtained which is the final solution for the graph bisection problem. Authors of [3] claim that this scheme can be utilized for the clustering problem. First of all the approach can be extended to hypergraphs by picking up a hyperedge at random and then contracting two random incident clusters. As an alternative, all the clusters incident to the hyperedge can also be collapsed into a single vertex. The process is repeated till the desired number of clusters is found or till the clusters become "strong" enough. An alternative greedy approach would be to merge two clusters with highest connectivity i.e., for the sake of choosing and at an iteration k from the current solution , the objective function would be

   Maximize .

   Here is the set of hyperedges cut by the cluster and is given by,

    

   Comments :

   1. Here the objective function is maximization of as defined above. This however does not seem to be a good objective function. Consider the scenario in Fig . Clearly the vertices of Fig.9.b are more closely connected than the vertices of Fig.9.a. So clearly merging the two vertices in Fig.9.b would be a better choice. However the parameter for the clusters in Fig.9.a is more than that for the clusters in Fig.9.b. Hence the scheme will prefer the clusters in Fig.9.a over those in Fig.9.b for the sake of merging, which is clearly undesirable.

        
      Figure: A Scenario For Clustering
      

   2. The main drawback of this scheme is that it does not take into consideration the sizes of the clusters that are being considered for merging. Hence the scheme seems to prefer large clusters for the sake of merging as the for a cluster will usually be higher if the cluster is large. Hence this objective formulation will not be so useful for a multilevel scheme as it tends to prefer larger clusters for merging.
   3. This objective clearly does not take into account the sizes of the clusters which it is considering for merging. A good choice for the objective function would be the one which takes into account the sizes of the cluster being merged along with the number of edges that go between them. Hence the objective function should be a function as shown: Maximize
      

      An example objective function could be Maximize

      One needs to experiment with these parameters to find out a good objective function. Such a function would be very useful for multilevel formulation as it would capture all the necessary information about the connectivity and the degree of connectivity as well in the whole graph, as well as graph at each level.

3. Scheme 3

   This scheme is due to Schuler and Ulrich [11]. This work is based on an observation regarding the previous scheme. The previous scheme ignores the number of edges cut by the merged cluster. It also fails to construct a balanced clustering. It seems to be giving preference to larger and larger clusters to collapse in spite of the fact that there could be situations where it is not a wise choice to do so. Thus taking these shortcomings of the previous scheme into consideration the authors have come up with a better objective function. The authors try to select and so as to maximize the objective of the form :

   

   where f is a function of the cluster weights. A simple example of f could be . In this case the formation of larger clusters is penalized by the weight of the cluster in the denominator. The two large clusters wont be merged together unless the affinity between them is strong enough.

   Comments:

   1. The objective here is to maximize the F as defined above. The maximization function essentially tries to capture the connectivity between the clusters that are considered for the sake of merging. The terms and can be made to capture the sizes of the clusters as well. Thus the scheme overcomes the discrepancies of the previous scheme due to Karger[10].
   2. The objective function seems to be a very good choice for the sake of multilevel formulation as it does capture all the necessary information about the connectivity in the graph at each level.
   3. The objective function in essence tries to maximize the connectivity within the clusters thereby minimizing the inter-cluster similarity. Thus this seems to be similar to the schemes proposed in this report. The later tries to maximize the connectivity within the clusters subject to a particular constraint about the connectivity specified by an input parameter .
   4. The objective is pretty generalized to capture the essential information. One needs to experiment with the terms and for the sake of obtaining a good clustering solution.
4. Scheme 4

   This particular scheme is due to Shin and Kim[12]. The authors have presented a hierarchical scheme for obtaining a good partitioning. It works as follows :
   The scheme consists of two phases. In the first phase initial clusters are constructed from the original graph and then partitioned to find a good initial solution. In the second phase, the clusters are flattened and then partitioned using a Gradual Constraint Enforcing Partitioning (GCEP) method. In the first phase, the clusters formed are partitioned using GCEP a lot of times and the best result is saved. This result is used as a starting point for the second phase which flattens the clusters first and then apply GCEP on it to obtain the final solution. The basic idea is to allow the closely coupled vertices to settle first and then allow freer vertices to move closer to an optimum bipartitioning in the later passes. The GCEP is actually a slight variant of the F&M algorithm. It consists of making multiple passes over the data where the cluster size constraints become tighter and tighter within each pass. The authors name their scheme as HGCEP ( Hierarchical Gradual Constraint Enforcing Partitioner), and it seems to be less dependent on the initial solution than the F&M method.
   For the first phase of the scheme, a good clustering of the initial graph is needed. The clustering scheme followed is same as the standard agglomerative scheme with the clusters selection criterion for merging as follows :
   Given , choose and which Maximize

   The first term captures the connectivity between the clusters, with the denominator favoring the selection of a cluster which has connections to only one other cluster. The second term implies a penalty for making a cluster too large. If the merged cluster has weight greater than the average cluster weight, then it is penalized by some factor. Thus the authors have developed a clustering approach for use with two phase FM. The scheme makes many runs on the clusters found to get an initial good partition. Then the solution is flattened and a partition is obtained by a F & M variant scheme named GCEP. The value of reported by the authors is 0.5/200. Fig  shows why the authors have chosen the function instead of choosing in the denominator of the first term.

     
   Figure: A Scenario For Clustering
   

   So let and
   

   let

   So as shown in the figure,
   
   
   
   
   

   Hence prefers merging and together to merging and while does not show any preference. As claimed by the authors, a human designed would choose to merge and together first, since should be merged to if it ever merges with a cell. The authors have reported better results with over .

   Comments :

   1. The objective function used by the authors seems to be a good objective function. The first term tries to maximize the connectivity within the clusters. This is in essence the theme of the schemes developed in this report.
   2. The scheme imposes a penalty for making clusters too big. Thus it prefers the formation of balanced clusters. The size of the clusters formed is approximately the same. This was not the aim of any of the schemes developed in this report. In this report, the problem was formulated in a way to maximize the connectivity within the clusters. The size of the cluster was never a concern. Hence that particular parameter was neglected while developing the schemes.
   3. This particular objective function also seems to capture all the essential information at all the levels. Hence it is suitable for a multilevel formulation.
5. Scheme 5

   These scheme is due to Ng et.al [13]. According to [14], there is a power-law relationship between the number of edges incident to a cluster and the size of the cluster, which is given by where, .
   

   Here d(C) represents the average degree of the modules in the cluster C. Based on this rule, Ng[13] have proposed an agglomerative method. Here the candidates for merging viz., and are chosen so as to minimize the Rent Parameter of the merged cluster C, which is given by,

   Minimize .

   Here the merging process continues until the prescribed number k of clusters is reached or until r exceeds a prescribed constant.

   Comments :

   1. Here the objective function is derived from an average case phenomenon in ``good'' circuit placements, which is given by the Rent's rule as described above. The objective function seems to be strong enough to capture the important enough at each stage of the clustering, making it a good choice for the multilevel formulation.
   2. The scheme in essence seems exactly similar to the schemes developed in this report. The schemes developed in this report characterize the clusters by means of an input parameter names . In the above mentioned scheme, the cluster is characterized by means of the rent parameter. Essentially, the desired clustering can be obtained by having the desired rent parameter as an input to the code viz. . So all the clusters have to have the .