<p>First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations <a href="http://sarielhp.org/p/06/relative/" rel="nofollow">http://sarielhp.org/p/06/relative/</a> and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - its well known, but i dont know a ref for that). Secondly, relative approximation sample in this case, guarantees that if the sample fails, then $k$ is too small. So, do exponential search for the right value of $k$, specifically, start with $k_i = 2^i$, and let $R_i$ be the the $i$th sample of size $n_i = O( \frac{kd \log k}{\epsilon} \log \frac{i}{\epsilon} )$ (the $i$ is not a typo).</p>

<p>Let $\alpha$ be the minimum $i$ for which the sample succeeds using the black box. Now, use brute force (on the sample) to find the minimum $k\leq k_\alpha$ for which the sample works. And this is your desired $k$. You need to carefully account for the probability of success, but thats why the $i$ is there - its one of these standard geometric summation stuff. </p>

<p>The $i$ can be avoided -- indeed, the probability that $\alpha$ is bigger by $\Delta$ than its correct value is smaller than $2^{-\Delta}$. If you do that, then the sample you are going to use is of the right size with good probability. That is, if the minimum $k$ for which you can cover more than $(1-\epsilon)n$ of the points is $\kappa$, then the sample the algorithm uses is $O\left( \frac{\kappa d \log \kappa}{\epsilon} \log \frac{1}{\epsilon} \right)$.</p>

<p>There is some added fuzzyness in the answer of this algorithm. The returned answer $\kappa$ is the minimum such that any value of $k &lt; \kappa$, is say $(1-\epsilon/2)$-far from from being k-clustered. I assume this is OK. </p>

<p>In practice you would do something different. Hmm. Something to think about....</p>

CC BY-SA 3.0
2014-09-03T11:30:19.037Z
Just to be certain I understand -- in the expression of $n_i$, the $k$'s are $k_i$'s, aren't they?
Clement C.
CC BY-SA 3.0
2014-09-04T08:02:29.797Z
@Sariel Har-Peled Thanks for your reply! But, I don't see any easy proof of the following claim: **If a set of points are $\kappa$-clustrable, then $\forall$ $k<\kappa$, points are $(1−\frac{\epsilon}{2})$-far from from being $k$-clustered.** Could you suggest some intuition or some reference to prove the claim.
Ram
CC BY-SA 3.0
2014-09-06T18:01:00.490Z
Shouldn't this be *not* κ-clustrable?
Sariel Har-Peled
CC BY-SA 3.0
2014-09-02T03:56:02.370Z
2014-09-02T03:56:02.370Z
Sariel Har-Peled
<p>We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of <a href="http://www.tau.ac.il/~nogaa/PDFS/adpr1.pdf" rel="nofollow">paper</a>) which consider a promise version of the above problem. The algorithm samples $O(\frac{kd}{\epsilon}\log \frac{kd}{\epsilon})$ many points from the set, and distinguish between following two cases with probability at least $\frac{2}{3}$:</p>

<p>-algorithm ACCEPTS, if all the points are $k$-clusterable.</p>

<p>-algorithm REJECTS, if points are $\epsilon$-far from $k$-clusterable, <em>i.e.</em> any $k$ unit balls covers at most $(1-\epsilon)n$ points.</p>

