Diferença entre algoritmos k-médias padrão e esféricos

Eu gostaria de entender, qual é a principal diferença de implementação entre os algoritmos de agrupamento padrão e esférico de k-means.

Em cada etapa, k-means calcula as distâncias entre vetores de elementos e centróides do cluster e reatribui o documento a esse cluster, cujo centróide é o mais próximo. Então, todos os centróides são recalculados.

Nas médias k esféricas, todos os vetores são normalizados e a medida da distância é dissimilaridade do cosseno.

Isso é tudo, ou há algo mais?

A questão é:

Qual é a diferença entre os meios k clássicos e os meios k esféricos?

K-significa clássico:

Nos meios k clássicos, procuramos minimizar a distância euclidiana entre o centro do cluster e os membros do cluster. A intuição por trás disso é que a distância radial do centro do cluster até a localização do elemento deve "ter uniformidade" ou "ser semelhante" para todos os elementos desse cluster.

O algoritmo é:

• Definir número de clusters (também conhecido como contagem de clusters)
• Inicialize atribuindo pontos aleatoriamente no espaço para agrupar índices
• Repita até convergir
  • Para cada ponto, encontre o cluster mais próximo e atribua o ponto ao cluster
  • Para cada cluster, encontre a média dos pontos membros e a média do centro de atualização
  • Erro é norma de distância de clusters

Meios K esféricos:

Nos meios esféricos k, a idéia é definir o centro de cada aglomerado, de maneira a uniformizar e minimizar o ângulo entre os componentes. A intuição é como olhar para estrelas - os pontos devem ter espaçamento consistente entre si. Esse espaçamento é mais simples de quantificar como "semelhança de cosseno", mas significa que não há galáxias "de via láctea" formando grandes faixas brilhantes no céu dos dados. (Sim, estou tentando falar com a vovó nesta parte da descrição.)

Versão mais técnica:

Pense em vetores, as coisas que você representa graficamente como setas com orientação e comprimento fixo. Pode ser traduzido para qualquer lugar e ter o mesmo vetor. ref

A orientação do ponto no espaço (seu ângulo a partir de uma linha de referência) pode ser calculada usando álgebra linear, particularmente o produto escalar.

Se movermos todos os dados para que sua cauda esteja no mesmo ponto, podemos comparar "vetores" pelo ângulo e agrupar os semelhantes em um único cluster.

Para maior clareza, os comprimentos dos vetores são redimensionados, para facilitar a comparação do "globo ocular".

Você poderia pensar nisso como uma constelação. As estrelas em um único aglomerado estão próximas umas das outras em algum sentido. Estes são os meus olhos considerados constelações.

O valor da abordagem geral é que ela permite criar vetores que, de outra forma, não teriam dimensão geométrica, como no método tf-idf, onde os vetores são frequências de palavras em documentos. Duas palavras "e" adicionadas não são iguais a "o". As palavras são não contínuas e não numéricas. Eles não são físicos em um sentido geométrico, mas podemos inventá-los geometricamente e, em seguida, usar métodos geométricos para lidar com eles. Os meios k esféricos podem ser usados ​​para agrupar com base em palavras.

$$\begin{bmatrix} x1&y1&x2&y2&group\\ 0&-0.8&-0.2013&-0.7316&B\\ -0.8&0.1&-0.9524&0.3639&A\\ 0.2&0.3&0.2061&-0.1434&C\\ 0.8&0.1&0.4787&0.153&B\\ -0.7&0.2&-0.7276&0.3825&A\\ 0.9&0.9&0.748&0.6793&C\\ \end{bmatrix}$$

Alguns pontos:

• Eles projetam em uma esfera unitária para explicar as diferenças no comprimento do documento.

Vamos trabalhar com um processo real e ver como (ruim) meus "olhos" foram.

O procedimento é:

1. (implícito no problema) conectar vetores caudas na origem
2. projeto na esfera da unidade (para considerar as diferenças no comprimento do documento)
3. use agrupamento para minimizar a " dissimilaridade de cosseno "

$$J = \sum_{i} d \left( x_{i},p_{c\left( i \right)} \right)$$
$$d \left( x,p \right) = 1- cos \left(x,p\right) = \frac{\langle x,p \rangle}{\left \|x \right \|\left \|p \right \|}$$

(mais edições em breve)

Ligações:

1. http://epub.wu.ac.at/4000/1/paper.pdf
2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8125&rep=rep1&type=pdf
3. http://www.cs.gsu.edu/~wkim/index_files/papers/refinehd.pdf
4. https://www.jstatsoft.org/article/view/v050i10
5. http://www.mathworks.com/matlabcentral/fileexchange/32987-the-spherical-k-means-algorithm
6. https://ocw.mit.edu/courses/sloan-school-of-management/15-097-prediction-machine-learning-and-statistics-spring-2012/projects/MIT15_097S12_proj1.pdf