Модификация способа построения системы аксиом и алгоритма поиска разметок для распознавания нештатного поведения при помощи аксиоматического подхода

В. В. ЩЕРБИНИН

Московский государственный университет им.

*****@***com

МОДИФИКАЦИЯ СПОСОБА ПОСТРОЕНИЯ СИСТЕМЫ АКСИОМ И АЛГОРИТМА ПОИСКА РАЗМЕТОК

ДЛЯ РАСПОЗНАВАНИЯ НЕШТАТНОГО ПОВЕДЕНИЯ

ПРИ ПОМОЩИ АКСИОМАТИЧЕСКОГО ПОДХОДА

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

Ключевые слова: фазовая траектория, алгоритм распо­знавания, динамическая си­стема, нечеткий поиск, аксиоматический подход к распознаванию нештатного поведения.

Введение

Рассматриваются системы, информация о поведении которых доступна в виде фазовых траекторий в пространстве показаний датчиков системы. Время рассматривается дискретное, датчики опрашиваются с некоторой фиксированной частотой . Фазовая траектория в пространстве показаний датчиков представляет собой набор последовательных измерений показаний датчиков системы: , где: – точка в многомерном фазовом пространстве показаний датчиков. Будем обозначать через длину траектории .

Состояние системы характеризуется точкой фазовой траектории. Со временем система изменяет свое состояние, последовательные изменения состояния системы будем называть ее поведением. Существует два типа состояний системы:

·  штатное состояние, при котором система стабильно выполняет заложенные в нее функции;

·  нештатное состояние, при котором система перестала или в скором времени гарантированно перестанет выполнять заложенные в нее функции.

Нормальное поведение системы – это такое поведение, при котором все состояния, которые принимает система, являются нормальными. Нештатное поведение системы – такое поведение, при котором все состояния, которые принимает система, являются нештатными. Может существовать несколько классов нештатного поведения, которые соответствуют различным неисправностям системы.

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

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

Аксиоматический подход к распознаванию

нештатного поведения

Опишем основные понятия аксиоматического подхода к распознаванию нештатного поведения динамических систем [1][2].

Определение 1. Элементарное условие – это функция, определенная на отчете и некоторой его окрестности на траектории , зависящая от набора параметров , которая принимает значения из множества .

Пример элементарного условия:

(1)

где , .

Определение 2. Аксиома – это функция, заданная в виде булевой формулы от элементарных условий, определенных на отсчете и некоторой его окрестности на траектории :

, (2)

где

Определение 3. Конечное множество аксиом будем называть системой аксиом, если оно удовлетворяет условию:

, (3)

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

Определение 4. Разметкой траектории системой аксиом будем называть конечную последовательность , где – индекс аксиомы в системе аксиом , выполняющейся на отсчете траектории .

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

1.  Размечаются эталонные траектории , соответствующие различным классам нештатного поведения.

2.  Размечается наблюдаемая траектория и формируется ряд разметки .

3.  В ряду разметки ищутся подпоследовательности номеров аксиом, соответствующие разметкам эталонных траекторий.

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

Задача поиска разметок

Пусть – система аксиом, построенная по набору прецедентов нештатного и нормального поведения динамической системы.

Задача поиска разметок формулируется так. Дано:

·  разметки эталонных траекторий системой аксиом ;

·  разметка наблюдаемой траектории системой аксиом ;

·  ограничения на полноту и точность распознавания: ,, где – число ошибок распознавания первого рода, – число ошибок распознавания второго рода, , – заданные числовые ограничения.

Требуется указать в разметке участки нештатного поведения и номер класса нештатного поведения для каждого указанного участка.

Определение 4. Пусть даны две траектории и , , и множество аксиом . Будем говорить, что траектории и различимы в аксиомах из множества , если выполнено следующее условие:

(4)

Здесь – окрестность отсчета траектории , – окрестность отсчета траектории . Данное определение взято из работы [1].

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

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

2.  Пусть – произвольный участок нештатного поведения в траектории , – произвольный участок нормального поведения в траектории , . Тогда и должны быть различимы в аксиомах из системы аксиом .

Доказательство данной теоремы приведено в работе [1].

Преобразование множества аксиом в систему аксиом

Система аксиом должна удовлетворять условию (3). Однако, при построении системы аксиом по набору прецедентов нормального и нештатного поведения системы при помощи генетического алгоритма [3] или алгоритма на основе направленного перебора [4] получается множество аксиом, для которого выполнение условия (3) не гарантировано. Для того, чтобы гарантировать выполнение условия (3), к множеству аксиом применяется преобразование, переводящее его в систему аксиом .

В качестве такого преобразования используется введение приоритета на множестве [1]. Это преобразование задается следующими формулами:

(5)

