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

Пусть обучающая выборка _ состоит из шести временных рядов: рис. 2.51–рис. 2.56. Экзаменационная выборка состоит из трёх временных рядов: рис. 2.57–рис. 2.59.Рисунок 2.51 — Ряд 1обуч. мн-ваРисунок 2.52 — Ряд 2обуч. мн-ваРисунок 2.53 — Ряд 3обуч. мн-ваРисунок 2.54 — Ряд 4обуч. мн-ваРисунок 2.55 — Ряд 5обуч. мн-ваРисунок 2.56 — Ряд 6обуч. мн-ваИсходя из приведенной выше постановки задачи, видно, что временныеряды на рис. 2.51, рис. 2.52 и рис. 2.56 сильно схожи между собой, а значит,67Рисунок 2.57 — Ряд 1 экз.

Рисунок 2.58 — Ряд 2 экз. Рисунок 2.59 — Ряд 3 экз.мн-вамн-вамн-вапринадлежат одному классу – назовем его класс1. Временные ряды рис. 2.53,рис. 2.54 и рис. 2.55 также схожи, но принадлежат другому классу – назовем егокласс2. Из экзаменационного множества (рис. 2.57–рис. 2.59) видно, что временной ряд на рис. 2.57, скорее всего, принадлежит классу класс1, временной рядна рис. 2.58 – классу класс2. Третий же временной ряд (рис.

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

Напротив, временные ряды на рис. 2.57 и рис. 2.58 изэкзаменационного множества не будут являться аномалиями, так как по формеочень «похожи» на отдельные временные ряды из обучающего множества.2.8Задача обнаружения аномалий в наборах временных рядов с однимклассом2.8.1Разработка метода обнаружения аномалийВ данной работе предлагается метод обнаружения аномалий в наборах временных рядов, который является модификацией метода, основанного на «точномописании исключения» [94].Исходная постановка задачи, данная в [94], следующая: для заданного конечного множества объектов I необходимо получить множество-исключение .Для этого на множестве I вводятся:1. функция неподобия (dissimilarity) ( ), ∈ , определенная на P(I) –множестве всех подмножеств и принимающая положительные вещественные значения;682.

функция мощности (cardinality) ( ), ∈ , определенная на P(I) –множестве всех подмножеств и принимающая положительные вещественные значения, такая, что для любых 1 ⊂ , 2 ⊂ выполняется1 ⊂ 2 ⇒ (1 ) < (2 );3. «фактор сглаживания» (smoothing factor) ( ) = ( ∖ ) * (() −( ∖ )), который вычисляется для каждого ⊆ .Тогда ⊂ будет считаться множеством-исключением для I относительноD и C, если его фактор сглаживания ( ) максимален [94].Неформально, множество-исключение – это наименьшее подмножество из, которое вносит наибольший вклад в его неподобие.

Фактор сглаживания показывает, насколько может быть уменьшено неподобие множества , если из негоисключить подмножество .На основании метода, описанного в [94], автором был разработан алгоритм − [3], предназначенный для обнаружения аномалий в наборах временных рядов. В качестве множества I рассматриваются множества _ ∪ {_ } для каждого _ ∈ _ .Функция неподобия для временных рядов будет задана следующим обра∑︀ ∑︀| − |2 , где =зом: ( ) = |1 | *| | .∈∈Сначала вычисляется – среднее для временных рядов из . В данномслучае это эквивалентно вычислению среднего для обычных векторов: – временной ряд из подмножества , | | – число элементов в | |.Функция неподобия вычисляется как сумма квадратов расстояний (используется евклидова метрика) между средним и векторами из , которая затем нормализуется – делится на число элементов во множестве .Функция мощности задаётся формулой ( ∖ ) = | 1|+1 .Формула для вычисления фактора сглаживания имеет прежний вид ( ) = ( ∖ ) * (() − ( ∖ )).Если множество-исключение , полученное для = _ ∪{_ } содержит _ , 1 ≤ ≤ | _ |, то _ является аномалией.692.8.2Алгоритм «TS-ADEEP»На основании описанного выше метода реализован непараметрический [95] алгоритм − [3] для определения аномалий в наборахвременных рядов для обучающего множества с одним классом.В табл.

2.8 приведен псевдокод алгоритма TS-ADEEP.Таблица 2.8 — Псевдокод алгоритма TS-ADEEPАлгоритм TS-ADEEP ( _ : обучающее множество, _ : экзаменационное множество)Результат: _ – набор временных рядов-аномалийначало _ = ∅Для от 1 до | _ |нцвыбрать _ ∈ _ = _ ∪ {_ }Найти множество-исключение в Если _ ∈ , то _ = _ ∪ {_ }кцвывести _ конецРассмотрим работу алгоритма − на примере. Пусть в обучающем множестве три временных ряда – рис.

2.60-2.62 (обозначим их для удобства1, 2, 3).Рисунок 2.60 — Ряд 1обуч. мн-ваРисунок 2.61 — Ряд 2обуч. мн-ваРисунок 2.62 — Ряд 3обуч. мн-ваНужно определить, является ли временной ряд, представленный нарис. 2.63 (обозначим его bel), аномалией.70Рисунок 2.63 — belТаблица 2.9 — Результаты вычисления фактора сглаживания для подмножеств IПодмножество Фактор сглаживанияcyl2, cyl3, bel0.370713cyl1, cyl3, bel0.370713cyl3, bel0.0677333cyl1, cyl2, bel0.370713cyl2, bel0.205667cyl1, bel0.45465bel0.136392cyl1, cyl2, cyl30.370713cyl2, cyl30.362783cyl1, cyl3-0.00448333cyl3-0.128708cyl1, cyl20.03515cyl20.0194417cyl10.0941917В соответствии с алгоритмом множество I будет состоять из указанныхчетырех временных рядов: = {1, 2, 3, }.

Рассматриваются все возможные подмножества из (за исключением пустого множества и самого множества ). Таких подмножеств 2|| − 2 = 14: {{1}, {2}, {3},{}, {1, 2}, {1, 3}, {1, }, {2, 3}, {2, }, {3, },{1, 2, 3}, {2, 3, }, {1, 3, }, {1, 2, }}. Для каждого из подмножеств по указанным формулам вычисляется фактор сглаживания.Результаты вычислений приведены в таблице 2.9.В данном случае максимальный фактор сглаживания (0.45465) имеет множество, состоящее из временных рядов = {1, }, следовательно, оно и71является множеством-исключением. А так как временной ряд попал в множество-исключение ({} ∈ ), то он является аномалией.2.8.2.1Вычислительная сложность алгоритма «TS-ADEEP»Нами была рассчитана вычислительная сложность алгоритма − .

Пусть – число временных рядов в рассматриваемом множестве . Для поиска множества-исключения надо рассмотреть булеан , заисключением пустого множества и самого . Общее число подмножеств за исключением пустого и самого равно равно 2 − 2 (не превосходит2 ). Таким образом, сложность алгоритма – (2 ), в связи с чем не рекомендуется использовать в качестве обучающих множеств большое число временныхрядов (более 20). Однако если учесть тот факт, что множество-исключение – этонаименьшее подмножество из , которое вносит наибольший вклад в его неподобие, то можно ограничиться рассмотрением подмножеств не более некоторогозаданного размера, что позволяет значительно сократить перебор без сниженияточности обнаружения аномалий в большинстве экспериментов, проведенных вработе.2.9Задача обнаружения аномалий в наборах временных рядов снесколькими классами2.9.1Разработка метода обнаружения аномалийВ данной работе предлагается метод обнаружения аномалий в наборах временных рядов с несколькими классами, который является обобщением методаобнаружения аномалий для случая обучающего множества, содержащего примеры одного класса.Обобщение является достаточно очевидным: разделив обучающее множество на подмножества, содержащие примеры только одного класса и последовательно применив к ним и каждому из временных рядов экзаменационногомножества метод обнаружения аномалий в наборах временных рядов с однимклассом, можно определить, является ли рассматриваемый временной ряд аномалией.

Если временной ряд является аномалией для каждого подмножества, тоон является аномалией и для всего обучающего множества.72Таблица 2.10 — Псевдокод алгоритма TS-ADEEP-MultiАлгоритм TS-ADEEP-Multi( _ : обучающее множество, содержащее примерынескольких классов; _ : экзаменационное множество)Результат: _ – набор временных рядов-аномалийНАЧАЛО _ = ∅Пусть – число классов, содержащихся в обучающем множестве _ _ ={ _ _1 , _ _2 , .., _ _ } –разбиение множества _ такое, что _ _ содержит только примеры класса , = 1..Для от 1 до | _ |нцвыбрать _ из _ Для от 1 до нц = _ _ ∪ _Найти множество-исключение в Если _ ∈ , то _ является аномалией длякласса (то есть не принадлежит ему)кцЕсли _ не принадлежит ни одному из классов _ _ , = 1..

,то _ = _ ∪ _кцвывести _ КОНЕЦ2.9.2Алгоритм «TS-ADEEP-Multi»На основании описанного выше метода реализован непараметрический [95] алгоритм − − , который является обобщением алгоритма − для случая обучающего множества, содержащего примерынескольких классов временных рядов.В табл. 2.10 приведен псевдокод алгоритма TS-ADEEP-Multi.Рассмотрим работу алгоритма − − на примере.

Пусть вобучающем множестве шесть временных рядов: три временных ряда из предыдущего примера, рис. 2.60-2.62 (обозначим их для удобства 1, 2, 3), и73три временных ряда, изображенных на рис. 2.64-2.66 (обозначим их для удобства 1, 2, 3).Рисунок 2.64 — Ряд 1обуч. мн-ваРисунок 2.65 — Ряд 2обуч. мн-ваРисунок 2.66 — Ряд 3обуч. мн-ваНужно определить, является ли временной ряд на рис. 2.67 (обозначим его) аномалией.Рисунок 2.67 — belВ соответствии с алгоритмом будут рассмотрены два множества – 1 ={1, 2, 3, }, 2 = { 1, 2, 3, }.

Аналогично алгоритму − рассматриваются все возможные подмножества из 1 и 2 и для каждого их них по указанным формулам вычисляется фактор сглаживания. Для 1множеством-исключением стало {1, } с фактором сглаживания 0.45465, для2 - {} с фактором сглаживания 0.385212. Так как временной ряд являетсяаномалией для обоих классов из обучающего множества, этот временной рядявляется аномалией по отношению и ко всему обучающему множеству.2.9.2.1Вычислительная сложность алгоритма «TS-ADEEP-Multi»Нами была рассчитана вычислительная сложность алгоритма − − .