What are some "clustering" algorithms? (but not the type of clustering you're thinking about)

Question

Given a set of $N$ points $\{x\mid x \in \mathbb{R}^D\}$ for some dimensionality $D$ I want a fast algorithm which will give me all unique subsets which satisfy:

• $\|x_{i} - x_{j}\|_{D} \leq M$ (all pairs of points in the subset are close to one another)
• $|\{x\}| \ge n$ (there is some minimum number of points in the subset)

In normal-speak: I want to find all sets of closely bunched points on a map and be able to point to them and say "that's a set of closely clustered points, we should look into it!".

The naive approach would be to check every point, and see if it has $n$ or more points within $M$ distance of it. But I feel like there should be a more efficient way.

Then, in the context of my map application, the follow up would be to do some sort of non-maximum suppression on overlapping subsets.

Answer 1

You are trying to list all cliques of a graph. You said that $x \in \mathbb{R}^2$, which greatly simplifies the problem: the graph is a unit disk graph, for which the maximum clique problem is polynomial. However, the number of cliques may be exponential.

In practice, it is likely easier to apply a heuristic or a generic maximum clique algorithm rather than rolling your own. The exponential worst case can be avoided by listing a limited number of clusters for each point.

Links:

• a heuristic to list all cliques on unit disk graphs
• a polynomial algorithm for the maximum clique problem

Answer 2

The naïve method you describe (loop over all points, select those that have more than $n$ other points within distance $M$ of them) is actually not a bad choice, as long as you store your points in a suitable spatial data structure (such as something based on a quadtree) that makes finding and/or counting nearby points a cheap operation. One advantage of this approach is that it will let you vary your definition of a cluster (e.g. to something like "the $n$-th nearest point is less than $f(n)$ distance away") fairly easily without having to switch to a different algorithm or a different data structure.

That said, for the specific definition you give, you don't really need a quadtree. The simplest spatial data structure sufficient for finding clusters according to your definition is just a regular grid.

As you note in the comments, simply dividing the map into a grid of squares (or triangles or hexagons) and binning each point into the square it's located in could fail to correctly detect clusters located near a grid boundary. However, the solution is simple: just count points located near a boundary in both of the squares on each side of the boundary.

In fact, if you make your grid consist of squares with a side length of (at least) $M$ units, you can use the following simple binning algorithm:

• For each point, find the location of the closest grid intersection (i.e. the closest corner point between four grid squares). You can do this with simple division and rounding of the point coordinates. Then add the point to each of the four grid squares touching the intersection.
• Once all points have been binned, look for squares with $n$ or more points. Not all such squares will necessarily contain a cluster according to your definition (and they might also contain several disjoint clusters), they are at least "weakly clustered" in the sense of having $n$ or more points at most $2\sqrt2 M'$ units apart (where $M' \ge M$ is the side length of your grid squares). What is guaranteed, however, is that all the points in any cluster with diameter at most $M$ are assigned to at least one common grid square.

In fact, for data visualization, you might not even need to find the actual clusters — it might be sufficient to plot the number of points assigned to each grid square by the algorithm above.

Note that, if your map is very large compared to your cluster diameter $M$, and your points are sparsely scattered on it, it may be inefficient to store the entire grid as a dense matrix or array. Instead, use a sparse array data type so that you only need to store data for squares that actually have points assigned to them. (This will also save time in the second step, since you can only iterate over the squares that actually have something in them.) You can also save a bit of storage space if you, instead of assigning each point to four adjacent squares, actually assign it to only one of them, but then, in the second step, look for groups of four adjacent squares with $n$ or more points.