Система персонализации News360: ранжирование кластеров информации

Когда система рекомендаций работает с большим количеством контента, основной задачей становится не фильтрация этого контента, а его ранжирование. Если говорить о новостях — каждый день выходят сотни тысяч статей, тысячи из которых могут затрагивать интересы каждого человека, читающего новости. Но в основном пользователи не читают больше 5-10 статей в день (по данным News360). Какие статьи показать первыми?

Ответ на этот вопрос в News360 ищут уже третий год. Мы нашли уже много разных ответов, но в этом году решили отказаться от концепции, которая была основной на протяжении всех предыдущих лет.

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

Основная задача News360 — это решение проблемы перенасыщения информацией с помощью персонализации. Представим современного пользователя, который использует социальные сети, читает новости, старается следить за несколькими новостными изданиями, чтобы иметь объективную точку зрения, и, конечно же, читает блоги друзей и других интересных людей. Такой пользователь либо проводит часы за тем, чтобы следить за всеми новостями, либо пропускает какую-то информацию. А с каждым новым блогом или другом в социальных сетях все сильнее одолевает чувство, что все больше и больше интересного теряется из виду. News360 для такого пользователя выберет все статьи, которые наиболее популярны в выбранных источниках, все самое обсуждаемое из социальных сетей, добавит нового контента по тематикам, о которых пользователь больше всего читает, и упорядочит все в одну удобную и красивую ленту.

Или представим другого современного пользователя — человека, которому интересно все, кроме политики, и он любит готовить. Тогда News360 может показать пользователю самые интересные неполитические мировые новости и добавить в ленту свежее и популярное из кулинарных блогов и изданий.

Для сравнения персонализированного и неперсонализированного подхода к организации ленты новостей давайте посмотрим на разные ленты:

CNN показывает не персонализированную ленту, а набор самых важных и популярных новостей.

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

Главный экран News360 старается объединить все новости, которые могут меня заинтересовать. Это и самые важные мировые новости, и то, что мне может быть любопытно, и то, что напрямую относится к моим интересам.

Для решения этой задачи, новости, поступающие в систему из Интернета, анализируются на предмет выявления дополнительных сведений:

• Система распознает именованные понятия в тексте, такие, как упоминаемые главные участники события — люди, компании, бренды, места, где происходит событие. Для этого у нас реализован алгоритм, основанный на грамматическом подходе к поиску шаблонов сущностей в тексте, вдохновленный работой «Named Entity Recognition: A LocalGrammar-based Approach».
• News360 классифицирует новости, используя несколько разных подходов. Для классификации статей по популярным рубрикам, таким как Спорт, Бизнес, или Политика, используется метод опорных векторов: машина на основе libsvm обучена на собственном размеченном корпусе, состоящем из 1000 статей СМИ, в котором за вектор взяты ключевые слова статей, взвешенные при помощи TF*IDF.
• Для выделения более мелких и узких тематик текста используется простейшая реализация rule-based classification похожая на то, как это реализовано в Oracle Rule Based Classificaiton и в работе «A Comparison of Classification Techniques for Technical Text Passages»

Для простоты именованные понятия, темы, рубрики и все остальные знания о статье мы называем тэгами статьи. В виде этих же тэгов News360 определяет интересы пользователя путем анализа статей, которые ему нравятся, или когда пользователь явно сообщает о своих интересах:

Для дальнейшей оптимизации ленты новостей, News360 группирует статьи из разных источников об одном и том же, чтобы в основной ленте пользователь не видел повторов, но, погрузившись в чтение истории, мог выбрать, с какой точкой зрения ему интересно ознакомиться. Такая кластеризация контента осуществляется специальным механизмом по алгоритму, близкому к методу Minimum Cut Trees, основанному на графах.

Граф статей News360, кластеры выделены цветом.

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

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

1. CIA faulted for choosing Amazon over IBM on cloud contract
   • Резонансность: 5
   • Тэги: CIA, Amazon, IBM, Cloud Computing
   • Наиболее свежая статья: Physorg.com, 18.06.2013
2. Global IT Spend Projected to Increase
   • Резонансность: 5
   • Тэги: Gartner, Cloud Computing
   • Наиболее свежая статья: The Strategic Sourceror, 19.06.2013
