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.


  • $\begingroup$ 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)? $\endgroup$ – rapaio Jun 27 '14 at 9:18
  • $\begingroup$ Yes, I edited the question. $\endgroup$ – remo Jun 27 '14 at 12:52
  • $\begingroup$ 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? $\endgroup$ – ttnphns Jun 29 '14 at 7:41

If you use k-medians instead of k-means, you can use absolute deviations.

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.

  • $\begingroup$ 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? $\endgroup$ – remo Jun 27 '14 at 19:48
  • $\begingroup$ 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... $\endgroup$ – ttnphns Jun 29 '14 at 7:48
  • $\begingroup$ @remo: Because quadratic mean (RMS) is the square root of the average squared value; not the other way round. On your lucky day (="nicely behaved data") quadratic mean and arithmetic mean do not make much of a difference. $\endgroup$ – Has QUIT--Anony-Mousse Jun 29 '14 at 13:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.