作者：小小明

在一堆基站经纬度数据中，时常涉及三种计算，例如查找某个点最近的N个点，查找某个点指定距离范围内的所有点，将距离小于指定阈值聚类的基站聚类在一起。

下面我们看看计算方法。

import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

首先读取数据集：

excel = pd.io.excel.ExcelFile("point.xlsx")
find = excel.parse("查找")
data = excel.parse("数据库")
# 去除重复数据
find.drop_duplicates(ignore_index=True, inplace=True)
data.drop_duplicates(ignore_index=True, inplace=True)
data.reset_index(drop=False, inplace=True)
print("被查找的点：", find.shape)
display(find.head())
print("经纬度数据库：", data.shape)
display(data.head())

数据预处理

为了后续计算方便，我们可以将被被查找表对应到经纬度数据库的索引保存起来：

data.rename(columns={"index": "索引"}, inplace=True)
find = pd.merge(find, data, how="left")
find.head()

计算被查找的点是否不在数据库中：

find.query("索引.isnull()", engine="python").shape[0]

返回0，说明所有被查找的坐标点都在数据库内。

为了后续计算方便，我们可以将被被查找表的索引对应到经纬度数据库：

find.index = data.index[data.小区名称.isin(find.小区名称)]
find

将坐标信息可视化一下，看一下整体分布:

plt.figure(dpi=200)
plt.scatter(data.Longitude,  data.Latitude, s=10, color='blue', alpha=0.1)
plt.scatter(find.Longitude, find.Latitude, s=1, color='red', alpha=0.1)
plt.show()

从图中的颜色深浅可以看到很多点的位置几乎相同，导致颜色叠加的比较深。

下面首先我们来计算一下每个点最近的N个点：

查找每个点最近的N个点

首先提取经纬度数据转成numpy数组：

data_p = data.values[:, 2:4]
find_p = find.values[:, 1:3]
print(data_p.shape, find_p.shape)

(5306, 2) (1773, 2)

创建用于计算两个经纬度距离的函数：

from math import *


def distancefuc(s1, s2):
    "创建用于计算两个经纬度距离的函数"
    # 经纬度转换成弧度
    lon1, lat1 = map(radians, s1)
    lon2, lat2 = map(radians, s2)
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
    distance = round(2 * asin(sqrt(a)) * 6371000, 1)  # 地球平均半径，6371km
    return distance

可以使用已经封装好的NearestNeighbors创建BallTree模型：

from sklearn.neighbors import NearestNeighbors

nn = NearestNeighbors(metric=distancefuc, algorithm='ball_tree')
nn.fit(data_p)

但我们直接使用内层BallTree类，因为API更加简单直接：

from sklearn.neighbors import BallTree
bt = BallTree(data_p, metric=distancefuc)

由于每个被查找点都存在于数据库中，所以必然找出的n个点会包含自身，但我们可以先找出最近的n+1个点，再去掉自身。

比如我们想找出每个点最近的10个点，可以先找出最近的11个点：

# 结果与nn.kneighbors(find_p, 11, return_distance=True)一样
distances, points = bt.query(find_p, 11, return_distance=True)
print(distances[:1])
print(points[:1])

[[  0.    0.    0.    0.    0.    0.  364.7 364.7 364.7 364.7 364.7]]
[[  11   15   13   12    2   14   17 4065   18   20 4067]]

下面我们首先将结果整合到表格中：

find["最近点索引"] = points.tolist()
find["距离"] = distances.tolist()
find

可视化检查BallTree查找效果

查看可用的颜色表：

plt.colormaps()

对于连续性colormap可以通过以下方法获取颜色值，可自由设置颜色个数：

cm = plt.get_cmap('gist_rainbow')
NUM_COLORS = 22
colors = [cm(1.*i/NUM_COLORS) for i in range(NUM_COLORS)]

对于离散颜色值使用以下命令获取颜色列表：

colors = plt.get_cmap('tab20b').colors

下面我们随机找20个点，并用不同的颜色可视化每个点最近的10个点：

plt.figure(figsize=(18, 8), dpi=100)
plt.scatter(data.Longitude,  data.Latitude, s=20, color='black', alpha=0.1)
for c, p in zip(plt.get_cmap('tab20b').colors, find.sample(20).最近点索引.values):
    plt.scatter(data.loc[p].values[:, 2],
                data.loc[p].values[:, 3], s=50, color=c, alpha=1)
plt.show()

可以看到颜色相近的正好在一起。

为了更清晰的看到效果，我们将其显示到folium地图上。

首先定义颜色值列表：

colors = ['cyan', 'lightblue', 'rosybrown', 'seagreen', 'sandybrown', 'salmon', 'silver', 'darkmagenta', 'darkorchid', 'honeydew',
          'cadetblue', 'thistle', 'blue', 'palegoldenrod', 'cornflowerblue', 'lightseagreen', 'hotpink', 'gainsboro', 'aqua',
          'lavender', 'darkturquoise', 'lightgray', 'lemonchiffon', 'cornsilk', 'chocolate', 'saddlebrown', 'darkolivegreen',
          'beige', 'tomato', 'darkslateblue', 'darkorange', 'mediumseagreen', 'orchid', 'chartreuse', 'darkblue', 'indianred',
          'lightsteelblue', 'navy', 'coral', 'limegreen', 'lime', 'sienna', 'deeppink', 'pink', 'gold', 'greenyellow', 'mediumorchid',
          'crimson', 'mediumslateblue', 'aquamarine', 'plum', 'lightcoral', 'orange', 'lightsalmon', 'papayawhip', 'lightgoldenrodyellow',
          'snow', 'olive', 'red', 'burlywood', 'mediumblue', 'darkcyan', 'skyblue', 'indigo', 'powderblue', 'darkgoldenrod', 'gray',
          'oldlace', 'darkgray', 'blueviolet', 'royalblue', 'khaki', 'darkgreen', 'palegreen', 'dimgray', 'floralwhite', 'firebrick',
          'navajowhite', 'mediumpurple', 'steelblue', 'lightcyan', 'ghostwhite', 'lightpink', 'bisque', 'whitesmoke', 'mediumturquoise',
          'fuchsia', 'ivory', 'slategray', 'darkviolet', 'deepskyblue', 'seashell', 'mintcream', 'forestgreen', 'mediumspringgreen',
          'azure', 'teal', 'green', 'wheat', 'lawngreen', 'lavenderblush', 'yellow', 'slateblue', 'peachpuff', 'mediumvioletred',
          'violet', 'peru', 'white', 'orangered', 'lightskyblue', 'darkred', 'aliceblue', 'blanchedalmond', 'mistyrose', 'linen',
          'yellowgreen', 'antiquewhite', 'springgreen', 'darkseagreen', 'lightgreen', 'lightslategray', 'goldenrod', 'paleturquoise',
          'purple', 'magenta', 'turquoise', 'black', 'tan', 'mediumaquamarine', 'dodgerblue', 'midnightblue', 'palevioletred',
          'darkslategray', 'lightyellow', 'maroon', 'brown', 'moccasin', 'olivedrab', 'darksalmon', 'darkkhaki']

folium地图可视化展示

使用pip安装folium后可以直接使用：

import folium
import itertools
from folium import plugins
m = folium.Map(location=[data.Latitude.median(), data.Longitude.median()],
               zoom_start=12, zoom_control='False', control_scale=True,
               tiles='http://webrd02.is.autonavi.com/appmaptile?lang=zh_cn&size=1&scale=1&style=8&x={x}&y={y}&z={z}',
               attr='&copy; <a href="http://ditu.amap.com/">高德地图</a>'
               )
# 为地图对象添加点击显示经纬度的子功能
# m = m.add_child(folium.LatLngPopup())

incidents = folium.map.FeatureGroup()
for p in data.values[:, [3, 2]]:
    incidents.add_child(
        folium.CircleMarker(  # CircleMarker表示画圆
            p.tolist(),  # 坐标
            radius=1,  # 圆圈半径
            color='gray',  # 标志的外圈颜色
        )
    )
colors_iter = iter(colors)
for name1, y1, x1, i, ps, ds in find.sample(140).values:
    color = next(colors_iter)
    for p, d in zip(ps, ds):
        j, name2, y2, x2 = data.loc[p]
        folium.PolyLine(locations=[(x1, y1), (x2, y2)], color=color).add_to(m)
        incidents.add_child(
            folium.Circle(  # CircleMarker表示画圆
                (x2, y2),  # 坐标
                radius=50,  # 圆圈半径
                color='blue',  # 标志的外圈颜色
                tooltip=f"{name2}\n距离\n{name1}\n{d:.2f}米",
                fill=True,  # 是否填充
                fill_color='blue',  # 填充颜色
                fill_opacity=0.05  # 填充透明度
            )
        )
    incidents.add_child(
        folium.CircleMarker(  # CircleMarker表示画圆
            (x1, y1),  # 坐标
            radius=1,  # 圆圈半径
            color='red',  # 标志的外圈颜色
            tooltip=name1,
        )
    )
m.add_child(incidents)
m

上面是随机选取140个点的地图可视化效果，地图可以任意放大缩小。

这是放大后，一些点的可视化效果。

图中红色点表示从被查找点随机选取的140个点，每个红色点与找到的最近10个点会有一个连线，终点会画一个50米的圆，根据填充色的颜色深度可以知道当前点与其他点的重合程度，与其重合的点越多颜色越深。

结果整理

下面我们将查找到的结果组织成每行如下列的格式：

• 查找点
• 经度-查找点
• 维度-查找点
• 附件点
• 经度-附件点
• 维度-附件点
• 距离-米

实际测试中发现，当找到距离等于0的点超过10个时，也可能不包含自身，所以发现不包含自身时也需要删除：

result = []
for name1, y1, x1, i, ps, ds in find.values:
    try:
        idx = ps.index(i)
    except ValueError:
        idx = -1
    if idx > 0 or len(ps) > 10:
        ps.pop(idx)
        ds.pop(idx)
    for p, d in zip(ps, ds):
        name2, y2, x2 = data.loc[p].values[1:4]
        result.append((name1, y1, x1, name2, y2, x2, d))
result = pd.DataFrame(result, columns=["查找点", "经度-查找点",
                                       "维度-查找点", "附件点", "经度-附件点", "维度-附件点", "距离-米"])
result

纯数据处理的整体代码

from sklearn.neighbors import BallTree
from math import *
import pandas as pd

# 数据预处理
excel = pd.io.excel.ExcelFile("point.xlsx")
find = excel.parse("查找")
data = excel.parse("数据库")
# 去除重复数据
find.drop_duplicates(ignore_index=True, inplace=True)
data.drop_duplicates(ignore_index=True, inplace=True)
data.reset_index(drop=False, inplace=True)

data.rename(columns={"index": "索引"}, inplace=True)
find = pd.merge(find, data, how="left")
find.index = data.index[data.小区名称.isin(find.小区名称)]
data_p = data.values[:, 2:4]
find_p = find.values[:, 1:3]


def distancefuc(s1, s2):
    "创建用于计算两个经纬度距离的函数"
    # 经纬度转换成弧度
    lon1, lat1 = map(radians, s1)
    lon2, lat2 = map(radians, s2)
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
    distance = round(2 * asin(sqrt(a)) * 6371000, 1)  # 地球平均半径，6371km
    return distance


bt = BallTree(data_p, metric=distancefuc)
distances, points = bt.query(find_p, 11, return_distance=True)
find["最近点索引"] = points.tolist()
find["距离"] = distances.tolist()
result = []
for name1, y1, x1, i, ps, ds in find.values:
    try:
        idx = ps.index(i)
    except ValueError:
        idx = -1
    if idx > 0 or len(ps) > 10:
        ps.pop(idx)
        ds.pop(idx)
    for p, d in zip(ps, ds):
        name2, y2, x2 = data.loc[p].values[1:4]
        result.append((name1, y1, x1, name2, y2, x2, d))
result = pd.DataFrame(result, columns=["查找点", "经度-查找点",
                                       "维度-查找点", "附件点", "经度-附件点", "维度-附件点", "距离-米"])

至此我们就完成了最近N个点的查找。

下面我们再继续演示需求2：

查找每个点N米范围内的所有点

前面我们已经创建了BallTree模型，并加载了经纬度数据库数据，直接使用前面创建的模型即可。

例如我们要查找半径500米范围内的点：

# 与distances, points = nn.radius_neighbors(find_p, 500, return_distance=True)结果一样
points, distances = bt.query_radius(find_p, 500, return_distance=True)
print(distances[:1])
print(points[:1])

[array([364.7, 364.7, 364.7, 364.7, 364.7, 364.7, 364.7, 364.7, 364.7,
          0. ,   0. ,   0. ,   0. ,   0. , 414.1, 414.1, 414.1, 414.1,
          0. ])                                                       ]
[array([  20, 4065,   18, 1355, 4066,   16,   17, 4067,   19,   12,    2,
          13,   11,   15, 1363,   34,   35,   36,   14], dtype=int64)    ]

find["最近点索引"] = points.tolist()
find["距离"] = distances.tolist()
find

