close

Вход

Забыли?

вход по аккаунту

?

9831.Агенты и их использование для поиска информации в сети Интернет

код для вставкиСкачать
Материалы Международной конференции
Интеллектуальные САПР”
“
УДК 518.5
А.Н. Целых, Р.В. Павленко
АГЕНТЫ И ИХ ИСПОЛЬЗОВАНИЕ ДЛЯ ПОИСКА ИНФОРМАЦИИ В
СЕТИ ИНТЕРНЕТ
Агенты и мультиагентные (МА) системы являются новым направлением в
вычислительных науках, которое берет свое начало в исследованиях искусственного интеллекта. В этой связи терминология в данной области еще не полностью устоялось, разные исследователи дают отличающиеся друг от друга определения понятия «агент». Но все же дадим этому понятию некоторое определение:
Агент - это адаптивная программная компонента, обладающая способностью
к самостоятельному принятию решений и проведению автономных действий, направленных на достижение цели, соответствующей интересам пользователя. Общей целью агента является представление и обслуживание интересов пользователя
в сложной информационной среде (в данном случаи поиск интересующей пользователя информации - релевантных документов в среде WWW).
Рассмотрим МА систему, основной составляющей которой являются агенты.
Агент является автономной программной компонентой, которая самостоятельно
определяет свои действия. МА идея заключается в том, что решаемая задача разбивается на подзадачи и решение этой задачи предоставляется отдельному агенту,
а суммой действий всех агентов достигается решение общей задачи. Эта особенность позволяет сделать вывод о высокой эффективности мультиагентных архитектур к построению информационных систем, ориентированных на работу в
сложных распределенных глобальных информационных средах, таких, как гипертекстовая среда InterNet.
Основной задачей, на решение которой направлены разрабатываемые модели
мультиагентной ПС, является обеспечения эффективного интеллектуального поиска релевантных документов в сложной гипертекстовой среде. Возможны и иные
виды агентов: торговые агенты, которые проводят сравнительный анализ магазинов электронной торговли с целью заключения наиболее выгодной сделки; агенты
сетевого управления, которые отыскивают ошибки в сети и проводят предварительно определенные мероприятия по их устранению, например, перезагружая
сервер; обучающие системы, в которых агенты могут отвечать на вопросы и вести
обучение, используя системы виртуальной реальности. Но вернемся к основной
задачи агентов. В отличие от существующих систем, которые для составления универсального индекса должны сканировать гипертекстовую среду WWW во всем ее
объеме, персональная МА ПС производит поиск HTML-документов с учетом конкретного запроса пользователя (хозяина). Факт известности запроса на момент
просмотра гипертекстовой среды позволяет поиск сделать интеллектуальным, нацеленным только на извлечение необходимой информации. Это позволяет сузить
поиск по сравнению с затраченным по времени и сетевыми ресурсами исчерпывающий просмотр документов. Является актуальным разработка алгоритма в котором, информационное содержимое HTML-документов, просматриваемых в текущий момент, используется для принятия решения о направлении поиска в последующие моменты времени. Возможность управлением поиском релевантных документов на основе информационного содержимого документов заложена в самом
принципе организации среды WWW. С этой связи можно сформулировать два допущения об организации гипертекстовых сред:
23
Известия ТРТУ
Тематический выпуск
Связь гиперссылками документов схожего содержимого.
Наличие связи между контекстом HTML-документа, в котором находится
гиперссылка, и содержимым документа, адресуемого данной гиперссылкой.
Данные утверждения очевидны, а именно, второе очевидно, т.к. создатели
Web-страниц, как правило, помещают рядом с гиперссылкой текст, поясняющий,
какая информация стоит за данной гиперссылкой. Первое допущение отражает тот
факт, что люди, создающие HTML-документы WWW, помещают в них гиперссылки на другие документы, в той или иной степени относящиеся к создаваемым документам. Связанные гиперссылкой документы могут относиться друг к другу в
различных аспектах, которые могут и не быть связаны с предметом производимого
поиска. Тем не менее, очевидно, что в общем случае, степень релевантности документов, связанных гиперссылками, должна быть высокой.
Указанные свойства WWW-среды обосновывают возможность построения
алгоритмов, интеллектуально повышающих эффективность поиска на основе анализа содержимого HTML-документов. Первое утверждение позволяет говорить о
том, что богатые требуемой информацией документы имеют тенденцию ссылаться
друг на друга, формируя области богатые релевантными документами.
Второе допущение обосновывает возможность прогнозирования и выбора гиперссылок, указывающих на релевантные документы. Прогнозирование полезности гиперссылок может быть сделано на основе анализа ее контекста. Эти допущения о статистических свойствах, присущих организации WWW, служат основой
эффективности предлагаемого алгоритма мультиагентного поиска.
Для разработки мультиагентной ПС возможно использование различных методов. Известен метод коллаборативной фильтрации, подразумевающий выдачу
рекомендаций, подготовленных на основе сведений о пристрастиях какого-то сообщества пользователей или индивидуальных пользователей. Согласно этой технологии, пользователям предлагается составить рейтинг, например, дюжины
фильмов, и агент коллаборативной фильтрации рекомендует конкретному пользователю фильмы, сравнивая его предпочтения со вкусами его единомышленников.
Алгоритмы коллаборативной фильтрации могут незаметно для пользователя дополняться другими методами.
Одна из проблем данной технологии - трудности, связанные с хранением информации о пользовательских предпочтениях. Если бы при перемещениях с узла
на узел пользователям удавалось сохранять личные сетевые атрибуты, то можно
было бы, например, учесть литературные пристрастия человека, обратившегося на
Web-узел, посвященный кинофильмам. К числу самых серьезных проблем, касающихся обработки личной информации на Web-узлах, относится проблема конфиденциальности. Очевидно, неограниченный доступ поставщиков к данным о предпочтениях любителей странствовать по Web чреват тем, что последние будут получать массу ненужных почтовых сообщений, возможны и более тяжелые последствия. Так же существует метод основанный на нейронных сетях. Этот метод заключается в том, что информационная среда WWW может быть рассмотрена как
аналог природной биологической экосистемы, в которой находится популяция
особей - агентов, «питающихся» информацией. Таким образом, в электронной среде WWW в роли энергоресурса - «пищи» для электронных существ, выступает информация, структурными единицами которой являются отдельные HTMLдокументы. Собственная энергетическая ценность HTML-документа определяется
на основе степени релевантности извлеченного документа.
Релевантные документы имеют положительную энергию. Энергия нерелевантных документов приравнена к нулю. Аналогично биологическим организмам,
3.
4.
24
Материалы Международной конференции
Интеллектуальные САПР”
“
агенты, энергия которых истощается, т.е. становится меньшей или равной нулю,
«погибают» - устраняются из памяти компьютера и рабочей популяции. Агенты,
энергия которых превышает некоторый уровень, дают потомство - помещают в
популяцию свою копию.
Возможен и другой подход, основанный на теории нечетких графов, документы отбираются по весу ребер нечеткого графа, т.е. в этом графе документы
представлены в виде вершин графа, которые связаны между собой ребрами (гиперссылками) с определенными весами. Данные веса варьируют от 0,5 до 1 и присваиваются ребрам в зависимости от того, на сколько этот документ релевантен. Данная релевантность определяется из контекста HTML-документа и, если она меньше
0,5, то дальнейший поиск в этом направлении не имеет смысла.
Перечислим некоторые преимущества МА-систем:
1. Высокая распределенность и параллельность вычислений - составляющие
МА-систему агенты могут одновременно выполняться на многих компьютерах,
территориально расположенных вдали друг от друга, осуществляя коммуникацию
через обмен сообщениями по сети. Это позволяет эффективно использовать вычислительные ресурсы сети, какой бы она не была локальной, городского масштаба или глобальной.
2. Высокая децентрализованность - работа МА-систем может происходить
без централизованного управления. Агенты просто выполняют собственные задачи, например, такие как: кооперация для достижения пересекающихся целей, коммуникация в целях координации планов действий или обмена взаимополезной информацией о системе. Поскольку глобальная цель МА-системы вытекает из целей
отдельных агентов ее достижение происходит автоматически в процессе работы
агентов, и существование центра, ответственного за всю систему в целом, необязательно, хотя и возможно. Фактически, каждый агент, в силу присущей ему самостоятельной активности, является некоторым центром управления распределенной
МА-системы.
3. Высокая надежность - архитектура МА-систем позволяет строить системы,
качество работы которых устойчиво по отношению к успешности функционирования отдельных агентов. Если один агент не может достичь цели или был уничтожен вследствие каких-либо причин, его задачи могут быть решены другими агентами. Такое становится возможным вследствие присущей агентам гибкости в реализации собственного поведения, которое может варьироваться в широких пределах. Другой способ обеспечения высокой надежности предоставляется «мобильными» агентами - агентами, способными к самостоятельному перемещению между
компьютерами сети. Мобильные агенты позволят перераспределять вычисления
между компьютерами сети в случаи отказов отдельных машин или каналов связи.
В случаи сигналов, свидетельствующих об отказе оборудования, агент просто записывает внутреннее состояние и вместе с машинно-независимым кодом переносит его на другой компьютер сети, где он продолжает свою работу.
Таким образом, разработка МА-систем является актуальным, т.к. у нее есть
множество преимуществ перед классическими ПС.
Разработка моделей гипертекстовой среды. Модели гипертекстовых информационных сред необходимы для тестирования и исследования эффективности
алгоритмов мультиагентного поиска. Агенты и мультиагентные системы являются
новым направлением в вычислительных науках, которое берет свое начало в исследованиях искусственного интеллекта. Основной составляющей мультиагентной
системы являются агенты. Агент является автономной программной компонентой,
которая самостоятельно определяет свои действия. Основной задачей, на решение
25
Известия ТРТУ
Тематический выпуск
которой направлены разрабатываемые модели мультиагентной ПС, является обеспечения эффективного интеллектуального поиска релевантных документов в
сложной гипертекстовой среде.
Рассмотрим графовое представление гипертекстовой среды. Обозначим через
Н граф, характеризующий гипертекстовую коллекцию документов. Граф Н задается множеством вершин D и множеством ребер L, обозначающих документы коллекции и гиперссылки между документами соответственно. Таким образом, моделирующий гипертекстовую среду граф Н задается как:
H=(D,L).
Отдельную гиперссылку будем обозначать как l, отдельный документ обозначим символом d. Гиперссылка lij, расположенная на документе di и указывающая
на документ dj, задается парой вершин (di,dj), определяющей ребро на графе Н, т.е.
l = (di, dj) ∈ L
Множество D документов коллекции разбивается на непересекающиеся подмножества документов, релевантных и нерелевантных по отношению к запросу
пользователя:
D =R UI ,
который в дальнейшем будем обозначать символом Q, где R - подмножество релевантных документов в коллекции; I — подмножество нерелевантных документов в
коллекции.
При этом
R II =0
Степень релевантности отдельного документа di обозначим как ri. Значение ri
определяется функцией релевантности р:
ri = p( d i , Q ) .
Функция релевантности может вычисляться двумя способами: автоматически
или на основе оценок пользователя.
Поскольку запрос Q для всех документов одинаков и остается постоянным на
время отработки моделями цикла поиска, в этом выражении символ Q будет опущен. Введем понятие порог релевантности г0, т.е. условие принадлежности документа di к множествам релевантных и нерелевантных документов, которые определяются следующим образом:
d i ∈ R , m.e.ri = p( d i ) >= r0
d i ∈ I , m.e.ri = p( d i ) < r0 .
Общее количество документов N моделируемой коллекции (размер коллекции) равняется мощности множества вершин графа D:
N =D.
Общее число релевантных документов в коллекции обозначим символом Nr,
нерелевантных - Nir:
26
Материалы Международной конференции
Интеллектуальные САПР”
“
Nr = R
Nir = I .
Доля R релевантных документов в общем числе документов коллекции N
равна:
R = Nr N .
Введем параметр Т, определяющий наличие и степень выраженности в гипертекстовой среде второго допущения: наличие связи между контекстом HTMLдокумента, в котором находится гиперссылка, и содержимым документа, адресуемого данной гиперссылкой. Его математическое определение зависит от вида
функции степени релевантности р, применяемой в модели. Степень релевантности
документов принимает значения из интервала [0,1], соответствующие степени релевантности документа. В этом случае Т определяется следующей формулой:
T = [Y ( l ij ) = p( d j ), d j ∈ D, lij ∈ L ] , формула − 1
где Y(lij) - оценка гиперссылки, даваемая агентом оценка релевантности документа
dj, на который указывает гиперссылка lij на основе контекста последней в тексте
базового документа di.
Таким образом, величина Т, определяет оценку совпадения релевантности
документа по контексту адресующей его гиперссылки с истинной релевантности
документа. Другими словами, Т задает возможность прогнозирования релевантности документов по адресующим документы гиперссылкам.
Алгоритм поиска и агенты не вычисляют функции p(d), Y(l), но пользуются
готовыми их значениями для осуществления поиска и анализа его эффективности.
Механизм, который обеспечивает эффективность поиска в данной модели, является перенос популяции агентов в область среды, богатой релевантными документами. В этой модели используется также и первое допущение о статистических свойствах организации гиперссылок в WWW – связь гиперссылками документов схожего содержимого.
Данная модель гипертекста состоит из введенного ранее графа Н, задающего
коллекцию документов D и множество гиперссылок L. Входные параметры данной
модели это: N - Общее число документов в коллекции; Т - степень релевантности
документа, определяемая формулой 1.
Набор этих параметров позволяет сгенерировать графовую модель гипертекста, основываясь на следующем алгоритме:
3.
Создать список вершин D графа Н, содержащий N элементов.
4.
Создать для каждой вершины di список гиперссылок документа Li.
5.
Определить веса ребер (гиперссылок) каждой вершины графа (документов) di
(1=1,... ,N) на основании степени релевантности документа di.
Таким образом, с помощью этого алгоритма мы получим модель гипертекстовой среды для эффективного поиска релевантной информации агентами в
WWW среде.
1.
ЛИТЕРАТУРА
SRI обеспечивают гибкость».
Дебора де Во «Распределенные агенты
Infoworld USA.
Computerworld №4, 1997.
2. Кононенко Р.Н. «Разработка методов и алгоритмов мультиагентного поиска релевантной
информации в информационных средах гипертекстовой организации»
//Дисс.канд.техн.наук, 1999.
27
Документ
Категория
Без категории
Просмотров
10
Размер файла
125 Кб
Теги
агенту, использование, сети, поиск, информация, 9831, интернет
1/--страниц
Пожаловаться на содержимое документа