Содержание к диссертации
Введение
Глава 1. Анализ существующих систем и методов поиска информации в Интернет 17
1.1. Информационный поиск 17
1.1.1. Место изучаемых методов поиска в теории информационного поиска 17
1.1.2. Информационные потребности пользователя и язык запросов 19
1.1.3. Релевантность 21
1.1.4. Оценка качества поиска 21
1.1.5. Основные модели представления данных и поиска 23
1.1.5.1. Булева модель 23
1.1.5.2. Модель векторного пространства 24
1.1.5.3. Вероятностная модель 25
1.1.6. Латентное семантическое индексирование 26
1.1.7. Вероятностное латентное семантическое индексирование 27
1.2. Анализ существующих систем поиска информации в Интернет 29
1.2.1. Характеристика классических поисковых систем WWW 29
1.2.2. Описание, задачи и основные требования к поисковым системам WWW 30
1.2.3. Обзор классических поисковых систем WWW 33
1.2.4. Архитектура и недостатки поисковых систем 40
1.2.4.1. Системы с централизованной архитектурой 40
1.2.4.2. Децентрализованная распределенная архитектура предлагаемой поисковой системы 42
1.2.5. Основные задачи, решаемые компонентами разрабатываемой системы с децентрализованной распределенной архитектурой 45
1.2.5.1. Информационный агент 45
1.2.5.2. Маршрутизация запросов пользователей 47
1.2.5.3. Настраиваемый пользовательский интерфейс 47
1.3. Выводы 48
Глава 2. Разработка алгоритма и архитектуры тематического информационного агента 49
2.1. Архитектура агента 53
2.2. Фильтр ядра индекса 58
2.3. Фильтр запросов пользователей 59
2.4. Управление очередью ссылок 64
2.5. Алгоритм работы агента 67
2.6. Эксперименты 67
2.7. Заключение 70
Глава 3. Разработка алгоритма и архитектуры брокера, осуществляющего маршрутизацию запросов пользователя 72
3.1. Задачи, решаемые брокером запросов 72
3.2. Архитектура брокера 74
3.3. Алгоритм работы брокера 78
3.3.1. Оценка числа документов, релевантных запросу пользователя 78
3.3.2. Алгоритм маршрутизации 83
3.4. Описание коллекций и результаты экспериментов 88
3.5. Заключение 90
Глава 4. Разработка настраиваемого пользовательского интерфейса 93
4.1. Информационные потребности пользователя и язык запросов 93
4.2. Сценарии работы пользователя 96
4.3. Выявление информационных потребностей пользователя 97
4.4. Поиск 104
4.4. Поиск 104
4.5. Результаты экспериментов 106
4.6. Заключение 111
Заключение 114
Список использованных источников 123
Приложение 1. Блок-схема алгоритма агента 133
Приложение 2. Блок-схема алгоритма брокера 137
Приложение 3. Формы интерфейса пользователя 139
Приложение 4. Структура и листинг программной реализации агента 140
Приложение 5. Блок-схема алгоритма брокера 165
Приложение 6. Структура и листинг программы интерфейса пользователя 184
Приложение 7. Документы подтверждающие внедрение и использование результатов диссертационной работы 205
- Информационные потребности пользователя и язык запросов
- Архитектура агента
- Оценка числа документов, релевантных запросу пользователя
- Результаты экспериментов
Информационные потребности пользователя и язык запросов
При изучении вопросов, связанных с информационным поиском, необходимо прежде всего рассмотреть такое понятие как информационные потребности пользователя.
Очевидно, что каждый пользователь любой поисковой системы имеет определенные информационные потребности, которые он должен выразить на языке запросов данной системы. При этом пользователь сталкивается со следующими проблемами:
Недостаточный уровень знаний в той области, в которой проводится поиск
Действительно, для построения хорошего запроса пользователь должен знать ключевые слова данной предметной области, их частоту использования, ключевые слова из смежных областей. В противном случае либо в результат поиска не попадут интересующие пользователя документы, либо в результат будет включено огромное число документов, не интересующих данного пользователя, а нужные ему документы затеряются среди них.
Владение языком запросов данной поисковой системы
Многие поисковые системы предоставляют пользователям возможность построения весьма сложных запросов. При этом используются логические операции, скобки, различные атрибуты и т.д. Как правило, алгоритм поиска, используемый данной поисковой системой, не известен конечному пользователю, в связи с чем он не может прогнозировать качество поиска при использовании тех или иных возможностей языка запросов. Необходимо приобретение определенного опыта работы с конкретной поисковой системой.
Знание содержимого коллекции, в которой выполняется поиск
Включаемые в запрос термины должны обладать определенной дискриминационной силой. Включение в запрос общеупотребительных в данной коллекции слов только уменьшит точность поиска. Информация о статистике распределения слов в данной коллекции также недоступна конечному пользователю. Альтернативой является получение определенного опыта работы с данной поисковой системой.
Проведенный анализ позволяет высказать следующее утверждение. Пользователь современных поисковых систем будет использовать запросы в достаточно простой форме, не учитывая их общеупотребительность в рамках данной системы. Для повышения качества результата поиска современная по исковая система должна самостоятельно выявлять информационные потребности конкретного пользователя и учитывать эту информации при поиске в интересах данного пользователя.
Архитектура агента
Тематический агент функционирует в интересах определенного тематического индекса D и в связи с этим имеет доступ ко всей информации, содержащейся в этом индексе. Мы полагаем, что это следующая информация:
Для каждого проиндексированного документа d є D и каждого входящего в него терма t є T(d) хранится число вхождений t в d - tf(d, t).
Для каждого проиндексированного терма t є T{D) хранится n{t) - число документов из D, содержащих терм t
n(t) = \{d:d&D,teT(d)].
Здесь, как и ранее, D задается множеством проиндексированных документов
D == {н/, ..., «я},
Т{([)- словарь документа d (множество входящих в него термов), T(D)- словарь индекса D:
T(D) = \JMT(d).
Представляется оправданным полагать, что упомянутая информация будет всегда доступна тематическому агенту. Это минимальная информация о проиндексированных документах, которая может быть получена при гюлнотек-стовом индексировании.
Архитектура тематического агента представлена на рис. 2.1.
Тематический агент, архитектура которого описывается в данном разделе, состоит из следующих компонентов:
Анализатор ядра индекса
Цель данной компоненты - подготовить информацию, которая будет далее использоваться генератором тематических фильтров. По сути дела, на этом этапе необходимо вычислить веса всех термов из T(K(D)), где через K(D) будем обозначать ядро индекса. Во введении уже описывался ряд моделей, которые могут использоваться при вычислении весов термов. В данной работе выполнена экспериментальная проверка эффективности использования вероятностного латентного семантического индексирования для решения задачи анализа ядра индекса.
Выбор данной модели обосновывается следующим образом.
Вероятностное латентное семантическое индексирование ориентировано именно на выявление скрытых факторов (которые можно интерпретировать как темы) в коллекции документов. Вся необходимая для этого информация доступна агенту непосредственно из индекса. Фактически это функция tf (d, t), дающая число вхождений терма t в документ d.
Известно, что метод вероятностного латентного семантического индексирования требует относительно больших вычислительных ресурсов. Это связано с тем, что на каждом шаге метода оценивания-максимизации, описанного во введении, оцениваются значения следующих функций:
P(z) - число точек, в которых оценивается значение функции, равно числу факторов Щ (фиксированное число из диапазона 50-150)
P(t\z) - число точек, в которых оценивается значение функции, равно Щ х \T(K(D))\.
P(d\z) - число точек, в которых оценивается значение функции, равно Щ х \K{D)\.
P{z\d, t) - число точек, в которых оценивается значение функции, равно \Z\ х \K(D)\ х \T(K(D))\. Для уменьшения объема вычислений данной функции было сделано следующее предположение - P{z\d, і) = 0, если № 0 = 0.
Приведенные оценки показывают, что для коллекций большого размера применение непосредственное метода вероятностного латентного индексирования становится невозможным из-за быстрого роста объема вычислений. Однако, ядро индекса имеет относительно небольшой размер, что и делает возможным применение данного метода.
Анализатор архива запросов Задача данной компоненты - анализ архива запросов пользователей, обратившихся к данному индексу ранее. Цель анализа - вычисление весов термов, встречавшихся в запросах пользователей, для последующего их использования при построении фильтра запросов. Для вычисления весов термов нужна достаточно объемная статистика. Для термов запросов, которые встречаются и в ядре индекса, в качестве весов разумно выбирать веса, вычисленные на основе анализа ядра индекса методом вероятностного латентного семантического индексирования.
Проблему представляет построение разумной оценки для весов тех термов, которые входят в запросы пользователей, но не представлены в ядре индекса. Здесь предлагается метод оценки весов таких термов, основанный на учете известных весов термов из ядра индекса и наличии связи этих термов с новыми термами, заданной вхождением термов в один и тот же запрос, представляется разумным предполагать, что термы, вошедшие в один запрос пользователя, с относительно большой вероятностью семантически связаны, что и дает возможность оценки весов новых термов через веса известных термов.
Вообще говоря, информация, поступающая в поисковую систему от пользователя, представляет собой ценнейший ресурс, который надо в максимально возможной степени использовать при решении всех задач поиска. Архивация запросов пользователей и анализ этого архива - шаг в указанном направлении.
Подробно алгоритм оценки весов термов из запросов пользователей описан в разделе, посвященном построению фильтров.
Генератор тематических фильтров
Традиционно в качестве фильтра при решении задач поиска документов используется взвешенное множество термов. Новый документ проходит через фильтр, если сумма произведений весов термов, общих для фильтра и документа, на частоты вхождения этих термов в новый документ превышает некоторый порог. В данной работе таким образом формируется как фильтр ядра индекса, так и фильтр запросов. Остается вопрос о выборе числа термов, включаемых в эти фильтры и о выборе порогов. Данные вопросы решаются в процессе проведения экспериментов.
Компонента, обеспечивающая загрузку документа по заданному URL Данная задача решается с помощью стандартной утилиты для Linux - wget.
Компонента, обеспечивающая разбор документа.
Задача этой компоненты - вычисление величин tf[d, і) для всех термов t загруженного документа d. Эта информация необходима для фильтрации нового документа через фильтр ядра индекса и фильтр запросов. В случае, если новый документ признается релевантным тематике индекса, необходимо выделение из текста документа ссылок на новые документы для последующей их загрузки и анализа. Выделение этих ссылок также возлагается на рассматриваемую компоненту.
Компонента, обеспечивающая фильтрацию документа
При наличии двух фильтров необходимо осуществить их интеграцию на этапе принятия решения о признании нового документа релевантным тематике индекса. Фильтры ядра индекса и запросов отражают возможно существенно различающиеся информационные интересы администратора (владельца) индекса и пользователей. В данной работе предлагается равноправно учитывать интересы и администратора, и пользователей. В связи с этим, документ признается релевантным тематике индекса, если он проходит хотя бы через один из двух фильтров.
Компонента, управляющая очередью ссылок
Как уже отмечалось ранее, в рамках выбранного в данной работе подхода, сетевой робот сканирует Интернет, просматривая документы, на которые имеются ссылки в просмотренных ранее и признанных релевантными документах. Число таких ссылок растет очень быстро, и от эффективности организации очереди подлежащих просмотру ссылок зависит и эффективность работы агента, которую мы измеряем отношением числа загруженных релевантных документов к общему числу релевантных документов. В данной работе предлагается новый подход к решению задачи управления очередью ссылок, осно ванный на оценке вероятности релевантности документа, на который указывает ссылка. Подробнее данный алгоритм описан в разделе "Алгоритм работы агента .
Оценка числа документов, релевантных запросу пользователя
Формула (3.1) была выведена в цитированной работе на основе использования вероятностной модели. Из (3.1) непосредственно видно, что вес терма t , рассматриваемого как терм из описания индекса, зависит от самого индекса, вес же этого же терма, рассматриваемого как терм запроса, зависит только от запроса.
В данной главе используется более сложная модель, в которой вес терма из запроса меняется в зависимости от индекса, в который направляется данный запрос.
Отсюда видно, что имеет место следующая зависимость между весом терма запроса и индексом, в который этот запрос был направлен: При фиксированном индексе Д и частоте вхождения/ / терма t в запрос q вес терма t запроса возрастает с уменьшением длины запроса. Это естественное предположение, т.к. с уменьшением числа термов запроса их информативность возрастает, в частности, уменьшается вероятность вхождения в запрос так называемого стоп-слова.
При фиксированном запросе q вес терма t этого запроса увеличивается при направлении данного запроса в индекс, содержащем ссылки на документы с большей средней длиной (выраженной числом входящих термов). Это предположение также может рассматриваться правильным в связи со следующим принципом, используемым многими экспертами при оценке релевантности документа запросу: некоторый документ считается релевантным некоторому запросу, если в данном документе имеется фрагмент (даже относительно короткий), отвечающий данному запросу. Если некоторый терм входит в некоторый достаточно длинный документ, то вероятность того, что в данном документе этот термин будет упомянут хотя бы один раз в контексте запроса выше, чем при вхождении этого терма в относительно короткий документ. Для вычисления величины Vt i используется следующая формула
При реальной работе брокера не вся указанная выше информация будет ему доступна. В отличие от сетевого робота (информационного агента), который работает в интересах индекса и, следовательно, имеет доступ ко всей информации, хранящейся в индексе, брокер является внешней по отношению к индексу компонентой и может использовать только ту общедоступную информацию об индексе, которую сам индекс разместил в общедоступном репозита-рии.
Мы полагаем, что из описания индекса Д брокер получит следующую информацию:
Lavr{i) - среднее число термов в документах коллекции Du
Уц - вес терма t в коллекции Д-.
Очевидно, что по заданному запросу q используя данное описание коллекции можно вычислить оценку числа релевантных документов Rt с точностью до выбора констант к и С. Выбор этих констант принадлежит брокеру, и в данной главе рассмотрен вопрос об их выборе.
Что касается весов термов в описании индекса (Уц), то методика их вычисления в общем случае брокеру неизвестна. Данные веса могут вычисляться в индексе с использованием любого подхода. В данной работе мы предположили, что веса термов в описании индекса вычисляются с использованием схемы, описанной ранее. Тогда администратор индекса должен определить значение параметра к. В экспериментах, описанных далее, рассматривается вопрос об оптимальном выборе этого параметра. Полученные результаты могут рассматриваться как рекомендации администратору индекса. Следуя им, он повысит качество работы всей распределенной системы в делом, что привлечет к системе дополнительных клиентов и, следовательно, дополнительных клиентов к данному индексу.
Таким образом, предлагаемый подход к оптимизации распределенной системы, отдельные компоненты которой принадлежат различным владельцам, состоит в выдаче рекомендаций, при выполнении которых большинством владельцев, вся система в целом получит большую прибыль.
Кроме выбора параметра к, при использовании схемы (3.3) администратор индекса может поставить задачу выбора функции/ .
Как указано в описании формулы (3.3.),/, есть число вхождений терма t в документ d. Однако эта функция может быть заменена другой.
Заметим, что величина ft,d призвана характеризовать силу связи между документом d и термом t. Очевидно, что частота вхождения терма в документ не является идеальной характеристикой, описывающей эту связь. На базе модели вероятностного латентного семантического индексирования возможно построение более реалистичных оценок силы связи документа d и терма t
T(d) - словарь документа d (множество различных термов, встречающихся в документе /), Z - латентный фактор,
P{z) - вес фактора z (вероятность того, что случайно выбранный документ из данной коллекции лучше всего характеризуется фактором г), P{t\z) - сила связи термина t с фактором z (вероятность того, что для данного фактора z для термина t этот фактор z наилучшим образом характеризует термин t), P(d\z) - сила связи документа d с фактором z (вероятность того, что для данного фактора г для документа d этот фактор г наилучшим образом характеризует документ d).
Покажем, что функцию fplsit d можно рассматривать как некоторую аппроксимацию функции ft)d, которая, как будет продемонстрировано в экспериментах, лучше отражает силу связи между документом d и термом t.
Действительно, величина P(t,d) в рамках подхода, использованного при вероятностном латентном семантическом индексировании, рассматривается как оценка вероятности совместного появления документа d и терма /. В связи с тем, что
Итак, в данной работе предполагается выполнить сравнение двух методов оценки силы связи терма и документа -ft,d wfplsit,d, и выдать рекомендации для администратора индекса о выборе лучшего метода.
Результаты экспериментов
Эксперименты проводились с использованием индекса, содержащего ссылки на документы из трех областей: языки программирования, информационный поиск и музеи.
На первом этапе формировались описания этих трех областей, которые рассматривались как информационные потребности пользователя.
Был подготовлен архив запросов пользователя, содержащий несколько десятков запросов, затрагивающих все три темы коллекции. Затем был проведен поиск в коллекции для всех запросов из архива. Для поиска использовалась библиотека Open Muscat[103], запросы формировались в дистрибутивной форме.
Из документов, полученных в ответ на запрос, выбирались десять первых (или меньше, если в результате поиска было получено менее десяти документов), и для каждого из них методом вероятностного латентного семантического индексирования выделялись три темы (три фактора), наилучшим образом описывающие тематику данного документа. Для каждой темы формировалось ее описание - множество из десяти слов, наилучшим образом описывающих данную тему.
Далее была проведена кластеризация всего множества тем (их описаний) и полученные кластеры предлагались пользователю для просмотра. Каждый кластер задавался в виде взвешенного списка слов, упорядоченного по убыванию веса слова. Для удобства просмотра и сравнения кластеров в этот список включались только те слова, вес которых превышал некоторое пороговое значение.
Пользователь выбирал для каждой из интересующих его тем (языки программирования, информационный поиск и музеи) один кластер, наилучшим образом соответствующий данной теме. Взвешенный список слов, описывающий данный кластер, рассматривался далее как описание соответствующей темы.
На втором этапе выполнялся поиск по новому множеству запросов (77 запросов). С каждым из полученных документов сопоставлялись описания всех трех тем пользователя, и документу приписывалась тема пользователя, чье описание наилучшим образом соответствовало описанию документа. Выбранная тема сравнивалась с реальной тематикой документа, которая в данном эксперименте была заранее определена. Для каждого запроса вычислялась точность оценки тематики полученных документов - отношение числа документов, для которых приписанная тема пользователя и реальная тема совпадали, к общему числу полученных документов. Как интегральная оценка точности предлагаемого метода вычислялась средняя по всем запросам точность оценки тематики документа.
Цель экспериментов состояла в оптимальном выборе двух функций: функции близости sim(%i, ху) двух тем документов х,- и xj, используемой при кластеризации, и функции близости sim(x, d) документа d и темы пользователя х є x(U), используемой при оценке темы полученного документа.
Рассматривались три варианта для первой функции simmi„(xh ху), simmax{xh xj) и sitttprocfai, у), и ТРИ варианта для второй функции simmin{xd), simmax(xtd) и simprod{t,d).
Прежде всего выполнялся выбор функции близости тем, используемой при кластеризации. В данном случае выбор оказался однозначным, т.к. при использовании функций simmax(Xi, Xj) и simprod(xi, xj) результаты кластеризации, выполненной методом single-pass кластеризации, оказались столь плохими, что пользователь не мог выбрать кластеры, наилучшим образом соответствующие интересующим его темам (информационный поиск, языки программирования и музеи). В описание каждого кластера вошли термы, характеризующие различные темы, в связи с чем выбор наиболее подходящих кластеров оказался невозможен.
При использовании на этапе кластеризации функции simmi„(x ху) были получены кластеры, по описанию которых удалось легко выделить наиболее предпочтительны кластеры для каждой из тем пользователя. Всего были выбраны 3 кластера (по числу тем пользователя), и их описания далее рассматривались как описания соответствующих тем.
Далее рассматривались все три варианта функции близости описания теше мы пользователя и описания документа. При этом размер описания темы пользователя был выбран фиксированным - 100 наиболее тяжелых термов, а размер описания документа варьировался.
Результаты представлены в таблицах 4.1, 4.2 и 4.3. и рис. 4.3.
Итак, результаты экспериментов показывают, что предложенный метод оценивания тем документов в терминах тем, заданных пользователем, обеспечивает достаточно высокую точность. В качестве функции близости для оценки близости тем и близости темы и документа следует использовать сумму минимумов весов общих слов.
