Как эффективно вычислить сходство косинусов между миллионами строк

Question

Мне нужно вычислить сходство косинусов между строками в списке. Например, у меня есть список из более чем 10 миллионов строк, каждая строка должна определять сходство между собой и каждой другой строкой в ​​списке. Каков наилучший алгоритм, который я могу использовать для эффективного и быстрого выполнения такой задачи? Используется ли алгоритм разделения и завоевания?

EDIT

Я хочу, чтобы определить, какие строки наиболее близки к заданной строке и быть в состоянии иметь меру/счет, связанный со сходством. Я думаю, что то, что я хочу сделать, совпадает с кластеризацией, где количество кластеров изначально неизвестно.

Answer 1

Работа с транспонированной матрицей. Это то, что Мауд делает на Hadoop, чтобы выполнить эту задачу быстро (или просто использовать Mahout).

По сути, вычислительное сходство с косинусом наивный путь является плохим. Потому что вы в конечном итоге вычислили много чего-то. Вместо этого вам лучше работать в колонках, и убрать все 0s.

Answer 2

Вы можете попробовать SimString.

Это библиотека C++ (с привязками Python или Ruby) для приближенного соответствия строк.

Он утверждает, что ищет строки с высоким коэффициентом косинуса менее 1 миллисекунды для базы данных из 13 миллионов строк.

Описанный алгоритм here основан на обрезке перевернутых списков.