Вестник Брянского государственного технического университета. 2011. №2(30)

Вид материала

Документы

Содержание Математическая модель описания агента метапоиска Op – множество описаний операндов, используемых в рассматриваемой операции; UI Математическая модель поиска документов SE – описание внешней ИПС в качестве внешнего агента поиска; SPh Q – множество передаваемых запросов; F

Подобный материал:

• Вестник Брянского государственного технического университета. 2011. №4(32), 114.16kb.
• Вестник Брянского государственного технического университета. 2011. №3(31), 389.65kb.
• Вестник Брянского государственного технического университета. 2011. №3(31), 141.24kb.
• Вестник Брянского государственного технического университета. 2011. №2(30), 81.9kb.
• Вестник Брянского государственного технического университета. 2010. №2(26), 83.85kb.
• Вестник Брянского государственного технического университета. 2008. №1(17), 121.05kb.
• Вестник Брянского государственного технического университета. 2008. №3(19), 168.61kb.
• Вестник Брянского государственного технического университета. 2008. №3(19), 138.83kb.
• Вестник Брянского государственного технического университета. 2008. №3(19), 114.86kb.
• Вестник Брянского государственного технического университета. 2011. №2(30), 213.37kb.

УДК 004.021


В.И. Аверченков, Е.А. Леонов


Математическая модель универсальной многоагентной подсистемы метапоиска¹


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


Ключевые слова: метапоиск, мультиагентное моделирование, мониторинг информации, автоматизация по­иска.


При построении интеллектуальных систем мониторинга и анализа информации важным этапом является сбор и накопление данных из сети Интернет [2]. Особенно актуальным это становится при наполнении предметно-ориентированных хранилищ документов с использованием подсистем метапоиска. Они позволяют обеспечить высокую точность выборки документов, отвечающих целям формирования коллекции, при допустимых вычислительных ресурсах и пропускной способности канала связи [1].

К
Рис. 1. Классическая структура подсистемы метапоиска
лассическим подходом при реализации процесса взаимодействия с информационно-поисковыми системами (ИПС) является создание и использование уникального модуля для каждой ИПС (рис. 1), с которой взаимодействует подсистема [5;6]. Такой подход обеспечивает высокую интеграцию и значительные возможности по конфигурированию параметров поиска. Однако он имеет ряд существенных недостатков: отсутствие быстрой адаптивной подстройки под динамично изменяющиеся форматы входных и выходных данных и изменение возможностей используемых систем; невозможность изменения списка используемых систем, так как при добавлении новой ИПС требуется разработка дополнительных модулей системы. Для устранения данных недостатков многие подсистемы применяют универсальный подход в работе с различными ИПС [4]. Однако, как правило, при разработке универсального подхода используется лишь один параметр для передачи ИПС поисковой фразы, причем без учета уникальности синтаксиса в каждой ИПС, что приводит к снижению достоинств данного подхода. Существует значительное количество работ, в которых сочетаются указанные подходы, но рассмотрение проблем носит частный характер, т.е. решаются отдельные проблемы, возникающие при взаимодействии с ИПС, такие, как выборка произвольного количества результатов, использование универсального транслятора языка запроса и некоторые другие[3;7].

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



Рис. 2. Предлагаемая схема взаимодействия с внешними ИПС

Ключевым этапом в работе с внешними ИПС является подключение их в систему в виде внешних агентов поиска (инициализации). Данный этап представляется в виде функции, алгоритм работы которой базируется на математических моделях описания внутреннего агента взаимодействия и описании внешней ИПС. В основе данного алгоритма лежит принцип анализа и последующего синтеза отдельных функциональных возможностей ИПС. При этом каждая внешняя ИПС представляется как система, имеющая набор функциональных возможностей, представленных для внешнего пользователя как набор управляемых параметров. Полный набор этих функциональных возможностей представляет полный набор параметров, которые могут быть переданы ИПС. Таким образом, ИПС представлена как мультимножество функциональных возможностей со связанным множеством входных параметров. Все рассматриваемые в работе модели строятся на теории множеств и мультимножеств [9], общей теории управления, теории построения мультиагентных систем [8].

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

Описание агента метапоиска было предложено представлять в виде множества

,

