Методы группировки и структуризации поисковых запросов и их реализация

Актуальность темы

.

Исследованиям в области анализа поисковых запросов уделяется много внимания в последние годы. Этому способствуют многие факторы, среди которых:

• общедоступность интернета для пользователей;

• увеличение объема полезной для пользователей информации в интернет-пространстве.

Данные факторы приводят к тому, что пользователи все чаще прибегают к поиску нужной им информации в интернете, и свои потребности они формулируют в виде запросов с «ключевыми словами» (keyword queries), и, как следствие, объем обрабатываемых поисковых запросов значительно увеличивается каждый год. В результате накапливаются большие по объему журналы, содержащие поисковые запросы пользователей (search query logs). Однако, любые коллекции данных бесполезны, если не существует методики для их анализа.

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

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

Также большое внимание уделяется методам, которые позволяют преобразовывать неструктурированный запрос пользователя1 с «ключевыми словами» (keyword queries) в структурированный. Основная причина популярности подобных методов заключается в том, что большая часть интернет-данных изначально содержатся в структурированных базах данных. И знание структуры запроса значительно облегчает поиск релевантных ответов. Для обучения модели анализа запросов, которая получает из запроса структуру, необходимо составить обучающее множество, в котором каждый запрос описывается векторами признаков (feature vector) или просто признаками — наборами числовых параметров, отражающих свойства характеристик запроса. Вектора признаков принимают значения в пространстве признаков. Задав метрику в подобном пространстве, можно сравнивать запросы друг с другом, вычисляя расстояние между соответствующими им векторами. Методы для создания обучающего множества и построения векторов признаков являются ядром любой системы анализа запросов. Качество системы анализа поисковых запросов в основном зависит от выбора обучающего множества и признаков, а также метрик для их сравнения.

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

В последние годы так же были разработаны методы, использующие «частичное обучение с учителем» (semi-supervised learning), которые используют 6 небольшое по размеру обучающее множество на первом этапе обучения, а затем итеративно добавляют наиболее хорошие предсказания, таким образом, расширяя обучающее множество.

В настоящее время существуют огромные объемы данных, которые содержат журналы щелчков пользователей. И естественно предположить, что на основе этих данных есть возможность создать обучающее множество автоматически, без использования работы асессоров, составляющих обучающее множество вручную. Данная концепция получила название обучение «без учителя» (unsupervised learning).

Цели работы.

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

Для достижения поставленной цели были выделены следующие задачи:

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

• Разработка метода для автоматического построения обучающего множества, которая обуславливается желанием не использовать дорогостоящие и трудоемкие методы составления обучающего множества вручную. Автоматический метод в качестве входных данных должен использовать только журналы щелчков пользователей (user clicks logs) и базу данных с описанием продуктов (product data base), которые ищут и на которые щелкают пользователи.

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

Основные результаты.

На защиту выносятся:

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

2. Реализованный прототип системы для группировки пользователей по интересам. Эксперименты для оценки достоверности полученных метрик проведены на реальных англоязычных запросах пользователей.

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

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

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

6. Проведены эксперименты с системой сегментации запросов на реальных данных и получены высокие экспериментальные оценки полноты, точности предложенного метода.

Научная новизна.

Научной новизной обладают следующие результаты работы:

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

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

• предложенный метод построения эффективных признаков для модели обучения сегментации запросов, которая преобразует неструктурированный запрос в структурированный запрос;

• разработанная система для сегментации запросов, которая обучается «без учителя».

Теоретическая ценность и практическая значимость.

Главной причиной внедрения методов анализа поисковых запросов являются:

• улучшение качества поиска;

• улучшение ранжирования результатов поиска;

• структуризация запросов с «ключевыми словами»;

• персонализация информации.

Данные методы также находят широкое применение в различных областях интернет-индустрии, таких как:

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

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

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

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

Апробация работы и публикации.

Основные результаты диссертации были опубликованы в работах: [5], [6], [45], [46], [47], [53] и докладывались на следующих конференциях и семинарах:

• на десятой Всероссийской научной конференции «Электронные Библиотеки: перспективные методы и технологии, электронные коллекции» К-СБЬ 2008, на которой работа была награждена, как лучший студенческий постер;

• на двенадцатой Восточно-Европейской Конференции по Базам Данных и Информационным системам ABDIS 2008;

• на третьей и четвертой конференциях Молодых Ученых при Российской Школе по Информационному Поиску RUSSIR 2009 и RUSSIR 2010, на которой работа была награждена, как лучшая статья;

• на двадцатой Международной Конференции World Wide Web 2010;

• на семинарах группы исследования методов организации информации при лаборатории исследования операций НИММ.

Структура диссертации.

Диссертация состоит из введения, трех глав и заключения:

ЗЛОВыводы.

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

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

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

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

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

Заключение

.

В диссертации получены следующие основные результаты:

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

2. Реализованный прототип системы для группировки пользователей по интересам. Эксперименты для оценки достоверности полученных метрик проведены на реальных англоязычных запросах пользователей.

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

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

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

6. Проведены эксперименты с системой сегментации запросов на реальных данных и получены высокие экспериментальные оценки полноты, точности предложенного метода.