Работаем с 2009 года Более 450 успешных проектов Санкт-Петербург
8 (999) 849-91-09

Все ли пользователи систем информационного поиска одинаково благонадежны?

Посвящается Илье Сегаловичу (13 сентября 1964 — 27 июля 2013). Светлая память. Кванли Син, Йин Лю, Ронвэй Чен, Мин Чжанг, Шаопин Мэй, Лиюн Ру Факультет информационных технологий университета Цзинхуа, Пекин, Китай.

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

1. Введение

Технологии обратной связи по релевантности в настоящее время используются в системах информационного поиска достаточно широко и, как вы можете понять, их основное предназначение состоит в улучшении качества поиска и взаимодействия с пользователем. Однако насколько нам известно, большинство моделей обратной связи, использующих кликовую информацию не уделяют пристального внимания качеству источников вышеуказанной связи, априори заявляя о благонадежности пользователя поиска. Sadagopan и др. [1] идентифицировали типичные и атипичные пользовательские сессии в потоке кликов, но это было выполнено на уровне сессии и без распознавания различных кликов. Мы можем представить, что опытность пользователей будет иметь существенные различия, обусловленные такими всевозможными причинами, как профессия и уровень образования. Например, мы полагаем, что в большинстве случаев опытные пользователи будут кликать по лучшим результатам органического поиска, нежели чем их неопытные собратья. Это свидетельствует о том, что информация обратной связи, следующая от пользователей различного уровня, будет также приобретать для нас и различную степень важности. Таким образом, обратная связь по релевантности может оказаться недостаточно аккуратной в том случае, если мы не будем отделять пользователей друг от друга в моделях обратной связи. Следовательно, оценка благонадежности веб-пользователей должна проводиться на этапе сбора информации обратной связи. В настоящем материале мы предлагаем графоориентированный подход, позволяющий оценивать пользовательскую благонадежность. Для начала мы создаем кликовый граф, описывающий отношения между пользователями посредством их кликов. Затем, мы используем итеративный алгоритм для подсчета оценок благонадежности по созданному ранее графу. И, наконец, мы экспериментально наблюдаем воздействие оценок благонадежности на эффективность обратной связи по релевантности. Результаты демонстрируют, что эффективность учета обратной связи действительно меняется от пользователя к пользователю, в соответствии с присужденными им оценками благонадежности; отсюда может быть выявлена тенденция. Это служит подтверждением нашей гипотезы о том, что пользовательская благонадежность должна быть учтена в том случае, если мы хотим улучшить качество органического поиска, сообщая машине о релевантности тех или иных интернет-страниц, выбранных пользователем.

2. Оценка пользовательской благонадежности

2.1 Определение

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

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

2.2 Графовая модель

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

Рисунок 1. Пример графа пользовательских кликов.

Примером, демонстрирующим созданный граф, может послужить Рисунок 1(а). Допустим, Пользователь 2 проходит по l1,l2,l3,l4 ссылке, используя запрос q3. Поскольку Пользователь 1, используя запрос q3, также кликает по ссылке l3, оба пользователя соединяются ребром. Кроме того, Пользователь 3 имеет два общих клика с Пользователем 2, а потому между ними формируются два ребра. Рисунок 1(b) представляет наш граф в иной форме, объединяя кратные ребра между двумя узлами в одно, а также назначая весовые значения для каждого соответствующего направления единого ребра. Таким образом, мы создаем итеративный алгоритм для подсчета оценок благонадежности каждого пользователя. Оценка благонадежности ri пользователя i определяется следующим образом:

 

,где E представляет собой реберный набор, Pij является штрафным коэффициентом для пользователя i с пользователем j, а Wij — реберный вес, следующий от пользователя j к пользователю i.

 

Qij представляет собой общий для пользователя i и j набор поисковых запросов. Di(q) является набором тех результатов, по которым прошел только пользователь i, использовав запрос q; Ci(q) является набором тех результатов, по которым прошел пользователь i, использовав запрос q; Eji является реберным набором, сформированным между пользователями i и j. Отметим, что как Pij отличается от Pji, так и Wij отличается от Wji. Используя в качестве примера все тот же граф, который изображен на Рисунке 1, для Пользователя 2 мы имеем r2=(3/4)•(r1/3+2r3/3). Та как ссылка l4 остается нетронутой каким-либо пользователем, за исключением Пользователя 2, то к данному пользователю применяется штрафной коэффициент, составляющий 3/4. Мы инициализируем ri на значении 1/N и завершаем процесс по истечению 20 итераций.

3. Эксперименты и оценка

3.1 Набор данных

