Under what conditions is K-means clustering transformation-invariant? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T14:27:33Z https://cs.stackexchange.com/feeds/question/64843 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/64843 8 Under what conditions is K-means clustering transformation-invariant? Ana Echavarria https://cs.stackexchange.com/users/39631 2016-10-19T16:13:20Z 2016-10-19T21:24:11Z <p>Given a set of data points $X = \{x_1, x_2, \ldots, x_m\}$ where $x_i \in \mathbb{R}^d$ we run K-means on $X$ and obtain the clusters $c_1, c_2, \ldots, c_k$.</p> <p>Now, if we create a new dataset $Y = \{y_1, y_2, \ldots, y_m\}$ where $y_i = Ax_i + b$ and $y_i \in \mathbb{R}^d$ and run K-means on $Y$ to get clusters $g_1, g_2, \ldots g_k$.</p> <p>Under what conditions of $A$ and $b$ are we guaranteed to get the same clusters?</p> <p>Let's assume that K-means is using the euclidean distance and has same initial conditions on both algorithms, that is, if the initial centers for X are $c^0_1, \ldots, c^0_k$ then the initial centers for Y are $g^0_1, \ldots, g^0_k$ where $g^0_i = Ac^0_i + b$.</p> <p>So far I've thought that $A$ has to be full rank and $b$ can be any vector. However, I haven't been able to prove it.</p> https://cs.stackexchange.com/questions/64843/-/64844#64844 6 Answer by Yuval Filmus for Under what conditions is K-means clustering transformation-invariant? Yuval Filmus https://cs.stackexchange.com/users/683 2016-10-19T16:23:35Z 2016-10-19T16:23:35Z <p>The answer depends on your K-means algorithm, but what follows should work for standard algorithms.</p> <p>You will get the same result if your transformation $T$ satisfies two conditions:</p> <ol> <li>It preserves distances: $d(z,w) = d(T(z),T(w))$, where $d$ is your metric, say $d(z,w) = \|z-w\|$.</li> <li>It preserves averages: if $\sum_i p_i z_i$ is a convex combination that $T(\sum_i p_i z_i) = \sum_i p_i T(z_i)$.</li> </ol> <p>You can check this by going over the algorithm, showing that it always makes the same choices.</p>