BC/NW 2008, №2 (13): 12.4

ПРИМЕНЕНИЕ СИСТЕМ МОБИЛЬНЫХ АГЕНТОВ ПРИ РЕШЕНИИ ЗАДАЧ КЛАССИФИКАЦИИ РАСПРЕДЕЛЕННЫХ ДАННЫХ

Бредихин К.Н., Варшавский П.Р.

(г. Москва, Московский Энергетический Институт (Технический Университет), Российская Федерация)

Работа выполнена при финансовой поддержке РФФИ по проекту № 08-01-00437 и гранту Президента РФ для поддержки молодых российских ученых (МК-6009.2008.9)

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

Точность и эффективность получаемой модели зависит от объемов обучающей выборки, данных, на основе которых осуществляется построение (обучение) классификатора. Чем больше данных подвергается анализу, тем выше качество извлекаемых закономерностей. В настоящее время большие объемы однородных данных хранятся, как правило, распределенно. Адаптация методов и алгоритмов добычи знаний (Data Mining, в частности, методов и алгоритмов классификации) к работе с распределенными данными – одна из наиболее актуальных на сегодняшний день задач в области интеллектуального анализа данных (ИАД).

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

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

Эти и многие другие достоинства СМА представляют их в качестве весьма эффективного решения при создании систем интеллектуального анализа распределенных данных.

На сегодняшний день реализовано довольно много различных библиотек и платформ для поддержки процесса разработки и внедрения СМА. Ассоциацией FIPA (Foundation for Intelligent Physical Agents) ведутся работы по стандартизации различных аспектов реализации как агентов, так и мультиагентных систем в целом.

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

Цель данной работы состоит в попытке рассмотреть основные вопросы проектирования и реализации базовой архитектуры СМА для решения задач ИАД на примере задачи распределенной классификации. В качестве методов решения мы используем деревья решений и метод k ближайших соседей.

 

В некоторых работах [2] по распределенной классификации выделяются два основных подхода к обучению классификаторов на основе распределенной обучающей выборки: последовательное распределенное обучение (serial distributed learning) и параллельное распределенное обучение (parallel distributed learning). В первом случае для анализа выделяется некий агент-аналитик, который последовательно перемещается между узлами сети и анализирует расположенные на них данные. После обработки всех нужных узлов он возвращается обратно к пользователю и формирует окончательный результат либо самостоятельно, либо взаимодействуя с управляющим агентом, который занимается координацией действий агентов и передачей результатов пользователю.

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

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

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

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

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

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

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

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

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

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

Известный алгоритм C4.5 [3], используемый для построения деревьев решений, был расширен несколькими дополнительными шагами, заключающимися в объединении агентом-менеджером полученных от агентов-аналитиков статистических данных о принадлежности объектов распределенной обучающей выборки тому или иному классу. На основе общей статистики обо всех объектах выборки, агент-менеджер вычисляет значение выигрыша от разбиения по каждой из независимых переменных и определяет лучший вариант разбиения, добавляя к формируемому дереву решений новый узел.

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

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

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

В качестве тестовых данных были выбраны две базы данных из известного хранилища UCI Machine Learning Repository [5], составленных на основе реальных данных: о случаях заболеваний щитовидной железы (Thyroid Disease) и о типах лесного покрова (Forest CoverType). Обе базы данных представляют собой единые (неразделенные) хранилища, поэтому при тестировании создание распределенной выборки проводилось искусственным образом (так как на момент написания этой работы авторам не удалось найти лежащие в открытом доступе распределенные базы данных, используемые при решении задачи классификации). Первая база данных использовалась для тестирования работы классификации методом k ближайших соседей, вторая – для тестирования работы классификации на основе деревьев решений.

 

В ходе реализации и тестирования системы было выявлено несколько недостатков, как чисто технических, связанных с платформой реализации (.NET Framework 2.0), так и алгоритмических, связанных с выбранными стратегиями решения задачи классификации. Например, в распределенной классификации с использованием метода k ближайших соседей, несмотря на перенос задач по определению класса нового объекта и формированию нового прецедента на агентов-аналитиков, загрузка агента-менеджера, осуществляющего поиск множества k ближайших соседей для каждого из классифицируемых объектов, оказалась слишком велика. В результате этого, данный центральный компонент становится «узким местом» всей системы.

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

В рамках данной работы был разработан прототип СМА для решения задачи классификации распределенных данных. В качестве платформы для реализации был выбран .Net Framework 2.0. Были реализованы два алгоритма распределенной классификации – на основе деревьев решений (С4.5) и на основе прецедентов (метод k ближайших соседей). Произведен анализ эффективности разработанной системы. Планируется дальнейшая доработка архитектуры платформы для СМА и исследование методов и алгоритмов добычи знаний на предмет реализации на данной платформе.

 

ЛИТЕРАТУРА

1.     Lange D.B., Oshima M.С. Seven Good Reasons for Mobile Agents. // Communications of the ACM, 42(3), 1999, pp. 88-89.

2.     Caragea D., Silvescu A., Honavar V. Decision Tree Induction from Distributed, Heterogeneous, Autonomous Data Sources. // In Proceedings of the 3^rd International Conference on Intelligent Systems Design and Applications (ISDA 03), Tulsa, Oklahoma, 2003, pp. 341-350.

3.     Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. // 2-е изд., -СПб: БХВ-Петербург, 2007.

4.     Варшавский П.Р. Реализация метода правдоподобных рассуждений на основе прецедентов для интеллектуальных систем поддержки принятия решений // 10-я национальная конференция по искусственному интеллекту с международным участием КИИ-2006: Труды конференции. В 3-х т., Т. 1. –М:Физматлит, 2006 г., – с. 303–311.

5. University of California, Irvine. Machine Learning Repository – Center for Machine Learning and Intelligent Systems, http://archive.ics.uci.edu/ml/index.html.