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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

КИСЕЛЁВА Юлия Евгеньевна

МЕТОДЫ ГРУППИРОВКИ и СТРУКТУРИЗАЦИИ ПОИСКОВЫХ ЗАПРОСОВ И ИХ РЕАЛИЗАЦИЯ

05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2011

1 7 МАР 2011

4840868

Работа выполнена на кафедре информатики математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук,

профессор НОВИКОВ Борис Асенович

Официальные оппоненты: доктор физико-математических наук,

профессор ШЕВЛЯКОВ Георгий Леонидович (Санкт-Петербургский государственный политехнический университет)

кандидат технических наук, БРАСЛАВСКИЙ Павел Исаакович (Уральский государственный университет)

Ведущая организация: Южно-Уральский государственный университет

Защита диссертации состоится " \У' ^»ч^р. 2011 года в И часов на заседании совета Д212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28, ма-тематико-механический факультет Санкт-Петербургского государственного университета, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан " У2- " -^ч^^о-л'-у 2011 года.

Ученый секретарь

диссертационного совета

доктор физико-математических наук,

профессор " Даугавет И.К.

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях и семинарах:

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

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

• на Workshop Distributed Intelligent Systems and Technologies proceedings 2009;

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

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

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

Публикации. Основные результаты диссертации были опубликованы в работах: 1-6. Статья 1 опубликована в журнале, входящем в список ВАК. Статьи 3 и 6 написаны в соавторстве. В статье 3 соискателю принадлежит идея метода автоматического построения обучающего множества и метод для расширения пространства признаков при построении вероятностной модели для сегментации запросов. В статье 6 соискателю принадлежит идея использования средней и медианной статистики.

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и списка литературы. Общий объем диссертации составляет 99 страниц машинописного текста. Библиография содержит 73 наименования. Рисунки и таблицы нумеруются последовательно.

Содержание работы

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

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

В разделе 1.1 представлены традиционные модели информационного поиска: векторные модели и метод для вычисления весов слов. Данные модели адаптированы для решения задач поставленных в диссертации. В разделах 1.2 - 1.4 описаны методы оценки, применяемые в задачах информационного поиска, и тестовые наборы данных. Представленные методики были применены и для оценки разработанных в диссертации методов анализа поисковых сессий пользователей. В том числе в разделе 1.2.1 представ-

лено описание инструмента Amazon Mechanical Turk1, который был использован при составлении тестового множества для экспертной оценки, которое использовалось в дальнейшем для определения качества экспериментов. В разделе 1.5 обсуждается применимость методов группировки интернет-пользователей по интересам в таких областях исследований как:

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

• поиск шаблонов.

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

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

Журналы поисковых сессий пользователей, в большинстве своем (80,6%) состоят из информационных запросов, которые отражают заинтересованность в конкретной информации. И это предположение позволяет полагать, что поисковые запросы отражают интересы пользователей.

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

• усредненная мера близости (УМБ);

• максимизированная мера близости (ММБ).

В разделе 2.2.1 описывается метод построения УМБ, которая порождает пространство слов, состоящее из объединения всех запросов:

где N — это количество уникальных элементов и {t,} - это множество всех уникальных слов, которые присутствуют в журналах запросов, и именно они

https://www.mturk.com/mturk/welcome

являются координатами обозначенного векторного пространства. Вектор запросов пользователей представлен в следующем виде:

dj = (wft )Mh ),-Mtj ),-MtN)).

где w(tj) - это вес - tf*idf (term frequency and inverse document frequency). Для определения расстояния между пользователями используется косинусная мера близости, которая высчитывается по следующей формуле:

M(d„dj) =cos (di,dj)

В разделе 2.2.2 описывается метод для построения ММБ, для которой каждый пользователь должен быть представлен в виде набора векторов для его запросов. Каждый вектор запросов j-ого пользователя имеют следующий вид:

Qjm= Mi )Mh).....w(ti),-MtN)),

