PaperlayerView exact revision on arXiv

Source-linked AI summary

Survey of state-of-the-art mixed data clustering algorithms

Amir Ahmad, Shehroz S. Khan

arXiv:1811.04364v6cs.LGcs.AIstat.ML

TL;DR

Mixed data clustering addresses datasets containing both numeric and categorical features, but similarity is difficult to compute because operations such as summation or averaging do not directly apply across feature types. This paper develops a five-theme taxonomy and reviews state-of-the-art methods, applications, challenges, and future directions. It concludes by identifying unresolved issues including initialization, model complexity, evaluation, and information loss from transformation.

  • Problem

    Clustering mixed datasets is important because they are common in real-world applications, yet computing similarity across numeric and categorical features remains difficult.

  • Method

    The paper proposes a five-theme taxonomy, reviews methods within each theme, and analyzes their applications, strengths, weaknesses, software, and research challenges.

  • Results

    The review identifies practical and methodological challenges involving initialization, cluster-number estimation, model complexity, evaluation, and mixed-data transformation.

  • Takeaways & Limitations

    The survey organizes the field and highlights open questions and guidelines for developing more effective mixed data clustering methods.

Abstract

from arXiv · show

Mixed data comprises both numeric and categorical features, and mixed datasets occur frequently in many domains, such as health, finance, and marketing. Clustering is often applied to mixed datasets to find structures and to group similar objects for further analysis. However, clustering mixed data is challenging because it is difficult to directly apply mathematical operations, such as summation or averaging, to the feature values of these datasets. In this paper, we present a taxonomy for the study of mixed data clustering algorithms by identifying five major research themes. We then present a state-of-the-art review of the research works within each research theme. We analyze the strengths and weaknesses of these methods with pointers for future research directions. Lastly, we present an in-depth analysis of the overall challenges in this field, highlight open research questions and discuss guidelines to make progress in the field.

I. INTRODUCTION

Mixed datasets combine numeric and categorical features and are common in real-world applications, but defining similarity across both feature types remains difficult. The paper addresses this challenge through a taxonomy, literature review, application analysis, and discussion of future research.

  • Mixed datasets contain numeric and categorical features and occur frequently in health, marketing, medical, and finance applications.
  • Similarity is difficult to define because numeric and categorical distances may measure different notions of similarity and operate on different scales.Combining Euclidean distance for numeric features with Hamming distance for categorical features requires non-obvious proportions.
  • Most mixed data clustering algorithms focus on defining similarity measures for mixed features and then applying existing or new clustering techniques.
  • The paper introduces a taxonomy identifying five broad research themes and critically reviews the literature within them.
  • The survey analyzes application areas, strengths and weaknesses of methods, challenges, open research questions, and guidelines for advancing the field.

II. SURVEY OF OTHER REVIEW PAPERS

Earlier reviews of mixed data clustering are fragmented, incomplete, and often omit practical challenges, application areas, and future directions. This paper addresses these gaps with a broader review organized around a five-theme taxonomy.

  • Limitations of prior reviews: Earlier reviews cover only selected algorithm types, datasets, or clustering paradigms rather than the full mixed-data clustering literature.Examples include a review of five distance-based algorithms on three datasets, reviews limited to partitional and model-based clustering, and a basic clustering review without mixed-data algorithms.
  • Limitations of prior reviews: Prior reviews generally lack concrete research themes or a taxonomy to structure systematic investigation of the field.This limitation is identified directly in the paper’s assessment of earlier review articles.
  • Limitations of prior reviews: Earlier reviews also rarely identify major application areas or provide guidance for future development and progress.The paper specifically notes omissions concerning applications, future directions, and field-development guidelines.
  • Limitations of prior reviews: Most prior reviews overlook practical issues including data availability, algorithm scalability, big-data challenges, and interpretability.These omissions limit the practical guidance available to researchers and practitioners studying mixed-data clustering.
  • Paper’s response: The review aims to overcome the limitations of previous work and enhance knowledge of mixed data clustering through a more unified research structure.Mixed-data clustering has grown in popularity because real-world datasets commonly combine numeric and categorical features, yet the field lacks a unified framework.
  • Paper’s response: This paper introduces a taxonomy with five research themes: partitional, hierarchical, model-based, neural network-based, and other clustering algorithms.The “other” category groups emerging or less extensively studied methods that do not fit the four principal themes.

