TL;DR
This paper introduces a novel global optimization algorithm for the K-center clustering problem, capable of handling datasets with up to one billion samples. By employing a specialized branch-and-bound approach that focuses solely on cluster center regions and a closed-form lower bound, the algorithm achieves global optimality efficiently, outperforming heuristic methods and existing optimizers on massive datasets.
What Problem Does This Paper Address?
The K-center clustering problem aims to select K representative points (centers) from a dataset such that the maximum distance from any data point to its nearest center is minimized. This is a fundamental problem in data analysis, with applications ranging from facility location to data summarization. However, the K-center problem is NP-hard, meaning finding the exact optimal solution becomes computationally intractable for large datasets. Existing exact methods struggle with datasets beyond a few thousand samples, while heuristic methods, though faster, do not guarantee optimality. This paper addresses the critical challenge of finding provably optimal K-center solutions for extremely large datasets, specifically up to one billion samples, a scale previously unaddressed by exact optimization techniques.
Methods
The core of the proposed solution is a tailored reduced-space branch-and-bound (BB) algorithm. Unlike traditional BB methods that branch on all variables, this algorithm only branches on the region of cluster centers. This significantly prunes the search space.
Key innovations include:
- Two-stage decomposable lower bound: A novel formulation that allows for a closed-form solution to calculate lower bounds, eliminating the need for expensive sub-problem solvers. This is achieved by relaxing non-anticipativity and "centers on samples" constraints.
- Structure-exploiting acceleration techniques:
- Bounds Tightening (BT): Techniques like cluster assignment (pre-determining sample-to-cluster mappings) and sample reduction (identifying and removing redundant samples) are used to shrink the search space for cluster centers.
- Sample Reduction: Identifies samples that are redundant for both lower and upper bounding, allowing them to be removed from consideration without affecting the optimal solution.
- Parallelization: A sample-level parallelization strategy is implemented using MPI to leverage high-performance computing clusters.
Datasets
The authors evaluated their algorithm on a comprehensive set of datasets:
- Synthetic datasets: Generated using Julia's
Distributions.jlandRandom.jlmodules, featuring 3 Gaussian clusters, 2 attributes, and varying numbers of samples. - Real-world datasets:
- 30 datasets from the UCI Machine Learning Repository.
- Specific datasets: Pr2392, Hemi, Taxi.
- The scale of these datasets ranges from 150 samples to over 1.1 billion samples (Taxi dataset), with attributes ranging from 2 to 68.
Key Insights and Ideas
- Branching on center regions is sufficient: The paper demonstrates that by intelligently branching only on the possible regions for cluster centers, convergence to the global optimum can be guaranteed, even for massive datasets. This is a significant departure from traditional BB approaches.
- Closed-form lower bounds are powerful: Developing a lower bound that can be computed directly, without solving complex sub-optimization problems, is crucial for the efficiency of the algorithm on large-scale instances.
- Acceleration techniques are critical: The effectiveness of the BB algorithm is heavily reliant on the proposed bounds tightening and sample reduction methods. These techniques dramatically reduce the search space and computational burden.
- Global optimality for massive datasets is achievable: The most striking insight is the demonstration that finding provably optimal K-center solutions for datasets with billions of data points is now feasible within practical time limits.
Key Results
- The algorithm can solve K-center problems for datasets with 10 million samples in serial mode and 1 billion samples in parallel mode within 4 hours, achieving a small optimality gap (≤ 0.1%). This is a significant leap from previous work that could only handle thousands of samples.
- Compared to state-of-the-art heuristic methods (like FFT), the global optimum obtained by this algorithm reduces the objective function by an average of 25.8% across synthetic and real-world datasets.
- For large datasets, the proposed algorithm significantly outperforms the commercial solver CPLEX, which often fails to converge to a small optimality gap within the given time limit.
- The acceleration techniques (BB+CF+BT) are shown to drastically reduce the number of BB nodes and computation time compared to the version without these techniques (BB+CF). For instance, on the Syn-1200 dataset, BB+LD+BT required 23 nodes and 13.5 seconds to reach a gap < 0.1%, while BB+LD needed over 1.1 million nodes and 3609 seconds.
- The parallel version of the algorithm achieved a small optimality gap (≤ 0.1%) within 4 hours on datasets with billions of samples, a feat previously unattainable.
Limitations and Future Work
- Optimality gap for K > 3: The authors note that their algorithm still struggles to obtain a small optimality gap when the desired number of clusters K is larger than 3, especially for datasets with millions of samples. However, they highlight that even in these cases, their algorithm provides a better upper bound than other methods.
- Future Work: The authors express interest in extending their algorithm to handle constrained versions of K-center problems, such as capacitated, restricted, absolute, and vertex-restricted versions.
Summary updated