где w(tt) - это вес слова I в запросе Qlm. И документ 7-ого пользователя в векторном пространстве характеризуется набором его запросов и представляется в виде:

dj ={QA,Qj2,-,Qjn}-

И мера близости между двумя пользователями определяется по следующему принципу:

M(di,dJ)= max{cos(Qjk,Qini)}.

В разделе 2.3 описывается набор данных для эксперимента. Раздел 2.4 описывает методику «очистки» запросов с помощью системы WordNet. Раздел 2.5 содержит описание и анализ результатов эксперимента по оценке эффективности построенных метрик, которые представлены в таблице 3 в диссертации.

Согласно полученным результатам метрика УМБ показала высокие значения точности (83%), в то время как для ММБ точность не столь высока (77%). Однако значения полноты для ММБ в два раза выше (60%), чем для УМБ (30%). Поэтому метрика ММБ является наиболее приемлемой для задачи построения групп пользователей со схожими интересами. В третьей главе «Сегментация поисковых запросов» обсуждается методика машинного обучения «без учителя» для построения вероятностной модели,

9

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

В разделе 3.1 содержится описание практических проблем, которые сводятся к задаче сегментации. Обсуждается задача сегментации поисковых запросов пользователей, которая решается в данной работе. Она визуализируется на примере запроса "sony vaio 12 200gb ", который в результате работы метода преобразуется в следующую структуру:

sony —> бренд, vaio —»модель, 14—> размер дисплея, 200gb —* объем жесткого диска.

В разделе 3.2 приводится обзор существующих методов сегментации запросов и подробно представлены следующие методики:

• Условных случайных полей (УСП)(Conditional Random Fields)',

• Скрытой Марковской Модели (СММ) (Hidden Markov Model).

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

• журналы щелков пользователей (user click logs);

• база данных продуктов (products data bases).

В разделе 3.3 сформулированы следующие требования к разработанной системе сегментации запросов:

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

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

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

Раздел 3.4 содержит описание процесса автоматического маркирования запросов. Данная методика последовательно описана в разделах 3.4.1-3.4.4. В

разделе 3.4.1 подробно описываются входные данные для метода, а именно журналы поисковых сессий и база данных продуктов. Обсуждается метод для составления промаркированного множества, на основе косинусной меры близости. В качестве функции присвоения весов для слов, используется модифицированный tfidf (term frequency and inverse document frequency). Модификация состоит в том, что «документ» в нашем случае - это комбинация всех слов, описывающих данных атрибут, среди всех продуктов из базы данных, на которые щелкали пользователи. Таким образом, мы получаем тематические документы. Рассмотрим на примере «документа брендов», который содержит все слова и их частоты, которые встречались в описании атрибута «бренд». Он будет выглядеть следующим образом:

<'dell': 140, 'lenovo':90, 'asus':70>.

Если же слово не определено ни одним атрибутом, то ему присваивается значение «неизвестный».

Список атрибутов, полученный путем объединения всех атрибутов из автоматически промаркированных запросов, будем называть целевым. В разделе 3.4.2 описывается словарь брендов и их аббревиатур, который используется в «улучшенном» процессе маркирования запросов. В разделе 3.4.3 представляется процесс уменьшения разреженности в обучающем множестве. И раздел 3.4.4 содержит описания критерия составления обучающего множества. А именно, в обучающее множество отбираются запросы, которые удовлетворят следующим двум свойствам:

• все пары слово-атрибут в запросе должны иметь присвоенное им значение косинусной меры не менее 0.3;

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

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

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

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

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

^почат = ((<** = бренд, ру = 0.7),(я2 = семейство, р2 = 0.2),

( )

(я3 = объем памяти, рг =0.1),...^ = « атрибут, р, =0.01),...)'

При построении «синтетических запросов», продукты, на которые щелкнули пользователи, рассматриваются один за другим. Каждый продукт ^ представлен в следующей форме:

~ {название атрибута (а описание этого атрибута (йе^с 1)}.

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

В разделе 3.6 представлена реализация метода для автоматического составления обучающего множества.

В разделе 3.6.1 показано подробное описание разработанной системы, которая состоит из трех основных частей:

1. Автоматическое маркирование запросов.

2. Генерация обучающего множества.

3. Обучение модели для сегментации запросов.

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

Также в разделе 3.6.2 представлен метод для нормализации запросов. Раздел 3.7 посвящен описанию процесса обучения модели для сегментации запросов. В разделе 3.7.1 обосновывается выбор вероятностной модели Условные Случайные Поля (УСП) для решения задачи сегментации. Линейная цепь УСП получила широкое применение в задачах маркирования последовательностей, таких, как определение частей речи или извлечение информации.

В описываемой задаче имеется запрос, состоящий из п слов - х = (*,,х2,...,хп)тл У = (У1>У2>--->Уп)"это соответствующая ему последовательность атрибутов.

Условная вероятность между словом и атрибутом определена следующим образом:

I "

р(у\хЛ) = ~7--ехр( ХЕЛ. / ^ ¡,у,,х,1)),

где функция Zl(x) — это нормализующий фактор, _/ - это коллекция признаков и Я - это соответствующий вес.

В разделе 3.7.2 приведено подробное описание целевых атрибутов для системы сегментирования запросов.

Раздел 3.7.3 описывает набор признаков, используемых для обучения УСП. Данный набор признаков подразделяется на две основные группы:

• общие признаки;

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

Обученная модель УСП2 для сегментации предсказывает атрибут для слова с определенным уровнем доверш.

Уровень доверш - это коэффициент, значение которого принадлежит отрезку [0,1]. Он отражает «уверенность» метода в данном предсказании. В разделе 3.8 приводятся описание следующих составляющих для проведения эксперимента:

• метрики качества;

• обучающее множество;

• тестовое множество.

В разделе 3.9 приводятся анализ результатов эксперимента. Процесс анализа был разделен на два этапа:

1. В разделе 3.9.1 проводится оценка автоматического маркирования запросов. Предложенный метод показал высокие оценки, а именно точность достигает 93 % и полнота 60%. В то время как точность и полнота для базы - 83% и 37% соответственно. Данный факт говорит о превосходстве представленного в диссертации метода.

2. В разделе 3.9.2 представляется описание результирующих оценок для метода сегментации запросов. Полученный метод показал высокие оценки: точность составляет 75 % и полнота - 53%. В то время как точ-

2 Для обучения модели УПС используется имплементация, представленная в библиотеке Mallet

fhttp^'mallet.cs.umass.eJu'O

ность и полнота для базы — 70% и 51 % соответственно. Приведенные измерения показывают превосходство разработанного метода.

Раздел 3.10 содержит основные выводы по исследованию методов сегментации запросов.

В заключении формулируется список основных результатов, полученных в

диссертационной работе.

Публикации автора по теме диссертации

Статьи в журналах, рекомендованных ВАК:

1. Киселёва Ю. Е. Автоматическое сегментирование запросов интернет-магазинов. Программные продукты и системы. —2010. — Вып. № 3 (91). -С. 129- 131.

Другие публикации:

2. Киселёва 10. Группировка пользователей интернета, основанная на истории их веб-сессий. Труды 10-ой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции " RCDL'2008. - 2008. - С. 405-407.

