{'fraction_non_alphanumeric': 0.024801840961390948, 'fraction_numerical': 0.009153669138327793, 'mean_word_length': 5.026348228043143, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hybrid Density- and Partition-based Clustering Algorithm for Data with Mixed-type Variables

Clustering is an essential technique for discovering patterns in data. The steady increase in amount and complexity of data over the years led to improvements and development of new clustering algorithms. However, algorithms that can cluster data with mixed variable types (continuous and categorical) remain limited, despite the abundance of data with mixed types particularly in the medical field. Among existing methods for mixed data, some posit unverifiable distributional assumptions or that the contributions of different variable types are not well balanced. We propose a two-step hybrid density- and partition-based algorithm (HyDaP) that can detect clusters after variables selection. The first step involves both density-based and partition-based algorithms to identify the data structure formed by continuous variables and recognize the important variables for clustering; the second step involves partition-based algorithm together with a novel dissimilarity measure we designed for mixed data to obtain clustering results. Simulations across various scenarios and data structures were conducted to examine the performance of the HyDaP algorithm compared to commonly used methods. We also applied the HyDaP algorithm on electronic health records to identify sepsis phenotypes.


Introduction
In precision medicine, the prevention and treatment strategies are tailored according to individual characteristics. Such practice has been greatly improved by using information obtained from large databases (Council et al., 2011) including electronic health record (EHR) which contains patient information such as demographics, daily charts, medical history, lab results, medication use, billing information and others (Häyrinen et al., 2008). In order to efficiently process data and extract useful information, machine learning methods are often applied (Coorevits et al., 2013). Clustering is an important aspect of unsupervised machine learning methods which aims to uncover hidden patient subgroups that may have different diagnoses and treatment responses in EHR data. Further investigations on these subgroups together with current clinical guidelines could help design precision medicine strategies to further assist physicians in providing better patient care (Jensen et al., 2012).
The basic concept of clustering is to divide individuals into a number of subgroups such that individuals within the same subgroup have more similar characteristics, as defined by a set of variables, than the individuals who belong to different subgroups. One of the main challenges in clustering is how to define "dissimilarity" between subjects with data of mixed variable types (continuous and categorical). If all variables are continuous, we can view the collection of information from an individual as a data point, or a vector of variables in a high-dimensional covariate space.
The distance between the data points of two individuals is used to determine the dissimilarity between these two subjects so that a closer distance indicates lower dissimilarity. If all variables are categorical, dissimilarity measures (or similarity measures) were proposed to evaluate how often two individuals are in the same category among those variables. In this context we will use "distance" and "dissimilarity" interchangeably. Gower distance (Gower, 1971), distance defined in factorial analysis of mixed data (FAMD) (Pagès, 2014), and K-prototypes (Huang, 1998) are possible methods to address the above mentioned issue.
Gower distance was proposed to measure dissimilarity between subjects with mixed types of variables. The distance measure used in FAMD can be applied on mixed data as well, even though FAMD was not originally intended for clustering. Distance measure defined in K-prototypes is similar to Gower distance, but it incorporates a user-defined weight for each type of variables. Therefore, K-prototypes assumes that all categorical variables have the same weight, and that all continuous variables have the same weight. This design may not be practical if within the same variable type, some are clinically more important than others in terms of clustering.
Finite mixture model (FMM) (McCutcheon, 1987;Moustaki, 1996) is a model-based clustering method that bypasses the challenge of defining dissimilarity between subjects with mixed types of variables. It assumes that the data is a mixture of several parametric distributions. The unknown distributional parameters including cluster membership can be solved via maximizing likelihood using the expectation-maximization (EM) algorithm. Moreover, it is able to transfer the task of selecting the optimal number of clusters into model selection problem which is much more straightforward. However, its main drawback is that all the distributional assumptions are conditional on the unknown cluster, making those assumptions unverifiable from the data.
In order to identify cluster memberships, it is also important to know the underlying data structure. For example, whether distinct clusters exist in the feature space; or if no natural clusters exist but the data is heterogeneous enough to be partitioned. Such information is crucial in understanding data, selecting clustering methods, and interpreting clustering results. However, to our knowledge, none of the existing methods incorporates this data structure information into clustering.
To address the limitations of the existing methods, we propose a Hybrid Density-and Partitionbased (HyDaP) algorithm to identify clusters for data with mixed types of variables and use this method to discover sepsis phenotypes using demographic and clinical data in EHR for sepsis patients at university affiliated hospitals.
In Section 2 we introduce the most commonly used dissimilarity measures and clustering algorithms; in Section 3 we define three data structures and propose a new clustering algorithm, HyDaP; in Section 4 we present performance comparisons among different methods under various simulation settings; in Section 5 we demonstrate the use of HyDaP algorithm to identify sepsis phenotypes; and Section 6 is discussion.

Review of dissimilarity measures and clustering algorithms
In this section, we briefly review some existing dissimilarity measures and clustering algorithms.
In addition, we discuss the pros and cons of each measure or algorithm.

Dissimilarity measures
Minkowski distance is a family of dissimilarity measures for numeric variables. Let x i be a vector (x i1 , x i2 , ..., x ip ) T representing p variables of subject i. For subjects i and i , Minkowski distance between the two is defined as follows: where m is related to the shape of unit circle which is a two-dimensional contour with every point on the contour at distance of 1 from the center (0, 0). Different choices of m lead to different distance measures. For example, m = 2 leads to the famous Euclidean distance which is intuitive and able to represent physical distances. When m = 1, we obtain Manhattan distance which is often used to detect hyperrectangular clusters. When m → ∞, we obtain Chebyshev (maximum) distance which is the same as chess board distance since it is defined as the greatest value of the differences among all dimensions. A potential problem of using the Minkowski distance is that variables with larger variances tend to dominate the others (Xu and Wunsch, 2005;Shirkhorshidi et al., 2015), therefore, it is recommended to perform variable standardization (that is, rescale the variable by dividing by its standard deviation) before applying this measure.
Other dissimilarity measures for numeric variables include cosine similarity measure, Pearson correlation, Mahalanobis distance, to name a few. Cosine similarity measures the angle between two vectors regardless of vector magnitudes. It is usually applied if we are not interested in magnitudes, for example, for text mining as it captures text meanings instead of counting numbers (Xu and Wunsch, 2005;Han et al., 2011). Pearson correlation is usually used in clustering gene expression data (Xu and Wunsch, 2005), but it is sensitive to outliers. Mahalanobis distance is scale-invariant, and takes into account variable correlations.
When variables are all categorical, simple matching dissimilarity is usually used: indicating whether variable j are the same for individuals i and i .
None of above-mentioned dissimilarity measures can be applied to mixed data. Gower distance was proposed to calculate the distance between subjects with mixed types of variables. Let X be a data matrix with n × p dimensions. Let the first h variables of X be continuous and the (h + 1) th to p th variables be multilevel categorical variables or symmetric binary variables. Let X j be a vector (x 1j , x 2j , ..., x nj ) T representing variable j. Gower distance between individuals i and i is defined as: Gower distance for an asymmetric binary variable is calculated differently. Asymmetry occurs when similarity within one level is perceived to be higher compared to the other level. For example, breast cancer (yes/no) could be viewed as an asymmetric binary variable since individuals with breast cancer are much more similar than those without breast cancer (which could include men and women, adolescents and elder people). If variable j is an asymmetric binary variable, then the Gower distance between individuals i and i with respect to this variable is defined as: and they are the level with larger similarity   1 otherwise.
In practice, there is one issue in applying Gower distance: as we will later show in simulations, Gower distance tends to give much larger weights to categorical variables than to continuous ones. This is because the distance due to a categorical variable is always 0 or 1, the minimum and the maximum of possible distance values, granting categorical variables more power in distinguishing subjects.
Another distance that could be used for mixed types of variables is the distance defined in FAMD: C j is number of levels of categorical variable j; p jl is proportion of l th category of variable j; L jl is l th category of variable j.

K-means-based clustering algorithms
K-means (MacQueen et al., 1967) is the most well-known and applied clustering method in practice.
The basic idea is to partition subjects with respect to minimizing the within-cluster sum of squares (WCSS). This algorithm is very efficient and has been the root of many later developed ones. It is usually used together with Euclidean distance. To cluster categorical data, K-modes (Huang, 1998) algorithm was developed by replacing Euclidean distance with simple matching dissimilarity measure, and replacing mean with mode to represent cluster centers.
To identify clusters with mixed types of variables, the partition around medoids (PAM) (Kaufman and Rousseeuw, 2009) has been proposed. PAM is a modification of K-means with a different definition of cluster centers. Unlike K-means which uses within-cluster mean to represent its centers, PAM uses medoids which are actual data points in the dataset. This makes defining centers of categorical variables possible. Moreover, medoids are analogous to medians and hence PAM is more robust to outliers. One drawback however is that PAM is computationally intensive and inefficient, making it less ideal for processing large data sets.
K-prototypes algorithm is another modified version of K-means with the ability of handling mixed types of variables. Its centers are called prototypes, which use within-cluster mean to represent continuous variables and mode for categorical variables. The distance between subjects i and i is defined as: and γ is a user-defined weight parameter for categorical variables. K-prototypes lacks flexibility in variables weights as it assumes equal importance for variables of the same type. Moreover, the tuning parameter γ is user-defined rather than data-driven.

Hierarchical clustering
Hierarchical clustering is another category of clustering methods. It first grows a dendrogram which is a tree-like diagram showing hierarchical structure of subjects and then cuts the dendrogram to obtain clusters. One advantage of hierarchical clustering is that the generated dendrogram is very informative and provides information of cluster structure besides cluster assignments. Its disadvantages include no global objective function, a greedy type of procedure, the sensitivity to outliers, and inefficient for large data sets.

Extended clustering framework
In many situations researchers are also often interested in variables' importance, not just cluster identification. Motivated by this interest, sparse clustering framework (Witten and Tibshirani, 2010) was proposed. It incorporates feature selection through a Lasso-type penalty, and adds variable weights to the objective function: subject to w 2 1, w 1 s, w j 0 ∀j, where n is number of subjects; p is number of features; w = (w 1 , w 2 , ..., w p ) T is the weight vector; Θ is a parameter vector restricted to lie in a set D; f j (X j ; Θ) is some function that involves feature j only; and s is a L1 norm restriction, which is a tuning parameter in the algorithm. We could plug in many algorithms like K-means, hierarchical clustering into this framework to obtain sparse version algorithms. One of the main attractions of sparse clustering is that it conducts data-driven variable selection and clustering simultaneously. However, the selection of tuning parameter s may not be straightforward.
Many partition-based algorithms require pre-specification of K, the optimal number of clusters, but how to choose it is another important question. The consensus clustering framework (Monti et al., 2003;Wilkerson and Hayes, 2010) can help determine number of clusters and obtain cluster memberships simultaneously. In addition, it can assess stability of discovered clusters. Consensus clustering incorporates results from multiple runs of an inner-loop clustering algorithm (e.g., Kmeans) on sub-sampled subjects. For each pair of subjects, a consensus index is obtained by calculating proportion of times the pair was assigned to the same cluster among times both pair members were sampled. The consensus index can then serve as a similarity measure and subjected to a hierarchical clustering algorithm to form final clusters. Choosing K is achieved by checking the consensus matrix heatmaps and cluster-consensus values. The number of clusters that yields the cleanest heatmap and highest cluster-consensus values is preferred.

Density-based clustering
Another important category of clustering methods is density-based clustering. All above-mentioned algorithms are distance-based methods which are more appropriate for detecting clusters that are convex shaped and with similar sizes and densities. If the underlying clusters have arbitrary shapes, density-based clustering algorithms may work better. Density-based spatial clustering of applications with noise (DBSCAN) (Ester et al., 1996) and ordering points to identify the clustering structure (OPTICS) (Ankerst et al., 1999) are two widely used density-based algorithms. DBSCAN does not need input of K, and it is robust to noise. However, it is not well suited for high dimensional data or for clusters with varying densities. OPTICS is an improved method which can detect clusters with varying densities while not being over sensitive to its user-specified tuning parameters.

Model-based clustering
FMM is a model-based clustering method assuming that the data is consists of K latent clusters.
Its density function is defined as: where π k is the cluster mixture probability, K k=1 π k = 1; and g k is the conditional distribution given cluster k. For a sample of size n, the log-likelihood can be written as: FMM assumes conditional independence given cluster k, that is, g k (x i ) = p j=1 g k (x ij ), and the EM algorithm is usually used to obtain the MLE. The posterior probability of each subject belonging to each cluster can be calculated as:p .
Subjects are then assigned to the cluster with which the posterior probability is the largest. These probabilities help discriminate core subjects (those with high probability of belonging to assigned cluster) and border subjects (those with low probability of belonging to assigned cluster) within each cluster. Given the parametric form of FMM, formal inference is possible. In addition, selecting the number of clusters becomes a model selection problem. The main drawback however is its unverifiable distributional assumptions; all the inferences are conducted conditional on unknown cluster assignments.
There are some other approaches to handle mixed types of variables. These include categorizing all continuous variables (Haripriya et al., 2015) or converting categorical variables into continuous or dummy variables and then treat the dummy variables as continuous (Hennig and Liao, 2013).
However, both ideas will lead to information loss. Another common idea is to cluster continuous part of the data and categorical part separately. The final clusters are obtained by ensembling these two sets of clustering results (Reddy and Kavitha, 2012). This method impractically weigh continuous and categorical variables equally and ignore possible mutual influences between the two variable types.

DaP) algorithm for mixed data
To address the limitations of the existing clustering methods in handling data containing mixed types of variables, we propose a hybrid density-and partition-based clustering (HyDaP) algorithm which consists of a pre-processing step (step 1) and a clustering step (step 2). The preprocessing step identifies the data structure formed by continuous variables and recognizes the important variables for clustering. In the clustering step, our proposed dissimilarity measure is used to obtain a dissimilarity matrix, which can be fed into PAM to obtain the final results. We describe the HyDaP algorithm in detail below.

