Косинусное сходство векторов со сложностью <O (n ^ 2)

Question

Осмотрев этот сайт на предмет похожих проблем, я нашел это: http://math.nist.gov/javanumerics/jama/ и это: http://sujitpal.blogspot.com/2008/09/ir-math-with-java-similarity-measures.html

Однако, похоже, они запускаются в O (n ^ 2). Я занимался кластеризацией документов и заметил, что такой уровень сложности невозможен даже при работе с небольшими наборами документов. Учитывая, что для скалярного произведения нам нужны только векторные члены, содержащиеся в обоих векторах, должна быть возможность поместить векторы в дерево и, таким образом, вычислить скалярное произведение с n log n сложностью, где n - наименьшее количество уникальных членов в 1 из 2 документов.

Я что-то упустил? Есть ли библиотека Java, которая делает это?

спасибо

Answer 1

Hashmap - это хорошо, но это может занять много памяти.

Если ваши векторы хранятся в виде пар ключ-значение, отсортированных по ключу, векторное умножение можно выполнить в O (n): вы простодля параллельной итерации по обоим векторам (такая же итерация используется, например, в алгоритме сортировки слиянием).Псевдокод для умножения:

i = 0
j = 0
result = 0
while i < length(vec1) && j < length(vec2):
  if vec1[i].key == vec2[j].key:
    result = result + vec1[i].value * vec2[j].value
  else if vec1[i].key < vec2[j].key:
    i = i + 1
  else
    j = j + 1

Answer 2

Если вы храните векторные элементы в хеш-таблице, поиск в любом случае только log n, нет?Переберите все ключи в меньшем документе и посмотрите, существуют ли они в большем документе ..?

Answer 3

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

Надеюсь, это поможет!

Answer 4

Если вы хотите рекомендовать ограниченное количество предметов, например, m предметов, каждому предмету в наборе с размером n, сложность должна быть не n ^ 2, а m * n.Поскольку m является константой, сложность является линейной.

Вы можете проверить с помощью simbase проекта https://github.com/guokr/simbase, это база данных векторного сходства nosql.

Использование Simbase по следующим понятиям:

• Векторный набор: набор векторов
• Основа: основа для векторов, векторы в одном наборе векторов имеют одинаковую основу
• Рекомендация: двоичный файл в одном направлениисвязь между двумя наборами векторов, которые имеют одинаковую основу