| The k-means problem is a classic NP-hard problem.Due to its NP-hardness,it is impossible to find an exact solution in polynomial time unless P=NP.The k-means problem has widely applications in data mining,machine learning and other areas.In the big data age,clustering related to big data has become a hot topic in current research.Usually we employ heuristic or approximate algorithms to solve such problemsIn this problem,we are given a n-point data set χ in Rd and an integer k(k ≤ n),the goal is to partition X into k subsets so as to minimize the sum of within-cluster variances(or the squared distances between every data to its cluster center).The point in X has different importance.In order to cluster important points better,researchers have proposed k-means problem with penalties.In this problem,the points is more important,the penalty cost is higher.The k-means problem with penalties is a generalized problem of the k-means problem.The penalty cost for any point x∈ χ is p(x).Each data point is either clustered to a center or penalized.In this thesis,we study the k-means problem with penalties,and give the parallel seeding algorithm.The number of sampling points in each iteration is random.In the case of a given number of iterations,the approximate ratio analysis of the algorithm is given. |