3. What I Use: Office 365 and SkyDrive Pro
   • Резонансность: 1
   • Тэги: Office 365, SkyDrive, Cloud Computing, Gadgets
   • Наиболее свежая статья: WinSuperSite, 20.06.2013

Кластеры используются в News360 как базовые единицы информации, то есть именно их система и рекомендует.

Когда пользователь читает статью, делится ей или лайкает, система старается выяснить, что из того, что известно об этой статье, больше нравится пользователю. Таким образом, система обучается для каждого пользователя, формируя его «портрет» и использует этот портрет для того, чтобы выбирать наиболее, на ее взгляд, интересные пользователю новости. Например, мой портрет выглядит примерно так (длинный хвост из редких тэгов я убрал для удобства чтения):

Вес — это уверенность системы в том, что тематика Cloud Computing будет мне интересна. Этот вес вычисляется на основе того, насколько активно пользователь «взаимодействует» с определенной тематикой. Например, читая статьи о Cloud Computing, я повышаю вес этой тематики у себя в профиле.

Основываясь на портрете, система берет актуальные кластеры информации, и решает, какие из них мне показать.

Все три истории рассказывают об облачных технологиях, а значит, в соответствии с моим портретом, они могут быть мне интересны. Таким образом, процесс персонализации контента можно представить вот так:

То есть система фильтрует контент по интересам пользователей.

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

С введением понятия «важность новости для пользователя» мы вводим сравнительную характеристику (т.е. одни новости могут быть более важными для пользователя, другие — менее), что приводит к необходимости ранжировать новости в соответствии с этой характеристикой индивидуально для каждого пользователя.

Подобная техника называется «рекомендации на основе контента» и широко используется различными продуктами, такими как система рекомендаций imdb.com.

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

1. Свежесть контента.
2. Количество тэгов новости, которые есть в портрете пользователя.
3. Вероятность того, что новости по соответствующим тэгам нравятся пользователю (коэффициент в таблице 1).
4. Резонансность — количество источников, осветивших эту новость, т.е. количество источников, чьи статьи участвуют в текущем кластере.

В момент, когда я обращаюсь к системе за новостями, известная обо мне информация (мой «портрет») используется как параметры запроса к системе, как это описано, например, в статье «Fab: Content-based, collaborative recommendation». Так параметры статей и информация о пользователе используются для ранжирования новостей.

Попробуем сделать это на наших данных (для примера допустим, что мы выполняем ранжирование 20-го июня 2013 года):

1. CIA faulted for choosing Amazon over IBM on cloud contract
   • Свежесть: двое суток (0 баллов)
   • Что нравится пользователю: Cloud Computing (0.95), IBM (0.24) (2 балла)
   • Резонансность: 5 (2 балла)
2. Global IT Spend Projected to Increase
   • Свежесть: сутки (1 балл)
   • Что нравится пользователю: Cloud Computing (0.95) (0 баллов)
   • Резонансность: 5 (2 балла)
3. What I Use: Office 365 and SkyDrive Pro
   • Свежесть: актуально (2 балла)
   • Что нравится пользователю: Cloud Computing (0.95) (0 баллов)
   • Резонансность: 1 (0 баллов)

Для простоты баллы я посчитал, отсортировав новости по каждому из параметров, и назначил 2 за первое место, 0 за третье и 1 за все остальное.

Итого, получаем новости, ранжированные следующим образом:

1. CIA faulted for choosing Amazon over IBM on cloud contract
2. Global IT Spend Projected to Increase
3. What I Use: Office 365 and SkyDrive Pro

Здесь мы ранжировали кластеры (= истории = события). При ранжировании кластеров рождается три неоспоримых преимущества:

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

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

Например, если в кластере пять статей, то резонансность кластера берется за 5, но это не значит, что все пять статей интересны пользователю. То есть, при ранжировании конкретного кластера для конкретного пользователя в каждом параметре надо учитывать все интересы пользователя. В данном случае, вычислять резонансность по количеству статей кластера, интересных пользователю (упоминающих интересы пользователя), а не по общему количеству статей кластера.

То же касается и свежести кластера, и выбора главной статьи кластера (т.е. что из этого кластера показывать пользователю на «обложке» кластера).

