Компания
1 140,21
рейтинг
12 апреля 2013 в 12:23

Разработка → Обработка и классификация запросов. Часть вторая: навигационные запросы

Чего мы больше всего хотим, когда открываем интернет-поисковик? Мы хотим как можно быстрее его покинуть, как это ни парадоксально. Формулируем наше желание, жмём кнопку и скорее отправляемся туда, где оно должно исполниться (мы надеемся).



Есть всего два основных способа выражения желаний: либо описать, что нужно получить (или сделать), либо указать, куда нужно «телепортироваться». В первом случае система пытается понять запрос, правильно выбрав лучшие из ответов cети, взвешивая сотни их свойств на деревьях принятия решений. Во втором правильный ответ, как правило, всего один, и мы ожидаем, что поисковик его знает.

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

Вообще говоря, граница между что и где достаточно нечёткая. Рассмотрим два поисковых запроса: «форум велосипедистов» и «велофорум ру». В настоящее время наиболее релевантный ответ на оба этих запроса — один и тот же сайт velo-forum.ru. Разница в том, что в первом случае ответ не является единственным и существует конкуренция между ним и его аналогами, во втором же сайт обязан не только присутствовать в списке результатов, но и возглавлять его, причём вне зависимости от того, насколько он плох или хорош по сравнению с другими велофорумами. Второй запрос навигационный, а первый — нет.

Существуют также запросы смешанного типа, например «вики ономатопея». Мы пока отложим их в сторону, но ещё вернёмся к ним.

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

Зачем это нужно?

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

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

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



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

Поехали!

Мы начали с того, что просто пошли вдоль списка, выкидывая красные вкрапления, и вручную приписали каждому из оставшихся запросов его таргет. Оказалось, что одни только «вконтакте» с «одноклассниками» покрывают 5% всего потока запросов, охват же списка из 120 верхних навигационных запросов составил почти 15%. Неплохо при столь мизерных интеллектуальных затратах.

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

Помощь зала

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

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

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

Пусть Ci — количество кликов в результат Ri, а ∑Ci — общее количество кликов по запросу.
Тогда N = log Ci / log ∑Ci — степень навигационности запроса.

Ручная оценка показала, что запросы со значением метрики выше 0.95 — навигационные с высокой точностью. Причём точность эта одинаково высока как для частотных запросов, так и для редких. Таким методом базу навигационных запросов-ответов удалось вырастить до примерно 80000 единиц хранения.

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

Новые факторы

Сначала мы решили помочь тем невезучим, кого хотя бы искали (но не нашли).

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

Всё это, в конечном счете, стало элементами байесовых классификаторов и факторами в узлах деревьев принятия решений. После нескольких итераций балансировки обучающих выборок и оценки результатов обучения асессорами удалось увеличить базу ещё в 10 раз. Теперь в ней присутствовали запросы, нацеленные почти на 800 000 различных страниц, включая:
  • ведущие внутрь сайтов («жж топ»)
  • имеющие несколько подходящих сайтов («тск антарес»: торгово-строительная компания и танцевально-спортивный клуб)
  • запросы с таргетом, зависящим от региона пользователя («сбербанк», «мвидео»)

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

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



В наших обстоятельствах непредсказуемость — это нехорошо: запросы с одинаковым смыслом должны обрабатываться одинаково. Однако включение в базу всех вариантов всех запросов раздуло бы её до космических размеров. И, как нередко случается, решение второй проблемы нашлось в процессе изучения первой — способов очистки базы от вышеупомянутого шума и избыточности. Для этого нам пришлось более пристально всмотреться в «устройство» навигационных запросов.

«Устройство» запросов

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



Это реальный навигационный запрос, у него, как и положено, единственный правильный ответ.

Опишем, в чём заключаются навигационные роли:

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

Фон – фрагменты, допустимые для сайта. Само по себе их наличие в запросе не свидетельствует о его навигационной природе, но вместе с тем они не изменяют таргет при наличии подходящего ядра. Для youtube.com это такие слова, как «видео», «ролики», для headhunter.ru — «вакансии», «работа» и т.д.

