Эффективно найти соседей по нескольким измерениям и рассчитать сумму значений на основе близости - PullRequest
2 голосов
/ 07 июня 2019

Мне поручено найти общую стоимость всех элементов на переменном расстоянии от центрального элемента.Элементы расположены в 3 измерениях (столбцы в моих данных).Каждый элемент имеет уникальное местоположение, учитывая 3 измерения (и имеет уникальный идентификатор).

У меня есть рабочая версия, которая делает то, что я хочу, однако она очень медленная.Я использую itertuples, нахожу значение для каждого кортежа с использованием подмножества фрейма данных, apply (np.isclose), и я устанавливаю значение с помощью .at (см. Код ниже).

Проблема не столько в функции моего кода, сколько в масштабируемости.Поскольку я хочу установить переменное расстояние для измерения и рассчитать это значение для каждой строки, в конечном итоге выполняется итерация nrows x ndistances, и в настоящее время каждая итерация занимает 1,7 секунды (мои данные содержат> 25 000 строк, по моим оценкам, ~ 12 часовна каждое расстояние, которое я пробую).

import pandas as pd
import numpy as np

Пример структуры данных:

df = pd.DataFrame({'id':[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19], 
                          'x':[-2,-2,-2,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,2,2,2], 
                          'y':[2,1,0,2,1,0,-1,2,1,0,-1,-2,1,0,-1,-2,0,-1,-2], 
                          'z':[0,1,2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,-2,-1,0], 
                          'val':[0,0,0,1,0,0,6,3,7,11,0,0,14,18,10,4,20,15,2]})
df.set_index('id', inplace=True)
# The 'val' column can have any non-negative whole number, I've just picked some randomly.

«Рабочий» код до сих пор:

n = 0  #Initial distance
while n < 3:  #This part allows me to set my distance range
    df['n{0}'.format(n)] = np.nan  #create a column for the new values
    for row in df.itertuples():
        valsum = df[(df['x'].apply(np.isclose, b=row.x, atol=n)) & 
                    (df['y'].apply(np.isclose, b=row.y, atol=n)) & 
                    (df['z'].apply(np.isclose, b=row.z, atol=n))].val.sum()
        df.at[row.Index, 'n{0}'.format(n)] = valsum
    n += 1

Текущий / требуемый выход:

    x   y   z   val n0  n1  n2
id                          
1   -2  2   0   0   0   1   22
2   -2  1   1   0   0   0   25
3   -2  0   2   0   0   6   17
4   -1  2   -1  1   1   11  54
5   -1  1   0   0   0   19  70
6   -1  0   1   0   0   17  57
7   -1  -1  2   6   6   6   31
8   0   2   -2  3   3   25  74
9   0   1   -1  7   7   54  99
10  0   0   0   11  11  46  111
11  0   -1  1   0   0   31  73
12  0   -2  2   0   0   10  33
13  1   1   -2  14  14  62  99
14  1   0   -1  18  18  95  105
15  1   -1  0   10  10  60  107
16  1   -2  1   4   4   16  66
17  2   0   -2  20  20  67  100
18  2   -1  -1  15  15  65  101
19  2   -2  0   2   2   31  80

Я знаю, что столбец 'n0' равен столбцу 'val', потому что расстояние поиска равно 0, но я хотел показать, что я ищу.Сумма всех элементов в столбце val равна 111, что совпадает, когда (x, y, z) = (0,0,0).Это потому, что (0,0,0) является центром моих данных в этом примере, и поэтому наличие расстояния 2 охватывает все элементы.Я хотел бы сделать это для полосы пропускания расстояний, скажем, 5-10.

Мой последний вопрос: как я могу сделать это, но быстрее / эффективнее?

Ответы [ 3 ]

2 голосов
/ 07 июня 2019

Здесь решение, которое не требует дополнительных пакетов.

Это функции, которые определяют расстояние между двумя точками a и b.Здесь показаны евклидово, манхэттенское и чебышевское расстояние (кредиты @ Peter Leimbigler answer , который признал, что последний - тот, который использовал ОП).a и b предполагаются как список из 3-х длин.Вы можете использовать одну из них (или даже определить другие настраиваемые функции расстояния).

def euclidean(a, b):
    """euclidean distance"""
    return np.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2 + (a[2] - b[2])**2) 

