Day46 ML Review - K-Nearest Neighbors (3)

📚 The Start of Recording TIL Summer ‘24 : Why Did I Start This Project? 🚀

🔔 Don't Miss: Continous Records of TIL '25 (Still On-Going!) 🌟

✨ A New Chapter in TIL '25: Reflecting, Growing, and Moving Forward 📖

The Curse of Dimensionality

It is essential to mention that KNN is very susceptible to overfitting due to the curse of dimensionality. The curse of dimensionality describes the phenomenon where the feature space becomes increasingly sparse for an increasing number of dimensions of a fixed-sized training dataset.

DataCamp, “The Curse of Dimensionality in Machine Learning: Challenges, Impacts, and Solutions,” accessed Aug. 6, 2024. [Online]. Available: https://www.datacamp.com/blog/curse-of-dimensionality-machine-learning

Key Concepts

The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces (with many features or variables). As the number of dimensions increases, the volume of the space increases exponentially, leading to various challenges for machine learning algorithms and statistical methods.

How does the curse of dimensionality occur?

As we increase the dimensions in our dataset, the space it occupies grows exponentially. This means the data is spreading more. If we have a one-dimensional line, it’s relatively easy to populate it with a few points. However, with a two-dimensional square, we would need more points to cover the area. Picture a three-dimensional cube - we’d require even more points to fill the space. This concept applies to higher dimensions, resulting in extremely sparse data.

What problems does it cause?

1. Distance Measures Become Less Meaningful:

   • The "distance" between data points in high-dimensional spaces becomes less informative. For example, nearby points are similar in low-dimensional space, and distant points are different. However, in high dimensions, the distances between all points tend to converge, meaning all points become nearly equidistant.
   • This phenomenon can make algorithms like K-Nearest Neighbors (KNN) less effective, as the distinction between “near” and “far” neighbors becomes blurred.

   Example: If you have data in a 2D space, the distance difference between the closest and farthest points might be significant. However, as you move to higher dimensions, such as 1000D, the difference between the nearest and farthest points decreases, making it harder to differentiate between them.

   
   
   

2. Data Sparsity:

   • As the number of dimensions increases, data points become more sparse, meaning their density decreases. This sparsity makes it challenging to find meaningful patterns because most of the space is empty.
   • In high dimensions, you would need an exponentially more enormous amount of data to have enough data to represent the space adequately. However, collecting such a vast amount of data is often impractical or impossible.

   Example: Imagine a simple grid. In 1D, you might need only 10 points to cover a line. In 2D, you might need 100 points to cover a square. In 3D, you’d need 1,000 points to cover a cube. As you go to higher dimensions, the number of points required grows exponentially.

   
   
   

3. Overfitting:

   • In high-dimensional spaces, models can quickly become overly complex because more features are available to explain the variance in the data. This complexity can lead to overfitting, where the model captures noise rather than the underlying patterns, performing well on training data but doing better on unseen data.
   • Overfitting is more likely because a model with many dimensions can find spurious correlations between features and the target variable that do not generalize.

   Example: A model might fit every training data point perfectly in a high-dimensional space by creating overly complex decision boundaries. However, this model would likely perform poorly on new data because it has learned to “memorize” the training data rather than generalize.

   
   
   

4. Increased Computational Complexity:

   • The computational cost of algorithms increases with the number of dimensions. Operations that are straightforward in low dimensions, like searching for the nearest neighbors or calculating distances, become computationally expensive in high-dimensional spaces.
   • Many machine learning algorithms, such as decision trees, support vector machines, or clustering algorithms, experience significant slowdowns or become intractable as their dimensionality increases.

   Example: A simple search for the nearest neighbor in a low-dimensional space might be fast, but in a high-dimensional space, it can become exponentially slower, requiring much more time and computational resources.

   
   
   

5. Dimensionality Reduction Techniques:

   • Dimensionality reduction techniques are often employed to combat the curse of dimensionality. These techniques aim to reduce the number of dimensions while preserving as much relevant information as possible.
   • Principal Component Analysis (PCA), t-SNE, and Autoencoders are common techniques for reducing dimensionality and mitigating the curse.

   Example: PCA can reduce a 100-dimensional dataset to just a few dimensions by finding the principal components that explain most of the variance in the data. This reduction helps to simplify the model, reduce overfitting, and improve computational efficiency.