Extending TCLUST to higher dimensions

Technical Summary: Extending TCLUST to Higher Dimensions via tHDDC

Problem Statement
Outliers significantly distort the results of standard clustering methods, often leading to unreliable partitions where meaningful clusters are merged or spurious clusters are detected. While robust clustering techniques based on trimming, such as TCLUST (Trimmed Clustering), have been developed to mitigate these issues, they face severe limitations in high-dimensional settings. As the dimensionality $p$ increases, TCLUST struggles due to two primary factors: the computational complexity of estimating a large number of parameters associated with full covariance structures, and the difficulty of initializing the algorithm effectively. Conversely, alternative approaches like Robust Linear Grouping (RLG), which assume clusters lie near lower-dimensional subspaces, offer dimensionality reduction but suffer from simplifying assumptions, such as isotropic orthogonal errors and difficulties handling intersecting subspaces.

Methodology: The tHDDC Approach
To address these limitations, the authors propose tHDDC (Trimmed High-Dimensional Data Clustering), a method that unifies the robustness of TCLUST with the subspace modeling of HDDC (High-Dimensional Data Clustering).

• Model Framework: tHDDC assumes that data arise from a mixture of $G$ Gaussian components. Unlike TCLUST, which estimates full covariance matrices, tHDDC adopts a parsimonious structure where each cluster $g$ is concentrated around an affine subspace $B_g$ of intrinsic dimension $q_g$ (where $q_g < p$).
• Covariance Structure: The scatter matrix $\Sigma_g$ for each cluster is decomposed into a specific subspace $B_g$ (spanned by the $q_g$ eigenvectors corresponding to the largest eigenvalues $\lambda_{g1}, \dots, \lambda_{gq_g}$) and an orthogonal complement $B_g^\perp$. In $B_g^\perp$, the variance is modeled by a single common parameter $\lambda_g$. This reduces the number of parameters significantly compared to full covariance estimation.
• Trimming and Constraints: The method incorporates a trimming level $\alpha$ to exclude the most outlying observations. To ensure mathematical well-posedness and prevent degenerate solutions, two eigenvalue-ratio constraints are imposed:
  1. A constraint $c_1$ on the ratio of the largest eigenvalues within the subspaces.
  2. A constraint $c_2$ on the ratio of the smallest eigenvalues (the common noise variance $\lambda_g$) across clusters.
• Algorithm: The authors present a feasible algorithm based on "concentration steps" (C-steps), an adaptation of the EM algorithm. The procedure involves:
  1. Random Initialization: Selecting small subsets of observations to initialize subspace parameters.
  2. C-steps: Iteratively updating membership weights (trimming the lowest likelihood observations), updating cluster means, and updating subspace parameters.
  3. Eigenvalue Truncation: A specific procedure is introduced to enforce the eigenvalue constraints ($c_1, c_2$) after each update, extending the truncation methods used in TCLUST.
  4. Intrinsic Dimension Estimation: A data-driven procedure based on the Cattell criterion is integrated to estimate the intrinsic dimensions $q_g$ automatically, using a complexity penalty to avoid overfitting.

Key Contributions

1. Theoretical Extension: The paper establishes the existence and consistency of the tHDDC estimators under mild conditions, proving that the population maximizer exists even for heavy-tailed distributions provided a strictly positive trimming level is used.
2. Algorithmic Innovation: A new C-step algorithm is developed that handles the specific parsimonious parameterization of HDDC while integrating the robust trimming and eigenvalue constraints of TCLUST. This includes a novel eigenvalue truncation mechanism to satisfy the dual constraints ($c_1, c_2$).
3. Automated Dimension Selection: The authors propose a method to automatically determine the intrinsic dimensions $q_g$ of the subspaces, reducing the need for manual specification and mitigating the risk of overfitting through a complexity-penalized likelihood criterion.
4. Diagnostic Tools: The paper introduces graphical diagnostic tools, including score distances and orthogonal distances, to assess cluster adequacy and detect anomalies, as well as "discriminant factors" to evaluate the reliability of cluster assignments and trimming decisions.

Results

• Simulation Study: Experiments on synthetic data in 200 dimensions ($p=200$) with varying degrees of cluster overlap and subspace orientation show that tHDDC achieves near-perfect classification accuracy across all scenarios. In contrast, TCLUST performs poorly in high dimensions, and RLG fails when subspaces intersect. Furthermore, tHDDC is approximately 2.5 to 3 times faster computationally than TCLUST under comparable conditions.
• Real Data Application: The method was applied to a dataset of handwritten digits (USPS358) contaminated with artificial and real outliers. tHDDC achieved a classification error of roughly 7% (on non-trimmed data), significantly outperforming TCLUST (error > 38%) and the non-robust HDDC (error > 39%). The analysis successfully identified and removed artificial outliers while preserving the structure of the digit clusters.

Significance and Claims
The paper claims that tHDDC provides a robust and computationally efficient solution for clustering in moderately high-dimensional settings where traditional methods like TCLUST fail due to parameter explosion and initialization sensitivity. By combining the subspace assumptions of HDDC with the robust trimming of TCLUST, the method offers a less simplistic alternative to RLG, capable of handling intersecting subspaces and non-isotropic errors. The authors emphasize that the methodology is particularly valuable for datasets with unknown cluster structures and contamination, offering both improved accuracy and reduced computational cost compared to existing robust high-dimensional clustering techniques. Future work is noted to include functional data extensions and cellwise trimming strategies.