# How to obtain the class conditional probability when using KNN classifier?

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) 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. – shn Jan 28 '14 at 14:17
• Should we learn the coefficients $B_0$ and $B_1$ ?! – 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.

• 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 ? – shn Jan 28 '14 at 14:19
• In that case, you can rely on smoothing: For example, one commonly used trick is to use the class probability in the whole data. – Weiwei Jan 29 '14 at 9:05
• 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. – shn Jan 29 '14 at 9:27
• 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 ? – shn Jan 29 '14 at 13:44
• Yes. I would say avoiding 0 probability is a good practice. – Weiwei Jan 29 '14 at 14:03