Clustering by graph theory

These algorithms treat the patterns as points in a pattern space, so distances are available between all pairs of patterns. A complete graph is formed by connecting each pattern with all its neighbours. The edge weights are distances between pairs of patterns.

Zahn's clustering Algorithm

1. Construct the MST for the set of n patterns given.
2. Identify inconsistent edges in MST.
3. Remove the inconsistent edges to form connected components and call them clusters.

Inconsistent edges are those whose weight is significantly larger than the average of nearby edge weights. This works well for a two-dimensional data set. Special heuristics are needed for complex situations and to select the proper heuristic we need the prior knowledge of the shapes of clusters. This is the greatest deficiency of the MST based approach in more than two dimensions.