Using the KNN classifier, given a test data-point $x$, how do we get the probability of membership of $x$ to each class $y_i$, that is the probabilities $P(y_i | x)$ for $i = 1, 2, .., n$ (where $n$ is the number of classes).


k-NN classifiers do not output probabilities.You would need to transform distance to a probability yourself, for example by fitting a logistic regression model on the distance.

The output of a k-NN classifier is in terms of distance of $\mathbf{x}$ to nearest member, e.g. $f(\mathbf{x}) = d \in \mathbb{R^+}$. You can transform this distance $d$ to a probability using logistic regression, e.g. find optimal coefficients $\beta_0$ and $\beta_1$ such that $$g(d) = \frac{1}{1+exp(\beta_0+\beta_1d)} \in [0, 1],$$

is a well calibrated probability of class membership. Your total classification would then resemble the following $g(f(\mathbf{x}))$.

  • 1
    $\begingroup$ (1) What is $B_0$ and $B_1$ (how to set them) ? (2) what you call $d$ is the mean distance from $x$ to the $k$ nearest points belonging to a given class $y_i$ (in which case it is $d_i$) ? or is it the mean distance to the instances belonging to the majority class in the $k$ neighbourhood of $x$ ? Please give more details. Thanks. $\endgroup$ – shn Jan 28 '14 at 14:17
  • $\begingroup$ Should we learn the coefficients $B_0$ and $B_1$ ?! $\endgroup$ – shn Jan 29 '14 at 13:45

I'd like to share a different way to get the class conditional probability, which is different from what Marc proposed.

For an instance $\mathbf{x}$, assume we have $N_i$ instances belong to class $Y_i$ in the neighborhood. Then we define

$$P(Y_i \, | \, \mathbf{x}) = \frac{N_i + s}{K + Cs},$$ where $K$ is total number of instances in the neighborhood, $C$ is the total number of classes, and $s$ is the smoothing parameter. The smoothing is used to avoid 0 probabilities.

It is kind of a nonparametric way to get the conditional probability.

  • $\begingroup$ If some classes do not appear in the $k$ neighbourhood of $x$ (e.g. no instance belonging to a given class $y_i$ is among the $k$ nearest instances to $x$); how would you do in this case ? $\endgroup$ – shn Jan 28 '14 at 14:19
  • $\begingroup$ In that case, you can rely on smoothing: For example, one commonly used trick is to use the class probability in the whole data. $\endgroup$ – Weiwei Jan 29 '14 at 9:05
  • $\begingroup$ What do you mean by "using the class probability in the whole data" ? Can you please give more details (by editing your current answer) ? Thanks. $\endgroup$ – shn Jan 29 '14 at 9:27
  • $\begingroup$ Using that kind of smoothing, we will just get a the same probability values for all classes having $N_i = 0$, so instead of having $P(y_i|x) = 0$, we will get $P(y_i|x) = \frac{s}{K + C \times s} = constant$. Does that change something compared to the 0 probabilities case ? $\endgroup$ – shn Jan 29 '14 at 13:44
  • $\begingroup$ Yes. I would say avoiding 0 probability is a good practice. $\endgroup$ – Weiwei Jan 29 '14 at 14:03

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.