Obtaining synthetic indications and sorting relevant structures from complex hierarchical clusters of multivariate data

The first step appears to be the simplest one, since it can be achieved by means of classical, well known techniques. Actually, the choice of the most suitable method turns out to be very helpful in the definition of the groups. When the definition of a number of families is the goal of the clustering, indeed, classical flat clustering could be directly applied. Unfortunately, it is mandatory to define a priori some parameters, such as the number of families, or the distance range among the centroids of the resulting sets, etc. This is usually possible when the problem under scrutiny is well known, or simple, e.g., the partition of a region into districts (Kalantari, 2013). When these data are not known, and hierarchical clustering must be therefore adopted, some constraints may sometimes apply to obtain simpler results: for example, in systematic biology, the number of branching occurring in the dendrogram is fixed (Michener et al., 1970), and therefore it is immediate to retrieve the required information even in large sets of data, e.g., the families within the Araneae order, in the Arachnida class of the Arthropoda phylum which belongs to the kingdom of all Animals (https://​wsc.​nmbe.​ch/​families).

When experimental results are analyzed, usually no constraint applies a priori, and moreover data are affected by measurement uncertainty. For this reason, the suggested clustering technique, whose mathematical details are duly described in Vignati et al. (2018), is based on the so-called “weighted asymmetric \(\infty \)-pseudometric” \(d_{\infty }^{*}\), which provides a unique clustering, regardless of the data scaling and experimental uncertainty (Vignati et al., 2018). This metrics, specifically designed for quantitative data, is defined as where P_i, Q_i are the values of the i-th variable making up the multivariate data, and w_i the corresponding value of a weight. The fractions are computed by means of a limit operator to account for the possibility of zero-value variables.

This method, termed “dynamic”, is an agglomerative, bottom-up technique, based on a similarity criterion which disengages the results from the data scaling. This possibility comes from a proper metrics definition, which is automatically and dynamically updated during the clustering procedure. To detect the similarity between the configurations, an area of influence is identified around each configuration, termed “bounding box”, whose size is dynamically increased during the clustering procedure: if two bounding boxes interact with each other, then the two configurations are merged together to form a new cluster, which is represented by the centroid computed on all its elements. With the adopted \(d_{\infty }^{*}\) metrics, each side of the bounding box is proportional to the coordinate value of the central element along the considered direction, i.e., a percentage of it, and it will be therefore termed “percentage distance”. The interaction between the bounding boxes of two configurations occurs when one configuration is included in the bounding box built around the other one. Details on the novel proximity measure which substitutes classical metrics, on the algorithm computational cost and on its geometric meaning are duly discussed in previous papers by the Authors Vignati et al. (2018), Niro et al. (2016), and Fustinoni et al. (2019). Figure 1 shows two possible implementation strategies for the described clustering algorithm: the first one, i.e., the geometric approach, is more straighforward and flexible, albeit less efficient. The second one, which introduces the \(d_{\infty }^{*}\) pseudometric, disengaged the procedure from its geometric interpretation, and therefore it reduces its computational cost, at the expense of a lower flexibility.

It is mandatory to stress that the proximity measure can be, in general, quantified by any metrics, since the synthesis of the results applies directly to the resulting dendrogram. However, due to the geometric interpretation of the described pseudometric, the implementation of the procedure is more straightforward and results are more robust when \(d_{\infty }^{*}\) is adopted.

A toy problem is now defined to understand the novel procedure described in the following. The configurations are represented by a generic set of 58 points, depicted in Fig. 2, identified by two coordinates, albeit the method can be generalized to spaces of any dimension. Similarly, since the adopted dynamic clustering does not depend on the data scaling, the numerical values are not relevant. Each coordinate represents the outcome of an experiment, after a proper averaging and uncertainty quantification. Experimental results depend on a number of controlled, i.e., independent variables and on a set of parameters: in the proposed procedure, one value of the controlled variable is considered, and the effect of the parameters on the outcomes is observed. In general, any kind of parameter, not only geometric ones, is valid: in the following example, the parameters are assumed to be Therefore, when experiments are carried out in, e.g., configuration 7, one has s = on, p = cyan, d = east, f = square.

The results of the clustering is usually represented by means of a dendrogram. The dendrogram ordinate represents the increasing size of the bounding box, necessary to cluster the diverse configurations reported in abscissa. The ordinate starts from zero (for fully-identical configurations) and it increases to the maximum value (for the least similar configurations), which depends on each case.

Figure 3 depicts an the dendrogram resulting from the dynamic clustering of the points of the toy-problem. To fit in the page, it is rotated of 90^∘ counterclockwise: for this reason, the ordinate, representing the percentage distance, is the horizontal axis. Similarly, all the original configurations are listed along the vertical axis, and represent experimental outcomes. The dendrogram in Fig. 3, as well as all other results presented in this paper and in Ref. Vignati et al. (2018), is generated by means of a code developed by the Authors and implemented in MATLAB (MATLAB and Statistics Toolbox Release, 2012b). For all the details on the clustering algorithm based on the novel \(d_{\infty }^{*}\) proximity measure, its implementation and discussion, the reader is addressed to Ref. Vignati et al. (2018).

The second step processes the results of the clustering and provides a first indication of the possible groups. Since this tool summarizes the hierarchical clustering, it will be termed “reduced” clustering.

These groups are defines as groups of configurations which share a “reasonable” level of similarity. For this reason, a threshold value τ is selected, which allows to partition the hierarchical clustering: the configurations with a percentage distance lesser than or equal to the threshold are merged together to form groups. The solid vertical line in Fig. 3 represents an example of possible threshold, i.e., the percentage distance of 20% among the configurations, which summarizes in one parameter all the effects of the multivariate data. Therefore, all the configurations that belong to the same group have a reciprocal distance smaller than 20% (in the example, or the selected threshold in general), and they are indeed linked by a branch intersecting the solid line.

When analyzing multivariate data, the relevance of each outcome may be different, to the purposes of the considered investigation. This is particularly true when experimental data are considered, since specific physical quantities are associated to the different directions in the multivariate space.

By means of the adopted proximity measure \(d_{\infty }^{*}\), the assignation of different relevance to each direction is straightforward. The aspect ratio AR of the bounding boxes must be simply modified: if the bounding boxes are enlarged in one or more directions, the clustering becomes more inclusive and therefore the physical quantity identified by the considered direction in the multivariate space is less influential on the partition into groups. Conversely, if the bounding boxes aspect ratio is shrunk along one or more directions, it becomes less likely for configurations to merge, and therefore the clustering procedure becomes more selective with respect to the considered physical quantity (or outcome). Clearly, a unit-value AR corresponds to the base case, where all the physical quantities have the same relevance and, therefore, all directions in the multivariate space are similarly accounted in the computation of \(d_{\infty }^{*}\).

The aspect ratio affects the size of the bounding boxes, and therefore the percentage distance among the configurations. For this reason, the threshold value may be modified with respect to the unit-value case, to account for the different selectivity of the bounding boxes. Figure 4 depicts the dendrogram resulting from the clustering performed with AR = 5 (along one direction in the multivariate space). Since the aspect ratio is larger than one, at each step of the clustering the bounding boxes are larger than the corresponding ones adopted for the standard clustering (resulting in the dendrogram in Fig. 3), and therefore the configurations are merged when their percentage distance (still computed by means of \(d_{\infty }^{*}\)) is lower. The solid line in Fig. 4, indeed, is still in correspondence of a threshold value of 20% for comparison with Fig. 3, but it intersects only three branches, and therefore only three groups are identified, whereas seventeen were obtained by cutting the dendrogram in Fig. 3.

It is mandatory to specify that there is no way to decide a priori the optimal combination of τ and AR, because it depends on the specific problem and goal of the investigation. However, the difference between the two cases (in Figs. 3 and 4) is clear, and therefore special care must be paid if different aspect ratios or data treatments are adopted (Langfelder et al., 2008), since only τ = 1 corresponds to a physical situation, where all directions in the multivariate space are equally weighted. To make the results more robust, a preliminary analysis is suggested, to investigate the effect of different bounding box aspect ratios and thresholds on the clustering of a specific dataset, in terms of, e.g., number of groups, selectivity, robustness, etc. Eventually, some indications may be retrieved by the application of the second tool (presented and discussed in Section 3), to recursively correct the values of AR and τ.

The described cluster reduction results in some groups of configurations, in analogy with flat clustering. However, the proposed procedure presents three main advantages:

After the reduction of the hierarchical clustering described in Section 2, groups of configurations are identified, which share the same internal similarity. Each group, therefore, represents a so-called clique (Luce and Perry, 1949), the set of vertexes of a complete, undirected graph (Thulasiraman et al., 2016). For this reason, the problem of obtaining synthetic indications from hierarchical clustering can be approached in accordance with graph theory. In this perspective, the cut dendrograms resulting from the cluster reduction are disconnected graphs: each element is connected to all those elements, and those only, which belong to the same group. The graphs obtained after the cluster reduction are depicted in Fig. 5 for the two aspect ratio values of 1 and 5, showing the resulting 17 and 3 cliques, respectively.

For every reduced clustering, the so-called “adjacency matrix” Λ (of size n × n) is then computed, that is, a table with each row and column identifying one of the n configurations. If the two configurations associated to the j − th row and k − th column belong to the same group, then the cell value, hereafter termed “similarity coefficient” λ_jk, is 1, otherwise it is zero (Biggs, 1993). In the present work, a modified definition is adopted, since λ_jj = 1, whereas it is commonly 0 or ≤ 2 in undirected graphs (for simple and multigraphs, respectively). Therefore, all the adjacency matrices are symmetric and have unit values along the main diagonal. For a given dataset, Λ depends on both the bounding box aspect ratio and on the threshold value, for an overall number of possible adjacency matrices of AR × τ. Moreover, experimental investigations are usually designed with one or more quantities varying over multiple levels, i.e., the controlled or independent variables. Each set of points in the multivariate space, therefore, represents the outcomes at a given combination of independent variables. For this reason, Λ depends also on the value of the controlled variables. Unexpectedly, thanks to the following procedure, this large number of available adjacency matrices is the key to sort the most relevant information from the clustering. On the first hand, indeed, some sets, termed “families”, are retrieved, containing configurations which tend to cluster together even for different values of AR and τ (disengaging the results from the arbitrary choice of the bounding box aspect ratio and threshold) or of the controlled variables (pointing to a physical and thus meaningful robustness of the results). On the second hand, it automatically identifies the parameters, e.g., geometrical or operational, identifying each configuration which mostly affect the clustering. This second result, in particular, is not usually permitted by simple cluster analysis, since it only retrieves which configurations are similar, but not why or to what extent. To achieve this result, a procedure is devised from the so-called weighted correlation network analysis and fuzzy clustering (Ross, 2004). In this approach, adjacency matrix elements may assume other values, in addition to 1 and 0, and therefore they do not simply identify a logical correlation, but a robustness of the link between the elements: the larger the value of a cell, the more robust or persistent the similarity between the two associated configurations. A number of fuzzy clustering algorithms are available (Bezdek, 1981; Dunn, 1973; Gustafson & Kessel, 1979), which require to perform a whole new clustering. To avoid this additional, memory consuming step, different adjacency matrices resulting from the reduced clustering step (for different AR or τ or operating conditions) are added. The result is a single matrix Λ^agg, of size n × n, termed “aggregated”. Boolean adjacency matrices are therefore added to build non-boolean aggregated matrices, whose values are still positive integers, but depart from 0 or 1. The analysis of aggregated matrices, therefore, allows to retrieve not only a boolean information, but a spectrum of similarities, ranging from 0 (none) to the diagonal values (used to set the reference of the maximum similarity). This approach is therefore not boolean, but fuzzy.

Different aggregated matrices can be defined. If the hierarchical clustering of a given dataset is performed with a constant bounding box aspect ratio, only the threshold affects the resulting adjacency matrices, and therefore their sum results in the “threshold-aggregated” matrix Λ^τ. Similarly, if τ and the operating conditions are kept constant, only the bounding boxes aspect ratio effect is observed on the clustering, and therefore the resulting matrix Λ^AR is termed “aspect ratio-aggregated”, and its elements \(\lambda ^{AR}_{jk}\) range from 0 to the number of explored aspect ratios. In the same way, both clustering parameters, i.e., AR and τ can be fixed, and hierarchical clustering applied to a number of dataset, representing outcomes of experiments carried out in different operating conditions: the matrix addition retrieves an “experimental-aggregated” matrix Λ^e, with \(\lambda ^{e}_{jk}\) ranging from zero to the number of levels for the considered controlled variable. It is remarkable that only the last two operations are meaningful, since τ does not influence the clustering, and it is not linked to the physics of the investigated problem. Λ^τ, therefore, should be computed and studied only when a priori considerations on reasonable values of the threshold are not available, or when the range of possible τ is too wide. Eventually, combined effects may be considered, by, e.g., adding all Λ^e obtained for different aspect ratios or threshold, into the so-called “overall-aggregated” Λ^O.

As an example of the described technique, experiments are carried out in eight operating conditions. For each of the eight levels of the controlled variable, the 58 configurations adopted to compute the dendrogram in Fig. 3 are tested, and therefore eight dendrograms are built, by means of the dynamic procedure described in Vignati et al. (2018) and with AR = 1. The obtained hierarchical clusters are then reduced in accordance with the method described in Section 2, adjacency matrices are computed and summed, resulting in Λ^e, which is displayed in Fig. 6. Albeit different threshold values were tested, too, in the following only the cases with τ = 20% will be shown, for brevity. The reading of adjacency and aggregated matrices is clearly not friendly, due to their large size; however, the computation and subsequent use of all matrices does not require an active role of the user, and therefore this limitation is naturally overcome by the automation of the method. Therefore, all the displayed matrices in this paper are for the purpose of a better understanding of the procedure steps.

During the experiments performed to compute the matrix in Fig. 6, the controlled variable is varied over 8 levels, and therefore \(\lambda _{jk}^{e}\) range from 0 to 8. The first case implies no similarity at all between the j − th and the k − th configurations, like between, e.g., 26 and 40. On the contrary, the second occurrence points to the maximum similarity between configurations j and k, i.e., the two configurations cluster for all the considered levels of the controlled variable like, e.g., 4, 16 and 44. These three configurations, therefore, make up a “family”, i.e., the smallest group of configurations which result in similar outcomes (that is, which cluster together) even in different operating conditions and regardless of the selectivity of the procedure (which depends on AR and τ). All other values of \(\lambda _{jk}^{e}\) provide good indications, since they allow to draw considerations on the distribution of data, whether, e.g., there are families of configurations which cluster together almost always or almost never. The pair 41 and 35, for example, belong to the same group resulting from the reduction of the dendrogram reported in Fig. 3, but \(\lambda _{35, 41}^{e} = 6\) instead of 8, implying that, in two operating conditions, the two configurations do not result in near outcomes, an therefore that their similarity is not due to stable, physical reasons.

Moreover, if in an aggregated table there were too many or too few occurrences of the minimum or maximum value (outside of the main diagonal, which is maximum by definition), the user could reconsider the selected values of AR or τ, being the clustering or its reduction too selective or inclusive.

The identification of the families can be speeded up and made error-proof thanks to a proper permutation of the rows (and, similarly, of the columns, to preserve the symmetry) of the aggregated matrices. The order of rows and columns within each adjacency or aggregated matrix is indeed arbitrary, since it represents a run order associated to each configuration, and therefore it can be modified. All possible n! permutations can be applied, preserving the meaning of the adjacency matrices, but some highlight a specific structure governing the values of the similarity coefficients, and therefore points to a possible criterion governing the experimental outcomes. Figure 7 shows a permuted version of the aggregated matrix depicted in Fig. 6, with similar rows sorted together. If any two or more rows are equal, they surely belong to the same family. It is worth stressing that this is ensured by the use of modified the adjacency matrices, with unit-values along the main diagonal. Equal groups of rows can be immediately spotted, when the number of configurations is low, like in the example. However, a large number of algorithms and tools are available to detect groups of equal rows and, therefore, of families.

The configurations are defined by means of a collection of parameters, which are usually well defined and quantified, in particular when they represent experimental features. Some parameters are, in general, more relevant in determining which configurations belong to the same groups or families. In the following, three indicators are defined and adopted, to determine the parameters hierarchy of relevance.

For the first part of the procedure, i.e., the hierarchical clustering of experimental data, some cost estimations are available, as presented in Section 1 (Sokal and Sneath, 1963; Johnson & Wichern, 1990; Anderson, 1984; Bouguettaya et al., 2015; Day & Edelsbrunner, 1984; Hruschka et al., 2009). For a dataset of n data, indeed, the computational cost for the hierarchical clustering is the same as classical ones, i.e., n², when the novel, \(d_{\infty }^{*}\) proximity measure is adopted. Conversely, it increases by a factor n if the geometric approach, based on the bounding boxes construction, is chosen. The refore, the latter is not convenient, since it results in the same dendrogram, but its definition is useful since:

The effort required by the second part of the procedure, i.e., the post-processing of the dendrograms, depends on the goal of the investigation. Each dataset, indeed, may result in different clusters, depending on AR, and therefore the computational cost of the clustering should be multiplied by the number of explored aspect ratios, yielding AR ⋅ n² operations. Albeit the increased number of operations due to the different AR values is performed during the first part of the work, i.e., the dendrogram derivation, its effect falls back on the second part, since the investigation of the aspect ratios effect makes sense only if a post-processing applies to the clustering.

The AR dendrograms are then partitioned at the level τ, retrieving the “reduced” clustering, i.e., a set of groups summarized in the boolean “adjacency matrices” Λ. The number of obtained matrices is not exactly τ ⋅ AR, since the number of investigated values of τ depends on AR, as discussed in Section 2.2: the larger the boxes, indeed, the lower the upper value of τ, yielding a computational cost fpr the definition of Λ of \({\sum }_{AR} (n^{2} \cdot \tau _{AR})\), where τ_AR is the number of investigated threshold values for a given aspect ratio.

To make the resulting families of configurations robust against the numerical parameters AR and τ, the aggregated matrices are computed as sum of adjacency matrices, retrieving as many Λ^τ as the investigated aspect ratios (from the sum of all Λ related to the partitioning of dendrograms built with the same aspect ratio), and a number of Λ^AR, similarly defined, depending on the number of values assumed by τ in the range common to all the clustering computed with different AR. To compute Λ^AR, therefore, it is mandatory that the investigated values of τ are the same for all the dendrograms, at least in the common range, albeit its upper value depends on AR. The computational effort for these operations is added to the previous one, and it depends on the actual enforcement. If the algorithm is implemented in a high-level language, which is equipped with libraries for matrix algebra, the cost is lower than n². However, the amount of dataset elements n can be arbitrarily large, whereas only a reasonable, much lower number of AR and τ levels are commonly investigated. For this reason, they do not significantly affect the magnitude order of the computational cost, which remains controlled by n².

Λ^τ and Λ^AR point to families of configurations which aggregate with each other regardless of the procedure selectivity (controlled by τ) or of the relevance of each variable in the multivariate space, which depends on the application (and is quantified by AR). Therefore, these aggregated matrices indicate the robustness of the found families against numerical parameters introduced by the mathematical enforcement of the algorithm. On the contrary, a different approach is devised to investigate the stability of the resulting families, if the initial dataset may vary. Indeed, if experimental results are obtained in different operating conditions, different dataset must be considered, and the resulting dendrograms are increased by a factor equal to the number of levels for the considered controlled variables, albeit this does not depend on the algorithm efficiency, but, clearly, only on the number of the experimental data available to the user, as for n. However, also in this case, a number of adjacency matrices can be computed, in the number of the values of the controlled variables times the aspect ratios selected during the clustering (assuming AR values fixed). The latter are added, retrieving the experimental-aggregated Λ^e, at a cost which depends on the actual algebraic enforcement of the operation, but which is, in general, lower than n².

Λ^e not only points to stable families of configurations, but also determines a hierarchy of relevance among the X parameters defining the different configurations, i.e., which ones are more influential on the retrieved families, thanks to the novel “(modified) relevance coefficients”. Their calculation requires to permute rows and columns of the matrices Λ^e: if only the direct effect of the parameters must be accounted, X permutations are required, while they become 2^X − 1 if second-order effects, due to the parameters interactions, are of interest, accounting for all the possible combinations among them. For arch Λ^e, therefore, the 2^X permutations are first performed, and then the relative coefficients are computed and ranked. The cost for this operation is added to the previous ones; however, unlike for AR and τ, the number of permutations is not necessarily negligible, if compared to n². X and n are, indeed, independent, with X ≤ n by definition, and X << n in experimental investigations; however the exponential function (such as 2^X) grows faster than a power-law (like n²). For this reason, the cost of the latter operation could be comparable to n², even for X smaller than n, but only if second-order effects are to be considered, and also in this case the overall effort would not exceed the order of n².