Аксиоманазывается тождественной аксиомой. Описанное преобразование зависит от выбранного во множестве порядка. Множество является системой аксиом, т. к. для него гарантированно выполняется условие (3). По сути, при разметке траектории системой аксиом каждому отсчету траектории ставится в соответствие аксиома из множества с наименьшим номером, выполняющаяся на отсчете , либо тождественная аксиома, если на отсчете не выполняется ни одной аксиомы из .

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

В данной работе предлагается другой способ преобразования множества аксиом в систему аксиом – построение показательного множества для множества . Это преобразование задается следующими формулами:

(6)

Для множества аксиом , полученного таким преобразованием, также гарантированно выполняется условие (3). Действительно, если t – отсчет некоторой траектории, то на отсчете t выполняется ровно одна аксиома , ее номер однозначно определяется множеством тех аксиом из , которые выполняются на отсчете t – аксиомы из этого множества входят в формулу (6) для без отрицания. Поэтому полученное таким преобразованием множество аксиом as является системой аксиом. Будем обозначать множество аксиом из , соответствующее аксиоме , через .

Можно выделить следующие преимущества предложенного способа построения системы аксиом по множеству аксиом:

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

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

Алгоритм поиска разметок

В данной работе предлагается модификация существующего алгоритма поиска разметок на основе DTW[5]. Алгоритм основан на принципе «скользящего окна» и состоит в следующем[1]:

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

, (7)

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

2.  Для каждой разметки эталонной траектории длины не больше t выполняется проверка:

(8)

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

Если хотя бы одно из неравенств (8) выполнено, то делается вывод о том, что соответствующий участок наблюдаемой траектории соответствует нештатному поведению класса .

3.  Переход на шаг 2 со сдвигом к следующему отсчету разметки наблюдаемой траектории . Если при этом достигается конец разметки , то алгоритм останавливается.

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

(9)

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

. (10)

Рассматривались следующие метрики.

1. Тривиальная метрика:

(11)

2. Метрика, основанная на коэффициенте Жаккара[6]:

(12)

3. Метрика Хемминга[7]:

(13)

4. Следующая метрика:

(14)

Численное исследование предложенного способа преобразования

системы аксиом

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

Численное исследование проводилось следующим образом:

1.  Запускался генетический алгоритм построения системы аксиом, в котором использовался существующий способ преобразования системы аксиом и алгоритм поиска разметок на основе DTW.

2.  Запускался генетический алгоритм построения системы аксиом, в котором использовался предлагаемый в данной работе способ преобразования системы аксиом и алгоритм поиска разметок.

3.  Лучшие системы аксиом, полученные в каждом случае, сравнивались по числу ошибок первого и второго рода.

Численное исследование проводилось на модельных данных. Рассматривались наборы данных с одним и двумя классами нештатного поведения, искажения по времени варьировались от 10 до 40 %, искажения по амплитуде варьировались от 10 до 30 %. Общая длина траекторий каждого из наборов данных составляла от 3000 до 10000 отсчетов.

При использовании предлагаемого способа преобразования системы аксиом и алгоритма поиска разметок с метрикой (14) уменьшение числа ошибок первого рода составило от 80 до 100%. При использовании других метрик выигрыша по числу ошибок первого рода удалось добиться только при искажениях по времени и по амплитуде, не превосходящих 20 %.

Заключение

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

·  Предложенное преобразование множества аксиом не требует задания порядка на множестве аксиом.

·  Предложенное преобразование множества аксиом сохраняет различимость траекторий.

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

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

Список литературы

1.  Коваленко и программные средства обучения алгоритмов распознавания участков фазовых траекторий: дис. … канд. физ.-мат. наук: 05.13.11 / МГУ им. . М., 2001.

2.  , , Щербинин семейство алгоритмов распознавания нелинейно искаженных фазовых траекторий динамических систем. // XIV Всероссийская научно-техническая конференция «Нейноинформатика-2012»: Сборник научных трудов. В 3-х частях. Ч. 1. М.: НИЯУ МИФИ, 2012. С. 266-276.

3.  Kovalenko D., Kostenko V. A Genetic Algorithm for Construction of Recognizers of Anomalies in Behaviour of Dynamical Systems. // Proceedings of the IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications, IEEEPress, China, 2010. P. 258-263.

4.  , , Костенко и автоматизированный метод построения алгоритмов распознавания участков фазовых траекторий. Труды 15ой Всероссийской конференции Математические методы распознавания образов (ММРО-15), С196-200, М.: Макс Пресс, 2011.

5.  Keogh E. J., Michael J. Pazzani. Derivative Dynamic Time Warping. // Proceedings of the First SIAM International Conference on Data Mining (SDM'2001), Chicago, USA. 2001.

6.  Raijski C. Entropy and metric spaces // C. Cherry (ed.). Information Theory. London: Butterworths, 1961. P. 41-45.

7.  Hamming R. Coding and information theory. Prentice Hall, USA, 1982.