Допомога у програмуванні, відповіді на питання / Найближчий сусід / найближчий сусід - k-d tree - wikipedia proof - найближчий сусід, kdtree

Найближчий сусід - дерево k-d - доказ Вікіпедії - найближчий сусід kdtree

На Вікіпедія запис для k-d дерев, представлений алгоритм виконання найближчогопошук сусідів на k-d дереві. Що я не розумію, - це пояснення кроку 3.2. Як ви знаєте, що немає ближчої точки лише тому, що різниця між координатами розщеплення точки пошуку та поточним вузлом більша, ніж різниця між координатою розщеплення координати точка пошуку та найкраща поточна?

EDIT: Додано текст статті у Вікіпедії, про яку йдеться, у разі, якщо вона буде згодом змінена у Вікіпедії.

Найближчий сусід пошук Анімація NN пошук за допомогою дерева KD у 2D

Алгоритм найближчого сусіда (NN) має на меті знайтикрапка на дереві яка найближча до заданого входу бал. Цей пошук можна здійснити ефективно, використовуючи дерево властивості для швидкого усунення великих частини простору пошуку. Пошук найближчого сусіда в а kd-дерево діє таким чином:

Починаючи з кореневого вузла, алгоритм рухаєтьсявниз по дереву рекурсивно, таким же чином, як і він якби точка пошуку вставлений (тобто він іде вправо або вліво залежно від того, є точка більший або менший, ніж поточний вузол у розділеному вимірі).

Як тільки алгоритм досягає вузла аркуша, він зберігає цю точку вузла як "поточний найкращий"

Алгоритм розкручує рекурсію дерева,виконання наступні кроки на кожному вузлі: 1. Якщо поточний вузол ближче до поточного найкращого, то це стає поточним кращим. 2. Алгоритм перевіряє, чи можуть бути якісь точки на інша сторона площини розщеплення які ближче до точки пошуку ніж нинішній найкращий. У концепції, це робиться шляхом перетину розщеплення гіперплана з a гіперсфера навколо точки пошуку який має радіус, рівний струму найближча відстань. Починаючи з Це все врівень з віссю реалізується як просте порівняння щоб побачити, чи є різниця між координата розбиття пошуку точка і поточний вузол менше, ніж відстань (загальні координати) від точки пошуку до течії найкращий. 1. Якщо гіперсфера перетинає площину, це може бути ближчі точки з іншого боку площині, тому алгоритм повинен рухатися вниз інша гілка дерева з поточний вузол шукає ближче балів, дотримуючись тієї ж рекурсивної обробляти як весь пошук. 2. Якщо гіперсфера не перетинає площину розщеплення, тоді алгоритм продовжує ходити вгору по дереву, і по всій гілці далі інша сторона цього вузла - усунено.

Коли алгоритм закінчить цей процес для кореневого вузла, тоді пошук завершений.

Зазвичай алгоритм використовує квадрат відстанідля порівняння уникати обчислення квадратних коренів. Крім того, він може зберегти обчислення, утримуючи Найкраща відстань у квадраті в квадраті змінна для порівняння.

Відповіді:

13 за відповідь № 1

Погляньте уважно на 6-й кадр анімація на цій сторінці.

Оскільки алгоритм відновлює рекурсію,можливо, що на іншому боці гіперплана є ближча точка, на якій він знаходиться. Ми перевірили одну половину, але на іншій половині могла бути ще ближча точка.

Ну, виявляється, ми можемо іноді зробити спрощення. Якщо це "s неможливо щоб там була точка на другій половині ближче, ніж наша поточна найкраща (найближча) точка, тоді ми можемо пропустити цю гіперплан наполовину цілком. Це спрощення показане на 6-му кадрі.

З'ясування, чи є це спрощенняможливо це робиться шляхом порівняння відстані від гіперплану до нашого місця пошуку. Оскільки гіперплощина вирівняна до осей, найкоротша лінія від неї до будь-якої іншої точки буде лінією вздовж одного виміру, тому ми можемо порівняти лише координату виміру, на яку розбивається гіперплан.

Якщо вона знаходиться від точки пошуку до гіперплану, ніж від точки пошуку до поточної найближчої точки, то немає підстав шукати повз цю координатну поділу.

Навіть якщо моє пояснення не допоможе, графіка буде. Удачі у вашому проекті!

0 для відповіді № 2

Так, опис пошуку NN (Найближчого сусіда) у дереві KD у Вікіпедії трохи важко дотримуватися. Це не допоможе цьому багато найкращих результатів пошуку Google у пошуку NN KD Tree - це просто неправильно!

Ось якийсь код C ++, щоб показати вам, як правильно це зробити:

template <class T, std::size_t N>
void KDTree<T,N>::nearest (
const const KDNode<T,N> &node,
const std::array<T, N> &point, // looking for closest node to this point
const KDPoint<T,N> &closest,   // closest node (so far)
double &minDist,
const uint depth) const
{
if (node->isLeaf()) {
const double dist = distance(point, node->leaf->point);
if (dist < minDist) {
minDist = dist;
closest = node->leaf;
}
} else {
const T dim = depth % N;
if (point[dim] < node->splitVal) {
// search left first
nearest(node->left, point, closest, minDist, depth + 1);
if (point[dim] + minDist >= node->splitVal)
nearest(node->right, point, closest, minDist, depth + 1);
} else {
// search right first
nearest(node->right, point, closest, minDist, depth + 1);
if (point[dim] - minDist <= node->splitVal)
nearest(node->left, point, closest, minDist, depth + 1);
}
}
}

API пошуку NN на дереві KD:

// Nearest neighbour
template <class T, std::size_t N>
const KDPoint<T,N> KDTree<T,N>::nearest (const std::array<T, N> &point) const {
const KDPoint<T,N> closest;
double minDist = std::numeric_limits<double>::max();
nearest(root, point, closest, minDist);
return closest;
}

Функція відстані за замовчуванням:

template <class T, std::size_t N>
double distance (const std::array<T, N> &p1, const std::array<T, N> &p2) {
double d = 0.0;
for (uint i = 0; i < N; ++i) {
d += pow(p1[i] - p2[i], 2.0);
}
return sqrt(d);
}

Редагувати: деякі люди також просять про допомогу з структурами даних (не лише з алгоритмом NN), ось ось що я використав. Залежно від вашої мети, ви можете трохи змінити структури даних. (Примітка: але ви майже напевно так робите ні хочу змінити алгоритм NN.)

Клас KDPoint:

template <class T, std::size_t N>
class KDPoint {
public:
KDPoint<T,N> (std::array<T,N> &&t) : point(std::move(t)) { };
virtual ~KDPoint<T,N> () = default;
std::array<T, N> point;
};

Клас KDNode:

template <class T, std::size_t N>
class KDNode
{
public:
KDNode () = delete;
KDNode (const KDNode &) = delete;
KDNode & operator = (const KDNode &) = delete;
~KDNode () = default;

// branch node
KDNode (const T                       split,
std::unique_ptr<const KDNode> &lhs,
std::unique_ptr<const KDNode> &rhs) : splitVal(split), left(std::move(lhs)), right(std::move(rhs)) { };
// leaf node
KDNode (std::shared_ptr<const KDPoint<T,N>> p) : splitVal(0), leaf(p) { };

bool isLeaf (void) const { return static_cast<bool>(leaf); }

// data members
const T                                   splitVal;
const std::unique_ptr<const KDNode<T,N>>  left, right;
const std::shared_ptr<const KDPoint<T,N>> leaf;
};

Клас KDTree: (Примітка. Вам потрібно буде додати функцію члена, щоб створити / заповнити дерево.)

template <class T, std::size_t N>
class KDTree {
public:
KDTree () = delete;
KDTree (const KDTree &) = delete;
KDTree (KDTree &&t) : root(std::move(const_cast<std::unique_ptr<const KDNode<T,N>>&>(t.root))) { };
KDTree & operator = (const KDTree &) = delete;
~KDTree () = default;

const KDPoint<T,N> nearest (const std::array<T, N> &point) const;

// Nearest neighbour search - runs in O(log n)
void nearest (const std::unique_ptr<const KDNode<T,N>> &node,
const std::array<T, N> &point,
std::shared_ptr<const KDPoint<T,N>> &closest,
double &minDist,
const uint depth = 0) const;

// data members
const std::unique_ptr<const KDNode<T,N>> root;
};