Эффективное сравнение 100 000 векторов

Question

Я сохраняю 100.000 векторов в базе данных. Каждый вектор имеет размер 60. (int vector [60])

Затем я беру один и хочу, чтобы настоящие векторы были для пользователя в порядке убывания сходства с выбранным.

Я использую Tanimoto Classifier сравнить 2 векторов:

Есть ли какие-либо методы, чтобы избежать делать все записи в базе данных?

Еще одна вещь! Мне не нужно сортировать все векторы в базе данных. Я хочу получить 20 лучших похожих векторов. Так что, может быть, мы можем примерно порог 60% записей и использовать остальные для сортировки. Как вы думаете?

Answer 1

Таким образом, следующая информация может быть кэширован:

• Норма выбранного вектора
• скалярное произведение АВ, повторное использование его для обоих числитель и знаменатель в заданном Т (А, В) расчета ,

Если вам нужны только N ближайших векторов или если вы выполняете этот же процесс сортировки несколько раз, могут быть доступны другие трюки. (Наблюдения, такие как T (A, B) = T (B, A), кэширование векторных норм для всех векторов и, возможно, своего рода пороговая/пространственная сортировка).

Answer 2

Короче говоря, нет, вероятно, не любой способ избежать прохождения всех записей в базе данных. Один квалификатор на этом; если у вас есть значительное количество повторяющихся векторов, вы можете избежать повторной обработки точных повторов.

Answer 3

Э-э, нет?

Вам нужно сделать всего 99,999 против того, который вы выбрали (а не всех n(n-1)/2 возможных пар), конечно, но это как можно меньше.

---

Глядя на ваш ответ на nsanders's answer, то ясно, что вы уже на вершине этой части. Но я подумал о специальном случае, когда вычисление полного набора сравнений может быть победой. Если:

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

, тогда вы можете предварительно вычислить данные по мере поступления данных и просто просмотреть результаты на пару во время сортировки. Это также может быть эффективным, если вы в конечном итоге будете делать много видов ...

Answer 4

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

Это то, о чем вы думаете?

======= Переехал комментарий:

Учитывая описание вы не можете не смотреть на все записи для расчета коэффициента подобия. Если вы укажете базе данных, чтобы использовать коэффициент подобия в разделе «порядок», вы можете позволить ему выполнить всю тяжелую работу. Вы знакомы с SQL?

Answer 5

Update:

После того, как вы сделали ясно, что 60 размерность вашего пространства, а не длина векторов, ниже ответ не применим для вас, так что я буду держать это только для истории ,

---

Поскольку ваши векторы нормализуются, вы можете использовать kd-tree найти соседей в пределах MBH пошагового гиперобъема.

Нет базу данных Я в курсе имеет встроенную поддержку kd-tree, так что вы можете попытаться осуществить следующее решение в MySQL, если вы ищете для ограниченного числа ближайших записей:

• магазин Проекция векторы на каждый из 2-мерного пространства возможного (принимает n * (n - 1)/2 столбцов) Index
• каждых из этих столбцов с индексом SPATIAL
• Выберите квадрат MBR из заданной области в пределах любой проекции. Продукт этих MBR даст вам гиперкуб ограниченного гиперволя, который будет содержать все векторы с расстоянием, не превышающим заданное.
• Найти все проекции в пределах всех MBR «с помощью MBRContains

Вы все еще нужно разобраться в этом ограниченном диапазоне значений.

Например, у вас есть набор 4-мерных векторов с величиной 2:

(2, 0, 0, 0) 
(1, 1, 1, 1) 
(0, 2, 0, 0) 
(-2, 0, 0, 0) 

Вы должны хранить их следующим образом:

p12 p13 p14 p23 p24 p34 
--- --- --- --- --- --- 
2,0 2,0 2,0 0,0 0,0 0,0 
1,1 1,1 1,1 1,1 1,1 1,1 
0,2 0,0 0,0 2,0 2,0 0,0 
-2,0 -2,0 -2,0 0,0 0,0 0,0 

Say, вы хотите подобия с первым вектором (2, 0, 0, 0) больше, чем 0.

Это означает наличие векторов внутри гиперкуба: (0, -2, -2, -2):(4, 2, 2, 2).

Вы выдает следующий запрос:

SELECT * 
FROM vectors 
WHERE MBRContains('LineFromText(0 -2, 4 2)', p12) 
     AND MBRContains('LineFromText(0 -2, 4 2)', p13) 
     … 

, и т.д., для всех шести колонн

Answer 6

Следующего ответ

Сколько предварительной обработки вы можете сделать?Можете ли вы заранее построить «окрестности» и указать, в каком окружении каждый вектор находится внутри базы данных? Это может позволить вам устранить многие векторы из соображений.