A. PARTITIONAL CLUSTERING

Partitional mixed-data clustering extends K-means-type ideas by combining mixed-feature centers, distances, and iterative cost functions. The surveyed variants address weighting, streams, constraints, fuzzy membership, and numeric recoding, while retaining concerns about initialization and cluster-count selection.

  • Most partitional methods combine a cluster center, a mixed-feature distance measure, and an iteratively minimized cost function.Numeric features may use means and Euclidean-like distances, while categorical features use representations such as modes or frequencies and Hamming-like distances.
  • Partitional algorithms are widely adopted because they scale linearly with the number of data points and can support parallelization frameworks such as MapReduce.
  • K-prototypes represents numeric cluster-center features by means and categorical features by modes, but its centers may poorly represent underlying clusters.Ahmad and Dey address related issues with data-derived categorical similarities, weighted numeric features, and frequency-based cluster centers.
  • Feature-weighted and distance-based variants report improvements over baseline K-prototypes, including W-K-prototypes and weightage Hamming plus Minkowski distance.The weightage Hamming method is reported to outperform the original K-prototypes algorithm.
  • Extensions cover mixed-data streams, constrained clustering, fuzzy membership, and conversion of categorical features into numeric representations for K-means.The stream method uses micro-clusters, while the constrained variant adds a constraint function to the K-prototypes cost function.
  • Partitional mixed-data methods inherit challenges involving cluster-center initialization and prior knowledge of the number of clusters.

1) Cluster Center Initialization

Cluster-center initialization is difficult because random selection can produce different outcomes across runs. Mixed-data methods use centrality, density peaks, search algorithms, or alternative objectives, but some introduce quadratic complexity.

  • Random initialization can produce different clustering outcomes across runs, reducing confidence in partitional clustering results.
  • Centrality-based initialization uses neighbor sets and distances to compute initial centers, but has quadratic complexity instead of linear K-means-type complexity.
  • Density-peak initialization selects higher-density points as centers, but its quadratic complexity limits usefulness for K-means-type algorithms.
  • A K-harmonic extension is reported as more robust to initial-center selection than other K-means-type mixed-data algorithms.
  • Combining an evolutionary algorithm with K-prototypes makes the method less sensitive to cluster initialization through global search.

2) Number of Clusters

Partitional mixed-data algorithms commonly assume that the number of clusters is known, although the selected value may not match the data’s natural cluster count. Other clustering families require similarity matrices and linkage criteria, often with substantial computational costs.

  • 2) Number of Clusters: Many partitional mixed-data methods assume that the number of clusters is known in advance, but the chosen value may not equal the natural number of clusters.
  • 2) Number of Clusters: A mixed-data cluster-validity index combines numeric and categorical components, weighting each according to the number of categories.
  • 2) Number of Clusters: A genetic-algorithm K-means method computes the number of clusters automatically, but its complexity is quadratic.
  • Hierarchical clustering: Hierarchical clustering requires a similarity matrix and linkage criterion, with the similarity metric influencing cluster shape.
  • Hierarchical clustering: Most hierarchical algorithms require O(n^3) time and O(n^2) memory for n data points.
  • Hierarchical clustering: Hierarchical mixed-data methods use measures including Gower, Goodall, concept-hierarchy distances, and combined categorical–numeric similarity matrices.

C. MODEL-BASED CLUSTERING

Model-based clustering represents mixed observations through statistical or latent-variable models, including mixture, Gaussian-multinomial, and copula approaches. These methods can capture mixed features and dependencies, but outcomes depend on model choices and computational cost can be high.

  • Model-based methods assume that each data point matches a user-defined model, often a statistical distribution.
  • Inappropriate model or parameter choices can yield undesirable clustering outcomes, and model-based methods are generally slower than partitional algorithms.
  • AUTOCLASS and related mixture models support datasets containing both categorical and numeric features through finite-mixture, threshold, latent-class, or latent-feature formulations.
  • ClustMD uses a latent Gaussian-mixture variable and EM-based estimation, but becomes computationally expensive as the number of features increases.
  • Copula-based methods model dependencies between numeric and categorical features, while vine copulas provide hierarchical pairwise dependency modeling.
  • KAMILA uses Gaussian-multinomial mixture properties to balance numeric and categorical effects without specifying feature weights or strong parametric assumptions for numeric features.

