Filtrando afastado próximos pontos a partir de uma lista

Question

respondeu-metade uma pergunta sobre encontrar aglomerados de massa em um bitmap. Digo meia respondeu porque eu deixei-o em uma condição em que eu tinha todos os pontos no bitmap classificadas em massa e deixou para o leitor para filtrar a lista removendo pontos do mesmo cluster.

Em seguida, quando se pensa que passo eu achei que a solução não saltar para fora em mim como eu pensava que seria. Então agora eu estou pedindo que vocês por ajuda. Temos uma lista de pontos com massas assim (uma lista Python de tuplas, mas você pode representá-lo como você vê o ajuste em qualquer língua):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

Cada tupla é da forma:

(x, y, mass)

Note que a lista é ordenada aqui. Se a sua solução prefere não tê-los ordenado é perfeitamente OK.

O desafio, se você se lembra , é encontrar as principais aglomerados de massa. O número de cachos não é conhecido. Mas você sabe as dimensões do bitmap. Às vezes vários pontos dentro de um cluster tem mais massa do que o centro do próximo cluster (em tamanho). Então, o que eu quero fazer é ir a partir dos pontos de maior massa e pontos de remover no mesmo cluster (pontos nas proximidades).

Quando eu tentei isso acabei por ter de caminhar até partes da lista uma e outra vez. Eu tenho um sentimento que eu sou apenas estúpido sobre isso. Como você faria? pseudo-código ou código real. Claro, se você pode apenas tirar onde deixei em que a resposta com código Python é mais fácil para mim para experimentar com ele.

O próximo passo é descobrir quantos grupos existem realmente no bitmap. Eu ainda estou lutando com a definição desse problema para que eu possa voltar com uma pergunta sobre isso.

EDIT: Devo esclarecer que eu sei que não há resposta "correta" a esta questão. E o nome da questão é fundamental. A primeira fase do meu agrupamento é feito. Im à procura de um rápido, accurate- método de "suficiente" de filtrar afastado próximos pontos.

Deixe-me saber se você ver como posso fazer a pergunta mais clara.

Answer 1

Só para você saber, você está pedindo uma solução para um mal-posto problema: não existe uma solução definitiva. do que bem ... isso só torna mais divertido. Seu problema está mal colocado principalmente porque você não sabe quantos grupos quiser. Clustering é uma das principais áreas de aprendizagem de máquina e há um muito poucas abordagens que têm sido desenvolvidos ao longo dos anos.

Como aracnídeo salientado, o algoritmo K-means tende a ser um bom e é muito fácil de implementar. Os resultados dependem criticamente da estimativa inicial feita e sobre o número de grupos desejados. Para superar o problema estimativa inicial, é comum para executar o algoritmo muitas vezes com inicializações aleatórias e escolher o melhor resultado. Você precisa definir o que "melhores" significa. Uma medida seria quadrado da distância média de cada ponto ao seu centro de cluster. Se você quer adivinhar automaticamente quantos grupos existem, você deve executar o algoritmo com toda uma gama de números de clusters. Para qualquer bom "melhor" medida, mais clusters olhará sempre melhor do que menos, então você precisa encontrar uma maneira de penalizar ter muitos clusters. A MDL discussão sobre wikipedia é um ponto de partida bom.

K-means agrupamento é basicamente o mais simples modelo mistura . Às vezes é útil para atualizar para uma mistura de gaussianas aprendida por maximização expectativa (descrito no link dado apenas). Isto pode ser mais robustas do que K-means. É preciso um pouco de esforço mais para compreendê-lo, mas quando o fizer, não é muito mais difícil do k-médias de implementar.

Há uma abundância de outras agrupamento técnicas como clustering aglomerativo e clustering espectral. agrupamento aglomerativo é muito fácil de implementar, mas escolher quando parar de construir os clusters pode ser complicado. Se você fizer agrupamento aglomerativo, você provavelmente vai querer olhar para kd árvores para uma mais rápida pesquisas vizinho mais próximo. A resposta de smacl descreve uma maneira ligeiramente diferente de fazer agrupamento aglomerativo usando um diagrama de Voronoi.

Existem modelos que pode escolher automaticamente o número de clusters para você, tais como os baseados em latente Dirichlet Allocation , mas eles são muito mais difíceis de compreender um implementar corretamente.

Você também pode querer olhar para o algoritmo de média-shift para ver se ele está mais perto do que você realmente quer.

Answer 2

Parece-me que você está procurando o href="http://en.wikipedia.org/wiki/K_means" rel="nofollow algoritmo K-means .

Answer 3

Como mencionei no comentário à sua pergunta, a resposta é baseada em se ou não de massa pode ser considerado escalar neste contexto. Se assim for, as soluções baseadas cores são provavelmente não vai trabalhar como cor muitas vezes não é tomado como sendo escalar.

Por exemplo, se tiver uma dada área com um ponto de massa elevada, que é o mesmo como tendo a mesma área com 10 pontos de 1/10 da massa? Se isso for verdade, a massa não é escalar neste contexto, e eu tendem a olhar para um algoritmo usado para espacialmente gouping valores não-escaláveis ??semelhantes, por exemplo, voronoi diagramas .

Neste caso, onde duas áreas de Voronoi adjacentes têm uma suficiente correspondência em massa perto e à distância, eles podem ser agrupados. Você poderia repetir isso para encontrar todos os clusters.

Se, por outro lado, sua massa é escalável, ou que a massa em uma posição desconhecida pode ser interpolada a partir de pontos circundantes, eu tenderia a Triangulate e contorno dos dados de entrada e áreas de uso entre contornos de encontrar aglomerados de massa similar.

Answer 4

Isso soa como quantização de cor, onde você reduzir o número de cores em uma imagem. Uma forma seria para traçar as cores no espaço, e combinar conjuntos para o centro (ou uma média ponderada) de um cluster.

O nome exato do algoritmo que desencadeou esta memória não me falha, mas eu vou editar a resposta se ele aparece, mas, entretanto, você deve olhar para quantização de cor e ver se alguns dos algoritmos são úteis.

Answer 5

Comece com o " Convex casco " problema. Você também está procurando alguma "casco convexo", como clusters.

Note que "clusters" é vago. Você tem uma massa média em toda a sua área. Alguns pontos têm acima massa média, e alguns abaixo da média. Como muito acima da média significa que você encontrou um cluster? Qual a distância entre fazer nós tem que ser para ser parte de um cluster ou em um cluster separado?

Qual é a diferença entre dois picos de montanha e um cume?

Você tem que calcular uma "topografia" - juntando todos os pontos com igual densidade em regiões. Isso requer que você escolher um local e trabalhar o seu desejo de um ponto radialmente, localizando posições onde as densidades são iguais. Você pode conectar esses pontos em regiões.

Se você escolheu o seu ponto inicial com sabedoria, as regiões devem ninho. Escolher o seu ponto de partida é fácil, porque você começa em máximos locais.

Answer 6

Uma vez que você já está falando em massa, por que não uma solução baseada gravidade. Um sistema de partículas simples não precisam ser super precisos, e você não teria que executá-lo por muito tempo antes que você poderia fazer uma melhor palpite quanto ao número de clusters.

Se você tem uma idéia melhor sobre os números de fragmentação, k-médias vizinho mais próximo se torna viável.