Usando k-means com outras métricas

Então, percebo que isso já foi perguntado antes: por exemplo, quais são os casos de uso relacionados à análise de cluster de diferentes métricas de distância? mas achei as respostas um tanto contraditórias ao sugerido que deveriam ser possíveis na literatura.

Recentemente, li dois artigos que mencionam o uso do algoritmo kmeans com outras métricas, por exemplo, editar a distância entre as cordas e a "Distância do movimentador da terra" entre as distribuições. Dado que esses trabalhos mencionam o uso de kmeans com outras métricas sem especificar como , particularmente quando se trata de calcular a média de pontos, sugere-me que talvez exista algum método "padrão" para lidar com isso que simplesmente não estou escolhendo em cima.

Tomemos, por exemplo, este artigo , que fornece uma implementação mais rápida do algoritmo k-means. Citando o parágrafo 4 da introdução, o autor diz que seu algoritmo "pode ​​ser usado com qualquer métrica de distância da caixa preta" e, no próximo parágrafo, ele menciona editar a distância como um exemplo específico. No entanto, seu algoritmo ainda calcula a média de um conjunto de pontos e não menciona como isso pode afetar os resultados com outras métricas (estou especialmente perplexo com a forma como a média funcionaria com a distância de edição).

Este outro artigo descreve o uso de k-means para agrupar mãos de pôquer para uma abstração do Texas Hold'em. Se você pular para a página 2 na parte inferior da coluna da esquerda, a gravação do autor "e o k-means serão usados ​​para calcular uma abstração com o número desejado de clusters usando a Distância do Movimentador da Terra entre cada par de histogramas como a métrica da distância".

Não estou realmente procurando alguém para me explicar esses documentos, mas estou perdendo algum método padrão para usar o k-means com outras métricas? A média padrão da distância do movedor de terra parece que poderia funcionar heuristicamente, mas a distância de edição parece não se encaixar no molde. Agradeço qualquer insight que alguém possa dar.

(edit) : Fui em frente e tentei o k-means nos histogramas de distribuição usando a distância do earth earth (semelhante ao que está no jornal de pôquer) e parecia ter funcionado bem, os clusters que saíam pareciam muito bons para o meu caso de uso. Para calcular a média, apenas tratei os histogramas como vetores e calculei a média da maneira normal. A única coisa que notei é que a soma de todos os pontos das distâncias aos meios nem sempre diminuiu de maneira monótona. Na prática, porém, ele se instalaria em um min local dentro de 10 iterações, apesar de problemas monótonos. Vou assumir que isso foi o que eles fizeram no segundo artigo, a única questão que resta então é: como diabos você mediaria ao usar algo como distância de edição?

Não é como se o k-means necessariamente explodisse e falhasse se você usar uma métrica diferente.

Em muitos casos, ele retornará algum resultado . Apenas não é garantido que ele encontre os centróides ou partições ideais com outras métricas, porque a média pode não ser adequada para minimizar distâncias.

Considere a distância dos motores da Terra. Dados os três vetores

3 0 0 0 0
0 0 3 0 0
0 0 0 0 3

A média aritmética é

1 0 1 0 1

que possui distâncias EMD 6, 4, 6 (total 16). Se o algoritmo tivesse usado

0 0 3 0 0

as distâncias EMD teriam sido 6, 0, 6; ou seja, melhor (total de 12).

A média aritmética não minimiza a EMD, e o resultado do uso de k-médias (com média artihmetic) não produzirá representantes ótimos.

Coisas semelhantes são válidas para distâncias de edição.

O K-means é apropriado para uso em combinação com a distância euclidiana, porque o objetivo principal do k-means é minimizar a soma das variações dentro do cluster , e a variação dentro do cluster é calculada exatamente da mesma maneira que a soma do Euclidean distâncias entre todos os pontos do cluster para o centróide do cluster. Como outras respostas apontam , o algoritmo só é garantido para convergir (mesmo que seja no mínimo local) se a etapa de atualização do centróide e a etapa de reatribuição dos pontos de dados forem realizadas no mesmo espaço euclidiano n-dimensional .

Além disso, foi demonstrado (e eu coloquei um link aqui porque eu mesmo não posso explicar isso) que a média é o melhor estimador a ser usado quando é necessário minimizar a variação total . Então k-médias amarrar à distância euclidiana é duplo: o algoritmo deve ter alguma maneira de calcular a média de um conjunto de pontos de dados (daí o nome k- meios ), mas esta média só faz sentido e garantias convergência da processo de agrupamento se a distância euclidiana for usada para reatribuir pontos de dados aos centróides mais próximos.

Você ainda pode usar k-means com outras medidas de distância, como neste artigo , em que o autor usa o algoritmo com a distância de Minkowski, que é uma generalização das distâncias de Manhattan, Euclidiana e Chebyshev. No entanto, nesses casos, a convergência não é garantida e, como conseqüência, você pode esperar que as iterações futuras do algoritmo realmente tenham maior variação total do que as iterações anteriores.

Mesmo assim, como mostrado no artigo acima, mesmo sem a garantia de convergência, o k-means pode obter melhores resultados de agrupamento em alguns cenários usando outras medidas de distância. Se você seguir as normas , por exemplo, e sabendo que a distância euclidiana é a norma e que a distância de Manhattan é a norma , foi mostrado que, para matrizes de distância esparsa, k-significa usado em conjunto com uma norma com atinge maior precisão de agrupamento do que quando se usa a distância euclidiana.$L^p$L 1 L p 0<p≤$L^2$$L^1$$L^p$$0 < p \leq 1$

Por fim, acho interessante ressaltar que existem algumas medidas de similaridade que, de alguma forma, podem ser convertidas para a distância euclidiana, de tal forma que, se você usar a referida medida de similaridade em conjunto com o k-means, deverá obter resultados semelhantes. Um exemplo disso é a semelhança de cosseno .

Não sei se é isso que os papéis vinculados estão fazendo, mas é possível fazer k-means com funções de distância não euclidiana usando o truque do kernel . Ou seja, mapeamos implicitamente as entradas para um espaço de alta dimensão (muitas vezes de dimensão infinita) onde as distâncias euclidianas correspondem à função de distância que queremos usar e executamos o algoritmo nesse local. Para o algoritmo k-means de Lloyd em particular, podemos atribuir pontos a seus clusters facilmente, mas representamos os centros de cluster implicitamente e encontrar sua representação no espaço de entrada exigiria encontrar uma média de Fréchet . O artigo a seguir discute o 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.

Existem kernels baseados na distância de edição e na distância do mecanismo de terra .