Определение взвешенных кластеров с максимальным диаметром диаметра и суммой (весом)> 50

Question

Задача

Необходимо определить способ поиска 2-мильных кластеров точек, в которых каждая точка имеет значение.Определите области в 2 мили, у которых сумма (значение)> 50.

Данные

У меня есть данные, которые выглядят следующим образом:

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

Примерно 200 тыс. Записей.Мне нужно определить, есть ли области, где сумма больше, чем сумма, превышает 65 в области радиусом в одну милю (диаметр в 2 мили).

Использование каждой точки в качестве центра для области

Теперь у меня есть код на Python из другого проекта, который будет рисовать шейп-файл вокруг точки диаметром x следующим образом:

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, чтобы увидеть, какие другие были внутри, и выполнить подсчет.

Нужен алгоритм кластеризации?

Однако может существовать область с требуемой плотностью счета, где одна из точек находится не в центре.

Я знаком с кластерными алгоритмами, такими как DBSCAN, которые используют атрибуты для классификации, но это вопрос поиска кластеров плотности, использующих значение для каждой точки.Существует ли какой-либо алгоритм кластеризации, чтобы найти кластер из круга диаметром 2 мили, в котором внутреннее число>> 50?

Любые предложения, python или R, являются предпочтительными инструментами, но это широко открытый и, вероятно, одно-выкл, поэтому эффективность вычислений не является приоритетом.

Answer 1

DBSCAN может быть адаптирован (см. Обобщенный DBSCAN; определить базовые точки как весовую сумму> = 50), но он не обеспечит максимальный размер кластера (он вычисляет транзитивные замыкания).

Вы также можете попробовать завершитьсвязь.Используйте его, чтобы найти кластеры с желаемым максимальным диаметром, затем проверьте, удовлетворяют ли они желаемой плотности.Но это не гарантирует, что вы найдете все.

Вероятно, быстрее (а) построить индекс для быстрого поиска по радиусу.(б) для каждой точки найти соседей по радиусу r;сохранить, если они имеют желаемую минимальную сумму.Но это не гарантирует, что можно найти все, потому что центр не обязательно является точкой данных.Рассмотрим максимальный радиус 1, минимальный вес 100. Две точки с весом 50 каждая, в точках (0,0) и (1,1).Ни запрос в (0,0), ни запрос в (1,1) не найдут решение, но кластер в (.5, .5) удовлетворяет условиям.

К сожалению, я считаю, что ваша проблемапо крайней мере NP-hard, так что вы не сможете позволить себе окончательное решение.

Answer 2

Не полное решение, но, возможно, оно поможет упростить проблему в зависимости от распределения ваших данных.Я буду использовать плоские координаты и cKDTree в моем примере, это может работать с географическими данными, если вы можете игнорировать кривизну в проекции.

Основное наблюдение заключается в следующем: точка (x,y) делает не вносят вклад в плотное скопление, если шар радиуса 2*r (например, 2 мили) около (x,y) вносит меньший вклад, чем пороговое значение (например, 50 в вашем названии).Фактически, любая точка в пределах 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

Пример с фиктивными данными: