---
# System prepended metadata

title: k-nearest neighbors algorithm(K-NN)
tags: [Optimization Algorithms, K-NN]

---

---
tags: Optimization Algorithms,K-NN
---
# k-nearest neighbors algorithm(K-NN)
- It is a Supervised learning algorithm 
- K-NN used to solve classification problem. 
- K-NN algorithm is classification algorithm that takes a bunch of labelled data, and use them to learn how to label other points
- Cases that are near each other are said to be “neighbours”
- K-NN comes under lazy learner category.

##  K-nearest Neighbors algorithm steps:

1.	Pick a value of k

3.	Calculate distance of unkonwn cases from all cases using Euclidian distance
$Eculidian\ distance= \sqrt{(x_2 - x_1)^2 +(y_2 - y_1)^2 }$ 


4.	Select the nearest neighbours based on calculated distance
5.	Predict the unknown data point using the most voted value from nearest neighbour

## Adavantages:
Easy for implementation 
More effective if training data is large
## Disadavantages:
Selecting v value is challenging
Computation east is high
## Application
Pattern regression 
sensitive to scale data

## Example
Let's assume this is sample for analysis

| $$ x_1 $$ | $$ x_2 $$ | classification |
| -------- | -------- | -------- |
| 7     | 7     | bad     |
| 7     | 4     | bad     |
| 3     | 4     | good    |
| 1     | 4     | good    |

$Let's\ predict for\ new \ data\ point \ x_1=3,x_2=7$

**assume** k=3

Using Eculidian formula
$\sum_{i=0}^n \sqrt{(x_2 - x_1)^2 +(x_2 - x_1)^2 }$

| $$ x_1 $$ | $$ x_2 $$ | distance |
| -------- | -------- | -------- |
| 7     | 7     | $$(7-3)^2+(7-7)^2 = 6$$     |
| 7     | 4     | $$(7-3)^2+(4-7)^2 = 25$$     |
| 3     | 4     | $$(3-3)^2+(4-7)^2 = 9$$    |
| 1     | 4     | $$(1-3)^2+(4-7)^2 = 13$$    |

Now sort distance based on calcuated value by compared k=3

| $$ x_1 $$ | $$ x_2 $$ | distance            | Rank | k <3 |
| --------  | --------  | --------            |------|---   | 
| 7     | 7     | $$(7-3)^2+(7-7)^2 = 6$$     | 1    |yes   |
| 7     | 4     | $$(7-3)^2+(4-7)^2 = 25$$    | 4    |no    |
| 3     | 4     | $$(3-3)^2+(4-7)^2 = 9$$     | 2    | yes  |
| 1     | 4     | $$(1-3)^2+(4-7)^2 = 13$$    | 3    |yes   |

Now select the observation which are nearst to k=3 and consider same value from calssificaiton column

| $$ x_1 $$ | $$ x_2 $$ | distance            | Rank | k <3 | calssificaiton of nearest neghbour|
| --------  | --------  | --------            |------|---   | -------
| 7     | 7     | $$(7-3)^2+(7-7)^2 = 6$$     | 1    |yes   | Bad
| 7     | 4     | $$(7-3)^2+(4-7)^2 = 25$$    | 4    |no    | --
| 3     | 4     | $$(3-3)^2+(4-7)^2 = 9$$     | 2    | yes  | Good
| 1     | 4     | $$(1-3)^2+(4-7)^2 = 13$$    | 3    |yes   | Good


Now by considering simple majority
Good --> 2 and Bad --> 1 we can conclude for new data point $x_1 =3 and x_2 =7$ is belongs to Good category.