В то же время пользователю нужно показывать именно истории (кластеры), а не статьи. Во-первых, потому что пользователь не хочет в своей ленте видеть несколько разных статей об одном и том же, даже если они опубликованы в разных источниках; во-вторых, потому что для ранжирования нам обязательно нужен такой параметр, как резонансность события.

Так мы пришли к системе, в которой ранжируются статьи, но при этом учитывается резонансность событий, а пользователю показываются истории.

Попробуем взять все статьи, указанные на графе выше:

И выбрать из них те, которые подходят пользователю (фильтрация):

Теперь отсортируем статьи по сумме баллов, посчитанных так же, как выше мы рассчитывали веса кластеров (в скобках указаны баллы по каждому параметру, в последнем столбце — сумма баллов). В этом случае в качестве резонансности мы учтем количество интересных пользователю статей в кластере, а не общее количество статей в кластере:

На последнем этапе сгруппируем выдачу по кластерам (в соответствии с графом на рисунке выше), взяв первую статью каждого кластера, и спрятав остальные:

1. What I Use: Office 365 and SkyDrive Pro
2. Report: The CIA Picked Amazon To Build Its Cloud
3. Mobile and cloud top governments' tech shopping lists

Этот результат больше похож на то, что мне интересно.

Кроме использования весов тэгов из портрета пользователя, система также может взвешивать параметры статьи по-разному относительно разных тэгов. Параметры — это дата статьи, количество источников, количество текстовой информации, индекс влиятельности в социальных сетях и другие подобные атрибуты статей. Например, мало текстовой информации в аналитических статьях для тега Politics — это плохо. Однако точно такое же количество информации для фотоблога — это допустимо. Таким образом, одна и та же статья будет обладать разными весами для разных тегов. После нормирования с помощью разработанной в News360 функции ранжирования эти параметры агрегируются в вес статьи относительно тега.

Рассмотрев портрет пользователя как желание видеть тот или иной тег у статьи, мы агрегируем веса статьи в тех тегах, которые есть у пользователя в портрете, таким образом получив окончательный общий вес статьи относительно пользователя.

Итоговый механизм позволяет ранжировать истории используя любой набор следующих признаков:

• Объективные характеристики историй. Например:
  • Дата статьи
  • Количество текстовой информации
  • Рейтинг в соц. сетях.
• Субъективные предпочтения пользователя, для которого производится конкретное ранжирование. Например:
  • Предпочитаемый жанр статьи (аналитические статьи, новости)
  • Взвешенный список предпочитаемых тематик (IBM (0.24), Cloud Computing (0.95))
• Ракурс, под которым пользователь исследует область информации:
  • То есть, статья о бюджете правительства на IT может попасть как в рубрику Politics, так и в рубрику IT, но с разными весами.

А так же, предоставляет широкие возможности выбора варианта представления ленты пользователю:

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

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

Ссылки:

1. Wikipedia: Named-entity recognition
2. Traboulsi, H. N. (2006). Named entity recognition: A localgrammar-based approach. PhD thesis, Department of ComputingSchool of Electronics and Physical Sciences, University of Surrey, Guildford, Surrey, U.K. Retrieved from: scribd.com
3. Boser, Bernhard E.; Guyon, Isabelle M.; and Vapnik, Vladimir N.; A training algorithm for optimal margin classifiers. In Haussler, David (editor); 5th Annual ACM Workshop on COLT, pages 144–152, Pittsburgh, PA, 1992. ACM Press. Retrieved from: citeseer.ist.psu.edu
4. Chang, C., & Lin, C. (n.d.). Libsvm — a library for support vector machines.
5. Classifying documents in oracle text.
6. Kornfein, M. M., & Goldfarb, H. (2007, July). In M.M. Kornfein (Chair). A comparison of classification techniques for technical text passages. WCE 2007, London, U.K. Retrieved from: citeseerx.ist.psu.edu
7. Flake, G. W., Tarjan, R. E. & Tsioutsiouliklis, K. (2004). Graph clustering and minimum cut trees. Internet Mathematics, 1, 385-408. Retrieved from: citeseerx.ist.psu.edu
8. Wikipedia: Recommender system: Content-based filtering
9. Balabanovic, M., & Shoham, Y. (1997). Fab: Content-based, collaborative recommendation. Сommunications of the Association for Computing Machinery, 40(3), 66-72. Retrieved from: citeseerx.ist.psu.edu

Автор: saynurin

Источник