agrupamento com elementos iguais

Question

Suponha que temos um conjunto de observações: $\mathbf{X} = \{x_{1}, \dots, x_{n}\}\subseteq \mathbb{R}^{d}$, contendo $n$ observações para uma dimensionalidade fixa $d$. Suponha que temos algum número inteiro fixo$k$. O agrupamento k-means (com distância de l2) é o problema de encontrar centróides dos clusters$S_{1}, \dots, S_{k}$ que minimiza $$ cost(S_{1}, \dots, S_{1}) = \sum_{j=1}^{k}\sum_{x\in S_{j}}||x - q_{j}||^{2}, $$ Onde $q_{1}, \dots, q_{k} \in \mathbb{R}^{d}$ são os centróides, ou seja $q_{j} = \frac{1}{|S_{j}|}\sum_{x\in S_{j}}x$.

Suponha, lá em $\mathbf{X} = \{x_{1}, \dots, x_{n}\}$ existem elementos iguais $\{x\} \subset \mathbf{X}$.

É possível que em uma solução global (teórica) esses elementos sejam iguais uns aos outros $\{x\}$ pertencem a diferentes clusters?

Answer 1

Primeiro, precisamos distinguir entre a solução k-médias globalmente ótima e o resultado obtido de um algoritmo k-médias. Existem vários deles e, a menos que o conjunto de dados seja muito pequeno, eles fornecerão um ótimo local que não é necessariamente o global. (Você diz "global" em sua pergunta, então presumo que se refira à solução globalmente ideal; apenas para ter certeza.)

A resposta à sua pergunta começa com "não normalmente"; deles$\|x-q_j\|$-valores são obviamente iguais para todos $q_j$, então, uma vez que o algoritmo é convergido (ou o globalmente ideal $q_j$ são conhecidos), todos eles serão atribuídos aos seus mais próximos $q_j$, que é igual para todos eles.

Uma situação excepcional que não é coberta pelo argumento acima ocorre se não apenas vários $x$ são iguais, mas também estão a uma distância igual a dois ou mais $q_j$. Na verdade, não conheço nenhum algoritmo que, neste caso, possa atribuí-los a diferentes clusters, mas não posso excluir a existência de tais implementações.

Na verdade, não tentei provar isso, mas suspeito que o ótimo global nunca separará observações iguais, porque as chances são de que se observações iguais forem separadas, pode-se alcançar uma solução melhor colocando todas elas no cluster que tem a maioria deles (ou apenas qualquer cluster, se estiverem uniformemente distribuídos). Não parece fazer sentido que essas observações influenciem mais do que a média de um cluster (tornando-o potencialmente pior para a maioria das outras observações naquele cluster). Provavelmente se poderia provar isso passando uma tarde fazendo matemática, mas não há garantia aqui, apenas um palpite.

O que eu olhei é um número de exemplos 1-d com pontos iguais situados entre duas metades dos dados, como 1,2,3,3,4,5. Na verdade, você obtém uma solução melhor ($k=2$) em termos de custo se você colocar os dois 3 em um cluster com 1,2 ou 4,5, em vez de um à esquerda e outro à direita (você pode verificar isso computando explicitamente as funções de custo) .