Алгоритм кластеризации карт

Ответ 1

Вам действительно нужно рассчитать Евклидово расстояние? Если вы просто сравниваете относительные величины расстояний, вы, вероятно, можете уйти с помощью Manhattan distance, что избавит вас от двух вызовов pow() и один к 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);
}

Не уверен, нужен ли вам бит >> (21 - $zoom) для ваших вычислений, поэтому я его оставил. Но если вам действительно не нужно использовать рассчитанные значения расстояния в другом месте, вам, вероятно, удастся просто использовать широту/долготу напрямую ( нет необходимости умножаться на что-либо) и принимая расстояние Манхэттена, предполагая, что вы предварительно вычислите $distance, чтобы соответствовать этой мере, что будет намного дешевле в вычислительных терминах, чем принуждение всех расстояний, чтобы они соответствовали единицам и величине $distance.

EDIT: Когда я изучал эту проблему в прошлом году, я нашел полезный материал в Википедии - да, это может произойти; -)

• Анализ кластеров
• Иерархическая кластеризация

Я также могу настоятельно рекомендовать книгу Программирование коллективного интеллекта: создание приложений Smart Web 2.0, которое идет в кластеризацию на большой глубине, как применимо не только к географическим данным, а также к другим областям анализа данных.

Ответ 2

Развернувшись на том, что сказал Джон, я думаю, вы должны попробовать включить эту функцию. Функциональные вызовы в PHP очень медленные, поэтому вы должны получить приличное ускорение от этого.

Ответ 3

Итак, вот что я сделал - я добавил два дополнительных столбца в таблицу маркеров (точек) с преобразованными меркатором значениями для широты и долготы, используя следующие функции:

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

Таким образом, я мог бы получить точно размещенные кластеры. Я все еще пытаюсь решить, как избежать использования array_pop и циклического перехода каждый раз. Пока что он довольно эффективен с маркерами под 1000. Я опубликую результаты для + 5K и + 10K маркеров позже.

Избегая функции pixelDistance и имея ее встроенный, производительность почти наполовину!

Ответ 4

Кажется, что ускорение функции pixelDistance() может быть частью вашего решения, поскольку оно выполняется внутри цикла. Это хорошее место для поиска в первую очередь, но вы не включили этот код, поэтому я не могу быть уверен.

Ответ 5

Здесь я вижу два возможных улучшения:

• Можете ли вы просто пропустить маркеры $ с циклом for вместо popping их от массива? Всплывающее вскрытие массива полностью не требуется - вы должны использовать только массивы в виде очередей, если вы одновременно добавляете и удаляете элементы (что вы не делаете, вы просто обрабатываете их, а затем отбрасываете)

• Вы должны попытаться вычислить count() массивов на начало, а затем вручную увеличить или уменьшить переменную счетчика $. Пересчет размера массива каждый цикл является расточительным.

Ответ 6

Ниже перечислены некоторые идеи, которые вы можете реализовать в случае, если производительность представляет собой большую проблему:

• Уменьшить размерность данные: у вас есть 2d данных long/lat, возможно, вы можете попробовать проецировать его до 1D, используя что-то вроде Многомерное масштабирование (MDS), которое пытается уменьшить количество размеров при сохранении расстояния в исходном пространстве, таким образом, функция расстояния будет иметь дело только с одной функцией вместо двух. Альтернативный способ - использовать Анализ основных компонентов (PCA)
• Быстрый поиск: шаг вычисления расстояние до каждого маркера может быть улучшено с помощью KD-tree.

Оба эти метода применяются в автономном режиме, поэтому они обычно вычисляются один раз, а затем используются много раз.

Ответ 7

Простая оптимизация заключалась бы в том, чтобы воспользоваться тем, что sqrt (x) < sqrt (y) истинно, если x < y, поэтому вы можете опустить sqrt в pixelDistance и вычислить $distance в квадрате вне цикла. Вы также можете вычислить 21 - $zoomLevel вне цикла, вам придется умножить его на 2, если вы сравниваете квадрат значений. Еще одна небольшая оптимизация заключалась бы в том, чтобы сохранить 2 умножения, выполнив $x1- $x2 до масштабирования на 10000000. И еще немного, хранение дельта в var и его умножение, вероятно, быстрее, чем функция pow. И еще для того, чтобы вы могли встроить функцию сравнения пикселей. Такая оптимизация даст только постоянный коэффициент ускорения.

Для большего ускорения вам понадобится какая-то структура данных ускорения. Легко было бы поместить маркеры на квадраты расстояния. Затем вы можете запускать над бункерами поиск маркеров для кластера с одним и тем же бункером и тремя другими, выбранными в зависимости от того, какая сторона центра бункера помечена маркером. Это приведет к линейной кластеризации времени, которая будет бить любую оптимизацию квадратичного алгоритма для больших наборов результатов.

Ответ 8

Если вы можете, сортируйте маркеры по долготе при первоначальном поиске; то, как только маркер будет больше ширины маркера от следующего маркера в отсортированном списке, вы определенно знаете, что оставшиеся маркеры не будут перекрываться, поэтому вы можете разбить цикл foreach и сэкономить массу времени обработки. Я реализовал это на своем собственном сайте и работает очень эффективно.

У меня есть исходный код в Python здесь.