Source-linked AI summary
Similarity encoding for learning with dirty categorical variables
Patricio Cerda, Gaël Varoquaux, Balázs Kégl
TL;DR
Dirty categorical variables combine high cardinality with redundant or morphologically varied representations, a setting that has received limited attention in statistical learning. The paper introduces similarity encoding, which builds features from similarities across categories, and evaluates it on seven real-world datasets. Similarity encoding improves prediction over established category and string encodings, with 3-gram similarity and reduced-dimensional representations offering practical choices.
Problem
Dirty categorical variables contain high-cardinality, redundant or erroneous string representations, while this setting has received limited attention in statistical-learning research.
Method
Similarity encoding generalizes one-hot encoding by building feature vectors from string similarities across categories and exposing redundancy to supervised learning.
Results
Empirical results on seven real-world datasets show that similarity encoding improves prediction over one-hot encoding and bags of character n-grams.
Takeaways & Limitations
3-gram similarity is a practical choice for morphological resemblance, while random projections or prototype subsets retain most benefits with lower dimensionality.
Takeaways & Limitations
Similarity encoding creates a dense feature matrix, increasing memory and computational costs; dimensionality reduction mitigates this cost while retaining most benefits.
Abstract
from arXiv · showhide
For statistical learning, categorical variables in a table are usually considered as discrete entities and encoded separately to feature vectors, e.g., with one-hot encoding. "Dirty" non-curated data gives rise to categorical variables with a very high cardinality but redundancy: several categories reflect the same entity. In databases, this issue is typically solved with a deduplication step. We show that a simple approach that exposes the redundancy to the learning algorithm brings significant gains. We study a generalization of one-hot encoding, similarity encoding, that builds feature vectors from similarities across categories. We perform a thorough empirical validation on non-curated tables, a problem seldom studied in machine learning. Results on seven real-world datasets show that similarity encoding brings significant gains in prediction in comparison with known encoding methods for categories or strings, notably one-hot encoding and bag of character n-grams. We draw practical recommendations for encoding dirty categories: 3-gram similarity appears to be a good choice to capture morphological resemblance. For very high-cardinality, dimensionality reduction significantly reduces the computational cost with little loss in performance: random projections or choosing a subset of prototype categories still outperforms classic encoding approaches.
1 Introduction
The paper addresses high-cardinality, dirty categorical variables, where redundant or erroneous string forms challenge one-hot encoding and conventional categorical methods. It introduces similarity encoding as a simple way to expose category similarities during supervised learning.
- Existing encoding: One-hot encoding represents each category with an orthogonal, equidistant feature vector.This matches nominal-category assumptions but does not represent relationships among morphologically similar strings.
- Motivation: Dirty categorical data can contain multiple morphological forms of the same entity, including variants caused by typos.These representations should be closer in feature space than unrelated categories, but one-hot encoding treats them as separate entities.
- Research gap: Existing categorical encoding methods generally do not address errors or categories absent from the training set.This leaves dirty-category encoding insufficiently covered by statistical-learning methods.
- Motivation: Entity resolution can merge variants before learning, but merging uncertainty is not exposed to the model and learning objectives do not guide resolution.The paper instead assumes that exposing similarities may be sufficient without fully solving entity resolution.
- Contribution: The paper benchmarks dirty-category prediction on seven real-world datasets and proposes similarity encoding as a softer generalization of one-hot encoding.The approach is designed for high-cardinality categorical variables and is evaluated in supervised-learning settings.
2 Problem setting: non-standardized categorical variables
Non-standardized categorical variables have unknown category sets and may contain variants whose entity relationships are unclear. Their cardinality can grow with sample size, while related categories may still carry shared structure.
- Non-standardized categories: Non-standardized categories are unknown before data collection and may contain multiple company-name variants for the same entity.The Open Payments company-name variable illustrates this issue with categories containing the word Pfizer.
- Analytical challenge: The exact relationship among dirty categories may be unclear without external expert information.Category frequencies can also differ by several orders of magnitude, potentially indicating data-collection errors.
- Cardinality: Cardinality often grows with sample size in dirty categorical variables.This pattern occurs across the seven datasets analyzed in the paper.
- Sources of dirtiness: Dirty categorical data can arise from typographical errors, extraneous data, abbreviations, aliases, encoding formats, special characters, and concatenated hierarchical data.These mechanisms create multiple string forms for category values.
- Shared structure: Related categories may share meaningful structure even when they are not identical entities.For example, cervical and non-cervical spinal fusion categories both share the broader concept of spinal fusion.
3 Related work and common practice
Prior work commonly encodes categorical values as vectors, but dirty high-cardinality data challenges assumptions of finite, known, mutually exclusive categories and creates unresolved issues for unseen or morphologically related values.
- Common practice: Categorical encoding converts table values into feature vectors so statistical-learning models can use them as numerical inputs.The feature matrix X contains the encoded representations of the table’s attributes.
- Common practice: One-hot encoding assigns each category a separate indicator dimension, making categories orthogonal and equidistant in the resulting vector space.Its variants include dummy, effects, contrast, and nonsense coding, which have equal linear-regression R2 performance but differ in interpretability.
- Dirty categories: Dirty categorical data can violate one-hot assumptions because categories may be morphologically related rather than mutually exclusive.Misspellings and other variants may represent overlapping categories, while one-hot encoding treats them as separate entities.
- Dirty categories: One-hot encoding provides no heuristic for categories unseen during training, assigning every new test category the zero vector and causing collisions among multiple new categories.This limitation is especially relevant when category domains depend on the training set.
- Alternative approaches: High-cardinality variables increase feature dimensionality and computational cost, motivating hashing, clustering, target statistics, neural embeddings, and character n-gram representations.Hashing reduces dimensionality but ignores morphological similarity; target-based methods can be undermined when dirty categories are rare, while domain-specific tabular entries limit pretrained semantic embeddings.
4 Similarity encoding: robust feature engineering
Similarity encoding generalizes one-hot encoding by replacing binary category indicators with string similarities, while dimensionality-reduction strategies address the resulting high-dimensional representations.
- Similarity encoding: Similarity encoding generalizes one-hot encoding by representing each category with its similarities to all known categories.For a variable with cardinality k, the resulting feature vector has k similarity values.
- String similarities: Levenshtein-ratio measures similarity from the minimum weighted edit operations required to transform one string into another.Insertions, deletions, and most operations have weight 1, whereas replacements have weight 2 in this implementation.
- String similarities: Jaro-Winkler similarity extends Jaro similarity by emphasizing the longest common prefix between two strings.Its formulation uses matching characters, transpositions, prefix length, and a scaling factor.
- String similarities: 3-gram similarity compares sets of consecutive character n-grams using the Dice coefficient, making strings with shared substrings close in feature space.For example, Paris and Parisian share three 3-grams.
- Dimensionality reduction: Random projections and prototype-based encodings reduce the dimensionality of similarity features, but projections require similarities to all categories and can reduce interpretability.Prototype methods instead compute similarities to a small representative subset, such as frequent categories or cluster representatives.
- Dimensionality reduction: Unlike preprocessing through deduplication, similarity-based clustering retains each category while encoding its similarities to cluster-related prototypes.This connects similarity encoding to database record-linkage strategies without replacing variants by cluster centers.
5 Empirical study of similarity encoding
The empirical study evaluates similarity encoding across seven real-world datasets, classifiers, and dimensionality-reduction strategies. Similarity methods generally rank best, with 3-gram similarity performing especially strongly, while dimensionality reduction preserves most benefits at lower cost.
- Experimental design: The study evaluates encoding methods on seven real-world datasets using standardized prediction pipelines and repeated train/test splits.The selected categorical variable has high cardinality, and performance is assessed with gradient boosting, ridge regression, and other classifiers or regressors.
- Encoding comparisons: Similarity encoding methods achieve the best average rankings across datasets, with 3-gram similarity performing best for both gradient boosting and ridge regression.For ridge regression, 3-gram similarity is the best method on every dataset.
- Classifier comparisons: Across linear and tree-based models, 3-gram similarity reduces the performance gap by providing a better vector representation of categories.The comparison includes ridge, logistic regression, random forest, and gradient boosting; tree learners were not hyperparameter-tuned.
- Dimensionality reduction: Random projections, prototype-category selection, and clustering-based reductions are evaluated on six datasets, while strong reduction to d=100 retains most similarity-encoding benefits.Medical charges is excluded from the dimensionality-reduction figure because its categorical variable has smaller cardinality.
6 Discussion
Similarity encoding improves learning from dirty categorical variables by exposing similarity among categories, with 3-gram similarity especially effective and dimensionality reduction preserving much of its benefit. Benchmarks on seven real-world datasets support practical choices for high-cardinality settings, while dense representations increase computational demands.
- Similarity encoding: Similarity encoding generalizes one-hot encoding by representing categories through their similarities rather than treating every category as unrelated.The method projects categories onto a dictionary of reference n-grams and weights n-grams according to how well they capture category similarity.
- Empirical benchmarks: Benchmarks on seven real-world dirty tables provide empirical evidence across diverse high-cardinality categorical variables.The datasets are openly available and support exploration of trade-offs among encoding approaches.
- Similarity choices: Bimodal similarity distributions in medical charge, employee salaries, and traffic violations coincide with the largest gains over one-hot encoding.In these datasets, similarity encoding produces vector representations where a non-negligible number of category pairs are close.
- Classifier effects: 3-gram similarity reduces the performance gap between linear and tree-based classifiers by providing a better vector representation of categories.In the reported experiments, linear models slightly outperformed tree-based models, whose hyperparameters were not tuned.
- Computational trade-offs: Dimensionality reduction preserves most benefits of similarity encoding even with d=100, while reducing its dense-matrix memory and computational costs.With Gradient Boosting, reducing similarity encoding to d=30 still outperforms one-hot encoding.
- Computational trade-offs: Prototype selection and random projection support online learning and datasets that do not fit in memory, while new categories can be encoded without retraining from scratch.The paper reports selecting 100 prototypes on subsampled data, for instance with k-means clustering, and requires no categorical data cleaning.
7 Conclusion
Similarity encoding improves representation and prediction for dirty or high-cardinality categorical variables across seven real-world datasets, without prior data cleaning. The paper recommends 3-gram similarity and reports that dimensionality reduction can retain these benefits at lower cost.
- Similarity encoding improves prediction on seven real-world datasets without any prior data-cleaning step.It also outperforms representing categories with bags of n-grams.
- 3-gram similarity is a good choice for capturing morphological resemblance between categories and encoding new categories absent from training.
- Random projections provide strong dimensionality reduction with little loss in performance, while retaining advantages over classic encoding approaches.
- The methodology supports online-learning settings and can enable tractable analysis of very large datasets without data cleaning.
- The paper presents statistical learning on non-curated tables as a relatively understudied topic and releases benchmark datasets to encourage further work.
8 Appendix
The appendix describes seven real-world datasets, preprocessing, repeated train-test evaluation, performance metrics, classifier parametrization, and prediction-time measurement. The datasets cover regression, binary classification, and multiclass classification with high-cardinality categorical variables.
- 8.1 Datasets description: The seven datasets include medical charges, employee salaries, open payments, a Midwest survey, traffic violations, road safety, and beer reviews.
- 8.1 Datasets description: The prediction tasks comprise regression, binary classification, and multiclass classification, with targets including payments, salaries, payment status, region, violation type, driver sex, and beer style.
- 8.1 Datasets description: Selected categorical variables have cardinalities ranging from 385 for employee position titles to 4,634 for beer names.
- Computational cost: Table 3 reports average prediction times in seconds for 3-gram similarity encoding with k-means dimensionality reduction.
- Data preparation: Large datasets were capped at 100,000 samples, while beer reviews and road safety used 10,000 samples because their categorical variables had the largest cardinalities.
- Data preparation: Missing values outside the selected categorical variable were removed, selected-category missing entries became ‘nan’, entries were lowercased, and feature columns were standardized.
- Evaluation: Each task used 100 random 80/20 train-test splits, stratification for binary classification, and task-specific metrics: R2, average precision, or accuracy.
- Classifier parametrization: The experiments used LogisticRegressionCV, RidgeCV, GradientBoosting, and RandomForest, generally with default parameters and 100 estimators for ensemble methods.