Algoritmo de cluster

5

Eu tenho um conjunto de n elementos (1.000 < = n < = 100.000) e posso calcular o grau de similaridade entre cada par, ou seja, um valor de 0 (muito semelhante) a 1 (muito diferente). Eu gostaria de agrupar os elementos com base em seu grau de similaridade.

Eu pensei em representá-los como um gráfico, os elementos são os vértices e as arestas ponderadas são a similaridade entre eles. Eu li sobre o algoritmo MCL, mas acho que não é a melhor abordagem já que meu gráfico está completo.

Por outro lado, como há muitos elementos, talvez calcular a similaridade entre cada par não seja a melhor prática (quero um algoritmo rápido). Eu também li algo sobre algoritmos de cluster de líderes, mas, novamente, não tenho certeza se é a melhor abordagem porque, até onde eu sei, é bastante propenso a falhar devido à sua ganância (eu gostaria de algo mais robusto). / p>

Edit: Eu esqueci de mencionar que eu conheço um limite para o qual quando a comparação entre dois elementos é maior do que isso, então eu sei que eles pertencem a clusters diferentes.

    
por ibci 19.03.2015 / 14:44
fonte

2 respostas

1

Não acredito que qualquer clustering significativo seja possível se similarity(a,b) e similarity(b,c) não fizerem o limite superior similarity(a,c) . Para demonstrar, vamos considerar o seguinte exemplo simples (e extremo) com apenas 3 itens:

  • similarity(a,b) == 0
  • similarity(b,c) == 0
  • similarity(a,c) == 1
Portanto,

a deve estar no mesmo cluster que b e b no mesmo cluster que c . Mas a e c devem estar em clusters diferentes, o que contradiz as expectativas anteriores.

    
por 12.04.2015 / 00:38
fonte
0

Este é um problema de agrupamento espectral que tem sido estudado na área de pesquisa há muito tempo. De modo geral, um algoritmo de agrupamento espectral usa a análise de autovalores (também conhecido como espectro) para dividir os dados em dois ou mais clusters por vez. Cada uma dessas divisões é de alguma forma globalmente otimizada, o que leva a bons resultados gerais do agrupamento final.

A entrada da wikipedia pode fornecer mais detalhes.

PS: Comumente, um elemento de uma matriz de similaridade, que é uma medida de similaridade para dois objetos, tem um valor menor para objetos dissimilares e um valor maior para outros similares.

    
por 12.04.2015 / 07:22
fonte