Самый быстрый способ вычисления кратчайшего (евклидова) расстояния между точками в панде - PullRequest
Новая
       21

Самый быстрый способ вычисления кратчайшего (евклидова) расстояния между точками в панде

2 голосов
/ 08 ноября 2019

Рассмотрим следующий кадр данных pandas: 

print(df)

     Id      X      Y Type  X of Closest  Y of Closest
0   201  73.91  34.84    A           NaN           NaN
1   201  74.67  32.64    A           NaN           NaN
2   201  74.00  33.20    A           NaN           NaN
3   201  71.46  27.70    A           NaN           NaN
4   201  69.32  35.42    A           NaN           NaN
5   201  75.06  24.00    B           NaN           NaN
6   201  74.11  16.64    B           NaN           NaN
7   201  73.37  18.73    B           NaN           NaN
8   201  56.63  26.90    B           NaN           NaN
9   201  73.35  38.83    B           NaN           NaN
10  512  74.15  28.90    A           NaN           NaN
11  512  75.82  17.56    A           NaN           NaN
12  512  74.78  33.21    A           NaN           NaN
13  512  75.43  32.41    A           NaN           NaN
14  512  75.90  25.12    A           NaN           NaN
15  512  79.76  29.49    B           NaN           NaN
16  512  76.47  36.91    B           NaN           NaN
17  512  74.70  19.19    B           NaN           NaN
18  512  78.75  30.53    B           NaN           NaN
19  512  74.60  31.88    B           NaN           NaN

Обратите внимание, что для каждого Id всегда есть 10 строк, 5 типа A и 5 типа B.

Мне бы хотелосьсоздать 2 столбца: «X из ближайшего» и «Y из ближайшего». Я имею в виду пару X, Y (противоположного типа на Id), которая является кратчайшим евклидовым расстоянием.

Пример для первой строки: Ближайшая пара (типа B) - (73.91, 34.84)это пара (73,35,38,83), которая имеет евклидово расстояние 4,03.

Один (возможный !?) способ - построить 10 столбцов - евклидово расстояние между точками в каждом идентификаторе, а затем выбрать минимальное евклидово расстояние от противоположного типа. Я уверен, что будет гораздо более быстрый путь.

Ответы [ 2 ]

1 голос
/ 08 ноября 2019

Для быстрого решения (кодирования) мы можем использовать apply в групповом режиме: 

from scipy.spatial import distance_matrix

def get_min_dist(x):
    # compute distance matrix
    tmp = distance_matrix(x.iloc[:5], x.iloc[5:])

    # get index min of corresponding types
    idx = np.concatenate((np.argmin(tmp,1)+5),  # type A to type B
                          np.argmin(tmp, 0)     # type B to type A
                        )

    return pd.DataFrame(x.iloc[idx].values, 
                        index=x.index, 
                        columns=[a+'_closest' for a in x.columns])

df.groupby('Id')[['X','Y']].apply(get_min_dist)

Выход: 

    X_closest  Y_closest
0       73.35      38.83
1       73.35      38.83
2       73.35      38.83
3       75.06      24.00
4       73.35      38.83
5       71.46      27.70
6       71.46      27.70
7       71.46      27.70
8       71.46      27.70
9       73.91      34.84
10      74.60      31.88
11      74.70      19.19
12      74.60      31.88
13      74.60      31.88
14      79.76      29.49
15      75.43      32.41
16      74.78      33.21
17      75.82      17.56
18      75.43      32.41
19      75.43      32.41
0 голосов
/ 08 ноября 2019

Вот мое решение с использованием вещания Numpy 

df = pd.DataFrame([[201, 73.91, 34.84, 'A', np.nan, np.nan], [201, 74.67, 32.64, 'A', np.nan, np.nan], [201, 74.0, 33.2, 'A', np.nan, np.nan], [201, 71.46, 27.7, 'A', np.nan, np.nan], [201, 69.32, 35.42, 'A', np.nan, np.nan], [201, 75.06, 24.0, 'B', np.nan, np.nan], [201, 74.11, 16.64, 'B', np.nan, np.nan], [201, 73.37, 18.73, 'B', np.nan, np.nan], [201, 56.63, 26.9, 'B', np.nan, np.nan], [201, 73.35, 38.83, 'B', np.nan, np.nan], [512, 74.15, 28.9, 'A', np.nan, np.nan], [512, 75.82, 17.56, 'A', np.nan, np.nan], [512, 74.78, 33.21, 'A', np.nan, np.nan], [512, 75.43, 32.41, 'A', np.nan, np.nan], [512, 75.9, 25.12, 'A', np.nan, np.nan], [512, 79.76, 29.49, 'B', np.nan, np.nan], [512, 76.47, 36.91, 'B', np.nan, np.nan], [512, 74.7, 19.19, 'B', np.nan, np.nan], [512, 78.75, 30.53, 'B', np.nan, np.nan], [512, 74.6, 31.88, 'B', np.nan, np.nan]], columns=('Id', 'X', 'Y', 'Type', 'X-of-Closest', 'Y-of-Closest'))

## assuming that df is sorted by ID and Type we can create this 4 dimensional array where
## dim0->no of unique ids, dim1-> 2 (type A, B), dim2->5 values of each type, dim3->X or Y
values = df[['X','Y']].values.reshape(-1,2, 5, 2).copy()

## values[:,0,:,:] will take rows of type A for all ids
## and the broadcast repeates values of type A and B 5 times each
## which represents 5X5=25 possible pairs of points of type A and B
diff = values[:,0,:,:][:,:,np.newaxis,:] - values[:,1,:,:][:,np.newaxis,:,:]

## get index of min distance for type A and B 
ind1 = np.argmin(np.sum(diff**2, axis=-1), axis=-1)
ind2 = np.argmin(np.sum(diff**2, axis=-1), axis=-2)

## use the index to set point with min distance to other type
closest_points = np.empty_like(values)
closest_points[:,0] = values[0,1,ind1]
closest_points[:,1] = values[0,0,ind2]

## assign result back to df
df[["X-of-Closest","Y-of-Closest"]] = closest_points.reshape(-1,2)
print(df)

Результат 

     Id      X      Y Type  X-of-Closest  Y-of-Closest
0   201  73.91  34.84    A         73.35         38.83
1   201  74.67  32.64    A         73.35         38.83
2   201  74.00  33.20    A         73.35         38.83
3   201  71.46  27.70    A         75.06         24.00
4   201  69.32  35.42    A         73.35         38.83
5   201  75.06  24.00    B         71.46         27.70
6   201  74.11  16.64    B         71.46         27.70
7   201  73.37  18.73    B         71.46         27.70
8   201  56.63  26.90    B         71.46         27.70
9   201  73.35  38.83    B         73.91         34.84
10  512  74.15  28.90    A         73.35         38.83
11  512  75.82  17.56    A         73.37         18.73
12  512  74.78  33.21    A         73.35         38.83
13  512  75.43  32.41    A         73.35         38.83
14  512  75.90  25.12    A         75.06         24.00
15  512  79.76  29.49    B         71.46         27.70
16  512  76.47  36.91    B         74.00         33.20
17  512  74.70  19.19    B         74.67         32.64
18  512  78.75  30.53    B         71.46         27.70
19  512  74.60  31.88    B         71.46         27.70

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

...