On the connection between SSE and absolute deviation from the centroids

Is there any connection between sum of squared error SSE and the absolute deviation from the centroids after clustering.

More formally, I have clustered $T=\{x_i\}, i\in\{1,\ldots,n\}$ and the results are $c$ clusters: $T^C=\{C_j\}, j\in\{1,\ldots,c\}$ (As a side note, I appreciate your comments on the notations). All records $x_i$ are assigned to clusters $G_j$ with the centroids $C_j=MEAN(x_i), x_i\in G_j$, so SSE is calculated as:

$\sum\limits_{\underset{x_i\in G_j}{i=1}}^{n}(x_i-C_j)^2$

I am seeking a way to calculate/estimate the following:

$\sum\limits_{\underset{x_i\in G_j}{i=1}}^{n}|x_i-C_j|$

However, I am not sure whether there is such a connection or not.

My algorithm is something similar to K-means and Euclidean distances are used.

Thanks

• Which clustering algorithm did you used (from your words it looks like a k-means)? Which distance did you used (it looks like euclidean distance on numeric variables)? Commented Jun 27, 2014 at 9:18
• Yes, I edited the question.
– remo
Commented Jun 27, 2014 at 12:52
• I did not understand it. What prevents you from computing the sum of absolute deviations? Is there some quantity you don't know for that? Commented Jun 29, 2014 at 7:41

It's a pretty straightforward adaption of the algorithm (just use the median in each dimension instead of the mean) and optimizes $L_1$ norms.
Arithmetic mean and quadratic mean are obviously closely related, and yield similar values on nicely behaved data. Then $\sqrt{\frac{1}{nd}SSE}\approx \frac{1}{nd} SAE$. If your data is not nicely behaved, then they will be more different.
• Thank you for your answer. Would you please let me know why you said $\sqrt{\frac{1}{nd}SSE}$ and not $\frac{1}{nd}\sqrt{SSE}$. What is more formal meaning of nicely behaved data?
• It is unclear whether $SSE$ and/or $SAE$ in your formula is about the mean (centroid) or about the geometric median. And what is "nicely behaved". Also, it seems to me that the OP was about centroids only... Commented Jun 29, 2014 at 7:48