K-bedeutet: Warum minimiert die Minimierung von WCSS die Entfernung zwischen Clustern?

7

Aus konzeptioneller und algorithmischer Sicht verstehe ich, wie K-means funktioniert. Aus mathematischer Sicht verstehe ich jedoch nicht, warum das Minimieren des WCSS (Quadratsummen innerhalb des Clusters) notwendigerweise den Abstand zwischen Clustern maximiert . Mit anderen Worten, kann jemand zeigen, wie diese Funktion der Maximierung des Abstands zwischen Clustern entspricht? Es wäre hilfreich, eine Ableitung zu sehen, die alle Schritte zeigt, oder mich auf die entsprechenden Referenzen zu verweisen.

Update Ich habe diese Referenz von Witten und Tibshirani gefunden, aber es ist nicht offensichtlich, wie ich von Gleichung 7 zu Gleichung 8 komme.

clustering k-means distance sums-of-squares euclidean Krautsalat
quelle
Ist SS zwischen den größten nicht, wenn jeder Datenpunkt ein Cluster ist? Wenn ja, dann würde das Minimieren von SS innerhalb (oder das Maximieren von SSbeteen) dazu neigen, jeden einzelnen Datenpunkt als Cluster zu haben ... Vermisse ich hier etwas? Vielen Dank für jede Klarstellung.
user192257
@ user192257 Ihre Schlussfolgerung verwendet implizit Eigenschaften von euklidischen Quadratabständen (nämlich den Satz von Pythagoras), die nicht mit anderen Abständen geteilt werden. Diese Eigenschaften werden in den Antworten und ihren Referenzen hervorgehoben.
whuber

Antworten:

5

Bei K-means dreht sich alles um das Varianzanalyse-Paradigma. ANOVA - sowohl uni- als auch multivariat - basiert auf der Tatsache, dass die Summe der quadratischen Abweichungen um den großen Schwerpunkt aus einer solchen Streuung um die Gruppenschwerpunkte und der Streuung dieser Schwerpunkte um den großen Schwerpunkt besteht: SStotal = SSwithin + SSbetween . Wenn also SSwithin minimiert wird, wird SSbetween maximiert.

Es ist bekannt, dass die SS der Abweichungen einiger Punkte um ihren Schwerpunkt (arithmetisches Mittel) in direktem Zusammenhang mit dem gesamten euklidischen Quadratabstand zwischen den Punkten steht: Die Summe der quadratischen Abweichungen vom Schwerpunkt entspricht der Summe der paarweisen quadratischen euklidischen Abstände geteilt durch die Zahl von Punkten . (Dies ist die direkte Erweiterung der trigonometrischen Eigenschaft des Schwerpunkts . Diese Beziehung wird auch bei der doppelten Zentrierung der Distanzmatrix ausgenutzt .)

Das Sprichwort "SS zwischen Zentroiden (als Punkte) wird maximiert" bedeutet daher "der (gewichtete) Satz quadratischer Abstände zwischen den Zentroiden wird maximiert".

Hinweis: In SS zwischen wird jeder Schwerpunkt mit der Anzahl der Punkte Niin diesem Cluster gewichtet i. Das heißt, jeder Schwerpunkt wird Nimal gezählt . Zum Beispiel mit zwei Schwerpunkten in den Daten 1und 2SSbetween = N1*D1^2+N2*D2^2wo D1und D2sind die Abweichungen der Schwerpunkte vom großen Mittelwert. Das, woher das Wort "gewichtet" im vorherigen Absatz stammt.

Beispiel

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