Robust K-means Clustering using the Density Power Divergence Measure

Anirban Mondal; Paromita Banerjee; Abhijit Mandal

Source-linked AI summary

Robust K-means Clustering using the Density Power Divergence Measure

Anirban Mondal, Paromita Banerjee, Abhijit Mandal

arXiv:2608.30093v1Aug 30, 2026stat.MEstat.APstat.COstat.ML

TL;DR

The paper addresses outlier sensitivity and missing general convergence guarantees in Mahalanobis distance-based K-means. It introduces DPD-based robust clustering, a density-consistent convergent variant, and robust internal indices; the proposed methods are reported as less sensitive to outliers and adaptable to heterogeneous, non-spherical clusters, with a finite-step convergence guarantee for the variant.

Problem
Mahalanobis distance-based K-means lacks a general convergence guarantee, while clustering and internal evaluation can be distorted by outliers.
Method
MK-means DPD uses DPD-based center and covariance estimation with Mahalanobis distance, while DC-MK-means DPD assigns points using a pointwise DPD loss.
Results
DC-MK-means DPD is proven to converge in a finite number of iterations, while the proposed algorithms are less sensitive to outliers and adaptable to heterogeneous, non-spherical clusters.
Takeaways & Limitations
Robust clustering and robust internal indices provide the paper’s supported framework for evaluating outlier-contaminated data without relying solely on classical procedures.
Takeaways & Limitations
The simulations and real-world applications assume that the number of clusters is known, and the convergence guarantee is to a stationary solution.

Abstract

from arXiv · show

We introduce a robust clustering method, MK-means DPD, that estimates cluster centers and covariance matrices using density power divergence (DPD) measures combined with Mahalanobis distance, making it resistant to outliers and adaptable to heterogeneous, elliptical clusters, unlike the classical K-means algorithm. Since Mahalanobis distance-based K-means lacks a general convergence guarantee, we further introduce a convergent variant, Density-Consistent MK-means DPD (DC-MK-means DPD), which redefines the cluster assignment step in terms of a pointwise DPD loss. We prove a formal theorem establishing that the resulting algorithm converges in a finite number of steps. We also propose two new robust internal evaluation indices, a Median Davies-Bouldin Index and a Trimmed Calinski-Harabasz Index, to ensure that performance comparisons are not themselves distorted by outliers. The efficacy of the proposed methods is demonstrated on simulated data, showing superiority over existing methods, and on two real datasets: Iris data, to identify similar species, and COVID-19 case fatality rate and infection rate data for countries worldwide, examining the resulting clusters' geographic and socio-economic patterns.

1. Introduction

The introduction motivates robust K-means for elliptical, heterogeneous, and outlier-contaminated data. It proposes DPD-based estimation with Mahalanobis distance, a convergent assignment variant, and robust internal evaluation indices.

Motivation: Euclidean distance is inadequate for elliptical clusters or heterogeneous variances, whereas Mahalanobis distance incorporates within-cluster variability.Mahalanobis distance accommodates elliptical shapes and heterogeneity across variables.
Motivation: Outliers distort cluster centers and distance metrics, causing inappropriate allocations in Euclidean and Mahalanobis distance-based K-means.MK-means performs poorly on contaminated datasets because centers and covariance matrices are distorted.
Proposed methods: MK-means DPD estimates cluster centers and covariance matrices with density power divergence while retaining Mahalanobis distance for elliptical, heterogeneous correlated data.Adjusting the DPD tuning parameter to contamination enables robust estimates of centers, covariance matrices, and clusters.
Convergence: DC-MK-means DPD replaces raw Mahalanobis assignment with a pointwise DPD loss to address the absence of a general convergence guarantee.The modification restores a joint objective that is non-increasing at every iteration.
Convergence: DC-MK-means DPD converges in a finite number of steps under the paper’s formal convergence theorem.The guarantee is presented as analogous to classical convergence guarantees for Lloyd’s and MacQueen’s Euclidean K-means algorithms.
Evaluation: The Median Davies-Bouldin Index and Trimmed Calinski-Harabasz Index replace outlier-sensitive classical evaluations in the paper’s performance comparisons.The median-based index uses medians, while the trimmed index preserves the Calinski-Harabasz variance-decomposition identity.

2. K-means using Mahalanobis distance

This section describes K-means with Mahalanobis distance for observations in a p-dimensional space divided into K clusters. The algorithm is formulated through cluster assignments and Mahalanobis-based optimization.

