Por que o algoritmo de agrupamento k-means usa apenas a métrica de distância euclidiana?

Existe um propósito específico em termos de eficiência ou funcionalidade porque o algoritmo k-means não usa, por exemplo, (des) semelhança de cosseno como uma métrica de distância, mas apenas pode usar a norma euclidiana? Em geral, o método K-means está em conformidade e correto quando outras distâncias além da Euclidiana são consideradas ou usadas?

[Adição por @ttnphns. A questão é dupla. "Distância (não) euclidiana" pode dizer respeito à distância entre dois pontos de dados ou à distância entre um ponto de dados e um centro de cluster. Ambas as formas foram tentadas abordar as respostas até agora.]

O procedimento K-Means - que é um método de quantização vetorial frequentemente usado como um método de agrupamento - não usa explicitamente as distâncias entre pares, em pontos de dados em p / p (em contraste com os agrupamentos hierárquicos e alguns outros que permitem a medição arbitrária da proximidade). Isso equivale a atribuir pontos repetidamente ao centróide mais próximo, usando a distância euclidiana dos pontos de dados para um centróide . No entanto, K-Means é implicitamente baseado em distâncias euclidianas em pares , em pontos de dados, porque a soma dos desvios quadrados do centróide é igual à soma das distâncias euclidianas quadradas em pares, divididas pelo número de pontos. O termo "centróide" é ele próprio da geometria euclidiana. É uma média multivariada no espaço euclidiano. O espaço euclidiano é sobre distâncias euclidianas. As distâncias não euclidianas geralmente não abrangem o espaço euclidiano. É por isso que K-Means é apenas para distâncias euclidianas.

Mas uma distância euclidiana entre dois pontos de dados pode ser representada de várias maneiras alternativas . Por exemplo, está intimamente ligado ao produto cosseno ou escalar entre os pontos. Se você tem cosseno, covariância ou correlação, sempre pode (1) transformá-lo em distância euclidiana (ao quadrado) e, em seguida, (2) criar dados para essa matriz de distâncias euclidianas (por meio das coordenadas principais ou outras formas de métricas Escala Multidimensional) a (3) insira esses dados no cluster K-Means. Portanto, é possível fazer o K-Means "trabalhar com" cossenos aos pares ou algo assim; de fato, essas implementações do cluster K-Means existem. Veja também sobre a implementação "K-means for distance matrix".

É possível programar meios K de uma maneira que calcule diretamente na matriz quadrada de distâncias euclidianas aos pares, é claro. Mas ele funcionará lentamente e, portanto, a maneira mais eficiente é criar dados para essa matriz de distância (convertendo as distâncias em produtos escalares e assim por diante - o passe descrito no parágrafo anterior) - e depois aplicar o procedimento padrão de meios K para esse conjunto de dados.

Observe que eu estava discutindo o tópico sobre se a dissimilaridade euclidiana ou nãouclidiana entre pontos de dados é compatível com K-means. Está relacionado à questão, mas não exatamente a mesma, de saber se desvios nãouclidianos do centróide (no sentido amplo, central ou quase-centróide) podem ser incorporados em meios K ou "meios K modificados".

Veja a pergunta relacionada K-means: Por que minimizar o WCSS está maximizando a Distância entre os clusters? .

Veja também a resposta @ttnphns para uma interpretação dos meios k que realmente envolve distâncias euclidianas ponto a ponto.

A maneira como k-means é construído não se baseia em distâncias .

K-means minimiza a variação dentro do cluster. Agora, se você olhar para a definição de variância, ela é idêntica à soma das distâncias euclidianas quadradas do centro. (@ttnphns resposta refere-se a distâncias euclidianas em pares!)

A idéia básica do k-means é minimizar os erros ao quadrado . Não há "distância" envolvida aqui.

Por que não é correto usar distâncias arbitrárias: porque o k-means pode parar de convergir com outras funções de distância . A prova comum de convergência é assim: a etapa de atribuição e a etapa de atualização média otimizam o mesmo critério. Existe um número finito de tarefas possíveis. Portanto, ele deve convergir após um número finito de melhorias. Para usar esta prova para outras funções de distância, você deve mostrar que a média (nota: k- significa ) também minimiza suas distâncias.

Se você está procurando uma variante de k-means à distância de Manhattan, existem k-medianas. Porque a mediana é um melhor estimador L1 conhecido.

Se você deseja funções de distância arbitrárias, dê uma olhada no k-medoids (aka: PAM, particionando em torno do medoids). O medóide minimiza distâncias arbitrárias (porque é definido como o mínimo), e só existe um número finito de possíveis medoóides também. É muito mais caro que a média, no entanto.

Eu posso ser um pouco pedante aqui, mas K-means é o nome dado a um algoritmo específico que atribui rótulos a pontos de dados, de modo que as variações de cluster sejam minimizadas, e não é o nome de uma "técnica geral".

O algoritmo K-means foi proposto de forma independente a partir de vários campos, com fortes interpretações aplicáveis ​​ao campo. Acontece que também é uma distância euclidiana do centro. Para uma breve história do K-means, leia Data Clustering: 50 anos além do K-means

Há uma infinidade de outros algoritmos de cluster que usam métricas diferentes do Euclidiano. O caso mais geral que conheço é o uso de Bregman Divergences para clustering, do qual Euclidean é um caso especial.

Uma vez que, aparentemente, essa é agora uma pergunta canônica, e ainda não foi mencionada aqui:

Uma extensão natural dos meios k para usar métricas de distância diferentes da distância euclidiana padrão em é usar o truque do kernel . Isso se refere à idéia de mapear implicitamente as entradas para um espaço Hilbert de alta ou infinita dimensão, onde as distâncias correspondem à função de distância que queremos usar e executar o algoritmo nesse local. Ou seja, deixando seja algum mapa de recursos, de modo que a métrica desejada possa ser escrita , executamos k-means nos pontos . Em muitos casos, não podemos calcular o mapa explicitamente, mas nós podemos$\mathbb R^d$$\varphi : \mathbb R^p \to \mathcal H$$d$$d(x, y) = \lVert \varphi(x) - \varphi(y) \rVert_{\mathcal H}$$\{ \varphi(x_i) \}$$\varphi$calcule o kernel . Nem todas as métricas de distância se encaixam nesse modelo, mas muitas se encaixam, e existem funções definidas em strings, gráficos, imagens, distribuições de probabilidade e muito mais ...$k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$

Nesta situação, no algoritmo k-means padrão (Lloyd's), podemos atribuir pontos facilmente aos seus clusters, mas representamos os centros de cluster implicitamente (como combinações lineares dos pontos de entrada no espaço de Hilbert). Encontrar a melhor representação no espaço de entrada exigiria encontrar uma média de Fréchet , o que é bastante caro. Portanto, é fácil obter atribuições de cluster com um kernel, mais difícil de obter os meios.

O artigo a seguir discute esse algoritmo e o relaciona ao agrupamento espectral:

I. Dhillon, Y. Guan e B. Kulis. K-means do kernel, cluster espectral e cortes normalizados. KDD 2005.

Eu li muitos comentários interessantes aqui, mas deixe-me acrescentar que a implementação "pessoal" do k-means do Matlab suporta 4 distâncias não euclidianas [entre pontos de dados e centros de cluster]. O único comentário da documentação que posso ver sobre isso é:

Medida de distância, no espaço p-dimensional, usada para minimização, especificada como o par separado por vírgula que consiste em 'Distância' e uma sequência.

O kmeans calcula clusters de centróides de maneira diferente para as diferentes medidas de distância suportadas. Esta tabela resume as medidas de distância disponíveis. Nas fórmulas, x é uma observação (ou seja, uma linha de X) ec é um centróide (um vetor de linha).

Em seguida, uma lista de funções ce xsegue. Assim, considerando que pé a dimensionalidade dos dados de entrada, parece que nenhuma incorporação euclidiana é realizada previamente.

BTW no passado, eu usei o k-means do Matlab com distância de correlação e (sem surpresa) fez o que deveria fazer.

A partir daqui :

Vamos considerar dois documentos A e B representados pelos vetores na figura acima. O cosseno trata os dois vetores como vetores unitários normalizando-os, fornecendo uma medida do ângulo entre os dois vetores. Ele fornece uma medida precisa de similaridade, mas sem considerar a magnitude. Mas a magnitude é um fator importante, considerando a semelhança.