Диссертация (Исследование и разработка методов и алгоритмов обобщения знаний для систем поддержки принятия решений реального времени), страница 13

Пусть – число временных рядов в рассматриваемом множестве , 1 < – максимальное число временных рядов, принадлежащих74одному и тому же классу, k – число классов. Для поиска множества-исключениянадо рассмотреть булеан , за исключением пустого множества и самого . Общее число подмножеств за исключением пустого и самого не превосходит 2 .

Таким образом, сложность алгоритма – ( * 2 ), в связис чем не рекомендуется использовать в качестве обучающих множеств большоечисло временных рядов одного и того же класса (более 20). Аналогично алгоритму «TS-ADEEP», можно сократить перебор, ограничившись рассмотрениемподмножеств не более некоторого заданного размера.2.9.3Использование деревьев решений для обнаружения аномалий внаборах временных рядов с несколькими классамиВ главе 1 были рассмотрены наиболее успешные для индуктивного формирования понятий модели представления знаний – деревья решений. Эта модельиспользуется в ряде алгоритмов, относящихся к категории «обучение с учителем». В соответствии с этой стратегией на основе обучающей выборки, содержащей примеры и контрпримеры объектов определённого класса, строится дереворешений, представляющее собой особую форму теста, позволяющего в дальнейшем успешно классифицировать новые примеры, не вошедшие первоначально вобучающую выборку.Известен ряд алгоритмов, результатом работы которых будет построенноев определённой форме дерево решений: алгоритм ДРЕВ [38], алгоритм, основанный на метрике Хэмминга [38], ID3 [35] и различные модификации этихалгоритмов – C4.5 [96], ID5R [97] и другие – обрели широкое распространениеи зарекомендовали себя в широком спектре приложений.Формально дерево решений – это взвешенный ориентированный граф = (, ).

В множестве вершин выделим вершину 0 ∈ – корень дерева.Все вершины разделим на два класса: ⊂ – множество внутренних вершины(узлов) дерева; включает в себя такие вершины, из которых выходят дуги; ⊂ – множество внешних, конечных, вершин дерева (листьев); включаетв себя такие вершины, из которых дуги не выходят; и образуют разбиениемножества вершин дерева решений : ∩ = ∅, ∪ = .Внутренние вершины дерева взвешены (помечены) именами атрибутов,используемых при признаковом описании объектов. Вершины-листья взвешены (помечены) именами классов.75Каждая дуга дерева решений взвешена условием «атрибут = значениеатрибута» (для качественных значений атрибутов) либо «атрибут значение атрибута» (для количественных значений атрибутов, ∈ {≥, >, <, ≤}), где «атрибут» – имя атрибута в вершине, из которой исходит дуга , «значение атрибута»– одно из возможных значений (количественное или качественное) признака «атрибут».Рассмотрим возможность применения алгоритмов построения деревьев решений для работы с такими объектами, как временные ряды.

Из перечисленных выше алгоритмов возьмём алгоритм ID3, поскольку он позволяет строитьдеревья решений, отличные от бинарных, и успешно работает с символьнымиданными. Этот алгоритм также позволяет классифицировать примеры в случаеих принадлежности к нескольким классам (2, 3 и более). Исходными данными для алгоритма построения дерева решений является обучающее множество,представленное в виде таблицы. Каждая строка таблицы содержит описание одного из примеров с указанием того, к какому классу относится данный пример.Описание примера представляет собой строку значений атрибутов (признаков),характеризующих свойства данного объекта.Для рассмотренного ранее алгоритма «TS-ADEEP-Multi» использовалисьисходные данные, представленные в виде таблицы 2.7.

Каждая строка таблицы 2.7 представляет описание одного из временных рядов, причём явно указано,к какому классу принадлежит этот ряд. Чтобы иметь возможность использоватьэти данные как обучающую выборку для построения дерева решений алгоритмом ID3 применим к числовым данным преобразование в символьную форму.Преобразование выполняется с помощью алгоритма SAX, описанного ранее. Результат преобразования представлен в таблице 2.11 (использовался алфавит из10 символов).

Таблица 2.11 с формальной точки зрения может быть использована как исходные данные (обучающая выборка) для алгоритма ID3: каждая строка представляет описание одного объекта – временного ряда; известно, к какомуклассу относится объект (CY, BE, FU), атрибутами являются моменты времени(0, 1, 2, .

. . 9), а их значениями – показания датчиков в дискретном символьномпредставлении в соответствующие моменты времени.На рисунке 2.68 представлено дерево решений, полученное алгоритмомID3 по обучающей выборке, данной в табл. 2.11.76Таблица 2.11 — Описание ситуаций на объекте для случая 1 датчика символьное представлениеtСит1Сит2Сит3Сит4Сит5Сит6Сит7Сит8Сит90BCBCBCDCB1ECBCBDICG2IIIECDIJJ3IIIHEHHII4HIIJGJDHG5IFIJHGDFF6ECDCIDDCD7BCBCJCDCC8BCCCBDBCB9BCCCBCDCCКСCYCYCYBEBEBEFUFUFUРисунок 2.68 — Дерево решенийПолученное дерево решений можно использовать для обнаружения аномалий в наборах временных рядов: если оно относит некоторый временной ряд к одному из классов , или , то рассматриваемый временной ряд неявляется аномалией.

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

Кроме того, при значительном количестве ситуаций, используемыхкак исходные данные для задачи диагностики/обнаружения аномалий, модель77может быть неэффективной, в связи с чем необходимо использовать лишь «существенные» данные из набора исходных ситуаций.2.10Выводы ко второй главеВо второй главе было сделано следующее:1. Рассмотрено понятие динамического объекта, представляющего собойвременной ряд. Дано определение временного ряда, характеристикивременных рядов и способы их представления.2.

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

