Approximation algorithms for fuzzy C-means problem based on seeding method

As a kind of important soft clustering model, the fuzzy C-means method is widely applied in many fields. In this method, instead of the strict distributive ability in the classical k-means method, all the sample points are endowed with degrees of membership to each center to depict the fuzzy clustering. In this paper, we show that the fuzzy C-means++ algorithm, which introduces the k-means++ algorithm as a seeding strategy, gives a solution for which the approximation guarantee is O ( k 2 ln ⁡ k ). A novel seeding algorithm is then designed based on the contribution of the fuzzy potential function, which improves the approximation ratio to O ( k ln ⁡ k ). Preliminary numerical experiments are proposed to support the theoretical results of this paper.

Authors

• Qian Liu Sea AI Lab
• Jianxin Liu
• Min Li School of Computer Science and Engineering, Central South University, China
• Yang Zhou Hangzhou Fenghua Technology Co., Ltd

Keywords

• Fuzzy C-means problem
• Seeding algorithm
• Approximation algorithm
• Approximation ratio