Clustering - Mining of Massive Datasets - page 251

For the second step, we pick the representative points. If the sample from which the
clusters are constructed is large enough, we can count on a cluster's sample points at
greatest distance from one another lying on the boundary of the cluster. Figure 7.13 sug-
gests what our initial selection of sample points might look like.

Figure 7.13 Select representative points from each cluster, as far from one another as possible

Finally, we move the representative points a fixed fraction of the distance from their
true location toward the centroid of the cluster. Note that in Fig. 7.13 both clusters have
their centroid in the same place: the center of the inner circle. Thus, the representative
points from the circle move inside the cluster, as was intended. Points on the outer edge of
the ring also move into their cluster, but points on the ring's inner edge move outside the
cluster. The final locations of the representative points from Fig. 7.13 are suggested by Fig.
7.14 . □

Figure 7.14 Moving the representative points 20% of the distance to the cluster's centroid

7.4.2 Completion of the CURE Algorithm

The next phase of CURE is to merge two clusters if they have a pair of representative
points, one from each cluster, that are sufficiently close. The user may pick the distance
that defines “close.” This merging step can repeat, until there are no more sufficiently close
clusters.

EXAMPLE 7.12 The situation of Fig. 7.14 serves as a useful illustration. There is some argu-
ment that the ring and circle should really be merged, because their centroids are the same.
For instance, if the gap between the ring and circle were much smaller, it might well be ar-
gued that combining the points of the ring and circle into a single cluster reflected the true
state of affairs. For instance, the rings of Saturn have narrow gaps between them, but it is