我有来自大量用户（数十万）的位置数据。我存储当前位置和一些历史数据点（分钟数据可以返回一小时）。
我该如何去发现聚集在生日聚会等自然事件周围的人群？应该检测甚至更少的人群（假设从5个人开始）。
该算法需要几乎实时（或至少每分钟一次）工作，以在人群发生时对其进行检测。
我研究了许多聚类分析算法，但其中大多数似乎是一个错误的选择。它们要么花费太长时间（我见过O（n ^ 3）和O（2 ^ n）），要么需要事先知道有多少个簇。
有人能帮我吗？谢谢！
最佳答案
让每个用户成为自己的集群。当她到达另一个用户的距离R以内时，形成一个新的群集，并在该人离开时再次分开。您在以下情况下有活动：
人数大于N
对于大于T的计时器，它们位于同一位置
派对不动（可能表示公共交通工具）
它不在公共服务大楼（医院，学校等）中
（其他条件很多）
一分钟是足够的时间来完成它，即使对成千上万的人也是如此。在幼稚的实现中，它将是O（n ^ 2），但是请注意，比较每个人的位置没有意义，只有比较近邻的人才有意义。首先，您可以将“世界”划分为多个扇区，这也使得并行处理任务变得容易，从而可以轻松地扩展规模。更多用户？只需添加更多节点并缩减规模即可。
一种想法是根据“质量”和重心进行思考。首先，不要将某物标记为事件，直到质量不大于例如15个单位。当然，位置是不精确的，但在发生事件的情况下，它应平均围绕事件中心。如果您的集群在不增加任何数量的情况下向任何方向增长，那么很可能是不对的。看一下像DBSCAN（基于密度的群集）之类的方法，也可以从物理系统中获得良好的灵感，甚至可以在活动受限时从Ising模型（这里是根据温度和“翻转”某人加入人群的角度）思考。
如何避免作者在评论中提到的“单链问题”？一种想法是根据“质量”和重心进行思考。首先，不要将某物标记为事件，直到质量不大于例如15个单位。当然，位置是不精确的，但是在发生事件的情况下，它应该平均围绕事件中心。如果您的集群在不增加任何数量的情况下向任何方向增长，那么很可能是不对的。看一下像DBSCAN（基于密度的群集）之类的方法，也可以从物理系统甚至是Ising模型（在这里，您根据温度来思考并“翻转”某人加入人群）获得良好的灵感。这不是一个新问题，我敢肯定有（部分）覆盖它的论文，例如Is There a Crowd? Experiences in Using Density-Based Clustering and Outlier Detection。