Stochastic Approximate Algorithms for Uncertain Constrained K-Means Problem

The k-means problem has received much attention in the past several decades. The k-means problems consists of partitioning a set P of points in d-dimensional space ${\mathbb{R}}^d$ into k subsets $P_1,\dots ,P_k$ such that ${\sum }_{i=1}^k{\sum }_{p\in P_i}\left|\right|p-c_i{\left|\right|}^2$ is minimized, where $c_i$ is the center of $P_i$, and $\left|\right|p-q\left|\right|$ is the distance between two points of p and q. The k-means problem is one of the classical NP-hard problems, and has been paid much attention in the literature [1,2,3].

For many applications, each cluster of the point set may satisfy some additional constraints, such as chromatic clustering [4], r-capacity clustering [5], r-gather clustering [6], fault tolerant clustering [7], uncertain data clustering [8], semi-supervised clustering [9], and l-diversity clustering [10]. The constrained clustering problems was studied by Ding and Xu, who presented the first unified framework in [11]. Given a point set $P\subseteq {\mathbb{R}}^d$, and a positive integer k, a list of constraints $\mathbb{L}$, the constrained k-means problem is to partition P into k clusters $\mathbb{P}=\{P_1,\dots ,P_k\}$, such that all constraints in $\mathbb{L}$ are satisfied and ${\sum }_{P_i\in \mathbb{P}}{\sum }_{x\in P_i}\left|\right|x-c(P_i){\left|\right|}^2$ is minimized, where $c(P_i)=\frac{1}{|P_i|}{\sum }_{x\in P_i}x$ denotes the centroid of $P_i$.

In recent years, particular research has been focused on the constrained k-means problem. Ding and Xu [11] showed the first polynomial time approximation scheme with running time $O(2^{poly(k/ϵ)}{(logn)}^{k}nd)$ for the constrained k-means problem, and obtained a collection of size $O(2^{poly(k/ϵ)}{(logn)}^{k+1})$ of candidate approximate centers. The existing fastest approximation schemes for the constrained k-means problem takes $O(2^{O(k/ϵ)}nd)$ time [12,13], which was first shown by Bhattacharya, Jaiswai, and Kumar [12]. Their algorithm gives a collection of size $O(2^{O(k/ϵ)})$ of candidate approximate centers. In this paper, we propose the uncertain constrained k-means problem, which supposes that all points are random variables with probabilistic distributions. We present a stochastic approximate algorithm for the uncertain constrained k-means problem. The uncertain constrained k-means problem can be regarded as a generalization of the constrained k-means problem. We prove the random sampling properties of the uncertain constrained k-means problem, which are fundamental for our proposed algorithm. By applying random sampling and mathematical induction, we propose a stochastic approximate algorithm with lower complexity for the uncertain constrained k-means problem.

This paper is organized as follows. Some basic notations are given in Section 2. Section 3 provides an overview of the new algorithm for the uncertain constrained k-means problem. In Section 4, we discuss the detailed algorithm for the uncertain constrained k-means problem. In Section 5, we investigate the correctness, success probability, and running time analysis of the algorithm. Section 6 concludes this paper and gives possible directions for future research.

In this section, we first introduce the main idea of our methodology to solve the uncertain constrained k-means problem.

Considering the optimal partition $\mathbb{X}=\{{\mathcal{X}}_1,\dots ,{\mathcal{X}}_k\}(|{\mathcal{X}}_1|\ge \dots \ge |{\mathcal{X}}_k|)$ of $\mathcal{X}$, since $|{\mathcal{X}}_1|/|\mathcal{X}|\ge 1/k$, if we could sample a set $\mathcal{S}$ of size $O(k/ϵ)$ from $\mathcal{X}$ uniformly and independently, then at least $O(1/ϵ)$ random variables in $\mathcal{S}$ are from ${\mathcal{X}}_1$ with a certain probability. All subsets of $\mathcal{S}$ of size $O(1/ϵ)$ could be enumerated to discover the approximate center of ${\mathcal{X}}_1$.