Pre-processing step (Step 1)
To help with variable selection and better understand the data set, we first define 3 data structures for the space spanned by the continuous variables as: natural cluster structure (data structure 1); partitioned cluster structure (data structure 2); and homogeneous structure (data structure 3).
Once the data structure is known, we apply tailored variable selection procedures. At the end of the pre-processing step, a set of selected variables will proceed to the clustering step (step 2) ( Figure 1).  with and without natural clusters. A hypothetical example of these two scenarios is depicted in Figure 2. We can observe that both Data 1 and Data 2 contain two variables, but natural clusters only exist in Data 1. Although this conclusion is straightforward for Data 1 and Data 2, when data is spanned in a high-dimensional space, it is impossible to visually examine existence of natural clusters. Therefore, we use a density-based clustering algorithm (e.g., OPTICS) and resulted reachability plot to help understand the spatial structure of the data. Reachability plot is a bar plot showing ordered reachability distances among subjects (Ankerst et al., 1999). A reachability plot provides an overall 2-dimensional spatial structure of a dataset regardless of its original dimensions. The horizontal axis of the plot is the processing order and the vertical axis is the reachability distance. Each trough on the reachability plot can be viewed as a single cluster.
Edges between two side-by-side troughs represent the distance between two closest border points from the corresponding two clusters. Higher edges imply that the corresponding two clusters are farther apart while lower edges or unclear edges imply that clusters are not that distinct from each other.  in Figure 2, this indicates existence of distinct clusters, i.e., the corresponding dataset has natural clusters. We call this type of structure natural cluster structure (data structure 1 ) and aim to identify these distinct clusters. If we only observe one trough or no clear through in the reachability plot (e.g., reachability plot of Data 2 in Figure 2), this indicates that distinct clusters do not exist.
Then we will investigate whether data points in the continuous covariate space are sufficiently heterogeneous to be further partitioned. We use consensus clustering framework for all continuous variables to access the possible heterogeneity by checking the selected optimal number of clusters.
If we obtain ≥ 2 clusters in consensus clustering, this indicates that heterogeneity exists and we can obtain stable clusters through partitioning. We call this type of structure partitioned cluster structure (data structure 2 ). If the optimal number of clusters is one from the consensus clustering results, this indicates that continuous part of the data is highly homogeneous and cannot be further partitioned. We call this type of structure homogeneous structure (data structure 3 ).

