Filtering away nearby points from a list

Question

I half-answered a question about finding clusters of mass in a bitmap. I say half-answered because I left it in a condition where I had all the points in the bitmap sorted by mass and left it to the reader to filter the list removing points from the same cluster.

Then when thinking about that step I found that the solution didn't jump out at me like I thought it would. So now I'm asking you guys for help. We have a list of points with masses like so (a Python list of tuples, but you can represent it as you see fit in any language):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

Each tuple is of the form:

(x, y, mass)

Note that the list is sorted here. If your solution prefers to not have them sorted it's perfectly OK.

The challenge, if you recall, is to find the main clusters of mass. The number of clusters is not known. But you know the dimensions of the bitmap. Sometimes several points within a cluster has more mass than the center of the next (in size) cluster. So what I want to do is go from the higher-mass points and remove points in the same cluster (points nearby).

When I tried this I ended up having to walk through parts of the list over and over again. I have a feeling I'm just stupid about it. How would you do it? Pseudo code or real code. Of course, if you can just take off where I left in that answer with Python code it's easier for me to experiment with it.

Next step is to figure out how many clusters there really are in the bitmap. I'm still struggling with defining that problem so I might return with a question about it.

EDIT: I should clarify that I know that there's no "correct" answer to this question. And the name of the question is key. Phase one of the my clustering is done. Im in search of a fast, accurate-"enough" method of filtering away nearby points.

Let me know if you see how I can make the question clearer.

Answer 1

Just so you know, you are asking for a solution to an ill-posed problem: no definitive solution exists. That's fine...it just makes it more fun. Your problem is ill-posed mostly because you don't know how many clusters you want. Clustering is one of the key areas of machine learning and there a quite a few approaches that have been developed over the years.

As Arachnid pointed out, the k-means algorithm tends to be a good one and it's pretty easy to implement. The results depend critically on the initial guess made and on the number of desired clusters. To overcome the initial guess problem, it's common to run the algorithm many times with random initializations and pick the best result. You'll need to define what "best" means. One measure would be the mean squared distance of each point to its cluster center. If you want to automatically guess how many clusters there are, you should run the algorithm with a whole range of numbers of clusters. For any good "best" measure, more clusters will always look better than fewer, so you'll need a way to penalize having too many clusters. The MDL discussion on wikipedia is a good starting point.

K-means clustering is basically the simplest mixture model. Sometimes it's helpful to upgrade to a mixture of Gaussians learned by expectation maximization (described in the link just given). This can be more robust than k-means. It takes a little more effort to understand it, but when you do, it's not much harder than k-means to implement.

There are plenty of other clustering techniques such as agglomerative clustering and spectral clustering. Agglomerative clustering is pretty easy to implement, but choosing when to stop building the clusters can be tricky. If you do agglomerative clustering, you'll probably want to look at kd trees for faster nearest neighbor searches. smacl's answer describes one slightly different way of doing agglomerative clustering using a Voronoi diagram.

There are models that can automatically choose the number of clusters for you such as ones based on Latent Dirichlet Allocation, but they are a lot harder to understand an implement correctly.

You might also want to look at the mean-shift algorithm to see if it's closer to what you really want.

Answer 2

It sounds to me like you're looking for the K-means algorithm.

Answer 3

As I mentioned in the comment to your question, the answer is based on whether or not mass can be considered scalar in this context. If so, color based solutions are probably not going to work as color is often not taken as being scalar.

For example, if I have a given area with 1 point of high mass, is that the same as having the same area with 10 points of 1/10 the mass? If this is true, mass is not scalar in this context, and I would tend to look at an algorithm used for spatially gouping similar non-scalable values, e.g. voronoi diagrams.

In this case, where two adjacent voronoi areas have a close enough mass match and distance, they can be clustered together. You could repeat this to find all clusters.

If on the other hand, your mass is scalable, or that the mass at an unknown position can be interpolated from surrounding points, I would tend to triangulate and contour the input data and use areas between contours to find clusters of similar mass.

Answer 4

This sounds like color quantization, where you reduce the number of colors in an image. One way would be to plot the colors in space, and combine clusters into the center (or a weighted average) of a cluster.

The exact name of the algorithm that triggered this memory fails me, but I'll edit the answer if it pops up, but in the meantime, you should look at color quantization and see if some of the algorithms are useful.

Answer 5

Start with the "Convex Hull" problem. You're also looking for some "convex hull"-like clusters.

Note that "clusters" is vague. You have an average mass across your field. Some points have above average mass, and some below average. How far above average means you've found a cluster? How far apart do nodes have to be to be part of a cluster or a separate cluster?

What's the difference between two mountain peaks and a ridge?

You have to compute a "topography" - joining all points with equal density into regions. This requires that you pick a spot and work your want out from a point radially, locating positions where the densities are equal. You can connect those points into regions.

If you picked your initial point wisely, the regions should nest. Picking your starting point is easy because you start at local highs.

Answer 6

Since you are already talking about mass, why not a gravity based solution. A simple particle system would not need to be super accurate, and you would not have to run it for too long before you could make a much better guess at the number of clusters.

If you have a better idea about cluster numbers, k-means nearest neighbour becomes feasible.