Наш алгоритм был выполнен в течение одного дня (1 октября 2009) на реальных поисковых логах крупнейшей китайской поисковой системы Sogou. На этапе создания графа мы исключаем из своих расчетов те пользователей, которые имеют не более 3-х кликов по той простой причине, что они не являются активными пользователями поисковой машины и, таким образом, необходимость оценки их благонадежности не представляется такой уж необходимой. В ходе данного процесса мы удаляем порядка 80% веб-пользователей. Распределение кликов (РК) [3] описывает плотность кликов для данного запроса. Мы удаляем пользовательские запросы со значением РК превышающим 0.5, которые имеют сходящиеся клики на некотором соответствующем результате. Причина этого заключается в том, что большинство из этих запросов (например, такие навигационные запросы, как «продвижение сайтов в компании SEO-константа») возвращают очевидные ответы, не позволяющие нам дать четкое представление о степени благонадежности пользователя. Содержание навигационных запросов будет стоить нам дополнительного времени исполнения алгоритма, да и на практике поисковые машины достаточно хорошо обрабатывают данные пользовательские запросы, а потому мы не видим никакого резона сосредотачиваться на них в решении указанной проблемы обратной связи. После предварительной обработки информации мы имели 691.290 пользователя и 3.382.001 уникальных кликов по графу.

3.2 Эффективность благонадежности

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

 

Рисунок 2. Распределение оценок благонадежности

Глядя на Рисунок 2, на котором изображен график с логарифмическим масштабом по обеим осям, можно увидеть, что распределение числа пользователей по показателю благонадежности в основном поддается степенному распределению. Такое распределение согласуется с нашими ожиданиями, а именно с тем, что количество пользователей быстро уменьшается по мере увеличения благонадежности. Для того, чтобы оценить эффективность нашего подхода мы создали перечень пользователей в порядке убывающих оценок благонадежности, а также сегментировали его по 10 блоков. Каждый блок содержал одинаковое число пользователей. То есть, первый блок содержал в себе 10% пользователей с наибольшими оценками благонадежности, а десятый блок — 10% пользователей с наихудшими показателями благонадежности. Мы позволяем веб-пользователям, размещенных в наших десяти блоках, голосовать за релевантность тех или иных результатов поиска. Один клик приравнивается к одному голосу, а итоговый результат голосования представляет собой суждение об относительной релевантности, которая присуждается голосующими. Для того, чтобы оценить эффективность обратной связи для каждого блока пользователей мы используем тестовый набор данных, в котором релевантность каждого результата, оказавшегося в ТОП-10 по 600 рандомно выбранным пользовательским запросам, имеет мануально-нанесенную метку: не релевантный, не совсем релевантный, релевантный, в высшей степени релевантный. Аккуратность обратной связи мы оцениваем с помощью метрики Тау Кендалла, которая описывает согласованность попарных суждений о релевантности между помеченными результатами и результатами обратной связи. Рисунок 3 (а) демонстрирует производительность каждого блока пользователей.

 

Рисунок 3. Эффективность обратной связи по релевантности

Мы наблюдаем, что пользователи, имеющие высокие оценки благонадежности, достигают лучших результатов в обратной связи по релевантности нежели чем те, что располагают меньшими оценками. Это свидетельствует о том, что полученные нашим алгоритмом оценки благонадежности отражают благонадежность и самих пользователей поиска. С учетом данной тенденции, мы заинтересованы в получении информации о том, какое количество пользователей обеспечивает большую аккуратность обратной связи. Рисунок 3 (b) демонстрирует производительность обратной связи в том случае, когда мы заняли различную долю пользователей, обладающих наибольшей благонадежностью. График указывает на то, что обратная связь оказывается эффективней за счет включения большего числа пользователей в начале и достигает наилучшей производительности с участием 60% от всех наиболее благонадежных веб-пользователей. Отметим, что пользователи поиска с высокими оценками благонадежности демонстрируют лучшую эффективность, нежели чем выбранные случайно.

4. Заключение и будущая работа

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

Ссылки:

[1] N. Sadagopan and J. Li. Characterizing typical and atypical user sessions in clickstreams. In WWW 08 :Proceedings of the 17th international conference on World Wide Web

[2] R. Cen, Y. Liu, M. Zhang, L. Ru and S. Ma. Automatic Search Engine Performance Evaluation with the Wisdom of Crowds. In AIRS 2009, Japan

[3] U. Lee , Z. Liu , J. Cho, Automatic identification of user goals in Web search, In WWW 05: Proceedings of the 14th international conference on World Wide Web

Перевод материала «Are Search Engine Users Equally Reliable?» выполнил: Константин Скоморохов

Полезная информация по продвижению сайтов:

Перейти ко всей информации