移動查詢點的K最近鄰居

我給出了n個固定點和m個查詢點的座標。我必須從n個固定點中找出每個m個查詢點的k個最近鄰居。爲每個查詢點分別查找距離非常昂貴。有沒有這樣做的有效方式？移動查詢點的K最近鄰居

2013-10-30 pikachu

數據的維度是重要的。 –

有這樣的問題，快速索引結構，像KD Tree或Ball Tree。特別是 - scikit-learn（sklearn）在他們的knn例程中實現它們（http://scikit-learn.org/stable/modules/neighbors.html）

2013-10-30 19:51:47 lejlot

如果您正在計算平方和的平方根以獲得距離，請嘗試刪除計算密集型的平方根。只需找到距離最近的平方距離 - 它們是相同的點。

2013-10-30 20:21:15

這是爲什麼這個標記好嗎？這是一個完全合法的答案。 –

我同意 - 請問下降者請詳細說明他對此答案的異議 –

您的問題的真實答案取決於許多因素。例如，如果您不使用歐幾里德距離 - 那麼您不能使用KDTrees。還有縮放問題（註冊點數有多少？維度大小？「聚集」）您可以等待多長時間的訓練，是否需要將值添加到該集合中，等等。

許多不常用的胸圍仍然有用，算法可在JSAT中找到。這包括VP Trees,RBC和LSH。（偏差警告，我是JSAT的作者）

2013-10-31 05:16:17

回答