Let's consider a classifier that for each new sample ($x_i$),

  • finds the nearest neighbor ($x'^k_j$) for each class $k$ present in the training data
  • computes the corresponding distances: $d(x_i, x'^k_j)$
  • computes the decision function as some function $\varphi$ of these distances: $\varphi(d(x_i, x'^0_j), d(x_i, x'^1_j), ..., d(x_i, x'^k_j))$.

For instance, if k=2, and $$\varphi(d_1, d_2) = \begin{cases} 1 & \text{if} \ d_1 \le d_2 \\ 0 & \text{otherwise} \end{cases}$$ the corresponding decision function would be equivalent to 1-NearestNeighbor (NN).

Such classifier appears be somewhat at the intersection of 1-NN, nearest centroid, and kernel methods. I'm wondering if it has a standard name, and looking for any literature on how the function $\varphi$ should be chosen.

Edit: I present this as a classification problem, but really I'm using the corresponding decision function to do ranking, so it's more of a ranking problem and $\varphi$ is in general a piecewise continuous function (not discrete).


1 Answer 1


I never heard a name for this algorithm but I have some ideas about this:

  • if you choose as your function the min function is the same as 1-NN, apart from the fact that you are looking th nearest neighbour of every class, and this makes it too expensive.
  • if you don't choose the min function you have many alternatives, but in my opinion if you want as output just one class you won't have many benefit from this
  • the thing i like in this approach is that you can decide not to have as output a class, but consider this as a soft assign (like you would do in clustering). This can be useful when classes are not really distinct or maybe the same unit can be in multiple classes. An easy example can be in music classification a song that is not only in a category but a mix of some.
  • $\begingroup$ Thanks for your response! Yes, this could be used for soft assign. Sorry my question wasn't very clear (I edited it). Fundamentally I'm using the decision function to do ranking. I.E. I'm trying to rank the input sample based on the distances to training classes, and so do need some function that would convert individual distances into a scalar (value of the decision function / ranking score). $\endgroup$
    – rth
    Commented Apr 20, 2017 at 9:53
  • $\begingroup$ it's still not clear to me. do you want to get a ranking between the classes?if you can explain better the idea of rank that you want $\endgroup$
    – Gio_cor
    Commented Apr 20, 2017 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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