1
$\begingroup$

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

$\endgroup$
3
  • $\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
    Commented Jun 27, 2014 at 9:18
  • $\begingroup$ Yes, I edited the question. $\endgroup$
    – remo
    Commented Jun 27, 2014 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
    Commented Jun 29, 2014 at 7:41

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\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
    Commented Jun 27, 2014 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
    Commented Jun 29, 2014 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$ Commented Jun 29, 2014 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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