Most foundational machine learning and data mining algorithms share a silent assumption: the data lives in a metric space where distances can be geometrically measured. In a continuous space, numbers possess an inherent order ($1 < 2 < 3$) and a strict scale ($3 - 2 = 2 - 1$). This geometry allows us to easily compute Euclidean distances, find spatial averages (means), and trace gradients.
However, a massive portion of real-world data is categorical. Attributes like colors ([Red, Blue, Green]), professions ([Doctor, Lawyer, Engineer]), or system logs ([User ID, File Path]) are discrete and completely unordered. Forcing these symbols into a continuous coordinate system breaks the underlying math. As noted by Neruda and Dennig et al., assigning arbitrary numerical values to categories (such as mapping Red to 1, Blue to 2, and Green to 3) introduces artificial spatial relationships that do not exist. This "metric gap" severely limits our ability to cluster, visualize, or optimize discrete datasets (Faloutsos et al.; Garrido-Merchán et al.).
To resolve this, a major research direction focuses on designing proximity and similarity metrics that natively understand categorical data without relying on artificial coordinate mappings.
The Failure of Naive Binary Matching
The simplest way to handle categorical mismatches is the overlap metric (or binary distance): if two attributes are identical, their distance is 0; if they differ, their distance is 1.
While computationally trivial, this approach treats all mismatches as equally distinct. As Zhang et al. point out, this binary assumption discards crucial semantic nuance. For example, in a job dataset, the categories "Data Scientist" and "Machine Learning Engineer" share deep contextual similarities, whereas "Data Scientist" and "Plumber" do not. An overlap metric treats both pairs as equally distant (a distance of 1), leading to significant information loss and poor cluster discrimination.
To build better metrics, researchers look beyond the values themselves and instead analyze how categories behave in context.
Discovering Similarity via Contextual Co-occurrence
If categorical values cannot be measured directly, how do we determine if "Red" is closer to "Pink" than to "Green"? The answer lies in co-occurrence: analyzing how often discrete tokens appear alongside other attributes across the entire dataset.
Dataset Context Example:
Transaction 1: [Item: Rose, Color: Red, Type: Flower]
Transaction 2: [Item: Tulip, Color: Pink, Type: Flower]
Transaction 3: [Item: Cactus, Color: Green, Type: Plant]
Even though "Red" and "Pink" are distinct strings, they frequently co-occur
with the context "Flower", signaling an implicit proximity.
This insight powers several foundational categorical frameworks:
- Summary Co-occurrences: The CACTUS algorithm, introduced by Ganti et al., avoids computing explicit pairwise distances between records. Instead, it generates compact in-memory summaries of attribute co-occurrences, defining a cluster as a region where attributes strongly imply one another.
- Dynamical Systems: Gibson et al. treat a categorical database as a dynamical system. In this framework, similarity propagates iteratively: two values are deemed similar if they are associated with similar values across other attributes, uncovering deep, transitive relationships.
- Feature Value Couplings: Rather than treating attributes as independent, Pang models the complex conditional probabilities between different features. This approach, called Coupled Biased Random Walks (CBRW), measures similarity based on how heavily feature values interact, making it highly effective at identifying anomalies that break these contextual patterns.
Probabilistic Landscapes and Information Theory
Another powerful strategy bypasses geometric distance entirely by treating the dataset as a statistical landscape. Instead of calculating a geometric center (which is impossible without a coordinate system), these methods identify "probability peaks" or leverage information theory.
For instance, Chen et al. model high-dimensional categorical data by mapping data points to their nearest local probability modes using tree-structured graphical models. This shifts the definition of a cluster from a spatial grouping to a topographical peak in a probability distribution.
To account for complex, non-linear dependencies between nominal features, Leppä-aho et al. derive the Fisher kernel for Bayesian networks. By measuring similarity based on the gradient of the log-likelihood function of a generative model, the Fisher kernel provides a mathematically rigorous proximity measure that naturally respects the structural dependencies of the data. Furthermore, No demonstrates that transforming complex categorical distortion measures into logarithmic loss makes these discrete optimization problems far more mathematically tractable.
Learning Continuous Embeddings for Discrete Symbols
With the rise of representation learning, researchers have increasingly turned to optimization techniques to learn continuous distance metrics directly from discrete data.
Discrete Space Continuous Latent Space
[Red] ───┐ ┌───────────────┐
[Pink] ───┼─► [Optimization / Gradients] ─► │ Red Pink │ (Close proximity)
[Green] ───┘ │ Green │
└───────────────┘
Instead of relying on static heuristics, these methods map discrete symbols into a continuous latent space where standard geometric operations work perfectly:
- Supervised Dissimilarity Learning: Xie et al. propose a gradient-descent framework that maps categorical symbols into a real-valued space. By optimizing the mapping to minimize downstream classification errors, the model automatically discovers a continuous "learned dissimilarity" that captures true category relationships.
- Entity Embeddings: For complex, heterogeneous system logs where user IDs, IP addresses, and file paths lack any natural metric, Chen et al. utilize a probabilistic framework to learn entity embeddings. This maps discrete entities into a continuous vector space where standard distance-based anomaly detection can successfully isolate outliers.
Unlocking Downstream Algorithms
By resolving the metric gap, these advanced similarity measures allow traditional algorithms to be safely extended to categorical domains.
In partitioning and clustering, algorithms can swap geometric means for frequency-based modes or medoids, as seen in the evolution of the K-modes algorithm (Dinh et al.; Khan et al.) and robust K-medoids frameworks (Staples et al.). The authors of Robust Categorical Data Clustering Guided by Multi-Granular Competitive Learning demonstrate that leveraging multi-granular competitive learning can automatically discover nested cluster structures without information loss.
Similarly, in global optimization, designing specialized kernels allows Gaussian Processes to natively navigate categorical hyperparameter spaces without forcing artificial linear sequences onto discrete choices (Lévesque et al.). Ultimately, moving away from rigid coordinate geometry toward contextual, probabilistic, and learned metrics allows us to process categorical data with the same mathematical rigor as continuous numbers.
Key Foundational Work
Symbolic Nearest Mean Classifiers (1997) — contributed 2 concept elements to this direction.
The New Jersey Data Reduction Report (1997) — contributed 1 concept elements to this direction.
Genetic algorithm for extracting rules in discrete domain (1995) — contributed 1 concept elements to this direction.