---

Старый ответ ниже, который предполагается 60 была величина всех векторов, а не измерения.

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

В 3D:

Три размножается. В 2D это всего лишь два умножения.

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

Answer 7

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

Затем триангуляция. если расстояние d между вашим целевым вектором v и некоторым вектором v 'велико, то расстояние между v и всеми другими v' ', которые близки к v', будет большим (-ish) тоже, поэтому нет необходимости сравнивать (вам придется найти приемлемые определения «большого»), хотя). Вы можете поэкспериментировать с повторением процесса для отброшенных векторов v '' и проверить, сколько выдержек времени выполнения вы можете избежать, прежде чем точность начнет уменьшаться. (сделать тестовый набор «правильных» результатов для сравнений)

удачи.

sds

Answer 8

Не пропуская ни одной записи? Это кажется невозможным. Единственное, что вы можете сделать, это сделать математику во время вставки (вспомните, что equivalence http://tex.nigma.be/T%2528A%252CB%2529%253DT%2528B%252CA%2529.png: P).

Это позволяет избежать ваш запрос, чтобы проверить список против всех остальных списков во время выполнения (но это может сильно увеличить пространство, необходимое для БД)

Answer 9

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

Теперь подумайте о новой функции D = расстояние между двумя точками в пространстве 60D. Это классический L2 distance, возьмите разницу между каждым компонентом, соберите квадрат, добавьте все квадраты и возьмите квадратный корень из суммы. D (A, B) = sqrt ((A-B)^2), где A и B представляют собой 60-мерные векторы.

Это может быть расширено, однако, до D (A, B) = sqrt (A * A -2 * dot (A, B) + B * B). A и B - это единица измерения. И функция D монотонна, поэтому она не изменит порядок сортировки, если мы удалим sqrt() и посмотрим на квадратные расстояния. Это оставляет нам только -2 * точку (A, B). Таким образом, минимализующее расстояние точно эквивалентно максимизации точечного произведения.

Таким образом, первоначальная метрика классификации T() может быть упрощена в поиске наивысшего точечного произведения между ноннализованными векторами. И это сравнение эквивалентно обнаружению ближайшего точек точки отсчета в 60-D пространстве.

Итак, теперь все, что вам нужно сделать, это решить эквивалентную проблему «заданной нормированной точкой в ​​пространстве 60D», перечислите 20 пунктов в базе данных нормализованных векторов образца, которые ближе всего к ней ».

Эта проблема хорошо понятна. Это K Nearest Neighbors. Существует множество алгоритмов для решения этой проблемы. Наиболее распространенным является классический KD trees .

Но есть проблема. Деревья KD имеют поведение O (e^D). Высокая размерность быстро становится болезненной. И 60 измерений, безусловно, в этой чрезвычайно болезненной категории. Даже не пытайтесь.

Однако существует несколько альтернативных общих методов для ближайшего соседа высокого D. This paper дает четкий метод.

Но на практике существует отличное решение, включающее еще одно преобразование. Если у вас есть метрическое пространство (которое вы делаете, или вы не будете использовать сравнение Tanimoto), вы можете уменьшить размерность проблемы с помощью 60-мерного вращения. Это звучит сложно и страшно, но это очень распространено. Это форма разложения по сингулярным значениям или разложение по собственным значениям. В статистике он известен как Principal Components Analysis.

В основном это использует простой линейный расчет, чтобы найти, какие направления ваша база данных действительно охватывает. Вы можете свернуть 60 измерений до меньшего числа, возможно, как 3 или 4, и по-прежнему сможете точно определять ближайших соседей. Существует множество программных библиотек для этого на любом языке, например, here.

Наконец, вы сделаете классических ближайших соседей K, возможно, только в 3-10 измерениях. Вы можете поэкспериментировать для лучшего поведения. Для этого есть потрясающая библиотека, которая называется Ranger, но вы можете использовать и другие библиотеки. Отличное преимущество - вам даже не нужно хранить все 60 компонентов ваших данных образца!

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

Так резюме вышеизложенное:

1. Нормализация векторов, превращая вашу проблему в K-ближайшие соседи задачу в 60 размерах
2. Использование Основных компоненты анализа для уменьшения размерности к управляемому пределу скажем, 5 измерений
3. Используйте алгоритм K Nearest Neighbor, такой как библиотека дерева KD Ranger, чтобы найти близлежащие образцы.

Answer 10

Другое дело, это проблема всех пар с заданным порогом для некоторой функции подобия. Взгляните на бумагу и код Байардо здесь http://code.google.com/p/google-all-pairs-similarity-search/

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