Como faço para agrupar objetos em um conjunto de proximidade?

Question

Eu tenho um conjunto contendo milhares de endereços. Se eu conseguir a longitude e latitude de cada endereço, como faço para dividir o conjunto em grupos pela proximidade?

Além disso, eu posso querer repetir a 'clusters' de acordo com regras diferentes:

• grupos N
• M endereços por grupo
• máxima distância entre qualquer endereço em um grupo

Answer 1

Você poderia tentar o k-means clustering algoritmo.

Answer 2

Você quer quantização vetorial:

http://en.wikipedia.org/wiki/Vector_quantization

" Ele funciona pela divisão de um grande conjunto de pontos (vectores) para os grupos que possuem aproximadamente o mesmo número de pontos mais próximos a eles. Cada grupo é representado pelo seu ponto de centróide, como em k-meio e algum outro agrupamento algoritmos. "

Aqui, os vetores são as coordenadas geográficas de cada endereço, e você pode alimentar seus algoritmos com outros parâmetros dependendo de suas limitações (proximidade, tamanho do grupo, Número de grupos ...).

Você pode começar com k-médias, mas a partir de minha experiência de um algoritmo baseado Voronoi é mais flexível. A introdução boa aqui .

Answer 3

Depende um pouco sobre a escala dos dados que você está querendo cluster. A abordagem de força bruta é para calcular a distância entre todos os pontos de combinação para uma matriz de distância. A matriz resultante N ^ 2 e uma vez que a distância de A a B é o mesmo que o de B para A só precisa de metade daqueles, de modo que o conjunto resultante é N ^ 2/2.

Para coordenadas lon relativamente perto lat às vezes você pode começar afastado com o uso do lat long como um x, y de rede e calcular a distância cartesiana. Desde que o mundo real não é plana a distância cartesiana vai ter erro. Para um cálculo mais exato que você deve usar se seus endereços estão localizados em todo o país, consulte este link de Mathforum.com .

Se você não tem a escala para lidar com a matriz de distância inteira, você vai precisar fazer algum algoritmo de programação para aumentar a eficiência.

Answer 4

Os "grupos n" e "M endereços por grupo" restrições são mutuamente exclusivas. Uma implica a outra.

Answer 5

1. construir uma matriz de distâncias entre todos os endereços.
2. A partir de um endereço aleatório, classificar a matriz pela distância ascendente para esse endereço
3. Remover os endereços a partir da matriz como você ir junto, coloque os endereços mais próximos ao endereço de início em um novo grupo até chegar os seus critérios (tamanho de grupo ou distância máxima).
4. Uma vez que um grupo está cheio, escolha outro endereço aleatório e recorrer a matriz de distância para esse endereço
5. Continuar desta maneira até que todos os endereços são levados para fora da matriz.

Se os endereços foram distribuídos uniformemente, cada grupo teria um tipo de forma circular em torno do endereço de início. O problema surge quando endereços iniciais estão perto os grupos existentes. Quando isso acontece, o novo grupo irá classificar de envolver em torno do antigo e poderia até circundar-lo completamente se o seu critério de parada é apenas o tamanho do grupo. Se você usar a restrição max-distância, então isso não vai acontecer (assumindo que não há outras restrições).

Eu realmente não sei se esta é uma boa maneira de fazer isso, mas é o que eu ia tentar. Estou seria necessária certeza que muita otimização. Especialmente para os endereços nas bordas.