Come raggruppare gli oggetti in un set per prossimità?

Question

Ho un set contenente migliaia di indirizzi. Se riesco a ottenere la longitudine e la latitudine di ciascun indirizzo, come faccio a dividere il gruppo in gruppi per prossimità?

Inoltre, potrei voler riprovare il "raggruppamento" in base a regole diverse:

• N gruppi
• M indirizzi per gruppo
• distanza massima tra qualsiasi indirizzo in un gruppo

Answer 1

Potresti provare l'algoritmo k-mean clustering .

Answer 2

Volete quantizzazione vettoriale:

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

" Funziona dividendo una grande serie di punti (vettori) in gruppi che hanno approssimativamente lo stesso numero di punti più vicini a loro. Ogni gruppo è rappresentato dal suo punto centroide, come in k-mean e alcuni altri algoritmi di clustering. & Quot;

Qui i vettori sono le coordinate geografiche di ciascun indirizzo e puoi alimentare i tuoi algoritmi con altri parametri a seconda dei tuoi vincoli (prossimità, dimensione del gruppo, numero di gruppi ...).

Puoi iniziare con k-mean, ma dalla mia esperienza un algoritmo basato su Voronoi è più flessibile. Una buona introduzione qui .

Answer 3

Dipende un po 'dalla scala dei dati che si desidera raggruppare. L'approccio della forza bruta consiste nel calcolare la distanza tra tutte le combinazioni di punti in un array di distanze. L'array risultante è N ^ 2 e poiché la distanza da A a B è uguale a B ad A, ne occorrono solo metà, quindi l'insieme risultante è N ^ 2/2.

Per coordinate lat lon relativamente vicine a volte puoi cavartela usando il lat long come una griglia x, y e calcolando la distanza cartesiana. Poiché il mondo reale non è piatto, la distanza cartesiana avrà errori. Per un calcolo più esatto che dovresti usare se i tuoi indirizzi si trovano in tutto il paese, vedi questo link da Mathforum.com .

Se non si dispone della scala per gestire l'intera matrice della distanza, sarà necessario eseguire una programmazione dell'algoritmo per aumentare l'efficienza.

Answer 4

Il " N gruppi " e " M indirizzi per gruppo " i vincoli si escludono a vicenda. Uno implica l'altro.

Answer 5

1. Crea una matrice di distanze tra tutti gli indirizzi.
2. Partendo da un indirizzo casuale, ordina la matrice in ordine crescente di distanza verso quell'indirizzo
3. Rimuovendo gli indirizzi dalla matrice mentre procedi, posiziona gli indirizzi più vicini all'indirizzo iniziale in un nuovo gruppo fino a raggiungere i tuoi criteri (dimensione del gruppo o distanza massima).
4. Una volta che un gruppo è pieno, scegli un altro indirizzo casuale e ricorri la matrice per distanza a quell'indirizzo
5. Continua così fino a quando tutti gli indirizzi non vengono rimossi dalla matrice.

Se gli indirizzi fossero distribuiti uniformemente, ogni gruppo avrebbe una sorta di forma circolare attorno all'indirizzo iniziale. Il problema si presenta quando gli indirizzi iniziali sono vicini a gruppi esistenti. Quando ciò accade, il nuovo gruppo si avvolgerà attorno a quello vecchio e potrebbe persino circondarlo completamente se i criteri di arresto sono solo di dimensioni di gruppo. Se si utilizza il vincolo di distanza massima, ciò non accadrà (presupponendo che non vi siano altri vincoli).

Non so davvero se questo è un buon modo di farlo, ma è quello che proverei. Sono sicuro che sarebbero necessarie molte ottimizzazioni. Soprattutto per gli indirizzi sui bordi.