尋找樣本子集的最近鄰居

Question

我有一個約300萬樣本（每個只有3個特徵）的數據集。我使用scikit的sklearn.neighbors模塊 - 特別是radius_neighbor_graph - 來查找哪些樣本屬於特定樣本的小半徑範圍內。

這工作正常，但毫不奇怪，它真的很慢，計算此圖。

這也是非常浪費的，因爲我只需要知道鄰居的一小部分樣本（約10萬） - 我事先知道這個子集。

那麼......有沒有什麼方法可以通過計算給定半徑範圍內的鄰居爲這個樣本子集提高效率？看起來應該很簡單，但我想不出一個簡單的方法。

Answer 1

首先，創建半徑鄰域圖的任務包括讀取與您的數據集關聯的N×N距離矩陣。由於距離矩陣具有很好的屬性，所以可以節省一些時間，但複雜性仍然存在於O（N^2）中。這裏N是數據集X中的數據點的數量。

所以可以這麼說，只有少數的N點作爲鄰域的中心是有意義的，但大多數點只是作爲鄰居有趣。這將導致n×n距離矩陣，其中行i包含數據點i與每個其他數據點j的距離，但是這個「距離矩陣」沒有一個正常距離矩陣（它甚至不是一個矩形矩陣）的理想屬性，您可以使用它來加速創建epsilon-neighborhood-graph的過程。

因此我不認爲你會爲你的情況找到預定義的函數。如果你想建立一個你自己的，步驟應該如下：讓X是你的數據集，我是感興趣的數據點。

1. 創建與您的數據集關聯的距離矩陣D，使用scipy.spatial.distance_matrix並將x作爲數據集的小子集，並作爲整個數據集。
2. 創建一個列表，neighbors = []
3. 循環遍歷距離矩陣的第i行。如果D（i，j）< epsilon，則將j保存在鄰居中。它是i的epsilon鄰域中數據點的索引。
4. 返回鄰居

跑道的距離矩陣的計算應該在開始發生一次（也許在初始化（），如果你包了一切的一類），和函數/方法返回數據點的所有epsilon鄰居應該僅取決於所討論的數據點的索引。

希望這會有所幫助！