algoritmo de agrupamento para dados não dimensionais

12

Eu tenho um conjunto de dados de milhares de pontos e um meio de medir a distância entre dois pontos, mas os pontos de dados não têm dimensionalidade. Eu quero um algoritmo para encontrar centros de cluster neste conjunto de dados. Eu imagino que, como os dados não têm dimensões, um centro de cluster pode consistir em vários pontos de dados e uma tolerância, e a associação dentro do cluster pode ser determinada pela média da distância de um ponto de dados a cada ponto de dados no centro de cluster.

por favor me perdoe se esta pergunta tem uma solução bem conhecida, sei muito pouco sobre esse tipo de problema! minha pesquisa (muito limitada) só descobriu algoritmos de agrupamento para dados dimensionais, mas peço desculpas antecipadamente se perdi algo óbvio.

obrigado!

machine-learning lg.learning clustering lata de tinta
fonte

Por que a não dimensionalidade torna esse problema especial?

Raphael

1

Alguns algoritmos que eu vi para agrupar (realmente apenas k-means) exigem a geração de pontos de dados aleatórios como sementes, o que não é possível com dados sem dimensão. Portanto, o requisito especial é que os centros de cluster sejam representados por um conjunto de pontos de dados existentes (talvez ponderados).

Paint22

15

$k$ $k$ $k$ $k$

$k$

Esses dois problemas são difíceis de NP em geral e difíceis de aproximar-se de um fator arbitrário. Observe que, se você abandonar a condição de métrica, as coisas pioram muito em termos de aproximabilidade.

$k$

Por fim, como na maioria dos problemas de cluster, sua escolha final depende do aplicativo, do tamanho dos dados e assim por diante.

Suresh Venkat
fonte

3

Obrigado pela visão geral rápida e clara. Levarei pelo menos alguns dias para determinar se você respondeu minha pergunta. Parece que tenho muito a aprender antes de entender o meu problema o suficiente :) #

315

5

Também há clustering de correlação , que tem como informação de entrada para cada par de itens indicando se eles pertencem ao mesmo cluster ou a diferentes clusters.

Warren Schudy
fonte

Sim, esse é outro bom exemplo. E, claro, Warren é um especialista nisso! Não sei se a entrada do OP foi +/-, ou pode ser convertida via limiar. Nesse caso, essa é definitivamente uma opção viável.

Suresh Venkat

5

Se você está apenas procurando um bom desempenho empírico, o algoritmo de propagação por afinidade geralmente funciona melhor do que k-medianas. Há código disponível em vários idiomas e publicações que descrevem o algoritmo em mais detalhes estão aqui: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

\sum_{i} s (i, c_{i})

$\sum_{i} s(i, c_i)$

$s$ $c_i \in \mathbf{c}$ $i$ $s(i, i)$

dan_x
fonte

5

Sua pergunta parece sugerir que você está procurando um algoritmo com tempo computacional decente. Dado o tamanho dos seus vértices (ou pontos), seria criar uma representação gráfica ponderada dos seus dados e usar o Algoritmo de Cluster de Markov (MCL) para agrupar o gráfico.

http://www.micans.org/mcl/

O MCL é baseado em passeios aleatórios através de gráficos ponderados e não ponderados para encontrar subgráficos densos. Ele é capaz de lidar com grandes gráficos e tem sido usado em muitos programas de bioinformática conhecidos e bem utilizados (como o BLAST). -Boucher

Christina Boucher
fonte

1

Considere o algoritmo vizinho k-mais próximo .

Rafael
fonte

Rafael, o algoritmo k-NN não é realmente um algoritmo de agrupamento, é? a menos que você retire repetidamente os k vizinhos de um nó?

quer

k

$k$

algoritmo de agrupamento para dados não dimensionais

Respostas: