php - metodos - cluster jerarquico ejemplo

Algoritmo de agrupamiento de mapas

Question

Mi código actual es bastante rápido, pero necesito hacerlo aún más rápido para que podamos acomodar aún más marcadores. ¿Alguna sugerencia?

Notas:

• El código se ejecuta más rápido cuando la instrucción SQL está ordenada por el nombre del marcador, que a su vez hace un trabajo muy parcial de agrupar los marcadores (los nombres de los marcadores en la misma ubicación son a menudo, pero no siempre similares).
• No puedo agrupar previamente los marcadores, porque se pueden buscar y filtrar dinámicamente.
• He intentado el clúster basado en cuadrícula, pero los resultados a menudo no son muy buenos.
• Sé que los grupos están ligeramente sesgados en una proyección de Mercator.
• No estoy interesado en un servicio de clustering comercial.

El código:

$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
}

ACTUALIZAR

Aquí está el código actual:

$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

¿Realmente necesitas calcular la distancia euclidiana ? Si solo estás comparando magnitudes relativas de distancias, probablemente puedas usar la distancia de Manhattan , que te ahorrará dos llamadas a pow() y una 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);
}

No estoy seguro si necesita el bit >> (21 - $zoom) para sus cálculos, así que lo dejé. Pero a menos que realmente necesite usar los valores de distancia calculados en otra parte, probablemente pueda salirse con la simple latitud / longitud directamente (no hay necesidad de multiplicar por nada) y tomar la distancia de Manhattan, asumiendo que usted calcula previamente la $distance para ajustarse a esa medida, lo que será mucho más barato en términos computacionales que obligar a todas las distancias para que se ajusten a las unidades y magnitud de $distance .

EDITAR: cuando estaba investigando este problema el año pasado, encontré algunas cosas útiles en Wikipedia - sí, puede suceder ;-)

• Análisis de conglomerados
• Agrupación jerárquica

También puedo recomendar encarecidamente el libro Programming Collective Intelligence: Building Smart Web 2.0 Applications, que se dedica a agrupar en clústeres con gran profundidad, ya que se aplica no solo a datos geográficos sino también a otras áreas de análisis de datos.

Answer 2

Ampliando lo que dijo John, creo que deberías intentar alinear esa función. Las llamadas de función en PHP son muy lentas, por lo que debería obtener una aceleración decente de eso.

Answer 3

Así que esto es lo que hice: agregué dos columnas adicionales a la tabla de marcadores (puntos) con los valores convertidos de mercator para la latitud y longitud utilizando las siguientes funciones:

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);
}

De esta manera podría obtener con precisión los grupos colocados. Todavía estoy intentando averiguar cómo evitar el uso de array_pop y recorrer cada vez. Hasta ahora es bastante eficiente con marcadores sub-1000. Estaré publicando los resultados de los marcadores + 5K y + 10K más tarde.

¡Evitar la función PixelDistance y tenerla en línea aumenta el rendimiento en casi la mitad!

Answer 4

Las siguientes son algunas ideas que puede implementar en caso de que el desempeño sea de gran importancia:

• Reduzca la dimensionalidad de los datos : tiene datos 2d de long / lat, tal vez pueda intentar proyectarlos a 1D utilizando algo como Multidimensional Scaling (MDS), que intenta reducir el número de dimensiones a la vez que conserva las distancias en el espacio original. por lo tanto, la función de distancia solo tendrá que lidiar con una característica en lugar de dos. Una forma alternativa es utilizar el análisis de componentes principales (PCA)
• Búsqueda más rápida : el paso de calcular la distancia a cada marcador se puede mejorar utilizando KD-trees .

Ambas técnicas se aplican en una configuración fuera de línea, por lo que generalmente se calculan una vez y luego se usan muchas veces.

Answer 5

Parece que acelerar la función pixelDistance () podría ser parte de su solución, ya que se ejecuta dentro del bucle. Este es un buen lugar para mirar primero, pero no incluyó ese código, así que no puedo estar seguro.

Answer 6

Puedo ver dos mejoras posibles más aquí:

• ¿Puedes pasar los marcadores $ con un bucle for en lugar de sacarlos de la matriz? El despliegue de matrices es completamente innecesario: en realidad solo deberías usar matrices como colas si estás agregando y eliminando elementos al mismo tiempo (lo que no es así, solo las procesas y luego las desechas)

• Debería intentar calcular el recuento () de los arreglos al comienzo y luego aumentar o disminuir manualmente una variable de $ recuento. Recalculando el tamaño de una matriz, cada bucle es inútil.

Answer 7

Si puede, ordene sus marcadores por longitud en la búsqueda inicial; luego, tan pronto como un marcador tenga más de un ancho de marcador del siguiente marcador en la lista ordenada, definitivamente sabrá que los marcadores restantes no se superpondrán, por lo que puede romper el bucle foreach y ahorrarse una tonelada de tiempo de procesamiento. He implementado esto en mi propio sitio y funciona de manera muy eficiente.

Tengo un código fuente en Python here .

Answer 8

Una optimización simple sería aprovechar que sqrt (x) <sqrt (y) es verdadero si x x <y, por lo que puede omitir sqrt en la distancia de píxeles y calcular la distancia cuadrada fuera del bucle. También puedes calcular el 21 - $ zoomLevel fuera del bucle, tendrás que multiplicarlo por 2 si estás comparando los valores cuadrados. Otra pequeña optimización sería ahorrar 2 multiplicaciones haciendo $ x1- $ x2 antes de escalar por 10000000. Y por un poquito más, almacenar el delta en una var y multiplicarlo por sí mismo es probablemente más rápido que la función pow. Y para algunos más puedes en línea la función de pixeldistance. Este tipo de optimización solo producirá un factor de aceleración constante.

Para una mayor aceleración, necesitará algún tipo de estructura de datos de aceleración. Una fácil sería colocar los marcadores en cuadrados de distancia. Luego, puede pasar por encima de las bandejas, buscar marcadores para agrupar solo en la misma bandeja y en otros 3 elegidos, dependiendo de en qué lado del centro de la bandeja caiga el marcador. Esto dará como resultado un agrupamiento de tiempo lineal que superará cualquier optimización del algoritmo cuadrático para conjuntos de resultados más grandes.