Classification Algorithms-2 Notes – Class 12 Data Science (844)

Classification Algorithms-2 Notes of Class 12 DS covers K-Nearest Neighbors (K-NN), its characteristics, advantages, disadvantages, and Cross Validation.

Introduction to K-Nearest Neighbors (K-NN)

• K-Nearest Neighbors (K-NN) is one of the simplest and easiest supervised machine learning algorithms. It is widely used because it is easy to understand and implement.
• K-NN can solve both classification and regression problems, but it is mainly used for classification, especially in pattern recognition and data mining.
• The basic idea of K-NN is that similar data points are usually located close to each other. Therefore, a new data point is likely to belong to the same category as its nearby data points.
• Data points belonging to the same class generally occupy the same feature space. For example, if circles are grouped in one area and triangles are grouped in another area, a new point will most likely belong to the group that is closest to it.
• The boundary that separates different classes is called the decision surface. It helps the algorithm decide which class a new data point belongs to.
• When a new (unknown) data point is given, the K-NN algorithm first calculates the distance between the new point and every data point in the dataset.
• After calculating all distances, K-NN selects the ‘K’ closest data points (nearest neighbors) and checks the class labels of these nearest points.
• The algorithm then performs a majority vote. The class that appears most frequently among the K nearest neighbors is assigned to the new data point as the predicted class.
• The value of ‘K’ represents the number of nearest neighbors that the algorithm considers before making a prediction.
• If K = 1, the algorithm checks only the single closest data point. If K = 2, it checks the two nearest data points, and similarly, it considers more neighbors as the value of K increases.
• There is no fixed value of K that works for every dataset. The best value of K is selected by testing different values and choosing the one that gives the highest prediction accuracy.
• In most cases, odd values of K (such as 3, 5, 7, etc.) are preferred because they help avoid ties during majority voting.
• A larger value of K reduces the influence of outliers, but it also makes the decision boundary more generalized, which may reduce the algorithm’s ability to capture small patterns in the data.

Characteristics of K-Nearest Neighbors (K-NN)

• Lazy Learning: K-NN follows the principle of lazy learning. It does not have a specific training phase where it learns from the data. Instead, it uses all the training data while performing the classification operation.
• Non-parametric Learning: K-NN is a non-parametric algorithm because it does not assume anything about the distribution of the data. Therefore, it does not need to find any parameter for the data distribution. The only hyperparameter in K-NN is the value of K, which is provided by the user.

Advantages of K-NN

• Simple and Intuitive: K-NN is easy to understand and implement. To classify a new data point, it finds the K nearest neighbors from the dataset and predicts the class using majority voting.
• No Training Step: K-NN does not have a separate training phase. It directly uses all the data points during the prediction stage to make predictions.
• Good for Multi-class Problems: K-NN can handle multi-class classification problems without requiring any additional steps.
• Supports Classification and Regression: K-NN can be used to solve both classification and regression problems, which makes it a versatile algorithm.
• No Assumptions about Data: K-NN is a non-parametric algorithm, so it does not assume any specific distribution of the data before making predictions.

Disadvantages of K-NN

• Slow and Memory Inefficient: K-NN becomes slower as the dataset grows because it compares the new data point with all the existing data points. It also requires storing the entire dataset in memory during prediction.
• Problems with Imbalanced Data: K-NN does not perform well on imbalanced datasets because it tends to predict the majority class more often, which can lead to incorrect classification of the minority class.
• Sensitive to Outliers: Since K-NN selects neighbours based on distance, the presence of outliers, especially near the decision boundary, can reduce the accuracy of the algorithm.
• Curse of Dimensionality: K-NN works well with a small number of input variables, but its performance decreases as the number of variables increases.
• Requires Distance Measurement: K-NN can only be used when the distance between data points can be measured using techniques such as Euclidean or Manhattan distance.

Cross Validation

• Cross Validation is a technique in which a small portion of the dataset is kept aside and not used for training. After training, the model is tested on this reserved data before it is finalized.
• The steps involved in Cross Validation are:
  1. Reserve a small portion of the dataset called the validation dataset.
  2. Train the model using the remaining dataset.
  3. Test the model on the validation dataset and check its accuracy.
• Cross Validation helps evaluate the performance of the model. If the model achieves high accuracy on the validation data, it is considered suitable for solving real-world problems.
• One of the most commonly used cross-validation techniques is K-Fold Cross Validation. In this method, the dataset is divided into K equal folds (sets).
• In K-Fold Cross Validation, K iterations are performed. During each iteration, one fold is used as the validation (test) set, while the remaining folds are used for training.
• K-Fold Cross Validation reduces bias because every data point is used for both training and testing during different iterations.
• The value of K should be chosen so that each fold is large enough to represent the overall dataset. If the appropriate value is not known, K = 10 is commonly used as a thumb rule.
• Cross Validation can also be used to find the best value of K in the K-NN algorithm. In most cases, the highest accuracy is achieved when K is between 7 and 13, and the accuracy generally decreases as the value of K becomes larger.