A Novel Heuristic Algorithm And Bi-criteria Analysis For Fuzzy C-means Problem

As an important analytical method,cluster analysis is widely applied in many fields.k-means problem is a famous clustering model.In this problem,the sample points are strictly classified,that is,a certain point can only belong to a certain cluster.This strict classification method belongs to hard clustering.However,in many practical situations,this hard clustering idea is not applicable.So we consider a kind of soft clustering model-fuzzy C-means problem.This problem describes the clustering relationship by endowing sample points with the membership degree of each center.In this paper,we mainly study the heuristic algorithm of fuzzy Cmeans problem and its bi-criteria analysis.In chapter 2,we prove that the fuzzy C-means++algorithm has an approximation ratio of O(k2 ln k).On this basis,we design a heuristic seeding algorithm based on the contribution of the fuzzy potential function,which can improve the approximation ratio to O(k ln k).We also generalize the fuzzy parameter m from 2 to any positive integer.The results of numerical experiments verify that the fuzzy C-means problem has higher stability in solving practical problems.In chapter 3,the fuzzy C-means problem is analyzed by bicriteria.We show that O(k2)and O(k)can be achieved by selecting βk cluster centers for arbitrary constant β≥ 1.The results of numerical experiments verify the validity and correctness of the bi-criteria theory.