Clustering is at the very core of machine learning, and its applications
proliferate with the increasing availability of data. However, as datasets
grow, comparing clusterings with an adjustment for chance becomes
computationally difficult, preventing unbiased ground-truth comparisons and
solution selection. We propose FastAMI, a Monte Carlo-based method to
efficiently approximate the Adjusted Mutual Information (AMI) and extend it to
the Standardized Mutual Information (SMI). The approach is compared with the
exact calculation and a recently developed variant of the AMI based on pairwise
permutations, using both synthetic and real data. In contrast to the exact
calculation our method is fast enough to enable these adjusted
information-theoretic comparisons for large datasets while maintaining
considerably more accurate results than the pairwise approach.

本文提出了一种基于蒙特卡罗方法的 FastAMI 算法，用于高效逼近除机会因素影响的 AMI 及其扩展版本 SMI，旨在解决大数据集下聚类比较的计算难题与偏差问题，并通过实验验证，FastAMI 方法能在维持比较精度的同时，显著提升运算速度，优于基于配对重排的 AMI 算法。

FastAMI-- 用蒙特卡罗方法进行聚类比较度量中的机会调整

FastAMI -- a Monte Carlo Approach to the Adjustment for Chance in  Clustering Comparison Metrics

Adjusted for chance measures are widely used to compare
partitions/clusterings of the same data set. In particular, the Adjusted Rand
Index (ARI) based on pair-counting, and the Adjusted Mutual Information (AMI)
based on Shannon information theory are very popular in the clustering
community. Nonetheless it is an open problem as to what are the best
application scenarios for each measure and guidelines in the literature for
their usage are sparse, with the result that users often resort to using both.
Generalized Information Theoretic (IT) measures based on the Tsallis entropy
have been shown to link pair-counting and Shannon IT measures. In this paper,
we aim to bridge the gap between adjustment of measures based on pair-counting
and measures based on information theory. We solve the key technical challenge
of analytically computing the expected value and variance of generalized IT
measures. This allows us to propose adjustments of generalized IT measures,
which reduce to well known adjusted clustering comparison measures as special
cases. Using the theory of generalized IT measures, we are able to propose the
following guidelines for using ARI and AMI as external validation indices: ARI
should be used when the reference clustering has large equal sized clusters;
AMI should be used when the reference clustering is unbalanced and there exist
small clusters.

本文介绍基于 Tsallis 熵的广义信息熵测量值计算方法，并将其应用于聚类比较中，从而提供了 AR1 和 AMI 的最佳应用场景和使用指南。