python - 识别最大距离直径和总和（权重）> 50 的加权聚类

Question

问题

需要找到一种方法来找到 2 英里的点集群，其中每个点都有一个值。确定总和（值）> 50 的 2 英里区域。

数据

我的数据如下所示

ID        COUNT LATITUDE    LONGITUDE
187601546   20  025.56394   -080.03206
187601547   25  025.56394   -080.03206
187601548   4   025.56394   -080.03206
187601550   0   025.56298   -080.03285

大约 20 万条记录。我需要确定的是，在半径一英里（直径 2 英里）的区域中，是否有任何区域的计数总和超过 65。

使用每个点作为区域的中心

现在，我有来自另一个项目的 python 代码，它将围绕 x 直径的点绘制一个 shapefile，如下所示：

def poly_based_on_distance(center_lat,center_long, distance, bearing):
# bearing is in degrees
# distance in miles
# print ('center', center_lat, center_long)

    destination = (vincenty(miles=distance).destination(Point(center_lat, 
       center_long), bearing).format_decimal())

还有一个返回目的地的例程，然后查看哪些点在半径内。

## This is the evaluation for overlap between points and 
    ## area polyshapes
    area_list = []
    store_geo_dict = {}
    for stores in locationdict:
        location = Polygon(locationdict[stores])

        for areas in AREAdictionary:
            area = Polygon(AREAdictionary[areass])
            if store.intersects(area):
                area_list.append(areas)

        store_geo_dict[stores] = area_list
        area_list = []

在这一点上，我只是在每个 200K 点周围绘制一个圆形 shapefile，看看还有哪些其他人在里面并进行计数。

需要聚类算法？

但是，可能存在具有所需计数密度的区域，其中一个点不在中心。

我熟悉使用属性进行分类的 DBSCAN 等聚类算法，但这是使用每个点的值找到密度聚类的问题。是否有任何聚类算法可以找到内部计数> = 50 的 2 英里直径圆的任何聚类？

任何建议，python 或 R 都是首选工具，但这是广泛开放的，可能是一次性的，因此计算效率不是优先事项。

标签： pythoncluster-analysis

Answer 1

不是一个完整的解决方案，但可能有助于简化问题，具体取决于数据的分布。我将在我的示例中使用平面坐标和 cKDTree，如果您可以忽略投影中的曲率，这可能适用于地理数据。

主要观察结果如下：如果周围的半径球（例如 2 英里）的贡献小于截止值（例如标题中的 50 ），则一个点(x,y)不会对密集集群做出贡献。事实上， 中的任何点都不会对蚂蚁密集集群做出贡献。2*r(x,y)r(x,y)

这使您可以反复放弃考虑的点。如果你没有点，就没有密集的集群；如果您留下一些点，则可能存在集群。

import numpy as np
from scipy.spatial import cKDTree

# test data
N = 1000
data = np.random.rand(N, 2)
x, y = data.T

# test weights of each point
weights = np.random.rand(N)


def filter_noncontrib(pts, weights, radius=0.1, cutoff=60):
    tree = cKDTree(pts)
    contribs = np.array(
        [weights[tree.query_ball_point(pt, 2 * radius)].sum() for pt in pts]
    )
    return contribs >= cutoff


def possible_contributors(pts, weights, radius=0.1, cutoff=60):
    n_pts = len(pts)
    while len(pts):
        mask = filter_noncontrib(pts, weights, radius, cutoff)
        pts = pts[mask]
        weights = weights[mask]

        if len(pts) == n_pts:
            break

        n_pts = len(pts)

    return pts

带有虚拟数据的示例：