Setup: The method considers n observations x_1, x_2, · · ·, x_n in a p-dimensional space and assumes K clusters.The section introduces the notation used for Mahalanobis distance-based K-means.
Objective: Classical K-means minimizes an objective over cluster partitions, with each cluster represented by its assigned observations and center.The supplied formulation introduces cluster sets C_k and cluster means.
Algorithm: The Mahalanobis distance-based version is called MK-means and is presented as a sequence of algorithmic steps.The section explicitly labels this procedure Algorithm 1.

1. Set initial values of K cluster centers (ˆµ1, · · · , ˆµK)

The algorithm assigns observations using Mahalanobis distance and updates centers and covariance matrices iteratively. Its initialization and estimation are vulnerable to covariance misspecification and outliers, motivating DPD-based estimators.

Assignment: Each observation is assigned to the cluster whose estimated center minimizes its Mahalanobis distance.Assignments are repeated for all observations to form new clusters.
Updating: MK-means updates cluster centers and covariance matrices with maximum likelihood estimators and repeats until tolerance or iteration limits are reached.The stopping rule uses changes between successive estimates or a preset maximum number of iterations.
Distance choice: Mahalanobis distance improves suitability for heterogeneous and elliptical clusters compared with Euclidean K-means.The two algorithms coincide when clusters are homogeneous and spherical according to the supplied passage.
Initialization: Incorrectly specified initial covariances can produce inappropriate clusters, so a concentrated core of neighboring points can initialize covariance estimates.The proposed algorithm adopts a similar core-group initialization approach.
Robust estimation: Outliers affect maximum likelihood estimates of cluster centers and covariance matrices, motivating replacement with density power divergence-based estimators.The paper introduces DPD-based estimation to address sensitivity to extreme observations.

3. Robust K-means algorithm

The paper develops robust Mahalanobis-distance K-means using density power divergence to estimate cluster centers and covariance matrices, then introduces a density-consistent variant with finite-step convergence. The proposed approach targets outlier-contaminated and heterogeneous clustering settings while retaining a stationary-point convergence guarantee.

MK-means DPD: The DPD-based normal model is intended to capture essential within-cluster distributional features and produce accurate, robust clustering results.The multivariate formulation uses the squared Mahalanobis distance for observations with correlated variables.
DPD-based estimation: MDPDE estimates normal-distribution parameters for each cluster by minimizing density power divergence, with α controlling the efficiency–robustness trade-off.Higher α increases robustness but decreases efficiency; α = 0 recovers the classical maximum-likelihood estimate.
MK-means DPD: MK-means DPD combines DPD-based estimation of cluster centers and covariance matrices with Mahalanobis distance for robust clustering.The method is designed to provide reliable estimates when data contain unusual or erroneous values.
Motivation for DC-MK-means DPD: Classical Mahalanobis K-means can target two different objectives, so its distance objective need not decrease monotonically during the algorithm.The mismatch arises because the assignment and update steps are not based on the same objective.
DC-MK-means DPD: DC-MK-means DPD replaces the assignment criterion with a pointwise DPD loss consistent with the update objective, yielding a joint objective that is non-increasing at every iteration.This redesign establishes a Lloyd/MacQueen-style convergence guarantee analogous to Gaussian maximum-likelihood K-means.
Convergence guarantee: DC-MK-means DPD converges in a finite number of steps to a partition and parameter set stable under both algorithmic steps.The partition sequence stabilizes after finitely many iterations, while the objective sequence is non-increasing and bounded below.
Convergence guarantee: The theorem guarantees convergence to a stationary point of the objective, not necessarily its global minimum.For α > 0, the objective is generally non-convex in the mean and covariance parameters.

4. Simulation results and comparison to other clustering algorithms

The simulation compares MK-means DPD and DC-MK-means DPD with established clustering methods using classical and robust internal and external metrics. Both proposed methods perform strongly under outlier contamination, while DC-MK-means DPD preserves performance and converges faster.

