Поиск ближайшего соседа (-ов) в дереве KD

Question

Предупреждение: Довольно длинный вопрос, возможно, слишком длинный. Если так, я извиняюсь.

Я работаю над программой, в которой поиск ближайшего соседа (ов) ищет дерево kd (в этом примере это 11-мерное дерево с 3961 индивидуальными точками). Мы только что узнали о них, и хотя я хорошо понимаю, что такое дерево, я очень смущен, когда дело доходит до поиска ближайшего соседа.

Я создал 2D массив точек, каждый из которых содержит качество и местоположение, которое выглядит следующим образом.

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 размеров и не затронутых.

Теперь я нахожусь в функции соседа(), и вот здесь я смутился.

Функция соседа() (последняя половина псевдокод, где я откровенно понятия не имею, где начать):

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 
} 

Вот призыв к соседу в основной(), в основном незавершенным. Я не уверен, что должно быть в основной() и что должно быть в функции соседа():

// 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-дерево не входит перетасовка.

Фактически, вы захотите использовать сортировку (или лучше, quickselect) для построения дерева.

Сначала разрешите его для ближайший сосед (1NN). Должно быть достаточно ясно, как найти kNN, когда у вас есть эта часть, работая, сохраняя кучу лучших кандидатов и используя k-ю точку для обрезки.