# distortion function for k-means algorithm

I was reading Andrew Ng's ML lecture notes on K-mean clustering, in which the distortion function is defined as follow $$J(c,\mu) = \sum^m_{i=1} || x^{(i)} - \mu_{c^{(i)}}||^2$$

I am puzzled about the $L_2$ norm, since $|| x^{(i)} - \mu_{c^{(i)}}||^2$ would imply $\sum^m_{i=1} (x^{(i)} - \mu_{c^{(i)}})^2$ and this means that there would be two summations $\sum_{i=1}^m$ in the entire expression.

I am sensing that I have misunderstood something crucial here. Please point out the error. Thanks.

UPDATE: the problem has a given a training set $\{x^{(1)}, ..., x^{(m)}\}$, where $x^{(i)} \in \mathbb{R}^n$ and the cluster centroids are $\mu_1, \mu_2,...\mu_k \in \mathbb{R}^n$

• What are $x^{(i)}$ and $\mu_{c^{(i)}}$ ? Vectors ? If so, what is their dimension ? What is $m$ ?
– Pop
Commented Feb 26, 2014 at 12:20
• maybe the inner summation is summing over the $n$. But I am not sure about this Commented Feb 26, 2014 at 12:27

As the norm is applied to vectors in dimension $n$, $$|| x^{(i)} - \mu_{c^{(i)}}||^2 = \sum^n_{j=1} (x^{(i)}_j - \mu_{c^{(i)},j})^2$$
with $x^{(i)} = (x^{(i)}_1,..., x^{(i)}_n)$ and $\mu_{c^{(i)}}=(\mu_{c^{(i)},1},..., \mu_{c^{(i)},n})$.
The summation is first on the $m$ points of the sample ($x^{(i)}$) and then on their $n$ components, sothat: $$J(c,\mu) =\sum^m_{i=1}\sum^n_{j=1} (x^{(i)}_j - \mu_{c^{(i)},j})^2$$