title: Correction for chance in generalized information-theoretic clustering similarity indices
title: Korrektur für Zufallseinflüsse bei verallgemeinerten informationstheoretischen Clusteringvergleichsindizes
Creators: name: Klede, Kai
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2025
Subjects: subject: clustering comparison
subject: external evaluation metrics
subject: mutual information
subject: rand index
subject: machine learning
subject: DDC Classification::0 Informatik, Information und Wissen, allgemeine Werke::00 Informatik, Wissen und Systeme::006 Spezielle Computerverfahren

description: Clustering is a fundamental technique in unsupervised machine learning with applications spanning numerous domains. Yet, objectively evaluating and comparingclustering results remains challenging due to limitations in current cluster similarityindices and computational scalability. This doctoral dissertation addresses criticallimitations in existing cluster similarity indices and their computational scalability.The first contribution is FastAMI, a highly efficient Monte Carlo method to approximate the popular Adjusted Mutual Information (AMI) for clustering comparison.FastAMI enables AMI calculations on massive datasets with complex cluster sizedistributions. Furthermore, FastAMI is extended to approximate the StandardizedMutual Information (SMI), which accounts for chance effects when comparingmultiple clusterings against a fixed ground truth clustering. Comprehensive experiments across diverse real-world network datasets demonstrate the accuracy, speed,and scalability of FastAMI over existing methods.The second key contribution is the introduction of the 𝑝-value adjusted MutualInformation (PMI) - the first cluster similarity metric that is provably unbiased whencomparing multiple clusterings to a fixed reference (type II unbiasedness), whilealso being monotonically increasing as clustering candidates approach the referenceclustering. Efficient approximations are presented for bounded-error computationsand theoretical and empirical studies highlight PMI’s utility for unbiased clusteringalgorithm selection over alternatives like the AMI and Adjusted Rand Index (ARI).Finally, the third contribution re-evaluates the standard random models used instandardizing cluster similarity metrics. By extending beyond the conventionalrandom permutation model to include fixed-cluster and uniform-cluster randommodels, this work demonstrates through gene expression data comparisons thatthe effectiveness of standardization is highly dependent on the selected null model,emphasizing the importance of model alignment in clustering applications.In summary, this dissertation presents scalable, unbiased methods for clusteringevaluation, supporting reliable benchmarking and model selection across variedapplications.
description: Clustering ist eine grundlegende Technik im Bereich des unüberwachten maschinellen Lernens mit Anwendungen in zahlreichen Domänen. Die objektive Bewertungund der Vergleich von Clustering-Ergebnissen stellen jedoch aufgrund von Einschränkungen der aktuellen Clustervergleichsindizes und der Skalierbarkeit derAlgorithmen eine Herausforderung dar. Diese Doktorarbeit adressiert wesentlicheEinschränkungen bestehender Clustervergleichsindizes und deren Laufzeiteffizienz.Der erste Beitrag ist FastAMI, eine hocheffiziente Monte-Carlo-Methode zur Approximation der weit verbreiteten Adjusted Mutual Information (AMI) für denVergleich von Clusterings. FastAMI ermöglicht AMI-Berechnungen auf umfangreichen Datensätzen mit komplexen Clustergrößenverteilungen. Desweiteren wurdeder Ansatz von FastAMI auf die Standardized Mutual Information (SMI) übertragen,um diese zu approximieren. Die SMI berücksichtigt Zufallseffekte, die auftretenwenn mehrere Clusterings mit einem festen Referenz-Clustering verglichen werden.Umfassende Experimente mit verschiedenen realen Netzwerkdatensätzen belegendie Genauigkeit, Geschwindigkeit und Skalierbarkeit von FastAMI im Vergleich zubestehenden Methoden.Der zweite wesentliche Beitrag ist die Einführung der 𝑝-value adjusted Mutual Information (PMI) – dem ersten Clustervergleichsindex, der nachweislich unverzerrt ist,wenn mehrere Clusterings mit einer festen Referenz verglichen werden (Typ-II Bias)und zudem monoton ansteigt, wenn sich die Clusterkandidaten dem Referenz-Clustering annähern. Effiziente Approximationen inklusive Fehlerabschätzungerlauben praktische Berechenbarkeit, und theoretische sowie empirische Studienzeigen die Nützlichkeit der PMI für eine verbesserte Selektion von Clustering-Algorithmen im Vergleich zu Alternativen wie der AMI und dem ARI.Abschließend wird im dritten Beitrag eine Neubewertung der Zufallsmodelle zurStandardisierung von Clustervergleichsindizes vorgenommen. Das herkömmlichePermutationsmodell wurde um ein Modell mit fester Anzahl an Clustern und einuniformes Modell über alle Cluster erweitert. Clustering Vergleiche von Genexpressionsdaten zeigen, dass die Wirksamkeit der Standardisierung stark vom gewähltenNullmodell abhängt und unterstreichen die Bedeutung des Zufallsmodells für dieAuswahl geeigneter Clusteringverfahren.Zusammenfassend stellt diese Dissertation skalierbare, unverzerrte Methoden fürdie Clusterbewertung vor, die zuverlässiges Benchmarking und Modellauswahl inverschiedenen Anwendungen unterstützen.