地图聚类算法

Question

我的当前代码已经很快了，但我需要让它更快，以便我们可以容纳更多的标记。 有什么建议吗？

注：

• 当SQL语句按标记名称排序时，代码运行得最快 - 这本身就是对标记进行非常部分聚类的工作（同一位置的标记名称通常相似，但并不总是相似）。
• 我无法预先对标记进行聚类，因为它们可以动态搜索和过滤。
• 我尝试过基于网格的聚类 - 但结果通常不太好。
• 我知道聚类在Mercator投影上略微偏斜。
• 我对商业聚类服务不感兴趣。

代码：

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

---

更新

以下是当前的代码：

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

- Chris B

Answer 1

你是否实际需要计算欧几里得距离？如果你只是比较距离的相对大小，你可能可以使用曼哈顿距离，这将节省两次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 的单位和大小要便宜得多。

编辑：去年我研究这个问题时，在维基百科上找到了一些有用的东西 - 是的，这是可能的 ;-)

• 聚类分析
• 层次聚类

我还强烈推荐这本书《集体智慧编程：构建智能 Web 2.0 应用程序》，它深入探讨了聚类算法，不仅适用于地理数据，还适用于其他数据分析领域。

- NickFitz

---

这个很好用。>> (21 - $zoom) 是我将缩放级别纳入方程的方法 - 但我决定在算法中摆脱它并根据缩放计算合格的 $distance - 这样我只需要做一次。谢谢！ - Chris B

此外，该方程式需要使用绝对值：$pixels = abs($x1-$x2) + abs($y1-$y2); - Chris B

Answer 2

继John所说的，我认为你应该尝试内联该函数。在PHP中，函数调用非常缓慢，因此你可以从中获得相当的速度提升。

- ryeguy

---

太棒了！这实际上相当重要。 - Chris B

Answer 3

以下是一些你可以实施的想法，以防性能成为重大问题：

• 降低数据维度：如果你有经度/纬度的二维数据，或许可以尝试使用多维缩放（MDS）将其投影到一维上，该技术试图减少维数同时保留原始空间中的距离，因此距离函数只需要处理一个特征而不是两个。另一种替代方法是使用主成分分析（PCA）。
• 更快的搜索：计算到每个标记的距离的步骤可以使用KD树进行改进。

这两种技术都是在离线设置下应用的，因此通常只需计算一次，然后多次使用。

- Amro

Answer 4

所以这是我做的 - 我在标记（点）表中添加了两个额外的列，使用以下函数将纬度和经度转换为墨卡托值：

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函数并将其内联可以将性能提高近一半！

- David Kobia

---

实际上 - 我不能向原始问题或任何其他答案添加评论，除非答案是我的...很奇怪。无论如何，看起来你正在运行Tuupola代码的修改版本（http：//github.com/tuupola/php_google_maps）。我已经对你到目前为止的内容进行了分析，当你有数千个点时，它绝对不高效。我一直在努力寻找各种解决方案，但所有这些解决方案都指向了预聚类 - 如果想要动态生成数据，则这是一个问题。 - David Kobia

我实际上没有将纬度和经度值转换为x和y值 - 我只是按原样对它们进行聚类。这意味着随着它们远离赤道，聚类会变得更加倾斜，但几乎不可察觉。我还使用了上面的建议来计算曼哈顿距离（而不是欧几里得距离），这有助于加快速度。它确实稍微降低了聚类的准确性，但同样 - 几乎不可察觉。现在我们正在快速运行约5K个标记，但这个数字正在增加。 - Chris B

曼哈顿距离也很有效 - 我一直在尝试。如果您正在处理集群，则精度可能不是问题。我只是想知道您是否根据缩放级别使用了哪种$distance。 - David Kobia

David，我更新了我的代码以展示我现在如何计算距离。 - Chris B

我已经成功地测试了10K个标记，通过添加视口查询来限制聚类仅在视口范围内。下一站20K。 - David Kobia

Answer 5

看起来加速 pixelDistance() 函数可能是你的解决方案的一部分，因为它在循环内运行。这是首先要查找的好地方，但你没有包含那段代码，所以我不能确定。

- John Fisher

---

