人群聚类分析

Question

我有来自大量用户(数十万)的位置数据。我存储当前位置和几个历史数据点(分钟数据返回一个小时)。

我该如何去探测聚集在自然事件中的人群，比如生日派对等等？更少的人群(假设从5人开始)应该被发现。该算法需要在几乎实时(或至少每分钟一次)工作，以发现人群的发生。

我研究过许多聚类分析算法，但它们中的大多数看起来都是个糟糕的选择。他们要么花的时间太长(我见过O(n^3)和O(2^n))，要么需要事先知道有多少簇。

有人能帮我吗？谢谢!

Answer 1

让每个用户都是自己的集群。当她离另一个用户很近时，R就会形成一个新的集群，当这个人离开时再次分离。你有你的活动时：

• 人数大于N
• 对于大于T的定时器，它们在同一个位置。
• 聚会不动(可能表示公共交通)
• 它不在公共服务大楼(医院、学校等)。
• (其他条件数目多)

即使在成千上万的人身上，一分钟也是足够的时间去完成。在简单的实现中，它将是O(n^2)，但是请记住，比较每个人的位置是没有意义的，只有那些近邻的人。在第一种近似下，您可以将“世界”划分为多个部门，这也使任务更容易并行--进而更容易扩展。更多的用户？只需再添加几个节点并缩小规模即可。

一个想法是从“质量”和重心的角度来思考。首先，在质量不超过15个单位之前，不要将某物标记为事件。当然，地点是不精确的，但如果是事件，它应该平均围绕活动的中心。如果集群在没有增加大量质量的情况下向任何方向发展，那么它很可能是不正确的。看看DBSCAN (基于密度的聚类)之类的方法，也可以从物理系统中得到很好的灵感，甚至是Ising模型(在这里你可以从温度和“翻转”某人加入人群的角度来考虑)--在活动有限的时候。

如何避免作者在评论中提到的“单链问题”？一个想法是从“质量”和重心的角度来思考。首先，在质量不超过15个单位之前，不要将某物标记为事件。当然，地点是不精确的，但如果是事件，它应该平均围绕活动的中心。如果集群在没有增加大量质量的情况下向任何方向发展，那么它很可能是不正确的。看看诸如DBSCAN (基于密度的聚类)这样的方法，物理系统，甚至Ising模型也可以得到很好的灵感(在这里，您认为从温度和“翻转”某人加入人群的角度来看)。这不是一个新的问题，我相信会有一些论文(部分地)覆盖它，例如有人群吗？基于密度聚类和孤立点检测的经验。

Answer 2

做一个完整的聚类几乎没有什么用处。

只是使用了很好的数据库索引。

保存当前职位的数据库。

每当你得到一个新的坐标，查询数据库所需的半径，比如说50米。一个好的索引将在O(log )中对一个小半径做这件事。如果您得到足够的结果，这可能是一个事件，或某人加入一个正在进行的事件。