c++ - 在 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()，或者如果我的树的结构有任何固有的错误，请告诉我。它应该打乱 parray 的第一个维度，同时保持每个维度的 11 个维度按顺序保持不变。

现在我开始研究 neighbor() 函数，这就是我感到困惑的地方。

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() 中对 neighbor 的调用，大部分未完成。我不确定 main() 中应该包含什么以及 neighbor() 函数中应该包含什么:

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