Подробно о BrowseRank, алгоритме учета поведенческих факторов. Программа о накрутке поведенческого фактора

Михаил Сливинский

Независимый эксперт аналитик, руководитель отдела поисковой аналитики «Викимарт»

Несколько дней назад я вел программу на Мегаиндекс.ТВ, в которой мы со Станиславом Ставским обсуждали возможности учета поведения пользователей для ранжирования документов. Главный фокус программы: попытки накруток поведенческих факторов, реакция поиска на эти действия, перспективы. Наша точка зрения состоит в том, что у поиска много возможностей эффективно обнаруживать накрутки, что мы проиллюстрировали на примерах. Поэтому целесообразнее тратить время и ресурсы на улучшение сайта, что обеспечит естественное улучшение ранжирования.

При этом, конечно, хорошо бы понимать, что именно учитывают поисковые системы при анализе поведения пользователей в выдаче и на сайтах. Как ни странно, весьма немногие оптимизаторы и вебмастера знают о BrowseRank, технологии учета поведения пользователей от Microsoft (pdf, англ.). Хотя этой разработке уже 3 года, полагаю, она вполне актуальна.

Граф кликов вместо ссылочного графа

Основное отличие BrowseRank от PageRank — структура графа. В технологии PageRank узлами графа являются документы, а ребрами — ссылки. В технологии BrowseRank ребра образуют не ссылки, но клики (переходы). Помимо этого, сохраняется мета-информация о продолжительности сессии в рамках документа.

Очевидны два существенных преимущества BrowseRank:

• существенно лучшая устойчивость к ссылочному спаму,
• учет продолжительности сессии позволяет оценить полезность документа для посетителя.

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

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

Для обработки данных о поведении пользователей предложено использовать цепи Маркова с непрерывным временем. Экспериментальные данные демонстрируют преимущество алгоритма BrowseRank по сравнению с алгоритмами PageRank и TrustRank в определении важности документов, борьбе со спамом и ранжировании.

По сути, собираемые данные можно представить записью вида URL; TIME; TYPE [input | click]. Предполагается два пути перехода на документ: по ссылке с другого документа (click), либо набором url в адресной строке браузера (input). Механизм извлечения данных о переходах:

1. Сегментация сессии.
   Новая сессия инициируется в случае 30-минутной и более паузы с момента предыдущей активности, либо в случае ввода названия сайта в адресную строку.
2. Формирование пар url.
   В рамках каждой сессии создаются пары url из соседних записей. Пара url означает, что переход был осуществлен при помощи ссылки.
3. Формирование начального распределения.
   В каждой сессии, сегментированной по типу перехода, первый url введен непосредственно пользователем. Такие url мы считаем «доверительными» и называем этот трафик «зеленым». Обрабатывая данные о поведении пользователей, мы считаем переходы на эти url следствием случайного распределения. Нормализация на частоту посещения этих документов дает начальные вероятности посещения соответствующих страниц.
4. Извлечение продолжительности сессии.
   Для каждой пары url продолжительность сессии первого url вычисляется простой разностью дат. Если url был последним в сессии, возможны два варианта. Для сессий, сегментированных по времени, продолжительность просмотра последнего url рассчитывается на основании данных о просмотрах других страниц. Для сессий, сегментированных по типу, время просмотра последнего url рассчитывается исходя из времени начала следующей сессии.

Результаты применения BrowseRank

Microsoft провела два исследования. Первый был проведен на уровне сайта для выявления важных сайтов и подавления спама. Второй эксперимент был проведен на уровне документа для тестирования BrowseRank с целью улучшения ранжирования.

Для первого эксперимента использовался набор данных из примерно 3 миллиардов записей, содержащий примерно 950 миллионов уникальных url. Любопытно, что распределение количества просмотров по времени просмотра отлично описывается классической экспонентой. В рамках этого эксперимента постраничные не использовались, они были агрегированы на уровне сайтов. Полученный поведенческий граф состоял из 5.6 миллионов узлов и 53 миллионов ребер.

Любопытна выборка ТОП20 сайтов, полученных ранжированием по трем разным алгоритмам. Видно, что BrowseRank отлично отранжировал MySpace, Youtube, Facebook и прочие сайты, для которых характерно большое время сессии. Обратите внимание, это данные 2008 года. Очевидно, в нашу эпоху социальных сетей и коммуникационных сервисов различие между PageRank и BrowseRank было бы еще более значительным.

На случайной выборке в 10 тысяч сайтов, вручную размеченной асессорами, показано, что BrowserRank эффективнее, чем TrustRank и PageRank решает задачу фильтрации спам-сайтов.

Второй эксперимент не менее интересен.

Факторы ранжирования документов можно грубо разделить на две группы: факторы релевантности и факторы важности. Предполагаем итоговую функцию релевантности линейной комбинацией этих двух групп факторов:

Θ * rank_relevance + (1-Θ) * rank_importance,

где Θ лежит в интервале [0;1].

Данные получены на выборке из сайтов, полученных для 8000 запросов. Каждая пара запрос-документ оценивалась тремя асессорами по бинарной шкале [релевантно; не релевантно]. Релевантными сочтены документы, получившие по запросу не менее 2 оценок «релевантно».

Результат: алгоритм BrowseRank обеспечивает существенно лучшее качество вплоть до полного подавления факторов важности факторами релевантности (Θ ~ 0.9).

Несколько слов о попытках накруток и манипуляциях

Может ли поиск эффективно отфильтровать накрутки? Безусловно. Чтобы понять это, достаточно трех фактов:

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

Ну и, наконец, простые логические доводы для тех, кто не верит в технологии.

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

Резюме: существенно продуктивнее потратить время на легальные способы удлинения сессии и повышения «пользовательского счастья». Благо, таких способов предостаточно.