Variable selection
After identifying the data structure, we conduct data structure tailored variables selection.
Under the natural cluster structure, distinct clusters can be determined by continuous variables.
Therefore, we would like to select those having high contributions. As shown in Figure 1,

Clustering step (Step 2)
After variables with high contributions are selected, we proceed to the final clustering step. This step is the same across all data structures. We calculate the dissimilarities between subjects using our proposed dissimilarity measure, a modified version of the Gower distance. Assume that the first h variables are continuous and the rest are categorical. Our proposed dissimilarity between subjects i and i is defined as: Our modification is based on the idea of standardization to avoid variables with high variability be extremely influential to clustering results. It is motivated by the definition of Gower distance for categorical variables as they receive extreme dissimilarity values 0 or 1, which could exhibit high variability. This allows them to exert greater influence in the clustering results even if they are less informative than the continuous ones.
Below we show how our modification on dissimilarities is analogous to the standardization on continuous variables. Standardized squared Euclidean distance between subjects i and i with respect to a continuous variable j is: which can be re-written as: where the numerator is the original squared Euclidean distance, the denominator is proportional to the sum of all pairwise distances. We adopt this idea to standardize the Gower distance, namely we divide the original Gower distance of variable j by sum of all pairwise Gower distance of variable j as shown above.
If after the pre-processing step all selected variables are continuous, we can just apply usual clustering methods to obtain the final clustering results.

