# Does "curse of dimensionality" really exist in real data?

I understand what is "curse of dimensionality", and I have done some high dimensional optimization problems and know the challenge of the exponential possibilities.

However, I doubt if the "curse of dimensionality" exist in most real world data (well let's put images or videos aside for a moment, I am thinking about data such as customer demographic and purchase behavior data).

We can collect data with thousands of features but it is less likely even impossible the features can fully span a space with thousands of dimensions. This is why dimension reduction techniques are so popular.

In other words, it is very likely the data does not contain the exponential level of information, i.e., many features are highly correlated and many features satisfy 80-20 rules (many instances have same value).

In such a case, I think methods like KNN will still work reasonably well. (In most books "curse of dimensionality" says dimension > 10 could be problematic. In their demos they use uniform distribution in all dimensions, where entropy is really high. I doubt in real world this will ever happen.)

My personal experience with real data is that "curse of dimensionality" does not affect template method (such as KNN) too much and in most cases, dimensions ~100 would still work.

Is this true for other people? (I worked with real data in different industries for 5 years, never observed "all distance pairs have similar values" as described in the book.)

• Since you specifically excluded images and image analysis, I'll just put a plug in the comments by saying this field does deal with the curse of dimensionality quite regularly. It's very easy to get an overfit solution.
– Ashe
Jun 17, 2016 at 14:14
• Binary/dummy/one-hot encoded categorical features can easily blow up a distance-based model Jun 17, 2016 at 14:40
• A colleague of mine has worked with sales of sunglasses. Quite a number of features were categorical with large numbers of possible levels (e.g., brands, materials of different parts of the glasses etc.). I was definitely afraid of the CoD, but it's always hard to say whether or not it is present in a particular dataset, plus we quite probably didn't do a lot of standard tricks, not being experts in this particular analysis type. Jun 17, 2016 at 14:44
• @StephanKolassa So, did distance based methods worked in the sun glass use case? Jun 17, 2016 at 14:57
• Not overly well. It was not a very successful project. Jun 17, 2016 at 15:00

This paper(1) discusses the blessing of non-uniformity as a counterpoint to the curse of dimensionality. The main idea is that data are not uniformly dispersed within the feature space, so one can gain traction by identifying the ways in which the data are organized.

(1) Pedro Domingos, "A Few Useful Things to Know about Machine Learning"

Curse of dimensionality in machine learning is more often the problem of exploding empty space between the few data points that you have. Low manifold data can make it even worse. Here is an example setup with 10000 samples where I try to do kNN with 1 neighbor.

from numpy.random import normal
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import precision_score
import matplotlib.pyplot as plt
import numpy as np
from math import sqrt
from scipy.special import gamma

N=10000
scale=20

dims=[]
precs=[]

def avg_distance(k):
return sqrt(2)*gamma((k+1)/2)/gamma(k/2)

clf = KNeighborsClassifier(1, n_jobs=-1)

clf.fit(X_train, y_train)

y_test_pred=clf.predict(X_test)

prec=precision_score(y_test, y_test_pred)
dims.append(dim)
precs.append(prec)
print(dim, prec)

plt.plot(dims, precs)
plt.ylim([0.5,1])
plt.xlabel("Dimension")
plt.ylabel("Precision")
plt.title("kNN(1) on {} samples".format(N))
plt.show()


You didn't like fully uniform distributions, so I've made this a 2D manifold with smaller dimensions (reduced by scale) sprinkled around the 2D plane of the first two coordinates. As it happens, one of the smaller dimensions is predictive (the label is 1 when that dimension is positive).

The precision drops rapidly with increasing dimension.

Of course, precision=0.5 would be random guessing. With a decision surface, which is more complicating than a plane, it would get even worse.

It's like the kNN balls are too sparse to be helpful at probing a smooth hyperplane. With higher dimensions they feel increasingly more lonely.

On the other hand, methods like SVM have a global view and do much better.

Consider for example time series (and images, and audio). Sensor readings (Internet of Things) are very common.

The curse of dimensionality is much more common than you think. There is a large redundancy there, but also a lot of noise.

The problem is that many people simply avoid these challenges of real data, and only use the same cherryupicked UCI data sets over and over again.

• Yes, I agree. Say a sequence model $P(\mathbf X)=P(X_1)\prod_{n=2}^N P(X_n|X_{n-1})$. Markov property is a way to regularize and over come the curse of dimensionality. But time series is kind like image or video. Jun 17, 2016 at 20:09
• Maybe most real world data is from sensors like images, video, and time series? Jun 17, 2016 at 22:00
• @hxd1011 markov property is an abstraction that may have nothing to do with real data!
– Sycorax
Jun 18, 2016 at 3:12

There is a wonderful article, "Statistical Modeling: the two cultures", by Breiman. He explains the two groups of scientists who deal with data and how each of them look at "dimensionality". The answer to your question is "it depends" in which group you are. Check the paper out.

• Thanks @Zamir Akimbekov, there are great discussions here, and another interesting paper here Jun 23, 2016 at 13:44