K-Nearest Neighbors Algorithm Overview

Nearest Neighbors

• K-Nearest Neighbor (k-NN) is an instance-based learning algorithm.
• It classifies new data points by finding the k closest instances in the training set and assigning the most common label among them.
• 1-NN predicts the label based on the closest instance in the training dataset.
• k-NN finds the k closest instances and predicts the label by majority voting.
• The distance between the test data and all the training data is calculated to select the k closest training data points (k-nearest neighbors).
• The label (class) is predicted through majority voting.
• Common distance measures include Euclidean distance, Mahalanobis distance, correlation, and cosine similarity.
• Choosing an appropriate value for k is crucial.
• Small k is good at capturing fine-grained patterns but may overfit.
• Large k makes stable predictions but may underfit.
• The optimal value of k is a hyperparameter that can be tuned using a validation set.

k-NN Advantages

• No explicit model is built during training.
• The algorithm simply stores the dataset and performs computations during prediction (lazy learning).
• Simple and easy to program.
• As more data becomes available, k-NN can better approximate decision boundaries.

k-NN Disadvantages

• Calculating the distance between the query point and all training samples at prediction time is computationally expensive for large datasets.
• Can be biased toward the majority class if the data is imbalanced.
• Curse of dimensionality: In high-dimensional data, the distance between points becomes less meaningful.
• Performance depends heavily on the choice of k.

Support Vector Machine

• SVM is a type of supervised learning algorithm for classification.
• It finds an optimal separating hyperplane that maximizes the distance to the closest points from each class, known as the margin.
• The data points that lie on the edge of the margin are called support vectors.
• The position of the decision boundary is determined entirely by the support vectors.
• The margin can be maximized using a max-margin objective, which minimizes the squared norm of the weight vector.
• The max-margin principle can be applied to non-separable data by allowing some points to be within the margin or be misclassified.
• Slack variables are used to represent the misclassification of points.
• The soft-margin SVM objective minimizes a weighted combination of the squared norm of the weight vector and the total amount of slack.
• The hyperparameter 𝛾 balances the margin with the amount of slack.
• Different values of C (a hyperparameter) can lead to overfitting or underfitting.

Kernel Trick

• The kernel trick transforms data into a higher dimension using kernels, enabling the construction of a decision boundary that can be linearly separable.
• Examples of kernels include polynomial kernels and RBF (Radial Basis Function) kernels.
• When using the kernel trick with soft-margin SVM, overfitting may occur.

This quiz covers the K-Nearest Neighbor (k-NN) algorithm, an instance-based learning technique used for classification tasks. It examines how k-NN predicts labels based on the closest instances and explores the importance of the parameter 'k' in achieving optimal predictions. Additionally, it discusses various distance measures used in the algorithm.