Experimental setup: The evaluation compares MK-means DPD and DC-MK-means DPD with K-means, Mahalanobis K-means, DBSCAN, and Gaussian mixture models on simulated data with known memberships and artificial outliers.The study uses internal metrics, external metrics, and robust counterparts to outlier-sensitive internal measures.
Evaluation metrics: Classical internal metrics can be distorted by outliers, motivating robust alternatives for evaluating clustering quality.The paper introduces robust versions because several classical indices rely on averages or squared Euclidean distances and are sensitive to extreme observations.
Robust evaluation metrics: The paper introduces the Median Davies-Bouldin Index and Trimmed Calinski-Harabasz Index as robust counterparts to DBI and CHI.It also uses established robust alternatives, trimmed R2 and PAM (Medoid) Silhouette Index, in performance comparisons.
Performance comparison: DC-MK-means DPD achieves the highest accuracy (0.955), κ (0.932), trimmed R2 (0.908), and CHItrim (3645.1) among the compared methods.MK-means DPD and DBSCAN are close behind on each listed metric.
Computational behavior: DC-MK-means DPD converges in 4 iterations versus 11 for MK-means DPD, while the two methods show very similar overall clustering performance.The faster convergence is consistent with the finite-convergence guarantee established in Theorem 3.2.

5. Real data application

The paper applies its proposed robust clustering methods to Iris data and worldwide COVID-19 indicators. The applications assess clustering performance and interpret country groups using demographic, healthcare, and socio-economic patterns.

Iris data: The Iris analysis uses 150 samples from three known species, with K=3 and α=0.2, enabling external and internal evaluation.The study compares the proposed methods with existing clustering approaches using visual inspection and multiple performance metrics.
Iris data: 0.967 accuracy and 0.950 κ are achieved by MK-means DPD, DC-MK-means DPD, and GMM, the highest values among compared methods.MK-means is close behind with accuracy 0.960 and κ 0.940, whereas K-means records 0.833 accuracy and 0.750 κ.
Iris data: 0.821 trimmed R2 and 318.5 CHItrim are highest for K-means, while DBSCAN has the best PAMSIL (0.624) and DBIM (0.540).These results show that internal and external metrics can favor different methods.
Iris data: The DPD-based methods provide only modest additional benefit on Iris because the dataset contains few genuine outliers or substantially ambiguous points.Their performance is similar to GMM and other classical methods on the reported metrics, unlike the stronger pattern observed in simulations.
COVID-19 data: COVID-19 country clustering combines CFR, infection rate, GDP per capita, hospital beds, infant mortality, life expectancy, and elderly population share.The analysis targets coherent country groupings in a setting where outliers arise naturally; CFR and infection rate contain substantial outliers, partly driven by small densely populated nations.

6. Conclusion

The paper introduces robust DPD-based Mahalanobis K-means methods, including a finite-step convergent variant, and robust internal evaluation indexes. Simulations and real-data applications show benefits that are strongest under outlier contamination.

Proposed methods: MK-means DPD combines DPD-based estimation of cluster centers and covariance matrices with Mahalanobis distance, reducing sensitivity to extreme values while accommodating heterogeneous, non-spherical clusters.The method is designed for data with elliptical structure and differing variances across variables.
Proposed methods: DC-MK-means DPD addresses the lack of a general convergence guarantee in Mahalanobis distance-based K-means by using a pointwise DPD loss for cluster assignment.The paper establishes a theorem guaranteeing convergence in a finite number of iterations.
Simulation evidence: 11 iterations versus 4: MK-means DPD and DC-MK-means DPD required different iteration counts while achieving comparable clustering performance across reported metrics in simulation.The comparison was made between MK-means DPD and its convergent variant.
Evaluation: Two robust internal indexes, the Median Davies-Bouldin Index and Trimmed Calinski-Harabasz Index, reduce the risk that outliers distort performance comparisons.They complement existing robust metrics such as trimmed R2 and PAMSIL.
Applications: The proposed methods were compared with K-means, Mahalanobis K-means, DBSCAN, and Gaussian Mixture Models, then applied to Iris and COVID-19 datasets.The Iris application showed only a modest robustness advantage because genuine outliers were scarce.
Limitations and future work: The simulations and applications assumed a known number of clusters, while selecting the optimal number remains a direction for future work.The initialization scheme may help identify the optimal number of clusters, but this aspect requires further study.
Limitations and future work: DC-MK-means DPD is guaranteed to converge to a stationary point rather than a global optimum, and principled data-driven selection of α remains future work.The paper identifies both theoretical extension and tuning-parameter selection as open directions.
Applications: The COVID-19 clusters formed coherent, interpretable country groupings with a clear geographic pattern despite geography not being used to construct the clusters.Clustering used case fatality rate, infection rate, and demographic and healthcare variables.