K-Nearest Neighbors (KNN)
K-nearest-neighbor (kNN) classification is one of the most basic and straightforward methods for classification. It is often the go-to choice for classification studies when there is minimal or no prior knowledge about the data’s distribution (Peterson, 2009). This method retains the entire training set during the learning phase and assigns each query to a class based on the majority label of its k-nearest neighbors within the training set.
The simplest form of KNN is the Nearest Neighbor rule (NN), where K = 1 (Imandoust, 2013). In this case, each sample is classified similarly to its closest surrounding samples. If the classification of a sample is unknown, it can be predicted by examining the classification of its nearest neighbor samples. For an unknown sample, the distances between this sample and all the samples in the training set are calculated. The sample with the smallest distance is the closest to the unknown sample, and thus, the unknown sample is classified based on the classification of this nearest neighbor.
Let’s understand the K-nearest-neighbor (kNN) classification with the help of an example. Suppose there are two categories, Category A and Category B, and we have a new data point x1. We need to determine which category this data point belongs to. To solve this problem, we can use the K-NN (K-Nearest Neighbors) algorithm. K-NN helps us identify the category or class of a specific data point by considering its closest neighbors. Refer to the diagram below for a visual representation.
Calculating KNN: Distance Metrics
The goal of the k-nearest neighbor (KNN) algorithm is to identify the nearest neighbors of a given query point, enabling the assignment of a class label to that point. To determine which data points are closest to a given query point, the distance between the query point and the other data points must be calculated. These distance metrics are essential for forming decision boundaries, which partition query points into different regions. Although there are several distance measures to choose from, this article will focus on three of them.
I. Euclidean Distance (p=2)
This is the most commonly used distance measure, and it is limited to real-valued vectors. Using the below formula, it measures a straight line between the query point and the other point being measured.
II. Manhattan Distance (p=1)
This is another popular distance metric that measures the absolute difference between two points. Often referred to as taxicab distance or city block distance, it is commonly visualized on a grid, demonstrating how one might navigate from one address to another via city streets.
III. Minkowski Distance
Minkowski distance is a generalized form of both Euclidean and Manhattan distance metrics. The parameter “p” in the formula allows for the creation of various distance metrics. When p=2, the Minkowski distance becomes the Euclidean distance, and when p=1, it represents the Manhattan distance.
Origin & History
K-nearest-neighbor classification emerged from the necessity to conduct discriminant analysis in situations where reliable parametric estimates of probability densities are unknown or hard to determine. In an unpublished report by the US Air Force School of Aviation Medicine in 1951, Fix and Hodges introduced a non-parametric method for pattern classification, now widely known as the k-nearest neighbor rule (Fix & Hodges, 1951).
They introduced an innovative nonparametric classification method based on the “distance” between points or distributions. The core concept is to classify an individual into the population whose sample has the majority of the closest neighbors. Later, in 1967, the formal properties of the k-nearest-neighbor (k-NN) rule were explored, including establishing upper bounds for the risk limit of nearest-neighbor classifiers. With these formal properties in place, extensive research followed as illustrated below:
I. Nearest Neighbor Pattern Classification
In 1967, Thomas Cover and Peter Hart made significant advancements in the field of non-parametric classification by expanding on the nearest neighbor method. Their seminal work, “Nearest Neighbor Pattern Classification,” introduced a comprehensive framework for pattern recognition using the nearest neighbor rule. This method classifies a data point based on the class of its closest neighbors in the feature space.
Cover and Hart’s research provided a rigorous theoretical foundation for the nearest neighbor algorithm and successfully demonstrated that as the number of samples approaches infinity, the error rate of the nearest neighbor classifier approaches twice the Bayes error rate, which is the lowest possible error rate for a given distribution. This finding highlighted the potential of the nearest neighbor method to achieve high classification accuracy without relying on parametric assumptions about the data distribution.
II. Nearest Neighbor Rule with a Reject Option
In 1970, Edward Hellman examined the Nearest Neighbor Rule With a Reject Option and explored how this method could balance the trade-off between classification accuracy and the robustness of decision-making. Hellman’s approach involved two key enhancements to the traditional k-nearest neighbor (k-NN) method:
(k, k*) Nearest Neighbor Rule: The traditional k-nearest neighbor rule classifies a sample based on the majority class among its k-closest neighbors. Hellman’s (k, k*) rule introduced a two-tiered classification mechanism. Here, ‘k’ represents the primary number of neighbors considered for initial classification, while ‘k*’ represents a secondary, potentially different number of neighbors used for refining the decision. This dual consideration helps in fine-tuning the classification process, making it more flexible and potentially more accurate.
Reject Option: One of the significant contributions of Hellman’s work was the introduction of a reject option in the classification process. The reject option allows the classifier to abstain from making a decision when it is not confident enough about the classification. This is particularly useful in situations where the cost of a wrong classification is high, such as in medical diagnosis or critical safety applications. By rejecting uncertain classifications, the system can maintain higher overall reliability and accuracy.
III. Refinements for the Bayes Error Rate
In 1975, Keinosuke Fukunaga and Larry Hostetler made significant contributions to the field of pattern recognition by refining the nearest neighbor classification method in relation to the Bayes error rate. Their work focused on improving the performance and theoretical understanding of nearest neighbor classifiers, particularly how these classifiers could approximate the Bayes error rate, which represents the lowest possible error rate achievable by any classifier for a given data distribution.
Background on Bayes Error Rate: The Bayes error rate is the minimum achievable error rate for a classifier, given the true underlying probability distributions of the classes. It serves as a benchmark for evaluating the performance of any classification algorithm. In practice, achieving the Bayes error rate is often impossible due to the unknown nature of the true distributions. However, approximating this error rate as closely as possible is a critical goal in developing effective classifiers.
Contributions of Fukunaga and Hostetler: Fukunaga and Hostetler introduced the concept of using density gradient estimation to refine the nearest neighbor rule. They proposed methods to estimate the gradient of the data’s probability density function (PDF). By understanding the density gradients, the classifier can better identify the boundaries between different classes, leading to more accurate classification decisions. This approach helps in adjusting the decision boundaries dynamically based on the local density of data points, thereby reducing misclassification errors.
IV. Distance-Weighted Approaches
In the mid-1970s, further advancements in nearest-neighbor classification were made by integrating distance-weighted approaches. These refinements aimed to enhance the classification accuracy of nearest-neighbor algorithms by giving more influence to closer neighbors. Notably, Dudani contributed significantly to this area in 1976, followed by Bailey and Jain in 1978.
Dudani’s Distance-Weighted k-NN: In 1976, S.A. Dudani introduced a pivotal enhancement to the k-nearest neighbor algorithm through a distance-weighted approach. Dudani recognized that all neighbors should not be treated equally in the decision-making process. Instead, neighbors that are closer to the query point should have a more significant influence on the classification outcome than those farther away (Dudani, 1976). Dudani proposed a method where the contribution of each neighbor to the classification decision is weighted inversely proportional to its distance from the query point. Specifically, closer neighbors are given higher weights and farther neighbors are given lower weights. This approach intuitively reflects the idea that closer neighbors are more likely to be similar to the query point and thus more relevant for its classification.
Bailey and Jain’s Refinements: Building on Dudani’s work, Thomas Bailey and Anil K. Jain further explored distance-weighted approaches in 1978. They considered various mathematical functions to determine the weights, such as inverse distance, inverse square distance, and exponential decay functions. This exploration provided a broader framework for implementing distance-weighted k-NN, allowing practitioners to choose the most suitable weighting function for their specific application.
VI. FKNN (Fuzzy kNN)
James Keller et al. and his colleagues (Keller, 1985) developed the Fuzzy k-Nearest Neighbor (Fuzzy k-NN) algorithm as an enhancement of the traditional k-Nearest Neighbor (k-NN) method. Similar to the traditional k-NN, the Fuzzy k-NN algorithm classifies an input based on the distance from its k-nearest neighbors. However, instead of assigning the input to a single class, it computes membership degrees indicating how strongly the input belongs to each class.
The Fuzzy k-NN algorithm is particularly useful in situations where class boundaries are not well-defined, and data points can belong to multiple classes to varying degrees. This is achieved by weighting each neighbor’s contribution to the classification based on its distance and its own membership values.
VII. Adaptive Soft k-Nearest-Neighbour Classifiers
Traditional k-NN classifiers are local learning systems that estimate posterior class probabilities using a fixed number of training points. These systems guarantee good generalization because they always have enough data to compute estimations. However, their approximation capabilities are often poor because they use a simple ratio of integers to estimate probabilities.
To improve the quality of these estimations, Sergio Bermejo and Joan Cabestany proposed using a Parzen window estimate computed with the k-nearest-neighbour training samples. This soft k-NN estimation retains the advantages of k-NN while enhancing the approximation quality through smooth interpolation between training points. The approach combines the strengths of k-NN and Parzen estimates, resulting in better performance (Bermejo and Cabestany, 2000).
Construction of KNN Model
The traditional KNN model is constructed through a series of steps that involve selecting the number of neighbors, calculating distances, identifying the nearest neighbors, counting the category frequencies, and assigning the new data point to the majority category. This process makes KNN a simple yet powerful algorithm for classification and regression tasks.
I. Select the Number K of the Neighbors
The first step is to select the number of nearest neighbors, denoted as K, that will be considered for determining the classification or regression output. The choice of K is crucial as it affects the model’s performance. A smaller K can make the model sensitive to noise, while a larger K can smooth out the predictions but may introduce bias.
II. Calculate the Euclidean Distance
Next, the Euclidean distance between the new data point (the query point) and each data point in the training dataset is calculated. The Euclidean distance is a common distance metric used in KNN and is defined as:
III. Identify the K Nearest Neighbors
After calculating the Euclidean distances, the next step is to identify the K nearest neighbors to the query point. This involves sorting the distances in ascending order and selecting the top K data points with the smallest distances.
IV. Count the Neighbors in Each Category
Once the K nearest neighbors are identified, the algorithm counts the number of data points in each category (class) among these neighbors. This step is critical for classification tasks, where the goal is to determine the majority class among the K neighbors.
V. Assign the New Data Point
The new data point is then assigned to the category (class) that has the maximum number of neighbors among the K nearest neighbors. This majority voting approach ensures that the classification is based on the predominant class in the neighborhood of the query point.
VI. Model is Ready
After assigning the new data point to the appropriate category, the KNN model is ready for use. This model can now be used to classify or predict the outcomes for new data points based on their proximity to the training data.
Types of KNN
The K-Nearest Neighbors (KNN) algorithm is a fundamental machine-learning method for classification and regression tasks. It operates on the principle of finding the ‘k’ closest data points (neighbors) to a query point and making predictions based on these neighbors. Various types of KNN algorithms modify this basic approach to improve performance and address specific challenges.
I. Locally Adaptive KNN
Locally adaptive KNN determines the optimal K value by analyzing data from discriminating classes. It considers the quantity and distribution of neighbors belonging to the majority class and the second majority class within the k-neighborhood of a test data point. By evaluating these classes, it generates a ranking table that includes various K values, distances from centroids, and their respective ratios. The optimal K value is then selected from this table through a ranking process, ensuring the most effective classification.
II. Weight adjusted KNN
Weight-adjusted KNN focuses on adjusting the weights of the training data points based on their proximity to the query point. Each point in the training data is assigned a weight using a kernel function, where closer points receive higher weights and farther points receive lower weights. The kernel function ensures that the weight decreases as the distance from the query point increases. The algorithm then predicts the class of a test data point by considering the most prevalent class among its weighted nearest neighbors.
III. Fuzzy KNN
The fuzzy KNN algorithm assigns “membership” values to each class for a given test data point. In this approach, once the nearest neighbors are identified, each potential class among these neighbors is assigned a membership value through a fuzzy mathematical procedure. The class with the highest membership value is then selected for the final classification. This method allows for more nuanced predictions by considering the degree of belonging to each class.
IV. MKNN
The primary concept of the MKNN method is to assign class labels based on the K-validated data points from the training set. Initially, the validity of all data samples in the training set is computed. Then, a weighted KNN is applied to any test sample. In the MKNN algorithm, each sample in the training set is validated in the first step. The validity of each point is calculated based on its neighbors, and this validation is performed once for every training sample. This validity information is then used as additional data for making predictions on test samples.
V. Generalized Mean Distance KNN
The generalized mean distance KNN variant emphasizes using local vector creation and iterative calculations of the generalized mean distance. Initially, it organizes and stores the lists of nearest neighbors for each class. These lists are then transformed into local mean vectors. The algorithm repeatedly calculates the mean distance from these vectors to the test data point to determine the final distance of each class. The class with the smallest mean distance is then predicted as the class for the test data point.
VI. Mutual KNN
The mutual KNN algorithm is based on the concept of mutual neighbors. It starts by refining the training dataset and removing data points that do not have mutually closest neighbors. Then, it searches the reduced training dataset to find the nearest neighbors for a test data point. The algorithm considers only these mutually closest neighbors as potential candidates for classification. Finally, it classifies each test data point using the majority vote among these mutually closest neighbors.
VII. Ensemble approach KNN
The Ensemble KNN method improves classification by utilizing multiple K values rather than a single one. It calculates the nearest neighbors for a test point up to a maximum value, typically the square root of the number of training data points. Neighbors are then ranked by their closeness, with weights assigned using an inverse logarithmic scale to give more importance to closer neighbors. The class of the test data is determined by the total weight of these neighbors, effectively combining the results of multiple KNN classifiers with different K values using a weighted sum rule.
Advantages of KNN
The KNN algorithm’s ease of implementation, lack of a training phase, versatility, adaptability with distance metrics, non-parametric nature, and incremental learning capability make it a powerful and flexible tool for a variety of machine learning tasks.
I. Easy Implementation
The KNN algorithm is very simple to implement. It involves basic calculations to determine the distance between different data points based on their features. This distance can be computed using straightforward distance formulas such as Euclidean or Manhattan distance. The simplicity of these calculations means that KNN can be quickly and easily coded, even for those new to machine learning.
II. No Training Period
KNN is known as a “lazy learner” because it does not have a distinct training phase. Instead of building a model through training, KNN stores the entire training dataset and only processes data when a prediction is needed. This means there is no upfront training time, making the algorithm efficient in terms of time. It leverages the stored training data to make real-time predictions based on the nearest neighbors of the input data point.
III. No Assumptions About Data Distribution
KNN is a non-parametric algorithm, meaning it makes no assumptions about the underlying data distribution. This is advantageous because it can be applied to a wide variety of data types and distributions without requiring any prior knowledge about the data. This flexibility makes KNN suitable for complex and non-linear datasets where traditional parametric algorithms might struggle.
IV. Incremental Learning Capability
KNN can easily accommodate new data points as they become available without the need to retrain the entire model. This incremental learning capability is useful in dynamic environments where the data continuously evolves, such as in real-time stock market predictions or user recommendation systems.
Disadvantages of KNN
While KNN is a simple and intuitive algorithm, its effectiveness is limited by issues related to computational efficiency, handling of high-dimensional data, the necessity for feature scaling, and sensitivity to noise and outliers. These disadvantages must be carefully considered when choosing KNN for practical applications, especially in scenarios involving large and complex datasets.
I. Inefficiency with Large Datasets
The KNN algorithm becomes increasingly inefficient as the size of the dataset grows. This inefficiency stems from the need to calculate the distance between the new data point and every existing point in the dataset. This computational burden leads to slower performance, making the algorithm impractical for large-scale datasets.
II. Challenges with High Dimensions
KNN does not perform well with high-dimensional data, a problem often referred to as the “curse of dimensionality.” As the number of dimensions increases, the distance metrics become less reliable and meaningful. This degradation in performance is due to the fact that all points tend to become equidistant from each other in high-dimensional spaces, reducing the algorithm’s ability to distinguish between neighbors effectively.
III. Sensitivity to Noisy Data and Outliers
KNN is highly sensitive to noisy data, missing values, and outliers. Noise and outliers can significantly distort distance calculations, leading to inaccurate classifications. Therefore, it is crucial to preprocess the data by imputing missing values and removing outliers to maintain the algorithm’s accuracy and reliability.
IV. Computationally Intensive
KNN is computationally intensive, especially when the number of predictors (features) and training records is large. For each prediction, the algorithm must compute the distance from the query point to all points in the training set, identify the k-nearest neighbors, and then determine the majority class among these neighbors. This process requires significant computational resources and time, particularly for large datasets, making the algorithm less suitable for real-time applications.
KNN in Trading
The kNN algorithm is often utilized for Stock price prediction purposes because it is simple to implement and effective in handling stock price data, which often contains a mix of numerical and categorical variables. Khalid Alkhatib and his colleagues performed a study “Stock Price Prediction Using K-Nearest Neighbor (kNN) Algorithm” that specifically focused on predicting stock prices for a sample of companies listed on the Jordanian stock exchange- (Alkhatib, 2013).
The dataset used in this study comprises historical stock prices from five randomly selected companies listed on the Jordanian stock exchange, collected over several months. The primary attributes considered for prediction include the closing price, low price, and high price of the stocks. The study presents the prediction results for each company in the sample. The results include the actual and predicted closing prices, with the residual values indicating the difference between these two. The findings show that the predicted values closely follow the actual stock prices, indicating the robustness and reliability of the kNN algorithm in stock price prediction.
Another study “Classification of Stock Index movement using k-Nearest Neighbours (k-NN) algorithm (Nambi, 2012) investigates the effectiveness of the k-NN algorithm in predicting the direction of stock market indices, specifically the BSE-SENSEX and NSE-NIFTY. The study was performed to classify daily movements of these indices into bullish (rising) or bearish (falling) states.
The study collected daily stock index data, including open price, high price, low price, and close price, from January 2006 to May 2011. For prediction, the k-NN algorithm identifies the k-nearest neighbors of a given day based on historical data and predicts the closing price for the next day as the average closing prices of these neighbors. For classification, the algorithm classifies the next day’s movement as either ‘bull’ or ‘bear’ by analyzing the majority class of the k-nearest neighbors based on the returns.
This study revealed that the k-NN algorithm outperformed logistic regression in all evaluation metrics. The k-NN algorithm achieved an accuracy rate of 88.74% in classifying the next day’s index (BSE-SENSEX) movement, significantly outperforming logistic regression, which had an accuracy rate of 58.87%.
The Bottom Line
K-Nearest Neighbors (KNN) remains a powerful and versatile algorithm for both classification and regression tasks, owing to its simplicity and effectiveness. Despite its straightforward nature, KNN offers robust predictive capabilities by leveraging the proximity of data points to make informed decisions. It operates without assumptions about the underlying data distribution, making it suitable for various applications, including stock market predictions.
KNN’s ease of implementation and the absence of a training phase allow it to adapt to new data seamlessly, providing real-time predictive analytics. However, practitioners must be mindful of its limitations, such as inefficiency with large datasets, challenges in high-dimensional spaces, and sensitivity to noise and outliers.
