Effective Heuristic Techniques for Combined Robust Clustering Problem

Yunhe Xu (), Chenchen Wu (), Ling Gai and Lu Han ()
Additional contact information
Yunhe Xu: Institute of Operations Research and Systems Engineering, College of Science, Tianjin University of Technology, No. 391 Binshui Xi Road, Tianjin 300384, P. R. China
Chenchen Wu: Institute of Operations Research and Systems Engineering, College of Science, Tianjin University of Technology, No. 391 Binshui Xi Road, Tianjin 300384, P. R. China
Ling Gai: Glorious Sun School of Business & Management, Donghua University, Shanghai 200051, P. R. China
Lu Han: School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 01, 1-17

Abstract: Clustering is one of the most important problems in the fields of data mining, machine learning, and biological population division, etc. Moreover, robust variant for k-means problem, which includes k-means with penalties and k-means with outliers, is also an active research branch. Most of these problems are NP-hard even the most classical problem, k-means problem. For the NP-hard problems, the heuristic algorithm is a powerful method. When the quality of the output can be guaranteed, the algorithm is called an approximation algorithm.In this paper, combining two types of robust settings, we consider k-means problem with penalties and outliers (k-MPO). In the k-MPO, we are given an n-point set U ⊂ ℠d, a penalty cost pv ≥ 0 for each v ∈ U, an integer k ≤ n, and an integer z ≤ n. The target is to find a center subset S ⊆ ℠d with |S|≤ k, a penalty subset P ⊆ U and an outlier subset Z ⊆ U with |Z|≤ z, such that the sum of the total costs, including the connection cost and the penalty cost, is minimized. We offer an approximation algorithm using a heuristic local search scheme. Based on a single-swap manipulation, we obtain 274-approximation algorithm.

Keywords: Robust clustering problem; k-means; local search scheme; approximation algorithm (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922400097
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:01:n:s0217595922400097

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922400097

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().