K-среднее дерево VS рандомизированное KD-дерево?

Question

K-среднее дерево VS рандомизированное KD-дерево?

Я читал эти слайды. В частности, на слайде 52 указано:

В наших экспериментах мы обнаружили, что любой из двух алгоритмов может иметь наилучшую производительность в зависимости от набора данных и желаемой точности

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

Это правильно, или я читаю что-то здесь не так? Если так, почему они говорят, что лучший алгоритм зависит от набора данных?

1

tree k-means kdtree

Источник

user4480180 03 окт '16 в 10:54

1 ответ

Решение

Другие вопросы по тегам tree k-means kdtree

user7473335 02 фев '17 в 12:01 2017-02-02 12:01 · Accepted Answer · 2017-02-02 12:01

После анализа графиков на слайде, который вы указали, вы можете заметить, что:

В (a) для совпадений SIFT 100k K-означает немного лучше при балансировке скорость / точность;
В (b) при масштабировании от 100K SIFT до 31M RKD-деревья могут работать быстрее, однако скорость немного снижается, если вы хотите добиться максимальной точности при поиске этих совпадений;
И в (c) поиск с помощью RKD-Tree лучше работает с наборами данных, которые не имеют истинных совпадений по запросу.

Таким образом, они действительно зависят от набора данных. Например, вы можете сделать вывод, что RKD-дерево работает быстрее для больших наборов данных, однако, если точность является важным показателем для любой задачи, которую вы пытаетесь достичь, производительность RKD-Trees будет аналогична поиску по K-среднему значению.