# Why KNN is a non linear classifier ?

How do we decide if a classifier is linear or non linear ?

What property/characteristic makes a classifier linear or non linear ?

Eg: Why SVM is a linear classifier ? Why Logistic Regression is linear classifier even though it uses logistic function which is a non linear function ?

• The linearity of the classifier refers to its decision boundary. Is it a hyperplane or not? (And SVM's is generally not linear.) – Emre Oct 25 '15 at 1:36
• Thanks @Emre , so as per your answer, if the feature space is say 6 dimensional and the decision boundary is 5 dimensional then it is a linear classifier. Am I right ? – mach Oct 25 '15 at 1:48
• So it doesn't depend on the sixth one? It could still be nonlinear in the other five. – Emre Oct 25 '15 at 1:54

## 1 Answer

A classifier is linear if its decision boundary on the feature space is a linear function: positive and negative examples are separated by an hyperplane.

This is what a SVM does by definition without the use of the kernel trick.

Also logistic regression uses linear decision boundaries. Imagine you trained a logistic regression and obtained the coefficients $\beta_i$. You might want to classify a test record $\mathbf{x} =(x_1,\dots,x_k)$ if $P(\mathbf{x}) > 0.5$. Where the probability is obtained with your logistic regression by: $$P(\mathbf{x}) = \frac{1}{1+e^{-(\beta_0 + \beta_1 x_1 + \dots + \beta_k x_k)}}$$ If you work out the math you see that $P(\mathbf{x}) > 0.5$ defines a hyperplane on the feature space which separates positive from negative examples.

With $k$NN you don't have an hyperplane in general. Imagine some dense region of positive points. The decision boundary to classify test instances around those points will look like a curve - not a hyperplane.

• Thanks ... but with a hyperplane we can classify into only two classes ( ie positive or negative) , then how do these classifiers (Logistic which is binary) handle multilabel classifications ? – mach Oct 25 '15 at 2:07
• Yes hyperplanes deal with binary classification problems. There are two ways to use hyperplanes for multiclass classification: one vs one, and one vs all. Have a look at this wiki page: en.m.wikipedia.org/wiki/Multiclass_classification – Simone Oct 25 '15 at 2:14