Using the curse of dimensionality for encoding non-ordered (nominal) categorical variables of high cardinality

Question

When the dimension is high, all data are approximately at the same distance away from each other. This makes distance-based methods such as k-nearest neighbors less useful if the data are more or less uniformly distributed. This is also referred to as the curse of dimensionality.

However, why not to make lemonade out of this dimensionality lemon?

Why not to encode nominal categorical variables of high cardinality with randomly distributed points in some high-dimensional space but such that the number of dimensions is much less than we would get with the one-hot encoding?

As the distance between any two points is almost the same, no artificial ordering will be introduced. The encoding is very fast. No need to calculate embedding with some neural network.

Will this encoding work? Will it be meaningless or introduce any bias? Is anybody using it? Do you know any references?

Answer 1

When the dimension is high, all data are approximately at the same distance away from each other.

Yes, but this is the worst case scenario of the curse of dimensionality:

• This happens only if the data is extremely sparse. In real cases it's not really "all data", because some data points are less sparse than others, and it's not really "the same distance", because there can be small but meaningful differences in the distance between points.
• There are known mitigation measures which can prevent this worst case scenario to happen, in particular various feature selection/extraction methods. So in real cases it's simply a mistake to work with some very high dimensionality data left "untreated".

Why not to encode nominal categorical variables of high cardinality with randomly distributed points in some high-dimensional space but such that the number of dimensions is much less than we would get with the one-hot encoding?

This would correspond to a random feature extraction method: instead of trying to group similar features together when reducing the dimensions, features are just randomly projected into a low-dimension space. The disadvantage is clear: instead of simplifying the data while preserving the patterns, the patterns in the data are just ignored. It's likely that the data would become pretty much useless after that.

The goal is not just to reduce dimensionality for the sake of it, it's to reduce dimensionality in a way which leaves the most important characteristics of the data as intact as possible, or even emphasize them by removing the noise. This method would be equivalent to randomly selecting features instead of selecting the most informative ones.

For example, in the case of text data there is often high dimensionality due to the high number of distinct words. A basic but very effective method consists in discarding words which appear rarely: this reduces the dimensions a lot (due to the Zipf distribution of words in a text), prevents noise due to words which happen by chance, and preserves most of the patterns which happen with moderately frequent words.