Best way to fuse clusters smaller than a certain size in a distributed way?

Question

I have X clusters of size (n1,n2...,nX) and I want to fuse small clusters with less than T members with the nearest adjacent cluster i.e. the nearest neighboring cluster.

The problem is when I've got two small neighbor clusters, A->B and B->A which create an infinite loop.

I try to avoid that by removing one of those which have this property [(A,B),(B,A)].

But is there a better way to accomplish this task in sequential way ?

Is it possible to do the trick in distributed way ( Spark ) ?

Answer 1

My suggestion is just a greedy brute force approach. I am sure that more efficient solutions may exist, but it may be a first step towards your final solution.

Store in a table, for each cluster which size is lesser than T, the distance to its closest neighbouring cluster and the ID of that closest cluster.

Now, sort the table entries in ascending distance order. Merge the cluster in the first entry with its closest neighbouring one. If the closest cluster also had an entry in the table, and its size got larger than T, remove its corresponding entry. Finally, update all the entries of the table, and sort them in ascending distance order again.

Repeat the steps above until there are not more entries in the table.

Answer 2

I'm not really seeing the issue with an infinite loop. It seems like you are looping through your clusters and finding all the clusters that need to be merged, then in a separate loop doing the merging and are getting tripped up when two clusters are flagged in such a way that they both need to be merged into one another. Instead, you can think of this as more of a queue.

Then you can loop through one time and merge the small clusters with their neighbors and then destroy them.

Imagine you have a cluster class with attributes: membercount, members, and nearestNeighbor, and methods addMembers() and destroy().

Then you could do something like:

for (cluster in clusterList):
    if cluster.membercount<T:
        cluster.nearestNeighbor.addMembers(cluster.members)
        cluster.destroy()

This will only cycle through clusterList one time and will instantly merge and destroy the clusters that are smaller than T.

Assuming you have experience with object oriented programming, this would be pretty straightforward to implement. Even if you do this within an array, you can just pop clusters after you merge them with other clusters.

Hope this helps!