10
$\begingroup$

From a conceptual and algorithmic standpoint, I understand how K-means works. However, from a mathematical standpoint, I don't understand why minimizing the WCSS (within-cluster sums of squares) will necessarily maximize the distance between clusters. In other words, can somebody show how this function is equal to maximizing the distance between clusters? It would be helpful to see a derivation that shows all of the steps or please point me to the appropriate reference(s).

Update I found this Witten and Tibshirani reference but it isn't obvious how to get from equation 7 to equation 8.

Improve this question
$\endgroup$
2
  • $\begingroup$ Isn't SSbetween the largest when each data point is a cluster? If so, then minimizing SSwithin (or maximizing SSbeteen) would tend to have each individual data point as a cluster... Am I missing anything here? Thanks for any clarification. $\endgroup$
    – user192257
    Commented Jan 20, 2018 at 18:06
  • $\begingroup$ @user192257 Your conclusion implicitly uses properties of squared Euclidean distances (namely, the Pythagorean Theorem) that are not shared with other distances. These properties are highlighted in the answers and their references. $\endgroup$
    – whuber ♦
    Commented Jan 20, 2018 at 19:07

2 Answers 2

Reset to default
8
$\begingroup$

K-means is all about the analysis-of-variance paradigm. ANOVA - both uni- and multivariate - is based on the fact that the sum of squared deviations about the grand centroid is comprised of such scatter about the group centroids and the scatter of those centroids about the grand one: SStotal=SSwithin+SSbetween. So, if SSwithin is minimized then SSbetween is maximized.

SS of deviations of some points about their centroid (arithmetic mean) is known to be directly related to the overall squared euclidean distance between the points: the sum of squared deviations from centroid is equal to the sum of pairwise squared Euclidean distances divided by the number of points. (This is the direct extension of the trigonometric property of centroid. And this relation is exploited also in the double centering of distance matrix.)

Thus, saying "SSbetween for centroids (as points) is maximized" is alias to say "the (weighted) set of squared distances between the centroids is maximized".

Note: in SSbetween each centroid is weighted by the number of points Ni in that cluster i. That is, each centroid is counted Ni times. For example, with two centroids in the data, 1 and 2, SSbetween = N1*D1^2+N2*D2^2 where D1 and D2 are the deviations of the centroids from the grand mean. That where word "weighted" in the former paragraph stems from.

Example

Data (N=6: N1=3, N2=2, N3=1)
        V1            V2       Group
       2.06          7.73          1
        .67          5.27          1
       6.62          9.36          1
       3.16          5.23          2
       7.66          1.27          2
       5.59          9.83          3

SSdeviations
        V1            V2            Overall
SSt   37.82993333 + 51.24408333 = 89.07401666
SSw   29.50106667 + 16.31966667 = 45.82073333
SSb   8.328866667 + 34.92441667 = 43.25328333

SSt is directly related to the squared Euclidean distances between the data points:

Matrix of squared Euclidean distances
     .00000000    7.98370000   23.45050000    7.46000000   73.09160000   16.87090000 
    7.98370000     .00000000   52.13060000    6.20170000   64.86010000   45.00000000 
   23.45050000   52.13060000     .00000000   29.02850000   66.52970000    1.28180000 
    7.46000000    6.20170000   29.02850000     .00000000   35.93160000   27.06490000 
   73.09160000   64.86010000   66.52970000   35.93160000     .00000000   77.55850000 
   16.87090000   45.00000000    1.28180000   27.06490000   77.55850000     .00000000 

Its sum/2, the sum of the distances = 534.4441000
534.4441000 / N = 89.07401666 = SSt

The same reasoning holds for SSb.

Matrix of squared Euclidean distances between the 3 group centroids (see https://stats.stackexchange.com/q/148847/3277)
     .00000000   22.92738889   11.76592222 
   22.92738889     .00000000   43.32880000 
   11.76592222   43.32880000     .00000000 

3 centroids are 3 points, but SSb is based on N points (propagated centroids):
N1 points representing centroid1, N2 points representing centroid2 and N3 representing centroid3.
Therefore the sum of the distances must be weighted accordingly:
N1*N2*22.92738889 + N1*N3*11.76592222 + N2*N3*43.32880000 = 259.51969998
259.51969998 / N = 43.25328333 = SSb

Moral in words: maximizing SSb is equivalent to maximizing
the weighted sum of pairwise squared distances between the centroids.
(And maximizing SSb corresponds to minimizing SSw, since SSt is constant.)
Improve this answer
$\endgroup$
-1
$\begingroup$

What you are looking for is the König-Huygens theorem.

cf. p. 3 in this article for an explicit reference to the Hyugens formula.

Improve this answer
$\endgroup$
2
  • $\begingroup$ cf. p. 3 in this article for an explicit reference to the Hyugens formula. $\endgroup$
    – mic
    Commented Jun 23, 2015 at 9:17
  • $\begingroup$ As of 2022, the link leads to an empty page and the comment to a 'page not found'. $\endgroup$
    – Diego Queiroz
    Commented Dec 13, 2022 at 17:19

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.