# Algorithm for clustering points into pairs (exactly two) by proximity without re-use

I have a reasonably large list of centroids that I want to cluster into groups of two by proximity (minimizing proximity).

I've explored k-means, which does cluster them by proximity, but the count of members in each group varies. With k-means you set a number of clusters, not a number of members in each cluster.

The nearest-neighbor problem solves this issue for two items from the set, but not against the entire data set.

K-nearest neighbors seems to break them into groups of N, but it appears to allow for points to be reused. In my scenario there can be no overlap.

Is there a particular algorithm, or suite of algorithms designed to address this? I'm pretty handy when I know what I'm working against, but I don't have a good sense of how to approach the problem.

To add more about the context and what we're trying to solve:

The points represent a number of sites throughout the USA. Each of these sites is a competitor (supply). Independently, we've aggregated demand (from census data, etc). We want to average the nearest pairs so that we can use the aggregated supply when calculating our supply/demand indexes for a given spatial extent (defined by the demand polygons).

We need to use at least two points so that individual data from a given site is obscured. This is a licensing/privacy requirement. We would otherwise analyze every point individually. We don't want to use more than two, because that further obscures the data. By using two, we adhere to licensing requirements, while minimizing the effect of averaging across a cluster.

• Since many different valid solutions are possible, and there is not yet sufficient information to recommend any one of them, could you edit this question to provide some context and any other information to help us figure out why you are trying to do this? What will the clusters represent? What objective is this clustering analysis trying to achieve? May 18, 2015 at 20:27
• @whuber, thank you, I've added more detail. Let me know if there is any additional information that would be relevant. May 18, 2015 at 20:43
• (+1) The thread at gis.stackexchange.com/questions/31236 concerns a similar problem with a similar objective. If you could relax your requirement to form clusters of two, and instead allow clusters of two or three, then some of the solutions there would apply without change. There remain plenty of alternative approaches, ranging from greedy algorithms to partitioning space-filling curves to simulated annealing and much more. May 18, 2015 at 20:55
• @whuber, oh wow, that's great. I think 2 or 3 would work just fine. Thank you very much. May 18, 2015 at 20:59
• Sounds like a modified travelling salesman problem...complicated because just because point A is closest to B, it does not imply that B is closest to A...additionally even if A is closest to B and B is closest to A, it may not mean that they should be paired! @whuber : great solution on the linked question! May 18, 2015 at 22:31