使用歐幾里得距離在numpy數組列表中找到numpy數組的最近鄰居

Question

我有一個n維向量，並且我想使用euclidian距離在n維向量列表中找到它的k個最近鄰居。

我寫了下面的代碼（k = 10），它運行得很慢，但我想知道是否有更優化的解決方案。

def nearest_neighbors(value, array, nbr_neighbors=1): 
    return np.argsort(np.array([np.linalg.norm(value-x) for x in array]))[:nbr_neighbors] 

Answer 1

使用scipy的kd-tree。

一個小例子是available here。

許多人似乎抱怨的性能，並建議sklearn's implementation雖然（鏈接sklearn.neighbors，這是使用data-structure內部）！

Answer 2

正如sascha所說，我最終使用了scipy庫（但方法爲NearestNeighbors），將計算時間從50小時減少到36分鐘。這是我不應該嘗試重新實現自己的計算，因爲專用庫對此更加優化。

NearestNeighbors方法還允許您傳入值列表並返回每個值的k個最近鄰居。

最後的代碼是：

def nearest_neighbors(values, all_values, nbr_neighbors=10): 
    nn = NearestNeighbors(nbr_neighbors, metric='cosine', algorithm='brute').fit(all_values) 
    dists, idxs = nn.kneighbors(values)