Hierarchical Agglomerative Clustering

Hierarchical clustering algorithms are either top-down or bottom-up. Bottom-up algorithms treat each document as a singleton cluster at the outset and then successively merge (or agglomerate) pairs of clusters until all clusters have been merged into a single cluster that contains all documents. Bottom-up hierarchical clustering is therefore called hierarchical agglomerative clustering or HAC . Top-down clustering requires a method for splitting a cluster. It proceeds by splitting clusters recursively until individual documents are reached.

An HAC clustering is typically visualized as a dendrogram. Each merge is represented by a horizontal line. The y-coordinate of the horizontal line is the similarity of the two clusters that were merged, where documents are viewed as singleton clusters. We call this similarity the combination similarity of the merged cluster. The combination similarity of a singleton cluster is by moving up from the bottom layer to the top node, a dendrogram allows us to reconstruct the history of merges that resulted in the depicted clustering.

Process

· Assign each object to a separate cluster.

· Evaluate all pair-wise distances between clusters

· Construct a distance matrix using the distance values.

· Look for the pair of clusters with the shortest distance.

· Remove the pair from the matrix and merge them.

· Evaluate all distances from this new cluster to all other clusters, and update the matrix.

· Repeat until the distance matrix is reduced to a single element.

Advantages

· It can produce an ordering of the objects, which may be informative for data display.

· Smaller clusters are generated, which may be helpful for discovery.

Disadvantages

· No provision can be made for a relocation of objects that may have been 'incorrectly' grouped at an early stage. The result should be examined closely to ensure it makes sense.

· Use of different distance metrics for measuring distances between clusters may generate different results. Performing multiple experiments and comparing the results is recommended to support the veracity of the original results.

SUBMITTED BY:

SONIKA PRADHAN

ROLL NO. 1 2164

MBA (HR)

SIBM- Bangalore