Search

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 + ϵ) -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 ((1891 e k ϵ 2) 8 k / ϵ n d) , and outputs a collection of size O ((1891 e k ϵ 2) 8 k / ϵ n) of candidate sets including approximation centers. [ABSTRACT FROM AUTHOR]