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

Просмотрев этот сайт в поисках похожих проблем, я нашел это: 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, которая делает это?

Благодарность


java algorithm information-retrieval
person Ash    schedule 27.07.2010    source источник
comment
Вам не повезет, ожидая, что люди прочитают обе эти страницы. Возможно, вы могли бы объяснить свою проблему более четко - почему вы умножаете векторы (и что вы имеете в виду, O (n ^ 2)? Вычисление скалярного произведения двух n-мерных векторов тривиально O (n), я очень сомневаюсь в любом векторный пакет может так сильно облажаться)   -  person BlueRaja - Danny Pflughoeft    schedule 27.07.2010
comment
Он вычисляет скалярное произведение для каждой пары документов. Это делает его квадратично сложным.   -  person Rekin    schedule 27.07.2010
comment
BlueRaja - Дэнни Пфлугхофт, эта задача связана с умножением очень многомерных, но очень разреженных векторов; и n - это не размерность, а количество ненулевых элементов.   -  person dmitry_vk    schedule 27.07.2010

Ответы (4)


arrow_upward
2
arrow_downward

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

person Nicolas78    schedule 27.07.2010
comment
Какой класс вы бы порекомендовали? Я считаю, что это довольно хорошо, если проблема с памятью: java2s.com/Code/Java/Collections-Data-Structure/ - person Ash; 27.07.2010
comment
Ничего себе, не могу судить об этом так быстро, но вы всегда можете начать с обычного java.util.HashMap. Кстати, поскольку вы говорите, что это влияние размера коллекции документов: если вы сравниваете каждый документ с каждым документом, у вас есть еще один квадратичный термин (теперь в числе документов), обернутый вокруг термина (n * log n). Для меня эта часть часто была гораздо более проблематичной, чем фактическое вычисление косинуса. Может ли это иметь место и для вас? - person Nicolas78; 27.07.2010
comment
Я выполняю обрезку набора кластеров, чтобы свести сравнение к константе, но для чего-то вроде GAHC вы совершенно правы, у вас есть проблема n ^ 2, где n — количество сравниваемых кластеров. - person Ash; 28.07.2010

arrow_upward
2
arrow_downward

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
person dmitry_vk    schedule 27.07.2010
comment
Мне нравится эта идея, спасибо. Есть ли библиотека java, которая использует этот принцип? - person Ash; 28.07.2010
comment
Я не знаю; но lucene (lucene.apache.org/java/docs/index.html ) может содержать такой алгоритм. - person dmitry_vk; 28.07.2010
comment
Спасибо, dmitry-vk, похоже, лучше всего использовать отсортированную карту: java.sun.com/j2se/1.4.2/docs/api/java/util/SortedMap.html - person Ash; 29.07.2010

arrow_upward
1
arrow_downward

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

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

person templatetypedef    schedule 12.06.2014

arrow_upward
0
arrow_downward

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

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

Simbase использует следующие концепции:

  • Векторный набор: набор векторов
  • Основа: основа для векторов, векторы в одном наборе векторов имеют одинаковую основу
  • Рекомендация: однонаправленная бинарная связь между двумя наборами векторов, имеющими одинаковую основу.
person Mountain    schedule 12.06.2014