Canopy clustering algorithm

The canopy clustering algorithm is an unsupervised pre-clustering algorithm, often used as preprocessing step for the K-means algorithm.

It is intended to speed up clustering operations on large data sets, where using another algorithm directly may be impractical due to the size of the data set.

The algorithm proceeds as follows:

• Cheaply partitioning the data into overlapping subsets (called "canopies")
• Perform more expensive clustering, but only within these canopies

Since the algorithm uses distance functions and requires the specification of distance tresholds, it's applicability for high-dimensional data is limited by the curse of dimensionality. Only when a cheap and approximative - low dimensional - distance function is available, the produced canopies will preserve the clusters produced by K-means.

Benefits

• The number of instances of training data that must be compared at each step is reduced
• There is some evidence that the resulting clusters are improved

External link

• McCallum, Nigam and Ungar: "Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching"