Next: Nearest Neighbor clustering
Up: Partitional Clustering
Previous: Clustering by density Estimation
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
- Construct the MST for the set of n patterns given.
- Identify inconsistent edges in MST.
- 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.
Miranda Maria Irene
Thu Apr 1 15:43:18 IST 1999