где L_in – описание внутреннего языка запросов; F – множество функциональных возможностей агента доступных пользователю для взаимодействия с внешней ИПС.

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

,

где – идентификатор операции, используемый в системе для трансляции языков; _min – маска, на основе которой составляется регулярное выражение для поиска операции (используется при разборе выражения, написанного на внутреннем языке, и сборке выражения по дереву операций; также маска операции используется для удобного описания синтаксиса операции и представляет собой строку с примером записи операции); pri_in– приоритет во множестве операций, определяющий порядок поиска операций в выражении (); Op – множество описаний операндов, используемых в рассматриваемой операции; UI – множество, содержащее элементы, описывающие интерфейсное представление операции для пользователя, такие, как визуальное представление операции в выражении, шаблон для вставки операции при редактировании выражения и параметры автоматического формирования интерфейса редактора выражений.

Описание операндов для операции является кортежем

,

где T_op – тип операнда; B_op – предикат прерывания ветвления дерева операций, который определяет, может ли операнд содержать внутри себя операции; N_op – порядковый номер операнда в операции, определяющий отношение между маской операции и описанием операнда.

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

,

где I_F – множество уникальных идентификаторов функциональных возможностей; P_n – семейство множеств входных параметров, определенных на домене P и необходимых для обеспечения функциональной возможности агента; R_F – предикат необходимости функции для работоспособности системы в целом (); A_n – семейство множеств, описывающих конкретные алгоритмы, реализующие функциональную возможность агента взаимодействия с внешними ИПС.

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

 – это кортеж множеств идентификаторов параметров i_h, идентификаторов типов параметров i­_T, используемых в реализации алгоритма при взаимодействии с внешней ИПС. Данное множество определено на домене P_hin, которым является множество, содержащее параметры, используемые во всех алгоритмах , т.е. множество всех аналогичных параметров, используемых в системе.

Значимым описанием алгоритма является также описание типов данных параметров, необходимое для корректного подбора алгоритма.

Типы данных параметров представляются в виде

,

где i_T – идентификатор типа параметра; G_T – область определения значения для типа данных. Это выражение представляет собой множество возможных значений параметра. Для упрощения записи множеств они были разделены на несколько возможных описаний по свойствам их перечисляемости и доменов.

Определим набор множеств, на которых может быть определен тип параметра:

• диапазон целых чисел ;
  
• диапазон рациональных чисел ;
  
• перечисляемый тип ;
  
• константа .
  

Тогда определение идентификатора типа для параметра можно показать в виде системы

.

Алгоритм сам не реализует функциональную возможность, он лишь делегирует исполнение внешней поисковой системе через систему запросов и, таким образом, служит для отображения множества параметров пользователя на множестве параметров внешней ИПС: . Для каждой функции идентификатор является уникальным, ; для каждого идентификатора имеется связанное семейство параметров, при этом каждое множество семейства также уникально, .

Определим P как домен семейства параметров, образующего единое множество с уникальным набором параметров, описанных в системе и доступных для установки пользователем: . Каждый элемент множества параметров является элементарным кортежем вида , где i_p – уникальный идентификатор параметра, необходимый для точной идентификации и сравнения параметров ; i_T – уникальный идентификатор типа параметра; v – значение параметра до выполнения функции инициализации, которое является элементом множества значений по умолчанию, .

При создании структуры описания поисковых систем необходимо соблюдать высокую степень абстракции, для того чтобы обеспечить совместимость с наибольшим количеством внешних информационно-поисковых систем, а также легкую расширяемость функционала поискового агента для поддержки новых функций управления поисковыми системами [8].

Представим описание внешней ИПС как множество

,

где S_ex – множество описаний подсистем управления внешней ИПС (в качестве подсистемы понимается отдельный интерфейс управления);  – особенности работы с системой, N_FSE – имя (назначение) особенности системы, V_FSE – значение особенности системы.

Опишем также множество подсистем управления , где n – количество подсистем [8]. Каждая подсистема управления может совмещать в себе функции поиска, а также быть отдельным настроечным интерфейсом, результатом работы которого является либо файл cookies, идентифицирующий пользователя, либо идентификатор сессии пользователя на сервере. Описание каждой подсистемы управления является составным множеством

,

