Suppose you need rough groups of points before running a more precise clustering algorithm. Canopy clustering uses two distance thresholds to decide which points belong near a chosen center and which points no longer need to become centers themselves. section 13.1.3
Choose thresholds T1 and T2 with T1 > T2, then repeat until no possible center remains:
- Draw a point p from the possible centers and start a canopy containing p. section 13.1.3
- Check every point q. If distance(p, q) < T1, add q to the canopy; a point may belong to more than one canopy. section 13.1.3
- If distance(p, q) < T2, also remove q from the possible centers. It stays eligible for other canopies, but cannot start one. section 13.1.3
T1 is the outer radius; T2 marks the inner region where a point is close enough to the center that another canopy centered on it is unnecessary. The tests are strict: a distance equal to either threshold does not pass that test. With k canopies and n points, the shown algorithm checks distances against all n points for each center, or O(kn) distance checks; overlapping membership can make stored canopy entries exceed n. section 13.1.3
Figure 13.2 An example of canopy clustering running on a dataset. The first three sub-figures show the creation of tree canopies, starting from randomly chosen points. Circles filled with a solid color other than the lightest shading are points removed from the list of possible centroids, while pentagons are the centroids of canopies. The solid-color points are removed from the list because they lie within the inner radius (T2) from the centroids (as shown in the first three steps). The last sub-figure shows the clusters created after a few more steps. Note that there are still some lightly shaded points, so at least three more canopies (that will partially overlap the five shown) will be created to include those points.
The inner circles show why nearby points cease to be candidate centers, while outer circles show the overlapping canopies they can still join. section 13.1.3
Thresholds are tuning parameters, not a direct setting for the number of canopies. Try values informed by the distance scale of the data, then check canopy count and quality. For k-means initialization, randomized runs may return different numbers of centers even with unchanged thresholds; when there are too few, lowering T2 can retain more candidate centers, while raising it can reduce an excess. section 13.1.3 section 13.3.2
