4
$\begingroup$

Imagine a data set with three features $A, B, C$.

A nearest neighbor algorithm can find what array $[a,b,c]$ is most similar (in terms of a given metric, e.g. euclidean distance) to $[x,y,z]$.

What method can be used to find the most similar array, given the requirement that one of the features is changed in a given direction, e.g. $[x, y+\epsilon, z]$. The original array $[x,y,z]$ is not allowed to be returned again.

The simplest way I can think of would be to perform nearest neighbor searches with increasing $\epsilon$ until a new array is found. However, this would be computationally expensive. What is a better method?

Improve this question
$\endgroup$
4
  • $\begingroup$ If you imagine a 2D example, are you asking what would be closest if you move a new point up one axis? In which case doesn't the value of $ϵ$ determine which is the nearest neighbor? $\endgroup$
    – tea_pea
    Oct 24, 2017 at 9:09
  • $\begingroup$ In a 2D example, I would like to find my nearest neighbor as I travel along one axis. Reduce my example to two features, $[A,B]$. I would like to find the point that keeps $A$ as constant as the data in the dataset allows, but with a higher or lower value for B. $\endgroup$
    – Woppe
    Oct 24, 2017 at 9:15
  • $\begingroup$ So the nearest neighbor given that your point can move along the WHOLE axis? In that case why not just exclude the feature you want to adjust and do NN with the remaining feature? $\endgroup$
    – tea_pea
    Oct 24, 2017 at 9:17
  • $\begingroup$ Search along the axis until the first (nearest) occurence is found. $\endgroup$
    – Woppe
    Oct 24, 2017 at 9:24

1 Answer 1

Reset to default
2
$\begingroup$

Let's consider $Q=(x,y,z)$ to be your query point and $P_i=(a_i,b_i,c_i)$ are all possible neighbors for $i=1,\dots n$.

For the first call, it is clear that you had to calculate the distance for all possible neighbors $d_i=||Q-P_i ||$.

If you change the $Q'\gets Q + \Delta$ where $\Delta=(0,\epsilon,0)$ or any other vector.

Then, we can analyze $$ d_i' = ||Q+\Delta - P_i|| $$

We can inspect the bounds as follows: $$ d_i'\in [d_i-||\Delta||, d_i+||\Delta||] $$ considering that in best case, $\Delta$ is towards $P_i$, and that in the worst case $\Delta$ goes directly from $P_i$.

Using this, you can calculate the upper bound for $$\min_i d_i'\leq \min_i (d_i+||\Delta||)$$ Note that: $$ \min_i (d_i+||\Delta||) = ||\Delta|| + \min_i d_i $$ where $\min_i d_i$ is the distance to the nearest neighbor in the previous step.

Having this bound, you can filter only those indices that have a chance to outperform it, i.e. $$ \left\{i':d_{i'}-||\Delta||\leq ||\Delta|| + \min_i d_i\right\} $$

If you have sorted the nearest neighbors in the first step, your list of candidates will be on the top.

Among these indices, you can find the new nearest neighbor.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do I understand you correctly, that this approach filters the data, and that once that step is performed, a common nearest neighbor search is to be applied? $\endgroup$
    – Woppe
    Oct 24, 2017 at 11:19
  • $\begingroup$ Yes, that's the case. $\endgroup$
    – Karel Macek
    Oct 24, 2017 at 12:07

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.