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?

  • $\begingroup$ What are c points? $\endgroup$ – rapaio Jul 6 at 18:51
  • $\begingroup$ I slightly reworded the question. $\endgroup$ – Lepidopterist Jul 6 at 19:46
  • $\begingroup$ 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)$ ? $\endgroup$ – rapaio Jul 8 at 13:09

Your Answer

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

Browse other questions tagged or ask your own question.