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
-approximate algorithm for the problem. First, a general mathematical model of the
[...] Read more.
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
-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
cluster centers are obtained, so we only need to solve the
j-th center. The algorithm has the elapsed time
, and outputs a collection of size
of candidate sets including approximation centers.
Full article