An Approximation Algorithm For Spherical K-means Problem With Penalty

In the background of data network development and information diversification,the development of mobile Internet and Internet of Things is developing rapidly,and massive data is generated,so mining data in mass data is increasingly important.k-means cluster is used in large quantities for data pretreatment,data analysis,and so on due to its simple and effective.As we all know,k-means problem is a classic combinatorial optimization problem,as well as the hot issues in the research of machine learning and theoretical computer science research,in data mining,artificial intelligence,and other fields has been widely used.Under the background of developed data network and diversified information,k-means clustering has faced many new challenges,generating a variety of challenging research topics that need to be solved urgently.We need to further study the k-means problem and its various deformation algorithms.Since k-means problem is NP-hard,Therefore,the design of approximate algorithm is one of the methods to solve NP-hard problems,which can give an approximate solution to the problem with guaranteed performance.In most cases,a given data set may contain a small portion of noise data that is quite different from most other data.If these noise data are clustered,the clustering center may be distorted,and most of the data may not be properly divided,this indicates that the distance between the data and its corresponding clustering centers may be greater than they actually are.These situations inspire us to consider paying penalty to ensure that some data is not clustered.Base on the k-means problem in this paper,a variant of thek-means problem in spherical space is considered,which is the spherical k-means problem with penalty.In this thesis,we have given the set D of n data points in a given d-dimensional unit sphere S^d,an integer k? n and each data punishment cost p_j,then we guarantee that some data will not be clustered by paying penalty fee,the aim is to minimizes the total cost of implementing the unpenalized data point to its nearest corresponding central point plus the penalty cost of the penalized point.Based on local search scheme,using single swap,we propose a(4(11 + 4(?))+ e)-approximation algorithm for the spherical k-means problem with penalty,finally,this thesis designs numerical experiments to prove the effectiveness of the algorithm.