Распределенные СППР

Технологии распределенных СППР

Лекция 2 часа

Алгоритмы ограниченного перебора

Алгоритмы ограниченного перебора были предложены в середине 60-х годов М.М. Бонгардом для поиска логических закономерностей в данных. С тех пор они продемонстрировали свою эффективность при решении множества задач из самых различных областей.

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

Наиболее ярким современным представителем этого подхода является система WizWhy предприятия WizSoft. Хотя автор системы Абрахам Мейдан не раскрывает специфику алгоритма, положенного в основу работы WizWhy, по результатам тщательного тестирования системы были сделаны выводы о наличии здесь ограниченного перебора (изучались результаты, зависимости времени их получения от числа анализируемых параметров и др.).

Автор WizWhy утверждает, что его система обнаруживает ВСЕ логические правила «ЕСЛИ... ТО» в данных. На самом деле это, конечно, не так. Во-первых, максимальная длина комбинации в правиле «ЕСЛИ... ТО» в системе WizWhy равна 6, и, во-вторых, с самого начала работы алгоритма производится эвристический поиск простых логических событий, на которых потом строится весь дальнейший анализ. Поняв эти особенности WizWhy, исследователями была предложена простейшая тестовая задача, которую система не смогла вообще решить. Другой момент — система выдает решение за приемлемое время только для сравнительно небольшой размерности данных (не более 20).

Тем не менее, система WizWhy является на сегодняшний день одним из лидеров на рынке продуктов Data Mining. Это не лишено оснований. Система постоянно демонстрирует более высокие показатели при решении практических задач, чем все остальные алгоритмы. Стоимость системы около $ 4000, количество продаж — 30000.

СППР могут быть сосредоточенные и распределенные.

а) Сосредоточенные СППР включают в себя одну СППР, установленную на одной ЭВМ. Они выполняют свои функции, помогая одному ЛПР (или небольшой группе специалистов) оценивать обстановку и принимать решения. Они проще, чем распределенные системы, т.к. в них отсутствует проблема обмена информацией.

Возможны следующие типы сосредоточенных СППР:

1. Решение в автоматическом режиме принимает система принятия решения, состоящая из одного узла. Такая система включает в себя ЭВМ, систему автоматического и/или ручного ввода информации и средства представления решения (возможно стандартное устройство вывода). Примером такой системы может быть система тушения пожара на каком-нибудь особо опасном объекте. В этой системе автоматические датчики температуры и газоанализаторы передают в ЭВМ результаты измерений, экспертная система определяет момент опасности возникновения пожара (если она есть) и его место и включает средства тушения пожара и/или передает сигнал тревоги. Это системы, принимающие решения (СПР), а не поддерживающие принятие решений.

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

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

Необходимо особо отметить очень распространенный класс систем – иерархические системы поддержки принятия решений (ИСППР).

ИСППР состоят из экспертных систем или систем поддержки принятия решений, расположенных в узлах, связанных между собой вычислительной сетью. С точки зрения принятия решений узлы не равноправны. Самый простой пример такой системы — это система, состоящая из подсистем W ₁, W ₂,…, W _n первого уровня и одной подсистемы W ₀ второго (более высокого) уровня.

Цель подсистемы W ₀ — влиять на низшие подсистемы таким образом, чтобы достигалась общая цель, заданная для всей системы. Такая система может служить в качестве элементарного блока при построении более сложных систем.

Объективно существуют интересы системы в целом. Их выразителем выступает подсистема W ₀. Существуют и интересы подсистем W ₁, W ₂,…, W _n, причем их интересы, как правило, не совпадают или совпадают не полностью как интересами подсистемы W ₀, так и друг с другом. Степень централизации системы определяется мерой разделения полномочий между уровнями системы. В тех случаях, когда система W ₀ не может приказывать подсистемам низшего уровня, а подсистемы низшего уровня не могут функционировать без координирующих действий (например, при выработке новой стратегии действий или распределении ресурсов), необходима разработка согласованных решений.

Распределенные системы получают в настоящее время все более широкое распространение по следующим причинам:

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

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

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

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

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

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