где P_re – правила разбора ответа от подсистемы (представляют собой набор регулярных выражений; если подсистема предназначена только для управления, то данное множество вырождено); P_hex – множество всех параметров, которые могут быть переданы подсистеме управления; T_ex – множество типов параметров; L_ex – описание языка поисковых фраз, интерпретируемых подсистемой управления.



Рис. 3. Схема создания экземпляра агента и его работы

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

,

где i_h – идентификатор параметра, определяющий его назначение (должен быть уникальным и определенным на домене идентификаторов параметров внутреннего агента метапоиска); i_T – идентификатор типа параметра (, где T_ex - множество типов параметров, уникальных для данной подсистемы управления); n – символьное имя параметра в описываемой подсистеме управления; v – значение параметра; m – метод передачи параметра.

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

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

Общий вид функции настройки можно представить следующим образом:

,

где SE_in – описание возможностей агента метапоиска; SE_ex – полное описание всех функций внешней ИПС; P_us – набор установок пользователя, содержащий связанные пары , P_u – параметры поиска (), R_us – предикат, определяющий обязательность исполнения заданного параметра поисковой системой (); H_us – описание настроек соединения по протоколу HTTP (данные настройки без изменений вносятся в описание поисковой системы, что обусловлено необходимостью уникальной имитации пользователя для каждой ПС в отдельности).

SE – измененное и ограниченное описание внешней ИПС с учетом возможностей внутренней ИПС и заданными параметрами поиска.

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

На первом этапе необходимо определить доступное множество типов параметров, передаваемых внешним ИПС. Общее множество типов можно найти объединением множеств, но так как элементы этих множеств не являются простыми атомарными единицами, то для начала определим бинарную функцию их равенства:

.

Таким образом, можем найти пересечение типов параметров агента взаимодействия и расширение множества типов, содержащегося в описании внешней ИПС:

.

Множество доступных типов позволяет найти множество параметров, доступных для использования при работе с внешней ИПС. Определим множество доступных параметров в виде

.

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



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

Зная множество доступных параметров, можем определить доступные для использования алгоритмы, содержащиеся в агенте взаимодействия:

.

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

.

Проведем усечение данного множества алгоритмов для однозначного сопоставления одной функциональной возможности одному алгоритму. Для этого сопоставим каждой доступной функциональной возможности только один алгоритм с наивысшим приоритетом. Конечное множество алгоритмов имеет вид

.

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

.

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

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

,

где S – множество подсистем, доступных для управления.

, при этом состав каждой подсистемы управления определяется множеством .

Составные элементы данных множеств подробно разъясняются в математической модели описания внешней ИПС и выводятся из контекста работы функции настройки.

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

,

где SE – описание внешней ИПС в качестве внешнего агента поиска; SPh – поисковое выражение, написанное на внутреннем языке системы (L_in); D_mi – упорядоченное множество элементарных кортежей с метаинформацией о найденных документах, .

При этом метаинформация о каждом документе имеет вид

,

где r – релевантность документа в ИПС относительно поискового выражения; u – URL адрес документа; dt – дата последнего изменения документа; s – ориентировочный размер документа; o – цитата документа, предоставляемая ИПС пользователю.

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

Таким образом, поисковое выражение является значением лишь одного из параметров, а передаваемые параметры в зависимости от метода передачи могут содержаться либо в начальной строке запроса (URI), либо в завершающем блоке запроса (Entity-Body), причем эти два блока являются частью параметров протокола HTTP.

При создании строки Request-Line и Entity-Body множество функций агента метапоиска, доступных для использования, позволяют осуществить трансляцию всех пользовательских параметров в параметры внешней поисковой системы. При этом каждой функции агента метапоиска при усечении описания ИПС был сопоставлен один конкретный алгоритм с точным определением необходимых для использования параметров внешней ИПС. Определим произвольную функцию агента метапоиска в следующем виде:

,

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

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

Также распишем более подробно состав каждого кортежа и определим мощности полученных множеств: .

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

Таким образом, одна функция f_i оперирует на одном подмножестве имен параметров, но для реализации заявленных требований пользователя может понадобиться выполнение нескольких запросов с различными комбинациями значений. Кортежи, возвращаемые одной функцией, определены на одном пространстве имен и не могут быть переданы ИПС в одном запросе, потому что каждая ИПС принимает только одно значение для каждого параметра в рамках одного запроса. Необходимо определить множество всех комбинаций запросов, которые необходимо выполнить, чтобы полностью удовлетворить все установки пользователя. Для этого можно использовать прямое произведение кортежей [9], получаемых от всех функций агента метапоиска:

