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

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

Постановка задачи

Рассматривается задача диагностики на основе модели [Brusoni et al., 1998]. Модель может быть использована для имитации поведения объекта и выявления неисправностей. Если имеются результаты наблюдений за поведением системы, диагностирование может быть произведено путем сравнения поведения, предсказанного моделью, и наблюдаемым поведением объекта. Чтобы такая модель была полезной и для бортовой диагностики, она должна включать в себя действия, которые должны производиться в случае обнаружения отказа. В общем случае действия (восстановительные действия) характеризуются некоторой стоимостью, которая чаще всего выражается в уменьшении функциональности системы. Таким образом, основная цель процедуры бортовой диагностики заключается в выборе оптимального действия в аварийном режиме.

Для имитации поведения объекта и выявления неисправностей может быть использована модель специального вида, которая описывает структуру и поведение сложного технического объекта. Такая модель представляет собой тройку <S, M, R>, где:

S - множество переменных, описывающих состояние системы (в технической диагностике это чаще всего измерения, получаемые от датчиков, установленных в системе, или результаты вычислений, выполненных над полученными измерениями);

M - набор режимов работы, включающих в себя состояния "норма" (корректное поведение) и "неисправность" (некорректное поведение);

R - набор отношений, связывающих множество переменных S, описывающих состояние системы, и набор режимов работы M.

В рассматриваемой задаче информация о функционировании объекта управления представлена множеством результатов измерений, поступающих с датчиков; таким образом, состояние сложного объекта и его компонентов описывается набором признаков (количественных и качественных), при этом одним из признаков является время. Целью работы является получение обобщенных описаний классов ситуаций, возникающих на объекте, причем с каждым классом ситуаций связываются определенные действия по управлению объектом, называемые далее восстановительными действиями. Постановка задачи обобщения по признакам приведена в [Вагин и др., 2008].

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

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

Необходимо на основе анализа обучающей выборки построить понятие, разделяющее положительные и отрицательные примеры. Понятие Q считается сформированным, если удалось построить решающее правило, которое для любого примера из обучающей выборки указывает, принадлежит ли этот пример понятию, или нет. Сформированное понятие может быть представлено в виде логической функции, дерева решений, набора продукционных правил вида “ЕСЛИ условие ТО искомое понятие”.

Исходными данными как для первоначального обобщения, так и для диагностики, является таблица наблюдений. Также может использоваться некоторая модель для восстановительных действий: например, может быть введен частичный порядок над действиями - тогда при наличии неразличимых ситуаций и сравнимых действий достаточно будет выполнить наиболее сильное из действий. Далее приведен пример таблицы с наблюдениями (табл. 1).

Табл. 1.

Каждой строке в таблице соответствует некоторая ситуация сит_i, которая определяется:

показаниями датчиков Датчик_j в моменты времени k=0, 1,.7 (здесь z, n, l, v, h соответствуют качественным показаниям датчиков: n - норма, l и h соответственно низкое и высокое, v - очень низкое, z - нуль);

восстановительным действием Д_i для каждой ситуации;

крайним сроком К_i выполнения соответствующего действия.

Такое представление позволяет не вводить каких-либо ограничений на способ представления времени в системе.

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

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

Общая схема алгоритма построения темпорального дерева решений приведена на рис.1. На вход алгоритма подаются:

1) таблица с ситуациями;

2) наблюдения (множество пар <датчик, временная метка>);

3) модель восстановительных действий. На выходе получаем темпоральное дерево решений. Функция Лист (S, M) на основе ситуаций и модели восстановительных действий строит лист дерева, помечая его множеством восстановительных действий, полученным согласно модели.

В работе был исследован алгоритм для построения темпоральных деревьев решений, изложенный в [Console et al., 2003] (назовем его CPD как сокращение от фамилий авторов - Console-Picardi-Dupre). Этот алгоритм строит темпоральное дерево решений на основе показаний датчиков с учетом крайнего срока выполнения действий и их стоимости. Временные метки в узлах дерева при движении от корня к листьям не убывают, следовательно, нет необходимости хранить показания датчиков при диагностировании.

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

Основное различие между алгоритмами CPD и temporal ID3 - выбор наблюдения, на основе которого будет производиться разбиение множества ситуаций. В алгоритме CPD выбирается наблюдение, минимизирующее стоимость результирующего дерева. В temporal ID3 мы используем критерий "прирост информативности" Куинлана [Quinlan, 1986].

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

Темпоральные деревья решений, построенные с использованием данных из табл.1 и алгоритмов CPD и temporal ID3, приведены соответственно на рис.2 и рис.3.

темпоральное дерево решение база интеллектуальная

Моделирование