Map Clustering Algorithm

Question

Il mio codice corrente è piuttosto veloce, ma ho bisogno di renderlo ancora più veloce in modo da poter ospitare anche più marcatori. Eventuali suggerimenti?

Note:

• il codice viene eseguito più veloce quando l'istruzione SQL è ordinato in base al nome marker - che a sua volta fa un lavoro molto parziale il clustering dei marcatori (i nomi dei marcatori nella stessa posizione sono spesso, ma non sempre simile).
• Non è possibile eseguire il pre-cluster dei marcatori, perché possono essere ricercati e filtrati dinamicamente.
• Ho provato il clustering basato su griglia, ma i risultati spesso non sono molto piacevoli.
• So che i grappoli sono leggermente inclinati su una proiezione di Mercatore.
• Non sono interessato a un servizio di clustering commerciale.

Il codice:

$singleMarkers = array(); 
$clusterMarkers = array(); 

while (count($markers)) { 
    $marker = array_pop($markers); 
    $cluster = array(); 

    // Compare marker against all remaining markers. 
    foreach ($markers as $key => $compareMarker) { 
     // This function returns the distance between two markers, at a defined zoom level. 
     $pixels = pixelDistance($marker['lat'], $marker['lng'], $compareMarker['lat'], $compareMarker['lng'], $zoomLevel); 
     // If two markers are closer than defined distance, remove compareMarker from array and add to cluster. 
     if ($pixels < $distance) { 
      unset($markers[$key]); 
      $cluster[] = $compareMarker; 
     } 
    } 

    // If a marker was added to cluster, also add the marker we were comparing to. 
    if (count($cluster) > 0) { 
     $cluster[] = $marker; 
     $clusterMarkers[] = $cluster; 
    } else { 
     $singleMarkers[] = $marker; 
    } 
} 

function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) { 
    $x1 = $lon1*10000000; //This is what I did to compensate for using lat/lon values instead of pixels. 
    $y1 = $lat1*10000000; 
    $x2 = $lon2*10000000; 
    $y2 = $lat2*10000000; 

    return sqrt(pow(($x1-$x2),2) + pow(($y1-$y2),2)) >> (21 - $zoom); //21 is the max zoom level 
} 

---

UPDATE

Ecco il codice corrente:

$singleMarkers = array(); 
$clusterMarkers = array(); 

// Minimum distance between markers to be included in a cluster, at diff. zoom levels 
$DISTANCE = (10000000 >> $ZOOM)/100000; 

// Loop until all markers have been compared. 
while (count($markers)) { 
    $marker = array_pop($markers); 
    $cluster = array(); 

    // Compare against all markers which are left. 
    foreach ($markers as $key => $target) { 
     $pixels = abs($marker['lat']-$target['lat']) + abs($marker['lng']-$target['lng']); 

     // If the two markers are closer than given distance remove target marker from array and add it to cluster. 
     if ($pixels < $DISTANCE) { 
      unset($markers[$key]); 
      $cluster[] = $target; 
     } 
    } 

    // If a marker has been added to cluster, add also the one we were comparing to. 
    if (count($cluster) > 0) { 
     $cluster[] = $marker; 
     $clusterMarkers[] = $cluster; 
    } else { 
     $singleMarkers[] = $marker; 
    } 
} 

Answer 1

Avete effettivamente bisogno di calcolare il Euclidean distance? Se sono solo confrontando le grandezze relative delle distanze, probabilmente si può ottenere via con l'utilizzo del Manhattan distance, che vi farà risparmiare due chiamate a pow() e uno a sqrt():

function pixelDistance($lat1, $lon1, $lat2, $lon2, $zoom) { 
    $x1 = $lon1*10000000; //This is what I did to compensate for using lat/lon values instead of pixels. 
    $y1 = $lat1*10000000; 
    $x2 = $lon2*10000000; 
    $y2 = $lat2*10000000; 

    return ($x1-$x2) + ($y1-$y2) >> (21 - $zoom); 
} 

Non sono sicuro se è necessario il bit >> (21 - $zoom) per la vostra calcoli, quindi l'ho lasciato inMa a meno che tu non abbia effettivamente bisogno di usare i valori di distanza calcolati altrove, probabilmente puoi scappare usando semplicemente la latitudine/longitudine direttamente (non c'è bisogno di moltiplicare per nulla) e prendendo la distanza di Manhattan, supponendo che tu abbia pre-calcolato $distance per adattarsi tale misura, che sarà molto più economica in termini computazionali rispetto alla coercizione di tutte le distanze per adattarsi alle unità e alla grandezza di $distance.

EDIT: Quando ero alla ricerca di questo problema l'anno scorso, ho trovato alcune cose utili su Wikipedia - sì, può succedere ;-)

• Cluster analysis
• Hierarchical clustering

