Метод формирования обобщенных понятий с использованием темпоральных деревьев решений

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

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

Диагностика
в искусственном интеллекте
Актуальной проблемой современных интеллектуальных систем является обнаружение знаний в массивах данных. Это связано с большим объемом современных баз данных, которые так велики, что практически невозможно вручную проанализировать их для извлечения ценной информации, помогающей принимать важные решения. Отсюда следует, что люди нуждаются в помощи интеллектуальных систем для повышения своих аналитических возможностей.
Системы автоматического обнаружения знаний могут анализировать "сырые" данные и предоставлять извлеченную информацию скорее и успешнее, чем аналитик мог бы найти её самостоятельно. Во многих случаях для описания поведения сложных систем приходится использовать сотни независимых атрибутов, которые необходимо анализировать, чтобы наиболее точно смоделировать поведение системы. В такой ситуации крайне важно решать задачу обобщения для получения компактных описаний классов ситуаций на объекте управления.
Диагностика как раздел искусственного интеллекта занимается разработкой методов и алгоритмов, способных определить корректность работы изучаемого объекта (системы). Если система работает некорректно, нужно как можно более точно определить, в какой части системы произошел отказ, и какая ошибка произошла. Определение ошибки происходит на основе наблюдений, которые дают информацию о поведении системы.

Постановка задачи обобщения
Дадим формулировку задачи обобщения понятий по признакам . Пусть имеется О - множество объектов, которые могут быть представлены в интеллектуальной системе S. Каждый объект характеризуется r признаками. Обозначим через Dom(А1), Dom(А2), … , Dom(Аr) множества допустимых значений признаков, где Dom(Аk)={x1, x2, … xq }, 1≤k≤r, и q - количество различных значений признака Ak. Каждый объект о∈О, представляется как множество значений признаков, т.е. о=
, где xik∈ Dom(Аk), . Такое описание объекта называется признаковым описанием. В качестве признаков объектов могут использоваться количественные, качественные либо шкалированные признаки.
В основе процесса обобщения лежит сравнение описаний исходных объектов, заданных совокупностью значений признаков, и выделение наиболее характерных фрагментов этих описаний. В зависимости от того, входит или не входит объект в объем некоторого понятия, назовем его положительным или отрицательным объектом для этого понятия.
Пусть O - множество всех объектов, представленных в некоторой системе, V - множество положительных объектов и W - множество отрицательных объектов. Будем рассматривать случай, когда O=V∪W, V∩W=∅ . Пусть K - непустое множество объектов такое, что K=K+∪K-, где K+ ⊂V и K- ⊂W . Будем называть K обучающей выборкой. На основании обучающей выборки надо построить правило, разделяющее положительные и отрицательные объекты обучающей выборки.
Таким образом, понятие сформировано, если удалось построить решающее правило, которое для любого примера из обучающей выборки указывает, принадлежит ли этот пример понятию, или нет. Решающее правило является корректным, если оно в дальнейшем успешно распознаёт объекты, не вошедшие первоначально в обучающую выборку.

Методы решения задачи обобщения
Известен целый ряд методов, пригодных для обнаружения знаний. Каждый предложенный метод имеет свои преимущества. Методы, обычно используемые для извлечения полезной информации из данных, можно разделить на следующие группы:
Статистические методы. Статистический подход обычно основывается на вероятностных моделях. Предполагается, что такие методы будут использованы специалистами по статистике и, следовательно, требуется человеческое вмешательство при порождении гипотез и моделей.
Вывод, основанный на прецедентах. Это технология решения поставленной проблемы путём непосредственного использования предыдущего опыта и ранее принятых решений. Прецедентом (случаем) считается проблема, которая возникала ранее и которая была решена. При возникновении новой проблемы вывод, основанный на прецедентах, проверяет множество ситуаций, хранящихся в информационной базе, и находит схожую.
Нейронные сети. Нейронные сети состоят из большого числа нейроподобных элементов, соединенных между собой наподобие нейронов человеческого мозга. Подобно тому, как это происходит в человеческом мозге, стремление нейронов к взаимодействию может изменяться в ответ на воздействие или полученный выходной сигнал, что делает возможным обучение в сети.
Деревья решений. Дерево решений – это дерево, в котором каждый узел, не являющийся конечным, представляет собой проверку условия, или, если узел конечный, предъявляется решение для рассматриваемого элемента. Чтобы выполнить классификацию предъявленного примера, необходимо начать с корневого узла. Затем мы следуем по дереву решений вниз, пока не будет достигнут конечный узел (или лист). В каждом узле, не являющемся конечным, проверяется одно из условий. В зависимости от результата проверки условия выбирается соответствующая ветвь для дальнейшего движения по дереву. Решение получено, если мы достигли конечного узла.
Байесовские доверительные сети. Байесовская доверительная сеть представляет собой направленный ациклический граф, узлы которого представляют значения атрибутов, а веса дуг представляют вероятностные зависимости между атрибутами. Каждому узлу сопоставляются условные распределения вероятностей, описывающие отношения между узлом и предками этого узла.
Генетические алгоритмы \ эволюционное программирование. Генетические алгоритмы и эволюция – это алгоритмически оптимизированные стратегии, базирующиеся на принципах естественной эволюции. Генетические алгоритмы и эволюционное программирование используют методы обобщения, чтобы сформулировать гипотезы относительно зависимостей между переменными в форме ассоциативных правил, либо используя какой-то иной формализм.
Приближенные множества. Приближенное множество определяется посредством задания верхней и нижней границ некоторого множества, называемых приближениями этого множества. Каждый элемент нижнего приближения наверняка является элементом множества. Каждый элемент, не вошедший в верхнее приближение, наверняка не является элементом множества. Верхнее приближение приближенного множества - это объединение нижнего приближения и так называемой граничной области. Элемент граничной области вероятно (но, не наверняка) является элементом множества. Подобно нечетким множествам, приближенные множества являются математической концепцией для работы с нечеткостями в данных.