好的，我加入了这个函数。在pixelDistance()里，我之前将lat/lon值转换成像素值，但是我发现如果直接使用纬度/经度值进行聚类，可以提高速度。尽管这会稍微扭曲一下集群的形状。 - Chris B

Answer 6

我在这里看到了另外两个可能的改进：

• 你能否只是使用for循环遍历$markers，而不是从数组中弹出它们？弹出数组是完全不必要的 - 如果您同时添加和删除项目，则应该仅将数组用作队列（但您不是；您只是处理它们然后丢弃它们）

• 您应该尝试在开始时计算数组的count()，然后手动增加或减少$count变量。每次循环重新计算数组大小是浪费的。

- ryeguy

---

重新计算数组大小确实是浪费的，但是在当前结构下我不知道如何摆脱它。在给定的循环中，数组可能会发生显着变化 - 当我将弹出标记与剩余标记中的每个标记进行比较时，任何一个标记都可能被添加到聚类中并从数组中删除。在高缩放级别下，数组中的所有或大多数标记都将被移除并放入聚类中，不再留下要检查的标记。这显著减少了完成所需的循环次数。希望这讲得通。 :) - Chris B

Answer 7

一种简单的优化方法是利用sqrt(x) < sqrt(y)当且仅当x < y，因此可以在pixelDistance中省略sqrt并在循环外计算$distance squared。你也可以在循环外计算21-$zoomLevel, 如果你正在比较平方值，你将不得不乘以2。另一个小优化是通过在乘以10000000之前执行$x1-$x2来节省2个乘法。对于稍微更多的优化，将增量存储在变量中并将其乘以自身可能比pow函数更快。而且为了获得更多的优化可以内联pixeldistance函数。这种类型的优化只能产生恒定的速度提升。

要获得更大的速度提升，您需要某种加速数据结构。一个简单的方法是将标记分成距离大小的正方形。然后，您可以运行超过容器在容器和3个其他容器中查找标记进行聚类，具体取决于标记是否落入容器中心的哪一侧。这将导致线性时间聚类，将击败任何针对较大结果集的二次算法优化。

- Ants Aasma

---

好的，我现在明白你的意思了 - 即使两个相邻的标记被分隔在一个 bin 边界上，也不会有影响，因为我可以检查相邻的 bins。我会看看能否想出如何实现这个功能。 - Chris B

我找不到比我现在的实现更快的方法。可能有一种方法可以做到... :( - Chris B

我不确定你无法获得加速的原因。我在Python中尝试了一个快速实现。对于10k个点，我获得了约100倍的加速（9.4秒对95毫秒）。数据集是随机生成的1000个位置，在每个位置上，有10个点随机偏移正态分布，标准差为窗口的1/250，聚类半径为窗口的1/100。结果看起来像这样：http://www.flickr.com/photos/antsaasma/3963640089/ - Ants Aasma

为了好玩，我尝试在分箱查找结构的基础上使用QT聚类，仍然比朴素方法快10倍，但聚类效果显著提高，平均少1.35倍的聚类。 - Ants Aasma

这是代码：http://gist.github.com/204365 我添加了一些注释以便更容易理解。 - Ants Aasma

Answer 8

如果可以的话，在初始搜索时按经度对标记进行排序；然后，一旦在排序列表中下一个标记与当前标记相距超过一个标记宽度，您就绝对知道其余标记不会重叠，因此您可以中断foreach循环并节省大量处理时间。我已经在自己的网站上实现了这一点，效率非常高。

- Tristen

---

我发现按经度（或纬度）排序的问题在于：当我浏览列表时，我会得到一个区域内的所有标记，然后它会跳到完全不同区域的标记（但经度略高）。在列表的下面，我会得到一些更多的标记，本应该在第一个区域中，但由于经度比第二个区域中的标记高，所以没有被包括在第一个区域聚类中，但仍然足够接近，应该被包括在第一个区域。希望这样说得清楚。 - Chris B

看起来你比较标记是否相交的算法不正确；我创建了一个围绕每个标记点的矩形，并测试它与排序列表中的下一个矩形的相交。一旦列表中的标记的相交测试失败，任何进一步在列表中的标记都不可能相交，因为它是已排序的。这些计算在像素空间中完成（我已将纬度/经度转换为地图上显示的像素）。 - Tristen