# CURE algorithm: what does moving the representative points towards the centroid do?

The CURE algorithm is a method of clustering data. An outline of it can be found here on slide 5: https://www.slideshare.net/ellepiu/cure-clustering-algorithm. I personally learnt it from this video: https://www.youtube.com/watch?v=JrOJspZ1CUw, where the algorithm is explained at 7 minutes.

This is my understanding of the process of CURE. Let's assume that the data set is large enough such that we have to store a portion of the data on disk.

1. Take an amount of the data set that fits onto the computer, and cluster (perhaps hierarchically) to initialise clusters.

2. For each cluster: pick k representative points, and move each a fixed distance, $\alpha$, towards the cluster centroid.

3. For each data point on disk, assign it to the cluster with the representative point it is closest to.

To me, this selection of representative points seems like a really arbitrary thing to do, and I don't really see the logical process behind choosing to do this.

For any two data sets representing the same thing, it could be possible (even likely) that one set of clusters pre-representative-point-moving for one data set would be the same as the set of clusters post-representative-point-moving for the other.

Could someone please help explain in more detail the reasoning behind doing this? (Beyond just the basic pseudo-algorithm I have seen.)

My thoughts

I think that when moving the representative points towards the centroid of each cluster, this is equivalent to shrinking the boundary of the cluster. Once this is done, the data points that remain outside of the boundary are eliminated as clusters. But I'm not sure if this is correct.

• What is exactly the problem 'CURE' solves? Could you provide a reference to some text defining 'CURE', i.e. not a video? (video's are generally hard to reference and skim through, which makes answering your question harder) Feb 21 '18 at 10:41

If I'm understanding your question correctly, you are interested in why the representative points are chosen as such, why they are merged and why this works. I'll first go over some background for CURE, then I focus on this particular question.

## Background: why CURE?

I think we should start with the intention of CURE. To see that, we look at slide 14:

Here, CURE is compared with BIRCH and MST. We see that BIRCH succeeds in identifying the top ellipsoid pair as different, but fails to detect the large disk as a single cluster. BIRCH seems to only support same-sized clusters, So BIRCH doesn't make some clusters big enough and others too big. MST successfully classifies the disk as a single cluster, but fails to separate the ellipsoids on top. MST makes the clusters too big.

So, BIRCH is an attempt at trying to 'hit' the sweet spot between BIRCH and MST, in the hope of creating better clusters. In this example, it seems to be working pretty well.

Alright, back to the main question, why are the representative points handled as such? Suppose CURE would output the BIRCH result as an intermediate step. It then looks at the representative points of the light-blue and black half-disks. As the representative points are close, CURE would decide to merge these two half-disks into a full disk, which is good.

Okay, that's nice and all, but what prevents CURE from merging the two ellipsoids above, as BIRCH does? CURE doesn't do this (or is at least unlikely to do so), as the representation points are well scattered. This means that it is only likely that two clusters that are touching each-other on a location with high density get merged (as otherwise many representatives being close has low probability). As the two ellipsoids only touch each-other at points with low density, CURE (with carefully chosen parameters, no doubt) detects them as different.

## How to merge?

We've seen that CURE sometimes has to merge two smaller clusters into a bigger one. The question is how to handle the representative points. The simplest way to do this is to simply add them to the new cluster. But this isn't a good idea. For their original clusters, the representation points were well scattered. But if we simply use the same points for our merged cluster, this is no longer the case.

To see this, consider the example of the two half-disks in the clustering provided by BIRCH. Suppose that the representation points form the outline of a half-disk slightly smaller than the ones given. Now, if we merge the clusters, the representation points lie a bit far away from the center. They are no longer well scattered.

This is a problem, because if there were another disk-like cluster nearby ('connected by a chain of outliers', as the authors would say), the fact that the representation points are too far to the edge of our newly merged disk means we're likely to put the two disks in a single cluster. Note that this process can occur many times at different hierarchical levels, so if we don't solve this, we won't get nice results.

So, the solution is to move the representation points a bit closer to the center, as this makes them more well-scattered and therefore decreases the probability that we make a bad merge.