Размещено на http://www.allbest.ru/

Пермский филиал федерального государственного автономного образовательного учреждения высшего образования

«Национальный исследовательский университет

«Высшая школа экономики»

Факультет экономики, менеджмента и бизнес-информатики

Проектирование агента, реализующего алгоритмы text mining, для моделирования социальных сетей

Выпускная квалификационная работа

по направлению подготовки 38.04.05 «Бизнес-информатика»

образовательная программа

«Информационная аналитика в управлении предприятием»

Кобцева Светлана Евгеньевна

Пермь, 2019 год



Аннотация

Выпускная квалификационная работа на тему «Проектирование агента, реализующего алгоритмы Text Mining, для моделирования социальных сетей»

Автор: Кобцева Светлана Евгеньевна

Факультет экономики, менеджмента и бизнес-информатики, группа ИАУП-17

Руководитель: Замятина Елена Борисовна

к.ф.-м.н., доцент, доцент кафедры информационных технологий в бизнесе НИУ ВШЭ - Пермь

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

Исследование выполнено на 69 листах с использованием 58 источников. Выпускная квалификационная работа содержит 1 таблицу и 7 рисунков.



Оглавление

Введение

Глава 1. Анализ методов и технологий проектирования агентов

1.1 Понятие агент

1.2 Проектирование агентов. Общие вопросы проектирования агентов и многоагентных систем

1.3 Требования к реализации мобильных агентных систем

1.4 Архитектура мультиагентных систем

1.5 Моделирование взаимодействия в мультиагентных системах

1.6 Координация поведения агентов в мультиагентной системе

Выводы по главе 1.

Глава 2. Анализ методов и технологий Text Mining и Social Mining

2.1 Понятие text mining

2.2 Методы и модели text mining

2.3 Понятие Social mining

2.4 Применение техник Text Mining для работы в социальных сетях

2.4.1 Предварительная обработка текста

2.4.2 Text Mining с использованием методов классификации

2.4.3 Text Mining с использованием кластеризации

Выводы по главе 2

Глава 3. Проектирование агента, реализующего алгоритмы text mining, для моделирования социальных сетей

3.1 Разработка требований к проектированию мультиагентной системы

3.2 Классификация тем

3.3 Проектирование архитектуры мультиагентной системы и функциональности агентов

3.4 Модель обнаружения фейковых новостей в социальной сети

Заключение

Список использованной литературы

Приложение А. Алгоритм для анализа и классификации новостей

агент проектирование text mining



Введение

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

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

Именно поэтому актуальной задачей сегодня является применение интеллектуального анализа текста (Text Mining). Как и большинство когнитивных технологий - Text Mining - это алгоритмическое выявление прежде не известных связей и корреляций в уже имеющихся текстовых данных. Важной задачей технологии Text Mining является извлечение из текста его характерных элементов или свойств, которые могут использоваться как метаданные документа, ключевых слов, аннотаций. Другая важная задача состоит в отнесении документа к некоторым категориям из заданной схемы их систематизации. Text Mining также обеспечивает новый уровень семантического поиска документов.

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

В настоящее время такого рода агенты широко используют в сетевом анализе (SNA - Social Networks Analyses), который предполагает извлечение информации из виртуальных социальных сетей, в том числе, и с помощью программных агентов, изучение структурных характеристик социальных сетей и выработку определенных стратегий, связанных, в частности, с распространением информации в социальных сетях. Однако сетевой анализ не всегда дает возможность выявить закономерности, причинно-следственные связи, которые способствуют возникновению того или иного события, в том числе, и событий, которые оказывают значительное влияние на пользователей социальной сети и их поведение. Выявление причинно-следственных связей возможно при изучении виртуальных социальных сетей в динамике. Для изучения изменений характеристик социальных сетей с течением времени используют метод имитационного моделирования [38]. Роль виртуальных социальных сетей в этом случае выполняют случайные графы особой топологии (модель Эрдеши-Реньи и т.д.) [16]. Анализ социальных сетей и поведения их пользователей выполняют системы имитационного моделирования. Однако зачастую актуально использовать для исследований и выполнения предсказательного моделирования не модели социальных сетей в виде случайных графов, а реальные социальные сети. Для сбора информации о реальной социальной сети, об ее структурных характеристиках, следует разработать специальное программное обеспечение.

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

