乐趣区

关于后端:如何在地图上寻找最密集点的位置

  最近我在工作中遇到了一个小的需要点,大略是须要在地图上展现出一堆点中的点密度最密集的地位。最开始没想到好的办法,就应用了一个非常简单的策略——所有点的坐标求平均值,这个办法大部分的时候好用,因为大部分城市所有点位基本上都是围绕某个中心点向周围发散的。但咱们理论在线上应用的时候,遇到了两个非凡的 case。

  首先就是当点位散布呈现出异形,比方哑铃型数据分布在中间,你们求平均值的办法就会找到两头数据密度最稠密的中央,就比方咱们在成都的数据上遇到的一样,下图中的红色点位就是按平均值求进去的中心点。

  另外一种异样 case 就是数据出现圆周散布的时候,比方北京的数据,北京的核心是故宫,咱们不可能会有点位,如果间接求平均值的话,计算出来的中心点就在故宫左近,这里的数据反而是最稠密的,如下图所示。

  起初查问材料,理解到核密度这一办法能够解决咱们所遇到的问题,通过试验后发现成果还不错,所以在这里分享给大家。核密度的思路也很简略,就是遍历所有的点位,计算其余点到以后点的核密度总值,而后找出均匀密度最大的点。举个简略例子,给定一个点,如果其余某个点距这个点间隔近,密度值就高,反之就远,这个点到其余所有点的密度和求均匀就是这个点最终的密度值,这里咱们能够间接选用间隔的倒数来当成核函数,不过这个核函数是线性的,最终后果和我求平均值差别不大。

  优化下思路,如果某个点的间隔越远,是不是其带来的密度值应该越小?前人也是这么想的,于是就有了很多非线性核函数,而我最终应用了高斯核,调整好核函数的带宽后,其余点带来的密度值也会随着间隔,以正态分布的形式衰减如下图,举例越远纵轴的坐标值越低,图中的 sigma 就是咱们核函数的里的带宽。

  接下来看下计算过程和成果,因为咱们是 Java 零碎,我的最终实现是用了 java 调用了 simle 包,整体代码如下:

    private double[] getHotpot(double[][] data) {
        // 创立高斯核
        MercerKernel<double[]> kernel = new GaussianKernel(0.02);

        // 计算所有点的核密度估计
        double[] densities = new double[data.length];
        for (int i = 0; i < data.length; i++) {for (int j = 0; j < data.length; j++) {densities[i] += kernel.k(data[i], data[j]);
            }
            // 计算均匀密度
            densities[i] /= data.length;
        }

        // 找出密度最大的点
        int maxDensityIndex = 0;
        for (int i = 1; i < densities.length; i++) {if (densities[i] > densities[maxDensityIndex]) {maxDensityIndex = i;}
        }
        return data[maxDensityIndex];
    }

  这里我带宽 (高斯核中的 sigma) 用了 0.02,这个也是屡次调试后的后果,如果过大会导致算进去的密度值更靠近于全局平均值,过小的话会呈现几个点集中在一起,但四周没有其余点的状况,咱们还是拿下面两个异样的 case 看下核密度办法的成果。首先就是成都哑铃型的数据。

再来就是北京的环形数据

  下面的图中,我应用了 python 中的 sklearn 来实现核密度,应用了 folium 来绘制地图,残缺的代码也贴出来供大家参考。

# -*- coding: utf-8 -*-
import folium
import pandas as pd
from sklearn.neighbors import KernelDensity
import numpy as np

def getCenterPoint(sites):
    points = sites[['latitude', 'longitude']].values
    weights = sites['score'].values
    
    # 实例化 KernelDensity 对象
    kde = KernelDensity(kernel='gaussian', bandwidth=0.02)

    # 对数据进行拟合
    kde.fit(points) 

    # 应用 KDE 模型评估每个点的密度
    log_densities = kde.score_samples(points)

    # 密度最高的点是评估密度最高(即,log_densities 值最大)的点
    highest_density_point = points[np.argmax(log_densities)]

    print(highest_density_point.tolist())
    return highest_density_point.tolist()

# 创立一个以给定经纬度为核心的地图,初始缩放级别设为 14
m = folium.Map(zoom_start=14)

for i, s in data.iterrows():
    # 在地图上增加一个点标记
    folium.Marker(location=[s['latitude'], s['longitude']],  # 经纬度
        popup=s['resblock'], 
    ).add_to(m)
# 保留为 html 文件
centerPoint = getCenterPoint(cityDf)
folium.Marker(
    location=centerPoint,  # 经纬度
    popup='中心点',  # 弹出内容
    radius=50,
    icon=folium.Icon(color="red", icon="info-sign")
).add_to(m)

m.location = centerPoint

m.save('map.html')
退出移动版