.

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

.

Каждый элемент полученного кортежа представляет собой семейство непересекающихся множеств, являющихся подмножеством параметров внешней ИПС:

.

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

.

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

Далее составляем строки запросов

,

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

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

Заключительным этапом получения информации о найденных документах, заданной внешней ИПС, является посылка запросов и разбор полученных результатов [5]. Для этого в агенте метапоиска реализована универсальная функция передачи данных. В качестве передаваемых данных выступает множество составленных запросов к подсистемам управления внешними ИПС (рис. 3). Функция получения метаинформации о найденных документах имеет следующий вид:

,

где Q – множество передаваемых запросов; F_SE – особенности внешней информационно-поисковой системы; P_re – набор регулярных выражений для разбора результатов, полученных от внешней ИПС; D_mi – упорядоченное множество элементарных кортежей с метаинформацией о найденных документах.

Конечным этапом является объединение всех подмножеств от каждого запроса в единое множество и сохранение промежуточных результатов в области данных агента метапоиска [3].

Разработанные математические модели взаимодействия с внешними ИПС являются универсальными для любого типа информационно-поисковых систем. В качестве внешней ИПС могут быть использованы ресурсы следующих типов: универсальные глобальные информационно-поисковые системы (Google, Yandex, Bing, Yahoo, Rambler, Mail и др.); сервисы поиска на отдельных ресурсах (wiki, форумы, каталоги); автоматические системы поиска, имеющие программные интерфейсы взаимодействия. Также нет практически никаких ограничений на используемые веб-технологии для передачи данных (HTML, XML, JSON и пр.).

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

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

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


Список литературы

1. 
   Аверченков, В.И. Система формирования знаний в среде Интернет: монография/ В.И. Аверченков, А.В. Заболеева-Зотова, Ю.М. Казаков, Е. А. Леонов, С.М. Рощин. – Брянск: БГТУ, 2008. -181 с.
   
2. Аверченков, А.В. Разработка автоматизированной системы мониторинга и анализа распределенной информации в сети Интернет на основе мультиагентной стратегии/ А.В. Аверченков, Е.А. Леонов, Д.В. Кравцов// Известия ОрелГТУ. Серия «Фундаментальные и прикладные проблемы техники и технологии: информационные системы и технологии». - 2008. - №1. - С. 127-133.
   
3. Браславский, П.И. Подходы к построению и реализация специализированной метапоисковой машины ProThes/ П.И. Браславский, А.С. Шишкин// Вычислительные технологии. Т. 10. Труды IX Рабочего совещания по электронным публикациям (El-Pub2004). - Новосибирск, 2005. - C. 49-57.
   
4. Ландэ, Д.В. Метапоиск доступных научно-технических документов в Интернете / Д.В. Ландэ, А.А. Снарский, В.В. Жигало// Труды 12-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» RCDL'2010. – Казань, 2010. – C. 321-325.
   
5. Singitham, P. A Meta search engine and Evaluation of ranking strategies/ P. Singitham, M.S. Mahabhashyam. - Stanford University, 2010. - Режим доступа: www.stanford.edu/class/cs276a/projects/reports/mmahathi-pavan.doc
   
6. Козлов, Е.Б. Мультиагентная система поиска информации в Интернет/ Е.Б. Козлов, А.В. Метелкин, В.Ф. Хорошевский// Труды Седьмой национальной конференции по искусственному интеллекту с международным участием КИИ’2000. – М.: Физматлит. - С. 840–850.
   
7. Meng, W. Building efficient and effective metasearch engines/ W. Meng, C. Yu, K.L. Liu// ACM Comput. Surv. – 2002. – V. 34. - № 1. – С. 48-89.
   
8. Тарасов, В.Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте/ В.Б. Тарасов// Новости искусственного интеллекта. – 1998. – №2.– С. 5-63.
   
9. Петровский, А.Б. Пространства множеств и мультимножеств/ А.Б. Петровский. - М.: Едиториал УРСС, 2003. – 248 с.
   

Материал поступил в редколлегию 28.04.11.