What is k-NN?

Overview#

You will probably have heard all the buzz about machine learning and its applications. And if you have, you’ve probably heard about $k$-nearest neighbors ($k$-NN). This algorithm is one of the simplest and easy-to-understand classification and regression algorithms and can be used for many practical applications. Some of these applications include:

• Classification problems: The $k$-NN algorithm can be used in pattern recognition and other classification problems, such as identification of spam emails and classification of documents.

• Recommender systems: The $k$-NN algorithm can be applied to find similar users or items and make recommendations.

• Regression analysis: The $k$-NN algorithm can also be used for regression tasks, such as predicting housing prices based on features such as area, location, and number of bedrooms.

• Healthcare and medicine: The $k$-NN algorithm can assist in identifying the likelihood of certain diseases based on patient data and historical records.

In this blog, our focus will be on only classification problems. We’ll take a look at a numerical example running the $k$-NN algorithm to see how it works. We’ll also run the example via Python code. Finally, at the end of this blog, we’ll have a look at some advantages and disadvantages of using the $k$-NN algorithm for classification purposes.

Now, let’s explore the basics of the $k$-NN algorithm.

Introduction to kkk-NN#

What is $k$-NN? As mentioned above, $k$-NN is a widely recognized classification technique used to assign items to particular categories based on how similar they are to nearby data points. It falls under the category of instance-based or lazy learning algorithms. Unlike some other algorithms that build explicit models during training, $k$-NN makes predictions by finding the most similar data points in the training dataset to the item being classified.

How kkk-NN works#

Let’s take a look at the $k$-NN algorithm step by step:

Step 1: To classify a test instance $d$, define the $k$-neighborhood $P$ as $k$-nearest neighbors of $d$.

Step 2: Calculate the similarity (often using Euclidean distance or other distance metrics) between the new item and all data points in the training dataset. Based on the similarity values, extract $k$ instances forming $P$.

Step 3: Assuming multiple classes ($c1$, $c2$, $c3$, ..., and so on), count the number $n_i$ of training instances in $P$ that belong to class $c_i$. An optional step is usually to sort the distances in ascending order before counting the instances for each class.

Step 4: Assign $d$ the class that is the most frequent or the majority class.

Example#

Assume that we have the following dataset:

We also have the following test data point: (6, 5)

Step 1: To classify a test instance (6, 5), define the $k$-neighborhood $P$ as$k$nearest neighbors of the test point.

Step 2: We calculate the similarity between the new instance and all data points in the training dataset.

Recall the formula for Euclidean distance:

Here, $x_i$​ and $y_i$ are the $i$th parameters of the $\mathbf{x}$ and $\mathbf{y}$ data instances, and $n$ is the number of features in each instance.

After calculating distances, here is a table of distances from each point to our test point, i.e., (6, 5):

Step 3: Count the number $n_i$ of training instances in $P$ that belong to class $c_i$.

Step 4: Assign the test instance (6, 5) the class that’s the most frequent or the majority class.

Choice of distance metric and impact#

A key part of what is k-NN involves how you measure similarity. The default is often Euclidean distance (straight-line), but in many domains other metrics perform better:

• Manhattan (L1): sum of absolute differences; useful when features have independent contributions or grid structure.

• Minkowski: generalization with parameter ppp, bridging between Euclidean (p=2p=2p=2) and Manhattan (p=1p=1p=1).

• Cosine distance: measures angular difference; useful when magnitude is less important (e.g., text embedding vectors).

• Mahalanobis distance: accounts for covariances among features; stretches space to de-emphasize redundant directions.

Your choice impacts classification—if features have varying scales or distributions, Euclidean may mislead. That leads us to scaling.

kkk-NN algorithm in Python#

The following code implements the $k$-NN algorithm in Python. Note that we won’t be using any libraries (except for the math library) in this implementation example.

The code is explained below:

Line 1: We start by importing the math library, which is later used to calculate square roots while computing Euclidean distances between two points.

Lines 7–11: We define the euclidean_distance function between two points.

Line 14: We start defining the k_nearest_neighbors algorithm, which takes three arguments: data (the dataset), query_point (the point for which we want to find $k$-nearest neighbors), and k (the number of neighbors).

Line 15: We initialize an empty list called distances to store distances between query_point and the data points.

