# K Nearest Neighbour with different distance matrix to each datapoint

I'm wondering if there is library support in python (such as sklearn) for doing KNN on a data set that has a custom distance matrix (positive definite) for each data point (x is a query point, $$x_i$$ is a data set point): $$d(x,x_i) = (x-x_i)^TQ_i(x-x_i)$$

I know that for a fixed positive definite matrix for all data points, this is a metric that I can transform into $$Q = A^TA \ \ \ \ \ \ \ d(x,x_i) = (Ax - Ax_i)^T(Ax - Ax_i)$$ Which I can compute via normal KNN by first transforming the input space via multiplying $$A$$.

My problem of having a separate matrix for each data point came up because I have a covariance around the neighbourhood of each point. KNN can then be interpreted as what are the most likely neighbourhoods this query point lies in. If a neighbourhood doesn't vary along a dimension then we should penalize difference along that dimension highly in terms of increasing distance.

• You can define custom metrics in sklearn stackoverflow.com/q/21052509/58737 Apr 20 '19 at 11:29
• Can Q_i be calculated from x_i? Apr 20 '19 at 16:58
• @PedroHenriqueMonforte No, that is part of the problem. If so I could use the metric keyword in sklearn. One idea I have is to append the $Q_i$ to $x_i$ and then use a custom metric function to extract each part. The problem is that I don't think this is an actual metric (triangle inequality doesn't make sense here), so k-d trees or ball trees wouldn't necessarily work. Apr 20 '19 at 18:12

As pointed out by @Pratik Deoghare you can create a custom metric on sklearn kNN and you can see how in the link he provided.

But you want a function to that is different for each $$x_i$$, that is not a metric in the mathematical sense, but I can see how that could benefit the algorithm either way.

the function you pass as a metric (see how in the link) could be defined as

def creatmydist(AllA):
Alist = AllA
def mydist(x, y):
nonlocal Alist
if x[-1] == 0: i = y[-1]
else: i=x[-1]
A = Alist[i]
x = np.dot(A,x[0:len(x)-1])
y = np.dot(A,y[0:len(y)-1])
return np.dot(x-y,x-y)
return mydist


Where AllA should be a list with all $$A = (A^T)^{-1}Q$$ and every $$x_i$$ should have as last element it's index $$i$$

• I considered doing this (comment on the original question), but I don't think k-d trees or ball trees would work without a proper metric. I'll give it a test and update when I have some time! Apr 20 '19 at 21:35