Если рассматривать применение агентных технологий при моделировании социальных сетей, стоит отметить работу бразильской исследовательницы Марии Гатти. Авторы работы [38] попытались проанализировать распространение информации в эгоцентрической сети, имеющей уникальный узел в качестве источника. Исследование основано на стохастическом мультиагентном подходе, когда каждый агент формируется по определенным правилам с использованием данных, взятых в реальной социальной сети Twitter. Процесс моделирования состоит из шести фаз и является итерационным.

В данной работе Гатти предлагает метод имитационного моделирования поведения пользователей в социальной сети. Данные, взятые из Twitter, позволили построить отдельные стохастические модели, для представления поведения каждого пользователя при публикации сообщений, связанных с Бараком Обамой и его предвыборной кампанией 2012 года или другими темами. Эксперименты с двумя различными сценариями показали, что удаление ядра эгоцентрической сети (аккаунта Обамы) или самых активных пользователей влияет на объем сообщений, особенно если речь идет о теме, связанной с ядром. В тоже время удаление 100 самых активных пользователей оказывает больше влияния, чем само ядро. Эксперименты продемонстрировали, что предлагаемый подход является перспективным для моделирования поведения пользователей в социальной сети.

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

Основные задачи:

1) Сбор, анализ, систематизация специальной литературы по рассматриваемой области;

2) Проектирование агента, реализующего алгоритмы text mining для построения модели реальной социальной сети с целью ее использования в системе имитационного моделирования;

3) Разработка оригинального алгоритма для выявления фейковых новостей;

4) Тестирование работы агента с использованием программных средств RStudio.

Объект исследования - агент моделирования социальных сетей, предмет исследования - проектирование агента.

Методы, использованные при проектировании системы: методы машинного обучения, методы интеллектуального анализа текста (Text Mining), интеллектуальный анализ данных (Data Mining).

Инструменты, использованные при проектировании системы: RStudio, UML диаграммы, Python.

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

Стоит отметить, что по результатам исследований большая часть пользователей интернета регулярно сталкиваются с файковыми новостями в сети. Согласно масштабному опросу общественного мнения, проведенному по поручению Европейской Комиссии в странах-членах Европейского Союза и опубликованному в апреле 2018 года, 37% опрошенных сталкиваются с фальшивыми новостями каждый день [35]. 85% участников опроса из различных стран уверены, что фейковые новости являются проблемой для их страны, 83% респондентов полагают, что они представляют собой проблему для демократии в целом [35]. Также стоит отметить, что согласно ежегодным исследованиям британского медиарегулятора Ofcom большая часть граждан не могут отличить «фейковый» контент от «не-фейкового» [47].

