在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个点进行修剪。