Java Data Analysis

The curse of dimensionality

Most clustering algorithms depend upon the distances between points in the data space. But it is a fact of Euclidean geometry that average distances grow as the number of dimensions increases.

For example, look at the unit hypercube:

The one-dimensional hypercube is the unit interval [0,1]. The two points that are farthest apart in this set are 0 and 1, whose distance d(0,1) = 1.

The two-dimensional hypercube is the unit square. The two points that are farthest apart in H₂ are the corner points 0 = (0,0) and x = (1,1), whose distance is .

In H_n, the two corner points 0 = (0, 0, …, 0) and x = (1, 1, …, 1) are at the distance ...