Find the most similar pairs from two data sets

Question

To cut a long story short, I have two datasets with $n$ data vectors each. Every vector contains a lot of features/variables.

I am looking for a method of finding $n$ pairs that contain two data vectors (one data vector from one data set and one vector from the other) in a way that minimize a norm, say L1. So each pair should contain the two most similar - in some sense - vectors, one from each data set. What's more there should be no repetition in pairs, one data vector should be used only once.

I was thinking about k-means and hierarchical clustering. But have no idea how to deal with the constraint that I need one vector from one data set and another from a second one. I also had an idea for a brute force approach, first calculate matrix $n$ by $n$ with norms of every possible pair. And then find the minimum sum of those norms, but this approach fails because of its computational complexity. Probably my thinking went in the wrong direction.

I guess it is simple if one can find the right approach, that I can't.

Edit: To add some context let's say I have two datasets (from two different locations) with features that describe weather in the way that one vector of data contains information (averaged over the day) about a temperature, humidity and so on. I need to find two days which are the most similar to each other from those two locations (data sets), but in the way that if one day from one location has been used it can not be used one more time in another pair.

Answer 1

This is a standard nearest-neighbor matching without replacement problem, well studied in the causal inference literature (though usually one of the datasets is much larger than the other). You do need to compute the distance between individuals if you want to be able to minimize a norm. Greedy nearest neighbor matching as described by Demetri is an option, but there is a variation called optimal matching that uses network flows to minimize the sum of the distances between units in a pair. It is described in Hansen & Klopfer (2006) and implemented in the R package optmatch. You supply the pairmatch() function a distance matrix and it will find the optimal pairings.

Answer 2

This is perhaps not the most efficient but it is a greedy approach to the problem.

Computation of the distances between observations is the most expensive part. However, you need only do it once and store it in a distance matrix where $M_{i,j}$ is the distance between vector $i$ and $j$.

Call the datasets A and B. Let the rows of M (the distance matrix) correspond to vectors in A, and let the columns correspond to vectors in B. The strategy is as follows. For each row in M:

• Argsort the row of M. This will give us an array in which the first element is the closest, the second element is the second closest, etc.

• Eliminate any columns which have already been selected by the procedure. If you have not selected any columns, select the first element in the argsorted row. Else, select the first element in the arg sorted row.

• Repeat until done.

Here is an implementation in python

import numpy as np
from scipy.spatial.distance import cdist

def find(A, B, dmat):

    # Initialize a place to store what columns we select so we can filter out the ones we choose
    selected = []
    
    # Initialize a place to store the output
    pairs = np.zeros((len(A), 2))
    
    for i in range(len(A)):
        # Sort the observations in descending order
        choices = dmat[i].argsort()
        
        # Eliminate those observations already selected
        remaining_choices = choices[~np.isin(choices, selected)]
        
        # Append the observation to select
        choose = remaining_choices[0]
        selected.append(choose)
        
        # Select the closest observation
        pairs[i] = [i, choose]
    return pairs

Here is a minimal working example. Let's say A = np.array([1,2,3].reshape(-1,1) and B = np.array([1, 0, 4]).reshape(-1,1). The first observation in A should be linked to the first observation in B. The second to the second, and the third to the third.

The result of the algorithm is (keeping in mind that python is zero indexed)

dmat = cdist(A, B)
find(A, B, dmat)
>>>array([[0., 0.],
       [1., 1.],
       [2., 2.]])

as expected.

This implementation takes about 194 ms to run on a 1000 by 1000 dataset.

A = np.random.normal(size=(1000, 1000))
B = np.random.normal(size=(1000, 1000))
dmat = cdist(A, B)
%timeit -n 10 find(A, B, dmat)
>>>194 ms ± 2.21 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

I'm no computer scientist, but some experiments seem to point towards this running in $\mathcal{O}(n)$ time complexity. A brute force approach would be $\mathcal{O}(n^2)$ since for every element in A you would compute the distance to every element in B to find the closest one. Keep in mind that this is because the approach is greedy.