D. NEURAL NETWORK-BASED CLUSTERING

Neural-network approaches for mixed-data clustering mainly use SOM and ART, but both require categorical features to be transformed before clustering. Other reviewed methods use concept hierarchies, frequency-based distances, or learned sparse representations to address mixed features.

  • Most neural-network research on mixed-data clustering focuses on self-organizing maps and adaptive resonance theory.
  • Traditional SOM- and ART-based methods handle numeric features but cannot directly process categorical features.
  • Categorical features are commonly converted into binary features and then treated as numeric inputs.
  • Hsu’s generalized SMO model computes categorical-value similarity using a distance hierarchy based on concept hierarchies.
  • A frequency-based distance measure relates categorical-value distance to feature frequencies, but it does not consider feature-value co-occurrence.
  • Fuzzy ART can create prototypes that encode mixed datasets into a new feature space, where K-means is then applied.

E. OTHER

The ‘Other’ theme gathers newer mixed-data clustering directions that do not fit established themes, including ensembles, spectral, subspace, density-based, conceptual, incremental, and stream methods. These approaches vary in how they represent similarity, reduce dimensionality, handle scale, and adapt to evolving data.

  • E. OTHER: The ‘Other’ theme groups newer or insufficiently explored mixed-data clustering directions that fall outside established research themes.
  • E. OTHER: Spectral methods compute similarities before clustering in a reduced space, including separate numeric and categorical similarity matrices combined by weighted summation.
  • E. OTHER: Subspace methods seek clusters in different feature subspaces using mixed-data distances, cluster similarity, or feature weighting.
  • E. OTHER: Density-based, conceptual, incremental, affinity-propagation, and stream methods adapt established clustering paradigms to mixed features, missing values, or changing data.
  • E. OTHER: Ensemble methods can build diverse base clusterings sequentially, but the described approach has quadratic complexity and depends on random initialization.
  • E. OTHER: INTEGRATE uses minimum description length to balance numeric and categorical effects and is scalable to large datasets.
  • E. OTHER: Three-way clustering extends mixed-data distances to distinguish certain membership, uncertain membership, and certain non-membership.

IV. ANALYSIS OF THE SURVEY

The survey finds that partitional methods remain favored because they are interpretable, scalable, and parallelizable, although mixed-data similarity and cost functions remain difficult. Evaluation and comparison are also limited by metric choices, inconsistent datasets, and small benchmarks.

  • Partitional algorithms are favored for simpler interpretation and implementation, linear scaling in data objects, and adaptability to parallel architectures.
  • Choosing an appropriate similarity measure and cost function for mixed data remains a challenge in partitional clustering.
  • Non-partitional approaches may offer better clustering outcomes but can involve nonlinear time or space complexity or unsupported distributional assumptions.
  • New mixed-data directions include subspace, spectral, ensemble, big-data, and data-stream clustering.
  • Clustering evaluation is difficult without class labels, yet surveyed studies commonly use clustering accuracy and other label-based measures.
  • The survey reports limited comparisons among competitive algorithms because researchers use different datasets, many of which are small and potentially unrepresentative.
  • The next section lists publicly available software packages and major application areas for mixed-data clustering.

V. SOFTWARE AND APPLICATIONS

Public implementations make mixed-data clustering methods available through software packages and libraries, with most surveyed packages provided in R and some methods implemented in Matlab.

  • Most publicly available mixed-data clustering software packages are implemented in R.
  • Available R implementations include K-prototypes, ClustMD, Gower’s similarity matrix, CluMix, and KAMILA.
  • The software ecosystem includes both hierarchical and K-means-type partitioning functionality for mixed-data clustering and visualization.
  • The Ahmad and Dey mixed-data clustering algorithm is available in Matlab.

