Skip to content
AI.info

Unsupervised learning

High-Dimensional Geometry and Mixed Data

Examine distance concentration, sparsity, hubness, feature dominance, and strategies for mixed numerical and categorical data.

By the end you can

Visual

Four pressures that weaken high-dimensional neighborhoods

These effects interact, and they need different remedies. At least one of those remedies has been measured.

In 2001 Aggarwal and colleagues argued that “the Manhattan distance metric (L1 norm) is consistently more preferable than the Euclidean distance metric (L2 norm) for high dimensional data mining applications”. They went further and introduced fractional norms. On synthetic data — 6 clusters, 10,000 points each, 20 dimensions — k-means recovered about 99% with the fractional metric f = 0.3, against 89% with the Euclidean metric. Under noise masking, the L10 metric fell to random accuracy at masking probability 0.4. L1 held out to 0.6. “The L0.1 distance metric is most robust to the presence of noise in the data set and degrades to random performance at the slowest rate,” they reported.

The remedy is not general. Six years later a group at UCLouvain showed that concentration is intrinsic to the distances rather than a finite-sample artifact, and François and his co-authors concluded that “contrary to what is generally admitted, fractional norms are not always less concentrated than the euclidean norm; a counterexample is given to prove this claim.”

So the layers below are not four dials with four settings. Changing the metric is a hypothesis about the data. It has to be tested on the data.

FigureLayers · 4 layers
  1. 01

    Irrelevant coordinates

    Noise dimensions add distance without adding task meaning.

  2. 02

    Scale and sparsity

    Rare nonzero values and uneven units create accidental dominance.

  3. 03

    Distance concentration

    Nearest and farthest distances can become relatively similar under some distributions.

  4. 04

    Hubness and crowding

    A few points appear in many neighbor lists while others become isolated.

A high-dimensional vector is not automatically a useful geometry.

Analogy

Searching for friends in a building with thousands of hallways

Every person in a building of thousands of corridors can differ along any one of them. Two people who share several rooms may still be separated by many irrelevant turns. And a few central figures end up close to everyone.

Whether concentration becomes harmful depends on the distribution and the metric, not on dimension alone. That is a measured statement, not a hedge. In 2009 Durrant and Kabán proved the converse of Beyer et al.'s theorem in the Journal of Complexity: for linear latent variable models, where the dimensions are not i.i.d., “the Euclidean distance will not concentrate as long as the amount of ‘relevant’ dimensions grows no slower than the overall data dimensions”.

Then they took the claim to real corpora, and two collections of comparable width behaved in opposite ways. A NIPS paper text collection of 13,649 dimensions, n = 1,740, had well spread-out pairwise distances. A 9,857-dimensional adenocarcinoma gene-expression set of just 25 arrays was the most concentrated they tested: every array had half the rest of the data within a factor of just 1.669 of its nearest-neighbour squared distance. Nearly the same number of corridors. One building navigable, the other collapsed.

“These findings suggest that it is not the high dimensionality per se that causes problems for automated data analysis. Rather, it is the issue of distance concentration that, when present, appears to be a key source of serious problems,” they wrote.

Dimensionality is dangerous when coordinates outnumber meaningful constraints.

A thousand features and almost no meaningful neighbors

A device-monitoring table expands from twenty engineered variables to twelve thousand automatically generated features. Validation plots become cleaner, yet nearest neighbors change wildly after tiny perturbations. More coordinates create more ways for observations to differ. When many differences are noise or redundant, distance can concentrate. Local neighborhoods can then lose semantic stability.

High dimension increases representational capacity and geometric risk at the same time.

Case

Nearest and farthest converge at ten to fifteen dimensions

Distance concentration has had a precise form since 1999. Beyer and colleagues showed that “under a broad set of conditions … as dimensionality increases, the distance to the nearest data point approaches the distance to the farthest data point”. Their empirical results demonstrated “that this effect can occur for as few as 10-15 dimensions”. Ten to fifteen. That is well below the twelve thousand columns above, and below most feature tables anyone would call wide.

Comparison

Three ways to represent mixed numerical and categorical evidence

No encoding is universally correct. Each one changes the implied neighborhood, and two of the three columns below have measured price tags.