Parameters selection
In this section we provide general suggestions on the selection of (1) the optimal number of clusters; (2) continuous variables under natural cluster structure.

Number of clusters
Under the natural cluster structure, the number of clusters can be decided by the number of troughs in the reachability plot. Under the partitioned cluster structure, the number of clusters can be selected from the results of the consensus clustering. Under the homogeneous structure, we only select categorical variables in determining cluster membership. Hence we suggest constructing a dissimilarity matrix using our proposed dissimilarity measure and then plot the number of clusters against the corresponding within-cluster sum of dissimilarities. In this plot, we look for an elbow for the optimal number of clusters.

Selecting continuous variables under the natural cluster structure
Selection of the continuous variables with high weights under the natural cluster structure could be subjective because of the choice of the weight threshold. We suggest applying sparse K-means for continuous part of each bootstrapping data set and then calculate the between-cluster sum of squares (BCSS). We then order these variables by their median BCSS from the smallest to the largest and plot the median (with 2.5 th quantile and 97.5 th quantile interval) of BCSS. Then we drop variables whose BCSS values are small or far away from the others. Our suggestion here is a heuristic one. Users can always incorporate other information and make their own judgements.

Simulation studies
In this section we use simulations to evaluate the performance of the HyDaP algorithm relative to the existing approaches. Assuming that there are 3 underlying true clusters with cluster sizes of 40, 40, and 120. In terms of variable importance, we considered scenarios (1) both variable types contribute to clustering, (2) only continuous variables contribute to clustering, and (3) only categorical variables contribute to clustering. In terms of data structures, all 3 data structures were covered in simulations. Details of the distributions and parameters used in these simulation settings are shown in Table 1.
For each setting, 500 datasets were generated. Cluster analysis was performed on each dataset using the proposed HyDaP algorithm. We compared its performance with PAM with Gower distance, K-prototypes, FMM, and PAM with FAMD distance. Since we know the true cluster labels, the adjusted rand index (ARI) was calculated and used to evaluate the performances of different methods. ARI is used to measure the agreement between two nominal variables. Its largest value is 1 indicating perfect agreement and its smallest value is close to 0 indicating no agreement. For the purpose of evaluating clustering performance in simulations, higher ARI values indicate better agreement with true cluster labels and hence better performance. The reachability plot for each setting is illustrated in Figure 3. Table 2 summarizes the results of the pre-processing step of the HyDaP algorithm. The clustering performance with respect to ARI across all simulation settings is shown in Table 3. To examine the impact of conditional correlation on clustering performance, each simulation setting was imbued with a pairwise correlation of 0.4 conditional on true cluster labels. Results are shown in Table 4. Median along with the 2.5 th and 97.5 th percentiles were reported for all statistics.