下面我通过folium地图可视化看看查找效果：

folium地图可视化展示

同样，随机选140个点，查看查找效果：

import folium
import itertools
from folium import plugins
m = folium.Map(location=[data.Latitude.median(), data.Longitude.median()],
               zoom_start=12, zoom_control='False', control_scale=True,
               tiles='http://webrd02.is.autonavi.com/appmaptile?lang=zh_cn&size=1&scale=1&style=8&x={x}&y={y}&z={z}',
               attr='&copy; <a href="http://ditu.amap.com/">高德地图</a>'
               )
# 为地图对象添加点击显示经纬度的子功能
# m = m.add_child(folium.LatLngPopup())

incidents = folium.map.FeatureGroup()
for p in data.values[:, [3, 2]]:
    incidents.add_child(
        folium.CircleMarker(  # CircleMarker表示画圆
            p.tolist(),  # 坐标
            radius=1,  # 圆圈半径
            color='grey',  # 标志的外圈颜色
        )
    )
colors_iter = iter(colors)
for name1, y1, x1, i, ps, ds in find.sample(140).values:
    # 对于每个被查找的点画一个500米范围的圆
    incidents.add_child(
        folium.Circle(
            (x1, y1),
            radius=500,
            color='blue',
            tooltip=name1,
        )
    )
    color = next(colors_iter)
    for (name2, y2, x2), d in zip(data.loc[ps].values[:, 1:], ds):
        incidents.add_child(
            folium.CircleMarker(  # CircleMarker表示画圆
                (x2, y2),
                radius=3,
                color=color,
                tooltip=f"{name2}\n距离\n{name1}\r{d:.2f}米",
                fill=True,  # 是否填充
                fill_color=color,  # 填充颜色
                fill_opacity=1  # 填充透明度
            )
        )
    incidents.add_child(
        folium.CircleMarker(  # CircleMarker表示画圆
            (x1, y1),  # 坐标
            radius=1,  # 圆圈半径
            color='red',  # 标志的外圈颜色
            tooltip=name1,
        )
    )
m.add_child(incidents)
m

放大再看看：

经过几轮检查，可以发现被找到的点都在蓝色圆的范围内。证明我们使用BallTree模型找到的点都有效。

下面将结果整理成需求1一样的结果形式：

结果整理

result = []
for name1, y1, x1, i, ps, ds in find.values:
    ps, ds = ps.tolist(), ds.tolist()
    try:
        idx = ps.index(i)
    except ValueError:
        idx = -1
    if idx > 0:
        ps.pop(idx)
        ds.pop(idx)
    for p, d in zip(ps, ds):
        name2, y2, x2 = data.loc[p].values[1:4]
        result.append((name1, y1, x1, name2, y2, x2, d))
result = pd.DataFrame(result, columns=["查找点", "经度-查找点",
                                       "维度-查找点", "附件点", "经度-附件点", "维度-附件点", "距离-米"])
result

需求2整体代码

from sklearn.neighbors import BallTree
from math import *
import pandas as pd

# 数据预处理
excel = pd.io.excel.ExcelFile("point.xlsx")
find = excel.parse("查找")
data = excel.parse("数据库")
# 去除重复数据
find.drop_duplicates(ignore_index=True, inplace=True)
data.drop_duplicates(ignore_index=True, inplace=True)
data.reset_index(drop=False, inplace=True)

data.rename(columns={"index": "索引"}, inplace=True)
find = pd.merge(find, data, how="left")
find.index = data.index[data.小区名称.isin(find.小区名称)]
data_p = data.values[:, 2:4]
find_p = find.values[:, 1:3]


def distancefuc(s1, s2):
    "创建用于计算两个经纬度距离的函数"
    # 经纬度转换成弧度
    lon1, lat1 = map(radians, s1)
    lon2, lat2 = map(radians, s2)
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
    distance = round(2 * asin(sqrt(a)) * 6371000, 1)  # 地球平均半径，6371km
    return distance


bt = BallTree(data_p, metric=distancefuc)
points, distances = bt.query_radius(find_p, 500, return_distance=True)
find["最近点索引"] = points.tolist()
find["距离"] = distances.tolist()
result = []
for name1, y1, x1, i, ps, ds in find.values:
    ps, ds = ps.tolist(), ds.tolist()
    try:
        idx = ps.index(i)
    except ValueError:
        idx = -1
    if idx > 0:
        ps.pop(idx)
        ds.pop(idx)
    for p, d in zip(ps, ds):
        name2, y2, x2 = data.loc[p].values[1:4]
        result.append((name1, y1, x1, name2, y2, x2, d))
