Содержание к диссертации
Введение
ГЛАВА 1. Интеллектуальные методы выявления аномалий в темпоральных данных 13
1.1 Обнаружение аномалий как область интеллектуального анализа данных 13
1.2 Признаки и типы аномалий 15
1.3 Методы обнаружения аномалий и области их применения 24
1.4 Поиск аномалий в темпоральных данных 32
1.5 Выводы 52
ГЛАВА 2. Выявление аномалий в темпоральных данных на основе адаптивных марковских моделей 53
2.1 Постановка задачи обнаружения аномалий в дискретных временных
рядах 53
2.2 Марковское моделирование динамических процессов 59
2.3 Марковская модель с доходами, настраиваемая темпорально-разностным способом 70
2.4 Выводы 84
ГЛАВА 3. Гибридные нечетко-стохастические модели представления и обработки темпоральных знаний в задачах выявления аномалий 86
3.1 Элементы нечеткой логики и актуальность их объединения со стохастическими методами обнаружения аномалий 86
3.2 Поиск аномалий на основе доходной Марковской модели с нечеткими продукционными правилами 92
3.3 Идея реконструированного фазового пространства 100
3.4 Методы обнаружения аномальных паттернов в реконструированных фазовых пространствах 103 3.5 Метод прогнозирования аномальных событий на базе реконструированного фазового пространства с использованием нечетких моделей типа Сугено 111
3.6 Выводы 119
ГЛАВА 4. Апробация методов выявления аномалий в системах горочной автоматизации 121
4.1 Состояние проблемы информатизации сортировочных станций 121
4.2 Интеллектуализация управления маневрами на сортировочных горках 126
4.3 Актуальность задачи прогнозирования нештатной ситуации нагона отцепов на сортировочных горках 132
4.4 Прогнозирование нештатных ситуаций на сортировочной горке с помощью гибридных нечетко-стохастических методов выявления аномалий 135
4.5 Выводы 140
Заключение 142
Список использованных источников 144
- Методы обнаружения аномалий и области их применения
- Марковское моделирование динамических процессов
- Поиск аномалий на основе доходной Марковской модели с нечеткими продукционными правилами
- Актуальность задачи прогнозирования нештатной ситуации нагона отцепов на сортировочных горках
Методы обнаружения аномалий и области их применения
Аномалиями являются такие паттерны данных, которые не удовлетворяют предопределенному понятию нормального поведения [18]. Рис. 1 иллюстрирует наглядный пример аномалий в двумерном пространстве. Представленные данные разделены на две нормальных области, N1 и N2, заключающих в себе большинство наблюдений. Точки, лежащие вне этих областей, т.е. точки a1, a2, а также точки области A являются аномалиями.
Аномалии могут появиться в данных по различным причинам, таким как вредоносная активность (например, кибер вторжение в систему безопасности, террористическая активность или поломка технического устройства), однако все эти причины имеют общие характеристики, что является ключевым аспектом заинтересованности исследователей в решении задачи обнаружения аномалий. Проблема детектирования аномалий связана со смежными проблемами, такими как удаление шума [112] и искусственное добавление шума [94], в виду того, что решение этих проблем предполагает изучение ненужной или вредоносной информации в данных. Шум может быть определен как некоторое явление в исследуемых данных, которое находится вне зоны интереса аналитика, но является помехой для анализа исследуемых данных. Методы удаления шума позволяют избавиться от таких явлений до проведения анализа данных. Методы добавления шума предполагают «иммунизацию» статистической модели к аномальным наблюдениям [30].
Еще один класс проблем, к которому можно отнести задачу детектирования аномалий – это обнаружение новинок [76, 77]. Исследования, ориентированные на обнаружение новинок, в первую очередь направлены на детектирование ранее неизвестных паттернов данных, например, при поиске новой темы обсуждений в новостной полосе. Отличие обнаружения новинок от обнаружения аномалий в том, что найденная новинка может быть классифицирована не только как паттерн несоответствующего поведения, но и как паттерн области нормальных данных.
Ключевым аспектом любого подхода к обнаружению аномалий является природа анализируемых данных, которые в общем смысле являются набором примеров (также называемых объектами, записями, точками, векторами признаков, паттернами, событиями, случаями, наблюдениями и сущностями [84]). Каждый пример данных может быть описан рядом признаков (характеристик, переменных, величин). Признаки могут быть различных типов, таких как бинарные, дискретные и непрерывные. Каждый пример может быть описан как одним (одномерные данные), так и множеством (многомерные данные) признаков. В случае многомерности признаки бывают как одного, так и различных типов.
Природа признаков определяет применимость методов обнаружения аномалий. Например, статистические методы могут быть использованы для анализа только непрерывных или дискретных данных, представленных временными рядами. Подобно этому, в зависимости от природы данных определяется мера расстояния для методов поиска ближайшего соседа. Зачастую вместо исходных данных используются расстояния между парами примеров в виде матрицы расстояний (или матрицы подобий). Очевидно, что в таком случае методы, нуждающиеся в использовании исходных данных для анализа, не являются применимыми. Входные данные также могут быть дискретизированы на основе отношения между примерами.
Зачастую примеры связаны друг с другом. Тогда они образуют последовательные, пространственные или графовые базы данных. Последовательные данные представляют собой линейно упорядоченные примеры, к ним относятся данные временных рядов, геномные последовательности и др. Пространственные данные представляют собой примеры, связанные с их ближайшими соседями. К такому типу связи относят данные автомобильного движения, а также данные экологии. Также существуют пространственные данные с временным (темпоральным, последовательным) компонентом. Их относят к пространственно-темпоральным данным (например, данные климатических условий). В графовых данных примеры представлены вершинами графов, соединенными между собой ребрами, характеризующими отношения между примерами.
Базовый подход к обнаружению аномалий заключается в определении области нормального поведения и в отнесении любого наблюдения, лежащего вне данной области, к аномальному. Существует ряд трудностей, неблагоприятным образом влияющих на этот, казалось бы, простой подход. К ним относятся [18]: Сложность определения области, сочетающей в себе всевозможные линии нормального поведения. При этом граница между нормальным и аномальным поведением не всегда четкая.
Марковское моделирование динамических процессов
Анализ темпоральных данных имеет долгую историю. Методы статистического и спектрального анализа временных рядов использовались около шестидесяти лет назад [11, 21]. Наиболее ранними и проработанными направлениями в области Temporal Data Mining являются прогнозирование погоды, прогнозы на фондовом рынке и финансовой сфере, а также управление и мониторинг автоматических процессов. Наибольшее развитие методы интеллектуального анализа временных рядов получили в исследованиях распознавания речи [83, 90]. Здесь важнейшую роль играли такие методы как Марковские модели и искусственные нейронные сети.
В [44] приведена классификация видов информации, оперируемой методами интеллектуального анализа данных. Согласно автору, здесь можно выделить модели и паттерны.
Модель – это глобальное, часто абстрактное представление данных высокого уровня. Обычно модели представляют собой набор признаков, которые наиболее характерны для моделируемого временного ряда или базы временных рядов. При этом делят модели предсказательные и описательные. Предсказательные модели используют для прогнозирования и классификации, в то время как описательные применимы для обобщения исследуемой выборки. Например, авторегрессионный анализ может быть использован для прогнозирования будущих состояний процесса на основе его прошлых значений. В качестве другого примера предсказательной модели могут быть представлены Марковские модели, используемые для классификации временных рядов. Примерами описательных моделей могут служить спектрограммы (полученные при частотном анализе временных рядов) и кластеры (полученные при кластеризации временных рядов).
В отличие от глобальной структуры модели паттерн является локальной структурой, представляющей специфическое описание нескольких переменных или точек исходных данных. Паттерны могут представлять полезную информацию в случае их регулярного повторения во временном ряду.
Интеллектуальный анализ временных рядов в зависимости от достигаемых целей можно разделить на несколько групп: 1) Прогнозирование. Задача прогнозирования временных рядов представляет собой определение будущих значений исследуемого временного ряда на основе его предыстории. Графический вид задачи прогнозирования наглядно проиллюстрирован на Рис. 11, а в математическом представлении она выглядит так [32]: Для данных значений временного ряда X = (x1, …, xn) необходимо вычислить его k будущих ожидаемых значений (xn+1, …, xn+k).
На рис. 11а изображен временной ряд с периодической, а, следовательно, с предсказуемой структурой. Цель прогнозирования (Рис. 11б) – построение всех ожидаемых значений будущего времени, заключенных в окне прогнозирования. Задача усложняется если прогнозирование рекурсивно (Рис. 11в), т.е. при условии долговременного прогнозирования временных рядов с использованием ранее полученных значений в качестве дальнейших условий для прогноза.
Прогнозирование является важной областью исследования во многих сферах. Самым первым примером такой модели является прогнозирование солнечного затмения с помощью авторегрессионной модели [124]. Авторегрессионные модели применяются уже долгое время, в частности, для таких случаев, как шумоподавление и моделирование динамических систем. В 21 веке исследования в решении задач прогнозирования начали применяться и более сложные алгоритмы, как искусственные нейронные сети [61] или функциональная кластеризация [97]. В последнее десятилетие внимание исследований направлено на внедрение методов прогнозирования в наиболее актуальные сферы деятельности [32]. В [87] представлен метод Байесовского прогнозирования, который основан на иерархических скрытых Марковских моделях, в приложении к обнаружению структурных скачков в экономике. В [114] представлена динамическая модель генетического программирования, описанная применительно к индексу увеличения цен. В [13] приводится сравнение методов прогнозирования временных рядов для использования в сфере мониторинга состояния здоровья. Методы прогнозирования стали популярными даже в таких областях, как расчет ожидаемого туристического спроса [100]. При решении таких задач, как рекурсивное прогнозирование (Рис. 11в)), предложено использовать метод опорных векторов [47]. Также для решения данной задачи в [102] и в [4] предлагается гибридный метод прогнозирования.
2) Классификация
При классификации предполагается, что каждая исследуемая последовательность данных принадлежит одному из определенных заранее классов или категорий, а главная цель – автоматическое определение класса последовательности, поступившей на вход классификатора. При этом в первую очередь, необходимо обучить сам классификатор на основе таких признаков, которые бы позволили отличить последовательности одного класса от последовательностей другого класса. Рис. 12 иллюстрирует пример общей задачи классификации данных, формулировка которой аналогична формулировке задачи классификации последовательностей. Представим далее математическое описание задачи классификации:
Поиск аномалий на основе доходной Марковской модели с нечеткими продукционными правилами
С точки зрения проблематики поиска аномалий последовательностями являются упорядоченные цепочки событий. Такие события могут представляться бинарными, дискретными или непрерывными в зависимости от прикладной области и способа представления данных. В реальных условиях наиболее применимыми являются представление данных в виде дискретных и непрерывных рядов. Так как непрерывные временные ряды являются трудномоделируемыми в связи с возможностями современных вычислительных устройств, практически во всех случаях предусмотрено преобразование непрерывных временных рядов в дискретные (дискретизация), либо, как в частном случае поиска контекстуальных аномалий, преобразование к виду одиночных аномалий. Первый вариант представляет собой менее развитую область исследований, в связи с чем в настоящей диссертационной работе сделан больший акцент именно на обработку дискретных временных рядов. Про второй способ преобразования будет сказано в третьей главе.
Дискретные временные ряды представлены в виде упорядоченных событий (или наборов событий), при этом каждое событие принадлежит определенному конечному множеству (или алфавиту). Например, текстовый документ является последовательностью слов, технологический процесс представим в виде последовательно выполняемых операций, а компьютерную программу можно представить в виде последовательности исполнения определенных команд или системных вызовов. Как было описано выше, детектирование символьных последовательностей, не удовлетворяющих типовому поведению, является популярным средством достижения целей систем контроля и диагностики, внедряемых в различных областях применения. При этом каждый метод обнаружения имеет применение только в специфической области, а решение проблемы поиска дискретных секвенциальных аномалий в общем ее смысле на данный момент не является возможным. Данный недостаток существующих разработок связан с фундаментальным различием природы нормальных последовательностей и аномалий в различных прикладных областях, в связи с чем метод, эффективно проводимый в одном приложении, может оказаться бесполезным в другом.
Хотя все существующие методы и предполагают одинаковую цель, заключающуюся в поиске аномалий в дискретных последовательностях, более глубокий анализ показывает, что формулировки задачи, решаемой ими, тесно связаны со структурой самих методов. Наиболее распространенными являются четыре формулировки задачи поиска символьных секвенциальных аномалий:
Детектирование немаркированных аномальных последовательностей на основе их сравнения с известной базой данных. При такой формулировке задачи объектом интересов системы детектирования являются последовательности, содержащие в себе известные элементы в порядке, не удовлетворяющем типичному поведению. При этом нормальными будут считаться уже завершенные последовательности, помеченные экспертом в соответствии с отрицательной принадлежностью к аномальному поведению. Данная формулировка проблемы является наиболее часто используемой при поиске аномалий в последовательностях данных. Большинство методов, решающих задачу обнаружения в такой ее формулировке, при тестировании присваивают каждой обрабатываемой последовательности определенное число, называемое степенью аномальности. На основе степеней аномальности далее выявляются «наиболее аномальные» последовательности. Решение задачи детектирования данных в немаркированных последовательностях может решаться четырьмя способами:
Решение на основе меры схожести. В данном случае каждая тестовая последовательность рассматривается как единичный элемент анализа, вследствие чего детектирование происходит на уровне одиночных аномалий. Решение предполагает использование методов детектирования аномалий на основе меры схожести тестового элемента и соответствующего обучающего элемента. Недостатками такого способа являются зависимость эффективности детектирования от выбранной меры схожести.
Решение с помощью скользящего окна. Данный способ решения предполагает разбиение тестовой последовательности на небольшие окна, которые будут считаться единичными элементами. При этом степень аномальности каждой последовательности оценивается в результате вычисления (суммирования) оценок всех окон, содержащихся в ней. Недостатком решения на основе скользящего окна является зависимость эффективности детектирования от длины окна.
Решение с помощью моделей Маркова. Такой способ решения предполагает упреждение появления определенного символа в тестируемой последовательности, используя вероятностную модель. Степень аномальности последовательности вычисляется на основе оценки вероятностей появления всех ее элементов и переходов между элементами. Недостатком таких методов является высокая степень зависимости точности детектирования от статистических характеристик обучающих последовательностей и необходимости выполнения условий Марковости, подробнее о которых будет сказано ниже.
Актуальность задачи прогнозирования нештатной ситуации нагона отцепов на сортировочных горках
Тогда завершенной последовательностью будет являться временной ряд базовых элементов [oi, 02, …, от], Оі Є О. Такая последовательность может быть определена экспертным путем как нормальная или аномальная. Однако, как показано в [69], недостаточно использовать один базовый элемент в качестве состояния системы. Для описания поведения кибер системы необходимо использовать модель переходов между состояниями. Под данной моделью понимается представление состояния st, оперируемого методом обнаружения аномалий, в виде короткой последовательности или комбинации темпорально связанных базовых элементов, т.е. Si = [oi+1,oi+2,...,oi+n]. (28)
Таким образом, видом данных, приемлемым для метода детектирования аномалий в секвенциальных данных в случае приложения к тематике поиска вторжений в кибер системах, является последовательность состояний, каждое из которых представляет паттерн темпорально связанных элементов исходных данных, заключенных в скользящем окне заданной длины п. При этом, для данных из [37] было принято считать оптимальным для п значение, равное 6 [69]. 2. Экспертное утверждение доходов состояний на основе (21). 3. Установка исходных данных для алгоритма:
Преобразование обучающего множества паттернов вида Ж= \Хи Х2, …, XN] , ХІ = [хц, ХІ2, …, ХЩІ)], Xtk Є S, к виду пар состояний с присвоенным доходом {xt, xt+i, r(xt)} (t = il, i2, …, iT(i), iT(i)+l = (z+7)l). - Установка критерия останова для алгоритма. Введение линейных базисных функций р(х) и константы . Начальное время t = 0. Обозначение тестовой последовательности состояний Xtest = [xtest(lx XtesH2), …, xtest(T)\ и установка порогового значения для классификации . 4. Обучение (до достижения критерия останова): Вычисление z(t) по формуле (26). Вычисление A(t) по формуле (24). Вычисление B(t) по формуле (25). t = t+l. Вычисление весового вектора по формуле (23). 5. Тестирование: - Вычисление вероятности развития аномалии для каждого состояния тестовой последовательности Pa(xtest(t)) по формуле (22) с учетом условия формулы (20). Вычисление суммарной вероятности развития аномалий для тестовой последовательности Pa(Xtest) по формуле (19). - Вывод решения об аномальности тестовой последовательности путем сравнения Pa(Xtest) с порогом . При превышении данного порога тестовая последовательность помечается как аномальная.
Далее в [119] также показана эффективность применения вышеописанного алгоритма темпорально-разностного обучения при оценке исхода завершенных последовательностей. Не смотря на возможность анализа «немарковских» последовательностей, данный метод имеет ряд недостатков, среди которых невозможность его прямого использования для упреждения целевых (или аномальных) исходов тестовых немарковских последовательностей, являющегося одним из ключевых особенностей классического темпорально-разностного обучения, что делает невозможным использование метода в системах поддержки принятия упреждающих решений. Кроме того, при TDSAD моделировании Марковского процесса используется только информация о частоте переходов без учета вероятности перехода между состояниями, важных при оценке стохастических процессов. В ходе настоящей диссертационной работы были проделаны исследования по модификации темпорально-разностного обучения Марковской модели. Результаты следующие.
Первая проблема может быть решена на этапе тестирования путем замены суммарной вероятности развития аномалий для всей последовательности оценочной функцией вероятности развития аномалии для каждого состояния тестовой последовательности [104, 105, 106, 107]. Для того, чтобы при этом оценка оставалась робастной к единичным случайным отклонениям, а также для учета тенденции развития аномалии, в ходе настоящего диссертационного исследования было принято ввести критерий учета вероятностей развития аномалии из предшествующих состояний при оценке текущей вероятности. Следуя вышеизложенному, можно записать формулу (18) в виде РаЫ = P((xlfx2 хт)єАпот(х)\Хі = xt) + a- /U ), (29) где - коэффициент зависимости оценки текущей вероятности развития аномальной последовательности от предыдущей тенденции развития аномалии.
Эффективность упреждающего алгоритма поиска аномалий можно показать в применении к стохастическому временному ряду с добавленными в него целевыми паттернами. Примером может служить стохастический временной ряд, в котором, к примеру, аномальным событием является наступление терминального состояния реализации ранее описанной бенчмарки Coffee [58, 106]. В этом случае реализация Coffee будет считаться паттерном, развитие которого приводит к аномальному исходу. Обучающий временной ряд включал в себя 93% последовательностей случайных величин и 7% аномальных паттернов, при этом предполагалось, что эксперту известны только терминальные состояния аномальных паттернов, т.е. моменты наступления аномальных событий (Рис. 21).