# Learning distance metric from output of knn

Consider a set $$\mathcal X$$ of points $$\{x_1,\dots,x_n,x_{n+1},\dots,x_{n+m} \}\subset \mathbb R^p$$. Let $$A$$ be some $$p\times p$$ matrix, unknown to you. Consider the set $$\mathcal X_A:=\{y_1,\dots,y_{n+m}\}:=\{Ax_1,\dots, A x_{n+m} \},$$ where the $$y_i$$ are unknown to us also.

For each $$i\in[1,n],$$ we are given the closest point to $$y_i$$.

Goal: For each point in $$\{y_{n+1}, y_{n+2}, \dots, y_{n+m}\}$$, supply a good guess for the closest point to that point.

Another way to look at this is that we are given an incomplete output to a knn algorithm, which was applied after some linear transformation of the feature space, and we are being asked to complete the output by perhaps reverse engineering the pre-processing.

My Idea:

For each $$i\in[1,n]$$, construct a new dataset $$\mathcal X_i:=\{x_2-x_1,\dots,x_n-x_1\},$$ consisting of the feature differences to that point. Fit a decision tree (or random forest, or SVM or other classifer), which tries to predict membership in the set of nearest neighbors. Average these models across all $$i$$, so that given any new point, one can output for every other point a probability that it is the nearest neighbor, based on its feature differences. Finally, output the point with the highest probability.

Is there a better approach?

• What are c points? – rapaio Jul 6 at 18:51
• I slightly reworded the question. – Lepidopterist Jul 6 at 19:46
• You do not know A, and as a consequence you do not know $y_i$. Do you have any idea about the distance function: $d(y_i, y_j)$ ? – rapaio Jul 8 at 13:09