Говоря об определении ложных новостей, стоит отметить уже существующие исследования в этой области. Отметим инструментальную панель «Hamilton 68» (http://dashboard.securingdemocracy.org), разработанную американской организацией The Alliance for Securing Democracy в целях информирования общественности о новостях, продвигаемых в США другими государствами в социальной сети Twitter.

Также к борьбе с ложным контентом присоединились такие крупные компании как Facebook, Youtube, Google. Например, Facebook использует такие средства оповещения пользователей как сообщения внутри социальной сети и рекламные объявления для того, чтобы информировать пользователей о том, как определить фейковый контент [29].

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

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



Глава 1. Анализ методов и технологий проектирования агентов

1.1 Понятие агент

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

Нас интересует понятие программного агента. В программировании агент - это некая сущность, система, которая обладает не только свойствами объекта (существовать и объединять), но и свойствами, необходимыми для взаимодействия с внешней средой. В компьютерных науках программный агент является программой, которая вступает в отношение посредничества с пользователем или другой программой. Такие «действия от имени» подразумевают право решать, какие действия (если они нужны) являются целесообразными [13, 27]. Согласно определению Фербера, агент - это реальная или виртуальная автономная сущность, которая работает во внешней среде, также, она способна воспринимать и действовать в этой среде. Агент может общаться с другими агентами и проявлять самостоятельность, выражающуюся в независимом поведение. Такое поведение может рассматриваться как результат его знаний, взаимодействия с другими агентами, а также целей, которых агент стремится достичь [36]. Идея агента состоит в том, что агенты проявляют активность самостоятельно, тогда, когда посчитают это нужным, а не запускаются непосредственно для решения задачи.

Агенты воспринимают внешнюю среду с помощью сенсоров. Воздействовать на внешнюю среду агенты могут с помощью эффекторов (актуаторов).

Говоря об агенте, стоит упомянуть близкую к нему концепцию «актора». Под актором подразумевается сущность, способную в ответ на полученное сообщение выполнить следующие действия [27]:

– Отправить конечное количество сообщений другим акторам;

– Создать конечное число новых акторов;

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

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

Родственные и производные понятия включают интеллектуальных агентов (в частности, обладают некоторыми аспектами искусственного интеллекта, такими как обучение и рассуждения), автономных агентов (могут менять способ достижения своих целей), распределенных агентов (действуют на различных компьютерах), многоагентные системы (распределенные агенты, которые не могут достигнуть цели по одному, из чего следует, что они должны общаться), и мобильных агентов (агентов, которые могут переместить свое выполнения на другие процессоры) [13].

Термин «агент» описывает программную абстракцию, идею или концепцию, подобно таким терминам объектно-ориентированного программирования как метод, функция или объект. Концепция агента помогает удобно и эффективно описать сложную программную сущность, способную действовать с определённой степенью автономности для выполнения задач от лица пользователя. Важно подчеркнуть, что агент, в отличии от объекта, определяется через описание его поведения [5].

Для агента характерны следующие свойства [10]:

– Автономность - способность функционировать без вмешательства со стороны своего владельца и осуществлять контроль внутреннего состояния своих действий;

– Социальное поведение - возможность взаимодействия и коммуникации с другими агентами;

– Реактивность - адекватное восприятие среды и соответствующие реакции на ее изменения;

– Активность - способность генерировать цели и действовать рациональным образом для их достижения;

– Базовые знания - знания агента о себе, окружающей среде, включая других агентов, которые не меняются в рамках жизненного цикла агента;

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

– Цели - совокупность состояний, на достижение которых направлено текущее поведение агента;

– Желания - состояния и/или ситуации, достижение которых для агента важно;

– Обязательства - задачи, которые берет на себя агент по просьбе и/или поручению других агентов;

– Намерения - то, что агент должен делать в силу своих обязательств и/или желаний.

Если говорить о классификации, то типология агентов связана с проблемой взаимодействия “субъект - объект”. Уровень субъектности агента зависит от того, наделен ли он символьными представлениями, требующимися для организации рассуждений, либо наоборот работает на субсимвольном уровне, то есть на уровне образов, связанных с сенсомоторной регуляцией [10]. Классификацию агентов можно выстроить, основываясь на степени развития внутреннего представления о внешнем мире. Тогда мы получаем два класса: интеллектуальные (когнитивные, рассудочные) и реактивные агенты.

Реактивные агенты обладают ограниченным представлением о внешнем мире, либо не имеют его вовсе. Реактивные агенты имеют слабую способность к планированию, это связано с тем, что реактивность означает такую структуру обратной связи, которая не содержит механизмы прогноза [10]. В основном такие агенты работают на уровне стимульно-реактивных связей. Стоит отметить, что они сильно зависят от внешней среды, в связи с чем они образуют сообщества агентов.

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

Когнитивные (интеллектуальные) агенты, в отличии от реактивных агентов, имеют богатое представление о внешнем мире. Это связано с тем, что интеллектуальные агенты обладают базами знаний и механизмами решений [18]. Благодаря своим прекрасно развитым внутренним представлениям о внешнем мире и возможностью рассуждать, они способны сохранять в памяти и проводить анализ различных ситуаций, прогнозировать возможные реакции на свое поведение, делать из этого полезные для дальнейшей деятельности выводы, и в целом планировать свое поведение. За счет своих интеллектуальных возможностей когнитивные агенты способны выстраивать виртуальные миры, где они могут формировать планы действий [18].

Интеллектуальные агенты имеют ярко выраженную индивидуальность, они более автономны, чем реактивные агенты, не зависят от внешней среды. Благодаря своей независимости и гибкому поведению, интеллектуальные агенты способны противиться внешним воздействиям, что вызывает трудности при организации взаимодействия нескольких таких агентов [10]. Именно поэтому в составе мультиагентных систем, состоящих из когнитивных агентов, присутствует примерно 5 - 10 единиц.

В таблице 1 представлен сравнительный анализ свойств когнитивных и реактивных агентов.

Таблица 1.1 Сравнительный анализ свойств когнитивных и реактивных агентов

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

Безусловно, программные агенты представляют собой инновационную технологию, которая может предложить много полезного для конечных пользователей благодаря автоматизации сложных или повторяющихся задач [18]. Стефен Хааг в своей работе [20] выделяет четыре основных типа интеллектуальных программных агентов:

– Агенты-покупатели или торговые боты;

– Пользовательские или персональные агенты;

– Агенты по мониторингу и наблюдению (предиктивные);

– Агенты по добыче и анализу данных.

Агенты-покупатели или роботы по закупкам просматривают ресурсы в сети Интернет для сбора информации о различных товарах и услугах.

Пользовательские агенты действуют от лица пользователя. Эти агенты могут заниматься следующими задачами:

– Проверка и сортировка электронной почты, оповещение о новых письмах;

– Активность в компьютерных играх от лица пользователя;

– Сбор отчетов новостей (прим. newshub и CNN);

– Поиск информации по определенным темам, запросам;

– Автоматическое заполнение веб-формы;

– Профилирование синхронизации разнородных социальных сетей.

Предиктивные агенты применяются для наблюдения за объектами и передачи информации на оборудование, обычно на компьютерные системы [27]. Агенты могут следить за уровнем запасов материалов компании, ценами конкурентов и доводить их до сведения компании, анализировать фондовые манипуляции и т.д.

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

Кроме того, стоит отметить такие примеры современных интеллектуальных агентов как некоторые спам-фильтры, игровые боты и средства мониторинга серверов, а также боты индексации поисковых систем.

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

Мобильный агент - это программа, которая может перемещаться по сети, самостоятельно выбирая время и место перемещения. При перемещении состояние мобильного агента запоминается и переносится в новую локацию, что позволяет продолжить работу агента [19]. Использование мобильных агентов воплощает идею удаленного программирования. То есть клиент создает процедуру, которая способна выполнить требуемую работу удаленно, после чего клиент передает данную процедуру для выполнения на сервере. Базовым свойством мобильного агента является его способность перемещаться из одной точки сети в другую, то есть агент не привязан к системе, на которой он был запущен и может перемещаться между различными системами [55]. Способность к перемещению дает мобильному агенту возможность попасть в систему адресат, содержащую объект, с которым агент должен взаимодействовать. Кроме того, агент способен воспользоваться сервисами системы адресата. Стоит отметить, что для существующих распределенных систем характерно ориентирование на коммуникационные нужды стационарных агентов, то есть они не отвечают требованиям и возможностям мобильных агентов [55].

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

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

Также, стоит отметить такое понятие, как мультиагентная система. Мультиагентная система - это сложная система, состоящая из нескольких взаимодействующих между собой агентов [52]. Мультиагентные системы могут быть использованы для решения проблем и задач, которые не могут быть решены силами одного агента. Примерами таких задач являются онлайн-торговля, ликвидация чрезвычайных ситуаций, моделирование социальных структур [45]. Для мультиагентной системы характерны автономность (агенты внутри системы хотя бы частично независимы), ограниченность представления (ни один агент не имеет представления о всей системе, либо система слишком сложна, чтобы знание о ней имело практическое применение для агента) и децентрализация (нет агентов, управляющих всех многоагентной системой) [52].

Обычно в рамках изучения многоагентных систем исследуются программные агенты внутри системы. Но элементами мультиагентной системы могут быть роботы, люди/группы людей [45]. Даже если поведение каждого отдельного агента довольно просто, в многоагентных системах может проявляться самоорганизация и сложное поведение. Это является основой так называемого роевого интеллекта. Также стоит отметить, что агенты могут общаться между собой и обмениваться своими знаниями с помощью специального языка и протоколов коммуникации.

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

1.2. Проектирование агентов. Общие вопросы проектирования агентов и многоагентных систем

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

Важно подчеркнуть, что в развитии концепции агентов и их последующего внедрения важную роль сыграла предыдущая разработка и освоение концепции открытых систем. Согласно определению, принятому Комитетом IEEE POSIX 1003.0 открытой информационной системой считается система, которая реализует открытые спецификации на интерфейсы, сервисы и поддерживаемые форматы данных, достаточные для того, чтобы дать возможность должным образом разработанному прикладному программному обеспечению быть переносимым в широком диапазоне систем с минимальными изменениями, взаимодействовать с другими приложениями на локальных и удалённых системах, и взаимодействовать с пользователями в стиле, который облегчает переход пользователей от системы к системе [41]. Основными свойствами открытых систем являются [41]:

– Расширяемость/масштабируемость (возможность изменения набора составляющих системы);

– Мобильность/переносимость (простота переноса программной системы на новые программно-аппаратные платформы);

– Интероперабельность (способность к взаимодействию с другими системами);

– Дружелюбность к пользователю/легкой управляемости.

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

Одним из важных последствий практического применения открытых систем стало широкое распространение клиент-серверной архитектуры. На сегодняшний день выделяют такие модели клиент-серверного взаимодействия как «Толстый клиент - тонкий сервер» (Серверная часть реализует только доступ к ресурсам, а основная часть приложения находится на клиенте) и «Тонкий клиент - толстый сервер» (клиентское приложение обеспечивает реализацию интерфейса, а сервер объединяет остальные части приложений).

При создании многоагентных систем чаще используют модель «тонкого клиента» [20]. Не зависимо от того, какая модель применяется, средства разработки и исполнения многоагентных систем опираются на статический подход, т.е. позволяют передать только данные приложений, или динамический подход (есть возможность передать исполняемый код).

1.3 Требования к реализации мобильных агентных систем

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

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

Для передачи сообщений между агентами или между агентом и пользователем существуют посредники [55].

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

Когда агент оказывается на новом сервере, его данные и код переносятся в новый контекст, при этом на предыдущем сервере его данные стираются, после переноса данных агент может выполнять на сервере все, что не запрещается новым контекстом [55].

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

Стоит отметить, что сейчас не существует языка программирования или инструментальной системы разработки, которая бы полностью отвечала нуждам построения агентов. Такая система должна была бы отвечать таким требованиям: обеспечение перенесения кода на разные платформы, доступность на многих платформах, поддержка сетевого взаимодействия, многопоточная обработка и другие [55]. Чаще всего в агентных технологиях используются: универсальные языки программирования.

1.4 Архитектура мультиагентных систем

Интеллектуальная мультиагентная система - это множество распределенных в сети интеллектуальных агентов. Агенты перемещаются по сети в поиске данных, знаний, они могут кооперироваться с целью выполнения задач, поставленных перед ними. Выделяют три типа архитектур МАС [10]:

1) Архитектуры, основанные на методах работы со знаниями;

