Introduction
Clustering is a fundamental task in data analysis, yet it is rarely a "one and done" process. Different algorithms, feature sets, or random initializations often produce wildly different results. Consensus clustering aims to reconcile these differences to find a single "ground truth" partition that captures the underlying structure of the data more reliably than any single expert.
However, most existing consensus methods rely on least-squares ($L_2$) loss functions. In statistical modeling, squaring errors gives outliers or "noisy" expert opinions massive leverage, potentially pulling the final consensus away from the true clusters. This paper introduces a robust approach to consensus clustering designed to be minimally affected by such bias, which is particularly critical in sensitive applications like advertising forecasting.
Robust Consensus Clustering (RCC)
The authors propose Robust Consensus Clustering (RCC), which rests on three technical pillars:
- $L_1$-Loss Formulation: By swapping standard squared-error loss for the $L_1$-norm (absolute differences), the model behaves like a "median" rather than a "mean." This makes the consensus significantly more resistant to extreme values and noisy inputs.
- Continuous Relaxation: To overcome the NP-complete nature of discrete clustering assignments, the problem is relaxed into a continuous domain using a clustering indicator matrix ($H$) and a diagonal matrix ($D$).
- ADMM Optimization: The resulting non-smooth optimization problem is solved via the Alternating Direction Method of Multipliers (ADMM). This technique decomposes the complex global problem into smaller, iterative sub-problems to update the error, indicator, and diagonal matrices.
For advertising-specific applications, the authors also integrate Kolmogorov-Smirnov (KS) Statistics to measure similarities between advertisers' win-rate and cost distributions, allowing for clustering based on the shape of bidding behavior.
Experimental Results
Benchmark Performance
The RCC method was validated against eight classic UCI datasets. As shown in the performance comparison below, RCC consistently outperformed standard baselines such as k-means, CSPA, and HPGA. Notably, on the Soybean dataset, RCC achieved a perfect 1.00 accuracy, a significant jump from the 0.72 achieved by standard k-means.
Multi-view and Real-world Impact
The robustness of the $L_1$ approach is further evidenced in multi-view image datasets where different features (like LBP or HOG) provide conflicting perspectives. On the MSRC-v1 dataset, RCC reached 80.17% accuracy, outperforming simple feature concatenation and other consensus methods.
In real-world advertising data from Yahoo Research, RCC reduced the Forecast Spend Error to 9.64%, compared to 12.78% for standard consensus clustering and over 25% for methods relying solely on textual data. This improvement in segmentation directly translates to higher financial predictability for advertisers.
Conclusion and Future Work
While RCC demonstrates significant gains in robustness and accuracy, the optimization problem is non-convex, meaning the ADMM algorithm finds a local rather than global optimum. Furthermore, the $O(n^3)$ computational complexity due to eigenvalue decomposition poses a challenge for massive datasets. Future research may focus on accelerating execution through GPU-based solvers or divide-and-conquer strategies to scale the algorithm for larger advertising ecosystems.
Summary updated