We assume that $C_{j-1}=\{c_1,\dots ,c_{j-1}\}$ is the set including approximate centers of the ${\mathcal{X}}_1,\dots ,{\mathcal{X}}_j$. Let ${\mathcal{B}}_j=\{X\in \mathcal{X}|dist(X,C_{j-1})=mi{n}_{c\in C_{j-1}}{\int }^{{\mathbb{R}}^d}\left|\right|s-c\left|\right|f_X(s)ds\le r_j\}$, where $r_j=\sqrt{\frac{ϵ}{40{\beta }_{j}k}}{\sigma }_{opt}$. The set ${\mathcal{X}}_j$ is divided into two parts: ${\mathcal{X}}_j^{out}$ and ${\mathcal{X}}_j^{in}$, where ${\mathcal{X}}_j^{out}={\mathcal{X}}_j\backslash {\mathcal{B}}_j$ and ${\mathcal{X}}_j^{in}={\mathcal{X}}_j\cap {\mathcal{B}}_j$. For each random variable X, let $\tilde{X}$ be the nearest point (particular random variable) in $C_{j-1}$ to X. Let ${\tilde{\mathcal{X}}}_j^{in}=\left\{\tilde{X}\right|X\in {\mathcal{X}}_j^{in}\}$, and ${\tilde{\mathcal{X}}}_j={\tilde{\mathcal{X}}}_j^{in}\cup {\mathcal{X}}_j^{out}$.

If most of the random variables of ${\mathcal{X}}_j$ are in ${\mathcal{X}}_j^{in}$, our idea is to use the center of ${\tilde{\mathcal{X}}}_j^{in}$ to approximate the center of ${\mathcal{X}}_j$. The center of ${\tilde{\mathcal{X}}}_j^{in}$ is found based on $C_{j-1}$. If most of the random variables of ${\mathcal{X}}_j$ are in ${\mathcal{X}}_j^{out}$, our ideal is to replace the center of ${\mathcal{X}}_j$ with the center of ${\tilde{\mathcal{X}}}_j$. For seeking out the approximate center of ${\tilde{\mathcal{X}}}_j$, we should find out a subset ${\mathcal{S}}^{\prime }$ by uniformly sampling from ${\tilde{\mathcal{X}}}_j$. However, the set ${\mathcal{X}}_j^{out}$ is unknown. We need to find the set ${\mathcal{S}}^{\prime }\cap {\mathcal{X}}_j^{out}$. We apply a branching strategy to find a set $\mathcal{Q}$ such that $\mathcal{X}\backslash {\mathcal{B}}_j\subseteq \mathcal{Q}$, and $\left|\mathcal{Q}\right|<2|\mathcal{X}\backslash {\mathcal{B}}_j|$. Then, a random variables set $\mathcal{S}$ is obtained by sampling random variables from $\mathcal{Q}$ independently and uniformly. And the set $\mathcal{X}\backslash {\mathcal{B}}_j\subseteq \mathcal{Q}$ can be replaced by a subset ${\mathcal{S}}^{*}$ of $\mathcal{S}$ from ${\mathcal{X}}_j^{out}$. Based on ${\mathcal{S}}^{*}$ and ${\tilde{\mathcal{X}}}_j^{in}$, the approximation center of ${\tilde{\mathcal{X}}}_j$ could be obtained. Therefore, the algorithm presented in this paper outputs a collection of size $O({(\frac{1891ek}{{ϵ}^2})}^{8k/ϵ}n)$ of candidate sets containing approximation centers, and has the running time $O({(\frac{1891ek}{{ϵ}^2})}^{8k/ϵ}nd)$.

Given an instance $(\mathcal{X},k,\mathbb{L})$ of the uncertain constrained k-means problem, $\mathbb{X}=\{{\mathcal{X}}_1,\dots ,{\mathcal{X}}_k\}$ denotes an optimal partition of $(\mathcal{X},k,\mathbb{L})$. There exist six parameters ($ϵ$, $\mathcal{Q}$, g, k, C, U) in our $\mathbf{cMeans}$, where $ϵ\in (0,1]$ is the approximate factor, $\mathcal{Q}$ is the input random variable set, g is the number of centers, k is the number of the clusters, C is the set of approximate cluster centers, and U is a collection of candidate sets including the approximate center. Let $M=\frac{6}{ϵ},N=\frac{79,380k}{{ϵ}^3}$, where M is the size of subsets of the sampling set and N is the size of the sampling set. Without loss of generality, assume that values of M and N are integers.