result = pd.DataFrame(result, columns=["查找点", "经度-查找点",
                                       "维度-查找点", "附件点", "经度-附件点", "维度-附件点", "距离-米"])

聚类距离小于N米的点

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。

数据预处理

为了减少无效计算，并方便可视化，下面先将经纬度数据库中经纬度完全相同的基站去重：

excel = pd.io.excel.ExcelFile("point.xlsx")
data = excel.parse("数据库")
# 去除经纬度的重复数据
data.drop_duplicates(subset=["Longitude", "Latitude"],
                     ignore_index=True, inplace=True)
print("经纬度数据库：", data.shape)
display(data.head())
data_p = data.values[:, 1:]
print(data_p.shape)

下面我们的需求是将半径500米范围内的基站都归为一类：

from sklearn.cluster import DBSCAN

db = DBSCAN(eps=500, min_samples=1, metric=distancefuc, algorithm='ball_tree')
# 调用DBSCAN方法进行训练，labels为每个数据的类别标签
labels = db.fit_predict(data_p)
data["类别"] = labels
data["类别数量"] = data.groupby("类别")["小区名称"].transform("count")
data

至此通过密度聚类算法DBSCAN已经将距离小于500米的基站分到同一类，给了一个唯一的类别标签。

计算每个类别下的最大距离

下面，计算一下每个类别下所有基站之间的最大距离：

t = pd.Series(index=data.index)
for i, df_split in data.groupby("类别"):
    ps = df_split[["Longitude", "Latitude"]].values
    bt = BallTree(ps, metric=distancefuc)
    k = len(ps)
    _, ds = bt.query(ps, k)
    t.loc[df_split.index] = ds.max()
data["最大距离"] = t
data

可视化聚类效果

import folium
import itertools
from folium import plugins
m = folium.Map(location=[data.Latitude.median(), data.Longitude.median()],
               zoom_start=12, zoom_control='False', control_scale=True,
               tiles='http://webrd02.is.autonavi.com/appmaptile?lang=zh_cn&size=1&scale=1&style=8&x={x}&y={y}&z={z}',
               attr='&copy; <a href="http://ditu.amap.com/">高德地图</a>'
               )
# 为地图对象添加点击显示经纬度的子功能
m = m.add_child(folium.LatLngPopup())

incidents = folium.map.FeatureGroup()

colors_iter = itertools.cycle(colors)
for i, df_split in data.groupby("类别"):
    color = next(colors_iter)
    for name, y, x in df_split.values[:, :3]:
        incidents.add_child(
            folium.Circle(
                (x, y),
                radius=500,
                color=color,
                tooltip=name,
            )
        )
        incidents.add_child(
            folium.CircleMarker(
                (x, y),
                radius=1,
                color='red',
            )
        )

m.add_child(incidents)
m

任意选个位置放大看看：

需求3数据处理整体代码

from math import *
from sklearn.cluster import DBSCAN
import pandas as pd
from sklearn.neighbors import BallTree

data = pd.read_excel("point.xlsx", "数据库")
# 去除经纬度的重复数据
data.drop_duplicates(subset=["Longitude", "Latitude"],
                     ignore_index=True, inplace=True)
print("经纬度数据库：", data.shape)
data_p = data.values[:, 1:]


def distancefuc(s1, s2):
    "创建用于计算两个经纬度距离的函数"
    # 经纬度转换成弧度
    lon1, lat1 = map(radians, s1)
    lon2, lat2 = map(radians, s2)
    dlon = lon2 - lon1
    dlat = lat2 - lat1
    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
    distance = round(2 * asin(sqrt(a)) * 6371000, 1)  # 地球平均半径，6371km
    return distance


db = DBSCAN(eps=500, min_samples=1, metric=distancefuc, algorithm='ball_tree')
# 调用DBSCAN方法进行训练，labels为每个数据的类别标签
labels = db.fit_predict(data_p)
data["类别"] = labels
data["类别数量"] = data.groupby("类别")["小区名称"].transform("count")
t = pd.Series(index=data.index)
for i, df_split in data.groupby("类别"):
    ps = df_split[["Longitude", "Latitude"]].values
    bt = BallTree(ps, metric=distancefuc)
    k = len(ps)
    _, ds = bt.query(ps, k)
    t.loc[df_split.index] = ds.max()
data["最大距离"] = t