Модель для описания объекта
Для имитации поведения объекта и выявления неисправностей может быть использована модель специального вида, которая описывает структуру и поведение сложного технического объекта.
Данная модель представляет собой четверку
, где:
O – множество компонент сложного технического объекта;
E – функциональные связи между компонентами;
S – множество переменных, описывающих состояние системы;
B – множество управляющих действий, допустимых в системе.

Модель для описания компонентов объекта
Для описания отдельного компонента o из O также используется модель, представляющая из себя тройку
, где:
- S' - подмножество переменных из S, описывающих состояние данного компонента;
- M – набор режимов работы, включающих в себя состояние «норма» (корректное поведение) и состояния «неисправность» (некорректное поведение) ;
- R – набор отношений, связывающих множество переменных S, описывающих состояние системы, и набор режимов работы M.

Общая схема процедуры диагностики и выбора управляющего воздействия

Формирование обобщенных понятий для решения задачи диагностики
Решение задачи обобщения на основе анализа набора признаков предполагает первоначально построение обобщенного понятия, а затем использование его для классификации ситуаций на объекте. Рассмотрим возможные ситуации на объекте. Введем понятия:
Cn – множество состояний сложного технического объекта, которые диагностируются как нормальные;
Cf – множество состояний, в которых наблюдаются неисправности на объекте.
Необходимо сформировать описание понятий Cn и Cf в рамках введенной модели. На основе полученных обобщенных описаний классов Cn и Cf необходимо выработать рекомендации по выбору восстанавливающего действия на сложном техническом объекте; такое действие должно переводить систему из состояния «неисправно» в состояние «норма».

Недостатки классических деревьев решений
В настоящее время известен целый ряд алгоритмов для построения деревьев решений. Такие алгоритмы, как ID3, ДРЕВ и различные модификации этих алгоритмов - C4.5, ID5R и др. - обрели широкое распространение и зарекомендовали себя в широком спектре приложений.
Однако деревья решений в их классическом виде имеют некоторые ограничения — в частности, невозможность работы с поведением объекта или системы во времени, невозможность принятия решений с течением времени.
Классические деревья решений позволяют рассматривать только отдельные состояния объекта;
- невозможно проследить динамику изменения состояний;
- невозможность учитывать фактор времени.
Без учета фактора времени не удастся проследить динамику изменения состояния системы. Предлагается расширить признаковое описание объектов: введем понятие «время» как один из атрибутов, используемых при построении дерева решений. Будем использовать дискретное время: t = 0, 1, 2, ...

Описание состояния объекта (системы) с учетом фактора времени

Ситуация
Пусть для слежения за состоянием сложного технического объекта или системы используется некоторое количество датчиков. Обозначим эти датчики s1, s2, …, sn. Пусть показания с этих датчиков снимаются через некоторый временной интервал t0 - в каждый момент времени.
Каждую ситуацию из Cn и Cf предлагается рассматривать на некотором временном интервале t*, включающем определенное количество дискретных значений t. При этом ситуацией будем называть последовательность из t* значений датчиков с соответствующими им временными метками.
В данной работе под конкретной ситуацией понимается последовательность показаний датчиков, снятых за интервал времени t*. Показания датчиков сопровождаются соответствующими им временными метками.

Пример ситуации(1)
t*=5

Пример ситуации (2)
t*=5

Пример ситуации (3)
t*=5

