K-Nearest Neighbour

MACHINE LEARNING

10/9/2024

1

K-Nearest Neighbour

• The k-nearest neighbors (KNN) algorithm is a simple, easy-to-implement supervised machine learning algorithm that can be used to solve both classification and regression problems.
• K-NN algorithm assumes the similarity between the new case/data and available cases and put the new case into the category that is most similar to the available categories.
• K-NN algorithm stores all the available data and classifies a new data point based on the similarity. This means when new data appears then it can be easily classified into a well suite category by using K- NN algorithm.
• K-NN is a non-parametric algorithm, which means it does not make any assumption on underlying data.
• It is also called a lazy learner algorithm because it does not learn from the training set immediately instead it stores the dataset and at the time of classification, it performs an action on the dataset.
• KNN algorithm at the training phase just stores the dataset and when it gets new data, then it classifies that data into a category that is much similar to the new data.
• Also, It is known as:
• Memory-Based Reasoning
• Example-Based Reasoning
• Instance-Based Learning
• Case-Based Reasoning
• Lazy Learning

2

10/9/2024

K-NN Fundamentals

• Requires three things
• The set of stored records.
• Distance Metric to compute distance between records.
• The value of k, the number of nearest neighbors to retrieve.

​

• To classify an unknown record:
• Choose a value for K (number of neighbors).
• Calculate the distance (e.g., Euclidean) between the test point and all training points.
• Select the K nearest neighbors.
• For classification: Assign the class with the majority vote among the K neighbors. For regression: Take the average value of the K nearest neighbors.

3

10/9/2024

3

Distance Metrics

4

10/9/2024

K-Nearest Neighbor

• Features
• All instances correspond to points in an n-dimensional Euclidean space
• Classification is delayed till a new instance arrives
• Classification done by comparing feature vectors of the different points
• Target function may be discrete or real-valued

5

10/9/2024

K-? Nearest Neighbor

6

10/9/2024

1-NN

2-NN

3-NN

Select K

• If K is too small, sensitive to noise points.
• If K is too large, neighborhood may include points from other classes.
• Coming to your question, the value of k is non-parametric and a general rule of thumb in choosing the value of k is k = sqrt(N)/2, where N stands for the number of samples in your training dataset.
• Keep the value of k odd, so that there is no tie between choosing a class but that points to the fact that training data is highly correlated between classes and using a simple classification algorithm such as k-NN would result in poor classification performance.

7

10/9/2024

K-Nearest Neighbor…

8

10/9/2024

K-Nearest Neighbor…

• By calculating the Euclidean distance we got the nearest neighbors, as three nearest neighbors in category A and two nearest neighbors in category B.
• As we can see the 3 nearest neighbors are from category A, hence this new data point must belong to category A.

9

10/9/2024

K-NN Algorithm

1. Load the data
2. Initialize K to your chosen number of neighbors
3. For each example in the data
• Calculate the distance between the query example and the current example from the data.
• Add the distance and the index of the example to an ordered collection
4. Sort the ordered collection of distances and indices from smallest to largest (in ascending order) by the distances.
5. Pick the first K entries from the sorted collection.
6. Get the labels of the selected K entries
7. If regression, return the mean of the K labels
8. If classification, return the mode of the K labels

10

10/9/2024

Advantages

• The algorithm is simple and easy to implement.
• There’s no need to build a model, tune several parameters, or make additional assumptions.
• The algorithm is versatile. It can be used for classification, regression, and search.
• It is robust to the noisy training data
• It can be more effective if the training data is large.

11

10/9/2024

Disadvantages

• The algorithm gets significantly slower as the number of examples and/or predictors/independent variables increase.
• Always needs to determine the value of K which may be complex some time.
• The computation cost is high because of calculating the distance between the data points for all the training samples.
• Curse of Dimensionality: Performance degrades with high-dimensional data (large number of features).

​

12

10/9/2024

Example1

• Consider a dataset of health status as given in Table. What will be the status of a sample (180, 65).

13

10/9/2024

Example 1…

14

10/9/2024

K=1, Healthy; K=2, Healthy; K=3, Healthy

Test Sample :(180, 65).

Example 2

15

10/9/2024

Age

Loan$

• Sanction of loan amount

K-NN Classification

16

10/9/2024

K-NN Regression Example

• A dataset contains the following points, where the X column represents the input features and the Y column represents the target values (for regression):

​

​

​

• You are asked to predict the target value Y for a new input X = 3.5 using K = 3 nearest neighbors with Euclidean Distance.
• Solution
• Calculate the Distance Between the Test Point (X = 3.5) and All Training Points:
• Euclidean distance between two points is given by: d(p,q)=∣p−q∣.
• Calculate the distance between X=3.5 and each training point:
• Distance to Point 1: 3.5-1=2.5, Point 2: 3.5-2=1.5, Point 3: 3.5-1.5=2, Point 4: 3.5-3=.5, Point 5: 3.5-4=.5

17

10/9/2024

K-NN Regression Example…

18

10/9/2024

Use Cases of KNN

• Recommendation Systems:
• Based on similarities between users or products.
• Pattern Recognition:
• Handwriting digit classification, image recognition.
• Medical Diagnosis:
• Classifying diseases based on symptoms.

19

10/9/2024

Conclusion

• Key Takeaways:
• KNN is simple and effective for many tasks.
• Works for both classification and regression.
• Choice of K and distance metric is crucial for performance.

20

10/9/2024