Sob quais condições o K-significa clustering invariante de transformação?

Dado um conjunto de pontos de dados $X = \{x_1, x_2, \ldots, x_m\}$ Onde $x_i \in \mathbb{R}^d$ corremos K-significa em $X$e obtenha os clusters .$c_1, c_2, \ldots, c_k$

Agora, se criar um novo conjunto de dados onde e e executar K-means em para obter aglomerados .$Y = \{y_1, y_2, \ldots, y_m\}$$y_i = Ax_i + b$$y_i \in \mathbb{R}^d$$Y$$g_1, g_2, \ldots g_k$

Em que condições de e temos a garantia de obter os mesmos agrupamentos?$A$$b$

Vamos supor que K-means esteja usando a distância euclidiana e tenha as mesmas condições iniciais em ambos os algoritmos, ou seja, se os centros iniciais de X forem , os centros iniciais de Y serão onde .$c^0_1, \ldots, c^0_k$$g^0_1, \ldots, g^0_k$$g^0_i = Ac^0_i + b$

Até agora, pensei que tivesse que ter classificação completa possa ser qualquer vetor. No entanto, não pude provar isso.$A$$b$

A resposta depende do seu algoritmo K-means, mas o que se segue deve funcionar para algoritmos padrão.

Você obterá o mesmo resultado se sua transformação atender a duas condições:$T$

1. Ele preserva as distâncias: , onde é sua métrica, diga.$d(z,w) = d(T(z),T(w))$$d$$d(z,w) = \|z-w\|$
2. Ele preserva as médias: se é uma combinação convexa que .$\sum_i p_i z_i$$T(\sum_i p_i z_i) = \sum_i p_i T(z_i)$

Você pode verificar isso revisando o algoritmo, mostrando que ele sempre faz as mesmas escolhas.