The cost of one-hot expansion is a count. Category counts were measured across 17 non-curated real datasets by Cerda and Varoquaux, at Inria, and the verdict on indicators is flat: “This strategy breaks down when the number of categories grows, as it creates high-dimensional feature vectors”. Chicago Building Permits carries 430,000 distinct values in its Work Description column across 554,000 rows. The U.S. FDA Drug Directory has 17,000 distinct Non Proprietary Names across 120,000 rows. Montgomery County's Employee Salaries has 385 distinct Employee Position Titles for only 9,200 employees. Yandex's CatBoost team hit the same wall independently in 2018, inside an industrial system: “However, in the case of high cardinality features (like, e.g., “user ID” feature), such technique leads to infeasibly large number of new features.”

The middle column has an author and a date. Gower-style dissimilarity is J. C. Gower's coefficient, published in Biometrics in 1971. It averages a per-character score over only those characters that can actually be compared. Quantitative characters score 1 − |x_i − x_j| / R_k, where R_k is the range of character k. Qualitative characters score 1 for agreement and 0 otherwise. And by construction it refuses to reward a shared nothing. “The term dichotomous is reserved for characters that are either present or absent and whose absence in both of a pair of individuals is not taken as a match,” Gower wrote. That rule is why the coefficient survives sparsity better than an indicator matrix does.

It is not a historical curiosity either. R's cluster package computes the same formula as the gower metric in daisy(), still shipping in version 2.1.8.3 of July 2026. The documentation is explicit: “The contribution of a nominal or binary variable to the total dissimilarity is 0 if both values are equal, 1 otherwise”, and “The contribution of other variables is the absolute difference of both values, divided by the total range of that variable”.

FigureComparison · 3 columns

One-hot plus scaled numerics

Convert categories to indicators and combine them with normalized continuous fields.

  • Works with many standard estimators
  • Can overweight high-cardinality variables
  • Makes shared absences numerous
  • Needs explicit block weighting

Gower-style dissimilarity

Compute per-feature dissimilarities and average them with type-aware rules.

  • Handles numeric, binary, and categorical fields
  • Supports missing-value-aware comparisons
  • Weights require domain judgment
  • Pairwise computation can be expensive

Learned representation

Map heterogeneous inputs into an embedding trained for a proxy task.

  • Can capture nonlinear interactions
  • Inherits proxy-objective bias
  • Requires held-out neighborhood checks
  • May hide which fields drive similarity

Key idea

PCA is not a universal cure for high dimension

Linear reduction can remove redundancy and noise when variance aligns with useful structure. It can also discard rare, low-variance signals that matter for anomalies or minority regimes.

Treat reduction as a hypothesis. Here is what happens when a deployed system does not. A week of network-wide traffic from the Abilene and Géant IP backbones, examined at three aggregation levels, broke PCA-based anomaly detection in two separate ways. Ringberg and colleagues published the result in 2007. First, “the false positive rate is very sensitive to small differences in the number of principal components in the normal subspace”. Second, a large anomaly can pollute that normal subspace until the detector stops seeing it. The tuning knob nobody thinks of as a modeling decision — how many components to keep — moves the false-positive rate.

Two years later the instability reproduced on somebody else's data. Brauckhoff and her co-authors, at ETH Zurich and Lancaster University, traced it to temporal correlation and non-stationarity that PCA's assumptions ignore: “It shows that tuning PCA to operate effectively in practice is difficult. Specifically, it shows high sensitivity of the false positive rate to the number of principal components chosen and relates this to the possibility that large anomalies pollute the normal subspace.”

Compare neighborhoods, downstream utility, reconstruction, and rare-case retention before declaring the compressed space better.

Compression improves geometry only when it preserves the relationships you need.

Steps

Diagnose neighborhood quality in high dimension

The aim is to learn whether proximity remains stable, discriminative, and interpretable.

Step 4 sounds like bookkeeping. It is not. In 2018 a shipped embedding space was repaired by treating hubness as an engineering defect rather than a fact of nature. “We introduce a cross-domain similarity adaptation to mitigate the so-called hubness problem (points tending to be nearest neighbors of many points in high-dimensional spaces),” wrote Conneau and colleagues. The correction is called Cross-domain Similarity Local Scaling, or CSLS. It changes nothing about the trained model. It changes only how retrieval measures a neighborhood.

The measurements are worth reading slowly. On fastText Wikipedia embeddings, with 1,500 source queries against 200,000 target words, swapping plain nearest-neighbour retrieval for CSLS raised English→Spanish P@1 from 77.4 to 81.4 in the supervised Procrustes setting. In the unsupervised setting it went from 79.1 to 81.7. On a separate Italian→English sentence-retrieval task it raised P@1 from 53.5% to 69.5%. CSLS has one neighbourhood parameter, K. They set it to 10 in every experiment, because the results were essentially identical for K = 5, 10 and 50. The fix is close to free of tuning.

The shipped code says the same thing the paper does. Facebook AI Research's own code release, MUSE, documents the correction as the default rather than a paper-only ablation: “By default, the validation metric is the mean cosine of word pairs from a synthetic dictionary built with CSLS (Cross-domain similarity local scaling)”. Inspecting hubs is not a diagnostic that ends in a shrug. On that system it was worth up to sixteen points of retrieval accuracy.

FigureProcess · 5 steps

  1. 1. Partition feature blocks

    Separate numeric, categorical, sparse, embedding, and metadata groups for independent inspection.

  2. 2. Measure distance spread

    Compare nearest, median, and farthest distances across representative observations.

  3. 3. Test neighbor stability

    Resample rows, perturb features, and measure overlap among nearest-neighbor lists.

  4. 4. Inspect hubs

    Count how often each point appears as a neighbor and review extreme cases.

  5. 5. Compare representations

    Evaluate raw, weighted, reduced, and learned spaces against domain contrast pairs.

Example

Symptoms of geometric trouble

These observations should send an analyst back to the data before anyone tunes an algorithm.

  • Neighbor churn: More than half of each point’s nearest neighbors change after a small rescaling of one feature block.
  • Hub dominance: A few generic text embeddings appear among the nearest neighbors of thousands of unrelated documents. That is the condition Conneau and colleagues corrected with CSLS, moving Italian→English sentence-retrieval P@1 from 53.5% to 69.5% without retraining anything.
  • Category explosion: One high-cardinality field swamps the behavioral variables. Chicago Building Permits holds 430,000 distinct Work Description values across 554,000 rows, as Cerda and Varoquaux measured; one-hot encoding that single column produces more indicator coordinates than the dataset has rows.
  • Flat distance distribution: The nearest and median distances differ only slightly, making radius-based density thresholds unstable. Durrant and Kabán's 25 adenocarcinoma arrays sat within a factor of 1.669 of each other's nearest-neighbour squared distance.
  • Sparse coincidence: Two users look similar because both lack almost every rare feature, not because they share meaningful activity. Gower's 1971 coefficient refuses that match by definition for dichotomous characters. An indicator matrix scored by Euclidean distance rewards it.

High-dimensional work needs geometry diagnostics, not fear

The curse of dimensionality is not a ban on rich representations. It is a warning that intuition from two dimensions can fail, and that proximity must be tested empirically. Durrant and Kabán's 13,649-dimensional text collection was fine. Their 25 gene-expression arrays, in 9,857 dimensions, were not. The column counts would not have told you which was which. A stable feature space may require weighting, feature selection, dimensionality reduction, or a task-informed embedding. Sometimes, as CSLS showed on a shipped embedding space, it needs only a change in how neighborhoods are scored at retrieval time. The correct choice follows from the relationship being preserved.

Do not trust a neighborhood merely because software can compute it.

Case

The points that become everyone's neighbor

Neighbor lists in high dimension are not evenly shared. The effect was named hubness in 2010, in the Journal of Machine Learning Research, by Radovanović and colleagues; they had stated the result a year earlier at ICML. It concerns k-occurrences, “the number of times a point appears among the k nearest neighbors of other points in a data set”. That distribution “becomes considerably skewed as dimensionality increases, causing the emergence of hubs”. A few points become everyone’s neighbor. The rest become nobody’s.

Key takeaways