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

Вам действительно нужно рассчитать евклидову дистанцию ? Если вы просто сравниваете относительные величины расстояний, возможно, вам удастся использовать расстояние Манхэттена , что позволит вам сэкономить два вызова 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», которое происходит в кластеризации с большой глубиной, применительно не только к географическим данным, но и к другим областям анализа данных.

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

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

 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 и имея ее встроенный, производительность увеличивается почти вдвое!

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

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

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

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

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

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

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

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

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

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

Здесь у меня есть исходный код на Python.