A Global Optimization Algorithm for K-Center Clustering of One Billion Samples
| Autor: | Jiayang Ren, Ningning You, Kaixun Hua, Chaojie Ji, Yankai Cao |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Web of Science |
| DOI: | 10.48550/arxiv.2301.00061 |
| Popis: | This paper presents a practical global optimization algorithm for the K-center clustering problem, which aims to select K samples as the cluster centers to minimize the maximum within-cluster distance. This algorithm is based on a reduced-space branch and bound scheme and guarantees convergence to the global optimum in a finite number of steps by only branching on the regions of centers. To improve efficiency, we have designed a two-stage decomposable lower bound, the solution of which can be derived in a closed form. In addition, we also propose several acceleration techniques to narrow down the region of centers, including bounds tightening, sample reduction, and parallelization. Extensive studies on synthetic and real-world datasets have demonstrated that our algorithm can solve the K-center problems to global optimal within 4 hours for ten million samples in the serial mode and one billion samples in the parallel mode. Moreover, compared with the state-of-the-art heuristic methods, the global optimum obtained by our algorithm can averagely reduce the objective function by 25.8% on all the synthetic and real-world datasets. Comment: 34 pages, 6 figures, and 5 tables |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|