KD-деревья и пропущенные значения (векторное сравнение)

Question

У меня есть система, которая хранит векторы и позволяет пользователю найти n наиболее похожих векторов с вектором запроса пользователя. То есть пользователь отправляет вектор (я называю это вектором запроса), и моя система выплевывает «вот n самых похожих векторов». Я генерирую похожие векторы, используя KD-Tree, и все работает хорошо, но я хочу сделать больше. Я хочу представить список из n наиболее похожих векторов, даже если пользователь не отправляет полный вектор (вектор с пропущенными значениями). То есть, если пользователь отправляет вектор с тремя измерениями, я все равно хочу найти n ближайших векторов (сохраненные векторы имеют 11 измерений), которые я сохранил.

У меня есть несколько очевидных решений, но я не уверен, что одно из них кажется очень хорошим:

1. Создайте несколько деревьев KD, каждое из которых построено с использованием самого популярного подмножества измерений, которое будет искать пользователь. То есть, если пользователь отправляет вектор запроса из этих измерений, x, y, z, я сопоставляю этот запрос с моим уже построенным KD-деревом, которое содержит только векторы трех измерений, x, y, z.

2. Игнорировать KD-деревья, когда пользователь отправляет вектор запроса с пропущенными значениями, и сравнивать вектор запроса с векторами (хранящимися в таблице в БД) по одному, используя что-то вроде точечного произведения.

Это должно быть распространенной проблемой, есть предложения? Спасибо за помощь.

Answer 1

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

Второй вариант выглядит очень медленно, если у вас есть только несколько очков. И если это так, то вам, вероятно, не понадобилось kd-дерево. :)

Я думаю, что лучшее решение - это испачкать руки в коде, с которым вы работаете. Предположительно, поиск ближайшего соседа вычисляет расстояние между точкой в ​​листе дерева и вектором запроса; Вы должны иметь возможность изменить это для обработки случая, когда точка и вектор запроса имеют разные размеры. Например. если точки в дереве заданы в 3D, но вектор вашего запроса имеет длину только 2, то «расстояние» между точкой (p0, p1, p2) и вектором запроса (x0, x1) будет равно

sqrt( (p0-x0)^2 + (p1-x1)^2 )

Я не копался в java-коде, на который вы ссылались, но я могу попытаться найти, куда именно нужно внести изменения, если вам понадобится помощь.

-Крис

PS - вам может не понадобиться sqrt в приведенном выше уравнении, поскольку квадрат расстояния обычно эквивалентен.

EDIT Извините, не понимал, что это будет так очевидно в исходном коде. Вы должны использовать эту версию функции соседей:

nearest(double [] key, int n, Checker<T> checker)

И реализовать свой собственный класс Checker; см. их EuclideanDistance.java, чтобы увидеть евклидову версию. Вам также может понадобиться закомментировать любое KeySizeException, которое выдает код запроса, поскольку вы знаете, что можете обрабатывать ключи разного размера.

Answer 2

Вот что я в итоге сделал: когда пользователь не указал значение (когда в векторе его запроса отсутствовало измерение), я просто настроил диапазон сопоставления (в API) на что-то огромное, чтобы я сопоставил любое значение.

Answer 3

Вы можете попробовать использовать существующее дерево KD - взяв обе ветви, когда расщепление относится к измерению, которое не предоставляется исходным вектором. Это должно занять меньше времени, чем поиск методом грубой силы, и может оказаться менее трудным, чем попытка сохранить набор специализированных деревьев для подмножеств измерений.

Вам нужно будет адаптировать свой N-ближайший алгоритм (без дополнительной информации, я не могу вас проконсультировать по этому вопросу ...), а для расстояния вы будете использовать сумму квадратов только тех элементов, которые поставляются вектором источника .

Answer 4

Ваш второй вариант выглядит как разумное решение для того, что вы хотите.

Вы также можете заполнить отсутствующие измерения самыми важными (или усредненными, или какими-либо другими значениями), если они есть.