2) Архитектуры, в которых используются поведенческие модели «стимул-реакция»;

3) Гибридные архитектуры.

В архитектурах, основанных на методах работы со знаниями, представление и обработка знаний реализуется через традиционные методы, модели и средства искусственного интеллекта, принятие решений происходит на основе механизмов формальных рассуждений. Главным недостатком архитектур, основанных на методах работы со знаниями, является сложность построения в достаточной мере полных баз знаний, необходимых для создаваемых систем. В частности, интеллектуальный агент может обладать архитектурой типичной продукционной системы, воспринимающей информацию из внешней среды и осуществляющей какие-либо действия в результате обработки этой информации. Основные отличия агентной программы от обычной продукционной системы связаны с наличием механизма формирования целей и модуля коммуникации, обеспечивающего взаимодействие с другими агентами. Стоит отметить, что агент, обладающий такой архитектурой, способен рассуждать, но не способен обучаться. Архитектура на основе классифицирующих систем Дж. Холланда позволяет реализовать адаптивное поведение агента. Важными отличиями классифицирующих систем от продукционных являются возможность формировать новых правил с применением генетического алгоритма и наличие механизма поощрений [10].

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

Гибридные архитектуры позволяют использовать возможности архитектур первых двух типов. В качестве примера можно привести архитектуру с иерархической базой знаний, которая содержит структурированную базу знаний, рабочую память, модуль управления коммуникацией и человеко-машинный интерфейс. Агент, обладающий такой архитектурой, способен рассуждать и проявлять реактивное поведение. Его база знаний содержит знания о предметной области, взаимодействии, позволяющие принимать решения при неопределенности и управляющие знания. Интеллектуальное поведение агента обеспечивается за счет способности принятия решений, реактивное через систему контроля за содержимым рабочей памяти, функционирующей по принципу глобальной доски объявлений. Взаимодействие агента и пользователя осуществляется с помощью человеко-машинного интерфейса. Гибридные архитектуры являются многоуровневыми, они отличаются друг от друга структурой и содержанием уровней [30].

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

