Как эффективно внедрить систему поиска по сходству документов?

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

В моей базе данных есть три таблицы: Article, ArticleTag и Tag. Каждая статья связана с рядом тегов отношением «многие ко многим». Для каждой статьи я хочу найти пять наиболее похожих статей, чтобы внедрить систему «если вам понравилась эта статья, вам понравятся и эти».

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

С 200 тысячами статей и 30 тысячами тегов мне требуется полминуты, чтобы подсчитать количество похожих статей для одной статьи. Поэтому мне нужен другой алгоритм, который дает примерно такие же хорошие результаты, как косинусное сходство, но который можно запускать в реальном времени и который не требует от меня каждый раз перебирать весь корпус документа.

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


search trigonometry similarity recommendation-engine
person Björn Lindqvist    schedule 03.02.2010    source источник
comment
Бьорн, пожалуйста, взгляните на simbase, он все еще находится в разработке, но цель как раз ваш вопрос. Это почти сделано, последняя работа — постоянный слой и настройка производительности. Вы можете попробовать, если у вас есть время. Спасибо.   -  person Mountain    schedule 30.12.2013

Ответы (2)


arrow_upward
1
arrow_downward

Некоторые вопросы,

  • Чем ArticleTag отличается от Tag? Или это таблица сопоставления M2M?
  • Можете ли вы набросать, как вы реализовали алгоритм сопоставления косинусов?
  • Почему бы вам не хранить теги ваших документов в какой-либо структуре данных в памяти, используя ее только для извлечения идентификаторов документов? Таким образом, вы попадаете в базу данных только во время поиска.
  • В зависимости от частоты добавления документов эта структура может быть рассчитана на быстрое/медленное обновление.

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

Ваше здоровье.

person viksit    schedule 04.02.2010
comment
1. Да ArticleTag — это таблица M2M. 2. Реализовано так, как предписывает статья в Википедии. Теги для статьи рассматриваются как векторы, в которых появление тега имеет значение 1, а 0 опущено. 3. Я сохраняю идентификаторы документов и идентификаторы их тегов в памяти, что, конечно, значительно ускоряет процесс, но все же замедляет его. Я думаю, что кластеризация k-средних может быть тем, что мне нужно, но я не совсем понимаю, как ее использовать для этого сценария. - person Björn Lindqvist; 08.04.2010

arrow_upward
0
arrow_downward

Вы можете сделать это с помощью набора инструментов Lemur. С его KeyfileIncIndex вам нужно повторно получить документ из его источника; IndriIndex поддерживает извлечение документа из индекса.

Но в любом случае вы индексируете свои документы, а затем строите запрос из документа, которому хотите найти похожие документы. Затем вы можете выполнить поиск по этому запросу, и он оценит другие документы на предмет сходства. По моему опыту это довольно быстро. Он обрабатывает как исходные документы, так и базовые запросы как документы, поэтому поиск сходства - это то, что он делает (если вы не используете парсер Indri - это немного отличается, и я не уверен, как это работает).

person Michael Ekstrand    schedule 19.03.2010
comment
Это ничем не отличается от того, как работают обычные текстовые поисковые системы. Суть проблемы в том, что для того, чтобы найти, скажем, десять лучших совпадений, нужно найти показатель сходства между поисковым запросом и каждым документом в базе данных. Затем вы должны упорядочить их по показателю сходства и выбрать десять лучших. Поскольку вам нужно просмотреть всю базу данных для каждой статьи, которую вы хотите найти, это становится очень медленным. - person Björn Lindqvist; 08.04.2010