Stochastic Approximate Algorithms for Uncertain Constrained K-Means Problem

The k-means problem has been paid much attention for many applications. In this paper, we define the uncertain constrained k-means problem and propose a (1 + epsilon)-approximate algorithm for the problem. First, a general mathematical model of the uncertain constrained k-means problem is proposed. Second, the random sampling properties of the uncertain constrained k-means problem are studied. This paper mainly studies the gap between the center of random sampling and the real center, which should be controlled within a given range with a large probability, so as to obtain the important sampling properties to solve this kind of problem. Finally, using mathematical induction, we assume that the first j - 1 cluster centers are obtained, so we only need to solve the j-th center. The algorithm has the elapsed time O((1891ek/epsilon(2))(8k/epsilon)nd), and outputs a collection of size O((1891ek/epsilon(2))(8k/epsilon) n) of candidate sets including approximation centers.

Automated summary

This paper introduces a mathematical model for the uncertain constrained k-means problem and proposes an approximate algorithm to solve it. By studying the properties of random sampling, the gap between the random sampling center and the real center is controlled to obtain important sampling properties for solving this problem.