Как задать очерёдность посещения новых страниц поисковым роботом на основе предсказания популярности веб-страницы (Часть I)

17:01 13.10.2014 anastasiapmp 1,815 0
Данный доклад был опубликован в хабе Яндекс Технологии в марте этого года. Исследование, проведённое группой компании Яндекс, ставит перед собой цель: определить порядок индексации новых страниц. В первой части работы рассматриваются предыдущие исследования на данную тему. Предложенный исследовательской группой метод предлагает принять во внимание прогнозирование поведения пользователей для данной страницы, что вновь возвращает нас к теме связи поведенческих факторов с ранжированием и скоростью индексации. Перевод публикуется при поддержке рабочей группы проекта SERPClick, нацеленного на повышение ранжирования вашего сайта за счет непосредственного влияния на параметры поведенческих факторов для вашего сайта.

image
Ползущий (crawling) по вашей странице в сети (web) поисковый робот

Резюме статьи


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

Ключевые слова: очередность индексации, новые веб-страницы, предсказание популярности.

1. Введение

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

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

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

Цель любого подхода [к вычислению важности страницы] состоит определении общей полезности проиндексированных страниц для поисковой системы. С этой точки зрения, оправданно использовать в качестве мерила популярности страницы — число пользовательских переходов (или посещений) той или иной страницы, или её популярности. Это так называемый подход, основанный на данных о поведении пользователей в поиске, предложенный в [14]. Уже доказано, что популярность почти любой страницы недолговечна: они популярны некоторое время после своего создания и затем интерес пользователей спадает со временем. В этом документе мы фокусируемся только на таких страницах с кратковременным интересом пользователей к ним, и предсказываем максимум для этого показателя после того, как страница проиндексируется.

Популярность новой страницы не может быть известна заранее, а следовательно её нужно предсказать, основываясь на параметрах страницы, которые известны к моменту её обнаружения в сети. Мы проанализировали проблему предсказания популярности для новых страниц, в частности мы учли динамику популярности, прогнозируя как саму популярность страницы, так и её спад для новых URL. Предложенная ранее в [14] заданная очерёдность индексации страниц основывается на предсказании популярности страницы в целом, а следовательно не принимает во внимание динамику этого показателя во времени. На самом деле при таком подходе, если мы возьмём две новых страницы, одна из которых популярна сегодня, а другая будет ещё более популярна, но спустя несколько дней, поисковый робот проиндексирует первой последнюю страницу и таким образом упустит текущий трафик для поисковой системы.
Мы считаем, что данные о динамике популярности могут эффективно использоваться для оптимизации поведения поискового робота, но вместе с тем предсказать эту динамику сложно.

Мы предсказываем общее число посещений, которое будет зафиксировано на новой странице со временем. В отличие от [14], наше предсказание основывается на модели, которая учитывает показатели из разных источников, включая сам адрес страницы и домен. Мы предсказываем динамику развития популярности страницы во времени при помощи соответствующей экспоненты, как это было предложено в [12].

Мы даём проводим оценку функциональности различных способов того, как можно задать очередность индексации страниц, основанных на предсказании популярности страниц. Алгоритм, который мы предлагаем в этой работе принимает во внимание прогнозируемый уровень спада популярности веб страниц и динамически перетасовывает очередь на индексацию в соответствии с динамикой популярности. Стоит упомянуть, что способ задачи очерёдности индексации, основанный на данных о поведении пользователей требует от нас того, чтобы мы экспериментально оценили его в реальных условиях, где необходимо учитывать изменяющуюся природу самой задачи: задержка индексации, появление новых страниц и ранее популярные страницы, которые больше не получают посещений. Насколько мы знаем, подобных экспериментов ещё не проводилось. Мы сравниваем различные стратегии задания очередности для поискового робота, тестируя их в реальных условиях и сравниваем полученные результаты с динамическими показателями успешности индексации, предложенными в [12].

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

Резюмируя всё выше сказанное, данное исследование является полезным благодаря двум следующим моментам:

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

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