<p>Now, using the above algorithm as a subroutine can we approximate the value of $k$ (number of clusters), <em>i.e.,</em> if we can ignore at most $\epsilon n$ points (because now we don't have the promised version of the input) from the input,
then we need to determine the number of clusters in the input. </p>

<p>(I was thinking to do some kind of binary search over $k$, start with k=2, if algorithm ACCEPTS then k=2, if REJECTS then try for k=4 and so on.)</p>

<p>Pls let me know if there is any confusion in the problem.</p>

CC BY-SA 3.0
2014-09-01T06:57:23.037Z
What are you asking?
R B
CC BY-SA 3.0
2014-09-01T07:02:58.550Z
@RB  We have given (as a black-box) a set of points which are clustered, but we don't know the number of clusters. Our goal is to find an approximate value of $k$ just by looking only sublinear/$O(1)$ many points, and using testing algorithm algorithm as subroutine.
Ram
CC BY-SA 3.0
2014-09-01T15:12:59.310Z
@Ram: do you know a reasonable upper bound $K$ on $k$? (by default, $K=n$ works, but it will introduce a dependence on $n$, namely $\log\log n$). For the binary search, wouldn't the following work: set $\delta=1/(3\log K)$, and amplify the probability of success of the subroutine to $1-\delta$ by standard techniques (blowup of a factor $\log(1/\delta)$ in the sample complexity). Then try $k=1,2\dots,K$ (wlog, $K$ is a power of $2$), and take $k^\ast$ to be the last value for which the test accepts. With probability at least $1-K\delta=2/3$, you got a 2-approximation of the "right $k$".
Clement C.
<clustering><property-testing><sample-complexity>
Determining the number of clusters using property testing algorithm
Ram
# Determining the number of clusters using property testing algorithm

(Asked by: username_0 on 2014-09-01)

We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of [paper](http://www.tau.ac.il/~nogaa/PDFS/adpr1.pdf)) which consider a promise version of the above problem. The algorithm samples $O(\frac{kd}{\epsilon}\log \frac{kd}{\epsilon})$ many points from the set, and distinguish between following two cases with probability at least $\frac{2}{3}$:

-algorithm ACCEPTS, if all the points are $k$-clusterable.

-algorithm REJECTS, if points are $\epsilon$-far from $k$-clusterable, *i.e.* any $k$ unit balls covers at most $(1-\epsilon)n$ points.

Now, using the above algorithm as a subroutine can we approximate the value of $k$ (number of clusters), *i.e.,* if we can ignore at most $\epsilon n$ points (because now we don't have the promised version of the input) from the input,
then we need to determine the number of clusters in the input.

(I was thinking to do some kind of binary search over $k$, start with k=2, if algorithm ACCEPTS then k=2, if REJECTS then try for k=4 and so on.)

Pls let me know if there is any confusion in the problem.

**Tags:** clustering, property-testing, sample-complexity

> **Comments:**
> **username_1**: What are you asking?  
> **username_0**: @RB  We have given (as a black-box) a set of points which are clustered, but we don't know the number of clusters. Our goal is to find an approximate value of $k$ just by looking only sublinear/$O(1)$ many points, and using testing algorithm algorithm as subroutine.  
> **username_2**: @username_0: do you know a reasonable upper bound $K$ on $k$? (by default, $K=n$ works, but it will introduce a dependence on $n$, namely $\log\log n$). For the binary search, wouldn't the following work: set $\delta=1/(3\log K)$, and amplify the probability of success of the subroutine to $1-\delta$ by standard techniques (blowup of a factor $\log(1/\delta)$ in the sample complexity). Then try $k=1,2\dots,K$ (wlog, $K$ is a power of $2$), and take $k^\ast$ to be the last value for which the test accepts. With probability at least $1-K\delta=2/3$, you got a 2-approximation of the "right $k$".  

---

## 1 answers

### Answer by username_3 on 2014-09-02. Score: 4 | Accepted answer

First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations <http://sarielhp.org/p/06/relative/> and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - its well known, but i dont know a ref for that). Secondly, relative approximation sample in this case, guarantees that if the sample fails, then $k$ is too small. So, do exponential search for the right value of $k$, specifically, start with $k\_i = 2^i$, and let $R\_i$ be the the $i$th sample of size $n\_i = O( \frac{kd \log k}{\epsilon} \log \frac{i}{\epsilon} )$ (the $i$ is not a typo).

Let $\alpha$ be the minimum $i$ for which the sample succeeds using the black box. Now, use brute force (on the sample) to find the minimum $k\leq k\_\alpha$ for which the sample works. And this is your desired $k$. You need to carefully account for the probability of success, but thats why the $i$ is there - its one of these standard geometric summation stuff.

The $i$ can be avoided -- indeed, the probability that $\alpha$ is bigger by $\Delta$ than its correct value is smaller than $2^{-\Delta}$. If you do that, then the sample you are going to use is of the right size with good probability. That is, if the minimum $k$ for which you can cover more than $(1-\epsilon)n$ of the points is $\kappa$, then the sample the algorithm uses is $O\left( \frac{\kappa d \log \kappa}{\epsilon} \log \frac{1}{\epsilon} \right)$.

There is some added fuzzyness in the answer of this algorithm. The returned answer $\kappa$ is the minimum such that any value of $k < \kappa$, is say $(1-\epsilon/2)$-far from from being k-clustered. I assume this is OK.

In practice you would do something different. Hmm. Something to think about....

> **Comments:**
> **username_2**: Just to be certain I understand -- in the expression of $n_i$, the $k$'s are $k_i$'s, aren't they?  
> **username_0**: @username_3 Thanks for your reply! But, I don't see any easy proof of the following claim: **If a set of points are $\kappa$-clustrable, then $\forall$ $k<\kappa$, points are $(1−\frac{\epsilon}{2})$-far from from being $k$-clustered.** Could you suggest some intuition or some reference to prove the claim.  
> **username_3**: Shouldn't this be *not* κ-clustrable?  

---

