Sparse clusterability: testing for cluster structure in high dimensions

Abstract

Background: Cluster analysis is utilized frequently in scientific theory and applications to separate data into groups. A key assumption in many clustering algorithms is that the data was generated from a population consisting of multiple distinct clusters. Clusterability testing allows users to question the inherent assumption of latent cluster structure, a theoretical requirement for meaningful results in cluster analysis.

Results: This paper proposes methods for clusterability testing designed for high-dimensional data by utilizing sparse principal component analysis. Type I error and power of the clusterability tests are evaluated using simulated data with different types of cluster structure in high dimensions. Empirical performance of the new methods is evaluated and compared with prior methods on gene expression, microarray, and shotgun proteomics data. Our methods had reasonably low Type I error and maintained power for many datasets with a variety of structures and dimensions. Cluster structure was not detectable in other datasets with spatially close clusters.

Conclusion: This is the first analysis of clusterability testing on both simulated and real-world high-dimensional data.

Keywords: Big data; Cluster analysis; Cluster tendency; Clustering; Dimension reduction; Distance metrics; Multimodality testing; Principal component analysis; Sparsity.

Fig. 1

Example visualizations based 4 Gaussian clusters with equal variances (Case 2). a–e are example visuals based on $p=500$ dimensions. f shows power estimates in dimensions from $p=2$ to 50,000, using 1000 simulated data sets of $n=200$ observations for each dimension

Fig. 2

Visualizations based on a single cluster (Case 1). a–e are example visuals based on $p=500$ dimensions. f shows Type I error estimates in dimensions from $p=2$ to 50,000, using 1000 simulated data sets for each dimension

Fig. 3

Flowchart for options of data reduction methods and multimodality tests. New methods proposed in this paper are denoted by the yellow bubble for SPCA as a new dimension reduction method, combined with each of two available multimodality tests (dip and Silverman) shown with orange bubbles

Fig. 4

Single cell RNA-seq

Fig. 5

Pan-cancer RNA-seq

Fig. 6

Pan-lung cancer microarray

Fig. 7

Squamous cell lung cancer proteomics

Fig. 8

Glioblastoma RNA-seq

Fig. 9

Visualizations for example Case 3: data set generated with 4 Gaussian clusters where 2 clusters have different variances to the other 2. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50 K via estimation based off 1000 simulated data sets on each dimension

Fig. 10

Visualizations for example Case 4: 4 Gaussian clusters with one cluster pushed to the outside. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50 K via estimation based off 1000 simulated data sets on each dimension

Fig. 11

Visualizations for example Case 5: four clusters with one small cluster. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50 K via estimation based off 1000 simulated data sets on each dimension

Fig. 12

Visualizations for example Case 6: five clusters with one central cluster. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50 K via estimation based off 1000 simulated data sets on each dimension

Fig. 13

Visualizations for example Case 7: five clusters with ten outliers. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50K via estimation based off 1000 simulated data sets on each dimension

Fig. 14

Visualizations for example Case 8: seven clusters with different variances. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50 K via estimation based off 1000 simulated data sets on each dimension

Fig. 15

Visualizations for example Case 9: seven clusters with different push apart degrees. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50 K via estimation based off 1000 simulated data sets on each dimension

Fig. 16

Visualizations for example Case 10: seven clusters with different push apart degrees and variances. All visualizations represent the use of a single example simulation in dimension $p=500$ except for Power which is measured in dimensions from $p=2$ to 50K via estimation based off 1000 simulated data sets on each dimension