Темпоральные (временные) деревья решений
Темпоральное дерево решений — это взвешенный ориентированный граф Ttemp=(Vtemp, Etemp).
Во множестве вершин Vtemp выделим вершину v0 – корень дерева. Все вершины разделим на два класса: Vi - множество внутренних вершины дерева; Vl – множество внешних вершин дерева (листьев)
Внутренние вершины Vi дерева взвешены (помечены) наблюдением, то есть парой
, где: a – имя атрибута; tc – временная метка.
Вершины-листья Vl взвешены (помечены) названием или номером ситуации и предлагаемым восстановительным действием, если ситуация относится к классу Cf.
Каждая дуга e дерева решений взвешена условием «атрибут[tc]= значение_атрибута». где «атрибут» - имя атрибута в вершине, из которой исходит дуга e, «значение_атрибута» - одно из возможных значений признака «атрибут»; tc – момент времени, в который необходимо проводить эту проверку, 0≤ tc< t*.

Исходные данные для построения темпоральных деревьев решений
Исходными данными является таблица наблюдений и
модель восстановительных действий.
Каждой строке в таблице соответствует некоторая
ситуация ситi, которая определяется:
- показаниями датчиков Датчикj в моменты времени
t=0, 1,.. t*
- восстановительным действием Д i для каждой ситуации;
- крайним сроком К i выполнения соответствующего действия.
Такое представление позволяет не вводить каких-либо ограничений на способ представления времени в системе.

О восстановительных действиях
Восстановительные действия должны переводить сложный технический объект или систему из состояния «неисправность» в состояние «норма», при этом надо учесть, что они:
- могут негативно сказываться на функциональности системы (например, отключение процессора в компьютере)
- могут быть связанными между собой: операции, выполняемые восстановительным действием d1 в ситуации f1, могут включать в себя некоторые (или даже все) операции, которые выполняются восстановительным действием d2 в ситуации f2

Стоимость восстановительных действий
Восстановительные
действия характеризуются
названием и некоторой
условной величиной —
стоимостью (учитывается
возможное негативное
влияние).
Дополнительно можно
ввести порядок над
действиями (учитывается
возможная связь между
ними).
{d}, 10

Пример исходных данных для алгоритмов построения темпоральных деревьев решений
(z, n, l, v, h соответствуют качественным показаниям датчиков )

Общая схема алгоритма построения темпоральных деревьев решений

Алгоритм CPD
В работе был исследован алгоритм для построения темпоральных деревьев решений, изложенный в работе
Console L., Picardi C., Dupré D. Temporal decision trees: model-based diagnosis of dynamic systems on-board // Journal of artificial intelligence research. 2003. №19
(назовем его CPD как сокращение от фамилий авторов - Console-Picardi-Dupre). Этот алгоритм предлагается использовать для бортовой диагностики, так как исходным ограничением на темпоральное дерево решений было неуменьшение временных меток при движении от корня дерева к листьям. В связи с этим отпадала необходимость хранить предшествующие значения датчиков для их возможного дальнейшего использования (вычислительные ресурсы, используемые при бортовой диагностике, сильно ограничены). Такое требование, наложенное на темпоральное дерево решений, нашло свое отражение и в алгоритме его построения. Более того, определение некорректной работы и неисправностей при бортовой диагностике часто включает в себя выбор некоторых управляющих действий, которые должны по возможности вернуть объект или систему в корректное состояние. В общем случае, как было показано выше, восстановительное действие имеет некоторую стоимость, которая выражается в том, что функциональность объекта или системы уменьшается - например, уменьшение скорости или полная остановка автомобиля, отключение каких-либо модулей системы
и т. п. Поэтому хотелось бы минимизировать негативный эффект от восстановительных действий.
Минимизируется величина — ожидаемая стоимость дерева:
χ(node)= стоимость действий в node, если node – лист дерева;
χ(node)= (перейти из node в с)* χ(с), если node – внутренний узел дерева.

Алгоритм CPD – выбор наблюдения для разбиения

Алгоритм CPD – выбор безопасного наблюдения

Темпоральное дерево решений, построенное с помощью алгоритма CPD

Алгоритм temporal ID3
В работе предлагается оригинальный алгоритм (назовем его Temporal ID3), который является расширением алгоритма ID3 , учитывающим фактор времени. Данный алгоритм представлен ниже. По сравнению с алгоритмом CPD, на темпоральное дерево решений не накладывается никаких ограничений по временным меткам в узлах. Однако не учитывается стоимость восстановительных действий при выборе наблюдения на каждом шаге. Кроме того, снимается ограничение на неуменьшение временных меток при движении от корня дерева к листьям, что приводит к необходимости сохранять некоторые значения датчиков для дальнейшего использования при проведении диагностики.
Наблюдения
(пара <датчик, временная метка>) рассматриваются как атрибуты (признаки).

Алгоритм temporal ID3

Алгоритм temporal ID3 – выбор наиболее информативного наблюдения

Темпоральное дерево решений (temporal ID3)

