How would I separate a data set into a large number of pairs? I have $n$ observations in $\mathbb{R}^2$ (where $n$ is large and even), representing points in physical space. What I am trying to do is to produce a set of $\frac{n}{2}$ pairs, such that the distances between paired points are minimised.
My first thought was that this seems to be a clustering problem. I first considered k-means clustering; indeed I even found a module for Python which performs constrained k-means clustering, which allows the cluster sizes to be fixed. However, while I found that module to be efficient (and produces good results) if the clusters are relatively large, when I attempted to use the algorithm to split the data into $\frac{n}{2}$ clusters with two members in each cluster, it was incredibly slow. It also produced results which seemed far from optimal, even after initialising the algorithm with many different random starting points and selecting the best result. Therefore, I'm wondering whether a different approach may be required - and whether this is even a clustering problem at all. I'd appreciate any advice on a potential alternative way to solve this problem.

One way of solving this is to treat it as a graph problem. Use the $n$ observations as the graph vertices and the distances between the observations as the edges. You can then treat this as minimum cost/weight perfect matching problem, which is to find the lowest cost set of edges that connect each vertex with exactly one other vertex. See also btilly's answer to "Given a group of people, where each pair has a value, how can I find the configuration of pairings with the least total value?" on Stack Overflow.
For a python implementation of an algorithm to solve this problem see the NetworkX package, which uses the Blossom algorithm. For more on the Blossom algorithm see Kolmogorov, V. Blossom V: a new implementation of a minimum cost perfect matching algorithm.
Note: if you have further questions about this method, try either Stack Overflow for programming/implementation issues or Computer Science for questions about the algorithm.