Lines 18–20: We initialize a loop to iterate through each data point in the dataset. We then call the euclidean_distance function that calculates the distance between query_point and the current data_point and store it in the distance variable. Finally, we append a tuple containing the data point and its distance to the distances list.

Line 23: We then sort the distances list in ascending order based on the distances. This step identifies the $k$-nearest neighbors.

Line 26: Next, we select the $k$-nearest neighbors from the sorted distances list and store them in the neighbors list.

Lines 29–35: We start by initializing an empty dictionary called class_counts to count the occurrences of each class among the neighbors. Then, we initiate a loop to iterate through each neighbor in the neighbors list. We store the class label ($A$ or $B$) for the current neighbor in the variable called label. We then have an if-else condition. We first check if the class label already exists. If it does, we increment its count by 1. Otherwise, we add it to our dictionary with a count of 1.

Lines 38–39: We now need to determine the majority class. For this, we sort the class_counts dictionary items in descending order, followed by returning the class label with the highest count (majority class).

Lines 42–45: Now, we need to test our $k$-NN algorithm. For that, we define query_point to be (6, 5) and set the value of k to be 3. We then call the k_nearest_neighbors function and print the result.

Feature scaling, normalization, and weighted voting#

To answer what is k-NN fully, we must stress feature scaling. Suppose one feature is in range [0,1000] and another in [0,1] — the large range dominates distance. Use:

• Min–max scaling: normalize to [0, 1]

• Z-score standardization: subtract mean, divide by standard deviation

Then weighted voting can refine majority decisions: instead of counting neighbors equally, weight by inverse distance:

vote(c)=∑i∈kNN1d(i)α[class(i)=c]\text{vote}(c) = \sum_{i \in \text{kNN}} \frac{1}{d(i)^\alpha} [\text{class}(i)=c]vote(c)=i∈kNN∑​d(i)α1​[class(i)=c]

Here α\alphaα is a smoothing exponent (commonly 1 or 2). Closer neighbors’ votes count more heavily—beneficial when neighbors vary in proximity.

Advantages and disadvantages of using the kkk-NN classification algorithm#

Let’s now take a look at a few advantages and disadvantages of using $k$-NN for classification tasks.

Advantages#

• The algorithm is simple to understand and implement.

• Unlike other classification algorithms, there’s no training involved. Learning is instance-based.

• The algorithm can adapt to changing data, also known as lazy learning.

• No assumptions are made about data distribution.

• The models generated by $k$-NN are interpretable. We can easily visualize decision boundaries.

Disadvantages#

• The algorithm can be computationally expensive with large datasets.

• $k$-NN is sensitive to the choice of $k$.

• The algorithm has limited ability to capture complex relationships.

• The $k$-NN algorithm might suffer from the curse of dimensionality. This curse refers to the phenomenon where the performance of algorithms such as $k$-NN degrades as the number of features or dimensions in the dataset increases.

• Scalability can be an issue with large datasets.

Choice of k, cross-validation, and speedups#

Finding the best value of k is central to what is k-NN in practice. Too small → noisy; too large → over-smooth. Use:

• Grid search with cross-validation: test candidate k values (e.g. 1, 3, 5, 7, …) via k-fold CV.

• Leave-one-out cross validation (LOOCV): useful for small datasets.

For large datasets, pure k-NN is too slow (distance to all points). Common optimizations include:

• KD-tree / ball-tree: hierarchical partitioning to prune distance calculations

• Approximate nearest neighbor: use locality sensitive hashing (LSH) or product quantization

• Dimensionality reduction: PCA, t-SNE or feature selection to reduce input size before k-NN

These techniques make k-NN usable beyond tiny toy datasets.

Visualizing decision boundaries and pitfalls#

To really understand what is k-NN, visualization helps. In 2D synthetic data, you can plot the decision boundary: irregular “patchwork” regions where class flips near neighborhoods. Pitfalls become visible:

• Sparse regions: in low-density areas, neighbors may come from far away, degrading reliability.

• Class imbalance: the majority class may dominate neighborhoods even where minority class is relevant.

• High dimensionality curse: in many dimensions, distance becomes less discriminative—neighbors all look nearly equally far.

Visual aids help learners internalize where k-NN works well and where it fails.

Conclusion and next steps#

#