K-means: ¿Por qué minimizar el WCSS es maximizar la distancia entre clusters?

Question

Desde un punto de vista conceptual y algorítmico, entiendo cómo funciona K-means. Sin embargo, desde un punto de vista matemático, no entiendo por qué la minimización de las sumas de cuadrados dentro de un clúster maximizará necesariamente la distancia entre clústeres . En otras palabras, ¿puede alguien mostrar cómo este función es igual a la maximización de la distancia entre clusters? Sería útil ver una derivación que muestre todos los pasos o, por favor, indíqueme la(s) referencia(s) adecuada(s).

Actualización Encontré este Witten y Tibshirani referencia pero no es obvio cómo pasar de la ecuación 7 a la 8.

Answer 1

K-means se basa en el paradigma del análisis de la varianza. El ANOVA -tanto uni como multivariante- se basa en el hecho de que la suma de desviaciones al cuadrado en torno al gran centroide se compone de dicha dispersión en torno a los centroides de los grupos y de la dispersión de dichos centroides en torno al gran centroide: SStotal=SSdentro+SSentre . Por lo tanto, si SSwithin se minimiza entonces SSiempre entre se maximiza.

Se sabe que el SS de las desviaciones de algunos puntos en torno a su centroide (media aritmética) es directamente relacionado a la distancia euclidiana global al cuadrado entre los puntos: la suma de las desviaciones al cuadrado del centroide es igual a la suma de las distancias euclidianas al cuadrado por pares dividida por el número de puntos . (Esta es la extensión directa de la propiedad trigonométrica de centroide . Y esta relación se aprovecha también en el doble centrado de la matriz de distancia).

Por lo tanto, decir "SSbetween para los centroides (como puntos) se maximiza" es un alias para decir "el conjunto (ponderado) de distancias cuadradas entre los centroides se maximiza".

Nota: en SSbetween cada centroide se pondera por el número de puntos Ni en esa agrupación i . Es decir, cada centroide se cuenta Ni tiempos. Por ejemplo, con dos centroides en los datos, 1 y 2 , SSbetween = N1*D1^2+N2*D2^2 donde D1 y D2 son las desviaciones de los centroides respecto a la media general. De ahí viene la palabra "ponderada" del párrafo anterior.

Ejemplo

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.)

Answer 2

Lo que se busca es el Teorema de König-Huygens .