Natural cluster structure
In simulation 1(a), we simulated a total of 5 variables: 4 continuous and 1 categorical. All except one continuous variable truly contribute to clustering. The sole categorical variable also contributes to clustering. In Step 1 of the HyDaP algorithm, the reachability plot ( Figure 3a) indicated 3 clusters. There-fore, this setting has natural cluster structure as 3 distinct clusters exist. Table 2 shows the very low contribution of x 4 from the sparse K-means and the strong association between x 5 and the clusters identified by the sparse K-means. We dropped x 4 and kept all the others. In Step 2, we applied PAM along with the proposed dissimilarity measure on the selected variables from Step 1: x 1 , x 2 , x 3 , and x 5 .
As shown in Table 3

Partitioned cluster structure
In simulation 1(b), we simulated a total of 14 variables: 11 continuous and 3 categorical. Six out of eleven continuous variables truly contribute to clustering; two out of three categorical variables contribute to clustering. In Step 1 of the HyDaP algorithm, Figure 3b indicated that no natural clusters exists. After conducting consensus K-means, we chose 3 as the optimal number of clusters as its corresponding cluster-consensus values were the largest. Thus, a partitioned cluster structure was identified. All continuous variables were retained for the next step. Variable x 12 was dropped because of its small Cramer's V with cluster assignments obtained in consensus K-means. In Step 2, PAM with proposed dissimilarity measure was applied on x 1 , x 2 ,. . . , x 11 , x 13 , and    In simulation 2(a), we simulated a total of 5 variables: 4 continuous and 1 categorical. This setting is the same as simulation 1(a) except that the sole categorical variable does not contribute to clustering. In Step 1 of the HyDaP algorithm, x 4 was dropped due to its low contribution in the sparse Kmeans. Table 2 shows a weak association between the categorical variable x 5 and clusters identified by the sparse K-means. In Step 2, we applied the sparse K-means on x 1 , x 2 , and x 3 as they are all continuous variables. Meanwhile, FAMD was not originally designed for clustering.

