Abstract
Utilizing expert input often improves clustering performance. However, in a knowledge discovery problem, ground truth is unknown even to an expert. Thus, instead of one expert, we solicit the opinion from multiple experts. The key question motivating this work is: which experts should be assigned higher weights when there is disagreement on whether to put a pair of samples in the same group? To model the uncertainty in constraints from different experts, we build a probabilistic model for pairwise constraints through jointly modeling each expert’s accuracy and the mapping from features to latent cluster assignments. After learning our probabilistic discriminative clustering model and accuracies of different experts, 1) samples that were not annotated by any expert can be clustered using the discriminative clustering model; and 2) experts with higher accuracies are automatically assigned higher weights in determining the latent cluster assignments. Experimental results on UCI benchmark datasets and a real-world disease subtyping dataset demonstrate that our proposed approach outperforms competing alternatives, including semi-crowdsourced clustering, semi-supervised clustering with constraints from majority voting, and consensus clustering.
Introduction
In semi-supervised clustering, algorithms are typically guided by human input in the form of pairwise constraints—specifying whether two samples "must-link" or "cannot-link." Most existing methods assume these constraints originate from a single, infallible expert. However, in complex domains like medical research, the ground truth is often unknown even to specialists. When multiple experts are consulted, they inevitably provide conflicting and sparse advice. This paper addresses the challenge of combining inconsistent constraints from multiple experts with varying, unknown levels of expertise without allowing noisy input to degrade clustering performance.
The Proposed Framework
The authors propose a joint probabilistic framework that simultaneously learns data clustering and expert reliability. Unlike generative models that make strict assumptions about data distribution, this approach uses a discriminative clustering model (multiple logistic regression) to map features to latent cluster probabilities. This flexibility allows the model to easily cluster new data points that were never seen by any expert.
Each expert's reliability is modeled using Bernoulli distributions parameterized by sensitivity (correctly identifying must-links) and specificity (correctly identifying cannot-links). The model is trained using the Expectation-Maximization (EM) algorithm. In the E-step, it estimates latent cluster assignments; in the M-step, it updates clustering weights and individual expert accuracy parameters. A key mathematical insight is that the optimization naturally scales an expert's influence based on their accuracy, effectively giving more reliable experts a "louder voice" in the final decision.
Experimental Evaluation
The model was evaluated on 11 UCI benchmark datasets and a real-world dataset of 987 patients with Chronic Obstructive Pulmonary Disease (COPD). For the UCI benchmarks, synthetic experts with varying accuracies were generated to simulate realistic uncertainty.
On the benchmark datasets, the proposed approach consistently outperformed competing methods such as SemiCrowd, ITML, and MPCKMeans in terms of Normalized Mutual Information (NMI). On the COPD dataset, which featured constraints from 27 actual experts, the model identified four distinct patient subtypes. It was the only method tested that yielded statistically significant differences across critical clinical outcomes, including mortality and lung function decline.
Conclusion
By explicitly modeling individual expert uncertainty alongside a discriminative clustering model, this framework provides a robust solution for knowledge discovery when ground truth is elusive. While the current model assumes linear cluster boundaries and requires multiple initializations due to a non-convex objective, it represents a significant step forward in handling real-world, noisy human input in machine learning.
Summary updated