Дальнейшее изложение построено в следующем порядке:
В следующем разделе мы рассматриваем предыдущее исследование методов индексирования новых страниц и прогнозирование популярности страниц. В разделе 3 мы описываем принципы и метод алгоритма индексации, который предлагаем в данной работе. В разделе 4 мы приводим результаты тестирования нового алгоритма и сравниваем его с используемой на данный момент стратегией. Раздел 5 резюмирует итоги работы.

2. Предыдущие исследования

Уже существует ряд работ, посвященных прогнозированию популярности для различных элементов Интернета: это тексты, новости, пользователи социальных сетей, твиты, хэш-теги Твиттера, видео и т. д. Однако, лишь несколько работ посвящены популярности страниц, которая подсчитывается на основе посещений пользователей. Одна из них предлагает модель, которая прогнозирует соответствующую популярность для определённого запроса, количество кликов из поиска на данную страницу, а также рассматривает пару запрос-страница. Эта модель основывается на данных (из логов) о ранее известной динамике данного запроса и кликов по соответствующему документу. Поэтому этот подход невозможно применить к решению задачи предсказания популярности для новых страниц, для которых у поисковой системы пока нет достаточного количества данных из логов, т. к. они ещё не подвергались индексации.

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

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

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

Новаторская работа [16] предлагает оценивать эффективность индексации на базе полезности проиндексированных страниц для пользователей поиска, который опирается на определённый метод ранжирования и логи поисковых запросов. Авторы определяют качество страницы выдачи как показатель среднего количества всех пользовательских запросов и сравнивают изменения этого показателя для различных методов построения стратегии индексации для поискового робота. Они предлагают алгоритм, который позволяет эффективно индексировать страницы повторно для того, чтобы своевременно обновлять их локальные копии. Польза от повторного индексирования конкретной страницы оценивается на основе логов, где отражена польза [для поисковой системы] от её предыдущих индексаций. В связи с этим ограничением работы, в ней не рассматривается порядок индексации новых страниц.
Наша работа, напротив, фокусируется на прогнозировании полезности новой страницы, которое должно строится на параметрах её URL, которые мы можем определить, не загружая страницу. Вопрос того, в каком порядке отправлять на индексацию новые URL был рассмотрен в [17]. В нашей работе, как и в работе [16], измерение эффективности всего алгоритма основывается на следующем факторе: полезность проиндексированных страниц в рамках существующего метода ранжирования и с учетом логов поисковых запросов. В приложении этого к новым страницам, ожидаемая их полезность должна быть вычислена на основе только адреса страницы, входящих ссылок, показателей доменов и соответствующих анкоров.

Способ оценки стратегии индексации, предложенный в [16] и [17] можно интерпретировать как ожидаемое число кликов, которые придутся на проиндескированную страницу при существующем методе ранжирования и на основе логов поисковых запросов, которые мы фиксируем в течение определённого временного отрезка. Действительно, если определённый объём данных о запросах Q состоит из запросов и их частотности, авторы определяют общую полезность страницы p как:


где f (q) — это частотность запроса q, а I(p, q) может быть определено как вероятность того что документ p получит клики на странице выдачи, сформированной текущим методом ранжирования в ответ на запрос q, полученный от пользователя. Считается, что определённый объём данных о запросах Q мы получаем из возникших в реальных условиях логов пользовательских запросов за определённый период времени, близкий к настоящему моменту. Таким образом, полезность страницы p — это ожидаемая частота пользовательских переходов на эту страницу с выдачи. В отличие от [16] и [17], мы не только измеряем текущую популярность страниц, но и общую полезность этих страниц для наращивания показателей эффективности поисковой системы, например количество будущих посещений. Таким образом, наш метод измерения качества рассчитывается на базе общей эффективности, в которой поисковая система «выиграет», если проиндексирует ту или иную страницу, а не только на этой эффективности на настоящий момент. В частности, наш подход принимает во внимание тот факт что та или иная страница становится менее популярной со своей собственной скоростью потери этой популярности.

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

От переводчиков: далее в тексте рассматривается алгоритм решения поставленной задачи со всеми соответствующими математическими выкладками. Хватило ли вам уже приведённой части статьи для ознакомления или вы хотели бы узнать все детали исследования в подробностях? Нам важно ваше мнение!
Источник: habrahabr.ru/company/altweb/blog/239153/
  anastasiapmp   1,815

Обсуждение