{'fraction_non_alphanumeric': 0.033415014479839605, 'fraction_numerical': 0.014442711814064008, 'mean_word_length': 4.642019271051529, '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': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Hierarchical clustering: visualization, feature importance and model selection

We propose methods for the analysis of hierarchical clustering that fully use the multi-resolution structure provided by a dendrogram. Specifically, we propose a loss for choosing between clustering methods, a feature importance score and a graphical tool for visualizing the segmentation of features in a dendrogram. Current approaches to these tasks lead to loss of information since they require the user to generate a single partition of the instances by cutting the dendrogram at a specified level. Our proposed methods, instead, use the full structure of the dendrogram. The key insight behind the proposed methods is to view a dendrogram as a phylogeny. This analogy permits the assignment of a feature value to each internal node of a tree through ancestral state reconstruction. Real and simulated datasets provide evidence that our proposed framework has desirable outcomes. We provide an R package that implements our methods.


Introduction
Clustering methods have the goal of grouping similar sample points. They are used in applications such as pattern recognition (Chen et al., 2014), image analysis (Rocha et al., 2009), bioinformatics (Datta and Datta, 2003), and information retrieval (Jardine and van Rijsbergen, 1971).
Clustering techniques can be divided into two categories: partition-based and hierarchical. An example of partition-based clustering is K-means (MacQueen, 1967), which creates K clusters based on a Voronoi partition of the feature space. Similarly, mode-based clustering (Fukunaga and Hostetler, 1975) creates a partition by assigning each observation to a mode of a density estimate. On the other hand, hierarchical clustering yields a tree-based representation of the objects (dendrogram), such as in agglomerative clustering (Ward Jr, 1963), DIANA (Rousseeuw and Kaufman, 1990) and partial least squares methods (Liu et al., 2006). This paper focuses solely on hierarchical clustering. (Right) By cutting the dendrogram at height 4, two clusters are obtained.
Hierarchical clustering has some advantages when compared to partition-based clustering. For instance, it does not require the specification of the number of clusters. Also, as shown in Figure 1, a dendrogram displays a general similarity structure of the data by providing a multiresolution view. The lower in the dendrogram that two observations are merged, the more similar they are. By using this similarity structure, Figure 1 illustrates how to obtain a partition by cutting a dendrogram at a given height.
When using hierarchical clustering, three questions need to be answered: 1. Which hierarchical clustering method should be used?
2. How is the resulting dendrogram interpreted in terms of the features?
3. How important is each feature in a dendrogram?
Current approaches to these questions require the user to generate a partition by cutting the dendrogram at a specified level (Datta and Datta, 2003;Hubert and Arabie, 1985;Rosenberg and Hirschberg, 2007;Yeung et al., 2001;Kassambara, 2017;Seo and Shneiderman, 2002;Galili, 2015;Ismaili et al., 2014;Badih et al., 2019). This step leads to loss of information, since it restricts itself to a single partition and, therefore, does not make use of the richer structure provided by the dendrogram. In this work, we develop a novel framework for using the full information in a dendrogram for answering questions 1 to 3. Our approach answers these questions based on methods for ancestral state reconstruction that are commonly used in phylogenetic analysis (Borges et al., 2021). The key insight in this framework is to view a dendrogram as a phylogeny. This metaphor is useful since the philogeny associates a probabilistic evolutionary model to the features.
We illustate this approach using the ceramic samples dataset 1 , which contains information about the chemical composition of ceramic samples. The table in Figure 2a provides the hierarhical clustering prediction loss (Subsection 3.2) for a few clustering methods. This loss provides an immediate way of comparing the performance of the methods. For instance, since McQuitty has the lowest loss, it has the highest performance in this dataset, closely followed by average linkage. Also, Figure 2b illustrates the feature importance score (Subsection 3.3). This figure shows that for example, while AL 2 O 3 , SrO and CaO are the most relevant feature in the construction of the dendrogram, MgO, CuO and ZnO are the least important ones. Finally, Figure 2c illustrates how the hierarquical structure explains the distribution behaviour of each feature. The left dendrogram shows that AL 2 O 3 is well segmented by the dendrogram, as explained by the even color distribution among its major branches. That is, while 2 major clusters are characterized by low values for AL 2 O 3 , a third major cluster is characterized by high values of AL 2 O 3 . The right dendrogram shows that MgO is not so well explained by the dendrogram, since its major branches contain a high variability of colors. None of the illustrations required us to fix the number of clusters.
This work is organized as follows: Section 2 reviews hieararchical clustering and ancestral state reconstruction, Section 3 formulates and explains our methodology, Section 4 outlines related approaches, and Section 5 shows experimental results.

The relation between hierarchical clustering and ancestral state reconstruction
Hierarchical clustering and phylogenetics share a common trait: dendrograms and phylogenies are both formalized as trees. That is, the difference between a dendrogram and a phylogeny is given solely by the context in which it is used. While a dendrogram is used to specify the similarity structure between instances, the phylogeny describes evolutionary relationships. Since both types of analysis share a common formalism, it is possible to adapt the methods of one to the other. Based on this shared formalism, we also use a common notation for describing the elements of a tree. The left panel in Figure 1 depicts a tree. The nodes at the bottom of the tree are called leaves. These leaves often represent instances in the dataset. As one moves up the tree, the leaves merge into internal nodes, and then internal nodes merge with one another until the root is reached at the top of the tree. The descendants of a node are the leaves that stem from it.
The following subsections briefly review hierarchical clustering and phylogenetical ancestral state reconstruction.

Hierarchical methods
Hierarchical clustering methods yield a tree-based representation of the data named dendrogram, as illustrated in Figure 1. In clustering, a node is often interpreted as the group of instances which are its descendants. The earlier a merge between two nodes, the more similar are the corresponding groups of descendants (James et al., 2013).
Using the dendrogram, it is possible to partition the instances according to their similarity. Such a partition is obtained by cutting the dendrogram with a horizontal line at a given height, as shown on the right panel of Figure 1. While cutting at lower heights obtains groups with a greater similarity, cutting at higher heights obtains a smaller number of groups. A trade-off between these properties yields the most interpretable partition.
Hierarchical clustering methods can be divided into two paradigms: agglomerative (bottomup) and divisive (top-down) (Hastie et al., 2009). Agglomerative strategies start at the leaves of the dendrogram, iteratively merging selected pairs of branches until the root of the tree is reached. The pair of branches chosen for merging is the one that has the smallest measurement of intergroup dissimilarity. Divisive methods start at the root at the root of the tree. Such methods iteratively divide a chosen branch into smaller ones until the leaves are obtained. The splitting criterion maximizes a measure of between-group dissimilarity.

Ancestral state reconstruction in phylogenetics
A phylogeny represents the evolutionary relationships among instances based on similarities in their features (traits) (Felsenstein, 1985). Each leaf of a tree often represents, for example, a specimen, a species or a family. In this context, an internal node is interpreted as the most recent common ancestor of its descendants. It is often reasonable to posit that these ancestors have unobserved feature values. In this context, ancestral state reconstruction is the task of estimating unobserved feature values based on the phylogenetic tree and on the feature values in the dataset. This reconstruction is often performed by SIMMAP (Bollback, 2006) for categorical features and by methods based on Brownian motion (O'Meara et al., 2006;Clavel et al., 2015;Revell, 2012) for continuous features.
The above ancestral state reconstruction methods are illustrated in Figure 3, which was obtained using the phytools package (Revell, 2012) 2 . Figure 3a illustrates ancestral state reconstruction for a categorical binary feature. The pie chart over each node is the estimated probability distribution of its feature value. Figure 3b illustrates ancestral state reconstruction for a continuous feature. The color of each node represents the expected value of its feature value.
In the following section, we present our methodology, which adapts methods of ancestral state reconstruction to the analysis of hierarchical clustering.

Evolutionary dendrograms
By interpreting a dendrogram as a phylogeny, one can obtain insights about the clustering through ancestral state reconstruction. This approach offers a multiresolution visualization of the data, which does not require a pre-specified number of clusters. More specifically, this approach describes how each feature behaves in each internal node of the dendrogram. Such a visualization provides insight about what partition size yields a more useful description of the data. We illustrate this graphical analysis with an application to the USArrests (McNeil, 1977) and Iris (Fisher, 1936) datasets.

Evolutionary dendrograms applied to the USArrests dataset
The USArrests dataset describes the urban population and murder, assault and rape rates per 100.000 residents for each of the USA states. Using this data, we obtain a dendrogram for the USA states using the McQuitty method and perform ancestral state reconstruction applying applying a maximum likelihood algorithm with interpolation along the edges (Felsenstein, 1985;Revell, 2012Revell, , 2013. Figure 4a shows the evolutionary dendrograms for standardized Murder (left) and Assault (right) rates per 100.000 residents. Since the major branches of the dendrogram have similarly colored descendants in both cases, the analyzed features are well segmented by the dendrogram. For instance in the left dendrogram, the major internal nodes go from high murder rate (yellow), with descendant states listed from South Carolina to Louisiana, medium murder rate (green), from New Mexico to Alaska, mild to low rates (light blue), from Utah to Arkansas, and low rates (dark blue), from New Hamsphire to South Dakota. In the right dendrogram, Assault rates are segmented in a similar way. The main difference from the previous analysis is that high assault rates are not well separated from medium assault rates. Indeed, the internal nodes in the list of states from New Mexico to Louisiana remain light green until close to the leaves. This analysis leads to insights about useful data partitioning. For instance, one might use a coarse partition which divides the states into three groups: one with medium to high murder and attack rates, another with mild rates, and the last with low rates. Furthermore, one could also refine the partition by dividing the first group into two others with respectively high and medium murder rates. Figure 4b shows the evolutionary dendrograms for Rape rate per 100.000 residents (right) and Urban population (left). The deep internal nodes of Rape rate are colored similarly to Assault rate. That is, these features segmented similarly by the dendrogram. However, Urban population is not well segmented by the dendrogram. Indeed, almost all deep internal nodes are green. The only exception occurs for the internal node in light blue that has descendants listed from New Hampshire to South Dakota, which is characterized by smaller urban populations.

Evolutionary dendrograms applied to the Iris dataset
The Iris dataset contains measurements related to 150 flowers. Specifically, it contains the width and length of the sepals and petals of flowers which are classified into three species: setosa, versicolor, and virginica. In this analysis, we performed clustering using complete linkage over the petal and sepal measurements. Although the species were not used in the clustering, a graphical analysis shows how well the resulting dendrogram segments this label. Figure 5 illustrates the evolutionary dendrogram for species using SIMMAP (Bollback, 2006). The Figure shows that, using a partition of size 5, the dendrogram segments the label adequately.  Before one can interpret a dendrogram, it is necessary to choose a clustering algorithm. The next subsection proposes a new loss function for evaluating the performance of each algorithm.

Cross-validated loss (CVL)
The connection between dendrograms and phylogenies can also be explored for choosing between clustering algorithms. The main advantage of this relation is that a phylogeny induces predictions over instances. As a result, it is possible to adapt to clustering the methods for model selection that are used in supervised learning. More specifically, our proposal is an adaptation of a leave-one-feature-out cross-validation approach for selecting phylogenies (Borges et al., 2021). The proposal is described in Algorithm 1. For Algorithm 1 to be operational, it is necessary to choose a prediction function and a measure of inaccuracy of predictions. We definex i , j as a prediction for x i , j , the j -th feature of the i -th instance, and d j (x i , j , x i , j ) as the inaccuracy ofx i , j with respect to x i , j . The choice of these functions depends on whether the feature under analysis is categorical or continuous.
When the feature is categorical, we consider that the prediction is a list of probabilities for each category. Formally, if x i , j ∈ A , thenx i , j = (π i , j ,a ) a∈A , where π i , j ,a is an estimate of the probability that x i , j = a. Determining these probabilities based on the dendrogram is analogous to inferring missing characters on phylogenies, as performed for example by SIMMAP. Hence, we propose using SIMMAP for computing π i , j ,a . Using such predictions,

algorithm 1 Cross-validation loss (CVL)
Input: Clustering algorithm,T , and data x i , j , for 1 ≤ i ≤ n and 1 ≤ j ≤ p. Output: CVL(T ), the cross-validated predictive loss ofT . LetT − j be obtained by applyingT to the data with feature j removed.

3:
for each instance, i , do 4: Letx i , j be a prediction for x i , j based onT − j and on x i , j for i = i . 5: Average inaccuracy for j 8: end for 9: Let CVL(T ) := p −1 p j =1 L j (T − j ) T 's average inaccuracy d j is defined as the Brier score, that is, When the testing feature is continuous, we consider that the prediction is an estimate of a typical feature value. Drawing from the phylogenetical analogy,x i , j is computed using the Brownian Motion process (O'Meara et al., 2006;Clavel et al., 2015), which was originally developed to infer continuous features for internal nodes and leaves of a phylogeny. In this case, each instance x i , j is standardized (that is, it is normalized to have mean zero and variance one) before fitting the Brownian Motion process, and d j is defined as the squared error, Besides motivating the above loss for clustering algorithms, the predictive approach to dendrograms can also be used to build a score of feature importance. This score is discussed in the next subsection.

Phylogenetic feature importance score (PFIS)
Based on the idea that dendrograms provide predictions over their leaves, it is possible to construct a score for feature importance. Letx i , j (T ) be a prediction for x i , j based on T and on x i , j , for i = i . We define the Phylogenetic Feature Importance Score (PFIS) of feature j over T , I j (T ), as: measures the inaccuracy of T 's in predicting j . Notice that, for standardized continuous features and the squared error (Equation 1), L j (T ) is exactly the ratio between sum of squares of residuals and total sum of squares, with SS r es = n i =1 d j (x i , j (T ), x i , j ) and SS t ot = n. It follows that, in this case, I j (T ) is a coefficient of determination, R 2 , often used to evaluate the explanation power of statistical models in regression analysis (Neter et al., 1996).
The main purpose of PFIS is to filter features according to how relevant they are in the segmentation of the dendrogram. For instance, the features in Subsection 3.1 with small importance scores lead to evolutionary dendrograms without a clear structure. By knowing this in advance, one focus on looking at the more informative figures.

Related Work
To the best of our knowledge, our framework to graphical analysis, clustering scores and feature importance is the first one that uses the full hierarchical structure given by a dendrogram. All previous approaches involve mapping the dendrogram to a partition of instances. For instance, graphical analysis of a dendrogram is performed by mapping it into a partition and then plotting boxplots of each feature or principal component (Kassambara, 2017;Galili, 2015;Seo and Shneiderman, 2002). Similarly, in order to evaluate the performance of a dendrogram, it is mapped into a partition, which is then evaluated according to measures such as non-overlap (Datta and Datta, 2003), average distance between means (Datta and Datta, 2003), average distance (Datta and Datta, 2003), adjusted Rand index (Hubert and Arabie, 1985), V-measure (Rosenberg and Hirschberg, 2007), Silhouette coefficient (Rousseeuw, 1987), Calinski-Harabasz index (Caliński and Harabasz, 1974), and Figure of Merit (Yeung et al., 2001). Similarly, feature importance is computed by classifying which partition element each instance belongs to based on the features (Ismaili et al., 2014;Badih et al., 2019).

Experiments
In this section, we compare our proposal for graphical analysis, feature importance and clustering loss to other methods based on partition clustering. In order to apply the latter methods, partitions are generated by cutting the dendrogram at varying heights. Subsection 5.1 compares evolutionary dendrograms to boxplots grouped by clusters. Section 5.2 compares PFIS to the importance measure obtained by applying a random forests to explain the cluster labels based on the features. Section 5.3 compares our cross-validated loss to FOM, a statistic that evaluates the predictive power of the clusters in explaining each of the features.

Evolutionary dendrograms vs. grouped boxplots
Boxplots are a common way of visualizing how a feature is segmented by a dendrogram. First, a partition is obtained by cutting the dendrogram at a given height. Next, a boxplot is drawn for each cluster in the partition. By successively cutting the dendrogram at different heights, one can fully visualize how the feature is segmented. However, much of the information in the dendrogram is lost in this procedure. Figure 6 compares such segmented boxplots to evolutionary dendrograms using the US-Arrests dataset. First, a dendrogram is obtained using the McQuitty method. Next, segmented boxplots and the evolutionary dendrogram are obtained for "murder rate". Figure 6a presents boxplots grouped by cluster when 2, 3 and 4 clusters are used. Using these plots, one can see that the feature is well segmented for the chosen number of clusters. However, although boxplots bring measures of centrality and dispersion, they lose information about the internal structure of each cluster. In particular, one cannot find in the boxplots which instances belong to each cluster.
In contrast Figure 6b displays the evolutionary dendrogram obtained for the same feature. By cutting the dendrogram at the root, one obtains the main top (B: green) and bottom (A: light blue) clusters. By looking at the color dispersion in both clusters, it is possible to conclude that the top cluster has a larger variance than the bottom cluster. Furthermore, by looking at the next internal nodes, one can observe that while the top cluster can be further segmented into dark green (F) and light green (E) sub-clusters, the bottom cluster can be segmented into purple (C) and dark blue (D) sub-clusters.
The following subsection illustrates the performance of our feature importance score.

PFIS vs. random forest importance scores
This subsection compares PFIS, presented in subsection 3.3, to a common alternative for feature importance in a dendrogram. According to the alternative, the dendrogram is cut at a given heigth into k clusters. Next, these clusters are taken as labels for a random forest classifier (Breiman, 2001) based on the remaining features. Finally, the importance scores for this random forest are taken as also representing the importance of the features in the dendrogram. This method is compared to PFIS through simulated data. Let X i , j be the j -th simulated feature value of the i -th instance, where 1 ≤ j ≤ 6 and 1 ≤ i ≤ 2 8 . The data, X , is generated recursively according to a tree procedure described in Algorithm 2. In this algorithm, θ i , j ,k−1 represents an ancestor of θ i , j ,k and of θ 2 k−1 +i , j ,k . Also, z i , j ,k represents the noise that is added when generating a descendant. Observe that z i , j ,k is of the order of magnitude of (σ j ) k . That is, the larger the value of σ j , the more noise is added to the leaf descendants proportionally to the internal nodes of the tree. As a result, the larger the value of σ j , the less the structure of the tree is preserved by feature j . Since in the simulation σ j = 2 j −3 , one expects that the feature importance in the adjusted dendrogram should decrease from j = 1 to 6.

algorithm 2 Simulated data
Output: X i , j , the simulated data.
1: Let σ = (2 −2 , 2 −1 , 2 0 , 2 1 , 2 2 , 2 3 ). 2: Let θ 1, j ,0 = 0, for 1 ≤ j ≤ 6. Let i 1 = i and i 2 = 2 k−1 + i 6: end for 9: end for 10: Let X i , j = θ i , j ,7 , for 1 ≤ i ≤ 2 8 and 1 ≤ j ≤ 6. Figure 7 shows the random forest and PFIS scores applied to the data described above. A dendrogram was obtained through Ward's method. Also, the random forest score was obtained by splitting the dendrogram into k = 3 groups. This is the optimal number of clusters according to the NbClust majority rule (Charrad et al., 2014). The right panel presents σ −1 j , a measure of how much the tree structure is preserved by each feature. The middle panel presents PFIS, which qualitatively follows closely the right panel. The left panel presents the random forest (RF) score. Contrary to PFIS, this score does not preserve the ordering of the features given by σ −1 j , which indicates that PFIS is more appropriate. The next subsection evaluates the performance of our proposed method for evaluating clustering methods.

Cross-validated Loss vs. FOM
For each experiment we will use different combinations of clustering methods and linkages in order to assess the quality and performance of each methodology. The combinations of methods and linkages are listed below: Features Importance score Figure 7: Measures of feature importance: (left) random forest, (middle) PFIS, (right) σ −1 j , a gold standard that measures how much the tree structure that is used to generate the data is preserved by each feature. Our score preserves the ordering given by σ −1 j , while RF does not. This section evaluates the performance of cross-validated loss (CV L) by comparing it to Figure of Merit (FOM, Yeung et al. (2001)). The FOM score is computed in three steps. First, for each feature, a dendrogram is adjusted holding out the feature from the data. Next, by cutting each dendrogram at a given height, it is transformed into a partition. Finally, the within-cluster similarity is computed for each held-out feature using its respective partition. The FOM score corresponds to the average of these similarities.
We compare CVL and FOM using simulated datasets and UCI datasets 3 that are available on R. The chosen UCI datasets are summarized in Table 1. We also use a simulated dataset with 250 instances such that the label is Y i ∼ Bernoulli(0.5) and the features are (X 1 , X 2 )|Y ∼ N 2 ( 2Y 2Y , I ). Note that although clustering methods use only features, each dataset also has a label.
In order to compare CVL and FOM, we compare these methods to a gold-standard which Not applicable uses the labels in the datasets. The main idea is that the dendrogram is treated as a classifier for the label and the F1 score is the gold-standard for the dendrogram's performance. Such a classifier is obtained by cutting the dendrogram at an appropriate height so that it becomes a partition with size equal to the number of labels. Next, each cluster in the partition is associated to a single label that maximizes accuracy. Each instance is labeled equally as the partition to which it belongs. The gold-standard for the dendrogram's performance is the F1 score based on its assigned labels. Based on the above information, it is possible to describe the experiment that compares CVL to FOM. For each dataset, we performed clustering using all of the the methods in Table 2. Each of the 11 clustering methods was applied using the euclidean, manhattan and canberra distances. As a result, 33 dendrograms were obtained for each dataset. For each dendrogram, the CVL, FOM and gold-standard F1 scores were calculated. Since FOM requires a pre-defined number of clusters, we calculated this score using the correct number of labels. Since the correct number of clusters is generally unavailable, this procedure gives an advantage to FOM. Table 3 shows, for each dataset, the Spearman correlation between CV L and F 1 and between F OM and F 1 among the clustering methods that were used. Recall that, while CVL and FOM measure how bad is a given clustering, F 1 is a gold-standard that measures whether the clustering is good. Therefore, a negative correlation between a loss and F1 indicates that the measures are in agreement. One can observe in Table 3 that, while the Spearman correlation between CVL and F1 is negative for all but one dataset, it is positive between FOM and F1 except for two datasets. Furthermore, in 5 out of the 8 datasets, CVL has a better agreement with F1 than FOM. These results provide evidence that CVL adequately describes the performance of clustering methods.