人群聚类分析
Cluster Analysis for crowds of people
我有大量用户（数十万）的位置数据。我存储了当前位置和一些历史数据点（一小时前的分钟数据）。
我将如何检测聚集在生日派对等自然事件周围的人群？应该检测到更小的人群（假设从 5 人开始）。
该算法需要几乎实时（或至少每分钟一次）工作以检测人群。
我研究了很多聚类分析算法，但其中大多数似乎都是一个糟糕的选择。它们要么花费太长时间（我见过 O(n^3) 和 O(2^n)），要么需要事先知道有多少个簇。
有人可以帮助我吗？谢谢！
让每个用户成为它自己的集群。当她到达另一个用户的距离 R 以内时，形成一个新的集群，并在该人离开时再次分离。您的活动时间：
- 人数大于N
- 对于大于T的定时器，它们在同一个地方
- 派对没有移动（可能表示 public 运输）
- 它不在 public 服务大楼（医院、学校等）
- （很多其他条件）
即使对数十万人来说，一分钟也足够完成。在天真的实现中，它将是 O(n^2)，但请注意，比较每个人的位置是没有意义的，只有那些在附近的人。在第一个近似值中，您可以将 "world" 划分为多个扇区，这也使得并行任务变得容易 - 进而可以轻松扩展。更多用户？只需再添加几个节点并缩小规模即可。
一个想法是根据 'mass' 和重心来思考。首先，不要将某物标记为事件，直到质量不大于例如15个单位。当然，位置不精确，但在发生事件的情况下，它应该平均在事件中心附近。如果你的集群在没有增加大量质量的情况下向任何方向增长，那么它很可能是不正确的。看看DBSCAN（基于密度的聚类）之类的方法，也可以从物理系统中获得很好的灵感，甚至是伊辛模型（这里你考虑温度和"flipping"有人加入人群）在有限的时间喝啤酒activity.
如何避免作者在评论中提到"single-linkage problem"？一种想法是根据 'mass' 和重心来思考。首先，不要将某物标记为事件，直到质量不大于例如15个单位。当然，位置不精确，但在发生事件的情况下，它应该平均在事件中心附近。如果你的集群在没有增加大量质量的情况下向任何方向增长，那么它很可能是不正确的。看看像 DBSCAN（基于密度的聚类）这样的方法，也可以从物理系统中获得很好的灵感，甚至是 Ising 模型（这里你考虑温度和 "flipping" 有人加入人群）。这不是一个新问题，我相信有论文（部分）涵盖了它，例如Is There a Crowd? Experiences in Using Density-Based Clustering and Outlier Detection.
做全聚类没什么用。
只是使用了良好的数据库索引。
保留当前位置的数据库。
每当你得到一个新的坐标时，用所需的半径查询数据库，比如 50 米。对于小半径，good 索引将在 O(log n) 中执行此操作。如果您获得足够的结果，这可能是一个活动，或者有人加入了正在进行的活动。
我有大量用户（数十万）的位置数据。我存储了当前位置和一些历史数据点（一小时前的分钟数据）。
我将如何检测聚集在生日派对等自然事件周围的人群？应该检测到更小的人群（假设从 5 人开始）。 该算法需要几乎实时（或至少每分钟一次）工作以检测人群。
我研究了很多聚类分析算法，但其中大多数似乎都是一个糟糕的选择。它们要么花费太长时间（我见过 O(n^3) 和 O(2^n)），要么需要事先知道有多少个簇。
有人可以帮助我吗？谢谢！
让每个用户成为它自己的集群。当她到达另一个用户的距离 R 以内时，形成一个新的集群，并在该人离开时再次分离。您的活动时间：
- 人数大于N
- 对于大于T的定时器，它们在同一个地方
- 派对没有移动（可能表示 public 运输）
- 它不在 public 服务大楼（医院、学校等）
- （很多其他条件）
即使对数十万人来说，一分钟也足够完成。在天真的实现中，它将是 O(n^2)，但请注意，比较每个人的位置是没有意义的，只有那些在附近的人。在第一个近似值中，您可以将 "world" 划分为多个扇区，这也使得并行任务变得容易 - 进而可以轻松扩展。更多用户？只需再添加几个节点并缩小规模即可。
一个想法是根据 'mass' 和重心来思考。首先，不要将某物标记为事件，直到质量不大于例如15个单位。当然，位置不精确，但在发生事件的情况下，它应该平均在事件中心附近。如果你的集群在没有增加大量质量的情况下向任何方向增长，那么它很可能是不正确的。看看DBSCAN（基于密度的聚类）之类的方法，也可以从物理系统中获得很好的灵感，甚至是伊辛模型（这里你考虑温度和"flipping"有人加入人群）在有限的时间喝啤酒activity.
如何避免作者在评论中提到"single-linkage problem"？一种想法是根据 'mass' 和重心来思考。首先，不要将某物标记为事件，直到质量不大于例如15个单位。当然，位置不精确，但在发生事件的情况下，它应该平均在事件中心附近。如果你的集群在没有增加大量质量的情况下向任何方向增长，那么它很可能是不正确的。看看像 DBSCAN（基于密度的聚类）这样的方法，也可以从物理系统中获得很好的灵感，甚至是 Ising 模型（这里你考虑温度和 "flipping" 有人加入人群）。这不是一个新问题，我相信有论文（部分）涵盖了它，例如Is There a Crowd? Experiences in Using Density-Based Clustering and Outlier Detection.
做全聚类没什么用。
只是使用了良好的数据库索引。
保留当前位置的数据库。
每当你得到一个新的坐标时，用所需的半径查询数据库，比如 50 米。对于小半径，good 索引将在 O(log n) 中执行此操作。如果您获得足够的结果，这可能是一个活动，或者有人加入了正在进行的活动。