An Approximation Algorithm Based on Seeding Algorithm for Fuzzy k-Means Problem with Penalties  

作　　者：Wen-Zhao Liu Min Li 

机构地区：[1]School of Mathematics and Statistics,Shandong Normal University,Jinan 250014,Shandong,China

出　　处：《Journal of the Operations Research Society of China》2024年第2期387-409,共23页中国运筹学会会刊（英文）

基　　金：Higher Educational Science and Technology Program of Shandong Province(No.J17KA171);Natural Science Foundation of Shandong Province(No.ZR2020MA029).

摘　　要：As a classic NP-hard problem in machine learning and computational geometry,the k-means problem aims to partition the given dataset into k clusters according to the minimal squared Euclidean distance.Different from k-means problem and most of its variants,fuzzy k-means problem belongs to the soft clustering problem,where each given data point has relationship to every center point.Compared to fuzzy k-means problem,fuzzy k-means problem with penalties allows that some data points need not be clustered instead of being paid penalties.In this paper,we propose an O(αk In k)-approximation algorithm based on seeding algorithm for fuzzy k-means problem with penalties,whereαinvolves the ratio of the maximal penalty value to the minimal one.Furthermore,we implement numerical experiments to show the effectiveness of our algorithm.

关 键 词：Approximation algorithm Seeding algorithm Fuzzy k-means problem with penalties 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]