{'fraction_non_alphanumeric': 0.041719183261910764, 'fraction_numerical': 0.011595664229896647, 'mean_word_length': 4.312688316036157, '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}}
Pairwise Adjusted Mutual Information

A well-known metric for quantifying the similarity between two clusterings is the adjusted mutual information. Compared to mutual information, a corrective term based on random permutations of the labels is introduced, preventing two clusterings being similar by chance. Unfortunately, this adjustment makes the metric computationally expensive. In this paper, we propose a novel adjustment based on {pairwise} label permutations instead of full label permutations. Specifically, we consider permutations where only two samples, selected uniformly at random, exchange their labels. We show that the corresponding adjusted metric, which can be expressed explicitly, behaves similarly to the standard adjusted mutual information for assessing the quality of a clustering, while having a much lower time complexity. Both metrics are compared in terms of quality and performance on experiments based on synthetic and real data.


Introduction
A well-known metric for quantifying the similarity between two clusterings of the same data is the adjusted mutual information [5,10]. Compared to mutual information, this metric is adjusted against chance, meaning that the similarity cannot be due to randomness but only to the structure of the dataset, appearing in both clusterings. This is the reason why this metric is widely used in unsupervised learning, see [13,9,8,12,11] for various applications.
The standard way of adjusting mutual information against chance is through random label permutations of one of the clusterings [10]. Unfortunately, this adjustment makes the metric computationally expensive. Specifically, the time complexity of the metric is in O(max(k, l)n), where k, l are the numbers of clusters in each clustering and n is the number of samples [6]. As a comparison, the time complexity of mutual information is equal to O(kl) given the contingency matrix of the clusterings, i.e., the matrix counting the number of samples in each cluster pair. The additional computational effort required by adjustment is significant as the number of samples n is typically much larger than the numbers of clusters k, l.
In this paper, we propose a novel adjustment based on pairwise permutations. That is, we consider permutations where only two samples, selected uniformly at random, exchange their labels. We show that the corresponding adjusted metric, we refer to as pairwise adjusted mutual information, is as efficient as adjusted mutual information for assessing the quality of a clustering, with a much lower time complexity. In particular, the time complexity is the same as that of mutual information. The gain in complexity is significant, as the computation time is now independent of the number of samples n, given the contingency matrix.
The rest of the paper is organized as follows. We first provide the definition and key properties of adjusted mutual information in the general setting of information theory. We then introduce mutual information with pairwise adjustement and explain why the exact same properties are satisfied by this new notion of adjusted mutual information. The application of both notions of adjustment to clustering, including the explicit expressions of the corresponding metrics, is presented in section 4. Experiments on both synthetic and real data are presented in section 5. Section 6 concludes the paper.

Adjusted mutual information
Let P be the uniform probability measure on Ω = {1, . . . , n}, for some positive integer n. Let X, Y be random variables on the probability space (Ω, P ). Without any loss of generality, we assume that X and Y are mapping from Ω to sets consisting of consecutive integers, starting from 1. Denoting by H the entropy, the mutual information between X and Y is defined by [1]: This is the information shared by X and Y , which is equal to 0 if X and Y are independent. A distance between X and Y can then be defined by: This distance, known as the variation of information, is a metric in the quotient space of random variables under the equivalence relation X ∼ Y if and only if there is some bijection ϕ such that X = ϕ(Y ) [4].
Adjusted mutual information. The adjusted mutual information between X and Y , corresponding to the mutual information between X and Y adjusted against chance, is defined by: where Y σ is the random variable Y • σ, for any permutation σ of {1, . . . , n}, and the expectation is taken over all permutations σ, chosen uniformly at random. Remark 1 (Normalization). It is frequent to also normalize adjusted mutual information, so as to get a score between 0 and 1 [10,6]. In this paper, we only focus on the adjustment step. Note that normalization can be equally applied to both considered notions of adjustment and thus be studied separately.
We have the equivalent definition: This equivalence follows from Proposition 1 and the fact that the definition is symmetric in X and Y . All proofs are deferred to the appendix. Proposition 1. We have for any random variables X and Y : In view of (3), we expect ∆I(X, Y ) to be positive if X and Y share information, as X is expected to be closer to Y (for the distance d) than to Y σ , a randomized version of Y . There are specific cases where ∆I(X, Y ) = 0, as stated in Proposition 2; these cases will be interpreted in terms of clustering in section 4. Proposition 2. We have ∆I(X, Y ) = 0 whenever Y (or X, by symmetry) is constant or equal to some permutation of {1, . . . , n}.
Adjusted entropy. Observing that H(X) = I(X, X), we define similarly the adjusted entropy of X by: By (1), we get: Since d is a metric, this shows that the adjusted entropy of X is non-negative. Proposition 3. We have ∆H(X) = 0 if and only if X is constant or equal to some permutation of {1, . . . , n}.
Proposition 3 characterizes random variables with zero adjusted entropy. Again, this result will be interpreted in terms of clustering in section 4.

Pairwise adjustment
In this section, we introduce pairwise adjusted mutual information. The definition is the same as adjusted mutual information, except that the permutation σ is now restricted to the set of pairwise permutations. Specifically, we consider permutations σ for which there exists i, j ∈ {1, . . . , n} such that σ(i) = j and σ(j) = i, whereas σ(t) = t for all t = i, j. We consider the set of such permutations σ where the samples i, j are drawn uniformly at random in the set {1, . . . , n}. We denote by σ p such a random permutation. Observe that σ p is the identity with probability 1/n (the probability that i = j).
Pairwise adjusted mutual information. We define the pairwise adjusted mutual information as: This is exactly the same definition as the adjusted mutual information, except for the considered permutations σ p . It can be readily verified that the same properties apply, with the exact same proofs, a key property being that the random permutations σ p and σ p −1 have the same distributions. In particular, we have the analogue of (3): Moreover, ∆ p I(X, Y ) = 0 whenever X or Y is constant or equal to some permutation of {1, . . . , n}.
Pairwise adjusted entropy. We also define the pairwise adjusted entropy as: We have ∆ p H(X) ≥ 0, with equality if and only if X is constant or equal to some permutation of {1, . . . , n}. We denote by a i = |A i | the size of cluster A i , by b j = |B j | the size of cluster B j , and by n ij = |A i ∩ B j | the number of samples both in cluster A i and cluster B j , for all i = 1, . . . , k and j = 1, . . . , l. The matrix (n ij ) 1≤i≤k,1≤j≤l is known as the contingency matrix. Note that a i and b j are the respective sums of row i and column j of the contingency matrix.

Application to clustering
Adjusted mutual information. A well-known metric for assessing the similarity s(A, B) between clusterings A and B is the adjusted mutual information 1 ∆I(X, Y ) between the corresponding random variables X and Y . In words, this is the common information shared by clusterings A and B not due to randomness.
By Proposition 2, we have s(A, B) = 0 whenever clustering A (or B, by symmetry) is trivial, that is, it consists of a single cluster or of n clusters (one per sample). This is a key property, showing the interest of the adjustment.
It is known that [10]: with the notation (·) + = max(·, 0). The time complexity of this formula, which is dominated by the second term, is in O(max(k, l)n) [6]. In particular, it is linear in the number of samples n.
Interestingly, we can similarly assess the quantity of information q(A) contained in clustering A through the adjusted entropy ∆H(X) of the corresponding random variable X. This is the information contained in A not due to randomness. We have q(A) ≥ 0 and, by Proposition 3, q(A) = 0 if and only if clustering A is trivial, that is, it consists of a single cluster or of n clusters (one per sample).
Since q(A) = s(A, A), it follows from (6) that: The time complexity of this formula, also dominated by the second term, is in O(kn). Again, this complexity is linear in the number of samples n.
Pairwise adjusted mutual information. The main contribution of the paper is the following new measure of similarity s p (A, B) between clusterings A and B, based on the pairwise adjusted mutual information ∆ p I(X, Y ) between the corresponding random variables X and Y . We have an explicit expression for this similarity: Theorem 1. We have: The time complexity of this formula is in O(kl), like mutual information. It is independent of the number of samples n, given the contingency matrix. Corollary 1 shows that the time complexity reduces to O(m) the number of non-zero entries of the contingency matrix, provided the latter is stored in sparse format. Corollary 1. We have: Similarly, we can define the quantity of information q p (A) in clustering A through the pairwise adjusted entropy ∆ p H(X) of the corresponding random variable X. Again, q p (A) ≥ 0, with q p (A) = 0 if and only if clustering A is trivial.
Corollary 2. We have: Note that the time complexity of this formula in O(k). It only depends on the number of clusters k, and not on the number of samples n.

Experiments
In this section, we compare both notions of adjusted mutual information through experiments involving synthetic and real data. The experiments are run on a computer equipped with an AMD Ryzen Threadripper 1950X 16-Core Processor and 32 GB of RAM, with a a Debian 10 OS. All codes and datasets used in the experiments are available online 2 .
Synthetic data. We start with the simple case of n = 100 samples with clusters of even sizes, consisting of consecutive samples. Specifically, we consider the set of clusterings A (s) , consisting of clusters of size s (except possibly the last one), for s = 1, 2, . . . , 100. In particular, both A (1) and A (100) are trivial clusterings while A (5) consists of 20 clusters of size 5. Figure 1 gives the similarity between clusterings A (10) and A (s) with respect to s in terms of adjusted mutual information, for both notions of adjustment. We observe very close behaviors, suggesting that both notions of adjustment tend to capture the same patterns in the clusterings. Note that the maximum similarity is attained for s = 10 in both cases, as expected. The similarity is equal to 0 for s ∈ {1, 100} for both cases, in agreement with Proposition 2. We also observe local peaks at s = 20, 30, . . . , 90, which can be interpreted by the fact that clustering A (10) is a refinement of clustering A (s) for these values of s; similarly, the local peak at s = 5 may be interpreted by the fact that clustering A (5) is a refinement of clustering A (10) .  We now consider random clusterings. Specifically, we assign n samples to k clusters independently at random, according to some probability distribution p = (p 1 , . . . , p k ), which is itself drawn at random 3 . Consider three such random clusterings A, B, C (with the same parameters n and k, but different probability distributions p). We would like to know whether A is "closer" to B or to C. In particular, we are interested in testing whether both notions of adjusted mutual information give the same ordering in the sense that: We compute the average precision score (fraction of triplets A, B, C for which (8) is true) over 1 000 independent samples of A, B, C, for different values of n and k. We repeat the experiment 100 times to get the mean and standard deviation. The results are given in Table 1. We observe a very high precision score, always higher than 93%, showing that both notions of adjusted mutual information tend to give the same ordering of these random clusterings.  For the performance gain, we compare the computation times of both versions of adjusted mutual information for the similarity between clusterings A and B, where A consists of k = 10 clusters of same size and B is a random clustering, drawn as in the previous experiment. Both versions of adjusted mutual information are coded in Python, with the standard version imported from scikit-learn. Figure 2 shows the computation time when the number of samples n grows from 10 2 to 10 7 . The performance gain brought by pairwise adjustement is significant. In particular, the computation time becomes independent of the number of samples.  Real data. For real data, we consider the 79 datasets of the benchmark suite [2] 4 . We apply to each dataset each of the following clustering algorithms: We use the scikit-learn implementation of these algorithms, with the corresponding default parameters 56 . We get 10 clusterings per dataset. The quality of each clustering is assessed through the similarity with the available groundtruth labels, using adjusted mutual information with either full adjustment or pairwise adjustment. We then compute the Spearman correlation of the corresponding similarities, a value of 1 meaning the exact same ordering of the 10 clusterings with full adjustment and pairwise adjustment. The results are shown in Figure 3, together with the speed-up in computation time due to pairwise adjustment. In both cases, the 79 datasets are ordered by the number of samples, ranging from 105 to 105 600 [2].  We first observe that the correlation is very high, suggesting again that both notions of adjusted mutual information tend to provide the same results. For 65 datasets among 79, the Spearman correlation is higher than 95%. As for the computation time, we observe a significant performance gain, by one order of magnitude for the largest datasets.

Conclusion
We have proposed another way of adjusting mutual information against chance, through pairwise label permutations. The novel metric, whose explicit expression is given in Theorem 1, has a much lower complexity than the usual adjusted mutual information. Interestingly, both metrics can also be used to assess the quantity of information contained in a clustering, which the common property of being equal to 0 if and only if the clustering is trivial, as stated in Proposition 3; again, the pairwise adjusted entropy, given in Corollary 2, has a much lower complexity. Experiments on synthetic and real data show that pairwise adjusted mutual information tends to provide the same results as the usual adjusted mutual information for comparing clusterings, while involving much less computations.
For future work, we plan to extend this idea to other similarity metrics. While the practical interest is less obvious for the Adjusted Rand Index [3], due to the fact that the time complexity of this metric is already independent of the number of samples, it would be worth considering other versions of information theoretic measures, as those studied in [7].
we get:

Proof of Corollary 2
The proof follows from (7) applied to the diagonal contingency matrix n ij = a i δ ij = b j δ ij , where δ ij denotes the Kronecker symbol.