Zwei k-Means-Kostenfunktionen sind gleich

Question

So lerne ich über den k-Means-Algorithmus für das Clustering und habe ein paar verschiedene Kostenfunktionen gesehen, die verwendet werden können, insbesondere $$ J_ {avg} = \ sum_ {i = 0}^k \ sum_ {x \ in C_i} d (x, m_j)^2 $$$$ J_ {IC} = \ sum_ {i = 0}^k \ frac {1} {| C_j | } \ sum_ {x \ in C_i} \ sum_ {x '\ in C_i} d (x, x')^2. $$ Jetzt versuche ich zu zeigen, dass wenn $ m_j = \ frac {1} {C_j} \ sum_ {x \ in C_j} x $ dann $ J_ {IC} = 2J_ {avg}. $ Das macht für mich einen intuitiven Sinn, da es der Unterschied zwischen der durchschnittlichen Entfernung zur Mitte und der durchschnittlichen Entfernung zwischen zwei Punkten zu sein scheint doppelt so groß sein wie in der Mitte). Würde mich über jede Hilfe freuen, danke!

Answer 1

Damit die Kostenfunktionen gleichwertig sind, müssen sie nicht exakt gleich sein, nur monoton verbunden sein, so dass die Optimierung die andere optimiert.

SUM_ij (Xi - Xj)^2 = SUM_ij (Xi - x + x - Xj)^2 = SUM_ij (Xi - x)^2 + (Xj - x)^2 + 2 (Xi - x). (x - Xj)

Wenn x der Mittelwert von Xi ist, dann SUM_j (x - Xj) = 0, so verschwindet der Skalarproduktterm und man erhält die Art der Verbindung zwischen der Summe der quadratischen Abstände vom Mittelwert und die Summe der quadratischen Abstände zwischen zwei beliebigen Punkten, von denen ich glaube, dass Sie sie brauchen.