posso raccomandiamo anche il libro Programming Collective Intelligence: Building Smart Web 2.0 Applications che entra nel clustering in grande profondità, applicato non solo ai dati geografici ma anche ad altre aree di analisi dei dati.

Answer 2

Sembra che accelerando il pixelDistance() funzione potrebbe essere parte del tuo sol ution, dal momento che corre all'interno del ciclo. Questo è un buon posto dove guardare prima, ma non hai incluso quel codice, quindi non posso esserne sicuro.

Answer 3

Espandere ciò che John ha detto, penso che dovresti provare a sottolineare quella funzione. Le chiamate di funzione in PHP sono molto lente, quindi dovresti ottenere una buona accelerazione.

Answer 4

riesco a vedere altri due miglioramenti possibili qui:

• puoi semplicemente un ciclo tra $ marcatori con un ciclo for, invece di popping loro fuori la matrice? L'array popping è completamente non necessario: dovresti utilizzare gli array come code solo se stai aggiungendo e rimuovendo gli elementi contemporaneamente (cosa che non lo sei, li stai elaborando e gettandoli via)

• Si dovrebbe provare a calcolare il conteggio () degli array all'inizio e quindi aumentare manualmente o diminuire una variabile $ count. Il ricalcolo delle dimensioni di un array ogni loop è uno spreco.

Answer 5

Di seguito sono alcune idee è possibile implementare in termini di prestazioni caso è di grande problema:

• Ridurre la dimensionalità dei dati : si dispone di dati 2D di lungo/lat, forse si può provare proiettandolo verso 1D utilizzando qualcosa di simile Multidimensional Scaling (MDS) che tenta di ridurre il numero di dimensioni mantenendo i distanze nello spazio originale, così la funzione distanza dovrà soltanto affrontare da e caratteristica invece di due. Un modo alternativo è quello di utilizzare Principal component analysis (PCA)
• ricerca veloce: la fase di calcolare la distanza per ogni indicatore può essere migliorata utilizzando KD-trees.

Entrambe queste tecniche sono applicate in un ambiente non in linea, in modo che di solito sono calcolati una sola volta e poi utilizzato molte volte ..

Answer 6

Un semplice ottimizzazione sarebbe quella di prendere vantaggio che sqrt (x) < sqrt (y) è vero iff x < y, quindi puoi omettere lo sqrt in pixelDistance e calcolare $ distanza al di fuori del ciclo. Puoi anche calcolare il 21 - $ zoomLevel fuori dal ciclo, dovrai moltiplicarlo per 2 se stai confrontando i valori al quadrato. Un'altra piccola ottimizzazione sarebbe di risparmiare 2 moltiplicando facendo $ x1 - $ x2 prima di ridimensionare di 10000000. E per un altro po ', memorizzare il delta in una var e moltiplicarlo da solo è probabilmente più veloce della funzione di pow. E per altri ancora è possibile integrare la funzione pixeldistance. Questo tipo di ottimizzazione produrrà solo un aumento costante del fattore.

Per una maggiore velocità è necessario un qualche tipo di infrastruttura di accelerazione. Uno facile sarebbe quello di segnare bin in quadrati di dimensioni della distanza. Quindi è possibile scorrere i raccoglitori in cerca di marker da raggruppare con solo lo stesso bin e altri 3 scelti in base a quale lato del centro del contenitore cade l'indicatore. Ciò comporterà un raggruppamento temporale lineare che colpirà qualsiasi ottimizzazione all'algoritmo quadratico per i risultati più ampi.

Answer 7

Se è possibile, ordina i segnalatori per longitudine sulla ricerca iniziale; quindi, non appena un marker è più largo di un marker rispetto al marker successivo nella lista ordinata, sicuramente saprai che i marker rimanenti non si sovrappongono, quindi puoi interrompere il ciclo foreach e risparmiare un sacco di tempo di elaborazione.L'ho implementato sul mio sito e funziona in modo molto efficiente.

Ho un codice sorgente in Python here.

Answer 8

Quindi, ecco quello che ho fatto - ho aggiunto due colonne in più per i marcatori (punto) tabella con la Mercator convertito i valori per la latitudine e la longitudine utilizzando le seguenti funzioni:

public static $offset = 268435456; 
public static $radius = 85445659.44705395; /* $offset/pi(); */ 

function LonToX($lon) 
{ 
    return round(self::$offset + self::$radius * $lon * pi()/180);   
} 

function LatToY($lat) 
{ 
    return round(self::$offset - self::$radius * log((1 + sin($lat * pi()/180))/(1 - sin($lat * pi()/180)))/2); 
} 

In questo modo ho potuto ottenere con precisione gruppi disposti. Sto ancora cercando di capire come evitare di usare array_pop e andare in bicicletta ogni volta. Fino ad ora è abbastanza efficiente con segnalini sub-1000. In seguito pubblicherò i risultati per i marcatori + 5K e + 10K.

Evitare la funzione pixelDistance e averlo in linea aumenta le prestazioni di quasi la metà!