Приведен обзор наборов данных, используемых в работе.6. Предложен метод и разработан алгоритм TS-ADEEP обнаружения аномалий для наборов временных рядов с одним классом, рассчитана еговычислительная сложность.7. Предложен метод и разработан алгоритм TS-ADEEP-Multi обнаружения аномалий для наборов временных рядов, относящихся к несколькимклассам, рассчитана его вычислительная сложность.78Глава 3. Задача обобщения для динамических объектов. Общий случай.В главе 2 рассматривалась лишь частная задача и методы ее решения – длянаиболее простго случая, когда динамический объект обобщения представляетсобой временной ряд.

При этом время рассматривалось лишь формально, неявно, тогда как в реальных системах поддержки принятия решений требуется явноучитывать фактор времени.Общий случай представляется гораздо более сложным: динамический объект обобщения можно рассматривать как набор временных рядов (см. представление в табл. 1.2), причем длина временных рядов может быть различной.В данной главе описано применение аппарата темпоральных деревьев решений, позволяющее решать задачу обобщения для динамических объектов спроизвольным числом атрибутов при условии использования символьного описания такого атрибута (временного ряда). Методы описания временного ряданабором символов были подробно рассмотрены в главе 2.Нашей целью является исследование случая, когда динамический объектобобщения характеризуется q>1 признаками. Предположим (для примера), чтоq=3. Тогда в представлении, введенном в главе 1 (см.

табл. 1.2) динамическийобъект обобщения, или динамическую ситуацию, можно рассматривать как набор из трех временных рядов. Зададим некоторое = * – максимальный интервал времени, на котором будем рассматривать ситуацию – такой промежутоквремени соответствует максимальной длине временного ряда. Пример динамического объекта обобщения приведен в табл. 3.1: здесь длина временного интервала = 10, каждая строка таблицы представляет собой значения одногоиз параметров на рассматриваемом интервале. Отметим, что представление втабл. 3.1 в точности соответствует представлению динамического объекта, данному в табл. 1.2.Таблица 3.1 — Пример динамического объекта обобщения для случаяполучения наблюдений от трёх датчиковt0123456789Датчик1 -0.56-0.62-0.19 0.64 1.451.39-0.69-0.61-0.66-0.62Датчик2 -0.98-0.91-0.59-0.530.300.80 1.25 1.41 -0.98-0.99Датчик3 -0.54-0.44-0.28 0.75 1.610.40-0.45-0.53-0.38-0.6179Пример набора динамически изменяющихся ситуаций (Сит1-Сит4) дляслучая, когда поведение сложной системы контролируется показаниями нескольких датчиков (q=3), приведён в табл.

3.2: здесь длина временного интервала, накотором ведутся наблюдения за ситуацией, = 10, для описания каждой ситуации используются показания трёх датчиков на заданном интервале, каждаяситуация относится к классу (соответствует нормальному состояниюсистемы, поведение которой следует контролировать). Заданный таким образомнабор ситуаций предлагается использовать как исходные данные для решениязадачи обобщения.Таблица 3.2 — Набор ситуаций на объекте для случая 3 датчиковt0123456789КСДатчик1 -1.07-0.13 0.85 0.96 0.81 0.84 -0.08-1.01-0.90-1.13Сит1 Датчик2 -0.72-0.70 1.25 1.23 1.27 0.03 -0.76-0.71-0.71-0.74 NORMДатчик3 -0.94-0.84 1.06 0.97 1.01 1.04 -0.35-0.92-0.83-0.80Датчик1 -0.56-0.62-0.19 0.64 1.45 1.39 -0.69-0.61-0.66-0.62Сит2 Датчик2 -0.98-0.91-0.59-0.53 0.30 0.80 1.25 1.41 -0.98-0.99 NORMДатчик3 -0.54-0.44-0.28 0.75 1.61 0.40 -0.45-0.53-0.38-0.61Датчик1 -0.45 1.05 1.25 0.61 -0.35-0.50-0.39-0.27-0.89-0.28Сит3 Датчик2 -0.68-0.67 1.63 1.07 0.69 0.01 -0.59-0.70-0.64-0.53 NORMДатчик3 -1.01 0.50 1.35 0.89 0.33 0.18 -0.34-0.75-0.98-0.65Датчик1 -0.72-0.70 1.25 1.23 1.27 0.03 -0.76-0.71-0.71-0.74Сит4 Датчик2 -0.98-0.91-0.59-0.53 0.30 0.80 1.25 1.41 -0.98-0.99 NORMДатчик3 -0.68-0.67 1.63 1.07 0.69 0.01 -0.59-0.70-0.64-0.53Набор динамических объектов обобщения, или динамических ситуаций,может описывать различные состояния сложного технического объекта или системы, причем объекты могут описывать как нормальное состояние системы,так и ненормальное, или аномальное, то есть соответствующее неисправности.В таком виде набор динамических объектов может использоваться как исходныеданные для решения задачи диагностики – определения неисправности системыи указания причин, вызвавших неисправность.

Рассмотрим задачу диагностикиболее подробно.803.1О технической диагностикеТехническая диагностика [98–100] – научно-техническая дисциплина, изучающая и устанавливающая признаки дефектов технических объектов, а такжеметоды и средства обнаружения и поиска (указания местоположения) дефектов.Основной предмет технической диагностики – организация эффективной проверки исправности, работоспособности, правильности функционирования технических объектов (деталей, элементов, узлов, блоков, заготовок, устройств, изделий, агрегатов, систем, а также процессов передачи, обработки и храненияматерии, энергии и информации), то есть организация процессов диагностирования технического состояния объектов при их изготовлении и эксплуатации, втом числе во время, до и после применения по назначению, при профилактике,ремонте и хранении.