Source-linked AI summary
A general trimming approach to robust Cluster Analysis
Luis A. García-Escudero, Alfonso Gordaliza, Carlos Matrán, Agustin Mayo-Iscar
TL;DR
The paper addresses robust clustering when groups have different scatters and weights and contaminating observations are present. It introduces eigenvalue-ratio restrictions controlled by a constant, establishes existence and consistency under stated assumptions, and provides an approximate algorithm. The approach spans clustering problems with different restriction strengths and addresses unequal group sizes.
Problem
Robust clustering must handle contaminating observations, heterogeneous covariance structures, and unequal group sizes while avoiding unbounded objectives and problematic scale effects.
Method
The method trims a proportion α of observations, constrains covariance eigenvalue ratios through a constant c, and incorporates different group weights.
Results
Existence holds for the sample and population problems, and sample maximizers are consistent with population maximizers under mild assumptions.
Takeaways & Limitations
The restrictions support a broad range of clustering approaches, while TCLUST approximately solves the computationally difficult sample problem.
Takeaways & Limitations
The consistency result requires a unique population maximizer, a condition that does not always hold.
Abstract
from arXiv · showhide
We introduce a new method for performing clustering with the aim of fitting clusters with different scatters and weights. It is designed by allowing to handle a proportion $α$ of contaminating data to guarantee the robustness of the method. As a characteristic feature, restrictions on the ratio between the maximum and the minimum eigenvalues of the groups scatter matrices are introduced. This makes the problem to be well defined and guarantees the consistency of the sample solutions to the population ones. The method covers a wide range of clustering approaches depending on the strength of the chosen restrictions. Our proposal includes an algorithm for approximately solving the sample problem.
1. Introduction.
The paper motivates model-based robust clustering because results depend on implicit probabilistic assumptions and outliers complicate group interpretation. It proposes trimming with eigenvalue-ratio restrictions and flexible group weights, supported by existence, consistency, and an approximate algorithm.
- Cluster results depend strongly on the chosen method and its implicitly assumed probabilistic model, contrary to claims of objectivity.
- Model specification is especially important with noisy data because scattered observations may represent either an additional group or background noise.
- Trimming is difficult because outliers lack privileged search directions and bridge observations between groups may also need removal.
- Heterogeneous robust clustering is harder because the objective can become unbounded and differing scales complicate observation ordering through Mahalanobis distances.
- The method constrains covariance eigenvalue ratios, with constant c controlling restriction strength across a wide range of clustering problems.
- It also accommodates different group weights and provides existence, consistency under mild assumptions, and TCLUST for approximately solving the sample problem.
2. Robust clustering and eigenvalues-ratio restrictions.
The paper formulates robust clustering with group-specific covariance matrices, weights, and trimming, while controlling covariance eigenvalue ratios. These restrictions support well-defined optimization and consistency, and TCLUST approximately solves the computationally difficult sample problem.
- Model formulation: The robust model allows different group scatter matrices and weights while trimming a proportion α of observations treated as spurious.The formulation uses assignment functions for regular groups and trimmed observations, with parameters for mixture weights, means, and positive-definite covariance matrices.
- Eigenvalue-ratio restrictions: Eigenvalue-ratio restrictions bound differences among covariance matrices and avoid singularities caused by very different group scatters.The restriction is imposed directly through the parameter space Θc; c = 1 is the strongest restriction, while larger c permits more controlled scatter differences.
- Restriction strength: When c = 1, the method can be viewed as trimmed k-means with weights, whereas the parameter c permits controlled freedom in handling different group scatters.The approach therefore spans clustering variants according to the strength of the covariance restrictions.
- Assignment and trimming: The assignment rule classifies observations using the largest discriminant value and trims them when all discriminant values fall below the α-quantile threshold.This reformulation expresses assignment functions in terms of θ and provides an outlyingness measure through the discriminant functions.
- Theoretical properties: Under condition (PR), the constrained population objective has an attained maximum, and under a strictly positive density plus uniqueness, sample estimators converge almost surely to the population maximizer.The existence result applies over Θc, while consistency requires that θ0 be the unique maximum.
- Approximate computation: Because the empirical problem has very high computational complexity, the paper proposes TCLUST, an EM-principle-based algorithm for approximately solving its sample version.The algorithm combines a classification EM perspective with a concentration step and enforces eigenvalue-ratio restrictions through a restricted least-squares problem.
3. The TCLUST algorithm.
TCLUST iteratively classifies observations while trimming the α hardest-to-classify cases, then updates weights, means, eigenvectors, and restricted eigenvalues. The eigenvalue-ratio constraint is enforced through projection, yielding an approximately solvable algorithm that also supports alternative determinant-ratio restrictions.
- Algorithm: The algorithm initializes cluster centers, covariance matrices, and equal weights, then repeatedly recomputes retained sets, assignments, sample summaries, and parameters.Multiple starts are iterated, and the best solutions are selected using the evaluation function.
- Classification and trimming: TCLUST converts posterior probabilities into discrete assignments and leaves unassigned the proportion α of hardest-to-classify observations.The retained observations are split among clusters using their largest classification distance.
- Parameter updates: With assignments fixed, optimal weights equal nj/[n(1 − α)], means are sample means, and eigenvectors are those of each cluster’s sample covariance matrix.These updates form the first three optimization steps in Proposition 4.
- Eigenvalue restriction: Restricted eigenvalues are obtained by projecting the inverse sample-eigenvalue vector onto the cone C, minimizing its Euclidean distance while satisfying the ratio constraints.Dykstra’s algorithm approximately solves the associated restricted least-squares problem through projections onto closed convex cones.
- Model flexibility: The restriction parameter c controls a broad family of clustering methods, and the algorithm can instead impose restrictions on covariance-determinant ratios.When c = 1 in the determinant-ratio formulation, an analogue of Gallegos’ proposal with group weights is obtained.
4. A simulation study.
The simulation compares TCLUST with three trimming approaches across Gaussian mixtures differing in covariance structure, scale, overlap, dimension, and group weights. TCLUST is reported as the only method coping with very different scales and distinguishing the least and most scattered groups in a difficult overlapping case.
- Design: The study generates samples of size n = 2000 from three multivariate normal clusters with specified centers and varying covariance structures.The simulation varies dimension and uses equal or unequal group proportions.
- Design: The cases range from spherical equal-scatter groups to groups with different covariance matrices, different scales, and severe overlap.M4 has different scales, while M5 combines different scales with severe overlap between two groups.
- Results: TCLUST is the only method reported to cope with mixtures having very different scales and appears less affected when group sizes are unequal.Figure 3 examines the M5 case with p = 2 and unequal weights.
- Results: In the overlapped M5 example, TCLUST is reported as the only procedure distinguishing the least and most scattered groups.The comparison concerns the four procedures applied to the same simulated dataset.
A.1. Existence.
The existence analysis establishes boundedness and convergence properties for the population optimization problem under the eigenvalue-ratio and probabilistic regularity conditions. It shows that positive limiting group weights preserve all k groups and rules out covariance degeneracies that would drive the objective to negative infinity.
- Existence argument: The existence proof starts from a sequence of parameter values and analyzes possible limiting behavior of weights, means, and scatter matrices.Subsequences are extracted using compactness of the weight space and relabeling when needed.
- Scatter behavior: Under the eigenvalue-ratio restriction, divergent scatter behavior would force L(θn,P) → −∞, contradicting the established lower bound.Thus, the problematic covariance-limit alternatives are excluded.
- Boundedness: The objective is bounded below because the trimmed k-means value Vα,k is positive under condition (PR), giving h := (1 − α)Vα,k > 0.The retained assignment set has probability at least 1 − α.
- Group weights: If every limiting group weight satisfies πj > 0, then the number of positive-probability groups is g = k.The proof shows that fewer effective groups would permit a strict decrease in the objective, contradicting optimality.
- Group weights: Zero limiting weights are permitted for surplus groups, whose means and scatter matrices may then be chosen arbitrarily subject to the eigenvalue-ratio restrictions.This is the complementary case in the existence proof.
A.2. Consistency.
The consistency analysis establishes conditions under which sample estimators remain controlled and converge to population solutions. It combines parameter compactness, eigenvalue and center bounds, uniform convergence, and empirical-process arguments.
- The consistency proof combines existence arguments with techniques from the modern theory of empirical processes.
- The proof constructs a compact parameter set containing the sample estimators for all sufficiently large samples with probability 1.
- Under an absolutely continuous distribution, the minimum and maximum eigenvalues of the empirical scatter matrices are controlled through Lemma A.4.
- Empirical cluster centers can be chosen with uniformly bounded norms with probability 1.
- Uniform-convergence lemmas, Glivenko–Cantelli classes, bounded integrands, and an empirical-process theorem complete the proof.