algorithm - 是否有任何点聚类算法可以将点收集到附近的组中？

Question

我正在编写一个 iOS 照片管理应用程序。

我想通过他们的 GPS 信息将照片分组。然后我可以得到一个 Group 的平均 GPS 信息，并给这个 group 一个名字，例如：Trip to New York。

是否有任何方便的算法可以通过 GPS 信息将附近的照片分组？

Answer 1

忘记k-means的通常回复。这很简单，但根本不适合这项任务。

看看DBSCAN（维基百科）。它是您需要的目标。您可以指定一个半径（如果您使用大圆距离，您可以使用米！）和最小集群大小。如果您的集群的密度变化很大，并且 DBSCAN 合并了它不应该的集群，您可以尝试OPTICS (Wikipedia)，它甚至不需要 epsilon 参数，只需要最小集群大小。然而，它确实会产生分层集群。因此，您将拥有例如一组埃菲尔铁塔图片，位于一组巴黎图片中。

DBSCAN 的一个很好的特性是它具有噪声的概念。不属于集群的对象。

Answer 2

我建议使用方形网格的空间索引或空间填充曲线。它类似于四叉树，您可以为每个 gps 对计算一个 quadkey 或 geohash。这是一种平铺算法并细分平面。它也是一个分层集群。