# Dimensionality Reduction for Categorical Data

arXiv: https://arxiv.org/abs/2112.00362 · HTML: https://mlsanity.com/paper/2112.00362/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 68 references that are in the map.
- First posted on arXiv 1 Dec 2021.

## Builds on (most cited first, 4 of 4)

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [Efficient Sketching Algorithm for Sparse Binary Data](https://mlsanity.com/paper/1910.04658/) (2019)
- [Efficient Compression Technique for Sparse Sets](https://mlsanity.com/paper/1708.04799/) (2017)
- [Effective Data-aware Covariance Estimator from Compressed Data](https://mlsanity.com/paper/2010.04966/) (2020)

## Built on by (most cited first, 4 of 4)

- [Significance-Based Categorical Data Clustering](https://mlsanity.com/paper/2211.03956/) (2022)
- [SPINEX: Similarity-based Predictions and Explainable Neighbors Exploration for Regression and Classification Tasks in Machine Learning](https://mlsanity.com/paper/2306.01029/) (2023)
- [MoE-Enhanced Explainable Deep Manifold Transformation for Complex Data Embedding and Visualization](https://mlsanity.com/paper/2410.19504/) (2024)
- [Tutorial: a priori estimation of sample size, effect size, and statistical power for cluster analysis, latent class analysis, and multivariate mixture models](https://mlsanity.com/paper/2309.00866/) (2023)

## Abstract (arXiv)

Categorical attributes are those that can take a discrete set of values, e.g., colours. This work is about compressing vectors over categorical attributes to low-dimension discrete vectors. The current hash-based methods compressing vectors over categorical attributes to low-dimension discrete vectors do not provide any guarantee on the Hamming distances between the compressed representations. Here we present FSketch to create sketches for sparse categorical data and an estimator to estimate the pairwise Hamming distances among the uncompressed data only from their sketches. We claim that these sketches can be used in the usual data mining tasks in place of the original data without compromising the quality of the task. For that, we ensure that the sketches also are categorical, sparse, and the Hamming distance estimates are reasonably precise. Both the sketch construction and the Hamming distance estimation algorithms require just a single-pass; furthermore, changes to a data point can be incorporated into its sketch in an efficient manner. The compressibility depends upon how sparse the data is and is independent of the original dimension -- making our algorithm attractive for many real-life scenarios. Our claims are backed by rigorous theoretical analysis of the properties of FSketch and supplemented by extensive comparative evaluations with related algorithms on some real-world datasets. We show that FSketch is significantly faster, and the accuracy obtained by using its sketches are among the top for the standard unsupervised tasks of RMSE, clustering and similarity search.