В отличии от других интеллектуальных систем, в многоагентных системах агенты взаимодействуют друг с другом, то есть в МАС устанавливаются двусторонние или многосторонние связи между элементами системы. Взаимодействие происходит не только как результат деятельности агентов, но и является необходимым условием для формирования виртуальных сообществ. Ключевые характеристики взаимодействия - направленность, избирательность, интенсивность и динамичность [52].

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

К базовым видам взаимодействия между агентами относятся [30]:

– Кооперация (сотрудничество);

– Конкуренция (конфронтация, конфликт);

– Компромисс (учет интересов других агентов);

– Конформизм (отказ от своих интересов в пользу других);

– Уклонение от взаимодействия.

Взаимодействие агентов обусловлено такими причинами как совместимость целей (или общая цель), отношение к ресурсам, необходимость привлечения недостающего опыта, взаимные обязательства. Совокупность разных причин приводит к различным формам сотрудничества агентов. Например, можно получить простое сотрудничество, предполагающее привлечение опыта отдельных агентов без каких-либо специальных мер по координации действий этих агентов. Если агентам необходимо согласовывать свои действия для эффективного использования ресурсов и опыта, то такой вид взаимодействия можно обозначить как координируемое сотрудничество. Либо же взаимодействие между агентами может быть непродуктивным (непродуктивное сотрудничество), то есть агенты пытаются достигнуть общей цели, либо совместно используют ресурсы, но при этом они могут мешать друг другу и не обмениваться опытом [30].

