Tim*_*tle 26 sql database location cluster-analysis geolocation
我有一个用户提交的纬度/经度点数据库,我试图将"关闭"点组合在一起.'关闭'是相对的,但现在似乎是~500英尺.
起初,似乎我可以按照前3个小数位具有相同纬度/经度的行进行分组(大约300x300的盒子,理解它在离开赤道时会发生变化).
但是,这种方法似乎很缺乏."接近度"与每个小数位所代表的距离不能显着不同.它没有考虑到两个位置在第三个(或任何)小数位可能有不同的数字,但仍然在该位置代表(33.1239和33.1240)的距离内.
我还仔细研究了A点和C点都与B点"接近"(但不是彼此)的情况 - 它们是否应该组合在一起？如果是这样,当D点"接近"C点(并且没有其他点)时会发生什么 - 它是否应该被分组.当然,我必须确定所需的行为,但如何实施呢？
任何人都能指出我如何做到这一点以及可以使用哪些不同的方法/方法？
我觉得有点像我错过了一些明显的东西.
目前,数据是一个MySQL数据库,由PHP应用程序使用; 但是,如果它们是实现这一目标的关键部分,我会对其他存储方法持开放态度.这里.
有许多方法可以确定两点之间的距离,但是对于在二维图上绘制点,您可能需要欧几里德距离.如果(x1, y1)代表你的第一个点并(x2, y2)代表你的第二个,那么距离是
d = sqrt( (x2-x1)^2 + (y2-y1)^2 )
关于分组,您可能希望使用某种二维均值来确定彼此之间的"接近"状态.举例来说,如果你有三个点(x1, y1),(x2, y2),(x3, y3),你可以找到这三个点的简单平均的中心:
x(mean) = (x1+x2+x3)/3
y(mean) = (y1+y2+y3)/3
然后,您可以看到它们与中心的接近程度,以确定它是否应该成为"集群"的一部分.
可以通过多种方式定义群集,所有这些方法都使用群集算法的某种变体.我现在很匆忙,没有时间进行总结,但查看链接和算法,希望其他人能够提供更多细节.祝好运!
使用与您在问题中列出的方法类似的方法来获得一组近似的结果,然后通过进行适当的计算来缩小该近似值.如果您正确地选择了网格大小(即,您的坐标多少),您至少可以希望将要完成的工作量减少到可接受的水平,尽管您必须管理网格大小.
例如,PostgreSQL 的地球延伸扩展通过将纬度/长度对转换为(x,y,z)笛卡尔坐标,将地球建模为均匀球体来实现.PostgreSQL有一个复杂的索引系统,允许这些坐标或它们周围的框被索引到R树中,但是你可以将一些东西混合起来,如果没有它,它仍然是有用的.
如果你取(x,y,z)三元组并舍入 - 即乘以某个因子并截断为整数 - 那么你有三个整数可以连接以产生一个"盒子名称",它标识你的"网格"这点是在.
如果你想搜索某个目标点X km内的所有点,你会在该点周围生成所有"盒子名称"(一旦你将你的目标点转换为(x,y,z)三元组,那就是容易)并消除所有不与地球表面相交的盒子(琐事,但x^2+y^2+z^2=R^2每个角落使用公式会告诉你)你最终会得到一个目标点可以进入的盒子列表 - 所以只搜索所有点匹配其中一个盒子,这也会给你一些额外的积分.因此,作为最后阶段,您需要计算到目标点的实际距离并消除一些(再次,这可以通过在笛卡尔坐标中工作并将目标大圆距离半径转换为割线距离来加速).
摆弄到了确保你不必搜索太多的盒子,但同时不要带来太多额外的积分.我发现对几个不同网格上的每个点进行索引很有用(例如1Km,5Km,25Km,125Km等分辨率).理想情况下,您只想搜索一个框,请记住,只要目标半径超过网格大小,它就会扩展到至少27个.
我已经使用这种技术使用Lucene构建空间索引,而不是在SQL数据库中进行计算.它确实有效,虽然有一些摆弄它,并且索引需要一段时间来生成并且非常大.使用R树来保存所有坐标是一种更好的方法,但需要更多的自定义编码 - 这种技术基本上只需要快速的哈希表查找(因此可能适用于所有NoSQL数据库,这些天风靡一时,也应该可以在SQL数据库中使用).