Vantage Point Tree — очень старый алгоритм быстрого поиска по дереву. Конечно, сегодня у нас так много инструментов для работы с большими данными, но иногда мы сталкиваемся с проблемой, когда хранилище больших данных не может обеспечить нам хорошую производительность или другое решение дешевле.
Я использовал этот алгоритм для поиска k ближайших вложений, которые представляют само изображение. На практике этот алгоритм показал хорошие результаты и убедил, что с небольшим изменением производительности он может работать в продакшене.
Я хочу рассмотреть разные подходы к выбору точки обзора и показать, что простой подход работает очень хорошо по сравнению с предложенным в бумаге, который требует больше времени.
Кратко опишите этот алгоритм: в статье говорится о дереве, которое мы можем использовать для быстрого поиска. Каждый узел дерева является так называемой точкой обзора, которая разбивает метрическое пространство на два подпространства — левое и правое. Первое подпространство содержит точки, наиболее близкие к точке обзора, а второе — наиболее удаленные. Для каждой точки мы строим поддерево, которое также делит пространство на два подпространства. В конце получаем дерево, в котором можно найти ближайшие точки для заданной.
Они предлагают выбрать точку обзора из случайной выборки, которая лучше распределит пространство. Больший второй момент определяет лучший спред. Что это означает?
- Во-первых, они вычисляют расстояние между точками для понимания их положения в метрическом пространстве.
- Тогда они не работают со средним расстоянием, они находят медиану расстояний. Медиана позволяет построить дерево баланса: если расстояние от точки обзора до другой меньше медианы, то она идет к левому листу, иначе — к правому.
- А главное, второй момент определяет лучший спред. Второй момент — это дисперсия, поэтому нам нужно найти точку с максимальным отклонением от медианы. Теоретически мы получаем точку обзора, которая имеет множество ближайших точек вокруг себя и в то же время имеет точки, находящиеся так далеко от нее. Тогда мы можем легко разделить пространство на левое и правое подпространства.
В статье также предлагается алгоритм эвристического поиска. Но я хочу рассмотреть различные подходы, которые используют людей для выбора точки обзора. Также я протестировал поиск в построенном дереве для поиска ближайших соседей дерева.
Для тестирования я использовал 50 вложений (размерность 128) и евклидово расстояние для расчета расстояния между вложениями.
Я использовал T-SNE для визуализации, поэтому все случаи будут иметь немного другой вид. А вот на что хочу обратить внимание:
1. Время построения дерева.
2. Нахождение времени 3 ближайших соседей и расстояния от заданной точки до соседей.
1. Выберите из случайной выборки точек.
Этот подход имеет математическое обоснование, описанное в статье.
а) В первом случае каждая точка наблюдения итерации выбиралась из всех точек, которые еще не были выбраны в качестве точек обзора.
Разумеется, время на постройку дерева будет самым большим.
Время построения дерева: 0,224 сек.
Поиск 3 ближайших моментов времени: 0,001 сек.
Расстояния от заданной точки до соседей:
0.8029372528422773
0.8701960738954612
0.888163262947272
Как я уже сказал, дерево сбалансировано. Таким образом, левая и правая ветви содержат одинаковое количество узлов.
Как мы видим, выбранная точка обзора действительно имеет самую дальнюю точку и больше самых близких.
б) Выбор из случайной выборки (размер случайной выборки, если 30 баллов или размер оставшихся баллов)
Время построения дерева: 0,150 сек.
Поиск 3 ближайших моментов времени: 0,002 сек.
Расстояния от заданной точки до соседей:
0.8029372528422773
0.8701960738954612
0.888163262947272
в) Выбрать из случайной выборки (5 баллов)
Время построения дерева:0,044 сек.
Поиск 3 ближайших моментов времени:0,001 сек.
Расстояния от заданной точки до соседей:
0.8029372528422773
0.8701960738954612
0.888163262947272
2. Всегда выбирайте первую точку из оставшихся в качестве точки наблюдения.
Время построения дерева:0,010 сек.
Поиск 3 ближайших моментов времени:0,001 сек.
Расстояния от заданной точки до соседей:
0.8029372528422773
0.8701960738954612
0.888163262947272
3. Выберите случайную точку обзора.
Время построения дерева:0,008 сек.
Поиск 3 ближайших моментов времени:0,001 сек.
Расстояния от заданной точки до соседей:
0.8029372528422773
0.8701960738954612
0.888163262947272
Вывод
Целью этого дерева является обеспечение быстрого и точного поиска. Для получения этого результата нам нужно точное дерево, которое будет корректно разбивать метрическое пространство.
Как видим, мы всегда получаем одних и тех же ближайших соседей для данной точки. И время выполнения тоже самое. Для этого игрушечного примера я могу сделать вывод, что мы можем работать со случайным выбором: а) время сборки наименьшее б) давать такой же результат, как и другие.
На практике у меня было около 2,5 миллионов эмбеддингов и время построения дерева очень важно, потому что я не могу тратить время на построение большого дерева слишком много. И поиск в этом дереве занял около 8 секунд для нахождения 4 ближайших соседей. Соседи были действительно самыми близкими. Время поиска также можно сократить за счет распараллеливания или другого подхода.
Иногда такой аккуратный подход не дает нам хорошей производительности и лучшего результата, просто потому, что, возможно, в этом алгоритме выбор точки обзора не был основной идеей — основная идея состоит в том, чтобы разделить пространство на левое и правое подпространства. Поэтому можно пренебречь описанным в статье подходом и работать с самым простым.
