4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You can define custom metrics in sklearn stackoverflow.com/q/21052509/58737 $\endgroup$ – Pratik Deoghare Apr 20 '19 at 11:29
  • $\begingroup$ Can Q_i be calculated from x_i? $\endgroup$ – Pedro Henrique Monforte Apr 20 '19 at 16:58
  • $\begingroup$ @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. $\endgroup$ – LemonPi Apr 20 '19 at 18:12
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – LemonPi Apr 20 '19 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.