4

我想对一组大约进行预聚类。500,000 点。

我还没有开始，但这是我认为我会做的：

  • 将所有点存储在 localSOLR 索引中
  • 根据一些行政信息确定“自然集群位置”（例如大城市）
  • 然后为每个城市计算一个集群：
    • 每个城市
      • 对于每个缩放级别
        • 查询索引以获取城市周围半径中包含的点（半径的长度取决于缩放级别）

这应该非常有效，因为只有 100 个主要城市，而且 SOLR 查询非常快。但再想一想，发现这是错误的：

  1. 可能存在比城市更“接近”的点集群：它们应该拥有自己的集群
  2. 在某些缩放级别下，某些点不会在任何城市的可接受距离内，因此不会被计算在内
  3. 一些城市彼此靠近，因此，一些点将被计算两次（添加到两个集群）

还有其他方法：

  • 检查每个点并确定它属于哪个集群；这消除了上面的问题2和3，但不是1，而且效率也极低
  • 制作（矩形）网格（针对每个缩放级别）；这可行，但会导致疯狂/任意的集群，这些集群并不“意味着”任何东西

我想我正在寻找一种通用的地理聚类算法（或想法），但似乎找不到任何东西。

编辑以回答 Geert-Jan 的评论

我想建立“自然”的集群，是的，是的，我担心如果我使用任意网格，它不会反映数据的真实性。例如，如果在两个矩形的交点处或附近的一个点周围发生了许多事件，我应该只得到一个集群，但实际上会构建两个（每个矩形中一个）。

最初出于性能原因我想使用 localSOLR（因为我知道它，并且有更好的经验将大量数据索引到 SOLR 中而不是加载到传统数据库中）；但是由于我们谈论的是预聚类，因此性能可能并不那么重要（尽管可视化新聚类实验的结果不应该花费数天时间）。我第一种根据预定义的“大点”集查询大量点的方法显然是有缺陷的，我提到的第一个原因是最强的：集群应该反映数据的现实，而不是其他一些官僚定义（它们会显然重叠，当然，但数据应该是第一位的）。

有一个用于实时集群的出色集群器，已添加到核心 Google Maps API：Marker Clusterer。我想知道是否有人试图“离线”运行它：运行它需要的任何时间，然后存储结果？

或者是否有一个聚类器可以逐点检查每个点，并输出包含坐标和点数的聚类，并且在合理的时间内执行此操作？

4

1 回答 1

1

您可能想研究先进的聚类算法，例如 OPTICS。

有了良好的数据库索引，它应该会相当快。

于 2013-04-06T23:34:56.807 回答