1
$\begingroup$

Let $K\in\mathbb N^+$ be a parameter.

Given a distribution $q$ over the real numbers, K-means clustering aims to find $K$ centroids $c_1,\ldots,c_k\in\mathbb R$ that minimize $$ \int_{-\infty}^\infty q(x)\cdot \min\{(x-c_i)^2\mid i\in\{1,\ldots,k\}\}dx. $$

We can, without loss of generality, assume that $c_1\le c_2\le\ldots\le c_k$.

What are the resulting centroids for the standard normal distribution $q=N(0,1)$?

The solution for $K=2$ is given by $c_1=-\sqrt{2/\pi}$ and $c_2=\sqrt{2/\pi}$. The reason is that the distribution is symmetric around $0$ and the expected value given that the variable is positive equals the mean of a half-normal random variable. I am interested in computing the result for a larger $K$, e.g.,

  • What are the centroids for $K=4$?

Using WolframAlpha, after some simplifications, it seems that the solution is approximately $c_1\approx -1.51, c_2\approx-0.453,c_3\approx 0.453, c_4\approx1.51$.

Improve this question
$\endgroup$
3
  • $\begingroup$ Can the downvoter please give feedback on what is wrong with the question? $\endgroup$
    – R B
    Commented Jun 9, 2021 at 11:43
  • $\begingroup$ I did not downvote, but if this is simply a matter of a numerical optimization, like you indicated you did yourself using WolframAlpha, then it's not clear what you would expect from this site. $\endgroup$
    – Carlo Beenakker
    Commented Jun 9, 2021 at 12:31
  • $\begingroup$ @CarloBeenakker - I am interested in finding the quantity. I was able to approximate it, just for $K=4$, but this approach is not suitable for general $k$ and doesn't give a closed-form quantity for even for $K=4$. $\endgroup$
    – R B
    Commented Jun 9, 2021 at 13:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .