machine-learning - 人群聚类分析

Question

我拥有大量用户(数十万)的位置数据。我存储当前位置和一些历史数据点(一小时前的分钟数据)。

我将如何检测聚集在生日聚会等自然事件周围的人群？甚至更小的人群(假设从 5 人开始)也应该被检测到。该算法需要几乎实时(或至少每分钟一次)工作，以在人群发生时检测到它们。

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

有人可以帮助我吗？谢谢!

Answer 1

让每个用户都有自己的集群。当她到达另一个用户的距离 R 内时，形成一个新的集群，并在该人离开时再次分开。您在以下时间举办事件:

• 人数大于N
• 对于大于 T 的计时器，它们位于同一位置
• 该方没有移动(可能表示有公共(public)交通工具)
• 不位于公共(public)服务建筑(医院、学校等)
• (许多其他条件)

即使对数十万人来说，一分钟也足够完成任务。在简单的实现中，时间复杂度为 O(n^2)，但请注意，比较每个人的位置是没有意义的，只有那些邻近的人。在第一近似中，您可以将“世界”划分为多个扇区，这也使得任务并行化变得容易 - 进而轻松扩展。更多用户？只需添加更多节点并缩小规模即可。

一个想法是从“质量”和重心的角度来思考。首先，在质量不大于例如15 个单位。当然，位置并不精确，但如果发生事件，它应该平均在事件中心附近。如果你的星团在没有增加大量质量的情况下向任何方向增长，那么很可能它是不对的。看看像 DBSCAN(基于密度的聚类)这样的方法，也可以从物理系统中获得很好的灵感，甚至可以从伊辛模型(在这里你用温度来思考，并在事件有限时“翻转”某人加入人群)啤酒。

如何避免作者在评论中提到的“单联动问题”？一种想法是从“质量”和重心的角度来思考。首先，在质量不大于例如15 个单位。当然，位置并不精确，但如果发生事件，它应该平均在事件中心附近。如果你的星团在没有增加大量质量的情况下向任何方向增长，那么很可能它是不对的。看看像 DBSCAN(基于密度的聚类)这样的方法，也可以从物理系统甚至伊辛模型中获得很好的灵感(在这里你可以用温度来思考并“翻转”某人加入人群)。这不是一个新问题，我确信有论文(部分)涵盖了它，例如Is There a Crowd? Experiences in Using Density-Based Clustering and Outlier Detection .