python - 如何在 pandas 数据帧上优化双 for 循环？

Question

我有这两个数据框:

df = pd.DataFrame({'Points':[0,1,2,3],'Axis1':[1,2,2,3], 'Axis2':[4,2,3,0],'ClusterId':[1,2,2,3]})
df
   Points  Axis1  Axis2  ClusterId
0       0      1      4          1
1       1      2      2          2
2       2      2      3          2
3       3      3      0          3

Neighbour = pd.DataFrame()
Neighbour['Points'] = df['Points']
Neighbour['Closest'] = np.nan
Neighbour['Distance'] = np.nan

Neighbour
   Points  Closest  Distance
0       0      NaN       NaN
1       1      NaN       NaN
2       2      NaN       NaN
3       3      NaN       NaN

我希望最近列包含不在同一簇中的最近点(df中的ClusterId)，基于以下距离函数，应用于轴1和轴2:

def distance(x1,y1,x2,y2):
    dist = sqrt((x1-x2)**2 + (y1-y2)**2)
    return dist 

我希望距离列包含该点与其最近点之间的距离。

以下脚本可以工作，但我认为这实际上不是在 Python 中执行的最佳方法:

for i in range(len(Neighbour['Points'])): 
    bestD = -1 #best distance
    #bestP for best point
    for ii in range(len(Neighbour['Points'])): 
        if df.loc[i,"ClusterId"] != df.loc[ii,"ClusterId"]: #if not share the same cluster
            dist = distance(df.iloc[i,1],df.iloc[i,2],df.iloc[ii,1],df.iloc[ii,2])
            if dist < bestD or bestD == -1:
                bestD = dist
                bestP = Neighbour.iloc[ii,0]
    Neighbour.loc[i,'Closest'] = bestP
    Neighbour.loc[i,'Distance'] = bestD

Neighbour
   Points  Closest  Distance
0       0      2.0  1.414214
1       1      0.0  2.236068
2       2      0.0  1.414214
3       3      1.0  2.236068

是否有更有效的方法来填充“最近”和“距离”列(特别是没有 for 循环)？这可能是使用map和reduce的合适场合，但我真的不知道如何使用。

Answer 1

要计算距离，您可以使用 scipy.spatial.distance.cdist在 DataFrame 的底层 ndarray 上。这可能比双循环更快。

>>> import numpy as np
>>> from scipy.spatial.distance import cdist

>>> distance_matrix = cdist(df.values[:, 1:3], df.values[:, 1:3], 'euclidean')
>>> distance_matrix
array([[0.        , 2.23606798, 1.41421356, 4.47213595],
       [2.23606798, 0.        , 1.        , 2.23606798],
       [1.41421356, 1.        , 0.        , 3.16227766],
       [4.47213595, 2.23606798, 3.16227766, 0.        ]])
>>> np.fill_diagonal(distance_matrix, np.inf) # set diagonal to inf so minimum isn't distance(x, x) = 0
>>> distance_matrix
array([[       inf, 2.23606798, 1.41421356, 4.47213595],
       [2.23606798,        inf, 1.        , 2.23606798],
       [1.41421356, 1.        ,        inf, 3.16227766],
       [4.47213595, 2.23606798, 3.16227766,        inf]])

为了加快速度，您还可以检查 pdist函数而不是 cdist，当您有 50_000 行时，它占用的内存更少。
还有KDTree旨在找到一个点的最近邻居。

然后你可以使用np.argmin来获取最近的距离，并检查最近的点是否在簇中，如下所示(但我没有尝试):

for i in range(len(Neighbour['Points'])):
    same_cluster = True
    while same_cluster:
        index_min = np.argmin(distance_matrix[i])
        same_cluster = (df.loc[i,"ClusterId"] == df.loc[index_min,"ClusterId"])
        if same_cluster:
            distance_matrix[i][index_min] = np.inf
    Neighbour.loc[i,'Closest'] = index_min
    Neighbour.loc[i,'Distance'] = distance_matrix[i][index_min]