1.5 Моделирование взаимодействия в мультиагентных системах

Коллективное поведение агентов в мультиагентных системах предполагает сотрудничество агентов при совместном решении задач. В случае, если во время рабочего процесса МАС агент не может самостоятельно решить задачу, он обращается и использует помощь иных агентов. Также стоит отметить тот факт, что агенты способны планировать совместные действия полагаясь на свои возможности и анализируя планы и намерения других агентов МАС. Необходимость моделирования коллективного поведения также возникает в случаях, когда агенты используют какой-либо общий ограниченный ресурс для выполнения своих задач. Агенты должны учитывать то, что в системе есть другие агенты, выбор стратегии поведения каждого агента зависит от действий остальных членов коллектива.

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

Взаимодействие агентов при решении индивидуальных задач (либо достижение единой для всех агентов МАС цели) приводит к появлению нового качества решения этих задач, а это в свою очередь является важной особенностью коллективного поведения агентов в МАС. При моделировании координации поведения агентов применяются такие идеи как [7]:

1) Отказ от поиска наилучшего решения в пользу «хорошего», что приводит к переходу от процедуры строгой оптимизации к поиску приемлемого компромисса;

2) Применение самоорганизации как устойчивого механизма формирования коллективного поведения;

3) Применение случайно-вероятностного способа выбора решений в механизмах координации для устранения конфликтов;

4) Реализация рефлексивного управления [12], иными словами заставить субъект осознанно подчиняться влиянию извне, сформировать у него такие интенции, которые совпадают с требованиями окружения.

1.6. Координация поведения агентов в мультиагентной системе

Если говорить о моделях координации поведения агентов, то выделяют следующие модели: теоретико-игровые модели, модели коллек­тивного поведения автоматов, модели планирования коллектив­ного поведения, модели на основе BDI-архитектур (Belief -Desire - Intention), модели координации поведения на основе конкуренции.

Если говорить о теоретико-игровых моделях, то стоит отметить, что предметом теории игр является задача выбора решений в условиях конфликта и неопределенности. Возникновение конфликта означает, что есть минимум два участника (игрока). Множество решений, которые могут быть выбраны каждым игроком, называется стратегия. Равновесными точками игры, или оптимальными решениями, считаются состояния, когда всем игрокам невыгодна смена своей позиции. В теории мультиагентных систем понятие равновесия играет важную роль, так как механизм поиска равновесных ситуаций может использоваться как средство самоорганизации коллективного поведения агентов [45]. Следствием такой интерпретации является подход, в котором необходимые атрибуты коллективного поведения агентов обеспечиваются через конструирование правил игры. Также, стоит отметить, что благодаря теории игр в области многоагентных систем, можно говорить о построении эффективных, распределенных протоколов коммуникации для координации коллективного поведения агентов.

Модели коллективного поведения автоматов основаны на идеях рандомизации, самоорганизации и распределенности [25]. Такие модели подходят для построения протоколов переговоров в задачах, характеризующихся большим количеством простых взаимодействий с неизвестными характеристиками.

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