3. Julia Kiseleva, Eugene Agichtein, Qi Guo, Daniel Billsus, Wei Chai. Unsupervised Query Segmentation Using Click Data: Preliminary Result. In processing of 19,h International Word Wide Web Conference (WWW'2010). -2010. -Pp. 1131-1132.

4. Julia Kiseleva. Grouping Web Users based on Query Log. In processing of 12th East European Conference Advances in Databases and Information Systems (ADBIS'2008). -2008. - Pp. 184-190.

5. Julia Kiseleva. Unsupervised Query Segmentation Using Click Data and Dictionaries Information. IV Российская летняя школа no информационному поиску RuSSIR'2010. Труды Четвертой Российской конференции молодых ученых по информационному поиску. — 2010. — С. 6-13.

6. Mikhail Kalinkin, Julia Kiseleva, Nikolay Vyahhi, Bernhard Lang. Comparison of Machine Learning Techniques for Document Ranking Problem. In processing of Workshop Distributed Intelligent Systems and Technologies proceedings. - 2009. - Pp. 85-92.

Подписано в печать 03.02.2011. Формат 60x90/16 Бумага офсетная. Усл. печ. л. 1 Тираж 100 экз. Заказ 34

Отпечатано в типографии ООО «Адмирал»

199048, Санкт-Петербург, В. О., 6-я линия, д. 59 корп. 1, оф. 40Н

Оглавление.

Глава 1. Методы анализа поисковых запросов пользователей.

1.1 Модели информационного поиска.

1.1.1 В екторная модель.

1.1.2 Вычисление веса слова.

1.2 Тестовые наборы данных.

1.2.1 Amazon Mechanical Turk (MTurk).

1.3 Метрики качества.

1.4 Лабораторная парадигма оценки.

1.4.1 Метод «общего котла» (pooling).

1.4.2 Характеристики котлов.

1.5 Определение групп пользователей по интересам.

1.5.1 Персонализация информации.

1.5.2 Поиск шаблонов в поведении пользователей.

1.5.3 Выявление групп пользователей.

1.6 Вероятностные модели на графах.

1.6.1 Представление графовой модели.

1.6.2 Ориентированные модели на графах.

1.6.2.1 Скрытая Марковская Модель (Hidden Markov Model).

1.6.3 Неориентированные модели на графах.

1.6.3.1 Условные случайные поля (Conditional Random Fields).

1.7 Word Net.

Глава 2. Группировка пользователей по интересам.

2.1 Классификация поисковых запросов.

2.2 Метрики для определения близких пользователей.

2.2.1 Усредненная мера близости (УМБ).

2.2.2 Максимизированная мера близости (ММБ).

2.3 Набор данных для эксперимента.

2.4 «Очистка» данных.

2.5 Полученные результаты.

2.6 Выводы.

Глава 3. Сегментация запросов.

3.1 Понятие сегментации запросов о продуктах.

3.2 Обзор существующих методов сегментации запросов.

3.3 Требования к разрабатываемой системе сегментации запросов.

3.4 Автоматическое маркирование запросов.

3.4.1 Метод составления автоматически промаркированных запросов.

3.4.2 Словарь брендов, их синонимов и сокращений.

3.4.3 Уменьшение «разреженности» в обучающем множестве.

3.4.4 Критерий составления обучающего множества.

3.5 Метод для создания «синтетических» запросов.

3.6 Реализация системы для автоматического составления обучающего множества.

3.6.1 Подробное описание реализованной системы.

3.6.2 Нормализация данных.

3.6.2.1 Нормализация базы данных продуктов.

3.6.2.2 Нормализация запросов.

3.7 Обучение модели сегментации.

3.7.1 Модель УСП для сегментации запросов.

3.7.2 Целевые атрибуты.

3.7.3 Признаки для модели УСП.

3.8 По становка эксперимента.

3.8.1 Критерии оценки.

3.8.1.1 Метрики.

3.8.1.2 Описание входных данных.

3.8.1.3 Множество для оценивания качества результатов.

3.9 Анализ результатов.

3.9.1 Оценка метода автоматического маркирования запросов.

3.9.2 Оценка качества для метода сегментации запросов.

3.9.2.1 Описание базового метода сегментации запросов.

3.9.2.2 Описание «улучшенных» методов сегментации запросов.

3.9.2.3 Выбор порога «уровня доверия» для предсказаний метода сегментации.

3.9.2.4 Результаты оценки методов сегментации запросов.

3.10 Выводы.

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

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

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

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

Данные факторы приводят к тому, что пользователи все чаще прибегают к поиску нужной им информации в интернете, и свои потребности они формулируют в виде запросов с «ключевыми словами» (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, на которой работа была награждена, как лучший студенческий постер;

10

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

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

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

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

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

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

ЗЛОВыводы

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

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

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

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

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

Заключение

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

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

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

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

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

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

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

1. И. Некрестьянов, М. Некрестьянова, А. Нозик. К вопросу об эффективности метода "общего котла". Труды 7-ой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции " RCDL'2005. - 2005.

2. М. Агеев, И. Кураленок, И. Некрестьянов. Официальные метрики. Труды Российского семинара по Оценке Информационного поиска РОМИП. 2007.- Приложение А.

3. Некрестьянов И.С. Кураленок И.Е. Оценка систем текстового поиска. Программирование.-№ 28.- 2002,- С. 226-242.

4. Некрестьянов И.С. Тематико-ориентированные методы информационного поиска. Рукопись. — 2000.

5. Юлия Киселева. Автоматическое сегментирование запросов интернет-магазинов. Программные продукты и системы. № 3 (91) . - 2010.

6. Юлия Киселева. Группировка пользователей интернета, основанная на истории их веб-сессий. Труды 10-ой Всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции "RCDL'2008. 2008.- С.405-407.

7. Agichtein Е., Ganti V. Mining Reference tables for automatic Text Segmentation. In processing of the Eleventh ACMSIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'2004). 2004. - Pp. 20-29.

8. Agirre, Eneko and David Martinez. "Integrating selectional preferences in WordNet." In: roceedings of the first International WordNet Conference, Mysore, India, 21-25 Januaiy 2002

9. Andrea Esuli, Fabrizio Sebastiani. PageRanking WordNet Synsets: An Application to Opinion Mining. In processing of 45th Annual Meeting of the Association of Computation Linguistic (ACL '2007) 2007.

10. Arasu, Garcis-Molina H. Extraction information from webpages. In processing of the ACM SIGMOD International Conference on Management Data. -2003.

11. B. Shipley. Cause and Correlation in Biology: A User's Guide to Path Analysis, Structural Equations and Causal Inference. Cambridge. - 2000.

12. B.Mobasher, H.Dai, T. Luo, and M.Nakagawa. Effective personalization based on association rule discovery from the web usage data. In Processing of 3rd International Workshop on Web Information and Data Management (WIDM'2001). 2001.

13. Baeza-Yates R., Hurtado C., Mendoza M. Query recommendation using query logs in search engines. In processing of Current Trends in Database Technology (EDBT'2004). Springer-Verlag GmbH. - 2004. - Pp. 588-596.

14. Barr C., Jones R. and Regelson M. The linguistic structure of English web-search queries. In Processing of Empirical Methods in Natural Language Processing (ENLP '2008). — 2008. Pp. 1021-1030.

15. Bernard J. Jansen, Danielle L. Booth, Amanda Spink. Determining the informational, navigational and transactional intent of Web queries. In Processing Information Processing and Management. — 44. 2008. - Pp. 1251-1266.

16. Broder, A. A taxonomy of Web search. In Processing of SIGIR Forum. -36(2).-2002.-Pp. 3-10.

17. C. Buchwalter, M.Ryan, and D. Martin. The state of online advertising: data covering the fourth Quarter. In Processing of TR Adrelevance. 2001.

18. C.W. Cleverdon. The Cranfield tests on index language devices. In Aslib Proceedings. Volume 19. 1967. - Pp. 173-192. (Reprinted in Readings in Information Retrieval, K. Sparck-Jones and P.Willett, editors, 1997)

19. Cansius, S., Spoleder, C.: Bootstraping information extraction from the field books. In Processing of Conference on Empirical Methods in Natural Language Processing (EMNLP'2007). 2007. Pp. 827-836.

20. Christopher D. Mining, Prabhakar Raghavan, Hinrich Schütze. An introduction to Informational Retrieval. Cambridge University Press Cambridge -England.- 2009

21. Crenager T., Klein D. and Manning C.: Unsupervised learning of field segmentation models for information extraction. In Processing of the Meeting of the ACL. 2005. - pp. 371-378.

22. D. Edwards. Introduction to Graphical Modelling. 2nd ed. - SpringerVerlag. - 2000.

23. Data mining for hypertext: A tutorial survey. SIGKDD Explorations, 1(2). -2000. Pp. 1-11.

24. E. M. Voorhees. The philosophy of Information Retrieval Evaluation. Revised Papers from the Second Workshop of the Cross-Language Evaluation

25. Forum on Evaluation of Cross-Language Information Retrieval Systems. 2001.-Pp. 355-370.

26. E. Voorhees. TREC 2007 Introduction (slides). Gaithersburg, Maryland, USA. - 2007

27. G.Salton and M.J. McGill. Introduction to the modern Informational Retrieval. McGraw-Hill Computer Science Series. - McGraw-Hill, New-York. - 1983.

28. Grandvalt, Y., Bengio, Y.: Semi-supervised Learning by Entropy Minimization. In processing of CA?. 2005. - Pp. 281-296.

29. Grcar M. User Profiling: Web Usage Mining. In Proceedings of the 7th International Multiconference Information Society IS 2004. October 9-15. -Ljubljana, Slovenia. 2004,- Pp. 79-82

30. Gui-Rong Xue, Hua-Jun Zeng, Zheng Chen, Yong Yu, Wei-Ying Ma, WenSi Xi, WeiGuo Fan. Optimizing web search using web-click through data. In processing of 13th ACM Conference on Information and Knowledge Management (CIKM'2004). 2004. - Pp. 118-126.

31. Hammersley J., Clifford, P. Markov fields on finite graphs and lattices. Unpublished manuscript. 1971

32. I. Soboroff. On evaluating Web Search With Very Few Relevant Documents. In Processing of the Annual International ACM SIGIR conference on Research and Development in Informational Retrieval (,SIGIR'04').- 2004. -Pp. 530-531.

33. J. Borges and M. Levene. Detecting Concept Drift in Web Usage Mining. In Proceeding of the Workshop on Web Mining and Web Usage Analysis. -2008.-Pp. 98-110.

34. J. Lafferty, A. McCallum and F.Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequences data. In Processing of the International Conference of Machine Learning. Williamstown, MA, USA. - 2001.-Pp. 282-289.

35. J. Pearl. Causality: Models, Reasoning and Inference. Cambridge Univ. Press. - 2000.

36. J. Zobel. How reliable are the Results of Large-Scale Information Retrieval Experiment?. In Processing of the 21st Annual ACM SIGIR Conference on Research and Development in Informational Retrieval (SIGIR'98). 1998. -Pp. 307-314.

37. Jiao F., Wang S., Lee C.-H., Greiner R., Schuumians D. Semi-Supervised Conditional Random Fields for Improved Sequence Segmentation and Labeling. In processing of 47th Annual Meeting of the Association of Computation Linguistic (ACL'2007). 2009

38. Johannes L., Gareth J., Jones F. Queiy recovexy of short user queries: on query expansion with stopwords. In Processing of the 33rd Annual ACM SI95

39. GIR Conference on Research and Development in Informational Retrieval (SIGIR 2010). 2010 - Pp. 733-734.

40. Joseph K. Bradley, Carlos Guestrin. Learning Tree Conditional Random Fields. In Processing of the 27th International Conference on Machine Learning (ICML 2010). 2010. Pp. 127-134.

41. Julia Kiseleva, Eugene Agichtein, Qi Guo, Daniel Billsus, Wei Chai. Unsupervised Query Segmentation Using Click Data: Preliminary Result. In Processing of 19th International World Wide Web Conference (WWW2010). -2010.- Pp. 1131-1132.

42. Julia Kiseleva. Grouping Web Users based on Query Log. In processing of 12th East European Conference Advances in Databases and Information Systems (ADBIS'2008). -2008. Pp. 184-190.

43. Kevin P.Murphy. An introduction to graphical models. MIT Press. 2001.

44. Li X., Wang Y.-Y., Acero A. Learning query intent from regularized click graph. In Processing of the 31st Annual ACM SIGIR Conference on Research and Development in Informational Retrieval. — 2008. Pp. 339-346.

45. M. I. Jordan, editor. Learning in Graphical Models. MIT Press. -1999.

46. Mikhail Kalinkin, Julia Kiseleva, Nikolay Vyahhi. Bernhard Lang. Comparison of Machine Learning Techniques for Document Ranking Problem. In processing of Workshop Distributed Intelligent Systems and Technologies proceedings. 2009. - Pp. 85-92.

47. Olfa Nasraoui, Myra Spiliopoulou, Jaideep Srivastava, Bamshad Mobash-er, Brij M. Masand. Advances in Web Mining and Web Usage Analysis. In Processing of 8th International Workshop on Knowledge Discovery on the Web (WebKDD). 2006.

48. P. Spirtes, C. Glymour, and R. Schemes. Causation, Prediction and Search. MIT Press. 2nd edition. - 2000.

49. Pinto D., McCallum A., Wei X., Croft W.B. Table extraction using conditional random fields. In Processing of the 26th Annual ACM SIGIR Conference on Research and Development in Informational Retrieval. 2003. Pp. 235-241,

50. Q. Yang, H.H. Zhang, and T. Li. Mining web logs for prediction models in www caching and prefetching. In Processing of International Conference on Computer Networks and Mobile Computing (ICCNMC'01). 2001.

51. R. Baeza-Yates, B. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley, Wokingham, UK 1999.

52. Robins D. Interactive Information Retrieval. Context and Basic Notions. Informing Science, 3(2). -2000. Pp. 57-62.

53. S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach -Prentice Hall, Englewood, NJ. 1995.

54. Sanda M. Harabagiu. An Application of WordNet to Prepositional Attachment. In Processing of 34th Annual Meeting of the Association of Computation Linguistic (ACL '1996). -1996. Pp. 360-362.

55. Shen D., Li Y., Li X. Dengyong Zhou. Product query classification. In Processing o/18th ACM Conference on Information and Knowledge Management (CIKM 2009). 2009. Pp. 741-750.

56. T.Li, Q. Yang, K.Wang. Classification pruning for web-request prediction. In processing of 10th International World Wide Web Conference (WWW'2001). 2001.

57. X. Yu and H. Shi. Query Segmentation Using Conditional Random Fields. In Processing of The first International Workshop on Keyword Search on structured data. Providence, Rhode Island, USA. - 2009. Pp. 21-26

58. Yanhong Zhai, Bing Liu. Extracting Web Data Using Instance-Based Learning. In Processing of International World Wide Web Conference (WWW'2007). 2007. Pp. 113-132.

59. Yanhong Zhai, Bing Liu. Web data extraction based on partial tree alignment. In Processing of World Wide Web Conference (WWW'2005). 2005. Pp. 76-85.

60. Yongge Shi, Yiqun Zhou. An Improved Apriori Algorithm. In Processing of Gordon Research Conference (GRC' 2010). 2010. Pp. 759762.

61. Yves Grandvalet, Yoshua Bengio. Semi-supervised Learning by Entropy Minimization. In Processing of CAP. 2005. Pp. 281-296.

62. Zhao C., Mahmud J. and Ramakrishna I. Exploiting structured reference data for unsupervised text segmentation with conditional random fields. In Processing of the SI AM International Conference on Data Mining. 2008.

63. Zhu J., Zhang B., Nie Z., Wen J.-R. and Hon H.-W. Webpage understanding: and integrated approach. In Processing of the Thirteenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007. Pp. 903-912.