Dimension of data; curse of dimensionality

The dimension (dimensionality) of a data set is the number of attributes (features) used to describe each object. A table with 4 attributes per record has dimension 4, and each record is a point in 4-dimensional space.

Curse of dimensionality

As the number of dimensions increases, data analysis becomes much harder. The term was coined by Richard Bellman.

• Sparsity: the volume of the space grows exponentially, so a fixed number of points becomes very sparse. To keep the same density the number of samples must grow exponentially with the dimension.
• Distance loses meaning: in high dimensions the distances to the nearest and farthest points become almost equal, so (max − min)/min → 0. Nearest neighbour, clustering and outlier methods based on distance or density become unreliable.
• Statistical problems: with few samples and many features, models overfit and give poor accuracy on new data.
• Computation: time and memory needed rise sharply with more attributes.
• Visualisation and interpretation are difficult beyond 3 dimensions.

Example: 10 intervals per attribute give 10 cells in 1-D, 100 cells in 2-D and 10¹⁰ cells in 10-D. 1000 records fill the first densely but leave almost all cells of the last empty.