Exploiting Categorical Structure Using Tree-Based Methods

Brian LucenaAISTATS 2020

Introduction

Standard machine learning models typically handle categorical variables through one of two extremes: one-hot encoding, which treats all categories as mutually unrelated, or ordinal encoding, which imposes a strict linear order. This paper introduces Structured Categorical Decision Trees (SCDT), a novel framework designed to leverage complex, non-linear relationships—such as geographical adjacencies or circular temporal patterns—to improve predictive performance, particularly in data-constrained environments.

The Problem of Categorical Representation

In traditional data science, numerical variables benefit from an inherent metric space where proximity is well-defined (e.g., the distance between 10 and 11 is smaller than between 10 and 100). Categorical variables, however, are often forced into representations that fail to capture their underlying structure.

Consider geographical data: a standard model might view Connecticut and Massachusetts as entirely distinct labels, ignoring their shared border. Similarly, temporal data like months are often encoded ordinally, which fails to recognize that December and January are adjacent. While modern Gradient Boosted Decision Trees (GBDTs) like CatBoost or LightGBM employ sophisticated categorical handling, they lack a mechanism to incorporate prior structural knowledge that is neither strictly linear nor independent. This research bridges that gap by allowing practitioners to define the "terrain" of their categorical data.

Methodology

The core of the SCDT approach is the mathematical concept of a Terrain, which defines the subsets of a categorical variable that are considered "averageable" or logically groupable.

  1. Graph-Based Terrains: The most intuitive implementation of a terrain is via a graph. Nodes represent categories (e.g., U.S. states), and edges represent relationships (e.g., shared borders). A subset of categories is considered averageable if it forms a connected component within the graph.
Graph-based terrain representing US state adjacencies
  1. The SCDT Algorithm: The algorithm generalizes standard decision tree splitting logic. Rather than searching for a split point along a real line, it identifies "maximally coarse" partitions of the terrain. For graph-based terrains, the author demonstrates that these partitions are binary, effectively splitting the graph into two connected subgraphs.
  2. Regularization via Sampling: Exhaustively searching all possible graph cuts is computationally intensive and prone to overfitting. To mitigate this, the author introduces the max_splits_to_search parameter. This parameter randomly samples a subset of valid splits during training, serving as a powerful form of regularization.

Experimental Setup

The SCDT framework was evaluated using California Weather Data (2000–2019) from the NOAA. The objective was to predict the probability of precipitation based on two predictors: the month of observation and the county. The study utilized two specific subsets:

  • CA-9: Nine counties in the San Francisco Bay Area.
  • CA-20: Twenty diverse counties representing various climates across California.

Performance was benchmarked against three standard approaches: One-Hot encoding, Ordinal encoding, and a "Siloed" approach (calculating raw means for every month-county pair).

Key Results and Insights

The experimental results, measured via log-loss curves, reveal a consistent performance hierarchy. The Structured approach, utilizing adjacency graphs for counties and circular graphs for months, significantly outperformed traditional encoding methods.

Performance comparison on the CA-20 dataset showing log-loss convergence

Data Efficiency and the Overfitting Paradox

The advantage of the Structured approach was most pronounced on small training sets (100 to 1,000 samples). By incorporating prior knowledge of geographical and temporal proximity, the model reached high accuracy with far less data than its counterparts. As training sets expanded toward 100,000 samples, all methods eventually converged toward the optimal siloed mean, though the Structured approach reached this asymptote much earlier.

Interestingly, the research identified an "Overfitting Paradox": searching fewer possible splits (a lower max_splits_to_search value) often improved performance on smaller datasets. By restricting the search space to a few random but "reasonable" graph-based splits, the model was less likely to find spurious patterns that failed to generalize.

Conclusion and Future Work

The SCDT framework demonstrates that incorporating prior structural knowledge into decision trees can yield substantial gains in data efficiency and predictive accuracy. While the current implementation requires pre-defined terrains, future research could explore methods for learning these structures directly from data. Additionally, the author suggests that this logic could be extended to structured target variables (e.g., hierarchical classification) to further refine loss functions in complex domains.

Summary updated

BibTeX
@inproceedings{lucena2020exploiting,
  author = {Brian Lucena},
  title = {{Exploiting Categorical Structure Using Tree-Based Methods}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}

Loading related content...

Figure