Моделирование процесса диагностики
Апостериорная диагностика: известны ситуации (все показания датчиков), требуется определить некорректность ситуации.
Диагностика в псевдореальном времени: последовательно поступают значения датчиков, требуется выявить некорректные ситуации.

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

Диагностика в псевдореальном времени
При диагностике в псевдореальном времени последовательно поступают значения датчиков.

Диагностика в псевдореальном времени
При диагностике в псевдореальном времени одним темпоральным деревом не обойтись. Потребуется t* рабочих агентов, которые будут следить за временными метками и хранить не потребовавшиеся на очередном шаге значения датчиков для их возможного дальнейшего использования. Первый такой агент начинает работу в момент времени t=0, второй — в момент времени t=1, …, последний, t*-ый агент начинает работу в момент времени t=t*-1. Для организации совместной работы этих агентов потребуется агент-координатор, который будет получать информацию с датчиков, рассылать ее рабочим агентам и получать от них сведения о некорректной работе объекта или системы

Диагностика в псевдореальном времени

Точность диагностики
Моделирование процесса диагностики на основе изложенных алгоритмов состоит из нескольких этапов: первый — построение темпорального дерева решений на основе таблицы с исходными некорректными ситуациями; второй — создание многоагентной системы для диагностики в псевдореальном времени; третий — непосредственно процесс диагностики. Результаты программного моделирования представлены в таблице 2. Исходные данные для таблицы, на основе которой проводилось построение темпорального дерева решений, генерировались случайным образом по описанию предметной области. Каждая строка таблицы соответствует одному тесту. Пример № 0 (строка в таблице 2) соответствует тесту, представленному в таблице 1. Описание предметной области (метаданные) включает в себя:
- описание датчиков и их возможных значений;
- временной интервал t*, в течение которого может возникнуть некорректная ситуация;
- описание восстановительных действий, их стоимостей и порядка над ними.
Для каждого теста выбранным алгоритмом строится темпоральное дерево решений. Полученное дерево решений далее используется многоагентной системой для отнесения ситуации, возникшей на объекте, к одному из классов ситуаций, для которых известны необходимые управляющие воздействия.
Второй этап моделирования заключается в генерации ситуаций, которые могут происходить на объекте, с последующей классификацией сгенерированных ситуаций. Представленные тесты содержат в среднем 40% некорректных ситуаций, остальные ситуации относятся к корректным.
Так как листья темпоральных деревьев решений помечены ситуациями, можно вычислить степень отличия таких ситуаций от ситуаций, которые были диагностированы деревом как некорректные. Предлагается следующая метрика:

РЕЗУЛЬТАТЫ ДИАГНОСТИКИ

Выводы по результатам эксперимента
Были рассмотрены два варианта диагностирования. В первом случае выполняется классификация ситуации целиком – это возможно, если показания датчиков сняты на временном интервале, не превышающем временной интервал, указанный в исходной таблице. При этом для классификации требуется единственное дерево.
Другой вариант - классификация на большом временном интервале: на вход последовательно поступают показания датчиков. В этом случае для классификации потребуется несколько деревьев решений (точнее, столько, какова величина временного интервала, использованного при построении деревьев). Помимо этого потребуются агенты, работающие с каждым из этих деревьев (выполняют функции "получение данных", "контроль времени") и агент-координатор, который получает данные и рассылает их рабочим агентам. Такая многоагентная система позволяет проводить бортовую диагностику в псевдореальном времени.
При проведении эксперимента было выявлено, что темпоральные деревья решений, построенные с использованием алгоритмов CPD и Temporal ID3, правильно определяют значительное количество некорректных ситуаций и выбирают нужные восстановительные действия. При этом следует отметить, что одним из недостатков алгоритма CPD является большое число ложных срабатываний — так называемых ошибок первого рода. Поэтому минимизация размера дерева решений не должна быть единственным критерием при его построении.

Заключение
В работе были решены следующие задачи:
- рассмотрен подход к диагностике с использованием деревьев решений;
- введен фактор времени как один из важных параметров при проведении диагностики;
- приведено описание исходных данных для задачи диагностики с учетом временного фактора;
- предложено формальное описание темпоральных деревьев решений;
- рассмотрен алгоритм CPD для построения темпоральных деревьев решений;
- предложен алгоритм temporal ID3, позволяющий строить темпоральные деревья решений без ограничения на неубывание временных меток в узлах дерева;
- рассмотрен процесс диагностики с использованием темпоральных деревьев решений;
- проведено моделирование апостериорной диагностики с использованием темпоральных деревьев решений;
- проведено моделирование диагностики в псевдореальном времени;
- на основе проведенного моделирования сделаны выводы о возможности использования темпоральных деревьев решений для задач диагностики, указаны недостатки рассмотренных алгоритмов и предложены варианты их совершенствования.