def manhattan(a, b):
    """manhattan distance"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1]) + abs(a[2] - b[2])

def cebyshev(a, b):
    """cebyshev distance"""
    return max(abs(a[0] - b[0]), abs(a[1] - b[1]), abs(a[2] - b[2]))

Следующая функция возвращает для точки point сумму значений столбца val в кадре данных data (это ваш фрейм данных), координаты которого ближе, чем расстояние d.func - это функция, используемая для расчета расстояния (одна из тех, что были раньше).

def getclosesum(data, point, d, func):
    dists = data.apply(lambda x : func(x, point), axis=1)
    return data['val'].loc[dists <= d].sum()

Наконец, вы можете рассчитать свой столбец, используя df.apply:

for n in range(3):
    df['n{0}'.format(n)] = df.apply(lambda x : getclosesum(df, x, n, cebyshev), axis=1)

ИспользуяПримерный кадр данных, на моей машине этот код занимает 0,155 секунды, а ваш оригинальный код - 0,233 секунды.
Так что это быстрее, чем ваше решение, но не так быстро, как код, предоставленный @Peter Leimbigler (держу париscikit более оптимизировано).

2 голосов
/ 07 июня 2019

Поиск ближайших соседей в k-мерном пространстве является классическим случаем структуры данных дерева kd ( Wikipedia ).Scikit-learn имеет гибкую реализацию ( docs ), которую я использую ниже, так как условная логика, используемая в вашем вопросе, по-видимому, определяет метрику расстояния Чебышева ( Wikipedia ), которая scikit-learnподдерживает изначально.SciPy cKDTree ( документы , C ++ исходный код ) поддерживает только евклидову (L2) метрику расстояния, но оптимизирован для нее и, следовательно, может быть быстрее.

# Setup
df = pd.DataFrame({'id':[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19], 
                   'x':[-2,-2,-2,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,2,2,2], 
                   'y':[2,1,0,2,1,0,-1,2,1,0,-1,-2,1,0,-1,-2,0,-1,-2], 
                   'z':[0,1,2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,-2,-1,0], 
                   'val':[0,0,0,1,0,0,6,3,7,11,0,0,14,18,10,4,20,15,2]})
df.set_index('id', inplace=True)


from sklearn.neighbors import KDTree

# Build k-d tree with the Chebyshev metric, AKA L-infinity
tree = KDTree(df[['x', 'y', 'z']].values, metric='chebyshev')

for radius in [0, 1, 2]:
    # Populate new column with placeholder integer
    df[f'n{radius}'] = -1
    for i, row in df.iterrows():
        coords = row[['x', 'y', 'z']].values.reshape(1, -1)
        idx = tree.query_radius(coords, r=radius)[0]
        df.loc[i, f'n{radius}'] = df.iloc[idx]['val'].sum()

df
    x  y  z  val  n0  n1   n2
id                           
1  -2  2  0    0   0   1   22
2  -2  1  1    0   0   0   25
3  -2  0  2    0   0   6   17
4  -1  2 -1    1   1  11   54
5  -1  1  0    0   0  19   70
6  -1  0  1    0   0  17   57
7  -1 -1  2    6   6   6   31
8   0  2 -2    3   3  25   74
9   0  1 -1    7   7  54   99
10  0  0  0   11  11  46  111
11  0 -1  1    0   0  31   73
12  0 -2  2    0   0  10   33
13  1  1 -2   14  14  62   99
14  1  0 -1   18  18  95  105
15  1 -1  0   10  10  60  107
16  1 -2  1    4   4  16   66
17  2  0 -2   20  20  67  100
18  2 -1 -1   15  15  65  101
19  2 -2  0    2   2  31   80
1 голос
/ 10 июня 2019

В этом решении также используется KDTrees (из библиотеки scipy).

В вашем коде и предыдущих ответах, когда цикл вычисляет результат для радиуса = 3, он повторяет работу, уже проделанную для радиуса = 0, 1, и 2.

Приведенный ниже код выполняет все вычисления за один проход через узлы. Определите максимальное расстояние и количество ячеек диапазона. Найдите все пары узлов с максимальным расстоянием и используйте np.digitize(), чтобы отобразить фактическое расстояние до бина диапазона. Добавьте 'val' в сопоставленную корзину диапазона.

import pandas as pd
import numpy as np

from scipy.spatial import cKDTree as KDTree

# define the range and number of range bins 
# this example defines 3 bins: 0.0 - 1.0; 1.0 - 2.0; 2.0 - 3.0
max_distance = 3.0
nbins = 3
bin_range = 0.0, max_distance
bins = np.linspace(*bin_range, nbins+1)[1:]

# build a KDTree and generate a sparse matrix of node pairs
# that have a max distance of bin_range[-1]
tree = KDTree(df[['x','y','z']])
dist = tree.sparse_distance_matrix(tree, bin_range[-1])

# one row per node, one column per range bin
sums = np.zeros((len(df), nbins))

# for each pair of nodes, map the range to the bin index and add
# the value of the second node to mapped bin for the 1st node 
for (j,k),d in dist.items():
    sums[j][np.digitize(d, bins)] += df['val'][k+1]

Для каждого узла массив sums содержит строку с суммами для диапазонов. Например, первый столбец содержит сумму значений для узлов с расстоянием <1, второй столбец для узлов между 1 и 2 и третий столбец для узлов между 2 и 3. Вы можете накопить по столбцам, чтобы получить то же самое результаты в виде таблицы. </p>

sums

array([[ 0.,  1., 21.],
       [ 0.,  0., 25.],
       [ 0.,  6., 11.],
       [ 1., 10., 43.],
       [ 0., 19., 51.],
       [ 0., 17., 40.],
       [ 6.,  0., 25.],
       [ 3., 22., 49.],
       [ 7., 47., 45.],
       [11., 35., 65.],
       [ 0., 31., 42.],
       [ 0., 10., 23.],
       [14., 48., 37.],
       [18., 77., 10.],
       [10., 50., 47.],
       [ 4., 12., 50.],
       [20., 47., 33.],
       [15., 50., 36.],
       [ 2., 29., 49.]])
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...