MODEL ASSISTED VARIABLE CLUSTERING: MINIMAX-OPTIMAL RECOVERY AND ALGORITHMS

Area of Science:

• Multivariate Statistics
• Machine Learning
• Data Mining

Background:

• Variable clustering aims to group similar components of high-dimensional vectors.
• Existing algorithms often yield data-dependent clusters with limited interpretability.
• Model-based clustering offers statistically interpretable groups by defining population-level clusters.

Purpose of the Study:

• Introduce G-block covariance models for statistically interpretable variable clustering.
• Quantify clustering difficulty using cluster proximity and derive minimax separation thresholds.
• Develop and analyze novel algorithms (COD and PECOK) for G-block covariance models.

Main Methods:

• Definition of G-block covariance models where variable similarity is based on associations with all other variables.
• Derivation of minimax cluster separation thresholds for two distinct cluster proximity metrics.
• Development of COD and PECOK algorithms, including a statistical analysis of PECOK based on a K-means relaxation.

Main Results:

• Minimax cluster separation thresholds differ for the two considered metrics.
• COD and PECOK algorithms are shown to be minimax-optimal with respect to their respective metrics.
• PECOK provides the first statistical analysis for K-means relaxation algorithms in variable clustering.

Conclusions:

• G-block covariance models provide a statistically grounded framework for variable clustering.
• The developed COD and PECOK algorithms effectively identify clusters under these models.
• The approach demonstrates applicability through simulations and data analyses, outperforming spectral clustering in certain scenarios.