Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2301.00061 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908860542877696 |
|---|---|
| author | Ren, Jiayang You, Ningning Hua, Kaixun Ji, Chaojie Cao, Yankai |
| author_facet | Ren, Jiayang You, Ningning Hua, Kaixun Ji, Chaojie Cao, Yankai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_00061 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Global Optimization Algorithm for K-Center Clustering of One Billion Samples Ren, Jiayang You, Ningning Hua, Kaixun Ji, Chaojie Cao, Yankai Optimization and Control Machine Learning 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. |
| title | A Global Optimization Algorithm for K-Center Clustering of One Billion Samples |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2301.00061 |