В моделях на основе BDI-архитектур [39, 22] используются аксиоматические методы теории игр и логической парадигмы искусственного интеллекта. В рамках таких моделей для описания агентов используются логические средства. Акцентируется описание таких понятий как убеждения (belief), желания (desire) и намерения (intention). Координация поведения агентов выполняется через согласование результатов логического вывода в базах знаний отдельных агентов. Логический вывод делается в процессе функционирования агентов, что ведет к сложности моделей, вычислительным трудностям.

В модели на основе конкуренции применяется понятие аукцион в качестве механизма координации поведения агентов. Использование механизма аукциона основано на предположении о возможности явной передачи «полезности» от одного агента к другому или к агенту-аукционеру, причем эта полезность обычно имеет смысл денег [7].

Выводы по главе 1.

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



Глава 2. Анализ методов и технологий Text Mining и Social Mining

2.1 Понятие text mining

Очевидным фактом является то, что Интернет является самым масштабным хранилищем знаний, в котором содержится невероятно огромное количество всевозможных документов. Человеку довольно сложно справиться с таким объемом информации, поэтому ему необходимы инструменты для ее обработки и расшифровки. При этом важно отметить, что такая информация не всегда хранится в удобной для понимания машины форме, в большинстве своем это текстовые документы, удобные для чтения человеком. В данном случае применяется технология text mining.

Прежде чем говорить об интеллектуальном анализе текста, стоит разобраться с понятием data mining, или интеллектуальный анализ данных, ведь он предшествовал и стал основой для возникновения text mining. Одно из значений термина «mining» переводится с английского языка как «добыча», то есть словосочетание «data mining» можно буквально перевести как «добыча данных». Согласно Григорию Пятецкому-Шапиро, который ввел данное определение в 1992 году, Data Mining - это процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных, доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности [54]. То есть интеллектуальный анализ данных помогает найти наиболее интересные пользователю данные из огромных баз данных, обработать которые вручную практически невозможно. Text mining, или интеллектуальный анализ текста, представляет собой некое продолжение data mining.

Text mining, или интеллектуальный анализ текста - направление в искусственном интеллекте, целью которого является получение информации из коллекций текстовых документов, основываясь на применении эффективных в практическом плане методов машинного обучения и обработки естественного языка [2]. Само понятие «интеллектуальный анализ текстов» тесно связано с понятием «интеллектуальный анализ данных» (ИАД, англ. data mining). Это проявляется в схожести их целей, подходов к обработке информации и сферах применения. Разница между Text Mining и Data Mining заключается в конечных методах и в том, что Data Mining связан с хранилищами и базами данных, а не электронными библиотеками и корпусами текстов.

Основными задачами text mining являются: категоризация текстов, извлечение информации и информационный поиск, обработка изменений в коллекциях текстов, разработка средств представления информации для пользователя [2]. Основной целью интеллектуального анализа текста является поиск новой информации, которая неизвестна и еще не записана.

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

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

Основными элементами text mining являются классификация, кластеризация, построение семантических сетей, извлечение фактов, суммаризация, формирование ответов на запросы, тематическое индексирование и поиск по ключевым словам [51].

Задача классификации - это классическая задача распознавания, где по некоторой контрольной выборке система относит новый объект к той или другой категории. В контексте машинного обучения, этот элемент относится к обучению с учителем. То есть пользователь предварительно обучает систему, предоставляя ей множество классов и примеры документов, относящиеся к этим классам. То есть, классификация необходима для того, чтобы построить некие правила, по которым документы распределяются по классам. Особенностью классификации в контексте text mining является большое количество объектов и атрибутов [24]. То есть, должны быть предусмотрены механизмы оптимизации процесса классификации, они должны быть интеллектуальными.

Кластеризация основывается на признаках документов, использует лингвистические и математические методы без использования определенных категорий. В результате мы получаем таксономию или визуальную карту, которая обеспечивает эффективный охват больших объемов данных. Кластеризация в Text Mining рассматривается как процесс выделения компактных подгрупп объектов с близкими свойствами. Система должна самостоятельно найти признаки и разделить объекты по подгруппам. То есть, в терминах машинного обучения, кластеризация относится к обучению без учителя. Различают два основных типа кластеризации - иерархическую и бинарную. Кластеризация используется при реферировании больших массивов документов, определение взаимосвязанных групп документов, упрощения процесса просмотра при поиске необходимой информации, нахождения уникальных документов из коллекции, выявления дубликатов или очень близких по содержанию документов.

...