# k-Nearest Neighbors (k-NN) algorithm

The k-Nearest Neighbors (k-NN) algorithm is a simple yet powerful machine learning algorithm that is commonly used for both classification and regression problems. It falls under the supervised learning category, where the model learns from labeled training data to make predictions or classify new or unseen data.

## How does it work?

The k-NN algorithm follows a very intuitive approach. Given a new input data point, the algorithm finds the k nearest data points in the training set based on a specified distance metric. These nearest neighbors vote or contribute to the classification/regression of the new data point. In classification tasks, the majority class among the k nearest neighbors is assigned to the new data point. In regression tasks, the algorithm averages the values of the k nearest neighbors to obtain the predicted value.

Here's a step-by-step guide on how the k-NN algorithm works:

1. Choose the value of k: Determine the number of nearest neighbors (k) that will be considered while making predictions. This value should be carefully selected based on the specific problem and dataset.

2. Calculate the distance: Calculate the distance between the new data point and all the data points in the training set using a distance metric such as Euclidean distance or Manhattan distance. Typically, Euclidean distance is used for continuous features and Manhattan distance for categorical features.

3. Find the k nearest neighbors: Select the k data points with the shortest distances to the new data point.

4. Classify or regress: For classification, assign the majority class among the k nearest neighbors to the new data point. For regression, average the values of the k nearest neighbors to obtain the predicted value.

The k-NN algorithm has several advantages:

• Simplicity: The algorithm is straightforward to understand and implement. It does not make any assumptions about the underlying data distribution, making it a non-parametric learning method.

• Versatility: k-NN can be used for both classification and regression tasks. It can handle both categorical and numerical features.

• Robustness to noisy data: Since the algorithm takes into account multiple data points instead of relying on a single point, it is less sensitive to outliers and noisy data.

However, k-NN also possesses some limitations:

• Computational cost: As the size of the training set grows, the computation of distances between new data points and all training instances becomes more expensive.

• Curse of dimensionality: k-NN is sensitive to the curse of dimensionality. In high-dimensional space, the nearest neighbors may not be truly representative due to increased sparsity.

• Choosing the right k: Selecting an appropriate value of k is crucial. A small k can lead to overfitting, while a large k can result in underfitting. This choice depends on the dataset and problem at hand.

## Implementing k-NN with Scikit-Learn

Scikit-Learn, a popular machine learning library in Python, provides an easy-to-use implementation of the k-NN algorithm. Here's a simple example of using the k-NN classifier from Scikit-Learn:

``````from sklearn.neighbors import KNeighborsClassifier

# Create the k-NN classifier
knn = KNeighborsClassifier(n_neighbors=5)

# Fit the model to the training data
knn.fit(X_train, y_train)

# Make predictions on new data
y_pred = knn.predict(X_test)``````

In this example, `X_train` and `y_train` represent the features and labels of the training dataset, while `X_test` contains the features of the new data points on which predictions are made. The `n_neighbors` parameter determines the value of k, i.e., the number of nearest neighbors to consider.

Overall, the k-Nearest Neighbors algorithm is a simple and powerful tool in the field of machine learning. Its intuitive approach and ability to handle both classification and regression problems make it a valuable technique for various applications.