Блог

Существует множество сайтов, которые используют «теги» для классификации элементов в своей системе. Например, YouTube использует ключевые слова для категоризации видео, Stack Overflow использует теги для категоризации вопросов и т.д.

Какие формулы используют эти сайты (особенно ТАКИЕ) для построения списка элементов, связанных с другим элементом, на основе имеющихся у него тегов? Я создаю систему, очень похожую на ту, что используется в SO, и я хотел бы найти способ сгенерировать список из 20 элементов или около того на основе тегов одного элемента, но также сделать его достаточно распространенным, чтобы каждая фотография генерировала совершенно другой список, и чтобы щелчок по элементу в любом данном связанном списке мог в конечном итоге привести вас почти к каждому элементу в базе данных.

Технический термин для организации, основанной на пользовательских тегах, — это народная экономика. Поиск в Google по этому термину выдает огромное количество материала о том, как эти системы объединены. Хорошее место для начала — это статья в Википедии.

Несколько лет назад мне пришлось решать именно эту проблему по контракту, и компания была достаточно любезна, чтобы позволить мне написать в блоге о том, как я это сделал наhttp://bentilly.blogspot.com/2011/02/finding-related-items.html .

Вы заметите, что если вы получите приличный объем данных, то вам действительно, действительно захочется сделать это из базы данных.

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

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

Также обратите внимание, что большинство систем полагаются не только на теги, но и на «поведение пользователя» (что бы это ни значило). Т.е. для Youtube пользовательским поведением будет «Просмотр видео», «Подписка на канал», «поиск похожих видео как video X» или «пометка видео x тегом y».

В итоге я использовал следующий код (с разными именами), который находит все другие элементы, имеющие хотя бы один общий тег, и упорядочивает результаты по количеству общих тегов по убыванию и сортирует по другим критериям, специфичным для моей проблемы:

 SELECT PT.WidgetID, COUNT(*) AS CommonTags, PS.OtherOrderingCriteria1, PS.OtherOrderingCriteria2, PS.OtherOrderingCriteria3, PS.Date FROM WidgetTags PT INNER JOIN WidgetStatistics PS ON PT.WidgetID = PS.WidgetID
    WHERE PT.TagID IN (SELECT PTInner.TagID FROM WidgetTags PTInner WHERE PTInner.WidgetID = @WidgetID)
    AND PT.WidgetID != @WidgetID
GROUP BY PT.WidgetID, PS.OtherOrderingCriteria1, PS.OtherOrderingCriteria2, PS.OtherOrderingCriteria3, PS.Date
ORDER BY CommonTags DESC, PS.OtherOrderingCriteria1 DESC, PS.OtherOrderingCriteria2 DESC, PS.OtherOrderingCriteria3 DESC, PS.Date DESC, PT.WidgetID DESC