An overview of clustering methods with guidelines for application in mental health research

Psychiatry Research 327 (2023) 115265 Available online 27 May 2023 0165-1781/© 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/bync-nd/4.0/). Review article An overview of clustering methods with guidelines for application in mental health research Caroline X. Gao a , b , c , * , Dominic Dwyer a , b , Ye Zhu d , Catherine L. Smith c , Lan Du e , Kate M. Filia a , b , Johanna Bayer a , b , Jana M. Menssink a , b , Teresa Wang e , Christoph Bergmeir e , f , Stephen Wood a , b , 1 , Sue M. Cotton a , b , 1 a Centre for Youth Mental Health, The University of Melbourne, Parkville, VIC, Australia b Orygen, Parkville, VIC, Australia c Department of Epidemiology and Preventative Medicine, School of Public Health and Preventive Medicine, Monash University, Melbourne, VIC, Australia d School of Information Technology, Deakin University, Geelong, VIC, Australia e Faculty of Information Technology, Monash University, Clayton, VIC, Australia f Department of Computer Science and Artificial Intelligence, University of Granada, Granada, Spain ARTICLE INFO Keywords: Clustering Cluster analysis Machine learning Unsupervised learning Mental health research ABSTRACT Cluster analyzes have been widely used in mental health research to decompose inter-individual heterogeneity by identifying more homogeneous subgroups of individuals. However, despite advances in new algorithms and increasing popularity, there is little guidance on model choice, analytical framework and reporting requirements. In this paper, we aimed to address this gap by introducing the philosophy, design, advantages/disadvantages and implementation of major algorithms that are particularly relevant in mental health research. Extensions of basic models, such as kernel methods, deep learning, semi-supervised clustering, and clustering ensembles are subsequently introduced. How to choose algorithms to address common issues as well as methods for pre-clustering data processing, clustering evaluation and validation are then discussed. Importantly, we also provide general guidance on clustering workflow and reporting requirements. To facilitate the implementation of different algorithms, we provide information on R functions and libraries. 1. Introduction In the presence of the substantial variety of different ways humans can suffer with illnesses (Feczko et al., 2019; Nunes et al., 2020), there have been attempts to group individuals together who demonstrate similar aetiologies, presentations, prognoses, and responses to treatments. As highlighted by Sokal (1974), written history of classification schemes that attempt to categorise the natural world date back to at least the ancient Greeks. Throughout this time, grouping was achieved subjectively by determining similarities between organisms or objects using human sense perception; for example, birds that looked the same were grouped together. Such subjective methods of clustering continued with systematic biological taxonomies (e.g., Linnean typologies) and the emergence of nosologies in psychiatry (e.g., Kraepelinan dementia praecox). With increasing amounts of data, a step-change in biological taxonomy was in the advent of computers that allowed simultaneous consideration of more variables than a human could and objective techniques to assess similarity, e.g., hierarchical agglomerative techniques and the numerical taxonomy approach of Sneath and Sokal (1973); Sokal and Sneath (1963). Computational classification also has a renewed interest in psychiatry due to the growing repositories of big data coupled with widespread recognition of multi-modal heterogeneity of individuals with the same diagnosis. For example, large variations in clinical presentations are well-recognized (Hyman, 2010), comorbidity occurs over the lifetime (Caspi et al., 2020), functional impairment widely varies (Dwyer et al., 2022), illness courses are unpredictable (Carpenter and Kirkpatrick, 1988), and there are multiple biological differences between individuals (Abi-Dargham and Horga, 2016; Insel and Cuthbert, 2015; Kapur et al., 2012) Simultaneously, there is recognition of the wide multi-modal similarity between individuals with different diagnoses in symptoms and biological measures, such as risk * Corresponding author at: Centre for Youth Mental Health, University of Melbourne, Orygen, Locked Bag 10, 35 Poplar Road, Parkville, VIC 3052, Australia. E-mail address: [email protected] (C.X. Gao). 1 Joint senior author Contents lists available at ScienceDirect Psychiatry Research journal homepage: www.elsevier.com/locate/psychres https://doi.org/10.1016/j.psychres.2023.115265 Received 15 December 2022; Received in revised form 20 May 2023; Accepted 21 May 2023 Psychiatry Research 327 (2023) 115265 2 genes (Lam et al., 2019; Schork et al., 2019; Zheutlin et al., 2019), blood proteins (Pinto et al., 2017), brain pathophysiology (Goodkind et al., 2015; Romer et al., 2021; Sha et al., 2019), cognition (Abramovitch et al., 2021), and more recent digital biomarkers (Fraccaro et al., 2019; Low et al., 2020). Such a growing array of differences and similarities has ignited debate within psychiatry that mirrors longstanding questions regarding the degree to which we either ‘lump’ or ‘split’ individuals into groups (McKusick, 1969). On one hand, there are entirely dimensional approaches that seek to identify major axes of illness variance shared by all individuals (Caspi et al., 2014; Caspi and Moffitt, 2018; Insel et al., 2010; Kotov et al., 2016, 2018, 2017, 2013) and on the other, there are approaches that attempt to discover subgroups of individuals who share distinctive attributes that separate them from others (Feczko et al., 2019). In this paper, we focus on the latter ‘clustering’ approach, but also note that the two extremes are not mutually exclusive and can greatly overlap and inform each other (Marquand et al., 2016). Clustering, also referred to as cluster analysis (Feczko and Fair, 2020), is an unsupervised machine (statistical) learning technique that involves grouping data points together based on their similarities (outcomes or data labels are unknown, see Table S1 in Supplementary Material). The term "cluster analysis" was first used by Tryon (1939), and started to be implemented into computer algorithms in the 1960s, e.g., k-means clustering and hierarchical clustering (Forgy, 1965; Ward, 1963). Advances in machine learning in recent years have allowed clustering algorithms to be extended in functionality, scalability and complexity (Jain, 2010) to assist with understanding heterogeneity in mental health, see Fig. 1. A variety of clustering algorithms can now be found in most statistical packages such as R, Python, Matlab, Stata, SAS and IBM SPSS, and new algorithms continue to be developed and distributed rapidly, especially in R and Python. Despite the increasing popularity of using clustering to identify homogeneous subgroups, there is little guidance on model choice, analytical frameworks and reporting requirements that links pioneering work in psychology (e.g.,Clatworthy et al. 2005; Milligan and Cooper 1987) with recent developments in machine learning (Jain, 2010; Russell and Norvig, 2021). Compared with commonly used statistical inference and prediction models, clustering tasks are often more challenging due to their explorative nature (Jain, 2010). Choices of algorithms and input parameters, statistical procedures, as well as randomness in parameter estimations, can all substantially influence the resulting groupings. Consequently, studies using these methods in mental health research often fail to demonstrate consistency (e.g., validation process), robustness (e.g., results not impacted by randomness in estimation) and reproducibility (e.g., details in reporting, open access code and data) (Clatworthy et al., 2005; Green et al., 2020; Ulbricht et al., 2018; Zhou et al., 2018). Therefore, there is a need to provide a comprehensive understanding of common clustering models and to establish frameworks for conducting cluster analysis. There have been many reviews of existing clustering algorithms (Ezugwu et al., 2020; Feczko and Fair, 2020; Gan et al., 2020; Jain, 2010; Jain et al., 1999b; Rui and Wunsch, 2005; Xu and Tian, 2015). However, these reviews generally target statistics, machine learning and computer science audiences. Most of these reviews only provide a general summary of methods without detailed practical guidance for those less familiar with these approaches. Thus, the aim of this paper is to: (i) provide an overview (the philosophy, design and implementation) of major clustering methods that are particularly relevant in mental health research; (ii) introduce the extensions of basic models; (iii) discuss important issues commonly faced in clustering tasks; and (iv) provide general guidance on the clustering workflow. Given the increasing popularity of the statistical computing software R in mental health research, we also provide information on R functions and libraries for implementing different algorithms. The paper is Fig. 1. Heterogeneity in Mental Health. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 3 targeted at readers in mental health research, but the analytical content is applicable to other research fields such as public health and social science. 2. Clustering algorithms Thousands of clustering algorithms have been published with variations in their fundamental design, assumptions, target data structures, parameters of interest, and computational/optimisation processes. The taxonomy of clustering algorithms can be mapped out in different ways (Fig. S1 in Supplementary Material), for example, partitional vs hierarchical, or soft vs hard (Giordani et al., 2020; Han et al., 2011; Reddy and Vinzamuri, 2018). Considering the common problems encountered in mental health research, we broadly summarize the common algorithms into four groups, namely center-based partitioning clustering, hierarchical clustering, density-based clustering, and model-based clustering (Fig. 2). 2.1. Similarity and dissimilarity (distance) measures Most clustering algorithms (except for model-based clustering) require measuring similarity or dissimilarity to group observations into alike subgroups. There are many types of similarity and dissimilarity measures. Distance, sometimes used interchangeably with dissimilarity, is a commonly used sub-type of dissimilarity measures. The most straightforward method for measuring distance for continuous variables is the Euclidean distance. It is simply the length of the path connecting two points in two-dimensional space. Although the Euclidean distance is easy to calculate and interpret, it may not be suitable or optimal for the data given. It cannot be used when the variable is not continuous or when variables have scale differences. It is also sensitive to outliers. A range of different types of measures have been developed to address different data types and issues (Alamuri et al., 2014; Cha, 2007). Detailed descriptions of common distance or dissimilarity measures are listed in Table 1 (continuous variables) and Table 2 (binary, nominal or mixed variables). The appropriate measure should be chosen according to the requirement of the clustering algorithm, the type of data (continuous, ordinal, nominal, binary, count or mixed), and whether the data have outliers (e.g., Manhattan distance is less sensitive to outliers compared with Euclidean distance). In some cases, the scale of the variable may not be associated with underlying differences (e.g., whether a word is presented in a document is more important than the frequency of the word). In these instances, measures such as Cosine distance should be used, which represents distance by the angle between vectors, therefore is scale-invariant (see Table 1). When data are sparse and have a high proportion of common zeros that do not represent similarity (for binary data), distance measures such as Hamming distance (Manhattan distance for binary data) can be problematic. This issue is also known as the “double-zero problem” (Legendre and Legendre, 2012). For example, when many clinical symptoms are measured, an individual presenting with only anxiety symptoms (anxiety=1, other symptoms=0,0,0,0…), should be considered very differently from another person presenting with only psychotic symptoms (psychotic=1, other symptoms=0,0,0, 0…). In this case, normalised measures such as Jaccard distance should be used as common 0 s are not included in the calculation of distance (see Table 2 for details). 2.2. Common clustering algorithms Although most algorithms use distance measures, they were commonly designed with different philosophical rationales. Center-based partitioning clustering (also known as center-based, distance-based or partitioning clustering), refers to a family of models Fig. 2. Simple Illustration of Main Types of Clustering Models. Note: (A) Center-based partitioning clustering aims at establishing the center of each cluster (with the number of clusters pre-specified) and determining group membership using the distance to the individual cluster center. (B) Hierarchical clustering groups data objects into a hierarchy or “tree” of clusters. (C) Density-based clustering groups data according to the density of data distribution, therefore, can identify clusters with arbitrary shapes and sizes. (D) Model-based clustering assumes the distribution of the data is underpinned by latent subgroups. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 4 Table 1 Common Distance or Dissimilarity Measures for Continuous Variables. Distance or dissimilarity Equation (distance between a and bon n dimensions) Graphical representation Description R code Euclidean distance*  ∑n i=1(ai−bi)2 √ Distance between two points in ndimensional space. It is the most commonly used distance measure in clustering; however, it can be sensitive to outliers (Jain et al., 1999a). A few other distance measures were modified based on Euclidean such as weighted Euclidean distance, and average Euclidean distance. stats::dist(x, method = "euclidean") philentropy::distance(x, method ="euclidean") Manhattan distance* ∑ n i=1|ai−bi| Calculated as the sum of the absolute differences in each dimension. It is faster to calculate and slightly more robust to outliers compared with Euclidean distance because there are no squared terms (Rui and Wunsch, 2005). stats::dist(x, method = "manhattan") philentropy::distance(x, method ="manhattan") Chebyshev distance* max i|ai−bi| It measures the maximum distance on all given dimensions. It is very fast to calculate, however, might not be accurate because the information on other dimensions is suppressed. philentropy::distance(x, method ="chebyshev") Mahalanobis distance  (a ⇀−b →)S−1(a ⇀−b →)T √ S is the covariance matrix of all the dimensions in the data Mahalanobis distance takes the data variation and correlation into account. Therefore, data points further away from their expected association were considered more dissimilar. Although this distance measure corrects for the data correlation structure, it is more computationally intensive and can have numerical issues when variables are highly correlated (De Maesschalck et al., 2000). stats::mahalanobis(x, center = FALSE, cov =cov(x)) Cosine distance ^ cos(θ) = ∑n i=1aibi ||a||2||b||2 ||a||2= ∑n i=1a2 i √ Instead of geometrical distance, cosine measures the angle between vectors. It is useful when the actual value of data (such as frequency of words in documents) can be a biased representation of the underlying feature, which is common in text mining (Huang, 2008). lsa::cosine(x) philentropy::distance(x, method ="cosine") Dot product ^ ∑n i=1aibi = ||a||2||b||2cos(θ) The dot product is similar to cosine similarity except that it considers the magnitude of vectors. The dot product can be very helpful when both the angle and the magnitude are important. For example, if we are interested in clustering frequencies developing clinical symptoms, both the frequency and symptom overlaps became important in defining how similar two patients are. corrr::colpair_map(as.data.frame(t (x)), function(x, y) x%*% y,. diagonal=apply(x,1,function(x) x %*% x)) (continued on next page) C.X. Gao et al. Psychiatry Research 327 (2023) 115265 5 including K-means and related algorithms. The core concept of these models is to find mutually exclusive clusters with spherical shapes based on data points’ distance to cluster centers. K-means, discovered independently by different authors in the 1950s and 1960s (Ball and Hall, 1965; MacQueen, 1967), is perhaps the most popular clustering algorithm. As shown in Fig. 3, the algorithm iteratively estimates the centroids of clusters (based on Euclidean distances) until convergence. Although the algorithm has high computational speed and easy interpretation, K-means suffers from a few major limitations, including being sensitive to outliers, unable to identify non-spherical shapes, and only obtaining the local optimum solution (sensitive to the random starting point)(Jain, 2010). A range of algorithms was subsequently developed to address issues of K-means, for example, K-medoids clustering which uses medoids (the data point with the lowest average distance to all other points in the cluster) to reduce the model’s sensitivity to outliers; K-means++ to initialize centroids (Arthur and Vassilvitskii, 2006); fuzzy C-means, which assign probabilistic membership to account for overlapping clusters (Bezdek, 1981); K-modes for categorical input data (Huang, 1997b) and; K-prototypes for mixed numeric and categorical data (Huang, 1997a). Hierarchical clustering takes a different approach to segmenting the data compared with center-based methods. The motivation for hierarchical clustering originated from the need for classification in biological taxonomy in the 1950s and 1960s (Johnson, 1967). It applies a hierarchical approach to establish a tree of clusters (as a dendrogram) either using a bottom-up (agglomerative) or a top-down (divisive, less popular due to high computational cost) based on distances between sub-clusters (Fig. 4). After completion of the algorithm, group membership of any given number of clusters can be determined by slicing the dendrogram. Hierarchical clustering can work with any similarity/dissimilarity matrix and has direct hierarchical interoperation of clusters using a dendrogram. As hierarchical clustering can be used to understand groupings and hierarchical structures of variables (using correlation coefficients as similarity measures), the model can fit well with the framework of accessing the hierarchical taxonomy of disorders and symptoms, for example, the Hierarchical Taxonomy of Psychopathology (HiTOP) (Kotov et al., 2017). However, it has a few drawbacks including being computationally expensive with large datasets, lacking the ability to predict cluster membership with new data, and lower level of stability (sensitive to minor data perturbation) (Milligan, 1980). Density-based clustering is designed from a different school of thought, which aims at finding high-density areas in the feature space (vector space of all variables). The general process is to link (or grow) neighboring dense points to form clusters and leave points that are far away from dense regions as un-clustered. The most well know densitybased model is DBSCAN proposed by Easter et al. (1996a), see illustration in Fig. 5. The benefits of DBSCAN include its robustness to outliers and noise in the data, and the ability to detect clusters with arbitrary shapes and sizes. However, it has two main limitations: it cannot work with clusters that have different densities and it is time-consuming to execute on large and high-dimensional data. These limitations motivated the development of extended models such as HDBSCAN (Campello et al., 2013). Another novel idea is Density Peak Clustering proposed by Rodriguez and Laio (2014), in which a user can decide the number of clusters by exploring locally densest data points as possible cluster centers. A comprehensive survey of density-based clustering algorithms is provided by Bhattacharjee and Mitra (2020). Density-based clustering can have significant benefits when researchers aimed at establishing clear boundaries between subclusters. For example, when aiming to identify subgroups of depression with distinct causal mechanisms, the researchers should avoid separating subgroups representing a continuum (e.g., low, medium, and high severity). In a re-evaluation of clustering for major depressive disorder by Drysdale et al. (2017), Dinga et al. (2019) found that the four cluster solution can also be replicated from data sampled from a single Gaussian distribution suggesting no clear boundaries between sub-biotypes. Another major approach in clustering analysis is model-based clustering, based on probability models. The most popular method in modelbased algorithms is the finite mixture model. The finite mixture model was first applied in parameter estimation by Pearson (1894) and has been widely used in the scientific literature. In the 1960s and 1970s, finite mixture models began to be used for clustering problems (Day, 1969; Edwards and Cavalli-Sforza, 1965). The method has gained increasing popularity following the development of the Table 1 (continued) Distance or dissimilarity Equation (distance between a and bon n dimensions) Graphical representation Description R code Chord distance ^  ∑n i=1(ai ||a||2−bi ||b||2)2 √ Chord distance is the Euclidean distance with raw data normalised between 0 and 1 (relative to all variables collected for the data point, also known as chord transformation). The normalisation removes the impact of the data scale differences, and deal with a numerical problem known as “Double-zero problem” in ecology: when a value of 0 does not represent similarity (e.g., absence of a species), Euclidean distance cannot properly represent similarity (Legendre and Legendre, 2012). stats::dist(vegan::decostand(x, method ="normalize"), method = "euclidean") Canberra distance ∑ n i=1|ai−bi| |ai|+|bi| Manhattan distance is weighted by the inverse of the sum of absolute value, so the data is more sensitive to differences that are closer to 0. philentropy::distance(x, method ="canberra") * Euclidean, Manhattan and Chebyshev distance are special types of Minkowski distance, which has a general expression:[∑n i=1|ai−bi|p]1/p ^ ||a||2, also known as l2-norm, is calculated as the square root of the sum of the squared, which represents the vector length. When using it as a normalising constant, it removes the impact of the vector length, e.g., two 2-dimensional vectors [0,1] and [10,10] became identical after dividing by their l2-norm: ||[0,1]||2 = [0,1/ 02+12 √] = [0,1]and ||[0,10]||2= [0,10 / 02+102 √] = [0,1] C.X. Gao et al. Psychiatry Research 327 (2023) 115265 6 Table 2 Common Distance or Dissimilarity Measures for Binary, Nominal or Mixed Variables. Distance or dissimilarity Equation (distance between aand bon n dimensions) Graphical representation Description R code Jaccard distance 1−a∩b a∪b For binary data: 1−n11 n11 +n01 +n10 Calculated as the proportion of mismatches between two data points (range from 0 to 1), which indicate how diverse the two data points are. It is mostly used for binary data or unstructured normal data (text data). It gives more weight to common ones than common zeroes (Leisch, 2006), e.g., the distance between [1,0] and [1,1] are the same as between [1,0, 0,0,0] and [1,1,0,0,0] as the three common 0 dimensions are not included in the calculation. stats::dist(x, method = "binary") prabclus::jaccard(t(x)) philentropy::distance(x, method ="jaccard") proxy::dist(x, by_rows = TRUE, method ="Jaccard") Dice distance 1− 2*a∩b a+b For binary data: 1−2n11 2n11 +n01 +n10 Modified version of Jaccard with more weights given to cases with agreements (common ones). philentropy::distance(x, method ="dice") Russell/Rao distance 1− a∩b n For binary data: 1−n11 n total dimensions n=n11 + n01 +n10 +n00 The proportion of disagreement between data points. Different from Jaccard and Dice distance, the common zeros are included in the calculation (n 00 is included in the denominator). The inclusion of common zeros can be problematic when the matrix is sparse, the distance will become too large to identify differences with rare cases. Mercator::binaryDistance(t (x), metric="russellRao") Simple matching distance 1−a∩b+¯ a∩¯ b n For binary data: 1−n00 +n11 n Simply calculated as the proportion of mismatched records (both common ones and common zeros) among all records. Similar to the Russell/Rao distance that cannot detect differences in sparse data. nomclust::sm(x) Hamming distance ∑ n i=1ai∕= bi Also known as the Manhattan distance for binary data. It is calculated as the number of values that are different between two data points. It is easy to compute, but it does not consider whether the data consistency is related to common zeros or common ones. Therefore, it has similar issues as the Russell/ Rao distance when dealing with a high dimensional sparse matrix (Norouzi et al., 2012). Hamming distance can also be used for nominal data, which counts for total mismatches regardless of the meaning or prevalence of each choice. Mercator::binaryDistance(t (x), metric="hamming") Gower distance 1− 1 ∑n i=1w(ai,bi)× ∑n i=1 1 w(ai,bi)s(ai,bi) s(ai,bi)is the similarity function and w(ai,bi)is a weight * Measures how different two data points are when mixed data (binary, categorical or continuous data) are presented. It is one of the most widely applied distance measures with mixed types of data. Weight can be applied (e.g., the weight of 0 for double zeros in binary data) to minimize the impact of the high dimensional sparse matrix (Gower, 1971). It can be sensitive to outliers. cluster::daisy(x, metric="gower") StatMath::gower.dist(x, metric="gower") * When i dimension is binary or categorical data when ai=bi s(ai,bi) = 1,otherwise s(ai,bi) = 0. When i dimension is continuous, range normalised rangenormalized Manhattan distance is used, (ai,bi) = 1−|ai−bi| Ri, where Ri is the range of the i dimension. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 7 Expectation-Maximization (EM) algorithm, an efficient algorithm used to find maximum likelihood parameters, first proposed by Dempster et al. (1977). The idea behind the finite mixture model for clustering is that the data originated from a mixture of subpopulations with each having different distributions. The process for finite mixture clustering involves randomly initialising parameters of different subgroups, evaluating how the observed data support the current distributions specified by the given parameter, and updating the parameter iteratively until the model converges (Fig. 6). When the observed variables follow normal distributions, the finite mixture model becomes a Gaussian mixture Fig. 3. Illustration of K-means Clustering. Note: The estimation routine of K-means involves: (i) randomly initialise centroids of a pre-specified number of clusters and partition data points into groups according to their distance to the centroids; (ii) re-estimate the centroids (calculated as the mean of all the data points of the cluster) using points for each cluster; (iii) re-partition data into clusters; and (iv) iteratively repeat (ii) and (iii) until no more changes were observed in the location of centroids (convergence). Fig. 4. Hierarchical Clustering. Note: (A) The agglomerative method is a bottom-up approach, which starts with treating individual data points as separate clusters and then iteratively merges “similar” clusters into larger clusters until all the data are in one cluster. The divisive hierarchical clustering, on the contrary, is a top-down approach, which starts with one cluster and sub-divides the cluster into smaller clusters. (B) Distance between subclusters can be measured using centroid linkage, single linkage, complete linkage, average linkage and Ward’s method (C) Dendrogram generated after clustering allows users to slice the hierarchical structure into any number of clusters. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 8 model, and this type of clustering method is known as the latent profile analysis (LPA). When observed variables are discrete, the finite mixture model clustering is also known as the latent class analysis (LCA, Oberski 2016). In practice, the finite mixture model can also work with variables with mixed distributions (Wallace and Dowe, 2000). Model-based clustering algorithms are popular in mental health research due to their similarity in concept as well as model fitting routine with other latent variable modelling methods (e.g., structure equation modelling and factor analysis). Model-based algorithms can also directly estimate parameters (e.g., item response probabilities for LCA) that can facilitate interoperating models (e.g., how individual variables are associated with latent subgroups). The R implementation methods, advantages and disadvantages for most of these common clustering algorithms are provided in Table 3. 2.3. Extensions of common clustering algorithms Developing new clustering methods has been one of the key machine learning areas with extensive research work in the past decades. A range of advanced models have been developed to address different types of issues, for example, non-linear cluster boundaries, high dimension and sparse data, complex data structure, improvement of stability, special data types, and scalability for big data. Here we briefly introduce some of the state-of-art applications to facilitate better applications of these models. 2.3.1. Kernel method One major limitation of many clustering methods is their difficulty in dealing with non-linear boundaries between clusters. An efficient method to deal with this issue is to use the kernel method first introduced by Aizerman (1964). The fundamental idea of the kernel method Fig. 5. Illustration of DBSCAN Input: dissimilarity matrix D; search radius eps and minimal number of data points to form a cluster minPoints Note: The concept of DBSCAN clustering is similar to disease transmission models, which involves the following steps: (i) randomly identify an initial point; (ii) use a radius (eps, user-defined) to find its neighbours; (iii) if there are enough neighbours (over minPoints, user-defined), the point will be considered as a core point, and its neighbours will be included in the current cluster, if not this point will stop “infecting” other points; (iv) iteratively repeat (ii) and (iii) for the newly classified points to establish the “infection” chain of the current cluster; (v) then select a different point that hasn’t been “infected” as the initial point for a new cluster. The algorithm finishes when all the points have been evaluated. The points that are located in the lower density areas (without enough neighbours to establish a separate cluster) will be left un-clustered. The minPoints is normally selected based on domain knowledge or twice the dimensions of the data (number of variables), and eps can be specified by evaluating distance to the (2 ×data dimensions +1) nearest neighbor (Sander et al., 1998; Schubert et al., 2017). Fig. 6. Illustration of Finite Mixture Model. Note: Finite mixture models require specifications of the type of distribution for each variable and the number of clusters. The programme will: (i) first randomly assign parameters defining each cluster, and (ii) update modelling parameters using the EM algorithm until convergence. In the E-step each observation is assigned a weight for each cluster, and in the M-step the modelling parameters will be updated according to the weights estimated in the E-step. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 9 Table 3 Types of Clustering Algorithms and Implementations in R. Algorithms Notes R functions References Center-based clustering K-means K-means requires an input of the Euclidean distance matrix. However, some studies suggest that other distance measures, such as Manhattan distance works better in a high dimensional space (Aggarwal et al., 2001). Advantages: fast to estimate and easy to interpret Disadvantages: assumes clusters have spherical shapes; sensitive to noise and outliers; global optimum is not ensured therefore sensitive to starting values stats::kmeans Hartigan and Wong (1979), MacQueen (1967), Forgy (1965), Lloyd (1982) cclust::cclust K-means++ An algorithm that optimises the initialisation of k-means Advantages: not sensitive to starting values Disadvantages: same as k-means; requires slightly longer estimation time compared with K-means pracma::kmeanspp Arthur and Vassilvitskii (2006) PAM (Partitioning Around Medoids) A k-medoids algorithm uses a greedy search method, which, although it may not find the optimal solution, is faster compared with using an exhaustive search. Advantages: allows any distance matrix; more robust to outliers compared with K-means Disadvantages: slower to estimate with large dataset; does not work well with non-spherical clusters cluster::pam Kaufman and Rousseeuw (1990) fastkmedoids::fastpam A faster implementation of PAM using C++. Schubert and Rousseeuw (2019) CLARA (Clustering Large Applications) Extension of PAM for larger datasets using a randomly sampled smaller dataset. Advantages: faster than PAM Disadvantages: same as PAM; if the sample is biased, the best medoids cannot be guaranteed cluster::clara Kaufman and Rousseeuw (1990) fastkmedoids::fastclara Schubert and Rousseeuw (2019) CLARANS (Clustering Large Applications based on Randomized Search) Extension for CLARA. CLARANS does not draw a fixed sample of the data set at the beginning of the search, instead, it draws a new sample of neighbours in each step of a search. Advantages: faster than PAM; full data better represented compared with CLARA Disadvantages: same as PAM; sensitive to sequence of input data fastkmedoids:: fastclarans A faster implementation of CLARANS using C++. Ng and Han (2002) K-medians Use Manhattan distance matrix. Advantages: more robust to outliers compared with k-means Disadvantages: can only identify multidimensional spherical clusters; global optimum is not ensured therefore sensitive to starting values Gmedian::KGmedian Cardot et al. (2012) cclust::cclust MacQueen (1967) K-modes K-means style method for categorical variable. The model uses simple matching distance. Advantages: efficient for categorical variable; fast to estimate Disadvantages: cannot work with input data with a mixture of categorical and continuous variables; as the simple matching distance is used, the method does not take into account the “double-zero problem”; global optimum is not ensured therefore sensitive to starting values klaR::kmodes Huang (1997b) . K-prototypes K-prototypes is an integration of K-means and K-modes clustering. It employs different weights for continuous and categorical variables to avoid favouring any. Advantages: similar to K-means and K-modes Disadvantages: similar to K-means and K-modes; results can be sensitive to the weighting parameter clustMixType::kproto Huang (1997a) Fuzzy C-means Soft (fuzzy) extension of k-means clustering. Advantages: can identify overlapping clusters; robust to outliers Disadvantages: assumes clusters have spherical shapes; requires longer estimation time compared with K- means e1071::cmeans Bezdek (1981) Kernel K-means Kernel extension of K-means clustering. Advantages: can identify non-spherical cluster. Disadvantages: need specification of kernel function; slower compared with k-means, particularly with increasing observations and dimensionality; standard kernel K-means has a bias towards small high-density clusters (Marin et al., 2019) klic::kkmeans G¨ onen and Margolin (2014) kernlab: kkmeans weighted kernel K- means Inderjit S Dhillon et al. (2004) Hierarchical clustering Agglomerative Hierarchical Clustering Agglomerative Hierarchical Clustering is a Bottom-up clustering method, which is good at identifying small clusters.Hierarchical clustering using single linkage and complete linkage can cluster nonelliptical clusters, but are very sensitive to outliers and variation in density. Other methods are more robust to outliers, particularly the Ward’s methods (Murtagh & Contreras, 2012), however do not work well with non-spherical clusters. Advantages: can work with any distance matrix cluster; all number of clusters estimated at the same time; dendrogram provides direct interpretation Disadvantages: mistakes made early in tree building stages cannot be fixed further down; slow to estimate with large dataset. stats::hclust Kaufman and Rousseeuw (1990) cluster::agnes Fastcluster:: hclust Note: C++ library for fast implementation of hierarchical agglomerative clustering. Müllner (2013) Divisive hierarchical clustering (DIANA) Top-down clustering, good at identifying large clusters. Advantages: same as agglomerative hierarchical clustering Disadvantages: same as agglomerative hierarchical clustering with only one criterion for dividing clusters (maximum average dissimilarity that is similar to average linkage in agglomerative hierarchical clustering); slower to estimate compared with agglomerative hierarchical clustering cluster::diana Kaufman and Rousseeuw (1990) (continued on next page) C.X. Gao et al. Psychiatry Research 327 (2023) 115265 16 et al., 2021). 3.3. Outliers Outliers are extreme data values that differ significantly from other observations. Outliers are commonly depicted in univariate distributions; however, in clustering algorithms, outliers have to be evaluated on multivariate associations (points in the center of a univariate distribution can still be an outlier). Many commonly used algorithms such as K-means and hierarchical clustering are known to be sensitive to outliers (Zouridakis et al., 1997). Density-based, model-based and fuzzy clustering are more robust to outliers (Zouridakis et al., 1997). Outlier/anomaly detection models, such as LOF (Breunig et al., 2000) and iForest (Bandaragoda et al., 2018; Liu et al., 2008, Liu, 2010), can be used to identify outliers before clustering (Chandola et al., 2009). 3.4. Overlapping boundaries In some cases, there may be overlap or ambiguity in underlying clusters (Chen et al., 2020). In this case, hard clustering methods can be problematic, and soft-clustering models, such as fuzzy clustering and model-based clustering should be used. Joint group membership can also be an independent research interest (Pantelis et al., 2003; Rovetta and Masulli, 2019). However, evaluating model performance and identifying appropriate group membership based on probabilities of group membership can sometimes be difficult for fuzzy clustering (Sato-Ilic and Jain, 2006). 3.5. Arbitrary cluster shapes Most of the traditional partitioning-based and model-based clustering methods assume spherical, elliptical or convex shapes of clusters. Although single linkage hierarchical clustering can identify arbitrarily shaped clusters (Ros and Guillaume, 2019), it often fails to identify clusters in practice due to data noise and overlaps between clusters. More recent models, such as density-based, kernel-based and deep clustering, can work well with arbitrary cluster shapes and should be the models of choice if the boundaries between clusters are hypothesised to be non-convex. 3.6. Rare event Imbalanced data can be challenging to work with for many machine learning algorithms, as they tend to be biased towards majority groups (Krawczyk, 2016). Small clusters can sometimes be very difficult to detect, but can often be important in clinical settings. The power of detecting small clusters mainly depends on how separable they are from main clusters, and the size of the cluster relative to the total sample size. Highly separable smaller clusters (e.g., two clusters with 9:1 ratio) are easy to identify using almost any method, but many existing methods cannot identify less-separable smaller clusters even with a large sample size (Dalmaijer et al., 2022). More advanced methods such as HDBSCAN and density peak clustering may provide better results. In some cases, finding smaller and less-separable clusters may, perhaps, be better considered as an anomaly detection task. 3.7. Mixed and multimodal data In practice, researchers often need to deal with clustering tasks where input data is a mixture of different data types (e.g., continuous, nominal, binary, and ordinal) or from different data sources (e.g., survey, biomarker, and image). There are a few methods available to work with mixed data types. The easiest approach is to use distance measures for mixed data (e.g., Gower distance). However, this method can be sensitive to outliers and ignores important multivariate data features. An alternative approach is to apply a dimensionality reduction technique on mixed data, such as unimodal Variational Autoencoder (Simidjievski et al., 2019), Factor Analysis of Mixed Data (FAMD) (Pag` es, 2014), or PCA for mixed data (PCAmix) (Chavent et al., 2014). An alternative regime is to operate in segmented datasets using methods such as subspace clustering and multi-view clustering. When data were obtained from combinations of psychological measures that can be summarized by underlying latent dimensions (e.g., from a combination of symptom severity measures, self-reported conditions), methods such as FAMD and PCAmix may be more attractive. However, when data were obtained from different sources with high dimensionality, deep learning, subspace clustering and multi-view clustering can be more useful to address the difficulties of linearly summarizing data. 3.8. Missing data When data is Missing Completely at Random (MCAR), all the clustering models will be unbiased. However, MCAR is rarely the case in practice. The most common type of missing data is Missing at Random (MAR: missingness is related to observed data) or Missing Not at Random (MNAR: missingness is related to unobserved data). As most clustering methods cannot directly deal with missing data, multiple imputation (using methods such as multiple imputation using chained Table 4 Challenges in Clustering Tasks and Robustness for Different Models. Center-based clustering Hierarchical clustering Density-based clustering Model-based clustering Extensions High dimensional, noise, and sparse data Problematic Problematic Problematic Problematic Requires variable selection and dimensionality reduction or subspace clustering methods Skewed distribution Problematic Problematic Robust for models allowing density variation Robust when distributions are correctly estimated Data normalization is generally needed. Outliers Problematic Problematic Robust Can be problematic Fuzzy clustering is more robust to outliers. Outlier/anomaly detection models can be used prior to clustering. Overlapping boundaries Problematic Problematic Problematic Robust Fuzzy clustering can be used when there are overlapping cluster boundaries. Arbitrary cluster shapes Problematic Likely to be problematic Robust Problematic There are many extension models available such as kernelbased clustering and non-linear feature extraction models. Rare events Likely to be problematic Likely to be problematic Likely to be problematic Likely to be problematic Consider anomaly detection algorithms when aiming to identify very small clusters. Mixed data Potentially problematic Potentially problematic Potentially problematic Potentially problematic Distance measures for mixed data can be used, however can be sensitive to outliers and not capturing important features. Dimensionality reduction is needed prior to clustering. Missing data Problematic Problematic Problematic Likely to be problematic Multiple imputation models or clustering algorithms that specifically model data missingness are needed for data MAR. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 17 equations [MICE]) is commonly needed (Basaga˜ na et al., 2013). A full information maximum likelihood model can be used for model-based clustering (Enders and Bandalos, 2001); however this model cannot take auxiliary variables (variables related to the missing data but not underlying cluster) into account. Although a few combined imputation and clustering models, such as k-POD (Chi et al., 2016) have been developed, the impact of missing data and imputation methods hasn’t been evaluated extensively compared with inference and prediction models. A sensible and promising domain is to combine multiple imputation with ensemble clustering, i.e., ensemble results from multiple imputed datasets within the cross-validation framework (Chao et al., 2022; Pattanodom et al., 2016; Wan et al., 2020). Future studies are needed to establish the optimal pipelines for addressing missing data under different conditions. 3.9. Statistical power Power estimation cannot be conducted for clustering analysis due to its exploratory nature. Whether clusters can be detected correctly depends on the sample size, number of parameters, how separatable clusters are, level of noise, relative size of clusters, and the method used (Dalmaijer et al., 2022; Dolnicar et al., 2013; Tueller and Lubke, 2010), all of which are largely unknown. Therefore, it is not feasible, or perhaps not appropriate, to determine the statistical power for clustering. Highly separable clusters without noise, though uncommon in practice, can be correctly detected with a small number of observations (Dalmaijer et al., 2022). However, researchers need to ensure that the modelling approach is feasible (e.g., not over parameterized, particularly for LCA), robust (e.g., sampling and CV provide consistent results), and generalizable (unbiased representation of the population of interest). A large number of clusters estimated from a small sample or clusters with very small sizes can be indicators of a lack of robustness and generalizability. 3.10. Multilevel data Data can have a multilevel nature (e.g., students nested in schools, randomized cluster trial). Higher correlations may be observed in naturally formed clusters. In some cases, this multi-level feature is not problematic (e.g., participants recruited in one site may show more severe symptoms but do not differ in the latent heterogeneity of interest such as causal mechanisms of the disorder). However, sometimes it may bias clustering results (e.g., different neuroimaging machines used), or be a separate research interest. In these cases, multilevel mixture models can be used (Asparouhov and Muth´ en, 2008). Alternatively, data fusion models can be applied to obtain reliable and consistent information from raw data and remove the systematic noise (Meng et al., 2020). 3.11. Poor stability All clustering algorithms can be impacted by the random starting point and minor data changes. The most widely known one is the local optima problem for K-means (Steinley, 2003). Essentially, the algorithm tends to obtain a suboptimal result (getting stuck in a local optimal solution, not a global optimal solution) when optimizing the loss criterion. Therefore, the exact shape of the input data, a change of random seeds, and any minor data perturbation, tend to generate different cluster memberships. Other methods largely suffer from the same issue (Goodman, 1974; Monti et al., 2003; van der Kloot et al., 2005). The lack of stability also impacts the choice of optimal modelling parameters such as the number of clusters. Although a few methods were developed to address this issue such as hybrid hierarchical k-means clustering (Milligan, 1980) and K-means++ (Arthur and Vassilvitskii, 2006), recently developed clustering ensemble methods offer a greater level of robustness when combined with resampling and CV. 3.12. Clinically meaningful clusters Although there are many aspects to consider when applying a clustering algorithm in practice, one of the most important issues is to ensure whether the model can detect clinically meaningful clusters. In some cases (e.g., establishing distinct illness subtypes), it is meaningless to dichotomize a continuum (Dinga et al., 2019). In clinical practice, however, it is commonplace to have varying degrees of intervention along such a continuum (e.g., normal variant requiring no further follow-up, watchful waiting, brief treatment, invasive therapy) and separating groups with different severity may become useful (Cotton et al., 2022). What is critical is to have engaged meaningfully with both clinical teams and consumers in question to ensure that the outcome represents a target relevant to both parties. 4. Data pre-processing and testing 4.1. Data pre-processing and dimensionality reduction In practice, data obtained for clustering are often high-dimensional, which introduces difficulties for most of the clustering algorithms. Therefore, an important stage in clustering tasks is data pre-processing, which often involves data normalization, variable selection and dimensionality reduction. To facilitate the estimation of similarity measures or probability distributions, the input data need to be transformed to adjust in range, dispersion and skewness. The commonly used methods include z-score normalization, min-max normalization, quotient normalization and Box-Cox power transformation, see the detailed summary of proposed methods elsewhere (Jajuga and Walesiak, 2000; Milligan and Cooper, 1988). Double standardization (z-score normalization by columns and rows) can be used when only the relative differences between variables are associated with underlying clusters (similar scenarios to when a scale-invariant distance measure is preferred). It is important to note that the type of normalization and transformation needed should be based on the clinical understanding of the data and how the variability, scale and shape of distribution may impact the difference between data points. For example, if the relative differences between individuals across variables are more important, z-score normalization is more suitable. However, when the raw score differences are more important, min-max normalization can be a better method as it preserves variability differences between variables. As the data collected may not necessarily be related to underlying heterogeneity, including a high proportion of “useless” or “low quality” variables can often introduce additional difficulties for clustering algorithms. Therefore, it is important to identify and pre-select variables that have good data quality and are potentially related to heterogeneity or use advanced computational methods to deal with data noise and quality problems (Shen et al., 2014). Another issue, a substantial concern in mental health research rarely mentioned in clustering literature, is the need to avoid over-represented variables measuring the same construct. For example, if the researcher included nine individual items of PHQ-9 and the mean scores of GAD-7 in a K-means clustering, the distance measured between two participants would be highly reflective of their differences in depression but not in anxiety. In practice, researchers are often required to further reduce data dimensions or suppress data non-linearity to ensure the efficiency of clustering algorithms. This process is known as dimensionality reduction which involves projecting the high dimensional space into a low dimensional space via a series of numerical operations based on the input data. The most commonly used dimensionality reduction techniques in psychology are principal component analysis (PCA) and factor analysis, which are both linear dimension reduction methods (Fodor, 2002; Jolliffe, 2022). In modern machine learning, a range of non-linear models such as kernel PCA, Non-negative matrix factorization (NMF), Graph Embedding, and autoencoder (discussed above) are widely used. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 18 These methods can be applied more regularly in mental health research to ensure that nonlinearity and interactions amongst variables are not ignored. Comprehensive reviews of these methods are available (Cunningham and Ghahramani, 2015; Van Der Maaten et al., 2009) to guide applications of these methods. 4.2. Pre-clustering testing A range of methods were proposed to test for the presence of multiple clusters in the data, see details summarized by Adolfsson et al. (2019). The basic design concept of the proposed clustering tests was to evaluate data multimodality (more than one mode indicates heterogeneity) or randomness (similarity with randomly generated data indicates lack of heterogeneity). The most widely used and robust method is the Dip test on pairwise distances (Dip-dist), which calculates and sorts all pairwise distances between any two data points, and evaluates whether there is any “dip” in the continuous distribution of the pairwise distances (Hartigan and Hartigan, 1985). The Silverman test can also be used to test multimodality, which tries to find out how much smoothing (larger bandwidth for the kernel density estimate) is needed for the data distribution to approximate a normal distribution (Silverman, 1981). Both Silverman test and Dip test can be used to test multimodality on the Principal Component and Principal Curve (Adolfsson et al., 2019). To evaluate data randomness, the Hopkins test compares the observed data with randomly generated data under a uniform distribution. If the observed data do not have any clusters, the distances between a sample of data points with their nearest neighbors will be the same as the distances between a sample of simulated data points with their nearest neighbors (Lawson and Jurs, 1990). It should be noted that different tests provide slightly different results depending on factors such as outliers, overlapping clusters, and non-linear boundaries (Adolfsson et al., 2019). Therefore, pre-clustering testing should be used as a guide rather than a hypothesis testing tool. Alternatively, clustering results and evaluation criteria from the data can be compared with synthetic data without subgroups, e.g., permutated or generated from a uniform or unimodal distribution (Gordon, 1996). 5. Cluster evaluation and cross-validation 5.1. Cluster evaluation Due to the unsupervised nature of clustering algorithms, there is no consensus on many modelling choices such as the optimal distance measures, number of clusters, parameters and/or modelling technique. The appropriateness of modelling choices depends on the nature of the data and the underlying heterogeneity. As a result, it is common practice to employ a range of different methods and parameter choices to analyze a dataset and then conduct evaluation and validation. To date, many methods have been developed to validate clustering results (Fig. 13), which can be broadly classified into external criteria (evaluate how well the model describes the truth, i.e., known subgroups), internal criteria (evaluate how well the model describes the data) or relative criteria (evaluate which model or modelling parameter produces best quality clusters) (Gan et al., 2020). A detailed summary of these criteria as well as R implementations are provided in Tables 5 and 6. 5.1.1. External criteria The external criteria compare clustering results with the known underlying cluster structure. They are generally used with a theoretical framework to validate and compare different methods. They can also be used to estimate the stability of cluster assignments over resampled data. When real and predicted clusters are assumed to have a one-to-one mapping, methods such as F-measure can be applied (Amig´ o et al., 2009). Alternatively, the agreement can be measured by counting all pairs of data points and evaluating whether they were grouped into the same or different groups in real and predicted clusters (e.g., Rand statistic, Jaccard coefficient and Fowlkes and Mallows index [FM]). The Fig. 13. Clusters Evaluation Criteria. Notes: (A) External criteria commonly compare clustering results with an external reference (normally the ‘ground truth’ or ‘gold standard’ clustering results). These criteria are commonly used to theoretically compare models using benchmark datasets. (B) Internal criteria utilize information estimated as a part of the clustering process to determine the fit of the model to the data. (C) Relative criteria focus on evaluating how well different models represent the underlying data structure. Sometimes relative criteria are also classified as internal criteria as it does not involve external known information about group membership. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 19 adjusted Rand statistic (also known as the normalised Rand statistic), proposed by Hubert and Arabie (1985), was perhaps one of the most popular indexes used in practice (Rodriguez et al., 2019; Yeung and Ruzzo, 2001). Similar normalization can also be obtained for other measures with counting pairs data points such as FM and Jaccard coefficient, which were found to have very similar validation performances as the adjusted Rand statistic (Aggarwal and Reddy, 2013). Detailed comparisons of different external criteria can be found elsewhere (Amig´ o et al., 2009). 5.1.2. Internal criteria Internal criteria evaluate specifically whether the clustering model describes the underlying data accurately (goodness-of-fit indicators). A commonly used method is the Cophenetic Correlation Coefficient (CPCC) for hierarchical clustering, which measures the correlation between the input distance (dissimilarity measures between points) and output distance on the dendrogram (Sokal and Rohlf, 1962). Although widely used, the CPCC should be interpreted with care as it is not a direct measure of goodness-of-fit and is sensitive to outliers, nonlinear associations and lower levels of separations in clusters (Farris, 1969; Holgersson, 1978; M´ erigot et al., 2010). 5.1.3. Relative criteria Relative criteria have received considerable attention in the literature as key elements in choosing the best number of clusters and validating clustering results. A variety of measures being developed are based on measurements of clustering compactness (homogeneity within the cluster), separation (between cluster distance), representativeness (representative of the underlying data structure), connectedness (clustered similarity with nearest neighbors), stability (consistency in results with subgroups of data) and various combination of these features. The commonly adopted methods were listed in Table 6. Criteria based on compactness, such as root-mean-square standard deviation (RMSSD), works well for spherical and well-separated clusters Table 5 External Validation Indexes and Implementation in R. Indexes Equation k:number of clusters n: number of data points L: real clusters C: predicted clusters Note R-packages Refs. F-measure * 1 k∑k i=1 2Pi×Ri Pi+Ri Pi=TPi TPi+FPi Ri=TPi TPi+FNi Evaluate average combination of precision (Pi) and recall (Ri) for each identified predicted cluster relative to the matching real cluster. FlowSOM:: FMeasure Zaki et al. (2014) BCubed F-score 2P×R P+R P=1 n∑n j=1 No.in same C No.in L R=1 n∑n j=1 No.in same L No.in C Similar with the F-measures except for using the BCubed precision and recall for individual observations. DPBBM:: BCubed_metric Bagga and Baldwin (1998) Rand index ^ TP +TN TP +TN +FP +FN Measuring similarity between clustering results and known clusters via counting pairs of data points. aricode::RI clusteval:: rand_indep Rand (1971) Adjusted Rand index index −E(index) max(index)− E(index) index =∑ i,j(nij 2) E(index) = [∑ i(Ci 2)∑ j(Lj 2)]/(nij 2) max(index) = [∑ i(Ci 2)+∑ j(Lj 2)]/2 The corrected-for-chance version of the Rand index. It establishes the lower bound of 0 when the index is the same as the expected index, E(index),which is the index from two completely random partitions. aricode::ARI Hubert and Arabie (1985) Jaccard coefficient ^ TP TP +FP +FN Measuring similarly by excluding pairs of data points belonging to different groups in both real and predicted clusters (TN). clusteval:: jaccard_indep Halkidi et al. (2001) Fowlkes and Mallows index (FM) ^  P×R √ P=TP TP +FP R=TP TP +FN Measuring similarly of pairs of data points using the product of precision (P) and recall (R). dendextend:: FM_index Fowlkes and Mallows (1983), Halkidi et al. (2001) Normalized mutual information (NMI) § I(L,C)  H(L)H(C) √ H(.): entropy I(L,C):mutual information I(L,C) = H(L)− H(YL|C) Indicate the reduction in the entropy of real clusters if the predicted clusters are known. Higher NMI indicates better clustering results. aricode::NMI Vinh et al. (2009) Adjusted mutual information (AMI) § I(L,C)− E(I(L,C)) max(H(L),H(C))− E(I(L,C)) E(I(L,C)): expected mutual information between two random clusters Similar to NMI and corrects the effect of agreement solely due to chance between clusters. aricode::AMI Vinh et al. (2009, 2010) * TPi (true positive), FPi (false positive), TNi (true negative) and FNi (false negative) are diagnoses of how well the data points in the ith predicted cluster compared with the best matching real cluster. ^ TP (true positive), FP (false positive), TN (true negative) and FN (false negative) refers to diagnoses of pairs of data points that were clustered into the same or different clusters when comparing the real and predicted clusters. § Entropy is calculated as ∑k i=1Pilog2(Pi),Pi is the ratio of points falling in cluster i to points not in cluster i. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 20 Table 6 Relative Validation Indexes and Implementation in R. Indexes Equation k:number of clusters j: a data point n: number of data points Ci cluster i Note R-packages References Root-mean-square standard deviation (RMSSTD) RMSSTD = ∑k i=1SSi ∑k i=1dfi √ SSi=∑n j=1(xj−¯ xi)2 dfi=No.in cluster i−1 Square root of the pooled individual clusters variance (SSi). It measures the within cluster homogeneity. Can be directly calculated (Halkidi et al., 2002) R-squared R2=SSt−SSw SSt SSt=∑n j=1(xj−¯ x)2 SSw=∑k i=1∑ ∈i(xj−¯ xi)2 ¯ xis the mean of all data ¯ xi is the mean of cluster i Measures the ratio of sum of squares between clusters (SSt−SSw)to the total sum of squares (SSt). It measures the degrees of separation between clusters. Can be directly calculated (Halkidi et al., 2002) Normalized Hubert Γ statistic Γ=∑n−1 i∑n j=i+1(Pij − μ P)(Qij − μ Q) M σ P σ Q M=n(n−1) 2 P is the distance matrix of data point, Qis the matrix of cluster distances which individual points belong to. μ P, μ Q, σ Pand σ Qare the respective means and variances of the P and Q matrices. Measures the correlation between data points and their representing clusters. The higher Normalized Hubert Γ indicate the existence of compact clusters. NbClust:: NbClust (Halkidi et al., 2002) Calinski–Harabasz (CH) Index CH =(n−k)B (k−1)W B=∑k i=1nid(Ci,C)2 W=∑k i=1∑ j∈Ci d(j,Ci)2 d(Ci,C)is the distance between cluster Ci to the center of all data, d(j,Ci)is the distance between data point j and its cluster center Ci. Based on the average between- (B) and within-cluster (W) sum of squares. Normally give preferences to convex shape clusters and do not work well with arbitrary shapes. fcp::cluster. stats (Cali´ nski and Harabasz, 1974) Dunn index Dunn = min 1≤i<j≤kd(Ci,Cj) max 1≤g≤kdiam(Cg) d(Ci,Cj)is the dissimilarity function between two clusters Ci and Cj;diam(Cg)is the diameter of the cluster Cg. Both d(Ci,Cj)and diam(Cg)can be measured in a variety of ways. Ratio between the minimal between-cluster distance, d(Ci,Cj),to maximal within-cluster distance diam(Cg). It can be time-consuming to estimate and can be sensitive to noise. fcp::cluster. stats (Dunn, 1974) clValid::dunn Davies–Bouldin (DB) index BD =1 k∑k i=1max i∕=j( σ i+ σ j d(Ci,Cj)) d(Ci,Cj)is the distance between centroids of cluster Ci and Cj. σ i= 1 ni∑ x∈i(x−Ci)2 √ is the standard deviation of the distance of data points in cluster i. Sum ratio of within-cluster scatter to between-cluster separation. A lower DB index relates to a model with better separation between the clusters. Similar to CH index, it does not work well with arbitrary shapes. clusterSim:: index.DB (Davies and Bouldin, 1979) Silhouette index Silhouette =1 k∑k i=1 1 ni∑ x∈Ci b(x)− a(x) max[a(x);b(x)] a(x) = 1 ni−1∑ y∈Ciy∕=x d(x,y)is average distance of data point x with all other data points in same cluster b(x) = min j∕=i[1 nj∑ y∈Cj d(x,y)]is the average distance of x with all data points in the closest cluster. Sum of pairwise difference of between-cluster distances, b(x),and withincluster distances a(x). Higher values indicate better clustering results. It is computationally intensive to estimate. cluster:: silhouette (Rousseeuw, 1987) SD index a SD = α ×Scat(k)+Dis(k) α =Dis(kmax)is a weighting factor. Scat(k) = 1 k∑k i=1‖ σ (vi) ‖ ‖ σ (v) ‖ Linear combination of average scattering of clusters, Scat(k)and total separation between clusters Dis(k).Scat(k)is calculated as the ratio of cluster variance to data set variance. Dis(k)estimates the separation based on the distances between cluster centers. clv::clv.SD (Halkidi et al., 2000) (continued on next page) C.X. Gao et al. Psychiatry Research 327 (2023) 115265 21 Table 6 (continued) Indexes Equation k:number of clusters j: a data point n: number of data points Ci cluster i Note R-packages References σ (vi)is the variance vector for each variable in the cluster i and σ (v)vector of variances in all dataset. Dis(k) = Dmax Dmin ∑k i=1(∑k j=1‖Ci−Cj‖)−1 Dmax and Dmin the maximum and minimum distance between cluster centers SDbw index SDbw =Scat(k)+ Den(k) Scat(k)is defined the same as SD index. Den(k) = 1 k(k−1)∑k i=1∑k j=1,j∕=i den(Ci∪Cj) max(den(Ci),den(Cj)) den(Ci) = ∑ x∈Ci f(x,ui) uiis the center of Ci f(x,ui)= {0if d(x,ui)>stdv 1otherwise stdv is the average standard clusters Introduced the intercluster density measure, Den(k),based on SD index. It evaluates the average density between pairwise clusters, den(Ci∪Cj),in relation to the density within clusters, den(Ci)and den(Cj). clv::clv.SDbw (Halkidi and Vazirgiannis, 2001) Clustering Validation index based on Nearest Neighbours (CVNN) CVNN(C, η ) = Sep(C, η ) maxC∈Γ(sep(C, η ))+com(C) maxC∈Γ(com(C)) sep(C, η ) = max1≤i≤k(1 ni∑ j∈Ci q η (i) η ) com(C)is average of all within-cluster dissimilarities. q η (i)is the number of observations among η nearest neighbours that are in other clusters Γ is all possible clustering results compared. CVNN is based on the intercluster separation, sep(C, η ),and intracluster compactness, Com(C, η ). sep(C, η )measures the level of overlap (with points’ nearest neighbours) in the highest overlapping cluster. The two terms were normalised before adding them up. Smaller values indicate better clustering. fcp::cvnn (Liu et al., 2013) Gap index G(k) = En(log(Wk))− log(Wk) Wk=∑k i=1 1 2niDi Di=∑ j,j′∈Ci dj,j′ Wk measures the expected pooled within-cluster sum of squares around the cluster means. The ideal is to compare Wkobtained from the data with its expectation under a null reference distribution of the data (e.g., uniform distribution). When there are smaller subclusters within large well-separated clusters, it can show non-monotonic behavior, so it is important to evaluate the overall gap curve rather than simply take the optimal value. cluster::clusGap (Tibshirani et al., 2001) a ‖X‖=  XTX √,X is a column vector. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 22 and will give preferences to algorithms that minimize the within-cluster variation (such as K-means). However, they may fail in detecting more complicated data structures such as arbitrarily shaped clusters. Cluster separation measures how distinct or well-separated the clusters are. Pairwise cluster distances, such as centroid linkage shown in Fig. 4 and R-squared can be used in this framework. Hubert Γ statistic as well as modified and normalized Hubert Γ statistic (Halkidi et al., 2002) adopt a similar idea to CPCC. They aim at comparing agreement/disagreement between the clustering results with the underlying data structure. As RMSSD, R-squared and Γ statistic are all evaluating one aspect of the clustering criteria, they will all monotonically increase when the number of clusters increases (Xiong and Li, 2013). A common method is to apply the “elbow” method to identify a drastic changing point in the fitting index. However, the “elbow” method is commonly ambiguous and subjective. As compactness and separation measures both only provide limited information on their own, they are usually combined to form overall indicators of a balanced with-in cluster homogeneity and betweencluster separation. Well known examples are Calinski-Harabasz (CH) index (Cali´ nski and Harabasz, 1974), Dunn index (Dunn, 1974), Davies–Bouldin (DB) index (Davies and Bouldin, 1979) and Silhouette index (Rousseeuw, 1987), see details in Table 6. Most of these indexes give preference to spherical or convex shapes and do not work well with arbitrary shapes. CH Index was also found to be more sensitive to noise in the data (Xiong and Li, 2013). A few recently developed indexes have moved slightly away from evaluating purely compactness and separation. For example, SDbw index proposed by Halkidi and Vazirgiannis (2001) extended the SD index by introducing a density measurement that compares density areas between clusters with density within clusters, considering well-separated clusters should have considerable density decay in the area separating them. Another index that was found to be able to work properly in arbitrarily shaped clusters is the Clustering Validation index based on Nearest Neighbors (CVNN). CVNN evaluates whether data points were grouped into the same clusters as their nearest neighbors, which facilitates the rationale of density-based clustering algorithms. For model-based clustering, goodness-of-fit indexes, such as Bayesian information criterion (BIC), are commonly used as relative criteria to compare between models (Fraley and Raftery, 1998). Hypothesis testing can also be employed to select the best numbers of clusters, e.g., Vuong-Lo-Mendell-Rubin adjusted likelihood ratio test (Vuong, 1989) and bootstrapped likelihood ratio test (McLachlan, 1987). These criteria measure different types of clustering quality and should be chosen according to the clustering method(s) used and the features of the data. In practice, users should aim to report results from multiple criteria to obtain a more comprehensive view of clustering performance. 5.2. Resampling and cross-validation An important validation process (e.g., choosing the best number of clusters) to include for all clustering tasks is resampling and Cross- Validation (CV). This is because many methods are sensitive to small variations in data and random seed and the risk for overfitting is high. Many types of resampling and validation methods have been developed (Fig. 14). All these methods involve creating subsamples of the data to establish models jointly to improve the stability and generalizability of the model as well as to avoid over-fitting the data. The common CV regime involves using both training dataset(s) (e.g., identifying best hyperparameters) and testing dataset(s) (e.g., prediction accuracy). As it is not possible to evaluate prediction accuracy in clustering (unknown cluster membership), CV is commonly used to in hyperparameter selection (e.g., number of clusters) using training datasets. However, testing data can be used to evaluate the generalizability of the established model (e.g., whether the clusters identified in the testing data under the same modelling parameters were consistent with training data). K-fold CV, Monte Carlo CV and Bootstrap are commonly used for selecting the best modelling parameters (Sylvain and Alain, 2010). Fig. 14. Common Methods for Resampling and Cross Validation (CV). Note: (A) The total sample can be randomly split into half with one being the “training data” and one being the “testing data”. The optimal model can be obtained in the training data, and then evaluated in the testing data. (B) In k-fold CV, the total dataset is randomly split into k-fold with equal size. Then the data can be organised into k pairs of training (k-1 folds) and testing datasets (1-fold). The commonly used method is the 10-fold CV. When k is the same as the sample size, the method became leave-one-out CV. (C) Monte Carlo CV, repetitively randomly samples a proportion of data into the training data and leaves the remaining data for testing. When the population is large, a much smaller number of training and testing samples can be selected. (D) Bootstrap creates random samples using sampling with replacement. Therefore, one observation can be sampled into a resampled dataset multiple times. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 23 These methods have different assumptions, advantages, and disadvantages; however, they can yield comparable results when properly specified (Molinaro et al., 2005). Bootstrap can retain the same sample size, establish confidence limits for hard clustering methods (Suzuki and Shimodaira, 2006) and apply in hypothesis testing (McLachlan, 1987). However, bootstrap samples cannot be used to evaluate agreements between sampled datasets (no one-to-one matching due to sampling with replacement) and can introduce high bias and unstable results (Efron and Tibshirani, 1997; Kohavi, 1995). K-fold CV is perhaps theoretically more attractive as it explores all possible combinations of small groups of data. As the parameter k is commonly recommended to be between 10 and 20 (Kohavi, 1995), the method is also practically more desirable due to the lower computational cost (Molinaro et al., 2005). However, due to its restricted number of resampling datasets, it may not be a preferred method for clustering ensemble. There is no optimal CV method for all different practical problems and the performance of CV depends on whether sampled data represent the underlying distribution. The choice of CV model can be based on features of the dataset as well as the overall clustering framework (e.g., whether clustering ensemble is used), and evaluation pipelines can be established to ensure CV leads to stable and generalizable results (e.g., testing with more than one CV methods). 6. Workflow and reporting Different clustering methods and different procedures employed may result in different partitioning of a data set. The optimal solution is largely dependant on the type of data used and how well the heterogenous groups were reflected by the data. Although there are no goldstandard procedures, here we provide a general guide for the clustering workflow, which could assist with improving the quality, efficiency, and transparency of clustering tasks. The recommended workflow consists of six steps (Fig. 15). It is important to apply the data pre-processing procedures, pretesting, clustering model optimization and visual evaluation within the CV loop (e.g., dimensionality reduction in each resampled dataset) to avoid overfitting and reduce bias. After the clusters were identified, there is a need to further validate their meaningfulness (e.g., evaluate how clustering results correlate with external variables) and external validity (e.g., evaluate whether the identified clusters are generalizable in external data). To achieve greater research transparency, the analysis plan should be pre-registered and results should be reported with sufficient details, including nature of data, theory supporting possible subgroups, detailed analysis procedures, implementation methods (e.g., software packages, code), validity and generalizability of findings. Although Aldenderfer and Blashfield (1984) established the original framework for reporting clustering results, their recommendations were outdated to meet the Table 7 Check-list for pre-registration and reporting clustering analysis. Preregistration Final publication Nature of the data and variables Context Context & results Rationale/theory supporting clustering analysis (e.g., theory supporting possible subgroups which can be identified using selected variables) Context Context & discussion Data pre-processing procedures Methods Methods & results Similarity/distance measure(s) and justification Methods if used Methods if used Pre-clustering testing Methods Methods & results Clustering method(s) and justification Methods Methods & results Selecting modelling parameters Methods Methods & results Missing data and methods to deal with missingness Methods Methods & missingness Resampling, CV, and/or external validation Methods Methods & results Visual representation of clustering results Methods Methods & results Evaluation of cluster meaningfulness Methods Methods & results Computer program(s), package(s), function(s) and associated version Not necessary All details Sensitivity analysis Methods Methods & results Deviation from analysis plan – Methods & results Research data (or synthetically generated data) and analysis code for replication – Supplementary files or citable resources Fig. 15. Clustering Workflow. Note: PCA: Principal Component Analysis; UMAP: Uniform Manifold Approximation; t-SNE: T-distributed Stochastic neighbor Embedding. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 24 needs of increasing complexity in analysis procedures. Therefore, we proposed an additional checklist for both pre-registration and final publication (Table 7). 7. Summary Clustering analysis is a longstanding but rapidly evolving machine learning area. Clustering methods are often difficult to choose, justify, robustly conduct, evaluate and validate. There have been many innovative clustering methods developed and/or applied in mental health research, such as FRF (Feczko et al., 2018) and HYDRA (Varol et al., 2017) as mentioned above. Tokuda et al. (2018) developed a multi-view clustering based on a non-parametric Bayesian mixture model for depression subtyping. Chen et al. (2020) applied fuzzy C-means and GMM jointly to identify ambiguous data points which may not belong to any schizophrenia subtypes. Dwyer et al. (2020) used a consensus clustering based on nonnegative matrix factorization to evaluate psychosis subgroups. To deal with the high dimensionality issue in neural imagining data, Chang and colleagues combined deep autoencoder with clustering ensembles (Chang et al., 2021). Most of these advanced modelling approaches have been applied in neuroscience. The current standard practice of using clustering models in mental health research remains relatively simple and lacks a robust framework. Across fields, research is also largely limited to describing empirical findings. We hope our overview and recommendations can assist mental health researchers to use these methods efficiently, transparently and robustly to produce results that lead towards clinical use and theoretical understanding of principles underlying illness. CRediT authorship contribution statement Caroline X. Gao: Conceptualization, Methodology, Visualization, Writing – original draft, Writing – review & editing. Dominic Dwyer: Conceptualization, Methodology, Writing – review & editing. Ye Zhu: Conceptualization, Methodology, Writing – review & editing. Catherine L. Smith: Methodology, Writing – review & editing. Lan Du: Methodology, Writing – review & editing. Kate M. Filia: Methodology, Writing – review & editing. Johanna Bayer: Methodology, Writing – review & editing. Jana M. Menssink: Methodology, Writing – review & editing. Teresa Wang: Methodology, Writing – review & editing. Christoph Bergmeir: Methodology, Writing – review & editing. Stephen Wood: Conceptualization, Methodology, Writing – review & editing. Sue M. Cotton: Conceptualization, Methodology, Writing – review & editing. Declaration of Competing Interest This study was not funded. The author(s) declare that there were no conflicts of interest with respect to the authorship or the publication of this article. Acknowledgments The designs of some of the graphical illustrations were inspired by online posts and blogs from the generous machine learning community. A/Prof. Lianne Schmaal, Dr James Kean, Dr Sarah Herniman and other researchers from the Orygen Clinical Neuroscience Group and Monash Biostatistics Unit have all provided valuable feedback on the contents. Supplementary materials Supplementary material associated with this article can be found, in the online version, at doi:10.1016/j.psychres.2023.115265. References Abi-Dargham, A., Horga, G., 2016. The search for imaging biomarkers in psychiatric disorders. Nat. Med. 22 (11), 1248–1255. https://doi.org/10.1038/nm.4190. Abramovitch, A., Short, T., Schweiger, A., 2021. The C Factor: cognitive dysfunction as a transdiagnostic dimension in psychopathology. Clin. Psychol. Rev. 86, 102007 https://doi.org/10.1016/j.cpr.2021.102007. Adolfsson, A., Ackerman, M., Brownstein, N.C., 2019. To cluster, or not to cluster: an analysis of clusterability methods. Pattern Recognit. 88, 13–26. https://doi.org/ 10.1016/j.patcog.2018.10.026. Aggarwal, C.C., Hinneburg, A., Keim, D.A., 2001. On the Surprising Behavior of Distance Metrics in High Dimensional Space. In: Van den Bussche, J., Vianu, V. (Eds.), Database Theory ICDT 2001. ICDT 2001. Lecture Notes in Computer Science, vol 1973. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44503-X_27. Aggarwal, C.C., Reddy, C.K., 2013. Data Clustering: Algorithms and Applications. CRC Press LLC. http://ebookcentral.proquest.com/lib/monash/detail.action?do cID=1355921. Aghabozorgi, S., Seyed Shirkhorshidi, A., Ying Wah, T., 2015. Time-series clustering – a decade review. Inf. Syst. 53, 16–38. https://doi.org/10.1016/j.is.2015.04.007. Agrawal, R., Gehrke, J., Gunopulos, D., Raghavan, P., 1998. Automatic subspace clustering of high dimensional data for data mining applications. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle, Washington, USA. https://doi.org/10.1145/276304.276314. Aizerman, M.A., 1964. Theoretical foundations of the potential function method in pattern recognition learning. Autom. Remote Control 25, 821–837. Alamuri, M., Surampudi, B.R., Negi, A., 2014. A survey of distance/similarity measures for categorical data. In: Proceedings of the International Joint Conference on Neural Networks (IJCNN), pp. 1907–1914. https://doi.org/10.1109/IJCNN.2014.6889941. Aldenderfer, M.S., Blashfield, R.K., 1984. Cluster Analysis. Sage Publications, CA. Amig´ o, E., Gonzalo, J., Artiles, J., Verdejo, M., 2009. A comparison of extrinsic clustering evaluation metrics based on formal constraints. Inform Retriev 12:461-486 Inf. Retr. Boston 12, 461–486. https://doi.org/10.1007/s10791-008-9066-8. Ankerst, M., Breunig, M.M., Kriegel, H.P., Sander, J., 1999. OPTICS: ordering points to identify the clustering structure. ACM Sigmod. Record. 28 (2), 49–60. Arthur, D., & Vassilvitskii, S. (2006). k-means++: The Advantages of Careful Seeding. http://ilpubs.stanford.edu:8090/778/. Asparouhov, T., & Muth´ en, B. (2008). Multilevel mixture models. Advances in Latent Variable Mixture Models, 27–51. Bagga, A., Baldwin, B., 1998. Entity-based cross-document coreferencing using the vector space model. In: Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics - Volume 1. Montreal, Quebec, Canada. https://doi.org/10.3115/ 980845.980859. Bair, E., 2013. Semi-supervised clustering methods. Wiley Interdiscip. Rev. Comput. Stat. 5 (5), 349–361. https://doi.org/10.1002/wics.1270. Bair, E., Tibshirani, R., 2004. Semi-supervised methods to predict patient survival from gene expression data. PLoS Biol. 2 (4), E108. https://doi.org/10.1371/journal. pbio.0020108. Ball, G.H., .& Hall, D.J. (.1965). ISODATA, a Novel Method of Data Analysis and Pattern Classification. Bandaragoda, T.R., Ting, K.M., Albrecht, D., Liu, F.T., Zhu, Y., Wells, J.R., 2018. Isolation-based anomaly detection using nearest-neighbor ensembles. Comput. Intell. 34 (4), 968–998. https://doi.org/10.1111/coin.12156. Bandeen-Roche, K., Miglioretti, D.L., Zeger, S.L., Rathouz, P.J., 1997. Latent variable regression for multiple discrete outcomes. J. Am. Stat. Assoc. 92 (440), 1375–1386. https://doi.org/10.1080/01621459.1997.10473658. Basaga˜ na, X., Barrera-G´ omez, J., Benet, M., Ant´ o, J.M., Garcia-Aymerich, J., 2013. A framework for multiple imputation in cluster analysis. Am. J. Epidemiol. 177 (7), 718–725. https://doi.org/10.1093/aje/kws289. Benaglia, T., Chauveau, D., Hunter, D.R., Young, D.S., 2009. mixtools: an R package for analyzing mixture models. J. Stat. Softw. 32 (6), 1–29. https://doi.org/10.18637/jss. v032.i06. Berndt, D.J., Clifford, J., 1994. Using dynamic time warping to find patterns in time series. In: Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. https://doi.org/10.5555/3001460.3001507. Bezdek, J.C., 1981. Pattern Recognition with Fuzzy Objective Function Algorithms. Springer. Bhattacharjee, P., Mitra, P., 2020. A survey of density based clustering algorithms. Front. Comput. Sci. 15 (1), 151308 https://doi.org/10.1007/s11704-019-9059-3. Booij, M.M., van Noorden, M.S., van Vliet, I.M., Ottenheim, N.R., van der Wee, N.J.A., Van Hemert, A.M., Giltay, E.J., 2021. Dynamic time warp analysis of individual symptom trajectories in depressed patients treated with electroconvulsive therapy. J. Affect Disord. 293, 435–443. https://doi.org/10.1016/j.jad.2021.06.068. Boongoen, T., Iam-On, N., 2018. Cluster ensembles: a survey of approaches with recent extensions and applications. Comput. Sci. Rev. 28, 1–25. https://doi.org/10.1016/j. cosrev.2018.01.003. Breunig, M.M., Kriegel, H.P., Ng, R.T., Sander, J., 2000. LOF: identifying density-based local outliers. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. Dallas, Texas, USA. https://doi.org/10.1145/342009.335388. Brusco, M., Steinley, D., Watts, A.L., 2022. A comparison of spectral clustering and the walktrap algorithm for community detection in network psychometrics. Psychol. Methods. https://doi.org/10.1037/met0000509. No Pagination Specified-No Pagination Specified. Cali´ nski, T., Harabasz, J., 1974. A dendrite method for cluster analysis. Commun. Stat. 3 (1), 1–27. https://doi.org/10.1080/03610927408827101. C.X. Gao et al. Psychiatry Research 327 (2023) 115265 25 Campello, R.J., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierarchical density estimates. Advances in Knowledge Discovery and Data Mining, Berlin, Heidelberg. 10.1007/978-3-642-37456-2_14. Cardot, H., C´ enac, P., Monnez, J.M., 2012. A fast and recursive algorithm for clustering large datasets with k-medians. Comput. Stat. Data Anal. 56 (6), 1434–1449. https:// doi.org/10.1016/j.csda.2011.11.019. Carpenter, W.T., Kirkpatrick, B, 1988. The heterogeneity of the long-term course of schizophrenia. Schizophr. Bull. 14 (4), 645–652. http://www.ncbi.nlm.nih. gov/pubmed/3064288. Caspi, A., Houts, R.M., Ambler, A., Danese, A., Elliott, M.L., Hariri, A., Harrington, H., Hogan, S., Poulton, R., Ramrakha, S., Rasmussen, L.J.H., Reuben, A., Richmond- Rakerd, L., Sugden, K., Wertz, J., Williams, B.S., Moffitt, T.E., 2020. Longitudinal assessment of mental health disorders and comorbidities across 4 decades among participants in the Dunedin birth cohort study. JAMA Netw. Open 3 (4), e203221. https://doi.org/10.1001/jamanetworkopen.2020.3221. Caspi, A., Houts, R.M., Belsky, D.W., Goldman-Mellor, S.J., Harrington, H., Israel, S., Meier, M.H., Ramrakha, S., Shalev, I., Poulton, R., Moffitt, T.E., 2014. The p factor: one general psychopathology factor in the structure of psychiatric disorders? Clin. Psychol. Sci. 2 (2), 119–137. https://doi.org/10.1177/2167702613497473. Caspi, A., Moffitt, T.E., 2018. All for one and one for all: mental disorders in one dimension. Am. J. Psychiatry 175 (9), 831–844. https://doi.org/10.1176/appi. ajp.2018.17121383. Cha, S.H., 2007. Comprehensive survey on distance/similarity measures between probability density functions. Int. J. Math. Models Methods Appl. Sci. 1 (2), 1. http ://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.154.8446&rep=rep1&type =pdf. Chand, G.B., Dwyer, D.B., Erus, G., Sotiras, A., Varol, E., Srinivasan, D., Doshi, J., Pomponio, R., Pigoni, A., Dazzan, P., Kahn, R.S., Schnack, H.G., Zanetti, M.V., Meisenzahl, E., Busatto, G.F., Crespo-Facorro, B., Pantelis, C., Wood, S.J., Zhuo, C., Davatzikos, C., 2020. Two distinct neuroanatomical subtypes of schizophrenia revealed using machine learning. Brain 143 (3), 1027–1038. https://doi.org/ 10.1093/brain/awaa025. Chandola, V., Banerjee, A., Kumar, V., 2009. Anomaly detection: a survey. ACM Comput. Surv. 41 (3), 15. https://doi.org/10.1145/1541880.1541882. Article. Chang, M., Womer, F.Y., Gong, X., Chen, X., Tang, L., Feng, R., Dong, S., Duan, J., Chen, Y., Zhang, R., Wang, Y., Ren, S., Wang, Y., Kang, J., Yin, Z., Wei, Y., Wei, S., Jiang, X., Xu, K., Wang, F., 2021. Identifying and validating subtypes within major psychiatric disorders based on frontal–posterior functional imbalance via deep learning. Mol. Psychiatry 26 (7), 2991–3002. https://doi.org/10.1038/s41380-020- 00892-3. Chao, G., Sun, S., Bi, J., 2021. A survey on multiview clustering. IEEE Trans. Artif. Intell. 2 (2), 146–168. https://doi.org/10.1109/TAI.2021.3065894. Chao, G., Wang, S., Yang, S., Li, C., Chu, D., 2022. Incomplete multi-view clustering with multiple imputation and ensemble clustering. Appl. Intell. 52 (13), 14811–14821. https://doi.org/10.1007/s10489-021-02978-z. Chavent, M., Kuentz-Simonet, V., Labenne, A., & Saracco, J. (2014). Multivariate analysis of mixed data: the R Package PCAmixdata. arXiv. 10.48550/ arXiv.1411.4911. Chen, J., Patil, K.R., Weis, S., Sim, K., Nickl-Jockschat, T., Zhou, J., Aleman, A., Sommer, I.E., Liemburg, E.J., Hoffstaedter, F., Habel, U., Derntl, B., Liu, X., Fischer, J.M., Kogler, L., Regenbogen, C., Diwadkar, V.A., Stanley, J.A., Riedl, V., Outcome Survey, I., 2020. Neurobiological divergence of the positive and negative schizophrenia subtypes identified on a new factor structure of psychopathology using non-negative factorization: an international machine learning study. Biol. Psychiatry 87 (3), 282–293. https://doi.org/10.1016/j.biopsych.2019.08.031. Chi, J.T., Chi, E.C., Baraniuk, R.G., 2016. k-POD: a method for k-means clustering of missing data. Am. Stat. 70 (1), 91–99. https://doi.org/10.1080/ 00031305.2015.1086685. Chiu, D.S., Talhouk, A., 2018. diceR: an R package for class discovery using an ensemble driven approach. BMC Bioinform. 19 (1), 11. https://doi.org/10.1186/s12859-017- 1996-y. Clatworthy, J., Buick, D., Hankins, M., Weinman, J., Horne, R., 2005. The use and reporting of cluster analysis in health psychology: a review. Br. J. Health Psychol. 10 (3), 329–358. https://doi.org/10.1348/135910705X25697. Cole, V.T., Apud, J.A., Weinberger, D.R., Dickinson, D., 2012. Using latent class growth analysis to form trajectories of premorbid adjustment in schizophrenia. J. Abnorm. Psychol. 121 (2), 388–395. https://doi.org/10.1037/a0026922. Collins, L.M., Lanza, S.T., 2009. Latent Class and Latent Transition Analysis: With applications in the Social, Behavioral, and Health Sciences, 718. John Wiley & Sons. Cotton, S.M., Hamilton, M.P., Filia, K., Menssink, J.M., Engel, L., Mihalopoulos, C., Rickwood, D., Hetrick, S.E., Parker, A.G., Herrman, H., Telford, N., Hickie, I., McGorry, P.D., Gao, C.X., 2022. Heterogeneity of quality of life in young people attending primary mental health services. Epidemiol. Psychiatr. Sci. 31, e55. https:// doi.org/10.1017/S2045796022000427. Croon, M., 1990. Latent class analysis with ordered latent classe. Br. J. Math Stat. Psychol. 43 (2), 171–192. https://doi.org/10.1111/j.2044-8317.1990.tb00934.x. Cunningham, J.P., Ghahramani, Z., 2015. Linear dimensionality reduction: survey, insights, and generalizations. J. Mach. Learn. Res. 16 (1), 2859–2900. Dalmaijer, E.S., Nord, C.L., Astle, D.E., 2022. Statistical power for cluster analysis. BMC Bioinform. 23 (1), 205. https://doi.org/10.1186/s12859-022-04675-1. Dara, S., Tumma, P., 2018. Feature extraction by using deep learning: a survey. In: Proceedings of the International Conference on Electronics, Communication and Aerospace Technology (ICECA). https://doi.org/10.1109/ICECA.2018.8474912. Davies, D.L., Bouldin, D.W., 1979. A cluster separation measure. IEEE Trans. Pattern Anal. Mach. Intell. (2), 224–227. Day, N.E., 1969. Estimating the components of a mixture of normal distributions. Biometrika 56 (3), 463–474. De Maesschalck, R., Jouan-Rimbaud, D., Massart, D.L., 2000. The Mahalanobis distance. Chemom. Intell. Lab. Syst. 50 (1), 1–18. https://doi.org/10.1016/S0169-7439(99) 00047-7. Dempster, A.P., Laird, N.M., Rubin, D.B., 1977. Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. Ser. B 39 (1), 1–22 (Methodological). Dhillon, I.S., Guan, Y., Kulis, B., 2004a. Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle, WA, USA. https://doi.org/ 10.1145/1014052.1014118. Dhillon, I.S., Guan, Y., Kulis, B., 2004b. A Unified View of Kernel K-Means, Spectral Clustering and Graph Cuts. Citeseer. Dinga, R., Schmaal, L., Penninx, B.W.J.H., van Tol, M.J., Veltman, D.J., van Velzen, L., Mennes, M., van der Wee, N.J.A., Marquand, A.F., 2019. Evaluating the evidence for biotypes of depression: methodological replication and extension of Drysdale et al. (2017). NeuroImage Clin. 22, 101796 https://doi.org/10.1016/j.nicl.2019.101796. Dolnicar, S., Grün, B., Leisch, F., Schmidt, K., 2013. Required sample sizes for datadriven market segmentation analyses in tourism. J. Travel Res. 53 (3), 296–306. https://doi.org/10.1177/0047287513496475. Drysdale, A.T., Grosenick, L., Downar, J., Dunlop, K., Mansouri, F., Meng, Y., Fetcho, R. N., Zebley, B., Oathes, D.J., Etkin, A., Schatzberg, A.F., Sudheimer, K., Keller, J., Mayberg, H.S., Gunning, F.M., Alexopoulos, G.S., Fox, M.D., Pascual-Leone, A., Voss, H.U., Liston, C., 2017. Resting-state connectivity biomarkers define neurophysiological subtypes of depression. Nat. Med. 23 (1), 28–38. https://doi.org/ 10.1038/nm.4246. Dunn, J.C., 1974. Well-separated clusters and optimal fuzzy partitions. J. Cybern. 4 (1), 95–104. Dwyer, D.B., Buciuman, M.O., Ruef, A., Kambeitz, J., Sen Dong, M., Stinson, C., Kambeitz-Ilankovic, L., Degenhardt, F., Sanfelici, R., Antonucci, L.A., Lalousis, P.A., Wenzel, J., Urquijo-Castro, M.F., Popovic, D., Oeztuerk, O.F., Haas, S.S., Weiske, J., Hauke, D., Neufang, S., Koutsouleris, N., 2022. Clinical, brain, and multilevel clustering in early psychosis and affective stages. JAMA Psychiatry 79 (7), 677–689. https://doi.org/10.1001/jamapsychiatry.2022.1163. Dwyer, D.B., Kalman, J.L., Budde, M., Kambeitz, J., Ruef, A., Antonucci, L.A., Kambeitz- Ilankovic, L., Hasan, A., Kondofersky, I., Anderson-Schmidt, H., Gade, K., Reich- Erkelenz, D., Adorjan, K., Senner, F., Schaupp, S., Andlauer, T.F.M., Comes, A.L., Schulte, E.C., Kl¨ ohn-Saghatolislam, F., Koutsouleris, N., 2020. An investigation of psychosis subgroups with prognostic validation and exploration of genetic underpinnings: the PsyCourse study. JAMA Psychiatry 77 (5), 523–533. https://doi. org/10.1001/jamapsychiatry.2019.4910. Eberle, O., Buttner, J., Krautli, F., Muller, K.R., Valleriani, M., Montavon, G., 2022. Building and interpreting deep similarity models. IEEE Trans. Pattern Anal. Mach. Intell. 44 (3), 1149–1161. https://doi.org/10.1109/TPAMI.2020.3020738. Edwards, A.W., Cavalli-Sforza, L.L., 1965. A method for cluster analysis. Biometrics 362–375. Efron, B., Tibshirani, R., 1997. Improvements on cross-validation: the 632+bootstrap method. J. Am. Stat. Assoc. 92 (438), 548–560. https://doi.org/10.1080/ 01621459.1997.10474007. Enders, C.K., Bandalos, D.L., 2001. The relative performance of full information maximum likelihood estimation for missing data in structural equation models. Struct. Equ. Model. Multidiscip. J. 8 (3), 430–457. https://doi.org/10.1207/ S15328007SEM0803_5. Eppstein, D., Paterson, M.S., Yao, F.F., 1997. On nearest-neighbor graphs. Discrete Comput. Geom. 17 (3), 263–282. https://doi.org/10.1007/PL00009293. Ester, M., Kriegel, H.P., Sander, J., Xu, X., 1996a. A density-based algorithm for discovering clusters in large spatial databases with noise. KDD’96. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. https://doi.org/10.5555/3001460.3001507. Ester, M., Kriegel, H.P., Sander, J., Xu, X., 1996b. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases With Noise. KDD. Ezugwu, A.E., Shukla, A.K., Agbaje, M.B., Oyelade, O.N., Jos´ e-García, A., Agushaka, J.O., 2020. Automatic clustering algorithms: a systematic review and bibliometric analysis of relevant literature. Neural Comput. Appl. 33, 6247–6306. https://doi. org/10.1007/s00521-020-05395-4. Fahad, A., Alshatri, N., Tari, Z., Alamri, A., Khalil, I., Zomaya, A.Y., Foufou, S., Bouras, A., 2014. A survey of clustering algorithms for big data: taxonomy and empirical analysis. IEEE Trans. Emerg. Top. Comput. 2 (3), 267–279. https://doi. org/10.1109/TETC.2014.2330519. Farahani, F.V., Karwowski, W., Lighthall, N.R., 2019. Application of graph theory for identifying connectivity patterns in human brain networks: a systematic review [Systematic Review]. Front. Neurosci. 13 (585) https://doi.org/10.3389/ fnins.2019.00585. Farris, J.S., 1969. On the cophenetic correlation coefficient. Syst. Zool. 18 (3), 279–285. https://doi.org/10.2307/2412324. Feczko, E., Balba, N.M., Miranda-Dominguez, O., Cordova, M., Karalunas, S.L., Irwin, L., Demeter, D.V., Hill, A.P., Langhorst, B.H., Grieser Painter, J., Van Santen, J., Fombonne, E.J., Nigg, J.T., Fair, D.A, 2018. Subtyping cognitive profiles in autism spectrum disorder using a functional random forest algorithm. NeuroImage 172, 674–688. https://doi.org/10.1016/j.neuroimage.2017.12.044. Feczko, E., Fair, D.A., 2020. Methods and challenges for assessing heterogeneity. Biol. Psychiatry 88 (1), 9–17. https://doi.org/10.1016/j.biopsych.2020.02.015. Feczko, E., Miranda-Dominguez, O., Marr, M., Graham, A.M., Nigg, J.T., Fair, D.A., 2019. The heterogeneity problem: approaches to identify psychiatric subtypes. Trends Cogn. Sci. 23 (7), 584–601. https://doi.org/10.1016/j.tics.2019.03.009 (Regul. Ed.). C.X. Gao et al.