如何对存储在SQL中的纬度和经度位置进行分组

Question

我试图分析英国周期事故的数据,以找到统计黑点.以下是来自其他网站的数据示例.http://www.cycleinjury.co.uk/map

我目前正在使用SQLite来实现~100k存储lat/lon位置.我想将附近的地点组合在一起.此任务称为群集分析.

我想通过忽略孤立的事件来简化数据集,而只是显示在一个小区域内发生多个事故的集群的起源.

我需要克服3个问题.

1. 性能 - 如何确保快速找到附近的点.我应该使用的SQLite的实现了的R树的例子吗？

2. 链条 - 如何避免拾取附近的链条？

3. 密度 - 如何考虑周期人口密度？伦敦的自行车运动员的人口密度远远超过布里斯托尔,因此伦敦似乎有更多的支持者.

我想避免像这样的'链'场景:

相反,我想找到集群:

伦敦截图(我手绘了一些集群)......

布里斯托尔截图 - 密度低得多 - 如果不考虑相对密度,在该区域上运行的相同程序可能找不到任何黑点.

任何指针都会很棒!

Answer 1

好吧,你的问题描述与DBSCAN聚类算法(维基百科)完全相同.它避免了链效应,因为它要求它们至少是minPts对象.

至于密度的差异,这就是OPTICS(维基百科)应该解决的问题.您可能需要使用不同的方法来提取群集.

嗯,好吧,也许不是100% - 你可能想拥有单个热点,而不是"密度连接"的区域.在考虑OPTICS图时,我认为你只对小而深的山谷感兴趣,而不是大山谷.您可以使用OPTICS绘图扫描"至少10次事故"的局部最小值.

更新:感谢指向数据集的指针.这真的很有趣.所以我没有把它过滤给骑自行车的人,但是现在我正在使用所有带坐标的120万条记录.我已将它们送入ELKI进行分析,因为它非常快,实际上它可以使用大地距离(即纬度和经度)而不是欧几里德距离,以避免偏差.我已经启用了STR批量加载的R*树索引,因为这应该有助于获得运行下来不少.我正在使用Xi = .1,epsilon = 1(km)和minPts = 100运行OPTICS(仅查找大型集群).运行时间大约是11分钟,不算太差.当然OPTICS图的宽度为120万像素,因此对于完全可视化而言并不是很好.鉴于巨大的门槛,它确定了18个集群,每个集群有100-200个实例.接下来我会尝试将这些集群可视化.但绝对可以尝试更低的minPts进行实验.

以下是发现的主要集群:

• 51.690713 -0.045545在伦敦北部的A10公路上穿过M25公路
• 51.477804 -0.404462"Waggoners Roundabout"
• 51.690713 -0.045545"Halton Cross Roundabout"或它的南面
• 51.436707 -0.499702 A30和A308 Staines By-Pass的叉子
• 53.556186 -2.489059 M61出口到曼彻斯特西北部的A58
• 55.170139 -1.53​​2917 A189,North Seaton Roundabout
• 55.067229 -1.577334 A189和A19,就在这个南边,一个四车道的环形交叉路口.
• 51.570594 -0.096159 Manour House,Picadilly Line
• 53.477601 -1.152863 M18和A1(M)
• 53.091369 -0.789684 A1,A17和A46,A1的两侧都有环形交叉口的复杂构造.
• 52.949281 -0.97896 A52和A46
• 50.659544 -1.15251怀特岛,桑当.
• ...

请注意,这些只是从群集中获取的随机点.相反,计算例如聚类中心和半径可能是明智的,但我没有这样做.我只是想了解一下这个数据集,看起来很有趣.

以下是一些截图,minPts = 50,epsilon = 0.1,xi = 0.02:

请注意,使用OPTICS,群集可以是分层的.这是一个细节: