Say we have $N$ points in 4 clusters. Each cluster has a small radius $\delta$ and a large distance between the clusters say $B$.

What would be the cost of the optimal clustering?

Apparently the answers is $\approx O(\delta^2N)$ but was unsure why if in the general case, it was independent of the number of clusters k.

I was wondering if someone understood if the above approximation was always independent of the number of clusters $k$?

It's not mentioned what cost function to use but I am assuming that it's euclidean distance squared.

I think that the answer is independent of the number of clusters but I was not sure if my argument is correct. The argument is the following:

The cost for a single cluster is:

$cost(C_j) = \sum_{i \in C_j}\| x^{(i)} - z^{(j)}\|^2 \leq |C_j| 4\delta^2$

Thus the cost for the clustering is:

$cost(C_i, ..., C_k)= \sum^k_{j=1}cost(C_j) \leq \sum^k_{j=1} |C_j| 4\delta^2 = 4\delta^2\sum^k_{j=1}|C_j| = 4\delta^2N = O(\delta^2N)$

Which seems to be independent of the number of clusters. Right? Does this seem correct?

If it is correct and you want to provide more insight of why it might be obvious or some intuition on it, feel free to do it!

Thanks in advance.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.