Содержание к диссертации
Введение
ГЛАВА 1. Интеллектуальные методы обнаружения аномалий в темпоральных данных 12
1.1 Обнаружение аномалий как область интеллектуального анализа данных 12
1.2 Признаки и типы аномалий 14
1.3 Методы обнаружения аномалий и области их применения 23
1.4 Поиск аномалий в темпоральных данных 31
1.5 Выводы 51
ГЛАВА 2. Обнаружение аномалий в темпоральных данных на основе стохастических марковских моделей 52
2.1 Постановка задачи обнаружения аномалий в дискретных временных рядах 52
2.2 Марковское моделирование динамических процессов 58
2.3 Марковская модель с доходами, настраиваемая темпорально-разностным способом 69
2.4 Выводы 83
ГЛАВА 3. Обнаружение аномалий в темпоральных данных на основе нечетко-продукционных моделей 85
3.1 Элементы нечеткой логики и актуальность их объединения со стохастическими методами обнаружения аномалий 85
3.2 Поиск аномалий на основе доходной Марковской модели с нечеткими продукционными правилами 91
3.3 Идея реконструированного фазового пространства 99
3.4 Методы обнаружения аномальных паттернов в реконструированных фазовых пространствах 102
3.5 Метод прогнозирования аномальных событий на базе реконструированного фазового пространства с использованием нечетких моделей типа Сугено 110
3.6 Выводы 118
ГЛАВА 4. Аппробация методов упреждающего обнаружения аномалий в системах горочной автоматизации 120
4.1 Состояние проблемы информатизации сортировочных станций 120
4.2 Интеллектуализация управления маневрами на сортировочных горках 125
4.3 Актуальность задачи прогнозирования нештатной ситуации нагона отцепов на сортировочных горках 131
4.4 Прогнозирование нештатных ситуаций на сортировочной горке с помощью гибридных нечетко-стохастических моделей 134
4.5 Выводы 139
Заключение 141
Список использованных источников 143
- Методы обнаружения аномалий и области их применения
- Марковское моделирование динамических процессов
- Поиск аномалий на основе доходной Марковской модели с нечеткими продукционными правилами
- Интеллектуализация управления маневрами на сортировочных горках
Методы обнаружения аномалий и области их применения
Интеллектуальный анализ данных, называемый также Data mining, можно определить как деятельность, позволяющую выделить некоторую новую значимую информацию, содержащуюся в большом объеме данных [65]. Главная задача интеллектуального анализа данных – это извлечение скрытых последовательностей, непредвиденных тенденций или других явно невидимых связей в данных – решение которой достигается путем использования методов машинного обучения, статистики и обработки баз данных. На сегодняшний день такая относительно новая дисциплина находит широкое использование в большинстве сфер деятельности, таких как экономика, медицина, а также диагностика и контроль технологических процессов. Приведем пример такого применения. Имеется огромная база данных о заявках на кредиты, содержащая различную информацию о персональных данных заявителей (включая истории погашения кредита). При этом работнику банка необходимо решить, можно ли одобрить следующую заявку конкретного лица на кредит или нет. Такие данные можно представить в виде множества паттернов, которые стремятся к неудовлетворительному состоянию, позволяя определить, будет ли начат следующий паттерн или нет (т.е. будет ли одобрена следующая заявка на кредит конкретного заявителя). Другим примером интеллектуального анализа данных может служить обработка данных, получаемых с искусственных спутников Земли и занимающих терабайтные объемы, с целью извлечения полезной информации и удаления остальных данных. Также Data mining позволяет обнаруживать потенциальные зарождения или местонахождения полезных ресурсов и ископаемых, прогнозировать экологические катастрофы, находить злокачественных опухоли у больных раком и др. Данный список областей применения интеллектуального анализа данных растет с каждым годом.
Выявление аномалий является важной задачей интеллектуального анализа данных, рассматриваемой во многих областях исследования и сферах применения [17]. Выявление аномалий (или детектирование аномалий, поиск аномалий) относится к проблеме нахождения паттернов данных, не соответствующих ожидаемому поведению. Такие несоответствующие паттерны в зависимости от прикладной области относят к аномалиям, выбросам, несогласованным наблюдениям, исключениям, аберрациям, сюрпризам, особенностям и загрязнителям. Наиболее часто используемыми и взаимозаменяемыми понятиями в контексте обнаружения аномалий являются «аномалия» и «выброс». В некоторых приложениях аномалии также называют целевыми (или особыми) событиями. Обнаружение аномалий широко используется в таких областях применения как обнаружение вторжений в компьютерной безопасности, обнаружение мошенничества при проведении банковских транзакций, выявление заболеваний раком, поиск отказов в системе безопасности, слежение за вражеской активностью, контроль движения поездов и др.
Необходимость обнаружения аномалий заключается в том, что присутствие аномалий в данных представляет собой важную (или даже критически важную) информацию применительно к широкому ряду областей применения. Например, в терминологии компьютерной безопасности паттерн аномального трафика может означать посылку незащищенных данных в неавторизованном направлении [64]. Аномальный снимок МРТ может означать присутствие злокачественной опухоли [41]. Аномалии в транзакциях по кредитной карте могут помочь в обнаружении попыток ее взлома [22]. Задача обнаружения аномалий также решается при обнаружении отказов в системах космических аппаратов. Здесь, к примеру, аномальные показания датчиков космического корабля могут сигнализировать о сбоях в его компонентах [59]. Детектирование выбросов или аномалий в данных было впервые исследовано в девятнадцатом веке в области статистики [30]. Спустя некоторое время проблематика обнаружения аномалий была поднята во множестве областей исследования. Многие из предложенных методов обнаружения аномалий создаются специально для определенной области применения [67, 147, 149], однако существуют и междисциплинарные методы [17, 18, 62].
Аномалиями являются такие паттерны данных, которые не удовлетворяют предопределенному понятию нормального поведения [17]. Рис. 1 иллюстрирует наглядный пример аномалий в двумерном пространстве. Представленные данные разделены на две нормальных области, N1 и N2, заключающих в себе большинство наблюдений. Точки, лежащие вне этих областей, т.е. точки a1, a2, а также точки области A являются аномалиями.
Марковское моделирование динамических процессов
Решение общей задачи классификации производится в 3 этапа. На первом в систему подаются обучающие данные с помеченными в соответствии с классовой принадлежностью элементами. Система на основе заданного алгоритма обучается разделять обучающие данные на основе их признаков. Данный этап изображен на рис. 12а (обучающее множество состоит из данных двух классов – C1 и C2 – определяемых границами, созданными при обучении классификатора). Второй этап классификации заключается во введении в систему тестовых данных, не помеченных в соответствии с принадлежностью их к определенному классу (Рис. 12б). Каждый элемент тестовых данных автоматически помечается обученным классификатором после чего (при необходимости) система создает новые границы классов, что является третьим этапом классификации (Рис. 12в).
Первый подход, направленный на классификацию временных рядов, представлен в [5]. Однако данный метод не имел высокой эффективности из-за сложной интерпретации его результатов. Позднее в [56] был предложен метод, более применимый для реальных условий. В настоящее время создано немалое количество подходов, а также произведено множество сравнений их результатов при классификации различных темпоральных данных. Так, например, в [90] представлен развернутый обзор, а также бенчмаркинг трех типов методов классификации: методов k-ближайших соседей, методов опорных векторов, а также методов, основанных на деревьях решений. Было показано, что все три типа одинаково эффективно справляются с задачей классификации временных рядов. Однако данная применимость ограничивается только набором представленных данных. Более широко используемый классификатор на основе поиска ближайшего соседа представлен в [115]. Недостатком данного метода была его большая вычислительная сложность. Для преодоления этой проблемы в [100] предложен метод построения шаблона темпоральной последовательности путем усреднения схожих паттернов. При этом классификация происходила путем сравнения тестовой последовательности с одним шаблоном каждого класса. Среди других популярных моделей классификации временных рядов можно выделить скрытые Марковские модели [32], модели авторегрессии — скользящего среднего [20], искусственные нейронные сети [33], а также байесовский классификатор [13]. Однако все данные методы все же уступают в точности методу поиска ближайшего соседа [115]. Стоит отметить широко известную проблему классификации – так называемое «переобучение». Данное понятие заключает в себе тот факт, что при достижении определенного объема обучающего множества большинство методов классификации теряют свою эффективность. В этой связи возникает проблема выбора репрезентативного множества данных для обучения. Один из вариантов решения этой проблемы представлен в [88], где авторы путем введения критерия остановки производят отбор данных для обучения классификатора.
В настоящее время существует множество случаев применения методов классификации темпоральных данных, среди которых распознавание речи, распознавание жестов, онлайн верификация подписей и др. Все они основываются как на сравнении тестируемых данных с типовыми паттернами, так и на сравнении с моделью анализируемого процесса. Классификация на основе сравнения с паттернами предполагает наличие доступных прототипов последовательностей для каждого класса. При этом классификатор производит обзор всех прототипов в поиске наиболее близкого паттерна к исследуемой последовательности. Нередко набор паттерн-прототип и тестовый паттерн имеют различные длины. В таком случае являются применимыми так называемые методы динамического трансформирования времени, позволяющие выравнивать последовательности [78]. Методы на основе сравнения исследуемых данных с моделью процесса не менее популярны для классификации последовательностей. Чаще всего это методы, использующие скрытые Марковские модели. Здесь классификаторы обучаются на основе всех паттернов каждого класса, после чего производится определение того, какой из полученных классификаторов наиболее вероятно мог бы быть построен из тестируемой последовательности.
Кластеризация временных рядов предполагает разделение множества последовательностей на группы, основанное их схожести друг с другом и отличия от последовательностей остальных групп. Рис. 13 иллюстрирует общий вид возможных путей решения задачи кластеризации данных. Как можно заметить, основная проблема решения – определение числа возможных кластеров.
Формулировка задачи кластеризации зависит от конкретной проблематики. Здесь разделяют 2 типа формулировки: кластеризация всей выборки данных и кластеризация определенной последовательности. В первом случае целью кластеризации является группировка базы данных временных рядов, содержащей множество последовательностей, на кластеры так, что внутри каждого кластера окажутся только схожие последовательности. Математически такую цель можно выразить следующим образом: Дана база данных временных рядов DB, а также меры схожести D(Xi} Xj), ХІ Є DB, Xj Є DB. Необходимо найти набор кластеров С = {с,-}, где с,- = {Хк \ Хк Є DB}, такой, что расстояния между кластерами разных групп будет как можно большим, а расстояния между кластерами одной группы как можно меньшим. Более формально это выглядит как
Для решения задачи кластеризации всего множества временных рядов разработано множество методов, среди которых наиболее популярные самоорганизующиеся карты [92], скрытые Марковские модели [96] и методы опорных векторов [120]. Одним из интересных алгоритмов является предложенный в [38] алгоритм максимизации ожидания для кластеризации. Однако такая кластеризация имеет один существенный недостаток, заключающийся в необходимости использования предопределенной заранее модели. Специфичный обзор методов кластеризации был произведен в [6]. Автор данного обзора предопределяет расширение действия методов решения задачи классической кластеризации данных на кластеризацию временных рядов. В [42] приведена категоризация методов кластеризации, содержащая пять категорий кластеризации: разделения, иерархическая, основанная на плотности, основанная на разграничении и основанная на моделировании. Развернутый обзор конкретно методов кластеризации временных рядов, их достоинств и недостатков приведен в [69]. Также в [69] приведено исследование применения различных категорий кластеризации для обработки временных рядов, в результате которого был сделан вывод о применимости трех типов кластеризации (кластеризация разделения, иерархическая кластеризация и кластеризация на основе моделирования).
Другой случай формулировки задачи кластеризации временных рядов заключается в разбиении одной последовательности данных на несколько паттернов. Одним из первых подходов к решению подобной задачи был предложенный в [45] метод на основе неперекрывающихся окон. Ширина окна при этом выбиралась на основе исследования периодической структуры при анализе спектра, получаемого при дискретном преобразовании Фурье. Данный метод ограничен тем, что в реальных случаях временные ряды не имеют постоянной периодической структуры, в связи с чем при разделении на окна можно потерять важную информацию об исследуемой последовательности темпоральных данных. Данный недостаток долгое время оспаривался в исследованиях, принимались решение о его применимости только в других сферах [83], а также о его бесполезности при кластеризации [54]. В [28] впервые было доказано обратное. Проблема разделимости на окна решалась путем создания алгоритма, не требующего использования всех паттернов последовательности для кластеризации.
Поиск аномалий на основе доходной Марковской модели с нечеткими продукционными правилами
Темпорально-разностное обучение наименьших квадратов LSTD() в отличие от классического алгоритма TD(), позволяющего инкрементально обновлять правило при поступлении каждого нового значения на вход классификатора, является алгоритмом, базирующемся на построении модели на основе априорных знаний. Модель, построенная при темпорально-разностном обучении наименьших квадратов, содержит в себе априорную статистическую информацию, схожую с информацией, извлекаемой при построении Марковской модели с доходами. Таким образом, алгоритм темпорально-разностного обучения наименьших квадратов может быть применен для оценки частоты появления целевых аномальных событий путем прогнозирования исходов Марковского доходного процесса (22) с учетом паттернов, предполагающих «немарковское» развитие.
Подробное описание использования данного алгоритма в применении к детектированию целевых событий в секвенциальных данных было приведено в [116]. Такой подход был назван как детектирование секвенциальных аномалий на основе темпорально-разностного обучения (Temporal-Difference Learning based Sequential Anomaly Detection или TDSAD). Авторы использовали данный метод для детектирования аномальных последовательностей системных вызовов в компьютерных системах, представляющих многошаговые кибер атаки [36]. Представленный алгоритм можно описать в виде следующих шагов:
Поиск вторжений в кибер системах, как предложенная тематика использования метода, предполагает данные наблюдений в виде вектора значений идентификационных номеров системных вызовов, выполняемых пользователем, также называемых базовыми элементами наблюдения. Базовый элемент наблюдения также может быть представлен как вектор-признак соединения, если объектом мониторинга системы поиска вторжений являются сеть. Обозначим как О множество возможных базовых элементов наблюдения ot. Тогда завершенной последовательностью будет являться временной ряд базовых элементов [oi, 02, …, от], Оі Є О. Такая последовательность может быть определена экспертным путем как нормальная или аномальная. Однако, как показано в [66], недостаточно использовать один базовый элемент в качестве состояния системы. Для описания поведения кибер системы необходимо использовать модель переходов между состояниями. Под данной моделью понимается представление состояния st, оперируемого методом обнаружения аномалий, в виде короткой последовательности или комбинации темпорально связанных базовых элементов, т.е. Si = [oi+1,oi+2,...,oi+n]. (28)
Таким образом, видом данных, приемлемым для метода детектирования аномалий в секвенциальных данных в случае приложения к тематике поиска вторжений в кибер системах, является последовательность состояний, каждое из которых представляет паттерн темпорально связанных элементов исходных данных, заключенных в скользящем окне заданной длины п. При этом, для данных из [36] было принято считать оптимальным для п значение, равное 6 [66]. Обозначение тестовой последовательности состояний Xtest = [xtest(lx XtesH2), …, xtest(T)\ и установка порогового значения для классификации .
Далее в [116] также показана эффективность применения вышеописанного алгоритма темпорально-разностного обучения при оценке исхода завершенных последовательностей. Не смотря на возможность анализа «немарковских» последовательностей, данный метод имеет ряд недостатков, среди которых невозможность его прямого использования для упреждения целевых (или аномальных) исходов тестовых немарковских последовательностей, являющегося одним из ключевых особенностей классического темпорально-разностного обучения, что делает невозможным использование метода в системах поддержки принятия упреждающих решений. Кроме того, при TDSAD моделировании Марковского процесса используется только информация о частоте переходов без учета вероятности перехода между состояниями, важных при оценке стохастических процессов.
В ходе настоящей диссертационной работы были проделаны исследования по модификации темпорально-разностного обучения Марковской модели. Результаты следующие. Первая проблема может быть решена на этапе тестирования путем замены суммарной вероятности развития аномалий для всей последовательности оценочной функцией вероятности развития аномалии для каждого состояния тестовой последовательности [101, 102, 103, 104]. Для того, чтобы при этом оценка оставалась робастной к единичным случайным отклонениям, а также для учета тенденции развития аномалии, в ходе настоящего диссертационного исследования было принято ввести критерий учета вероятностей развития аномалии из предшествующих состояний при оценке текущей вероятности. Следуя вышеизложенному, можно записать формулу (18) в виде РаЫ = P((xlfx2 хт)єАпот(х)\Хі = xt) + a- Pa(xt-i), (29) где - коэффициент зависимости оценки текущей вероятности развития аномальной последовательности от предыдущей тенденции развития аномалии.
Эффективность упреждающего алгоритма поиска аномалий можно показать в применении к стохастическому временному ряду с добавленными в него целевыми паттернами. Примером может служить стохастический временной ряд, в котором, к примеру, аномальным событием является наступление терминального состояния реализации ранее описанной бенчмарки Coffee [57, 103]. В этом случае реализация Coffee будет считаться паттерном, развитие которого приводит к аномальному исходу. Обучающий временной ряд включал в себя 93% последовательностей случайных величин и 7% аномальных паттернов, при этом предполагалось, что эксперту известны только терминальные состояния аномальных паттернов, т.е. моменты наступления аномальных событий (Рис. 21).
Интеллектуализация управления маневрами на сортировочных горках
Если сравнить целевую функцию, описываемую в рамках текущей диссертационной работы (70) с целевой функцией, представленной ранее (60), можно сделать вывод, что оптимизация функции (70) ведет к сокращению непредиктивных паттернов внутри кластера путем уменьшения размеров кластера или смещения его центра в отличие от оптимизации функции (60), в результате которой параметры кластера устанавливаются только на основе информации о предиктивных паттернах без учета возможного включения в кластер непредиктивных паттернов.
Как и в предыдущих работах, этап тестирования метода производится путем сопоставления предъявленного паттерна полученным в результате обучения кластерам. Ключевым элементом настоящего метода является использование нечеткого вывода типа Сугено, где антецедентами являются нечеткие отношения между параметрами кластера и параметрами паттерна, а консеквентами - способы определения вероятности того, что паттерн действительно является предиктивным. При этом принципиальной особенностью метода является наличие правил двух типов. Первую группу составляют универсальные правила, описывающие очевидные зависимости между темпоральными паттернами и кластерами предиктивных паттернов. Например, вполне очевидным является предположение о том, что с увеличением размеров предиктивного кластера и уменьшением расстояния от предъявленного паттерна до центра кластера возрастает вероятность появления целевого события. На основе данного предположения можно сформулировать следующее универсальное нечеткое правило для классификационной модели:
В эту же группу входят и универсальные нечеткие правила Сугено, консеквентами в которых являются значения вероятностей того, что паттерн кластера, наиболее близкого к тестируемому паттерну, является предиктивным, а именно: ЕСЛИ о = БОЛЬШОЕ и d = МАЛОЕ, то (72) Pa(Xt) = Prob(g(xt) = l\Xt Є Р). Второй тип образуют частные нечеткие правила, зависящие от особенностей приложения. Частные нечеткие правила формируются экспертами на основе качественных представлений об особенностях временного ряда, реконструированного фазового пространства и размещения в нем кластеров. Антецедентами частных правил обычно являются параметры значений отдельных координат темпоральных паттернов, являющихся отсчетами исходного одномерного ВР. Причем используются текущий xt или ближайшие к нему xt, xt-2T, в наибольшей мере влияющие на поведение временного ряда в будущем. В качестве примера частного правила приведем нечеткое правило, использовавшееся для анализа особенностей аттрактора Лоренца: ЕСЛИ d = МАЛОЕ и х, = БОЛЬШОЕ ПОЛОЖИТЕЛЬНОЕ, (73) ToPa = Prob(g(xt) = l\XtEP). Благодаря такому подходу к классификации, метод позволяет совместить статистическую информацию об анализируемой выборке и данные, полученные на основе экспертных знаний.
Проверка эффективности метода в рамках настоящего исследования предполагала множество экспериментов [62]. Здесь наглядным примером сравнения метода классификации паттернов в фазовом пространстве при использовании нечетких моделей типа Сугено с предыдущими методами, основанными на формировании кластеров предиктивных паттернов на базе нечеткого множества, может служить решение задачи прогнозирования пиковых значений стохастического временного ряда[62].
В качестве бенчмаркинговой выборки, как и в предыдущих случаях [34, 85], был взят аттрактор Лоренца [52]. Данный хаотический аттрактор определяется системой трех нелинейных дифференциальных уравнений, которые определяют динамическую систему с непрерывным временем: где ,гиЬ- параметры модели, известные как число Прандтля, число Рэлея и геометрический фактор, соответственно.
Временной ряд, аналогично предыдущим экспериментам, был сгенерирован с параметрами = 10, г = 28 иЬ = 8/3 (Рис. 34).
Анализированный временной ряд был получен из 625 секундной записи аттрактора с частотой дискретизации 100 Гц. В результате его длина составила 62500 событий. Считалось, что паттерн является предиктивным прихг+і 15 (т.е. g(xt) = 1 при xt+i = 15 в случае случая использования классификации с правилами Сугено и g(xt) = xt+i - 15 в случае других методов данного класса).
Оценка времени задержки показала, что оптимальным значением является = 0,12 с (Рис. 35). Также было доказано, что при размерности вложения Q= 115 реконструированное фазовое пространство все еще сохраняет динамические свойства исходного пространство состояний.
Исходный временной ряд был поделен на обучающую и тестовую выборку, которые содержали 50000 и 12500, соответственно. Набор паттернов, полученных из обучающего временного ряда и имевших значение характеристической функции, равное 1, был использован в качестве исходного множества кластеров. Таким образом, исходное количество кластеров составляло 911. Данное количество было сокращено до 9 на этапе первичного обзора. В результате проведения второго этапа обзора данный набор содержал в себе один паттерн. На рис. 36 изображены проекции нескольких паттернов, представляющих аттрактор Лоренца в фазовом пространстве, а также полученный кластер (его центр обозначен в виде черной отметки).
Для обеспечения необходимых условий для сравнения методов с нечетким выводом и без него была установлена граница соответствия . Если значение Pa(Xt) превышало данное границу, то считалось, что данный паттерн является предиктивным. Оптимальное значение границы соответствия = 0 выбиралось на основе анализа обучающей выборки при условии, что коэффициент верного детектирования (36) равнялся единице, т.е. все целевые события были предсказаны. В случае метода анализа паттернов в фазовом пространстве без нечеткого вывода для тестирования была использована формула качественного разделения паттернов (62).
Что касается базы нечетких правил, в обоих случаях (Мамдани и Сугено) были использованы максимально близкие по смысловому значению правила (Рис. 37 и рис. 38). Здесь, антецеденты представлены в заголовках столбцов и строк, а консеквенты – в пересечениях.