We use the branching strategy to seek out the approximate centers of clusters in $\mathbb{X}$. There exist two branches in our algorithm $\mathbf{cMeans}$, which can be seen in Figure 1. On one branch, a size N set ${\mathcal{S}}_1$ is obtained by sampling from $\mathcal{Q}$ uniformly and independently; ${\mathcal{S}}_2$ is constructed by ${\mathcal{S}}_1$ and M copies of each point in C. Moreover, we consider each subset ${\mathcal{S}}^{\prime }$ of size M of ${\mathcal{S}}_2$, and the centroid c of ${\mathcal{S}}^{\prime }$ is solved to represent the approximate center of ${\mathcal{X}}_{k-g+1}$, and our algorithm $\mathbf{cMeans}$($ϵ,\mathcal{Q},g-1,k,C\cup \left\{c\right\},U$) is used to obtain the remaining $g-1$ cluster centers.

On the other branch, for each random variable $X\in \mathcal{Q}$, we calculate the distance between X and C first. H denotes the set of all distances of random variables in $\mathcal{X}$ to C, where H is a multi-set. We should obtain the median value m for all values in H, which is the $\lfloor \left|H\right|/2\rfloor$-th element if all of the values in H are sorted. In the second branch, $\mathcal{Q}$ is divided into two parts, ${\mathcal{Q}}^{\prime }$ and ${\mathcal{Q}}^{″}$, based on m such that for $\forall X^{\prime }\in {\mathcal{Q}}^{\prime }$, $X^{″}\in {\mathcal{Q}}^{″}$, $dist(X^{\prime },C)\le dist(X^{″},C)$, where $|{\mathcal{Q}}^{\prime }|=\lceil \frac{|\mathcal{Q}|}{2}\rceil$, $|{\mathcal{Q}}^{″}|=\lfloor \frac{|\mathcal{Q}|}{2}\rfloor$. Subroutine $\mathbf{cMeans}$($ϵ,{\mathcal{Q}}^{″},g,k,C,U$) is used to obtain the remaining g cluster centers. Therefore, we present the specific algorithm for seeking out a collection of candidate sets in the Algorithm 1.

Algorithm 1:$\mathbf{cMeans}$($ϵ,\mathcal{Q},g,k,C,U$)

We investigate the success probability, correctness, and time complexity analysis of the algorithm $\mathbf{cMeans}$ in this section.

The following Lemmas from Lemma 6 to 16 are used to prove Lemma 5. We prove Lemma 5 via induction on j. For $j=1$, we can obtain ${\beta }_1\ge 1/k$ easily, and prove the success probability first.

From Lemma 6, an ${\mathcal{S}}^{*}$ with size $6/ϵ$ of ${\mathcal{S}}_2$ can be obtained, and the probability that all points in ${\mathcal{S}}^{*}$ are from ${\mathcal{X}}_1$ is at least $1/2$. Let $c_1$ denote the centroid of ${\mathcal{S}}^{*}$, and $\mathsf{\delta }=5/6$. For $|{\mathcal{S}}^{*}|=6/ϵ$, by Lemma 2, we conclude that $\left|\right|m_1-c_1{\left|\right|}^2\le \frac{1}{5}ϵ{\sigma }_1^2$ holds with a probability of at least $1/6$. Then, the probability that a subset ${\mathcal{S}}^{*}$ of size $6/ϵ$ of ${\mathcal{S}}_2$ can be found such that $\left|\right|m_1-c_1{\left|\right|}^2\le \frac{1}{5}ϵ{\sigma }_1^2\le \frac{9}{10}ϵ{\sigma }_1^2+\frac{1}{10{\beta }_{1}k}ϵ{\sigma }_{opt}^2$ holds is at least $1/12$. Therefore, we conclude that Lemma 5 holds for $j=1$.

Moreover, we assume that for $j\le j_0(1\le j_0)$, Lemma 5 holds with a probability of at least $1/{12}^j$. Considering the case $j=j_0+1$, we prove Lemma 5 by the following two cases: (1)$|{\mathcal{X}}_j^{out}|\le \frac{ϵ}{49}{\beta }_{j}n$; (2)$|{\mathcal{X}}_j^{out}|>\frac{ϵ}{49}{\beta }_{j}n$.