Ranked Adjusted Rand: integrating distance and partition information in a measure of clustering agreement

Abstract

Background: Biological information is commonly used to cluster or classify entities of interest such as genes, conditions, species or samples. However, different sources of data can be used to classify the same set of entities and methods allowing the comparison of the performance of two data sources or the determination of how well a given classification agrees with another are frequently needed, especially in the absence of a universally accepted "gold standard" classification.

Results: Here, we describe a novel measure--the Ranked Adjusted Rand (RAR) index. RAR differs from existing methods by evaluating the extent of agreement between any two groupings, taking into account the intercluster distances. This characteristic is relevant to evaluate cases of pairs of entities grouped in the same cluster by one method and separated by another. The latter method may assign them to close neighbour clusters or, on the contrary, to clusters that are far apart from each other. RAR is applicable even when intercluster distance information is absent for both or one of the groupings. In the first case, RAR is equal to its predecessor, Adjusted Rand (HA) index. Artificially designed clusterings were used to demonstrate situations in which only RAR was able to detect differences in the grouping patterns. A study with larger simulated clusterings ensured that in realistic conditions, RAR is effectively integrating distance and partition information. The new method was applied to biological examples to compare 1) two microbial typing methods, 2) two gene regulatory network distances and 3) microarray gene expression data with pathway information. In the first application, one of the methods does not provide intercluster distances while the other originated a hierarchical clustering. RAR proved to be more sensitive than HA in the choice of a threshold for defining clusters in the hierarchical method that maximizes agreement between the results of both methods.

Conclusion: RAR has its major advantage in combining cluster distance and partition information, while the previously available methods used only the latter. RAR should be used in the research problems were HA was previously used, because in the absence of inter cluster distance effects it is an equally effective measure, and in the presence of distance effects it is a more complete one.

Figure 1

Small clusterings example of RAR's unique properties. Clustering A divides 9 points (numbered circles) in three clusters identified by rectangles. By splitting the {1, 2, 3, 4} cluster, the clusterings B, C and D were formed. One of the child clusters kept the same location. The second child cluster moved away from the original location. In B and C, the second child cluster has only one entity, while in D it has three. In B and D the two split clusters are nearest neighbours, while in C they are maximally separated. The two dimensional coordinates of the points in the figure were used to compute average distances between clusters and to calculate RAR and other clustering comparison measures. The results are presented in Table 4.

Figure 2

Ranked Adjusted Rand (RAR), Adjusted Rand (HA) and Wallace (W) indices for the comparison of emm type with PFGE clusterings using different Dice dissimilarity thresholds. Dice dissimilarity is in a 0–100 scale. The plot in the top indicates the number of PFGE clusters originated with the respective threshold, while the number of emm types is always 12. The minimum threshold studied, 1, does not originate 325 clusters because there are sets of isolates whose PFGE band patterns have a Dice dissimilarity of 0. W(emm-PFGE) is the probability that a pair of isolates is in the same PFGE cluster knowing that they have the same emm type. Analogously, W(PFGE-emm) is the probability that a pair of isolates has the same emm type knowing that they are in the same PFGE cluster. HA reflects the evolution of both Wallace indices. The plateau of maximum HA, between the thresholds of 28 and 41, is a region of compromise where both Wallace indices are high. The curve of RAR values shows a more complex behaviour, with a plateau of maximum values between the thresholds of 20 and 29, and a significant decrease between 29 and 41, where HA is nearly constant.

Figure 3

Ranked Mismatch Matrix (RMM) composition at different Dice dissimilarity thresholds for PFGE clustering. The RMMs for the comparison of emm type with PFGE clusterings have dimensions p × 2, where p depends on the number of PFGE clusters and the two columns correspond to isolate pairs with the same or with different emm type. The PFGE intercluster distance rank is represented in the horizontal axis. The isolate pairs with the same emm type are represented with full lines while for pairs with different emm type a dashed line was used. The frequencies plotted in the vertical axis are relative, meaning that the content of each RMM element was divided by the sum of all RMM elements. It corresponds to the fraction of isolate pairs contributing for the respective RMM element. RMM composition was studied at three different thresholds (T = 21, 29 and 41) because, 21 is an optimal threshold for RAR but not for HA, 29 is an optimal threshold for both measures and 41 is a slightly sub-optimal threshold for HA (it is at the end of the maximal plateau of HA in Figure 3) and a bad threshold for RAR. The frequency distributions of isolate pairs with the same emm type are similar for the three thresholds. This is not the case for isolate pairs with different emm type. Here, as the threshold increases, the frequency peaks become larger and occur at lower cluster distance ranks, contributing in this way for a weaker agreement.