在KD樹中尋找最近的鄰居

Question

警告：相當長的問題，也許太長。如果是這樣，我表示歉意。

我正在研究一個涉及kd樹的最近鄰居搜索的程序（在這個例子中，它是一個具有3961個獨立點的11維樹）。我們只是剛剛瞭解了它們，而且我很好地掌握了樹的功能，但在涉及到最近的鄰居搜索時，我感到非常困惑。

我已經設置了一個點陣的二維數組，每個點都包含一個質量和位置，看起來像這樣。

struct point{ 
    double quality; 
    double location; 
} 

// in main 
point **parray; 
// later points to an array of [3961][11] points 

然後我翻譯了數據，使其具有零均值，並將其重新調整爲單位差異。我不會發布代碼，因爲這對我的問題並不重要。之後，我按如下隨機順序將點建成樹：

struct Node { 
    point *key; 
    Node *left; 
    Node *right; 
    Node (point *k) { key = k; left = right = NULL; } 
}; 

Node *kd = NULL; 
// Build the data into a kd-tree 
random_shuffle(parray, &parray[n]); 
for(int val=0; val<n; val++) { 
    for(int dim=1; dim<D+1; dim++) { 
    kd = insert(kd, &parray[val][dim], dim); 
    } 
} 

很漂亮的東西。如果我錯誤地使用了random_shuffle（），或者如果我的樹的結構有任何內在錯誤，請告訴我。它應該洗牌的第一個維度，同時保持每一個的11個維度沒有變化。

現在我開始使用neighbor（）函數，這裏是我感到困惑的地方。

鄰居（）函數（最後半是僞代碼，在那裏我坦率地不知道從哪裏開始）：

Node *neighbor (Node *root, point *pn, int d, 
       Node *best, double bestdist) { 
    double dist = 0; 
    // Recursively move down tree, ignore the node we are comparing to 
    if(!root || root->key == pn) return NULL; 

    // Dist = SQRT of the SUMS of SQUARED DIFFERENCES of qualities 
    for(int dim=1; dim<D+1; dim++) 
    dist += pow(pn[d].quality - root->key->quality, 2); 
    dist = sqrt(dist); 

    // If T is better than current best, current best = T 
    if(!best || dist<bestdist) { 
    bestdist = dist; 
    best = root; 
    } 

    // If the dist doesn't reach a plane, prune search, walk back up tree 
    // Else traverse down that tree 

    // Process root node, return 
} 

下面是主要的呼叫鄰居（），主要是未完成。我不知道應該在main（）什麼，應該是在鄰居（）函數是什麼：

// Nearest neighbor(s) search 
double avgdist = 0.0; 
// For each neighbor 
for(int i=0; i<n; i++) { 
    // Should this be an array/tree of x best neighbors to keep track of them? 
    Node *best; 
    double bestdist = 1000000000; 
    // Find nearest neighbor(s)? 
    for(int i=0; i<nbrs; i++) { 
    neighbor(kd, parray[n], 1, best, &bestdist); 
    } 
    // Determine "distance" between the two? 
    // Add to total dist? 
    avgdist += bestdist; 
} 
// Average the total dist 
// avgdist /= n; 

正如你所看到的，我卡上的代碼的最後兩個部分。過去幾天我一直在對這個問題大發雷霆，而我仍然陷入困境。這很快就會到期，所以當然，任何和所有的幫助是值得讚賞的。提前致謝。

Answer 1

kd-tree不涉及洗牌。

實際上，您會希望使用排序（或更好的快速選擇）來構建樹。

首先解決它的最近的鄰居（1NN）。一旦你有這個部分的工作，如何找到kNN應該是相當清楚的，保留一大堆候選人，並使用第k個點進行修剪。