Trimmed factorial k-means: a simulation study

• Department of Statistical Sciences, University of Bologna, Bologna, Italy [matteo.farne@unibo.it]

Keywords: Robust clustering – Dimension reduction – Factorial k-means – Trimming

1 Introduction

Clustering multivariate data in high dimensions is a challenging task [Bouveyron and Brunet-Saumard, 2014]. First, agglomerative hierarchical methods like Ward’s method [Ward, 1963] may soon become computationally intractable as the dimension $p$ increases. Second, hierarchical partitioning methods like k-means algorithm [MacQueen, 1967] may be very unstable in high dimensions, due to numerical instability and multicollinearity. Third, dimension reduction is imperative to avoid the curse of dimensionality and to obtain interpretable partitions [Ding, 2009]. Fourth, when the sample size $n$ is also large, robust methods are often needed [García-Escudero et al., 2010], due to the much likely presence of outliers able to distort the obtained partition. For these reasons, the need rises to develop clustering procedures able to combine robustness and dimension reduction.

The very first dimension reduction tool is principal component analysis (PCA) [Hotelling, 1933], which is a geometric procedure to represent a high-dimensional dataset by means of a much lower-dimensional one. At some point, when the data dimension started to grow, it became evident [Hubert and Arabie, 1994] that existing clustering methods could be applied to the first extracted principal components. However, it also became apparent that the directions identified by PCA may not be the optimal ones for clustering purposes, as they neglect the cluster structure present in the sample. This fact was pointed out in [De Soete and Carroll, 1994] as a motivation to propose reduced k-means (RKM), a method to cluster objects in a low-dimensional space. The strong consistency of RKM was proved under independent and identically distributed data in [Terada, 2014].

RKM, in turn, may still mask the most relevant directions for clustering purposes when the directions explaining most of the variance are not close to the directions separating the objects the most. For this reason, [Vichi and Kiers, 2001] proposed factorial k-means (FKM), a method to identify the latent space most able to maximize the distinctiveness of projected objects. The strong consistency of FKM was proved in [Terada, 2015]. Proof is based on the original proof of the strong consistency of k-means clustering in [Pollard, 1981].

Given these premises, in this paper we present a robust version of factorial k-means, where outliers are iteratively removed via a trimming procedure in the low-dimensional space, thus simultaneously identifying radial outliers and designing better shaped clusters. This is obtained by minimising the trimmed least squares criterion in the low-dimensional space. The resulting method is called trimmed factorial k-means (TFKM). TFKM algorithm is reported in [Farnè, 2023]. In this paper, we propose a new simulation study which shows the effectiveness of TFKM against competitors such as the trimmed k-means of [Cuesta-Albertos et al., 1997] (using the R package trimcluster by Christian Hennig), and a robust tandem procedure which first estimates the robust principal components by the R package robpca as proposed in [Hubert et al., 2005], and then applies the trimmed k-means of [Cuesta-Albertos et al., 1997]. Importantly, we also study a new criterion to select the latent rank, the number of clusters and the proportion of outliers, based on a sequence of F-tests based on the deviance within the clusters in the reduced space. We then present an illustrative example involving Internet cookies data.