Путь – слова, смещающие таргет с корневой страницы внутрь сайта. Например, слово «карты», будучи приложенным к любому ядру Яндекса, перенацеливает запрос на maps.yandex.ru

Регион – разновидность пути, обозначающая географию запроса. Особенность его в том, что для геозависимой навигации явное указание региона в тексте запроса равносильно реальному изменению местоположения пользователя. Например, запрос «икеа», полученный от пользователя из Казани, должен вести туда же, куда запрос «икеа казань», посланный из любого другого региона.

Шум – слова, ничего не значащие с точки зрения навигации. Это служебные части речи и такие слова, как «www», «http», «сайт» и т.д.

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

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

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

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

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

От хаоса к порядку

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

Зато так нам удалось убить сразу трёх зайцев одним выстрелом: полнота классификации выросла при том, что база уменьшена в размерах и очищена от низкочастотного шума. Получилось примерно следующее (dust — очень вольный перевод слова фон):



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

Онлайн-логика

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


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

Ниже приведено схематическое изображение процесса выяснения навигационности запроса «тут зайцев нет»:


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

Локальные поиски

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

Строго говоря, они не являются навигационными, но, коль скоро мы мимоходом поймали и их, грех не упомянуть.

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

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

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


Что в итоге?

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



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

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

И, наконец, визуальные последствия: для результатов навигационного поиска мы формируем расширенный сниппет, иногда выдаём несколько результатов с искомого сайта, показываем фавиконки, сайтлинки и другие спецэффекты:



Что дальше?

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

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

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

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

Михаил Долинин,
руководитель группы обработки поисковых запросов
Автор: @michoello

Комментарии (10)

  • –6
    Чего мы больше всего хотим, когда открываем интернет-поисковик? Мы хотим как можно быстрее его покинуть

    Извините, но «Поиск Mail.Ru» даже открывать не хочется.
  • +3
    Буквально вчера рассуждал о том, что современные поисковики должны чем-то подобным заниматься, чтобы оставаться конкурентными.

    Скажите, а до полноценного семантического анализа без участия человека всё ещё так же далеко как лет 10-15 назад?
    • +1
      Да, сейчас считается, что до полноценного семантического анализа без участия человека осталось примерно 20 лет. То есть столько же, сколько оставалось 10-15 лет назад.
      Это, похоже, инвариантная величина.
  • 0
    Как вы различаете ядро — понятно, шум — тоже не тяжело догадаться, а вот как вы различаете роли типа «фон» и «путь» осталось неясным.
    • –1
      > Если взять запросы, ведущие внутрь сайта (например, «райффайзен банкоматы»), и похожим образом «вычесть» из них запросы, ведущие на его корневую страницу («райффайзен»), получим путь.

      Вроде идея в том, чтобы считать путем часть запроса, которая меняет таргет с главной на внутреннюю страницу сайта.
      • 0
        Мой вопрос, не по принятой терминологии, а о том как научиться отличать где «путь», а где «фон». Какой механизм используется для этого?
        • 0
          Да и я вроде не про терминологию.
          Есть ядро [авито] и два запроса: с фоном [авито объявления] и с путем [авито телефоны].
          Ваш вопрос, как понять в каком запросе путь, а в каком фон, верно?
          Если с ядром, шумом и регионом все ясно, то судя по статье, имеется разметка:
          [авито] --> avito.ru
          [авито объявления] --> avito.ru
          [авито телефоны] --> avito.ru/telefony
          Соответственно, механизм вычитает из двух последних запросов ядро и оставляет два слова. Дальше смотрит, что одно из слов (объявления) не изменило урл в сравнении с ядром, значит является фоном, второе (телефоны) изменило урл, значит является путем.
          • 0
            Тут больше вопрос как решаются задачи классификации токенов, если есть более крупные запросы, например, [авито объявления с телефонами] в нескольких случаях:
            1) если токен «объявления» или «телефон» не размечены в базе (или такого не бывает)?
            2) если оба токена («объявления» и «телефон») размечены, как путь?

            И второй момент: как происходит классификация токенов «объявления» и «телефон» в запросе [авито объявления с телефонами], если по запросам [авито объявления] и [авито телефоны] люди кликали на два разных url в 95%+ случаев.

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка