High-Cardinality Categoricals

The High-Cardinality Challenge

When category count $C > 1,000$ (e.g. IP Address, User ID, ZIP Code):

• One-Hot Encoding: Produces $N \times 1,000,000$ sparse matrix. Memory crashes, decision trees fail.
• Label / Ordinal Encoding: Imposes arbitrary numerical ordering ($1000 > 1$), corrupting distance-based models and linear layers.

High-Cardinality Toolkit

                             High-Cardinality Strategies
    ┌───────────────────────┬───────────────────────┬───────────────────────┐
    ▼                       ▼                       ▼                       ▼
Out-of-Fold Target     Frequency / Count     Hashing Trick         Entity Embeddings
     Encoding              Encoding         (FeatureHasher)          (Neural Nets)
Compresses C -> 1     Compresses C -> 1     Fixed N buckets       Compresses C -> k
(Must use smoothing!) (Simple & robust)     (Collision risk)      (Learns semantics)

Out-of-Fold Target Encoding with Bayesian Smoothing

For category $c$:

$$S_c = \frac{n_c \cdot \bar{y}c + m \cdot \bar{y}{\text{global}}}{n_c + m}$$

• $n_c$: Number of training samples in category $c$.
• $\bar{y}_c$: Mean target value of category $c$ in training set.
• $\bar{y}_{\text{global}}$: Global target mean across full dataset.
• $m$: Smoothing weight hyperparameter (e.g. $m = 10\text{--}100$).

Mandatory Leakage Prevention (Out-of-Fold Split)

Never compute $\bar{y}_c$ on the full dataset! Compute target encoding means strictly within K-Fold cross-validation folds:

  Fold 1 (Val) ──► Encoded using target means from [Fold 2 + Fold 3 + Fold 4 + Fold 5]
  Fold 2 (Val) ──► Encoded using target means from [Fold 1 + Fold 3 + Fold 4 + Fold 5]

Entity Embeddings (Guo & Berkhahn, 2016)

Pass categorical integer IDs into a trainable embedding table:

$$E \in \mathbb{R}^{C \times k}, \quad \text{where Rule of Thumb } k = \min(50, \lfloor C^{0.5} \rfloor)$$

Category ID: 4021 (ZIP Code) ──► [ Embedding Lookup Table ] ──► Dense Vector [e1, e2, ..., e16]

Key Insight: Entity embeddings map discrete categories into continuous vector spaces where semantically similar categories (e.g. adjacent ZIP codes or similar merchants) cluster together naturally.

Say this out loud

"High-cardinality features contain thousands of unique categories, making One-Hot Encoding memory-prohibitive. For GBDTs, we use Out-of-Fold Target Encoding with Bayesian smoothing to shrink rare category means toward global averages without target leakage. For deep neural networks, we use Entity Embedding layers to map category IDs into learned dense k-dimensional vectors."

Follow-ups to expect

• What is the Hashing Trick rule of thumb? Set hash table size $N$ to 5–10x the expected number of distinct active features to keep hash collision rate below 10%.
• How do you handle unseen new categories during production serving? Assign unseen categories to global target mean $\bar{y}_{\text{global}}$ (for Target Encoding), or map to a dedicated [UNK] (Unknown) token / zero vector (for Entity Embeddings).