Natural cluster structure
In simulation 2(b), we simulated a total of 8 variables: 5 continuous and 3 categorical. Four out of five continuous variables truly contribute to clustering and follow highly skewed distributions.
None of the categorical variables contributes to clustering. In Step 1 of the HyDaP algorithm, Figure 3d shows 3 distinct clusters and hence this setting was identified as natural cluster structure. We dropped x 5 because of its small contribution to clustering as shown in Table 2. All categorical variables were dropped as well given their weak associations with clusters obtained in the sparse K-means. In Step 2, we applied the sparse K-means on x 1 , x 2 , and x 3 since they are all continuous variables. In simulation 3, we simulated a total of 7 variables: 4 continuous and 3 categorical. None of the continuous variables truly contributes to clustering. Two out of three categorical variables contribute to clustering. In Step 1 of the HyDaP algorithm, Figure 3e indicates no natural clusters exist. After conducting consensus K-means, the optimal number of clusters chosen was 1 because cluster-consensus values were low for all numbers of clusters. Hence this was identified as homogeneous structure. All continuous variables were dropped but categorical variables x 5 and x 7 were kept due to their strong association with each other as shown in Table 2. In Step 2, PAM with proposed dissimilarity measure was applied on x 5 and x 7 .
In this setting, the HyDaP algorithm performed the best (

Variables are conditionally correlated
To assess the impact of within-cluster correlation, simulations for each of the 5 settings above was repeated with pairwise correlation of 0.4 for all continuous variables conditional on true cluster labels. As summarized in Table 4, within-cluster correlation had little to no impact on the performance of the HyDaP algorithm, PAM with Gower distance, K-prototypes, and PAM with FAMD distance. In some situations, it led to worse performance of FMM. This is expected since FMM assumes conditional independency, namely all variables are independent with each other conditional on clusters labels. However, we did observe that in simulation 3 when none of the continuous variables contributes to clustering, the optimal number of clusters selected by the consensus K-means was 2 instead of 3 (figures not shown here). This is understandable since all pairs of continuous variables are correlated given true cluster labels, therefore, they share a lot of common information. To some extent we can use only one of them without losing much information as all others as redundant. For any single continuous variable we can potentially divide it into 2 subgroups that have some differences. But this does not essentially mean these 2 subgroups can be viewed as 2 clusters. Therefore, if we observe that 2 is the optimal number of clusters in consensus clustering results and most pairs of continuous variables have high conditional correlations, we should be cautious. One suggestion is that we could try to look for continuous variables that have similar

Simulation summary
From the simulation studies, we found that our proposed HyDaP algorithm was consistently the top or one of the top performers across all simulation settings. Moreover, we found that (1) when categorical variables do not contribute much to clustering, PAM with Gower distance performed poorly; (2) when continuous variables follow arbitrary distributions, FMM may not perform well due to assumption violation; (3) when none of continuous variables contributes to clustering, Kprototypes may fail; (4) performance of PAM with FAMD distance was not stable across different scenarios as its distance measure is not specifically designed for clustering. The objectives of the analysis are to select the most important variables among 30 demographic and clinical variables, and to identify homogeneous clusters (phenotypes). Twenty eight variables were continuous and 2 were categorical. Although we do not have much information about the optimal number of clusters for the data set, our clinician colleagues suggested that larger numbers of clusters are preferred.

Real data application
Data structure identification: The reachability plot in Figure 4 indicates that there is no natural clusters in the SENECA data. Unlike the genetic data, we rarely observe natural clusters in data collected from clinical settings. We then performed the consensus K-means for all continuous variables, and the results are depicted in Figure 5 suggesting that the optimal number of clusters is 4, which indicates that the data structure of the SENECA data belongs to partitioned cluster structure.
Variable selection: Under partitioned cluster structure we kept all continuous variables. For categorical variables, Cramer's V is 0.05 between gender and cluster membership from consensus clustering and it is also 0.05 between race and cluster membership. Therefore, we dropped gender  Figure 5: Consensus K-means optimal number of clusters selection and race before proceeding to the final clustering step.
Clustering step: All categorical variables were excluded after the pre-processing step, so we took the results from the consensus K-means as our final clustering results. In terms of variable importance, all continuous variables together had contributions to the obtained partitions but none of them showed dominant impact. Neither gender nor race were important clustering variables. We obtained 4 clusters with relatively balanced sample sizes: 6, 625, 5, 512, 5, 385, and 2, 667. Within each cluster, distributions of some important clinical endpoints are shown in top left plot of Figure 6.
We can observe that Cluster 1 has the lowest proportion for all clinical endpoints while Cluster 2 has the second lowest ones. Cluster 4 has the highest proportions. With our clinician colleagues, we examined patient characteristics of the resulting clusters. We observed that sepsis patients in Cluster 1 had fewer other health issues; patients in Cluster 2 were those who were older, had multi morbidities, and renal dysfunctions; patients in Cluster 3 were those who had more inflammations and pulmonary dysfunctions; and patients in Cluster 4 were whose who had more acidosis, liver, and cardiovascular dysfunctions.
For comparison, we applied PAM with Gower distance, K-prototypes, and FMM to obtain cluster memberships assuming 4 clusters. The results are summarized in Figure 6. For PAM with Finite mixture model Figure 6: Clinical endpoints across 4 clusters identified by different methods Gower distance, we took a random sample of the whole SENECA data with size 5, 000 because the computation time of this algorithm was very long. After further exploration we found that gender dominated the clustering result as the proportion of male is 0.0% in Cluster 1, 2.7% in Cluster 4, 99.4% in Cluster 2, and 99.8% in Cluster 3. Note that gender was not relevant based on our proposed HyDaP algorithm. For the K-prototypes, we found that the 4 clusters obtained were not that distinct from each other in terms of the distribution of clinical endpoints. The 4 clusters obtained from the FMM appeared to be distinct from each other and similar to what we observed in HyDaP algorithm. However, Cluster 1 has larger proportion of patients admitted to ICU, use of mechanical ventilation and vasopressor compared to Cluster 2, but it has lower mortality rate.
Next, we re-applied the existing methods by first selecting the method-specific optimal number of clusters. The number of clusters versus the total WCSS or BIC values are shown in left column of Figure 7. We found that the optimal number of clusters was 2 for PAM with Gower distance and for K-prototypes, and 3 for FMM. We once again observed that the clustering results were dominated by gender when using PAM with Gower distance. The proportion of men was 1.

Discussion
We proposed a hybrid density-and partition-based clustering (HyDaP) algorithm to conduct variable selection and identify clusters in data consisting of mixed types of variables. Our algorithm involves a pre-processing step to identify the data structure formed by continuous variables and to select important variables, and a clustering step to determine the cluster membership. In the clustering step, we proposed a dissimilarity measure that balances the contributions between continuous and categorical variables, which the existing clustering methods do not offer. Through simulation studies, we showed that the proposed HyDaP algorithm is robust to different data structures and outperforms or at par commonly used methods. We also defined 3 different data structures to help understand data and better interpret clustering results. Our method successfully identified four clinically meaningful sepsis phenotypes for data extracted from EHR of multiple health care systems. The resulting phenotypes are highly associated with several clinical endpoints.
Our HyDaP algorithm inherits the limitations of sparse K-means. For data under the natural cluster structure, if the continuous variables contain many outliers or excessive zeros (a.k.a. zeroinflated), the sparse K-means procedure cannot correctly identify variables with high contributions.
Another situation that could affect the later steps in our method and lead to unsatisfactory results is that when data contains continuous variables of the same value for the majority of subjects while other few have different values. We also suggest checking variables that have similar clinical meanings or highly clinically related before clustering and only keep one of them to avoid existence of within-cluster correlations.
Clustering has emerged as one of the essential and popular techniques for discovering patterns in data or disease phenotypes. Although clustering methods keep evolving to cope with increasing complexity in data, certain features in data sets could limit the utilization of the existing approaches.
Unlike genetics or genomics data, data collected from clinical settings often include various types.
Our proposed algorithm overcomes the drawbacks of the commonly used clustering algorithms therefore the results from using our method may be more helpful to clinicians in making good medical decisions.  (SaO2) Minimum partial pressure of oxygen (PaO2) within 6 hours of ER presentation