🤖 machine learning

A Deterministic Information Bottleneck Method for Clustering Mixed-Type Data

Original authors: Efthymios Costa, Ioanna Papatsouma, Angelos Markos

Published 2026-02-02

📖 5 min read🧠 Deep dive

Original authors: Efthymios Costa, Ioanna Papatsouma, Angelos Markos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a party planner trying to group guests into conversation circles. Some guests are very chatty and talk about everything (continuous data, like height or income), while others only speak in specific categories, like "likes sports," "loves art," or "prefers quiet" (categorical data).

The problem is: How do you mix these two very different types of people into groups where everyone feels they belong, without letting the loud talkers drown out the quiet categorizers, or vice versa?

This paper introduces a new tool called DIBmix to solve exactly that problem. Here is how it works, broken down into simple concepts:

1. The Core Idea: The "Information Bottleneck"

Think of the Information Bottleneck as a strict filter at a party entrance.

The Goal: You want to compress a huge list of 1,000 guests into just 5 conversation circles.
The Rule: You want to keep the most important details about who fits with whom, but throw away the noise.
The Catch: If you make the circles too small, you lose the big picture. If you make them too big, everyone is just standing in one giant, messy group.

The authors use a mathematical "tuning knob" (called beta) to balance this. They want the groups to be distinct enough to be useful, but not so rigid that they force people into groups where they don't belong.

2. The New Challenge: Mixing "Apples and Oranges"

Most old party-planning tools (algorithms) are bad at mixed data.

Some tools only know how to measure distance (like "who is standing 5 feet away?"). This works for height or weight, but you can't measure the "distance" between "Cat Lover" and "Dog Lover" easily.
Other tools try to force everything into numbers, which can distort the reality of the categories.

DIBmix is special because it uses a Universal Translator (called a Generalised Product Kernel). It creates a custom "similarity score" for every pair of guests.

If two people are both 6 feet tall, they get a high score.
If two people both love "Sci-Fi," they get a high score.
If one is 6 feet and loves Sci-Fi, and the other is 5 feet and loves Sci-Fi, the tool calculates a combined score that respects both the height difference and the shared interest.

3. The Secret Sauce: Balancing the Volume

The biggest trick in this paper is how they handle the "volume" of different variables.
Imagine you have a microphone for "Height" and a microphone for "Favorite Color." If you turn the "Height" mic up too loud, it drowns out the "Color" mic. The groups will form based only on height, ignoring the colors.

The authors developed a Systematic Volume Control:

They automatically adjust the sensitivity (bandwidth) of the microphones.
They ensure that the "Height" mic and the "Color" mic contribute equally to the decision-making process.
This prevents the algorithm from getting biased toward whichever type of data happens to be more numerous in the room.

4. Keeping the Groups Alive (The Adaptive Knob)

Sometimes, when you try to force people into 5 groups, the algorithm might accidentally put everyone into 4 groups and leave one group empty (or merge two groups together).

The authors added an Adaptive Safety Mechanism:

The "tuning knob" (beta) doesn't stay fixed. It changes slightly with every step of the process.
If it looks like a group is about to disappear, the knob automatically tightens to save that group.
This ensures you always get exactly the number of groups you asked for, even if the groups are very different sizes (e.g., one huge group and one tiny group).

5. Did it Work? (The Party Test)

The authors tested DIBmix in two ways:

The Simulation Lab: They created 28,800 fake parties with different rules (some with equal groups, some with one giant group and many tiny ones; some with lots of categories, some with lots of numbers).
- Result: DIBmix was the best at finding the "real" groups, especially when the groups were uneven in size or when the data was a true mix of numbers and categories.
The Real World: They tested it on 10 real datasets from a public library (like medical records or credit applications).
- Result: It performed very well, often beating established methods like K-Prototypes or KAMILA. It was particularly good at finding meaningful patterns in datasets where numbers and categories were balanced.

Summary

DIBmix is a smart, flexible tool for grouping mixed data. It acts like a fair moderator at a party, ensuring that both the "quantitative" guests (numbers) and the "qualitative" guests (categories) get an equal say in who sits with whom. It uses a dynamic tuning system to ensure no group gets left behind, making it a powerful new option for organizing messy, real-world data.

Technical Summary: A Deterministic Information Bottleneck Method for Clustering Mixed-Type Data

