BC/NW 2007, №2, (11) :8.2

Разработка мультиагентной системы для решения задач интелЛектуального анализа данных.

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

(г. Москва, Московский Энергетический Институт (ТУ), Россия) [1]

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

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

Средствами Data Mining применяются для решения различных аналитических задач. Среди них основными на данный момент являются задачи классификации, регрессии, кластеризации и задача поиска ассоциативных правил [1].

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

К задачам описательного типа относятся кластеризация и поиск ассоциативных правил. Решение задачи кластеризации, как правило, проводится на самом начальном этапе анализа данных, когда о них практически ничего неизвестно. Основная цель состоит в поиске множества возможных кластеров объектов и определении принадлежности объектов к этим кластерам.

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

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

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

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

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

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

Алгоритмы, заключающиеся в построении деревьев решений «сверху вниз» (ID3, C4.5), на основе методики «разделяй и властвуй», очень хорошо поддаются распараллеливанию [3]. После разбиения множества объектов на подмножества, содержащие элементы, различающиеся по некоторому признаку, анализ каждого подмножества может проводиться параллельно. Управляющий агент при этом должен следить за загрузкой подопечных агентов, распределяя между ними соответствующие подзадачи, а также отвечая за сбор результатов работы с агентов-аналитиков и формирование конечной модели.

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

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

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

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

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

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

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

ЛИТЕРАТУРА

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

2.     Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия,  психология,  информатика. // М.: Эдиториал УРСС, 2002.

3.     Narlikar G. J. A Parallel, Multithreaded Decision Tree Builder. // Computer Science Department, Carnegie Mellon University, CMU-CS-98-184, 1998.

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