查找兩個巨大CSR矩陣的行之間的歐幾里德距離

我有兩個稀疏矩陣A和B.A是120000 * 5000和B是30000 * 5000。我需要找到B中的每一行與A的所有行之間的歐式距離，然後在A中找到5行，並與B中選定的行的距離最小。由於這是一個非常大的數據，我正在使用CSR，否則我會得到內存錯誤。很明顯，對於A中的每一行，它計算（x_b - x_a）^ 2 5000次並將它們相加，然後得到一個sqrt。這個過程需要很長時間，就像11天！有什麼辦法可以更有效地做到這一點？我只需要在B中每行最低距離的5行。查找兩個巨大CSR矩陣的行之間的歐幾里德距離

我正在實現K-最近鄰居，A是我的訓練集，B是我的測試集。

來源

2017-02-13 peykaf

嗯 - 我不知道你是否可以'向量化'該代碼，以便它可以在本機代碼而不是Python中運行。加速numpy和scipy的訣竅總是能夠實現這一點。

如果你可以在1GHz的CPU中使用本機代碼運行該代碼，並使用1 FP指令作爲時鐘，那麼你可以在10小時內完成它。（5000 * 2 * 30000 * 120000）/ 1024 ** 3

將其提升至1.5Ghz x 2個CPU物理內核x 4路SIMD指令，帶乘法+積分（Intel AVX擴展，大多數CPU都可用）和您可以將這個數字嘎吱嘎吱地下到一個小時，在一個適中的核心i5機器上以2 x 100％的速度運行。但是，這需要在本地代碼中進行完全SIMD優化 - 這遠非一項微不足道的任務（儘管如果你決定走這條道路，那麼關於SO的進一步問題可以得到人們的幫助，或者用SIMD編碼弄溼他們的手:-)） - 接口這個代碼在C中與Scipy並不是很難用cython，例如（你只需要那部分就可以把它變成10個小時以上的數字）

現在...至於算法優化和保持Python的東西:-)
事實是，你不需要完全計算全部距離A行的距離 - 你只需要保留一個排序的5行較低的列表 - 任何時候累加的平方和大於第5個最近的行（到目前爲止），您只需中止該行的計算。

你可以使用Python的heapq操作爲：

import heapq 
import math 

def get_closer_rows(b_row, a): 
    result = [(float("+inf"), None) * 5] 
    for i, a_row in enumerate(a): 
     distance_sq = 0 
     count = 0 
     for element_a, element_b in zip(a_row, b_row): 
      distance_sq += element_a * element_b 
      if not count % 64 and distance_sq > result[4][0]: 
       break 
      count += 1 
     else: 
      heapq.heappush(result, (distance, i)) 
      result[:] = result[:5] 
    return [math.sqrt(r) for r in result] 

closer_rows_to_b = [] 
for row in b: 
    closer_rows_to_b.append(get_closer_rows(row, a))

注意附配‘計數’，以避免價值昂貴的檢索和對比所有的乘法。現在，如果您可以使用pypy而不是常規Python來運行此代碼，我相信它可以充分利用JITting，並且如果您在純Python中運行代碼（例如：non numpy/scipy向量化代碼）。

來源

2017-02-14 05:05:30 jsbueno

查找兩個巨大CSR矩陣的行之間的歐幾里德距離

回答

相關問題