Как (аккуратно) перебрать все точки в GeoDataframe и посмотреть на ближайших соседей - PullRequest
Новая
       15

Как (аккуратно) перебрать все точки в GeoDataframe и посмотреть на ближайших соседей

1 голос
/ 21 июня 2019

У меня есть большой (O (10 ^ 6) рядов) набор данных (точки со значениями), где мне нужно сделать следующее для всех точек:

  • Найти 3 ближайшие точки в пределах предварительно определенногоradius.
  • Рассчитайте среднее значение связанного значения для этих трех точек.
  • Сохраните это среднее значение в точке, которую я смотрю

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

Я включил игрушечный пример, который делает то, что я хочу.Из идей, которые я уже рассмотрел:

  • с использованием shapely.ops.nearest_points: Это, однако, только возвращает одну ближайшую точку.
  • буферизует вокруг каждой отдельной точки и делаетsjoin с оригинальным GeoDataframe: кажется, что масштаб будет даже хуже, чем наивный подход.

Вот забавный пример логики, которую я хочу реализовать: 

import pandas as pd
import numpy as np
from shapely.wkt import loads
import geopandas as gp

points=[
    'POINT (1 1.1)', 'POINT (1 1.9)', 'POINT (1 3.1)',
    'POINT (2 1)', 'POINT (2 2.1)', 'POINT (2 2.9)',
    'POINT (3 0.8)', 'POINT (3 2)', 'POINT (3 3)'
]
values=[9,8,7,6,5,4,3,2,1]

df=pd.DataFrame({'points':points,'values':values})
gdf=gp.GeoDataFrame(df,geometry=[loads(x) for x in df.points], crs={'init': 'epsg:' + str(25832)})

for index,row in gdf.iterrows(): # Looping over all points
    gdf['dist'] = np.nan
    for index2,row2 in gdf.iterrows(): # Looping over all the other points
        if index==index2: continue
        d=row['geometry'].distance(row2['geometry']) # Calculate distance
        if d<3: gdf.at[index2,'dist']=d # If within cutoff: Store
        else: gdf.at[index2,'dist']=np.nan # Otherwise, be paranoid and leave NAN
    # Calculating mean of values for the 3 nearest points and storing 
    gdf.at[index,'mean']=np.mean(gdf.sort_values('dist').head(3)['values'].tolist())

print(gdf)

Результирующий GeoDataframe находится здесь: 

          points  values       geometry      dist      mean
0  POINT (1 1.1)       9  POINT (1 1.1)  2.758623  6.333333
1  POINT (1 1.9)       8  POINT (1 1.9)  2.282542  7.000000
2  POINT (1 3.1)       7  POINT (1 3.1)  2.002498  5.666667
3    POINT (2 1)       6    POINT (2 1)  2.236068  5.666667
4  POINT (2 2.1)       5  POINT (2 2.1)  1.345362  4.666667
5  POINT (2 2.9)       4  POINT (2 2.9)  1.004988  4.333333
6  POINT (3 0.8)       3  POINT (3 0.8)  2.200000  4.333333
7    POINT (3 2)       2    POINT (3 2)  1.000000  3.000000
8    POINT (3 3)       1    POINT (3 3)       NaN  3.666667

Вы можете видеть состояние последней итерации.

  • Все расстояния были рассчитаны, кроме последнего места, которое было оставлено в NAN.
  • Среднее значение последней итерации является средним значением трех ближайших точек: 2, 4 и 5, а именно 3 666667.

Как мне это сделатьболее масштабируемым образом?

Ответы [ 2 ]

1 голос
/ 24 июня 2019

Я бы использовал пространственный индекс для этого.Вы можете использовать возможность libpysal, которая использует KDTree под капотом.Для 2000 случайных точек следующий код выполняется на 3,5 секунды по сравнению с вашим, который работает целую вечность (я потерял терпение после первой минуты).Сохранение значений в списке, а затем преобразование списка в столбец DF также экономит ваше время. 

import pandas as pd
import numpy as np
from shapely.wkt import loads
import geopandas as gp
import libpysal

points=[
    'POINT (1 1.1)', 'POINT (1 1.9)', 'POINT (1 3.1)',
    'POINT (2 1)', 'POINT (2 2.1)', 'POINT (2 2.9)',
    'POINT (3 0.8)', 'POINT (3 2)', 'POINT (3 3)'
]
values=[9,8,7,6,5,4,3,2,1]

df=pd.DataFrame({'points':points,'values':values})
gdf=gp.GeoDataFrame(df,geometry=[loads(x) for x in df.points], crs={'init': 'epsg:' + str(25832)})

knn3 = libpysal.weights.KNN.from_dataframe(gdf, k=3)

means = []
for index, row in gdf.iterrows(): # Looping over all points
    knn_neighbors = knn3.neighbors[index]
    knnsubset = gdf.iloc[knn_neighbors]
    neighbors = []
    for ix, r in knnsubset.iterrows():
        if r.geometry.distance(row.geometry) < 3: # max distance here
            neighbors.append(ix)

    subset = gdf.iloc[list(neighbors)]
    means.append(np.mean(subset['values']))
gdf['mean'] = means

Это результат: 

          points  values       geometry      mean
0  POINT (1 1.1)       9  POINT (1 1.1)  6.333333
1  POINT (1 1.9)       8  POINT (1 1.9)  7.000000
2  POINT (1 3.1)       7  POINT (1 3.1)  5.666667
3    POINT (2 1)       6    POINT (2 1)  5.666667
4  POINT (2 2.1)       5  POINT (2 2.1)  4.666667
5  POINT (2 2.9)       4  POINT (2 2.9)  4.333333
6  POINT (3 0.8)       3  POINT (3 0.8)  4.333333
7    POINT (3 2)       2    POINT (3 2)  3.000000
8    POINT (3 3)       1    POINT (3 3)  3.666667
0 голосов
/ 21 июня 2019

Это напоминает мне математическую задачу, которую я делал в колледже некоторое время назад.Он тесно связан с Глава 7 Пример 7 .Таким образом, проблема заключается в

Рассмотрим набор клиентов мобильных компьютеров в определенном городе, каждый из которых должен быть подключен к одной из нескольких возможных базовых станций.Предположим, что существует n клиентов, причем положение каждого клиента определяется его (x, y) координатами на плоскости.Есть также k базовых станций;положение каждого из них также определяется координатами (x, y).Для каждого клиента мы хотим подключить его точно к одной из базовых станций.Наш выбор соединений ограничен следующими способами. Существует параметр диапазона r, так что клиент может быть подключен только к базовой станции, которая находится на расстоянии r.Существует также параметр загрузки L, так что к любой отдельной базовой станции может быть подключено не более L клиентов.Ваша цель - разработать алгоритм с полиномиальным временем для следующей задачи.Учитывая расположение набора клиентов и набора базовых станций, а также параметры диапазона и нагрузки, решите, может ли каждый клиент быть подключен одновременно к базовой станции, с учетом диапазона и условий нагрузки в предыдущем абзаце.

Я полагаю, что вы можете преобразовать эту проблему в проблему сетевого потока за полиномиальное время, а затем использовать модифицированный алгоритм Форда-Фулкерсона, чтобы решить ее для того, что вы ищете в O (n * m + cmax) время при условии, что вы добавляете только операции с постоянным временем в ford-fulkersonЭто может не быть масштабируемой проблемой и может быть в списке проблем полиномиального времени, но, возможно, это будет лучший подход, чем постоянно O (n ^ 2) время выполнения.

Для получения информации о том, как преобразовать эток проблеме с сетевым потоком, я бы попытался прочитать псевдоиш-код этого человека .Пароль pdf - птицы

...