Геопространственная охота на кластеры с фиксированным радиусом в питоне

Question

Я хочу взять ввод миллионов длинных точек широты (с числовым атрибутом) и затем найти все геопространственные кластеры с фиксированным радиусом, где сумма атрибута в круге выше определенного порога.

Я начал с использования sklearn BallTree для суммирования атрибута в любом определенном круге, чтобы затем расширить его, чтобы пробегать сетку или решетку окружностей.Время пробега для одного круга составляет около 0,01 с, так что это хорошо для небольших решеток, но не масштабируется, если я хочу пробежать круги радиусом 200 м по всей территории Великобритании.

#example data (use 2m rows from postcode centroid file)
df = pandas.read_csv('National_Statistics_Postcode_Lookup_Latest_Centroids.csv', usecols=[0,1], nrows=2000000)
#this will be our grid of points (or lattice) use points from same file for example
df2 = pandas.read_csv('National_Statistics_Postcode_Lookup_Latest_Centroids.csv', usecols=[0,1], nrows=2000)

#reorder lat long columns for balltree input
columnTitles=["Y","X"]
df = df.reindex(columns=columnTitles)
df2 = df2.reindex(columns=columnTitles)

# assign new columns to existing dataframe. attribute will hold the data we want to sum over (set to 1 for now)
df['attribute'] = 1
df2['aggregation'] = 0

RADIANT_TO_KM_CONSTANT = 6367
class BallTreeIndex:
    def __init__(self, lat_longs):
        self.lat_longs = np.radians(lat_longs)
        self.ball_tree_index =BallTree(self.lat_longs, metric='haversine')

    def query_radius(self,query,radius):
        radius_km = radius/1000
        radius_radiant = radius_km / RADIANT_TO_KM_CONSTANT
        query = np.radians(np.array([query]))
        indices = self.ball_tree_index.query_radius(query,r=radius_radiant)
        return indices[0]

#index the base data
a=BallTreeIndex(df.iloc[:,0:2])
#begin to loop over the lattice to test performance
for i in range(0,100):
    b = df2.iloc[i,0:2]
    output = a.query_radius(b, 200)
    accumulation = sum(df.iloc[output, 2])
    df2.iloc[i,2] = accumulation

По ощущениямкак будто приведенный выше код действительно неэффективен, так как мне не нужно выполнять вычисления на всех кругах в моей решетке (так как большинство будет намного ниже моего порога - или вообще не будет иметь точек данных).

Вместо этого для цикла, есть ли лучший способ масштабирования этого алгоритма, чтобы дать мне наиболее плотные круги?

Я новичок в Python, поэтому любая помощь будет высоко ценится !!

Answer 1

Сначала не пытайтесь сделать это на сфере!ГБ маленький, и у нас есть четкая географическая проекция, которая будет работать.Поэтому используйте столбцы oseast1m и osnorth1m в качестве X и Y. Они указаны в метрах, поэтому не нужно переводить (примерно) в градусы и использовать Haversine.Это должно помочь.

Затем добавьте пространственный индекс для ускорения поиска.

Если вам нужна большая скорость, есть различные приемы, такие как загрузка 2R-полосы по всей стране впамяти, а затем проведите ваши круги по этой полосе, затем двигайтесь вниз по шагу сетки и обновите эту полосу (проверка значений Y по фиксированному значению выполняется быстро, особенно если вы сохраняете данные, отсортированные по Y, а затем по значению X).Если вам нужна большая скорость, посмотрите на любую из статей, которые Стэн Опеншоу * (а иногда и я) писал о распараллеливании GAM.Существуют примеры реализации GAM в python (например, , эта статья , , эта статья ), которые также могут указывать на лучшие пути.