Médias K em semelhanças de cosseno vs. distância euclidiana (LSA)

Estou usando a análise semântica latente para representar um corpus de documentos no espaço dimensional inferior. Quero agrupar esses documentos em dois grupos usando k-means.

Vários anos atrás, eu fiz isso usando o gensim do Python e escrevendo meu próprio algoritmo k-means. Eu determinei os centróides do cluster usando a distância euclidiana, mas depois agrupei cada documento com base na semelhança de cossenos com o centróide. Pareceu funcionar muito bem.

Agora, estou tentando fazer isso em um corpus muito maior de documentos. K-means não está convergindo, e estou me perguntando se é um bug no meu código. Li recentemente que você não deve agrupar usando similaridade de cosseno, porque k-means só funciona com distância euclidiana. Embora, como mencionei, pareceu funcionar bem no meu caso de teste menor.

Agora me deparei com isso na página da Wikipedia da LSA :

Documentos e representações vetoriais de termo podem ser agrupados usando algoritmos tradicionais de agrupamento, como k-means, usando medidas de similaridade como cosseno.

Então qual é? Posso usar semelhança de cosseno ou não?

Sim, você pode usá-lo. O problema é que a semelhança de cosseno não está à distância, por isso é chamada de similaridade. No entanto, pode ser convertido para uma distância, conforme explicado aqui .

Na verdade, você pode usar qualquer distância. Um estudo muito bom das propriedades das funções de distância em espaços de alta dimensão (como é geralmente o caso na recuperação de informações) é Sobre o comportamento surpreendente das métricas de distância no espaço de alta dimensão . Porém, não compara Euclidiano x cosseno.

Me deparei com este estudo, onde eles afirmam que em espaços dimensionais altos, as duas distâncias tendem a se comportar de maneira semelhante.

A distância euclidiana não é adequada para comparar documentos ou grupos de documentos. Ao comparar documentos, um problema importante é a normalização pelo tamanho do documento. A semelhança do cosseno atinge esse tipo de normalização, mas a distância euclidiana não. Além disso, os documentos geralmente são modelados como distribuições de probabilidade multinomial (o chamado pacote de palavras). A similaridade do cosseno é uma aproximação à divergência JS, que é um método estatisticamente justificado para a similaridade. Uma questão importante nos documentos e no cosseno é que se deve aplicar a normalização tf-idf adequada às contagens. Se você estiver usando o gensim para derivar a representação LSA, o gensim já faz isso.

Outra observação útil para o caso de uso de 2 clusters é que você pode obter uma boa inicialização não aleatória porque o LSA é apenas SVD. Você faz isso da seguinte maneira:

• Pegue apenas o primeiro componente de cada documento (assumindo que o primeiro componente seja o vetor singular superior).
• Classifique esses valores acompanhando os IDs do documento para cada valor.
• cluster 1 = IDs do documento correspondentes aos valores superiores, por exemplo, 1000 (ou mais)
• cluster 2 = IDs do documento correspondentes aos valores inferiores, por exemplo, 1000 (ou mais)
• apenas calcule a média dos vetores para cada cluster e normalize pelo comprimento do vetor.
• Agora aplique k-means nessa inicialização. Isso significa apenas iterar (1) atribuir documentos ao centróide mais próximo atual e (2) calcular e normalizar novos centróides após a reatribuição

Sim, a mesma atualização do centróide por média de vetores funciona.

Veja m = 1 caso na Seção 2.2 deste documento . w's são os pesos e os pesos são todos 1 para algoritmos de média k-base.

O artigo utiliza propriedades da desigualdade de Cauchy-Schwartz para estabelecer a condição que minimiza a função de custo para k-mean.

Lembre-se também de que a semelhança de cosseno não é uma distância vetorial. A dissimilaridade do cosseno é. (Esse deve ser um bom termo de pesquisa.) Portanto, quando você atualiza a partição, está procurando por arg maxoposição arg min.