Learning unified distance metric for heterogeneous attribute data clustering

Yiqun Zhang, Mingjie Zhao, Yizhou Chen, Yang Lu, Yiu-ming Cheung

Introduction

Clustering datasets with "mixed data"—a combination of numerical (e.g., income) and categorical (e.g., occupation) attributes—presents a significant challenge in data science. Traditional methods often struggle with the "apples and oranges" problem, where different data types lack a common basis for comparison. The HARR (Heterogeneous Attribute Reconstruction and Representation) paradigm addresses this by projecting all attributes into a unified, learnable distance space, treating categorical values as points in a "pseudo-numerical" 1D space.

The Mixed Data Challenge

Numerical data typically resides in a well-defined Euclidean space. However, categorical data is often embedded in an implicit space where distances are not inherently clear. As shown in the attribute hierarchy, attributes are broadly divided into numerical and categorical types, with the latter further subdivided into nominal and ordinal categories.

Hierarchy of attribute types including numerical, nominal, and ordinal classifications.

Existing solutions usually rely on one-hot encoding, which can lose semantic relationships, or hybrid metrics like the k-prototypes algorithm, which fails to capture inherent connections between different attribute types. The goal of HARR is to establish a homogeneous basis where all attribute types can be compared and weighted fairly.

The HARR Framework

The HARR framework operates in two primary stages to bridge the gap between these disparate data types:

  1. Attribute Reconstruction: Instead of simple encoding, the model uses Conditional Probability Distributions (CPDs) to calculate "base distances" between categorical values. These values are then projected onto multiple one-dimensional spaces. For a categorical attribute with $v$ values, it creates $\gamma = v(v-1)/2$ projection spaces, effectively transforming categorical data into "pseudo-numerical" sub-attributes that retain rich structural information.
  2. Joint Learning & Weighting: The model iteratively updates cluster assignments, prototypes, and attribute weights. It employs a "Discriminative" Weighting Strategy, calculating weights based on the ratio of inter-cluster separation to intra-cluster compactness. This prevents the model from over-weighting attributes that merely have low variance.
Conceptual representation of how numerical, nominal, and ordinal attributes map values to semantic concepts.

By projecting these various types into a shared 1D Euclidean space, the framework treats numerical, nominal, and ordinal attributes as the same species of data, unified by their intrinsic semantic concepts.

Experimental Evaluation

The study evaluated HARR against 10+ state-of-the-art methods across 14 real-world public datasets (e.g., Heart Failure, Mushroom, Australia Credit) and a large-scale synthetic dataset ($n=100,000$).

Key findings include:

  • Superior Accuracy: The matrix-based version, HARR-M, consistently achieved the highest Adjusted Rand Index (ARI) and Clustering Accuracy (CA), outperforming vector-based weighting (HARR-V).
  • Fine-Grained Clustering: t-SNE visualizations demonstrated that HARR produces tighter, more distinct cluster separations than traditional one-hot encoding.
  • Scalability: The algorithm maintains linear time complexity relative to the number of data objects, ensuring viability for large-scale analysis.

Conclusion

HARR provides a parameter-free, adaptive approach to mixed-data clustering. By expanding the "Degree of Learning Freedom" (DoLF) through multi-space projections, it allows optimization algorithms to find the most effective representations for specific clustering tasks. While future work is needed to address noise and streaming data, HARR represents a significant step toward a unified metric for heterogeneous data.

Summary updated

Abstract

Datasets composed of numerical and categorical attributes (also called mixed data hereinafter) are common in real clustering tasks. Differing from numerical attributes that indicate tendencies between two concepts (e.g., high and low temperature) with their values in well-defined Euclidean distance space, categorical attribute values are different concepts (e.g., different occupations) embedded in an implicit space. Simultaneously exploiting these two very different types of information is an unavoidable but challenging problem, and most advanced attempts either encode the heterogeneous numerical and categorical attributes into one type, or define a unified metric for them for mixed data clustering, leaving their inherent connection unrevealed. This paper, therefore, studies the connection among any-type of attributes and proposes a novel Heterogeneous Attribute Reconstruction and Representation (HARR) learning paradigm accordingly for cluster analysis. The paradigm transforms heterogeneous attributes into a homogeneous status for distance metric learning, and integrates the learning with clustering to automatically adapt the metric to different clustering tasks. Differing from most existing works that directly adopt defined distance metrics or learn attribute weights to search clusters in a subspace. We propose to project the values of each attribute into unified learnable multiple spaces to more finely represent and learn the distance metric for categorical data. HARR is parameter-free, convergence-guaranteed, and can more effectively self-adapt to different sought number of clusters $k$. Extensive experiments illustrate its superiority in terms of accuracy and efficiency.
BibTeX
@article{zhang2025learning,
  author = {Yiqun Zhang and Mingjie Zhao and Yizhou Chen and Yang Lu and Yiu-ming Cheung},
  title = {{Learning unified distance metric for heterogeneous attribute data clustering}},
  journal = {Expert Systems with Applications},
  year = {2025},
  doi = {10.1016/j.eswa.2025.126738},
}

Loading related content...

Figure