Abstract
Consensus problems involve merging multiple, potentially noisy grouping solutions into a single robust result. This paper introduces a unified bi-clustering framework that addresses this challenge by applying iterative L1-norm matrix factorization to a "preference matrix." This versatile method is applicable to diverse domains, including image segmentation, community discovery in social networks, and parametric model estimation. By leveraging the L1-norm, the framework achieves high robustness against outliers and "junk" candidate solutions, outperforming traditional co-occurrence based methods in both accuracy and scalability.
Introduction
In data science, there is rarely a single "perfect" algorithm. Running different clustering algorithms on the same dataset often yields varying results. The "consensus problem" asks how to combine these disparate solutions to uncover the underlying ground truth.
Traditional consensus methods often rely on an $m \times m$ co-occurrence matrix (where $m$ is the number of data points), recording how often pairs of points end up in the same group. This approach has two major flaws: it loses the context of larger group structures by only looking at pairwise relations, and it becomes computationally prohibitive for large datasets. Furthermore, the authors demonstrate that fitting multiple parametric models (such as finding multiple lines in a noisy image) is essentially a consensus problem that has lacked a formal unified treatment until now.
The Bi-clustering Framework
The core of the proposed framework is the Preference Matrix ($A$). In this $m \times n$ matrix, rows represent data points ($m$) and columns represent "candidate groups" ($n$) generated by various base algorithms. If point $i$ belongs to candidate group $j$, the entry $A_{ij}$ is marked (typically with a 1).
Instead of clustering the points in isolation, the authors perform bi-clustering—simultaneously selecting a subset of points and a subset of candidate groups that "agree" with each other. The optimization is performed using a modified version of Non-negative Matrix Factorization (NMF). While standard NMF uses the L2 (Frobenius) norm, this framework employs the L1-norm. The L1-norm acts like a "median," making the process significantly more robust to outliers and poor candidate solutions.
The algorithm utilizes an iterative rank-one scheme to find the most significant bi-cluster, "zeros out" those rows and columns to prevent overlap, and repeats the process. For parametric models, the framework incorporates a "sanity check" from Computational Gestalt theory known as A Contrario validation, ensuring that detected models are statistically meaningful rather than random noise.
Applications and Key Results
The authors demonstrate the framework's "universal" nature across several domains:
- Clustering: On standard UCI repository datasets and the Hopkins 155 motion segmentation dataset, the bi-clustering approach consistently ranked among the top performers, often exceeding the accuracy of the best individual base algorithm.
- Community Detection: In social networks like the "Les Misérables" character network and large-scale Facebook 100 datasets, the consensus solution proved more stable and closer to the ground truth than single algorithm runs, especially in perturbed networks.
- Parametric Estimation: The method significantly outperformed state-of-the-art techniques like J-linkage in multi-model estimation tasks, such as detecting lines, circles, and 3D planes in datasets like the Pozzoveggiani point clouds and York Urban database.
Discussion
A primary advantage of this approach is its efficiency; the $m \times n$ preference matrix is much smaller than the $m \times m$ co-occurrence matrix since the number of candidate groups ($n$) is usually much smaller than the number of data points ($m$). The choice of the L1-norm is critical, allowing the algorithm to ignore "junk" candidate groups.
However, limitations exist. If all base algorithms consistently share the same systematic error, the consensus framework will reproduce it. Future work may explore "soft" thresholding for overlapping clusters and the use of real-valued distances in the preference matrix to eliminate the need for initial tuning parameters. By bridging modern matrix factorization with classical psychological theories of perception, this framework provides a robust and scalable solution for a wide array of data grouping challenges.
Summary updated