Przyspieszenie obliczania pobliskich grup?

Question

Mam ramkę danych, która zawiera identyfikator grupy, dwie miary odległości (miara długości/szerokości geograficznej) i wartość. Dla danego zestawu odległości chcę znaleźć liczbę innych pobliskich grup oraz średnie wartości innych pobliskich grup.

Napisałem poniższy kod, ale jest tak nieefektywny, że po prostu nie kończy się w rozsądnym czasie dla bardzo dużych zestawów danych. Kalkulacja pobliskich sprzedawców jest szybka. Ale obliczenie średniej wartości pobliskich sprzedawców detalicznych to wyjątkowo powolny. Czy istnieje lepszy sposób na zwiększenie wydajności?

distances = [1,2] 

df = pd.DataFrame(np.random.randint(0,100,size=(100, 4)), 
        columns=['Group','Dist1','Dist2','Value']) 

# get one row per group, with the two distances for each row 
df_groups = df.groupby('Group')[['Dist1','Dist2']].mean() 

# create KDTree for quick searching 
tree = cKDTree(df_groups[['Dist1','Dist2']]) 

# find points within a given radius 
for i in distances: 
    closeby = tree.query_ball_tree(tree, r=i) 

    # put into density column 
    df_groups['groups_within_' + str(i) + 'miles'] = [len(x) for x in closeby] 

    # get average values of nearby groups 
    for idx, val in enumerate(df_groups.index): 
     val_idx = df_groups.iloc[closeby[idx]].index.values 
     mean = df.loc[df['Group'].isin(val_idx), 'Value'].mean() 
     df_groups.loc[val, str(i) + '_mean_values'] = mean 

    # merge back to dataframe 
    df = pd.merge(df, df_groups[['groups_within_' + str(i) + 'miles', 
           str(i) + '_mean_values']], 
        left_on='Group', 
        right_index=True) 

Answer 1

Jego jasne, że problem jest indeksowanie główną dataframe, metodą isin. Wraz ze wzrostem długości ramki danych należy wykonać znacznie większe wyszukiwanie. Proponuję zrobić to samo wyszukiwanie na mniejszej ramce danych df_groups i zamiast tego obliczyć zaktualizowaną średnią.

df = pd.DataFrame(np.random.randint(0,100,size=(100000, 4)), 
        columns=['Group','Dist1','Dist2','Value']) 
distances = [1,2] 
# get means of all values and count, the totals for each sample 
df_groups = df.groupby('Group')[['Dist1','Dist2','Value']].agg({'Dist1':'mean','Dist2':'mean', 
                    'Value':['mean','count']}) 
# remove multicolumn index 
df_groups.columns = [' '.join(col).strip() for col in df_groups.columns.values] 
#Rename columns 
df_groups.rename(columns={'Dist1 mean':'Dist1','Dist2 mean':'Dist2','Value mean':'Value','Value count': 
          'Count'},inplace=True) 


# create KDTree for quick searching 
tree = cKDTree(df_groups[['Dist1','Dist2']]) 

for i in distances: 
    closeby = tree.query_ball_tree(tree, r=i) 
    # put into density column 
    df_groups['groups_within_' + str(i) + 'miles'] = [len(x) for x in closeby] 
    #create column to look for subsets 
    df_groups['subs'] = [df_groups.index.values[idx] for idx in closeby] 
    #set this column to prep updated mean calculation 
    df_groups['ComMean'] = df_groups['Value'] * df_groups['Count'] 

    #perform updated mean 
    df_groups[str(i) + '_mean_values'] = [(df_groups.loc[df_groups.index.isin(row), 'ComMean'].sum()/
              df_groups.loc[df_groups.index.isin(row), 'Count'].sum()) for row in df_groups['subs']] 
    df = pd.merge(df, df_groups[['groups_within_' + str(i) + 'miles', 
           str(i) + '_mean_values']], 
        left_on='Group', 
        right_index=True) 

formuła i upated średnia jest tylko (m1 * n1 + n2 * m2)/(N1 + N2)

old setup 

100000 rows 
%timeit old(df) 
1 loop, best of 3: 694 ms per loop 

1000000 rows 
%timeit old(df) 
1 loop, best of 3: 6.08 s per loop 

10000000 rows 
%timeit old(df) 
1 loop, best of 3: 6min 13s per loop 

nowa konfiguracja

100000 rows 
%timeit new(df) 
10 loops, best of 3: 136 ms per loop 

1000000 rows 
%timeit new(df) 
1 loop, best of 3: 525 ms per loop 

10000000 rows 
%timeit new(df) 
1 loop, best of 3: 4.53 s per loop