B. MAJOR APPLICATION AREAS

Mixed-data clustering is applied across health, business, marketing, finance, education, and other domains to identify groups for practical analysis. The paper highlights health informatics and business analytics as especially impactful application areas because they address problems related to people.

  • Major application areas: Mixed-data clustering supports applications spanning health, marketing, business, finance, social studies, education, archaeology, and intrusion detection.Examples include metabolic-syndrome analysis, customer and financial segmentation, student dropout prediction, archaeological classification, and security monitoring.
  • Research impact: The authors argue that health and business informatics may have greater impact because they address real-world problems related to people.This is presented as a motivation for prioritizing these application areas while recognizing the importance of mixed-data clustering across multiple domains.
  • Health informatics: Health applications combine categorical and numeric patient information from electronic health records and sensors for evidence-based care analysis.Electronic health records may include medical histories, diagnoses, medications, treatment plans, allergies, images, and laboratory results.
  • Business analytics: Business analytics uses mixed customer, company, and employee data to study markets, financial health, productivity, and satisfaction.Examples combine categorical attributes such as customer type, preference, department, or region with numeric attributes such as age, salary, and financial ratios.

B. CHALLENGES

The review identifies unresolved challenges across partitional, hierarchical, model-based, and neural-network-based mixed-data clustering. These include defining similarity and centers, initializing clusters, selecting cluster counts and models, and controlling computational complexity.

  • Partitional clustering: Partitional methods retain linear time complexity, but mixed numeric-categorical centers and the scale for combining distances remain unclear.The review reports no unanimous winner among available similarity measures and calls for better cluster-center representations.
  • Partitional clustering: No existing initialization method is both computationally inexpensive and consistent across different runs.The review also identifies estimating the natural number of clusters as an important challenge for interpreting mixed datasets.
  • Hierarchical clustering: Hierarchical clustering depends on a similarity matrix, making its effectiveness contingent on a well-defined distance between mixed data objects.The review states that mixed-data distance is not self-explanatory and requires further research.
  • Model-based clustering: Model-based methods face high model complexity, difficult parametric assumptions, and challenging modeling of dependencies between categorical and numeric features.The authors call for models with fewer parameters and lower complexity to support large real-world datasets.
  • Neural network-based clustering: Neural-network approaches centered on SOM and ART may produce poor topological mappings or incur high computational complexity.SOM methods may fail to match data-distribution structure, while ART models are typically governed by differential equations.

C. OPEN RESEARCH QUESTIONS AND GUIDELINES

The survey identifies open directions spanning robustness to imperfect and uncertain data, scalability, interpretability, domain knowledge, parameter selection, evaluation, and shared infrastructure. It concludes that progress requires broader methods, datasets, benchmarks, and publicly available implementations.

  • Data quality: Missing values can impair mixed-data clustering, while competing strategies either impute values first or incorporate missingness into the objective function.The survey notes that these approaches have not been sufficiently developed and compared.
  • Data quality: Uncertain mixed datasets remain largely unaddressed despite their presence in medical and socioeconomic applications.The authors identify clustering uncertain mixed datasets as an important research direction.
  • Scalability: Mixed-data clustering research must scale with increasing dataset sizes while preserving linear time complexity, particularly for partitional methods and online streams.Online clustering also faces challenges involving clustering quality, evaluation of new concepts, and concept drift.
  • High-dimensional data: Subspace clustering can handle high-dimensional mixed data, but extending additional approaches, including grid-based methods, remains necessary.The survey notes that subspace clustering permits points to belong to multiple axis-parallel subspaces.
  • Interpretability and knowledge: Domain knowledge can improve clustering accuracy and interpretation, yet constrained clustering has mainly been proposed for iterative partitional methods.Applications to hierarchical and density-based approaches remain unexplored.
  • Evaluation and infrastructure: Parameter-dependent results, difficult unsupervised evaluation, limited public datasets, and scarce shared code hinder reliable comparison and progress.The survey recommends community repositories, benchmarks, and public implementations to support comparison and development.
Loading 1811.04364v6…