Problem Statement
Clustering mixed-type data—datasets comprising both continuous and categorical (nominal and ordinal) variables—presents significant challenges due to the heterogeneity of variable types. Traditional clustering algorithms often struggle to balance the contributions of these disparate variable types, leading to suboptimal cluster structures. While existing methods such as K-Prototypes, KAMILA, and distance-based approaches (e.g., PAM with Gower's dissimilarity) offer solutions, they often rely on centroid-based assumptions or specific distance metrics that may not fully capture the underlying information structure of heterogeneous data. Furthermore, many existing approaches lack a unified theoretical framework that naturally handles continuous, nominal, and ordinal variables without requiring extensive preprocessing like one-hot encoding, which can obscure cluster structures and increase dimensionality.

Methodology: DIBmix
The paper proposes DIBmix, a clustering algorithm based on the Deterministic Information Bottleneck (DIB) framework, extended to handle mixed-type data. The core objective is to find a compressed representation $T$ (clusters) of the input data $X$ that maximizes the mutual information with the data's location $Y$ in the mixed-attribute space, subject to a compression constraint.

Key methodological components include:

Generalized Product Kernels: To estimate the joint density $p(x, y)$ for mixed data, the authors employ a generalized product kernel. This integrates:
- Gaussian kernels for continuous variables.
- Aitchison & Aitken kernels for nominal (unordered categorical) variables.
- Li & Racine kernels for ordinal (ordered categorical) variables.
  This approach avoids assuming variable independence, using the kernel product as a weighting mechanism for robust density estimation.
Optimization Framework: The algorithm seeks to minimize the objective function $H(T) - \beta I(Y; T)$ , where $H(T)$ is the entropy of the cluster assignments (acting as a regularizer for cluster sizes) and $I(Y; T)$ is the mutual information between the clusters and the data locations. The parameter $\beta$ controls the trade-off between compression and relevance.
Adaptive Hyperparameter Selection:
- Bandwidth Selection: A systematic strategy is proposed to equalize the contributions of continuous and categorical variables. This involves defining kernel ratios (e.g., average furthest-neighbour kernel ratio for continuous variables and disagreement ratios for categorical variables) and tuning bandwidths to ensure no single variable type dominates the similarity matrix.
- Adaptive $\beta$ : Unlike standard DIB implementations where $\beta$ is fixed, DIBmix employs an adaptive updating scheme for the regularisation parameter $\beta$ at each iteration. This ensures that the algorithm converges to a solution with exactly $C$ non-empty clusters, even when the data contains imbalanced cluster sizes, by preventing the smallest cluster from vanishing.
Scalability: For large datasets, the method utilizes the Nyström approximation to reduce the computational complexity of constructing the full similarity matrix from $O(n^2)$ to $O(n\sqrt{n})$ , making the approach feasible for large-scale applications.

Key Contributions
The paper outlines three primary contributions:

Framework Extension: Adapting the DIB framework to natively handle mixed-type data (continuous, nominal, and ordinal) without requiring dimensionality reduction or one-hot encoding.
Systematic Hyperparameter Strategy: Proposing a method for selecting bandwidths and the regularisation parameter $\beta$ that balances variable contributions and guarantees a valid partition into a predetermined number of clusters, addressing the issue of imbalanced cluster sizes.
Comprehensive Evaluation: Benchmarking DIBmix against four established methods (KAMILA, K-Prototypes, FAMD with K-Means, and PAM with Gower's dissimilarity) across extensive simulations and real-world datasets.

Results
The performance of DIBmix was evaluated through:

Simulations: 28,800 synthetic datasets were generated varying in sample size, number of clusters, variable proportions, overlap levels, and cluster shapes.
- DIBmix achieved the highest median Adjusted Rand Index (ARI) and Adjusted Mutual Information (AMI) compared to all competitors.
- It demonstrated particular robustness in scenarios with imbalanced cluster sizes and low to moderate cluster overlap.
- Effect sizes (partial $\eta^2$ ) indicated that DIBmix consistently outperformed competitors, with values ranging from 0.32 to 0.99.
Real-World Benchmarks: The method was tested on ten publicly available UCI datasets.
- DIBmix achieved the best ARI in four out of ten datasets.
- It performed best when datasets contained a balanced mix of variable types.
- Performance was competitive but slightly lower than FAMD or K-Prototypes in datasets dominated almost exclusively by either categorical or continuous variables.
- A Friedman test on the ten datasets showed DIBmix had the best average rank (2.45), though statistical significance was not reached due to the small number of datasets and the critical difference threshold.

Significance and Claims
The authors claim that DIBmix establishes a theoretically grounded alternative for mixed-type data clustering. Its significance lies in:

Handling Imbalance: Unlike traditional centroid-based algorithms that often favor equally sized clusters, DIBmix's entropy-based objective function allows for and effectively handles highly imbalanced cluster sizes.
Theoretical Rigor: By utilizing the Information Bottleneck principle, the method provides a principled way to extract relevant information while compressing data, offering a different perspective from distance-based or model-based approaches.
Interpretability: The framework allows for the quantification of variable importance via mutual information, helping to identify which features drive the clustering structure (e.g., identifying clinically relevant biomarkers in a prostate cancer dataset).

The paper concludes that while DIBmix is highly competitive and robust, particularly for genuinely mixed data, it may not be the optimal choice for datasets where one variable type overwhelmingly dominates. The authors acknowledge limitations regarding bandwidth selection in extreme scenarios and the assumption of cluster homogeneity, suggesting future work could explore local bandwidths and robustness to outliers.