close

Вход

Забыли?

вход по аккаунту

Арбузов Александр Александрович. Разработка подсистемы динамического поиска аномалий в потоке данных IoT-устройств

код для вставки
АННОТАЦИЯ
ВКР 73 с., 13 рис., 40 источников
ИНТЕРНЕТ ВЕЩЕЙ, ПОИСК АНОМАЛИЙ, ИНФОРМАЦИОННАЯ
СИСТЕМА, КЛАСТЕРИЗАЦИЯ АНОМАЛИЙ, ВЫЧИСЛЕНИЕ СИГНАТУРЫ,
СГЛАЖИВАНИЕ ДАННЫХ
Выпускная квалификационная работа посвящена разработке подсистемы
динамического поиска аномалий в потоке данных IoT-устройств.
В первой главе приводится детальный обзор предметной области,
приводится определение аномалии, проведен подробный анализ существующих
отечественных и зарубежных решений в данной сфере, обосновывается
необходимость разработки собственного решения. Кроме этого, рассматривается
ряд проблем, которые могут возникнуть при разработке подсистемы
и предлагаются варианты решения этих проблем с помощью алгоритмов,
обоснованных теоретически.
Во второй главе обосновывается выбор инструментов разработки, а также
описывается сама разработка. Значительное внимание уделено алгоритмам
вычисления сигнатуры аномалии и кластеризации этих сигнатур. Описан процесс
разработки веб-приложения, которое будет применяться в качестве инструмента
для исследования аномалий,
5
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 ИССЛЕДОВАНИЕ
ПРЕДМЕТНОЙ
ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ
7
ОБЛАСТИ.
1.1 Понятие аномалии в данных
9
9
1.2 Обзор существующих методов поиска аномалий
12
1.2.1 Фреймворк для контекстного поиска аномалий
14
1.2.2 Алгоритм «TS–ADEEP»
20
1.3 Поиск аномалий на временных рядах
21
1.4 Фильтрация и сглаживание потока данных
25
1.5 Проблема концептуального дрейфа и способы ее решения
31
1.5.1 Аллигатор
32
1.5.2 Полосы Боллинжера
34
1.5.3 Средний истинный диапазон
35
1.5.4 Метод зигзага
35
1.6 Методы нахождения экстремумов в многоэкстремальной задаче
37
1.6.1 Полином Ньютона
38
1.6.2 Метод ломаных
39
1.7 Определение сигнатуры и кластеризация
40
2 РАЗРАБОТКА ПРОТОТИПА ПОДСИСТЕМЫ ДИНАМИЧЕСКОГО
ПОИСКА АНОМАЛИЙ В ПОТОКЕ ДАННЫХ IOT-УСТРОЙСТВ
43
2.1 Описание диаграммы вариантов использования
43
2.2 Описание диаграммы компонентов
46
2.3 Разработка серверной части
48
2.3.1 Выбор фреймворка
49
2.3.2 Выбор СУБД
50
2.4 Алгоритм поиска аномалий
51
2.4.1 Реализация определения сигнатуры
53
6
2.4.2 Реализация кластеризации
55
2.5 Реализация клиента веб-приложения
60
2.5.1 Выбор библиотеки для реализации клиентского приложения
60
ЗАКЛЮЧЕНИЕ
62
СПИСОК ЛИТЕРАТУРЫ
63
ПРИЛОЖЕНИЕ А
67
УДОСТОВЕРЯЮЩИЙ ЛИСТ №165134
74
ИНФОРМАЦИОННО-ПОИСКОВАЯ ХАРАКТЕРИСТИКА ДОКУМЕНТА
НА ЭЛЕКТРОННОМ НОСИТЕЛЕ
75
7
ВВЕДЕНИЕ
Беспроводные сенсорные сети (Wireless Sensor Network — WSN)
появились относительно недавно и представляют собой сети небольших,
недорогих, энергоэффективных и многофункциональных датчиков, которые
развернуты для мониторинга отклонений, отслеживания перемещений объекта
или управления процессом. WSN — частные элементы более общей сети Internet
of Things (IoT), которая предполагает, что множество объектов в жизни человека
будет оснащено датчиками, формирующими еще один слой сети Интернет.
WSN применяются в различных типах приложений, например:
приложения умного дома для индивидуального использования; бизнесприложения для контроля продаж; промышленные приложения для контроля
безопасности здания; а также военная сфера — мониторинг и отслеживание
целей противника. в IoT узлы датчиков подключаются к Интернету
динамически и используют интернет-инфраструктуру для совместной работы
и выполнения своих задач.
Совершенствование технологий, а также значительное снижение цен
на устройства Интернета Вещей за последние несколько лет спровоцировали
экспоненциальный рост объемов данных, передаваемых датчиками. Отсюда
возникла проблема ручного анализа полученных данных.
Отсутствие возможности эффективно анализировать потоки данных IoTустройств не позволяет контролировать ситуацию в реальном времени. В свою
очередь, невозможность контроля ситуации в реальном времени замедляет
процесс принятия решений любого уровня, не только в экстренных случаях,
но также и требующих длительного анализа.
Как сообщается в [1], целью использования WSN является не только
сбор данных от развернутой системы, но, что более важно, своевременный
анализ этих данных, это позволяет принимать важные решения, опираясь
на конкретные факты. Поэтому качество данных является главной проблемой,
поскольку отражает истинное мировое состояние приложений IoT. К сожалению,
необработанные измерения, собранные сенсорными узлами, особенно
из широкомасштабных WSN, часто страдают от неточности и неполноты
[2]. Эти неточные измерения датчиков могут возникать по причинам, связанным
с самим сенсорным устройством или средой восприятия. Ограничения ресурсов
сенсорных устройств с точки зрения хранения, энергии, обработки и полосы
8
пропускания могут способствовать сбоям узлов и, следовательно, возникает
вероятность аномальных показаний. Трудности в области развертывания, также
могут приводить к ошибочным данным [3]. Кроме того, вредоносные атаки, такие
как отказ в обслуживании, провал, черная дыра и выборочная переадресация,
могут также способствовать созданию таких неточных и некачественных
данных. Кроме того, физические сбои, такие как разрушение или перемещение
сенсорных устройств, вызванных людьми или животными, могут повлиять
на процесс сбора данных и привести к аномальным измерениям [4]. Проблема
обнаружения аномалий изучалась с разных точек зрения, таких как безопасность
данных, интеллектуальный анализ данных или распознавание образов. Термин
«аномалия» по-разному известен в литературе как выброс, ошибка или
отклонение.
Обнаружение аномалий в потоках данных от подобных устройств
может по-разному трактоваться и иметь большое значение в разных
отраслях: предотвращение мошенничества в финансах, мониторинг
неисправностей в энергетике и медицине, контроль за расходом топлива
любого вида транспорта и т. д.
Автоматизация поиска аномалий на платформе IoT-устройств поможет
создать оперативный инструмент для обнаружения проблем в эксплуатации
объектов системы, а на основе некоторой классификации аномалий возможна
реализация системы поддержки и принятия решений.
Цель данной работы — создать эффективный инструмент отслеживания
аномалий в данных в режиме реального времени для бизнеса, построенного
на основе IoT.
Чтобы достичь цели, необходимо выполнить следующие задачи:
— провести детальное исследование предметной области и обзор
существующих решений;
— разработать прототип подсистемы динамического поиска аномалий
в потоке данных IoT-устройств на основе изученного материала.
9
1 ИССЛЕДОВАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ.
ОБЗОР СУЩЕСТВУЮЩИХ РЕШЕНИЙ
1.1 Понятие аномалии в данных
Неточные или неполные измерения данных, вызванные ранее
упомянутыми причинами, известны как аномалии. В соответствии с [5]
аномалию можно определить как интервал во времени, где поведение системы
или объекта эксплуатации необычно и значительно отличается от предыдущего,
нормального поведения.
Поиск аномалии определен в [6] как процесс нахождения шаблонов
данных, которые отклоняются от ожидаемого поведения. В связи с этим,
обнаружение аномалий относится к поиску непредвиденных значений
(паттернов) в потоках данных.
Аномалия может означать отрицательное изменение в системе, которое
является, например, сбоем в работе двигателя. Аномалия может быть
и положительной, например, очень большое количество кликов на веб-странице,
что может свидетельствовать о повышенном интересе пользователей к продукту.
В любом случае, аномалии в данных идентифицируют нестандартное поведение
с полезной информацией.
Аномалии в данных могут быть пространственными или групповыми, где
отдельный пакет данных можно считать аномальным по отношению к остальным
независимо от того, где он встречается в потоке данных (первый и третий
аномальные всплески, обозначенные черными точками на рисунке 1).
Аномалия также может быть временно́й или контекстной, если актуальна
временная последовательность данных; то есть набор данных является
аномальным только в определенном временном контексте, но не по-другому,
поэтому в некоторых источниках встречаются термины «контекстная» или
«контекстуальная» аномалия. Временные аномалии, такие как средняя аномалия
на рисунке 1, часто тонкие и трудно обнаруживаются в реальных потоках
данных. Обнаружение временных аномалий в практических приложениях может
служить ранним предупреждением о проблемах с системой. Стоит отметить, что
определение аномалий в режиме реального времени имеет бо́льшую значимость,
чем анализ пакета устаревших данных.
10
Рисунок 1 – Примеры аномалий
В англоязычной литературе принято различать два направления поиска
аномалий: детектирование выбросов (Outlier Detection) [7] и «новизны» (Novelty
Detection) [8].
Выброс — это результат измерения, выделяющийся из общей выборки [9].
Иными словами, выбросы –– это необычно низкие или высокие значения
наблюдаемой величины, причем настолько, что это заметно невооруженным
глазом: в ходе графического анализа можно заметить значения, которые
не принадлежат популяции наблюдений. Определить выбросы можно с помощью
гистограмм, точечных диаграмм, диаграмм индивидуальных значений, рассеяния
и диаграмм временных рядов.
В теории статистического анализа нет однозначного критерия
идентификации выбросов, и это — только одна из причин, по которой выбросы
представляют опасность для исследования.
Из определения следует, что все необычно низкие или высокие
значения наблюдаемой величины могут быть выбросами. Однако важно
понимать, что экстремальное значение не является выбросом. Один из самых
простых способов определить, какое значение переменной является выбросом,
заключается в использовании диапазона трех стандартных отклонений
вокруг среднего значения: вероятность выхода величины за пределы ±3σ
(где σ — величина стандартного отклонения) составляет 0,0027, а значит,
с большой долей вероятности, значение, которое выходит за пределы ±3σ
не принадлежит к популяции.
11
С другой стороны, можно привести ряд доводов против этого
утверждения. Например, оно теряет смысл, если функция распределения
отличается от нормальной или размер выборки слишком мал, чтобы
представить генеральную совокупность значений. Кроме того, с малой долей
вероятности наблюдение все же может выйти за пределы диапазона трех
стандартных отклонений.
Выбросы могут становиться причиной искажения статистики или
результатов статистических расчетов. Такие показатели как среднее
арифметическое, стандартное отклонение, асимметрия, эксцесс, а также
критерий согласия с нормальным законом весьма подвержены влиянию
выбросов. В отличие от среднего арифметического, медиана менее подвержена
влиянию выбросов.
Легкость неверного истолкования полученных выбросов приводит
к неверному направлению последующего анализа. Наличие выбросов может
означать ошибку ввода данных, недостаточную величину выборки или
присутствие специальной причины отклонения –– действие конкретного
фактора или причины. При диагностике выбросов, легко допустить ошибку,
исключив нужные для анализа данные или наоборот — рассчитав показатели
процесса, используя неверные результаты наблюдений.
Таким образом, недостаточный анализ выбросов может стать причиной
ошибки последующих выводов. Следовательно, обнаружив необычно низкие или
высокие значения наблюдаемой величины, исследователь обязан найти причину
их появления, прежде чем делать выводы о наблюдаемой переменной или
приступать к последующему анализу данных.
Обнаружение новизны — это идентификация новых или неизвестных
данных или сигналов, о которых обучаемая система или система-учитель не знают
во время обучения. Методы обнаружения новизны пытаются выявить выбросы,
которые отличаются от распределения обычных данных [10].
Другими словами, цель обнаружения новизны — выявление
ненормальных системных поведений, которые не согласуются с нормальным
состоянием системы. Новые события происходят относительно редко, но могут
иметь значительные последствия для общей работы системы, в том числе
вызывать концептуальный дрейф.
12
1.2 Обзор существующих методов поиска аномалий
Традиционно в задаче поиска аномалий выделяют несколько подходов,
различающихся применяемыми математическими методами.
К первой группе методов можно отнести подходы, основанные
на статистических тестах. Также подобные алгоритмы применяются в анализе
сенсорных данных при моделировании их временными рядами. Такой подход
применен, например, в работе [11], где сенсорные данные моделируются
авторегрессионной моделью, а для обнаружения аномалий используется теория
проверки гипотез.
Другую группу составляют метрические и итерационные алгоритмы
обнаружения выбросов. Простейшим примером такого подхода является
построение выпуклой оболочки в многомерном пространстве в предположении,
что выбросы в данных будут лежать на ней. В качестве другого варианта можно
привести метод k ближайших соседей, в котором применительно к аномалиям
предполагается, что выбросы имеют «большое» расстояние до соседних точек
пространства. Применение подобных алгоритмов для задач поиска аномалий
рассмотрено в работах [12] и [13].
К недостаткам таких подходов относятся вычислительная трудоемкость
и сложность выбора подходящей метрики. Причем если производительность
метода можно повысить при помощи параллельных и распределенных
вычислений, то выбор метрики, удачно отражающей структуру многомерных
данных, остается открытым вопросом и требует отдельного рассмотрения.
Модельные тесты обнаружения аномалий основаны на построении
некоторой модели данных. Точки пространства, которые существенно
отклоняются от модели, можно считать аномалиями. Преимуществами таких
подходов являются возможность учета предметной области и задание требуемого
функционала качества [14].
Теоретико-информационные методы обнаружения аномалий анализируют
количество информации в данных, используя различные теоретикоинформационные величины, такие как колмогоровская сложность, энтропия,
относительная энтропия и т. п. При этом предполагается, что аномалии в данных
приводят к неравномерности информационного содержания набора данных.
Спектральные методы обнаружения аномалий пытаются найти
приближение данных с использованием набора атрибутов таким образом,
13
чтобы отразить все разнообразие данных. Спектральные методы используют
в предположении, что данные можно представить в пространстве меньшей
размерности, причем в новом представлении различие между нормальными и
аномальными данными будет значительным. Следовательно, основная задача
— определить такое пространство, в котором можно было бы легко обнаружить
аномалии [15].
С точки зрения методов машинного обучения задача нахождения аномалий
в данных может быть выделена в отдельный класс. К самым популярным
алгоритмам относятся метод опорных векторов с одним классом и алгоритм
изолирующего леса [16].
Основная идея первого подхода заключается в применении классического
метода опорных векторов для отделения точек пространства от начала
координат. Второй подход основан на построении разделяющих деревьев,
описывающих данные. Деревья строятся, пока каждая точка рассматриваемого
пространства не окажется в листовом узле, после чего критерием нормальности
может служить глубина (или среднее значение глубин для леса) этого узла.
К достоинствам данных алгоритмов относится их простая параметризуемость,
возможность задавать различные метрики и количество степеней свободы модели.
Также в процессе работы алгоритмов строится разделяющая гиперплоскость,
расстояние до которой также может служить мерой аномальности данных [17].
К недостаткам можно отнести вероятность деградации алгоритма при накоплении
большого количества однотипных данных.
Помимо перечисленных методов для поиска аномалий во временном
потоке данных с устройств могут быть применены алгоритмы поиска аномалий
на временных рядах (ВР). Обычно задача обнаружения аномалий на временных
рядах возникает в связи с пропуском значений или появлением значений,
выходящих за пределы диапазона допустимого интервала. Однако эти подходы
не учитывают аномалии, связанные с нарушением поведения временного ряда,
выраженные в изменении локальных тенденций.
Как указано в работе [18] поиск и обнаружение аномалий на ВР
рассматриваются как совокупность задач обнаружения аномалий на всем ВР,
на участке ВР или в отдельной точке ВР.
Например, в работе [19] предложен алгоритм поиска и обнаружения
аномалий на ВР, который успешно внедрен и применяется в процессе
14
экспертного анализа параметров космических челноков NASA. В этой работе
авторы решают задачу обнаружения аномалий ВР с помощью применения
алгоритма кластеризации Gecko для выявления аномальных состояний,
описанных логическими правилами (алгоритм классификации RIPPER). Кроме
этого, подсчитывается количество аномальных состояний, которое не должно
превышать заданный исследователем порог. Исследования показали, что метод
сравним по эффективности работы с анализом данных человеком-экспертом.
В работе [20] все множество значений ВР разбивается на несколько
уровней, каждому из которых сопоставляется символ заданного конечного
алфавита. В этом случае для поиска и обнаружения аномалий используется
скользящее окно и сравнение с ВР, характеризующим нормальное
поведение процесса. Данный алгоритм использовался для анализа ВР
данных ЭКГ, мониторинга телеметрии космического челнока, видеопотоков и т. д.
1.2.1 Фреймворк для контекстного поиска аномалий
В 2015 году было проведено исследование, в котором описана методика
обнаружения контекстуально аномальных значений в потоковых сенсорных
системах. Это исследование основано на представлении о том, что аномалии
имеют размерную и контекстуальную локальность, то есть, размерная
локальность будет определять те аномалии, которые, как установлено, структурно
отличаются на основе показаний датчика. Контекстуально, однако, датчики могут
ввести новую информацию которая уменьшает или увеличивает вероятность,
что значение будет отнесено к аномальному. Кроме того, авторы используют
схему обнаружения из двух частей, чтобы гарантировать, что точечные аномалии
обнаруживаются в режиме реального времени, а затем оцениваются с помощью
контекстной кластеризации. Последняя оценка проводится на основе профилей
датчиков, которые определяются путем идентификации датчиков, используемых
в аналогичных контекстах. Основная цель этого метода — обеспечить
масштабируемый способ обнаружения, классификации и интерпретации
аномалий в системах на основе датчиков. Это гарантирует возможность
обнаружения аномалий в реальном времени. Предлагаемый подход используется
для снижения скорости ложных срабатываний.
15
В статье приведено несколько типов контекстных атрибутов:
1. Пространственный: записи в наборе данных включают объекты,
которые идентифицируют информацию о местоположении для записи. Например,
показания датчика могут иметь пространственные атрибуты для города,
провинции и страны, в которой находится датчик; они также могут включать
более детальную информацию о расположении датчиков в здании, такую
как этаж, комната и номер здания.
2. Диаграммы: записи связываются с другими записями согласно
некоторой структуре графика. Затем структура графика определяет
пространственную окрестность, в которой эти отношения могут рассматриваться
как контекстуальные индикаторы.
3. Последовательный: записи рассматриваются как последовательность
друг в друге. То есть определяется набор записей, которые позиционируются
одна за другой. Например, это чрезвычайно распространено в данных
временных рядов, когда записи имеют временную метку и, таким образом,
могут располагаться относительно друг друга на основе показаний времени.
4. Профиль: записи кластеризуются в профилях, которые могут не иметь
явных временных или пространственных контекстуальностей. Это часто
встречается в системах обнаружения аномалий, где, например, компания
определяет профили для своих пользователей; если новая запись нарушает
существующий профиль пользователя, эта запись объявляется аномальной.
Контекстная аномалия обычно обрабатывается одним из двух способов.
Во-первых, проблема контекстной аномалии преобразуется в проблему
точечной аномалии, то есть приложение пытается применить отдельные методы
обнаружения точечных аномалий к одному и тому же набору данных в разных
контекстах. При таком подходе необходимо определить контексты нормальных
и аномальных записей, что не всегда возможно во многих приложениях. Это
верно для случая использования больших данных, передаваемых с датчика,
когда трудно определить весь набор известных аномальных записей. Второй
подход к работе с приложениями контекстных аномалий заключается
в использовании существующей структуры в записях для обнаружения аномалий
с использованием всех данных одновременно. Это особенно полезно, когда
контекст данных не может быть разбит на отдельные категории или когда новые
записи не могут быть легко размещены в одном из заданных контекстов. Второй
16
подход обычно требует более высокой вычислительной сложности, чем первый
подход, поскольку базовая алгебра при вычислении контекстуальной аномалии
является вычислительно дорогостоящей.
В статье [21], описывается структура, состоящая из двух различных
компонентов: детектор аномалии содержимого и детектор контекстной аномалии.
Описывается как структура, обеспечивающая расширяемый и модульный подход
к обнаружению аномалий, не требуя конкретных реализаций для каждого модуля:
в частности, контент и контекстные детекторы. Остальная часть этой статьи
предложит одно возможное решение для модулей, которое особенно хорошо
работает для использования в потоковом датчике.
Основной причиной создания разделения проблем между контентом
и контекстом является интерес к масштабируемости для больших объемов
данных. Детектор на основе контента будет способен обрабатывать каждый
новый фрагмент данных, отправляемых в центральный репозиторий, поскольку
он будет использовать алгоритм с быстрым временем тестирования. В отличие
от этого, детектор на основе контекста будет использоваться в двух ситуациях:
чтобы определить, является ли аномалия, обнаруженная детектором контента,
ложной позицией, и случайным образом гарантировать, что датчик не производит
полностью аномальные результаты. Последнее заключается в том, что датчик
может действовать не аномально в своей собственной истории значений,
но не при просмотре с датчиками с аналогичным контекстом. Профиль
датчика определяется как контекстно-зависимое представление датчика
в качестве подмножества его атрибутов. Сравнение входного значения датчика
с соответствующим профилем датчика состоит в сравнении входного значения
со средним значением всех значений датчика, составляющих соответствующий
профиль датчика. Это создает два уровня абстракции для контекстного
детектора. Во-первых, поскольку аналогичные датчики объединяются в профили
датчиков, уровень контекста создается на уровне атрибута датчика. Во-вторых,
контекстное обнаружение использует корреляционную матрицу атрибутов
для датчиков для дальнейшего применения контекста к входящим значениям
для сравнения. Использование кластеризации используется для двух целей.
Во-первых, кластеризация помогает уменьшить размер популяции, создавая
подзадачи, которые работают против вычислительно дорогостоящей функции
обнаружения контекстной аномалии. Во-вторых, кластеризация обеспечивает
17
раннее понимание контекста нового значения датчика.
Методика обнаружения аномалий контента использует одномерный
гауссовский предиктор для определения точечных аномалий. Одномерные
гауссовские предикторы строят историческую модель данных, а затем
прогнозируют и сравнивают новые значения на основе модели. Предиктор
будет одномерным, поскольку он рассматривает только исторические показания
датчика для настройки параметров модели. не будет учитываться контекстная
метаинформация, связанная с показаниями датчика. Это гарантирует,
что предиктор может быстро классифицировать новые значения, жертвуя
некоторой точностью. Скорость - это самая важная характеристика для точечного
детектора, поскольку она должна оценивать высокую скорость и объем данных
в реальном времени. Недостаток точности будет обрабатываться детектором
контекстных аномалий.
Датчик контекстной аномалии основан на двух концепциях: определении
профилей датчиков и присвоении каждого датчика одному из профилей
датчиков, а также оценке значения текущего датчика (аномального по аномалии
содержимого аномалия) относительно среднего ожидаемого значения профиля
датчика. Профили датчиков определяются с использованием многомерного
алгоритма кластеризации; алгоритм является многомерным, чтобы включать
в себя датчики многомерных контекстуальных метаданных, которые могут
включать в себя местоположение, здание, собственность компании, время года,
время суток и явления погоды. Алгоритм кластеризации помещает каждый
датчик в профиль датчика и затем назначает эту группу профиля датчику. Когда
датчик аномалирован аномальным детектором аномалий содержимого, детектор
аномалий контекста определит среднее ожидаемое значение группы датчиков.
Алгоритм контекстного обнаружения работает с несколькими
измерениями набора данных и, следовательно, имеет более высокую
вычислительную сложность по сравнению с детектором контента. Чтобы
справиться с более высокой вычислительной сложностью, предлагаемая
структура использует важную роль в распараллеливании и сокращении
данных. Оценка обнаружения аномалий использует понятие сокращения
данных, только оценивая вычислительно более дорогой детектор контекстной
аномалии на очень маленьком подмножестве данных. Детекторы контента могут
независимо обрабатывать информацию параллельно на распределенных машинах
18
и только обмениваться данными с детектором контекста при обнаружении
аномалии. Затем структура может масштабироваться горизонтально, добавляя
дополнительные машины для независимой обработки новых данных.
Реализация для платформы была завершена с использованием
виртуализованного потока датчиков. То есть приложение было построено
вокруг старого представления набора данных данных Big Sensor Data, а не
для реальных реальных данных. для гарантии, что данные все еще были
протестированы, как если бы это было в режиме реального времени, был создан
виртуальный поток датчиков. Это было достигнуто путем извлечения различных
датчиков из всего набора данных в их собственные отдельные наборы данных.
Затем очередь оценивалась и удалялась. Еще одна важная деталь реализации —
это определение количества профилей датчиков, создаваемых во время процесса
контекстного обнаружения. Определение количества профилей было сделано
в качестве этапа предварительной обработки, итеративно увеличивая количество
профилей датчиков до тех пор, пока точность не будет улучшена. Эмпирически
это было определено как три кластера для наборов данных Powersmiths.
Логически это также имело смысл, поскольку Powersmiths предоставляет своим
клиентам три типа сенсорного восприятия.
Оценка данных датчика проводилась в режиме реального времени,
когда имитатор передавал значения. Учитывая низкие вычислительные
затраты на этот шаг, распараллеливание может не обеспечить большого
увеличения производительности. Эмпирически было определено, что три
кластера подходят для построения модели кластеризации; за пределами трех
алгоритм кластеризации видел мало улучшений. После определения профилей
датчиков с помощью кластеризации для каждого контекстного кластера или
профиля датчика был построен контекстуальный гауссовский предиктор.
Результаты работы можно описать в два шага. Первым шагом алгоритмов
является возможность определения точечных аномалий в реальном времени.
Второй шаг-определить, какие из этих аномалий являются контекстуально
аномальными, а также точечными. Вторая часть результатов-определение того,
какие из этих значений датчиков являются контекстуально аномальными. То есть,
на основе контекстуальной информации: датчик физического местоположения,
время чтения датчика дня, датчик чтения день недели, и корреляции между
другими датчиками; какие значения остаются аномальными?
19
Таким образом, можно сказать, что алгоритм уменьшил количество
ложноположительных аномалий. Другое преимущество, которое видно здесь,
заключается в том, что более дорогостоящий контекстуальный детектор
необходим только для оценки меньшего количества показаний датчиков, а не
десятков тысяч, которые передаются на точечный детектор. Поэтому, по мере
того как алгоритм обнаружения масштабируется до большего количества
объемов данных, с более высокими скоростями потоков данных, алгоритм
все еще сможет оценить вычислительно более дорогой контекстный детектор,
все еще обеспечивая обнаружение в реальном времени. Авторами статьи
был сделан вывод, что предлагаемая структура выполнена, а также пакет
R выбросов в обнаружении аномалий, и является гораздо более масштабируемой
и применимой к обнаружению в режиме реального времени.
Проверка показала, что не было никаких аномалий контекста, которые
не были переданы детектору контента. не было обнаружено аномалий, которые
были нормальными по отношению к их содержанию, но ненормальными
по отношению к их контексту.
В описанной работе показаны плюсы использования иерархического
подхода к поиску аномалий, в котором, чтобы справиться со скоростью
и объемом больших данных, алгоритм обнаружения аномалий опирается
на быстрый, хотя и менее точный, алгоритм обнаружения точечных аномалий
для поиска аномалий в реальном времени из сенсорных потоков. Эти аномалии
затем могут быть обработаны контекстуально-зависимым, более дорогостоящим
вычислительным алгоритмом обнаружения аномалий, чтобы определить, была
ли аномалия контекстуально аномальной. Этот подход позволяет алгоритму
масштабироваться в соответствии с требованиями к большим данным, поскольку
вычислительно более дорогостоящий алгоритм необходим только для очень
небольшого набора данных.
Одной из главных целей фреймворка было оставаться модульным
и масштабируемым для будущих работ. Фреймворк был протестирован
в моделируемой, виртуализированной, сенсорной потоковой среде. Эти
фреймворки можно было бы также интегрировать с системами принятия решений
в рамках реальной среды. Результат работы фреймворка — информация об
аномальной работе некоторого датчика. Эта информация может использоваться
алгоритмом принятия решений, таким как комплексная платформа обработки
20
событий, для координации изменений в бизнес-среде.
Модульность фреймворка позволяет добавлять или обновлять
дополнительные компоненты фреймворка. Данное исследование может лечь
в основу будущих улучшений для текущей подсистемы. В частности, могут быть
внедрены модульная структура и алгоритм обнаружения ложноположительных
аномалий.
1.2.2 Алгоритм «TS–ADEEP»
В работе [22] приводится собственный метод поиска аномалий,
основанный на методе из работы [23].
Исходная постановка задачи, данная в [23], описана следующим образом:
для заданного конечного множества объектов I необходимо получить множествоисключение Ix .
Для этого на множестве I вводятся:
1. Функция неподобия (dissimilarity) D(Ij ), Ij ∈ I, определенная
на P (I) — множестве всех подмножеств и принимающая положительные
вещественные значения.
2. Функция мощности (cardinality) (Ij ), Ij
∈
I, определенная
на P (I) — множестве всех подмножеств и принимающая положительные
вещественные значения такая, что для любых I1 ⊂ I, I2 ⊂ I выполняется
I1 ⊂ I2 ⇒ C(I1 ) < C(I2 ).
3. «Фактор сглаживания» (smoothing factor), который вычисляется
для каждого Ij ⊆ I по формуле:
( ) (
( ))
I
I
SF (Ij ) = C
· D(I) − D
.
Ij
Ij
(1)
Тогда Ix ⊂ I будет считаться множеством-исключением для I
относительно D и C, если его фактор сглаживания SF (Ix ) максимален [23].
Неформально,
множество-исключение
—
это
наименьшее
подмножество из I, которое вносит наибольший вклад в его неподобие. Фактор
сглаживания показывает, насколько может быть уменьшено неподобие множества
I, если из него исключить подмножество Ij .
Автором [22] был разработан алгоритм «TS–ADEEP», предназначенный
для обнаружения аномалий в наборах временных рядов. В качестве
21
множества I рассматриваются множества T S ST U DY ∪ {ts testj } для каждого
ts testj ∈ T S T EST .
Функция неподобия для временных рядов будет задана следующим
образом:
1 ∑
D(Ij ) =
·
|i − Ij |2 .
(2)
|Ij |
i∈Ij
Сначала вычисляется Ij — среднее для временных рядов из Ij . В данном
случае это эквивалентно вычислению среднего для обычных векторов: i —
временной ряд из подмножества Ij , |Ij | — число элементов в Ij . Функция
неподобия вычисляется как сумма квадратов расстояний (используется евклидова
метрика) между средним и векторами из Ij , которая затем нормализуется —
делится на число элементов во множестве Ij .
( )
I
1
Функция мощности задается формулой C
=
.
Ij
|Ij | + 1
Формула для вычисления фактора сглаживания имеет прежний вид.
Если множество исключение Ix , полученное для T S ST U DY ∪ {ts testj }
содержит ts testj , 1 ≤ j ≤ T S T EST , то ts testj является аномалией.
В предложенной работе также предлагается метод обнаружения аномалий
в наборах временных рядов с несколькими классами, который является
обобщением метода обнаружения аномалий для случая обучающего множества,
содержащего примеры одного класса.
Обобщение является достаточно очевидным: разделив обучающее
множество на подмножества, содержащие примеры только одного класса
и последовательно применив к ним и каждому из временных рядов
экзаменационного множества метод обнаружения аномалий в наборах временных
рядов с одним классом, можно определить, является ли рассматриваемый
временной ряд аномалией.
Если временной ряд является аномалией для каждого подмножества,
то он является аномалией и для всего обучающего множества.
1.3 Поиск аномалий на временных рядах
Временной ряд –– это последовательность дискретных упорядоченных
в неслучайные равноотстоящие моменты времени измерений (показателей
наблюдений) X = xt , где где t = 1,N , характеризующих уровни состояния
изучаемого процесса. Практически любые наблюдения, полученные в результате
22
мониторинга процессов в различных сферах человеческой деятельности
(безопасность, медицина, экология и т.д.), могут быть представлены в виде
некоторой последовательности, зависимой от времени, то есть в форме ВР.
Временной ряд, проанализированный правильным образом, может многое
сказать о состоянии и изменении состояния сложного объекта. Именно по этим
причинам в последнее время уделяется большое внимание интеллектуальному
анализу временных рядов [24].
Неформально задача определения аномалий в наборах временных рядов
ставится следующим образом. Пусть имеется коллекция временных рядов,
описывающих некоторые процессы. Эта коллекция используется для описания
нормального протекания процессов. Требуется на основании имеющихся данных
построить модель, которая является обобщенным описанием нормальных
процессов и позволяет различать нормальные и аномальные процессы.
Задача усложняется, тем, что набор исходных данных ограничен и не имеет
выделенных примеров аномальных процессов; также не задан критерий,
по которому можно было бы различать «нормальные» и «аномальные» временные
ряды. В связи с этим трудно точно оценить качество работы алгоритма
(процент правильно определенных аномалий, число ложных срабатываний
и число пропущенных аномалий). К тому же многие алгоритмы, хорошо
показавшие себя на одних наборах данных, совершенно не подходят для других
предметных областей. Также может отличаться и критерий, на основании
которого определяется «нормальность» рядов.
Для верификации разработанных методов были использованы реальные
данные с автомобиля, на котором в режиме эксплуатации установлена система
сбора данных. На автомобиле собирается информация с большого количества
датчиков. В рамках тестирования использованы данные, собранные за месяц
и представимые в виде временного ряда.
X = {(ti , x1,i , ..., xk,i , ...,xM,i )}N
i=1 ,
где ti — обозначает время поступления данных
xk,i — показатели k-ого датчика в ti -ый момент времени,
N — общее число накопленных данных,
M — общее количество датчиков.
Следует отметить, что данные от устройства приходят
(3)
всегда
23
неравномерно из-за помех в сети, поэтому необходимо применять интерполяцию
данных по времени:
tj − ti
xk,j − xk,i
=
, k = 1,M ,
xk,i+1 − xk,i
ti+1 − ti
(4)
В формуле (4) соседние интервалы времени равны ∆t = tj − tj−1 = Const.
Таким образом, в каждый момент времени рассматривается M -мерный вектор
состояния автомобиля.
Очевидный подход к решению задачи обнаружения аномалий следующий:
необходимо определить область, соответствующую нормальному поведению,
тогда любое наблюдение, лежащее в этой области, будет считаться нормальным,
а вне области — аномальным. Тем не менее, даже при таком простом подходе
возникает много трудностей:
1. Определить область, которая охватывает все возможные варианты
нормального поведения непросто; кроме того, граница между нормальными
и аномальными наблюдениями очень часто размыта, аномальное наблюдение,
лежащее близко к границе области, на самом деле может быть нормальным,
и наоборот.
2. В случае, если аномалии являются результатом злонамеренных
действий, злоумышленники обычно стремятся замаскировать свои действия
таким образом, чтобы аномалии выглядели нормальным поведением, делая
задачу определения области нормального поведения еще более сложной.
3. Точное определение термина «аномалия» различается в зависимости
от выбранной предметной области. Например, в медицине небольшие отклонения
от нормального состояния (например, температура тела) могут считаться
аномалиями, в то время как небольшие колебания цен на бирже могут
считаться нормальными. Таким образом, достаточно часто нельзя напрямую
применять методы, разработанные для конкретной предметной области, в других
предметных областях.
4. Часто данные содержат шум, за счет которого некоторые наблюдения
становятся похожими на аномальные, при этом не являясь таковыми.
Применимость методов обнаружения аномалий определяется характером
атрибутов. Например, для статистических методов при работе с непрерывными
и категорийными данными должны использоваться различные статистические
24
модели. Аналогично, для методов, основанных на методе ближайших соседей,
характер атрибутов будет определять метрику.
В общем случае экземпляры данных, используемых в задачах обнаружения
аномалий, могут быть связаны между собой: например, последовательности,
пространственные данные, графовые данные. В последовательностях экземпляры
данных линейно упорядочены — это временные ряды, геномы, протеиновые
последовательности. В пространственных данных каждый экземпляр данных
связан с соседними — например, данные о городском трафике, экологии.
Если в пространственных данных есть временной компонент, то говорят
о пространственно-временных данных (напр., климат). В графовых данных
экземпляры данных представляют собой вершины в графе, которые связаны
с другими вершинами дугами.
Наиболее подходящим для поиска локальных аномалий алгоритмом
является алгоритм скользящего окна. Если подобрать оптимальный размер и шаг
окна алгоритм позволяет уменьшить объем обрабатываемых данных, при этом
сохранить скорость обработки и полноту анализа.
Рисунок 2 – Пример применения алгоритма скользящего окна
Данная методика используется для временных рядов, которые разбиваются
на некоторое число подпоследовательностей — окон (Рисунок 2). Поиск
аномальной подпоследовательности осуществляется при помощи скольжения
окна по всему ряду с шагом, меньшим длины окна. Необходимо выбрать
окно фиксированной длины, меньшей чем длина самого ряда, чтобы захватить
аномалию в процессе скольжения.
25
Поток данных может быть распределен во времени неравномерно [25],
т. е. xt+1 − xt ̸= xt − xt−1 Этот факт связан с техническими особенностями сетей,
в которых распространяется информация, а также с особенностями эксплуатации
и условиями работы конкретного датчика.
Так же при равномерном получении данных появляется вероятность того,
что данные могут приходить либо недостаточно часто для исследований, из-за
чего возникает необходимость достраивать недостающие точки xt , либо частота
данных может быть слишком высокой, из-за чего в сигнале появляется «шум».
В связи с этим появляется необходимость аппроксимации данных —
замене сложных функций приближенными аналитическими выражениями,
а также интерполяции — достраивании недостающих данных на основе
определенной функции.
Наиболее часто используют два вида аппроксимации — полиномиальная
и кусочно-линейная. Аппроксимация степенным полиномом выполняется
на основе ряда Тейлора:
i′ (u0 )
i′′ (u0 )
i(u) = i(u0 )+
(u−u0 )+
(u−u0 )2 +. . . = a0 +a1 u+a2 u2+ ...+an un +... (5)
1!
1!
Подобные расчеты с вычислением производных на больших
потоках данных могут привести к неоправданной значительной потере
производительности, поэтому выбор сделан в пользу кусочно-линейной
аппроксимации.
Кусочно-линейная аппроксимация представляет данные в виде
совокупности линейных участков различной длины, то есть точки, полученные
после аппроксимации будут найдены с помощью канонического уравнения
прямой, в случае интерполяции применяется тот же алгоритм, разница в том,
что аппроксимация уменьшает количество точек, интерполяция — увеличивает.
1.4 Фильтрация и сглаживание потока данных
Большинство алгоритмов предполагают, что большие отклонения
от среднего (скачки) значений, получаемых от IoT-устройства, являются ошибкой,
вызванной неисправным датчиком. Однако это далеко не всегда так, потому что
скачок может также стать важным событием, которым нельзя пренебрегать [26],
кроме этого использование базы данных в качестве обучающего множества
26
вызывает следующие трудности. Во-первых, информация в базе данных
ограничена, так что не вся информация, необходимая для определения класса
объекта, доступна. Во-вторых, доступная информация может быть повреждена
или частично отсутствовать. Наконец, большой размер баз данных и их изменение
со временем рождает дополнительные проблемы. Далее если база данных
содержит всю информацию, необходимую для корректной классификации
объектов, некоторые данные могут не соответствовать действительности.
Например, значения каких-либо атрибутов могут содержать ошибки в результате
измерений или субъективных суждений. Ошибка в значениях предсказываемых
атрибутов приводит к тому, что некоторые объекты в обучающем множестве
классифицированы неправильно. Несистематические ошибки такого рода
обычно называются шумом. Шум в обучающих примерах может вызываться
различными причинами: ошибками при описании объектов (это могут быть
ошибки при описании предметной области: ошибки в измерениях, погрешности
измеряющих приборов, неправильное распределение примеров по классам
экспертом и т. п.), второй причиной является то, что сам язык описания
предметной области недостаточен для того, чтобы полностью и корректно
описать все возможные ситуации.
В работе [27] проводилось исследование влияния шума на работу
алгоритмов обобщения понятий при наличии шума во входных данных.
При этом одним из основных параметров исследования являлся уровень шума —
величина p0 , (0 < p0 < 0.5), которая показывает, что с вероятностью p0
значение признака в обучающем или экзаменационном множестве искажено.
Также эта величина показывает, что среди всех N значений признаков в среднем
N · p0 значений признаков будет искажено.
Это подчеркивает необходимость разработки алгоритмов, которые
рассматривают все возможные случаи: результаты неисправных датчиков
или события, являющиеся признаком аномального явления.
Однако на начальных этапах сбои в показаниях данных могут привести
к некорректной тонкой настройке системы поиска, в связи с этим, предполагается,
что от ошибочные показания датчиков и «шум» в целом необходимо сгладить,
чтобы в том числе, и зрительно можно было увидеть экстремумы, указывающие
на аномалию. В дальнейшем, после тонкой настройки системы необходимо
подобрать оптимальные параметры, которые бы не сглаживали аномальные
27
значения, а выделяли оставляли для дальнейшего анализа подсистемой.
Задача сглаживания — это задача фильтрации сигнала от ступенчатых
изменений [28]. Ступенчатый сигнал за счёт множества резких, но небольших
по амплитуде, перепадов уровня содержит высокочастотные составляющие,
которых нет в сглаженном сигнале. Поэтому для алгоритма сглаживания
необходимо определить как сильно ослабляются разные частотные
составляющие, то есть, необходимо построить амплитудно-частотную
характеристику соответствующего фильтра.
Сглаживание может использоваться при прореживании сигналов,
например, в случае, когда необходимо отобразить большую картинку
на небольшой экран. Или когда частота дискретизации звука снижается,
например, с 48000 Гц до 44100 Гц. Понижение частоты выборок — операция,
требующая предварительной обработки сигнала (низкочастотной фильтрации).
При сглаживании возникает ряд вопросов относительно качества
операции:
— сколько элементов использовать в отдельной итерации?
— какое сглаживание считать оптимальным?
— насколько корректно применяется текущий алгоритм сглаживания,
не теряется ли после обработки «полезный» сигнал?
Один из самых простых способов сглаживания является усреднение:
yi =
1
· (xi+1 + xi + xi−1 ).
3
(6)
Количество элементов, используемых для усреднения может разниться
в зависимости от природы усредняемого признака. Если рассмотреть пример
произношения любого слова [28], то влияние сигналов (отсчетов) снижается
прямопропорционально расстоянию между этими отсчетами, поэтому
использование «больших расстояний» при сглаживании приводит к потере
«полезного» сигнала.
Применительно к автомобилю в качестве примера можно привести
значения скорости в разное время. Скорость автомобиля в некоторой начальной
точке отсчета никак не зависит от скорости через час, однако, скорость за
секунду до текущего значения оказывает влияние на текущую — водитель
нажал на педаль газа, и текущая скорость повысилась на некоторое значение
относительно предыдущего.
28
Становится очевидным, что количество слагаемых в сглаживании
с помощью усреднения должно зависеть от того, насколько сильно зависят или
влияют друг на друга соседние отсчеты.
Более оптимальным, с точки зрения уровня сглаживания, является
медианная фильтрация.
Медианный фильтр представляет собой оконный фильтр, последовательно
скользящий по массиву сигнала и возвращающий на каждом шаге один из
элементов, попавших в окно (апертуру) фильтра [29]. Выходной сигнал yi
скользящего медианного фильтра шириной 2n + 1 для текущего отсчета i
формируется из входного временного ряда ...,xi−1 ,xi ,xi+1 ,... по формуле:
yi = med(xi−n ,...,xi−1 ,xi ,xi+1 ,...,xi+n ).
(7)
Как правило, апертура медианного фильтра устанавливается с нечетным
числом элементов. Медианная фильтрация реализуется в виде процедуры
локальной обработки отсчетов в скользящем окне, которое включает
определенное число отсчетов сигнала. Для каждого положения окна выделенные
в нем отсчеты ранжируются по возрастанию или убыванию значений. Средний
по своему положению отчет в ранжированном списке называется медианой
рассматриваемой группы отсчетов. Этим отсчетом заменяется центральный
отсчет в окне для обрабатываемого сигнала. В силу этого медианный фильтр
относится к числу нелинейных фильтров, заменяющим медианным значением
аномальные точки и выбросы независимо от их амплитудных значений, и является
устойчивым по определению, способным аннулировать даже бесконечно
большие отсчеты. В качестве начальных и конечных условий фильтрации
обычно принимаются концевые значения сигналов либо медиана находится
только для тех точек, которые вписываются в пределы апертуры.
Медианная фильтрация позволяет исключить из графика слишком
большие амплитудные значения, которые очевидно являются ненужными
выбросами, например, в период, когда были потеряны данные. Еще одним
недостатком медианной фильтрации является снижение качества фильтрации
при приближении к границам. Также при резких скачках графика и маленьком
значении апертуры может стать сглаживание графика по уровню начальных
значений, что может исказить данные.
С учетом перечисленных недостатков результирующий график нельзя
29
считать достаточно сглаженным и возникает необходимость применять
дополнительные фильтры, которые еще больше укажут на аномальные значения.
Наиболее подходящими и популярными решениями для сглаживания
и поиска экстремумов являются фильтры по скользящему среднему. Скользящее
среднее — общее название для семейства функций, значения которых в каждой
точке определения равны среднему значению исходной функции за предыдущий
период [30]. Скользящие средние обычно используются с данными временных
рядов для сглаживания краткосрочных колебаний и выделения основных
тенденций или циклов.
Математически скользящее среднее является одним из видов свертки.
В общем случае взвешенные скользящие средние вычисляются по формуле:
W W M At =
n−1
∑
wt−i · pt−1 ,
(8)
i=0
где W W M At — взвешенное скользящее в момент времени t,
n — количество значений исходной функции,
wt−i — весовой коэффициент (t − i)-го значения,
pt−i — значение функции в момент времени, отдаленный на i интервалов.
Важно отметить, что в этой формуле присутствуют весовые
коэффициенты, которые позволяют повышать значимость некоторой точки
временного ряда в зависимости от расстояния до текущего отсчета.
Наиболее простой в реализации фильтр из набора средних скользящих —
фильтр по простому скользящему среднему. Фильтр представляет собой
обыкновенное вычисление среднего значения. Уровень сглаживания зависит
от количества элементов, учитываемых при подсчете, а весовой коэффициент
всегда равен единице. Как было выяснено ранее, данный метод не дает
достаточного уровня сглаживания и обладает рядом недостатков.
Бывает, что исходная функция многомерна, то есть представлена
сразу несколькими связанными рядами. В этом случае, может возникнуть
необходимость объединить в итоговой функции скользящей средней все
полученные данные. Например, временные ряды биржевых цен, обычно,
для каждого момента времени представлены как минимум двумя значениями —
ценой сделки и её объёмом. Необходим инструмент для вычисления скользящей
средней цены, взвешенной по объёму.
30
В этих и подобных случаях применяются взвешенные скользящие средние.
В случае временных рядов, последние — более актуальные данные могут быть
весомее предыдущих.
Взвешенное скользящее среднее (англ. weighted moving average,
WMA) или линейно взвешенное скользящее среднее — скользящее среднее,
при вычислении которого вес каждого члена исходной функции, начиная
с меньшего, равен соответствующему члену арифметической прогрессии. То
есть, при вычислении WMA для временного ряда последние значения исходной
функции более значимы чем предыдущие, причём функция значимости линейно
убывающая.
Например, для арифметической прогрессии с начальным значением
и шагом, равным 1, формула вычисления скользящей средней примет вид:
∑
2
W M At =
(n − i) · pt−i ,
n · (n + 1) i=0
n−1
(9)
где W M At — предыдущий результат в точке t,
n — количество значений исходной функции,
pt−i — значение функции в момент времени, отдалённый на i интервалов.
Экспоненциально взвешенное скользящее среднее, (англ. exponentially
weighted moving average, EWMA) экспоненциальное скользящее среднее —
разновидность взвешенной скользящей средней, веса которой убывают
экспоненциально и никогда не равны нулю.
Пример графиков убывания весов для экспоненциального скользящего
среднего и взвешенного скользящего среднего представлены на рисунке 3.
Экспоненциальное скользящее среднее определяется формулой:
EM At = α · pt + (1 − α) · EM At−1 ,
(10)
где EM At−1 — предыдущий результат в точке t − 1,
pt — значение исходной функции в момент времени t,
α — коэффициент скорости уменьшения весов, α ∈ [0, 1], чем меньше
значение, тем больше влияние предыдущих значений на текущее.
Первое значение экспоненциального скользящего среднего, обычно
принимается равным первому значению исходной функции.
31
Рисунок 3 – Графики убывания весов: слева экспоненциальное скользящее
среднее, справа взвешенное скользящее среднее
Рисунок 4 – Результаты алгоритмов сглаживания со скользящим средним
После детального экспертного анализа графика, представленного
на рисунке 4, фрагмент которого представлен также на рисунке 5, принято
решение для сглаживания данных в работе использовать экспоненциальное
скользящее среднее.
1.5 Проблема концептуального дрейфа и способы ее решения
Во многих сценариях статистика объекта может меняться, эта
проблема известна как концептуальный дрейф [31]. Изменения конфигурации
32
Рисунок 5 – Фрагмент обработанных данных
контролируемого объекта могут произойти в любое время и могут изменить
поведение системы. В таких случаях подсистема поиска должна адаптироваться
к новому определению «нормального поведения» в автоматическом режиме
без присмотра.
Так же важным является отсутствие или снижение к допустимому
минимуму количества ложных срабатываний, так как не исключено, что в случае
множественных ложных срабатываний корректный предупреждающий сигнал
алгоритма будет проигнорирован.
Помимо описанных выше фильтров существуют методы технического
анализа, позволяющие выявить тренды, то есть предсказать возможное изменение
поведения объекта. Эти методы применяются чаще в финансовой сфере, но могут
быть применены и для описания ситуации в потоке данных.
1.5.1 Аллигатор
Принцип работы метода схож с медианным фильтром, однако его главная
задача — дать представление о зарождающемся тренде в потоке данных [32].
У этого метода существует несколько модификаций, наиболее популярной
из которых является Аллигатор Била Вильямса. Пример результатов анализа
представлен на рисунке 6.
33
Рисунок 6 – Пример результатов метода Аллигатор
Аллигатор Била Вильямса реализуется, как комбинация трех скользящих
средних разной длины, используя разный сдвиг вперед.
Скользящее
среднее
первого
типа,
называется
«Челюсть
Аллигатора», также называют линией баланса для временного отрезка,
за который используются данные. Такой вид кривой представляет собой
тринадцатипериодное скользящее среднее, которое будет сдвинуто на графике
на 8 точек вперед:
AJaw = SM A(yi , 13, 8),
(11)
где SM A — сглаженное скользящее среднее.
Скользящее среднее второго типа называют «Зубы Аллигатора» в случае,
если линия баланса для рассматриваемого временного ряда на порядок ниже.
Линия представляет собой восьмипериодное скользящее среднее, сдвинутое
на графике при визуализации данных на пять точек в будущее:
AT eeth = SM A(yi , 8, 5).
(12)
Третий тип скользящего среднего называется «Губы Аллигатора»
при условии, что использовано пятипериодное скользящее среднее, которое было
сдвинуто на три точки вперед:
ALips = SM A(yi , 5, 3).
(13)
34
В индикаторе «Аллигатор» для расчетов применяется формула
сглаженного скользящего среднего. Самое первое значение рассчитывается,
исходя из SM A, суммируя yi . Второе и последующие скользящие средние
рассчитываются по формуле:
SM Ai =
Sum1 − SM Ai−1 + yi
,
n
(14)
где SM Ai — сглаженное скользящее среднее текущего значения,
Sum1 — первое значение y1 ,
SM Ai−1 — скользящее среднее на предыдущем шаге.
Скользящие средние с меньшим периодом оцениваются точно также,
но их желательно применять к более краткосрочному периоду.
Одним из самых больших плюсов метода «Аллигатор» является то,
что он позволяет избежать двоякого толкования большинства сигналов.
Метод «Аллигатор» применяют для определения, насколько сильным
будет последующее изменение поведения данных. Сигналом служит
переплетение скользящих средних, чем дольше такое происходит, тем дольше
будет держаться тренд в поведении данных.
Если на каком-то временном периоде амплитуда колебаний кривых
и расстояние между ними начнет увеличиваться, то скорее всего, в ближайшее
время поведение основного графика изменится.
Если линия с периодом «13» далека от значений графика исходных
данных, линия с периодом «8» — между кривыми «13 »и «5», то это служит
сигналом к появлению тренда, а окончание тренда предскажет момент, когда
линии разных периодов начнут переплетаться. Минус применения «Аллигатора»
в том, что он будет запаздывать при входе на тренд.
1.5.2 Полосы Боллинжера
Полосы Боллинджера позволяют получить статистическую оценку того,
как долго может держаться краткосрочное движение прежде, чем оно вернется
в состояние основной тенденции.
Метод требует построения трех линий:
— центральная линия может быть простым, экспоненциальным,
взвешенным или скользящим средним другого типа;
35
— верхняя линия представляет собой сумму скользящего среднего
и стандартного отклонения, умноженного на некоторый коэффициент;
— нижняя линия — это скользящее среднее без стандартного отклонения,
умноженного на коэффициент.
Под стандартным отклонением понимается среднеквадратическое
отклонение, которое вычисляется по формуле:
√∑
σ=
n
j=i (Pi
− P̄ )2
n
,
(15)
где P — цена актива, в случае с данными — значение данных,
N — количество периодов времени.
1.5.3 Средний истинный диапазон
Средний истинный диапазон (Average True Range, ATR) —метод анализа,
который предназначен для измерения волатильности (или изменчивости)
финансового инструмента. Изначально он предназначался для фьючерсов
на сырье, т.к. во времена разработки (1978) на американских рынках товары
и сырье были намного более изменчивы чем акции [33].
Этот показатель выводится путем усреднения по какому-либо из методов
— простому среднему, экспоненциальному или другому.
Используют ATR на различных временных промежутках. Экстремальные
значения индикатора часто указывают на начало нового движения. Как и полосы
Боллинджера, ATR не может предсказать направление или продолжительность
движения, он указывает только на уровень активности (в случае данного
исследования — аномальности).
Основную концепцию индикатора «cредний истинный диапазон» можно
выразить следующим образом: чем больше значение индикатора, тем больше
вероятность разворота тренда; чем меньше значение индикатора, тем слабее
направленность тренда. При большом периоде ATR может запаздывать.
1.5.4 Метод зигзага
При исследовании данных был сделан вывод, что наиболее подходящим
фильтром-индикатором поведения данных будет «Зигзаг». Его применяют для
обнаружения трендов, когда позволительно опускать экстремумы, которые
36
отличаются незначительно от текущих данных. Зигзаг — это ломаная линия, узлы
расположены в точках, где значения принимают максимальные и минимальные
значения. Существует много модификаций зигзага, которые зависят от целей
исследователя.
Порой выгодно сочетать зигзаг с другими фильтрующими методами,
например, с индикаторами конвертов (модификация линий Боллинджера),
с условием, что необходимо подобрать такие параметры для задания конвертов,
что почти все узлы будут ограничены линиями конвертов.
В исследовании применялся метод зигзага с опережением, основная
задача при этом — предсказывание положения следующего экстремума. Текущий
экстремум формируется относительно поступающих данных. Прогнозируемый
узел должен предсказать расположение следующего экстремума. Конверты
скользящих применяются для ограничения зигзага, чтобы он проходил
в дозволенной конвертами области. При исследовании рассматривались такие
линии конвертов, отклонения которых от узлов зигзага были минимальными.
Для максимумов и минимумов зигзага искать эти линии необходимо отдельно.
Теперь детализация про конверты скользящих, порой их называют
огибающими линиями, которые образуются двумя скользящими средними, одна
из которых смещена вверх, а другая — вниз.
Скользящие определяют верхние и нижние границы колебаний значений
дискретных данных.
Для построения прогноза используется последняя влиятельная точка
(экстремум), то есть при поиске вершины зигзага, необходимо взять характерные
точки огибающих кривых.
При реализации зигзага сначала должны быть найдены первый
и последний экстремумы аномалии, и максимум с минимумом во всем
объеме данных, чтобы в процентном соотношении задать дрейфующее плато
(10% от размаха максимума и минимума объема данных по оси Y , также
необходимо задать размах плато и по оси X).
Важные детали: скользящее среднее — это нижняя огибающая линия,
индикаторы рассчитываются на полном объеме данных, то есть при подаче новых
данных происходит перерасчет.
Наблюдения за индикатором показали:
— отклонения координат экстремумов зигзага от прогнозируемых
37
расположены в зоне допустимых значений. Оказалось, что большинство узлов
расположено вблизи от огибающих линий. Это качественная оценка;
— изгибы графика очень зависимы от рассматриваемого окна данных;
— когда экстремум огибающей линии сверху обгоняет его, то это говорит
о том, что присутствует тенденция к росту значений графика.
Реализация метода зигага требует реализации двух алгоритмов:
— алгоритм поиска узлов зигзага на заданном временном окне, который
сохраняет их в разных массивах, отдельно вершины и отдельно впадины (для
удобства расчета конвертов);
— алгоритм, который вычисляет последние узлы и сохраняет их в один
массив. Этот метод необходим для визуализации зигзага.
Достоинства:
— самая затратная по времени функция — поиск экстремумов, которые
принимаются к рассмотрению и визуализации;
— вся необходимая информация для каждого значения данных не только
доступна в любой момент истории, но и также доступна для любого момента
истории;
— отсутствие висящих вершин;
— возможность эффективного поиска вершин без перебора значений;
— очень быстрая работа по сравнению с другими методами;
— корректная обработка истории и переключения таймфреймов.
Недостатки:
— требуется большой объем оперативной памяти для вычислений;
— незначительное запаздывание;
— сложности разметки экстремумов (настройка зависит от целей).
1.6 Методы нахождения экстремумов в многоэкстремальной задаче
При исследовании многоэкстремальной задачи можно применять
несколько подходов:
— аналитический, если известна функция, исследуемая на экстремум;
— численный, если есть лишь набор данных.
Плюсы аналитического подхода состоят в том, что ни один экстремум
не будет упущен, достаточно простыми методами вычитывается точное
расположение минимума или максимума функции любого порядка.
38
Численные методы применяются при наличии набора данных, то есть
применимы как при наличии заданной зависимости между параметрами, так
и при ее отсутствии, но необходимо для каждой ситуации подбирать наиболее
подходящий метод, который будет давать наименьшую погрешность и работать
быстрее на рассматриваемом наборе данных.
В связи с этим было предложено к рассмотрению несколько известных
численных методов. Для использования методов, в которых необходимо
знание зависимости между данными, предложено построить интерполяционный
многочлен Лагранжа, чтобы определить области расположения возможных
экстремумов.
Далее описаны алгоритмы применяемых методов: интерполяционный
многочлен Лагранжа и интерполяция с помощью сплайн-функций.
Результаты интерполяции претерпевают изменения в зависимости
от степени интерполирующего полинома. При параболической и кусочнолинейной интерполяции результат в значительной степени зависит от количества
узлов интерполяции. Хорошие результаты имеют место быть при интерполяции
кубическими сплайн-функциями.
Многочлен Лагранжа задается для n + 1 набора точек (xi , yi ), степенью
не выше n, причем многочлен L(x) — единственный, где L(xi ) = yi .
Формула для задания многочлена:
L(x) = Σni=1 yi li (x),
где li (x) = Πnj=0,j̸=i
x − xj
.
xi − xj
(16)
(17)
Необходимо отметить, что узлы интерполяции могут не быть
равноотстоящими друг относительно друга.
С помощью второй производной полинома определить экстремумы,
если функция дифференцируема.
1.6.1 Полином Ньютона
Для математической обработки дискретных данных применима кусочнолинейная интерполяция с помощью полинома Ньютона. Важно отметить, набор
данных разбивается на несколько подинтервалов, причем конечная точка одного
интервала является начальной точкой следующего, интерполянт строился
39
для каждого подинтервала. Графики данных, которые интерполировались
полиномами в алгебраической форме, склеивались на границах подинтервалов
равными узловыми значениями. Предложенная интерполяция обеспечила
непрерывность, более того, была получена непрерывная дифференцируемость
всюду, кроме границ подинтервалов.
Полином Ньютона требует равного расстояния между узлами
интерполяции, формула для задания многочлена:
m−k k
Pn (x) = Σnm=0 Cxm Σm
Cm f (k),
k=0 (−1)
(18)
где Cxm — биномиальные коэффициенты.
С помощью второй производной полинома определить экстремумы, если
функция дифференцируема.
1.6.2 Метод ломаных
Используется для поиска глобального минимума функции, который
удовлетворяет условию Липшица на отрезке [a,b], функция f (x) удовлетворяет
условию при существовании константы Липшица L > 0 такой, что |f (x′ ) −
f (x′′ )| ≤ L|x′ − x′′ | для всех x′ , x′′ ∈ [a,b]. Смысл метода заключается в том, что
строятся ломаные, приближающиеся к графику данных снизу и имеющие угловые
коэффициенты всех звеньев ±L, но для начала необходимо выяснить значение
константы.
Разделить данные на интервалы, на каждом интервале через первую (A)
и последнюю (B) точки интервала на графике данных построить прямую,
вычислить тангенс угла наклона прямой
tan α =
yB − y A
BC
=
,
AC
xB − xA
(19)
где xA < xB — значения аргументов,
yA , yB — соответствующие значения по оси y.
Как только значение тангенса изменится при переходе от интервала
[A1 , B1 ] к [A2 , B2 ], то необходимо рассмотреть интервал с концами [B1 , A2 ]
и применить к нему один из методов пункта 3. Занести значение найденного
экстремума в массив, затем для нахождения глобальных экстремумов, применить
метод нахождения максимального и минимального значений.
40
Наличие локальных минимумов функции f (x) часто затрудняет поиск
глобального минимума. Из-за этого многие численные методы применимы только
в случае, когда минимум является и глобальным. Это дает гарантию сходимости
метода, иначе при применении метода нет гарантии, что глобальный экстремум
будет обнаружен верно, поэтому метод деления отрезка пополам, метод золотого
сечения и метод дихотомии признаны подходящими для унимодальных функций.
1.7 Определение сигнатуры и кластеризация
Кластеризация [34] используется для разбиения заданной выборки
объектов на подмножества, называемые кластерами, так, чтобы каждый кластер
состоял из схожих объектов. При использовании данного класса методов
полагаются на одно из следующих предположений:
— нормальные объекты принадлежат кластеру, аномальные — нет;
— нормальные объекты лежат близко к центру кластера, аномальные —
вдали от центра;
— нормальные объекты принадлежат большим, плотным кластерам,
в то время как аномалии принадлежат небольшим и разреженным.
Методы, основанные на кластеризации, оценивают расстояние до объектов
на основании информации о кластере, к которому принадлежат объекты,
в то время как методика использования ближайших соседей пользуется
локальным окружением каждого объекта. Достоинствами данного класса методов
являются возможность обучения без учителя, адаптация методов к различным
типам данных и небольшое число вычислений при отнесении объектов
к нормальным или аномальным (так как число кластеров обычно незначительно).
К недостаткам следует отнести сильную зависимость от выбранного алгоритма
кластеризации и специфики его работы (метод кластеризации не оптимизирован
для задачи обнаружения аномалий, аномалии — лишь побочный результат
от работы алгоритма кластеризации и т. п.).
Сигнатура — это набор характеристик, однозначно описывающих
контекстную аномалию. Одним из способов вычисления сигнатуры является
метод, предложенный в статье [35] в 1962 году. В данном исследовании
поднимается проблема распознавания графических образов независимо
от их положения, размера и ориентации. Автор подчеркивает, что методы,
используемые для распознавания графических образов, должны быть
41
нечувствительными к изменениям объекта. Характеристики изображения,
не зависящие от его афинных преобразований, называются инвариантами.
Инварианты позволяют осуществлять сравнение графических образов. Более
того, инварианты дают возможность определять классы похожих объектов,
а также обладают способностью к обобщению, что является особенностью
систем искусственного интеллекта.
В работе [35] автор математически обосновывает возможность
применения теории двумерных инвариантных моментов для обработки
информации, представленной в графическом виде. Данная теория основывается
на вычислении интегральных моментов. Момент в случае изображения является
характеристикой контура графического образа, то есть границы объекта,
представленного на изображении. Таким образом, для сравнения двух контуров
достаточно сравнить их моменты.
В случае цифрового непрерывного изображения геометрический момент
изображения mpq рассчитывается по формуле:
∫
mpq =
∞
−∞
∫
∞
xp y q f (x,y)dxdy,
(20)
−∞
где x,y — координаты пикселя изображения,
f(x,y) — функция, которая характеризует яркость пикселя,
p + q) ≤ 3 — порядок момента.
Однако данные моменты не являются инвариантами. Чтобы получить
моменты, инвариантные относительно переноса, необходимо центрировать
моменты следующим образом:
∫
µpq =
∞
−∞
∫
∞
−∞
(x − x̄)p (y − ȳ)q f (x,y)dxdy,
(21)
m01
m10
, ȳ =
— центр тяжести фигуры.
m00
m00
Чтобы получить моменты, также инвариантные к операциям сжатия
и растяжения (масштабирования), необходимо провести нормировку:
где x̄ =
ηpq =
µpq
1+ p+q
µ00 2
.
(22)
На основе нормированных моментов можно вычислить семь моментов,
42
инвариантных относительно операций сдвига, масштабирования, поворота
и зеркального отображения по формулам (23). Моменты, представленные в таком
виде, используются для контурного анализа в библиотеке OpenCV.
ϕ1 =η20 + η02 ,
2
ϕ2 =(η20 − η02 )2 + 4η11
,
ϕ3 =(η30 − 3η12 )2 + (3η21 − µ03 )2 ,
ϕ4 =(η30 + η12 )2 + (η21 + µ03 )2 ,
ϕ5 =(η30 − 3η12 )(η30 + η12 )[(η30 + η12 ) − 3(η21 + η03 ) ]+
2
2
(23)
+ 3(η21 − η03 )(η21 + η03 )[3(η30 + η12 )2 − (η21 + η03 )2 ],
ϕ7 =(3η21 − η03 )(η30 + η12 )[(η30 + η12 )2 − 3(η21 + η03 )2 ]−
− (η30 − 3η12 )(η21 + η03 )[3(η30 + η12 )2 − (η21 + η03 )2 ].
В случае бинарного дискретного изображения контур задаётся набором
N точек с координатами (xi , yi ). Вычисление инвариантов осуществляется
по аналогии со случаем цифрового изображения, однако соотношение
для центральных моментов определяется следующим образом:
N
1 ∑
(x − x̄)p (y − ȳ)q , p + q ≤ 3,
mpq =
N i=1
N
N
1 ∑
1 ∑
x̄ =
xi ; ȳ =
yi .
N i=1
N i=1
(24)
Инварианты (23) являются сигнатурой графического образа, в качестве
которого можно рассматривать исходные данные, представляющие собой
аномалию. Поэтому инвариантный подход можно применять для решения
поставленной задачи, причём набор инвариант будет составлять сигнатуру
аномалии.
43
2 РАЗРАБОТКА ПРОТОТИПА ПОДСИСТЕМЫ ДИНАМИЧЕСКОГО
ПОИСКА АНОМАЛИЙ В ПОТОКЕ ДАННЫХ IOT-УСТРОЙСТВ
Задача разработки подсистемы в обобщенном виде выглядит так: в каждый
момент времени t от датчика приходит набор данных xt . Необходимо в каждый
момент времени определить, является ли поведение объекта необычным.
Определение должно проводиться в режиме реального времени.
В случае постановки подобной задачи в алгоритме поиска должно быть
учтено условие: перед тем, как увидеть следующий набор данных xt+1 алгоритм
должен учитывать текущее и предыдущее состояния, чтобы определить, является
ли поведение объекта аномальным, а так же выполнять любые обновления модели
и переквалификацию. В отличие от пакетной обработки потоковые данные
невозможно разбить на блоки.
Как правило, данные от IoT-устройств отправляются большими потоками
и с высокой скоростью, что оставляет мало возможностей для человека, не говоря
уже об экспертном вмешательстве.
Таким образом, работа в неконтролируемом, автоматизированном режиме
часто является необходимостью. Однако на начальном этапе требует постоянного
контроля и тонкой настройки. В связи с этим возникает необходимость разработки
интерфейса для конфигурации и оценки работы подсистемы и т. д.
Интерфейс позволит взаимодействовать с сервером с помощью
визуальных компонентов, проводить некоторые эксперименты, а в дальнейшем
стать инструментом для конфигурации автономной работы системы.
Для обеспечения наибольшего охвата платформ и исключения привязки
к одной из них наилучшим решением будет создание веб-приложения,
использование которого возможно через браузер, что позволяет всегда
использовать последнюю версию приложения.
2.1 Описание диаграммы вариантов использования
В соответствии с [36] диаграммы вариантов использования описывают
взаимоотношения и зависимости между группами вариантов использования
и действующих лиц, участвующими в процессе.
Важно
понимать,
что
диаграммы
вариантов
использования
не предназначены для отображения проекта и не могут описывать внутреннее
44
устройство системы. Диаграммы вариантов использования предназначены для
упрощения взаимодействия с будущими пользователями системы, с клиентами,
и особенно пригодятся для определения необходимых характеристик системы.
Другими словами, диаграммы вариантов использования говорят о том,
что система должна делать, не указывая сами применяемые методы.
Далее в работе приведена UML-диаграмма вариантов использования
прототипа разрабатываемой подсистемы (Рисунок 7).
EMA
? ???????????????
<<include>>
? ? ????? ?????
????? ?
? ???????
????? ????
???????
<<extend>>
WMA
<<include>>
<<extend>>
<<include>>
? ???? ?
?????? ?
? ????? ?? ?
????????????
<<include>>
? ????????????
? ???? ???????????
???????
???? ????????
? ???????
? ?????
<<extend>>
EWMA
<<extend>>
<<include>>
EMA
??????? n
? ???????
????? ????
? ???? ???????????
??????? ???????
<<include>>
<<include>>
? ???????
? ????
<<extend>>
? ?????? ?????????
??????? ???? ????
K-means
<<extend>>
? ????????
????? ? ??
???? ????
? ???????
????? ????
<<extend>>
? ????????
???????? ?
???? ????
<<extend>>
? ????????
? ???????
??? ??? ????
?? ???????
Рисунок 7 – Диаграмма вариантов использования
При разработке подсистемы и продолжительное время после введения
ее в эксплуатацию предполагается, что веб-приложение понадобится, в первую
очередь, для исследований видов аномалий и тонкой настройки поиска,
соответственно основным пользователем подсистемы является исследователь,
т. е. в данном контексте термины «исследователь» и «пользователь» равнозначны
и взаимозаменяемы.
45
Чтобы получить доступ к возможностям системы пользователь, в первую
очередь, должен авторизоваться. После авторизации, пользователь может выбрать
набор данных, на которых будет проводится анализ, т. е. выбрать тип объекта,
конкретный объект и параметр (или пакет параметров), по которому будет
проводится исследование. Затем необходимо сузить набор больших данных
и выбрать шаг смещения окна. Эти параметры должны быть настраиваемы,
поскольку разрабатывается, в первую очередь, исследовательский инструмент
и здесь должна быть возможность выбирать данные и параметры, по которым
будет проводится анализ.
Кроме выбора набора данных у пользователя есть возможность
конфигурации двух цепочек. Первая цепочка является цепочкой нормализации,
в которой выбираются фильтры для нормализации и их последовательность —
реализованы фильтры WMA, EMA, EWMA, список фильтров может изменяться,
т. к. подсистема находится в разработке.
У каждого фильтра есть параметры, поэтому их необходимо указать
при добавлении фильтра. После запуска цепочки нормализации начинается
обработка данных — данные последовательно проходят через все фильтры
в порядке, заданном цепочкой. Результатом, который видит пользователь —
два аппроксимированных графика: график исходных данных и график данных,
обработанных с помощью фильтров. Аппроксимация графиков требуется в связи
с тем, что мощность клиентской машины не позволяет работать с большим
количеством точек (не более 5000 точек).
Кроме выполнения цепочки нормализации существует возможность
конфигурировать цепочки анализа. Здесь исследователь может выбрать метод,
который будет применяться для поиска аномалий — нейронная сеть или k-means.
Результатом работы этого этапа является некоторый отчет о поиске аномалий на
выбранном участке данных. На этапе обучения в случае, если аномалия была
найдена впервые и может подходить под несколько кластеров, то исследователь
может выбрать самостоятельно, границы какого кластера необходимо расширять
или же следует создать новый.
После того, как аномалия была кластеризована, есть возможность извлечь
данные об анализе (например, идентификатор кластера) и сохранить для того,
чтобы впоследствии иметь возможность загрузить эту информацию (получить
информацию об анализе). Это сделано для того, чтобы иметь возможность сказать,
46
с помощью какого метода была получена та или иная аномалия и из нескольких
экспериментов (цепочек) выбрать лучшую цепочку для обработки конкретного
типа объекта и конкретного параметра. Также можно сохранить данные
конкретной аномалии.
2.2 Описание диаграммы компонентов
Полный проект программной системы представляет собой совокупность
моделей логического и физического представлений, которые должны быть
согласованы между собой. В языке UML для физического представления
моделей систем используются так называемые диаграммы реализации, которые
включают в себя две отдельные диаграммы: диаграмму компонентов и диаграмму
развертывания.
Диаграмма
компонентов
описывает
особенности
физического
представления системы. Диаграмма компонентов позволяет определить
архитектуру разрабатываемой системы, установив зависимости между
программными компонентами, в роли которых может выступать исходный,
бинарный и исполняемый код [37]. Во многих средах разработки модуль или
компонент соответствует файлу. Пунктирные стрелки, соединяющие модули,
показывают отношения взаимозависимости, аналогичные тем, которые имеют
место при компиляции исходных текстов программ. Основными графическими
элементами диаграммы компонентов являются компоненты, интерфейсы и
зависимости между ними.
В разработке диаграмм компонентов участвуют как системные аналитики
и архитекторы, так и программисты. Диаграмма компонентов обеспечивает
согласованный переход от логического представления к конкретной реализации
проекта в форме программного кода. Одни компоненты могут существовать
только на этапе компиляции программного кода, другие – на этапе его исполнения.
Диаграмма компонентов отражает общие зависимости между компонентами,
рассматривая последние в качестве отношений между ними.
Диаграмма компонентов, соответствии с которой будет работать
подсистема поиска, представлена на рисунке 8.
Основными компонентами подсистемы динамического поиска аномалий
в потоке данных IoT-устройств стали четыре компонента: Mediator, Normalizer,
Analyzer, Client Layer.
47
Рисунок 8 – Диаграмма компонентов
Client Layer — клиентское веб-приложение на React, которым должны
пользоваться исследователи для управления подсистемой. Из этого компонента
отправляется данные цепочек нормализации и анализа, которые принимает
Mediator.
Mediator — управляющий компонент-посредник, выступающий в роли
контролера. Компонент работает с результатами трех других компонентов:
— данные о цепочках обработки и анализа распределяются здесь для
последующей сортировки и отправки компонентам Normalizer и Analyzer;
— результаты работы компонентов Normalizer и Analyzer должны быть
сохранены во временную память для быстрого доступа, это так же задача
компонента Mediator, в качестве временного хранилища используется база
данных MongoDB.
Normalizer — компонент, который проводит нормализацию и
обрабатывает данные. После обработки данные могут быть предоставлены
для анализа, либо сохранены во временное хранилище. Для получения данных
компонент взаимодействует с системой обмена данными, которая не является
частью подсистемы поиска, но входит в систему Rightech IoT Cloud.
Analyzer — компонент представляет собой класс, в котором хранятся
реализации методов поиска аномалий на нормализованных данных, которые
были перечислены ранее. Компонент получает на вход управляющую
последовательность команд в виде цепочки анализа от компонента Mediator
48
и предварительно нормализованные входные данные от Normalizer. В случае,
когда подсистема будет работать в автономном режиме и будет найдена аномалия,
компонент автоматически отправляет сообщение во внутреннюю подсистему
взаимодействия с сервисами партнеров, либо напрямую — в СRM-систему
бизнес-партнеру, в зависимости от договоренности между компаниями, а также
доступности внутренней подсистемы.
2.3 Разработка серверной части
Перед началом проектирования системы необходимо определиться
с инструментами, которые будут использоваться в разработке. Для разработки
серверной части, в первую очередь, необходимо определиться с используемым
языком программирования. Среди большого разнообразия представленных
средств был выбран язык программирования Python, поскольку это —
универсальный язык программирования, на котором возможно реализовывать
практически любые проекты, в том числе и веб-сервер. Более того, язык Python
обладает значительной поддержкой со стороны сообщества.
Python предоставляет множество инструментов для математических
вычислений, например, NumPy для научных вычислений, scikit-learn —
библиотека для работы с алгоритмами машинного обучения, Matplotlib —
для визуализации данных, Pandas, предоставляющий структуры данных для
работы с различной информацией и множество других библиотек. Библиотеки
готового кода предоставляют возможность быстрого создания прототипа, что
является большим преимуществом.
К недостаткам Python можно отнести низкую скорость исполнения
программ и динамическую типизацию. По скорости исполнения Python
проигрывает таким языкам как Java, C или C++. Динамическая типизация
является как преимуществом, которое дает больше гибкости при разработке,
так может вызвать и проблемы с поддержкой кода при значительном росте
кодовой базы.
Исходя из перечисленных фактов, язык Python является инструментом,
достаточным для разработки прототипа. В случае снижения производительности,
в дальнейшем некоторые части могут быть заменены на вызовы кода,
написанного на более производительном языке.
49
2.3.1 Выбор фреймворка
Одним из главных преимуществ Python является поддержка сообществом
и большое количество готового кода. Это дает возможность выбрать готовый
фреймворк, в котором содержится оптимальный набор готовых функций.
Наиболее популярные фреймворки для разработки веб сервисов на языке
Python — Django, Flask и Pyramid. Данные фреймворки предназначены
для реализации функций, присущих большинству веб-приложений, таких
как передача HTTP аргументов из URL в код [38].
Django — Python фреймворк, использующий концепцию MVC. В Django
уже присутствует большое количество встроенных возможностей, которые
востребованы при разработке приложения — панель администратора, интерфейс
для работы с базами данных, структуру каталога для работы с приложением и т. д.
Подобная организация позволяет разработчику подключать необходимые модули
с готовым кодом. Предпочтительно использовать Django для быстрой разработки
крупного проекта, например, блог, новостной сайт или электронный магазин,
без необходимости принимать множество решений об архитектуре приложения
и используемых компонентов. Также стоит сказать, что Django был выпущен в
2005 году, с тех пор растет в популярности и обладает крупным и активным
сообществом разработчиков. Фреймворк считается более сложным в освоении,
однако дополнительные возможности помогают в разработке однотипных
компонентов веб-приложения.
Flask — фреймворк, относится к категории микрофреймворков — каркасов
приложений, предоставляющих только базовые возможности, а выбор всех
компонентов необходимо провести самостоятельно — Flask реализует минимум.
Таким образом достигается простота и гибкость приложения. Flask совместим
как с Python версии 2, так и с Python 3. Фреймворк Flask выгодно использовать
при разработке небольших проектов, когда нужно в короткие сроки реализовать
веб-сервер. Flask был выпущен в 2010 году и, вместе с Django, только
растет в-популярности. Стоит заметить, что Flask фокусируется на простоте
и минимализме, запущенные приложения будут работать быстрее по сравнению
с приложениеями на основе Django.
Так же, как и Django, Pyramid нацелен на использование в крупных
проектах [39], однако, в отличие от него, предлагает разработчику свободу
в выборе используемых средств — какую базу данных (SQLAlchemy, SQLite,
50
DynamoDB, MongoDB и т. д.) или структуру URL использовать и т. д.
Учитывая те обстоятельства, что разрабатывается прототип приложения,
а также то, что отсутствует необходимость в широком выборе дополнительных
средств, в качестве основы для создания подсистемы был выбран Flask.
2.3.2 Выбор СУБД
В связи с возникшей необходимостью выбора СУБД проведем краткое
описание современных систем, которые могут подходить под текущую задачу.
Далее приведен краткий анализ наиболее популярных СУБД [40]. Microsoft
SQL Server, IBM DB2 и Oracle 12c, Oracle MySQL не рассматриваются в связи
с высокой стоимостью.
MariaDB — СУБД, предоставляющая как бесплатную, так и платные
версии. Данная СУБД является ответвлением от СУБД MySQL — необходимость
в ответвлении возникла для обеспечения свободного статуса СУБД (в отличие
от MySQL, ведется открытое обсуждение, и любой разработчик может внести
свой вклад в проект), поскольку политика компании Oracle не подразумевает этого.
Ядро этой базы данных предоставляет выбор системы хранения (XtraDB, InnoDB,
Aria, PBXT и FederateX), что позволяет более эффективно использовать ресурсы
и повысить скорость выполнения запросов. MariaDB совместима с MySQL
и может ее заменить, а многие разработчики MySQL сейчас занимаются
развитием MariaDB. К преимуществам данной системы можно отнести быстроту
работы, свободный статус и расширяемую архитектуру. Недостатком является
очень низкая стабильность.
PostgreSQL — профессиональное решение, которое распространяется
бесплатно. Это одна из самых известных и хорошо развитых баз данных.
Предоставляет простые встроенные инструменты для импорта данных из других
систем баз данных. Последние версии предлагают очень высокий уровень
безопасности и надежности, обработку больших объемов данных и поддержку
большого количества одновременных соединений. Также к преимуществам
данной СУБД можно отнести поддержку формата JSON, обработки огромных
данных (более терабайта), а к недостаткам — ее сравнительную медлительность
и сложности в конфигурировании, повышенные требования к квалификации
работающим с ней специалистам.
51
СУБД SQLite хранит данные в отдельных файлах и обращается к ним
напрямую, что позволяет повысить скорость при чтении информации. Большое
количество разработчиков используют ее в своих приложениях. Однако у SQLite
присутствует несколько серьезных недостатков — медлительность при записи
и отсутствие реализации многопользовательского режима. Таким образом, это
СУБД нельзя использовать в полноценных веб-серверах.
MongoDB — бесплатная СУБД, предоставляющая также коммерческую
версию. MongoDB может хранить структурированные и неструктурированные
данные. Также эта СУБД может хранить реляционные модели данных, хотя
и изначально не предназначена для этого — могут возникнуть просадки
производительности. MongoDB последних версий поддерживает документы
NoSQL, в том числе json, а также обладает высокой скоростью. К недостаткам
можно отнести отсутствие поддержки языка SQL. Исходя из приведенных
описаний СУБД можно сделать вывод, что для данного проекта наиболее
удобным вариантом является MongoDB, поскольку данная СУБД может хранить
неструктурированные данные и обладает высокой скоростью, а в проекте не
требуется большое количество реляционных связей.
2.4 Алгоритм поиска аномалий
Центральным звеном подсистемы поиска аномалий в потоке данных
является алгоритм поиска. Ранее было сказано, что наиболее оптимальным
является поиск с помощью плавающего окна. Соответственно способ
перемещения по данным задан данным алгоритмом. Последовательность
обработки данных представлена на рисунке 9.
Обработка данных происходит следующим образом: сырые данные
нормализуются с помощью интерполяции и аппроксимации, затем происходит
фильтрация с помощью одного или нескольких фильтров. Далее перед тем,
как классифицировать аномалию, если она была найдена, можно попытаться
предсказать направление движения данных с помощью алгоритмов предсказания
трендов. Это позволит по незавершенной части аномалии уже судить о ее
принадлежности к некоторому классу. После этого вычисляется сигнатура
аномалии без предсказания тренда и с предсказанными значениями, в таком
случае незаконченная сигнатура аномалии не может быть отнесена к какому либо
классу и кластеризацию будет проходить предсказанная аномалия.
52
В случае с предсказанием тренда можно избавиться от проблемы
концептуального дрейфа, например, когда нормальное поведение объекта
находится в переходном состоянии алгоритм может определить это как аномалию,
а предсказание может «убедить подсистему в нормальном поведении объекта».
Рисунок 9 – Последовательность обработки данных
53
2.4.1 Реализация определения сигнатуры
Описанный в пункте 1.7 метод Ху представлен для задачи, имеющей
большую размерность, чем задача, поставленная в данной работе. Приведение
метода интегральных инвариантов Ху к виду, который может быть применён
к контекстным аномалиям является нетривиальной задачей, математическое
обоснование которого выходит за рамки данного исследования. В связи
с этим был предложен альтернативный метод поиска сигнатур, реализация
которого включает использование уже существующей библиотеки SciPy,
написанной на языке Python. Предложенный подход основывается на том,
что исследуемая зависимость может быть интерполирована непрерывной,
ограниченной и определённой на заданном отрезке функцией, что в свою очередь
позволяет использовать теорему Вейерштрассе об аппроксимации функции
полиномом степени n.
Пусть f — непрерывная функция, определенная на отрезке [a, b]. Тогда
для любого ε ≥ 0 существует такой многочлен степени p с вещественными
коэффициентами, что для всех x ∈ [a, b] одновременно выполнено условие:
|f (x) − p(x)| ≤ ε.
(25)
В использованном методе последовательно осуществляется интерполяция
каждой аномалии на заданном отрезке, после чего полученная зависимость
аппроксимируется полиномами различных степеней до тех пор, пока
среднеквадратичное относительное отклонение полученного полинома
от исходной зависимости не достигнет заданного пользователем значения,
или пока степень полинома не превысит значения 100. За оптимальную степень
полинома в первом случае принимается минимальное значение, при котором
выполняется заданное пользователем ограничение на ошибку, а во втором —
значение, при котором отклонение от начальных данных минимальное из всех
рассмотренных. В данном случае сигнатурой будет являться 100-мерный
вектор коэффициентов полинома (если степень полинома n меньше 100,
то соответствующие коэффициенты [n + 1; 100] принимают нулевое значение).
На рисунке 10 изображена тестовая аномалия, выявленная при
отслеживании изменения скорости автомобиля при движении по населённому
пункту. Также на рисунке представлены графики полиномов, использованных
для аппроксимации тестовой аномалии, со степенями, находящимися
54
Рисунок 10 – Применение полиномов разных степеней
в диапазоне [1; 16]. Очевидно, что начиная со степени полинома n = 12,
полученная зависимость начинает давать ложное представление о характере
аномалии. Данное утверждение может быть объяснено тем, что с увеличением
степени полинома метод склонен к переобучению, что ведет к значительным
отклонениям полинома от значений, полученных с помощью интерполяции
исходного графика.
55
2.4.2 Реализация кластеризации
На предыдущем шаге каждой выявленной аномалии была поставлена
в соответствие её сигнатура. Необходимо определить, каким образом полученные
аномалии разделить на классы схожих по смысловой ситуации объектов.
Для решения данной проблемы необходимо провести кластеризацию сигнатур
аномалий, представленных в виде n-мерных векторов (т.к. вычисление сигнатуры
проводилось на основе аппроксимации полиномом, то размерность пространства
будет равняться 100).
Задачей кластеризации является разбиение множества исходных векторов
на группы, называемые кластерами. Объекты попадают в один и тот же кластер,
исходя из их «похожести» друг на друга, мерой которой является расстояние
между объектами. Выбор метрики, на основе которой рассчитывается расстояние,
полностью зависит от поставленной задачи. Следует отметить, что в отличие
от методов классификации кластеризация является задачей обучения без учителя,
то есть заранее неизвестно, какому классу принадлежит тот или иной объект
обучающей выборки, кроме того, зачастую количество кластеров также является
неизвестным.
Принято разделять алгоритмы кластеризации на следующие типы:
иерархические и плоские, чёткие и нечёткие.
Иерархические алгоритмы позволяют представлять исходную выборку
в виде системы вложенных разбиений на непересекающиеся кластеры. Корнем
полученного таким образом дерева кластеров является вся выборка, а в листьях
находятся наиболее мелкие кластеры. В отличие от иерархических алгоритмов
плоские алгоритмы строят единственное разбиение на кластеры.
Что касается чётких алгоритмов кластеризации, то их суть заключается
в том, что каждому объекту ставится в соответствие единственный кластер.
Нечёткая кластеризация основывается на том, что каждому объекту ставится
в соответствие набор чисел, отражающих вероятность попадания данного объекта
в определённый кластер.
В процессе разработки прототипа использовались следующие
иерархические алгоритмы кластеризации: алгоритм k-means (иерархический,
чёткий), алгоритм c-means (иерархический, нечёткий), алгоритм DBSCAN
(иерархический, чёткий).
Метод k-средних (k-means) является одним из наиболее распространенных
56
методов кластеризации. Данный алгоритм является четким, иерархическим
и итерационным.
На первом этапе алгоритма в исходном множестве случайным образом
выбирается k точек. Выбранные точки принимаются за центры кластеров.
Затем все точки разбиваются на кластеры: для каждой точки находится центр
кластера, расположенный ближе остальных центров. На второй итерации у всех
полученных кластеров вычисляется новый центр, после чего вычисляется новое
разбиение. Цикл повторяется до тех пор, пока полученный на очередном шаге
набор центров не совпадет с набором на предыдущем шаге.
Одним из существенных недостатков данного метода является сильная
зависимость результатов обработки данных от начального разбиения. Наиболее
часто в качестве начального разбиения выбираются наиболее отдаленные друг
от друга точки. Еще один недостаток данного алгоритма — необходимость
задания точного числа кластеров в итоговом разбиении множества. Оптимальное
число кластеров может быть найдено с помощью введения внутрикластерного
расстояния:
l
∑
J(C) =
ρ(xi ,cyi ),
(26)
i=1
где l — размер выборки,
ρ — выбранная метрика,
xi — элемент выборки,
yi — кластер, которому принадлежит xi ,
cyi — центр кластера yi .
Число кластеров увеличивается до тех пор, пока значение J(C) не начнет
сходиться (Рисунок 11):
Не смотря на достаточно высокое качество работы, метод k-means
не справляется со случаями, когда объект не принадлежит ни к одному
из известных кластеров или в одинаковой степени принадлежит к разным
кластерам. Следует отметить, что данный недостаток свойственен всем четким
алгоритмам.
Распространенным алгоритмом, являющимся примером нечеткого
алгоритма кластеризации является алгоритм с-means (с-средних). Как и k-means,
данный алгоритм требует изначального задания количества кластеров и не имеет
гарантий глобальной оптимальности, однако в отличие от k-means он также
57
Рисунок 11 – Пример работы алгоритма k-means
требует серьезных вычислительных затрат, что является платой за решение
обозначенной выше проблемы. Как и алгоритм k-means, с-means является
итерационным методом. Результатом выполнения данного алгоритма является
матрица разбиения F , с размерностями M (число элементов в выборке) и (число
кластеров). На начальном этапе выполнения алгоритма матрица F заполняется
случайными значениями, таким образом чтобы все элементы матрицы (µkj )
принадлежали отрезку [0, 1], а также выполнялось условие:
c
∑
i=1
µki = 1
(27)
58
Далее центры кластеров определяются следующим образом:
∑M
m
k=1 µki · Xk
∑M m , i
k=1 µki
Vi =
= 1,c,
(28)
где Vi — центр i-ого кластера,
Xk — элемент выборки,
m — экспоненциальный вес, m ∈ [1,∞),
cyi — центр кластера yi .
Расстояние от элементов выборки до центров кластеров вычисляется
следующим образом:
Dki =
√
||Xk − Vi ||2 , k = 1,M , i = 1,c.
(29)
После вычисления расстояний осуществляется пересчет степеней
принадлежностей элементов выборки к кластерам:
µki =
∑c
j=1
(
1
Dki
Dkj
2 , k = 1,M , i = 1,c.
) m−1
(30)
Приведенные выше пункты повторяются до тех пор, пока не будет
выполнено условие остановки:
max(|µki − µ∗ki |) < ε или max(|Vi − Vi∗ |) < ε.
(31)
Здесь величины µ∗ki и Vi∗ соответствуют значениям, полученным
на предыдущей итерации.
В отличие от большинства алгоритмов, осуществляющих плоское
разбиение на кластеры сферической формы (поскольку эти алгоритмы
минимизируют расстояние от объекта до центра кластера), алгоритм
DBSCAN позволяет получать кластеры сложной формы, зачастую отличной
от сферической, что довольно удобно при решении многомерной задачи
кластеризации, поставленной в данном исследовании. Более того, DBSCAN
достаточно хорошо работает с зашумлёнными данными. Суть алгоритма
заключается в следующем: предполагается, что каждый кластер состоит
из объектов, в ε-окрестности которых находится как минимум Nmin других
59
объектов кластера. Алгоритм состоит из следующих этапов:
1) задаётся ε-окрестность и Nmin ;
2) выбирается произвольный объект выборки. Проверяется, чтобы
в заданной ε-окрестности находилось n ≥ Nmin объектов выборки. Если данное
условие не выполняется, объект помечается как шум, далее выбирается другой
произвольный объект;
3) если условие выполняется, то данный объект помечается
как принадлежащий кластеру. Все точки, находящиеся в её ε-окрестности,
проверяются по аналогии;
4) в некоторый момент все точки текущего кластера будут помечены. Когда
это произойдёт, необходимо выбрать следующий произвольный объект.
Рисунок 12 – Пример работы алгоритма DBSCAN
На рисунке 12 изображён пример работы алгоритма DBSCAN. По условию
задачи минимальное количество объектов, находящихся в ε-окрестности,
равнялось 3. Зелёным цветом представлены объекты, принадлежащие кластеру,
жёлтым цветом представлен объект, находящийся на границе кластера, красным
цветом изображены выбросы.
В процессе тестирования прототипа на разных наборах данных было
обнаружено, что результат работы алгоритмов кластеризации напрямую зависит
60
от набора исходных данных. Например, на тестовом наборе данных рисунка 13
только один из методов корректно определил аномалию, представляющую собой
параболу с увеличенной амплитудой.
Рисунок 13 – Виды одной аномалии с разной амплитудой
В связи с этим, было решено, что выбор подходящего для решения
конкретной задачи метода кластеризации будет осуществляться пользователем.
2.5 Реализация клиента веб-приложения
2.5.1 Выбор библиотеки для реализации клиентского приложения
В современных браузерах, таких, как Chrome и Firefox, могут быть
запущены полноценные приложения, ничем не уступающие приложениям,
написанным под определенную операционную систему. Для создания таких
приложений существует множество фреймворков. Самыми популярными
фреймворками являются React, Vue.js и Angular.
React — JavaScript-фреймворк с открытым исходным кодом для разработки
пользовательских интерфейсов. Основными особенностями React являются:
декларативность, компонентная основа и отсутствие привязанности
к определенному стеку технологий. Под декларативностью подразумевается
простота создания интерактивных компонентов, когда не нужно реализовывать
отдельные методы для обновления и отрисовки элементов страницы — React
делает это автоматически при обновлении данных (состояния) с помощью
Virtual DOM.
Второй особенностью React является компонентная основа.
И в декларативной модели возникает возможность разделения компонентов
на визуальные, которые отрисовывают данные, и «контейнерные» компоненты,
61
которые отвечают за манипуляции с данными. Таким образом, получается
разделение состояния и представления, что упрощает повторное использование
компонентов.
Третьей особенностью React является то, что он не привязан
к определенному набору технологий, с которыми он может работать,
в связи с этим, реализация пользовательского интерфейса может происходить
независимо от того, на каких технологиях построен сервер.
В дополнение к перечисленным свойствам, для данной библиотеки
существует специальная версия для мобильных устройств — React Native,
с помощью которой можно также просто создавать приложения для смартфонов,
не меняя при этом серверной части.
Vue.js — JavaScript-фреймворк с открытым исходным кодом для создания
пользовательских интерфейсов в парадигме реактивного программирования. Этот
фреймворк очень похож на React, но имеет несколько отличий.
Во-первых, все компоненты в React реализуют свой интерфейс в renderфункциях с использованием JSX, который имеет декларативный XML-подобный
синтаксис, а Vue.js поддерживает и HTML-шаблоны.
Другим отличием является реализация модульных (компонентных) стилей:
в React для этого используется подход CSS-in-JS, Vue.js позволяет использовать
знакомые веб-программистам style-теги.
Angular — это открытая и свободная платформа для разработки вебприложений, написанная на языке TypeScript. Именно TypeScript является
основным отличием от React и Vue.js. Использование TypeScript имеет ряд
весомых преимуществ, характерных для строго типизированных языков
программирования, однако для небольших приложений использование TypeScript
может быть связано с большими накладными расходами. По производительности,
скорости и сложности сборки React и Vue.js показывают более высокие
результаты, чем Angular.
В данной работе выбор между React и Vue.js в сторону React обусловлен
тем, что React использует более современные технологии шаблонизации
и построения компонентов, а также обладает бо́льшим сообществом
разработчиков.
62
ЗАКЛЮЧЕНИЕ
В ходе выполнения работы были проанализированы существующие
отечественные и иностранные решения по поиску аномалий в данных.
Рассмотренные подходы к обнаружению аномалий обладают достаточной
степенью универсальности и могут быть применены для различных
сценариев. Однако, как продемонстрировано в данной работе, перед
исследованием все равно возникает необходимость предобработки данных
и, как минимум, указания областей в пространстве данных, в которых следует
ожидать аномальное поведение.
Было предложено собственное решение, специализированное для работы
в конкретных условиях, которое в дальнейшем может быть модифицировано
и иметь широкую область применения.
В подсистеме поиска предусмотрена очень гибкая настройка
параметров фильтрации и кластеризации, а так же обширные возможности
для анализа аномальных данных. Кроме того, подсистема поиска может
работать в автономном режиме и с течением времени качество поиска
аномалий будет только расти, т.к. был решен ряд проблем, возникающих
при работе с потоковыми данными.
В изложенном материале присутствует подробный анализ существующих
решений, а также описана разработка прототипа инструмента, который позволит
руководству бизнеса отслеживать аномальные показания IoT-устройств в режиме
реального времени следовательно, все задачи поставленные в работе решены,
цель работы считается достигнутой.
63
СПИСОК ЛИТЕРАТУРЫ
1. Agarwal Basant, Mittal Namita. Hybrid Approach for Detection of Anomaly
Network Traffic using Data Mining Techniques // Procedia Technology. –– 2012. –– 1. ––
Т. 6. –– С. 996–1003. –– Режим доступа: https://www.sciencedirect.com/science/article/
pii/S2212017312006664.
2. Han Jiawei, Kamber Micheline, Pei Jian. Data Mining. Concepts
and Techniques. –– 3 изд. –– 2012. –– С. 740. –– ISBN: 978-0-12-381479-1. ––
Режим
доступа:
http://myweb.sabanciuniv.edu/rdehkharghani/files/2016/02/
The-Morgan-Kaufmann-Series-in-Data-Management-Systems-2011.pdf.
3. Rassam Murad A., Zainal Anazida, Maarof Mohd Aizaini. Advancements of
data anomaly detection research in Wireless Sensor Networks: A survey and open
issues. –– 2013.
4. Wireless sensor networks: a survey / I.F. Akyildiz, W. Su,
Y. Sankarasubramaniam, E. Cayirci // Computer Networks. –– 2002. –– 3. –– Т. 38,
№ 4. –– С. 393–422. –– Режим доступа: https://www.sciencedirect.com/science/article/
pii/S1389128601003024.
5. Chandola Varun, Mithal Varun, Kumar Vipin. A Comparative Evaluation of
Anomaly Detection Techniques for Sequence Data. –– 2008. –– Режим доступа: https:
//www.cs.umn.edu/sites/cs.umn.edu/files/tech_reports/08-021.pdf.
6. Chandola Varun, Banerjee Arindam, Kumar Vipin. Anomaly Detection : A
Survey // ACM Computing Surveys. –– 2009. –– Т. 41. –– Режим доступа: http://cucis.
ece.northwestern.edu/projects/DMS/publications/AnomalyDetection.pdf.
7. Wikipedia. Anomaly Detection [Электронный ресурс]. –– Режим доступа:
https://en.wikipedia.org/wiki/Anomaly_detection/ (дата обращения: 12.10.2017).
8. Wikipedia. Outlier Detection [Электронный ресурс]. –– Режим доступа: https:
//en.wikipedia.org/wiki/Outlier/ (дата обращения: 12.10.2017).
9. Online Six Sigma. Outlier Detection [Электронный ресурс]. –– Режим
http://sixsigmaonline.ru/baza-znanij/22-1-0-291
(дата
обращения:
доступа:
20.10.2017).
10. Miljković Dubravko. Review of Novelty Detection Methods // MIPRO/CTS. ––
2010. –– С. 27 – 32. –– Режим доступа: https://bib.irb.hr/datoteka/509342.Review_of_
Novelty_Detection_Methods.pdf.
11. An application of sensor-based anomaly detection in the maritime industry /
64
Andreas Brandsæter, Gabriele Manno, Erik Vanem, Ingrid Kristine Glad // Prognostics
and Health Management (ICPHM), 2016 IEEE International Conference on / IEEE. ––
2016. –– С. 1–8.
12. Xu Jingxin, Fookes Clinton. Automatic Event Detection for Signal-based
Surveillance. –– 2016. –– Режим доступа: https://pdfs.semanticscholar.org/495f/
a8f7d9d0e4d472c49de34a9d17343668f4a4.pdf.
13. Borne K. Effective Outlier Detection using K-Nearest Neighbor Data
Distributions: Unsupervised Exploratory Mining of Non-Stationarity in Data Streams //
Submitted to the Machine Learning Journal. –– 2010.
14. Model-based anomaly detection for discrete event systems / Timo Klerx,
Maik Anderka, Hans Kleine Büning, Steffen Priesterjahn // Tools with Artificial
Intelligence (ICTAI), 2014 IEEE 26th International Conference on / IEEE. –– 2014. ––
С. 665–672.
15. Anomaly detection in transportation corridors using manifold embedding /
Amrudin Agovic, Arindam Banerjee, Auroop R Ganguly, Vladimir Protopopescu //
Proceedings of the 1st International Workshop on Knowledge Discovery from Sensor
Data. –– 2007. –– С. 435–455.
16. Liu Fei Tony, Ting Kai Ming, Zhou Zhi-Hua. Isolation forest // Data Mining,
2008. ICDM’08. Eighth IEEE International Conference on / IEEE. –– 2008. –– С. 413–
422.
17. Шолохова А. А. Поиск аномалий в сенсорных данных на примере анализа
движения морского судна // Моделирование, оптимизация и информационные
технологии. –– 2017. –– Т. 3. –– Режим доступа: https://moit.vivt.ru/wp-content/
uploads/2017/08/Sholohova_3_1_17.pdf.
18. Cheboli Deepthi. Anomaly Detection of Time Series [Электронный
ресурс]. –– Режим доступа: https://conservancy.umn.edu/bitstream/handle/11299/
92985/?sequence=1 (дата обращения: 17.12.2017).
19. Salvador Stan, Chan Philip. Determining the number of clusters/segments in
hierarchical clustering/segmentation algorithms // Tools with Artificial Intelligence,
2004. ICTAI 2004. 16th IEEE International Conference on / IEEE. –– 2004. –– С. 576–
584.
20. Assumption-Free Anomaly Detection in Time Series. / Li Wei, Nitin Kumar,
Venkata Nishanth Lolla и др. // SSDBM. –– Т. 5. –– 2005. –– С. 237–242.
21. Hayes Michael A, Capretz Miriam AM. Contextual anomaly detection
65
framework for big sensor data // Journal of Big Data. –– 2015. –– 12. –– Т. 2, № 1. ––
С. 2. –– Режим доступа: http://www.journalofbigdata.com/content/2/1/2.
22. Антипов С. Г. Исследование и разработка методов и алгоритмов
обобщения знаний для систем поддержки принятия решений реального времени :
Дисс… кандидата наук / С. Г. Антипов ; НИУ МЭИ. –– 2016. –– С. 152. –– Режим
доступа: http://mpei.ru/diss/Lists/FilesDissertations/170-%D0%94%D0%B8%D1%
81%D1%81%D0%B5%D1%80%D1%82%D0%B0%D1%86%D0%B8%D1%8F.pdf.
23. Arning Andreas, Agrawal Rakesh, Raghavan Prabhakar. A Linear Method for
Deviation Detection in Large Databases // KDD. –– Т. 1141. –– 1996. –– С. 972–981.
24. Ярушкина Н. Г., Афанасьева Т. В., Перфильева И. Г. Интеллектуальный
анализ временных рядов : Дисс… кандидата наук / Н. Г. Ярушкина,
Т. В. Афанасьева, И. Г. Перфильева ; УГТУ. –– 2010. –– С. 315. –– Режим доступа:
http://venec.ulstu.ru/lib/disk/2010/Yaruwkina.pdf.
25. Marnerides A.K., Pezaros D.P., Hutchison D. Internet traffic characterisation:
Third-order statistics &amp; higher-order spectra for precise traffic modelling //
Computer Networks. –– 2018. –– 4. –– Т. 134. –– С. 183–201. –– Режим доступа: https:
//www.sciencedirect.com/science/article/pii/S1389128618300677.
26. Unsupervised real-time anomaly detection for streaming data / Subutai Ahmad,
Alexander Lavin, Scott Purdy, Zuha Agha // Neurocomputing. –– 2017. –– 11. –– Т.
262. –– С. 134–147. –– Режим доступа: https://www.sciencedirect.com/science/article/
pii/S0925231217309864.
27. Вагин В. Н., Фомина М. В., Антипов С. Г. Моделирование алгоритмов
индуктивного формирования понятий в «зашумленных» базах данных // Научнотехническая информация. Серия 2: Информационные процессы и системы. ––
2013. –– № 7. –– С. 20–32.
28. Сглаживание цифровых сигналов [Электронный ресурс]. –– Режим
доступа: https://habr.com/post/184728/ (дата обращения: 19.04.2018).
29. Wikipedia. Median Filter [Электронный ресурс]. –– Режим доступа: https://
en.wikipedia.org/wiki/Median_filter (дата обращения: 06.06.2018).
30. Wikipedia. Moving Average [Электронный ресурс]. –– Режим доступа: https:
//en.wikipedia.org/wiki/Moving_average (дата обращения: 11.05.2018).
31. Janardan, Mehta Shikha. Concept drift in Streaming Data Classification:
Algorithms, Platforms and Issues // Procedia Computer Science. –– 2017. –– 1. –– Т.
122. –– С. 804–811. –– Режим доступа: https://www.sciencedirect.com/science/article/
66
pii/S1877050917326881.
32. Индикатор Alligator (Аллигатор) [Электронный ресурс]. –– Режим доступа:
http://enc.fxeuroclub.com/409/ (дата обращения: 19.04.2018).
33. Средний истинный диапазон, ATR [Электронный ресурс]. –– Режим
доступа: http://berg.com.ua/indicators-overlays/atr/ (дата обращения: 19.04.2018).
34. Jain Anil K. Data clustering: 50 years beyond K-means // Pattern Recognition
Letters. –– 2010. –– 6. –– Т. 31, № 8. –– С. 651–666. –– Режим доступа: https://www.
sciencedirect.com/science/article/pii/S0167865509002323.
35. Hu Ming-Kuei. Visual pattern recognition by moment invariants // IRE
transactions on information theory. –– 1962. –– Т. 8, № 2. –– С. 179–187.
36. UML—диаграмма вариантов использования (use case diagram)
[Электронный ресурс]. –– Режим доступа: https://habr.com/post/47940/ (дата
обращения: 26.05.2018).
37. Элементы графической нотации диаграммы компонентов [Электронный
ресурс]. –– Режим доступа: https://www.intuit.ru/studies/courses/32/32/lecture/1022
(дата обращения: 26.05.2018).
38. Dwyer Gareth. Flask vs. Django: Why Flask Might Be Better
[Электронный ресурс] . –– Режим доступа: https://www.codementor.io/garethdwyer/
flask-vs-django-why-flask-might-be-better-4xs7mdf8v (дата обращения: 19.04.2018).
39. Brown Ryan. Django vs Flask vs Pyramid: Choosing a Python Web Framework
[Электронный ресурс]. –– Режим доступа: https://www.airpair.com/python/posts/
django-flask-pyramid (дата обращения: 19.04.2018).
40. Драч В. Н. Сравнение современных СУБД [Электронный ресурс]. ––
Режим
доступа:
http://drach.pro/blog/hi-tech/item/145-db-comparison
(дата
обращения: 19.04.2018).
67
ПРИЛОЖЕНИЕ А
Исходный код программы
[ main . py ]
import c o n f i g p a r s e r
from m o d u l e s . g e t _ r i c _ d a t a import R i c D a t a
from m o d u l e s . p r o c e s s _ d a t a import s o r t a s s o r t i n g _ o f _ t i m e
from m o d u l e s . p r o c e s s _ d a t a import w m a _ f i l t e r , e w m a _ f i l t e r ,
ema_filter , normalise_sampling ,
get_avg_sampling_interval
from numpy import a v e r a g e
import m a t p l o t l i b . p y p l o t a s p l o t
i f __name__ == ’ __main__ ’ :
# Init config
config = configparser . ConfigParser ()
config . sections ()
config . read ( ’ config . i n i ’ )
# Get c o n f i g d a t a
object_id = config [ ’ Rightech ’ ] [ ’ ObjectId ’ ]
r e q u e s t _ f i e l d s = config [ ’ Rightech ’ ] [ ’ Fields ’ ]
b a s e _ u r l = c onf ig [ ’ Rightech ’ ] [ ’ BaseUrl ’ ]
t o k e n = c o n f i g [ ’ R i g h t e c h ’ ] [ ’ Token ’ ]
v a l u e _ f i e l d = config [ ’ Rightech ’ ] [ ’ ValueField ’ ]
p a c k e t s _ l i m i t = c o n f i g [ ’DEFAULT ’ ] [ ’ L i m i t ’ ]
p a c k e t s _ o f f s e t = c o n f i g [ ’DEFAULT ’ ] [ ’ O f f s e t ’ ]
p a g e _ s i z e = c o n f i g [ ’DEFAULT ’ ] [ ’ P a g e S i z e ’ ]
median_filter_divider = config [ ’ MedianFilter ’ ][ ’
MedianFilterDivider ’ ]
window = c o n f i g [ ’ M e d i a n F i l t e r ’ ] [ ’ Window ’ ]
# Get d a t a f r o m RiC
r i c = RicData ( base_url , token )
68
data = ric . get_data ( object_id ,
scope= p a c k e t s _ l i m i t ,
page_size=page_size ,
offset=packets_offset ,
fields=request_fields )
# Prepare data
data = sorting_of_time ( data )
# Get s a m p l i n g i n t e r v a l
avg_sampling_interval = get_avg_sampling_interval (
d a t a , window , m e d i a n _ f i l t e r _ d i v i d e r )
a v g _ s a m p l i n g _ i n t e r v a l = round ( a v g _ s a m p l i n g _ i n t e r v a l ,
2)
p r i n t ( ’ \ n A v e r a g e s a m p l i n g i n t e r v a l −> \ t \ t { s a m p l i n g }
’ . format ( s a m p l i n g = a v g _ s a m p l i n g _ i n t e r v a l ) )
p l o t . f i g u r e ( ’ B e n c h m a r k i n g f i l t e r s f o r f i e l d ”{{ f i e l d
}}” ’ . format ( f i e l d = v a l u e _ f i e l d ) )
# Plot source data
source_data = []
source_time = []
for i in data :
s o u r c e _ d a t a . append ( i [ v a l u e _ f i e l d ] )
s o u r c e _ t i m e . a p p e n d ( round ( i [ ’ t i m e ’ ] − d a t a [ 0 ] [ ’
time ’ ] ) / avg_sampling_interval )
p l o t . p l o t ( source_time , source_data , l a b e l = ’ Source
data ’ , linewidth =3.0 , alpha =0.4)
# Plot normalised data
normalised_data = normalise_sampling ( data ,
avg_sampling_interval , value_field=value_field )
p l o t . p l o t ( normalised_data , l a b e l = ’ Normalised sampling
data ’ , linewidth =2.0 , alpha =0.6)
# Plot average value l i n e
average_value = [ average ( normalised_data ) ]* len (
normalised_data )
69
p l o t . p l o t ( a v e r a g e _ v a l u e , l a b e l = ’ Average v a l u e ’ ,
linewidth =4.0 , alpha =0.7)
# Plot f i l t e r e d result
f i l t e r e d _ d a t a _ w m a = w m a _ f i l t e r ( normalised_data , 1000)
p l o t . p l o t ( f i l t e r e d _ d a t a _ w m a , l a b e l = ’WMA f i l t e r e d d a t a
’)
filtered_data_ewma = ewma_filter ( normalised_data ,
0.02)
p l o t . p l o t ( f i l t e r e d _ d a t a _ e w m a , l a b e l = ’EWMA f i l t e r e d
data ’ )
f i l t e r e d _ d a t a _ e m a = e m a _ f i l t e r ( normalised_data , 5)
p l o t . p l o t ( f i l t e r e d _ d a t a _ e m a , l a b e l = ’EMA f i l t e r e d d a t a
’)
plot . legend ( loc= ’ best ’ )
p l o t . show ( )
[ p r o c e s s _ d a t a . py ]
# Prepare data
from numpy import a v e r a g e
from tqdm import tqdm
import math
import numpy a s np
COLS_NUMBER = 100
d e f w m a _ f i l t e r ( d a t a , window =1 0 ) :
d a t a _ n p = np . a s a r r a y ( d a t a )
w e i g h t = [ i f o r i i n range ( window , 0 , −1) ]
d = 2 . 0 / ( window * ( window + 1 ) )
result = []
r a n g e _ a r r a y = range ( window , d a t a _ n p . s h a p e [ 0 ] )
p r i n t ( ’ \ n−> WMA f i l t e r i n g d a t a \ n ’ )
p r o g r e s s _ b a r = tqdm ( t o t a l = l e n ( r a n g e _ a r r a y ) , n c o l s =
COLS_NUMBER)
for i in range_array :
70
r e s u l t . a p p e n d ( np . sum ( d a t a _ n p [ i − window : i ] *
weight ) * d )
progress_bar . update (1)
progress_bar . close ()
r e t u r n np . a r r a y ( r e s u l t )
d e f e m a _ f i l t e r ( y , p = 5 0) :
y = np . a s a r r a y ( y )
r = [ y [0] ]
r a n g e _ a r r a y = range ( 1 , y . s h a p e [ 0 ] )
p r i n t ( ’ \ n−> EMA f i l t e r i n g d a t a \ n ’ )
p r o g r e s s _ b a r = tqdm ( t o t a l = l e n ( r a n g e _ a r r a y ) , n c o l s =
COLS_NUMBER)
for i in range_array :
r . a p p e n d ( r [ −1] + 2 . 0 / ( p +1 ) * ( y [ i ] − r [ − 1 ] ) )
progress_bar . update (1)
progress_bar . close ()
r e t u r n np . a r r a y ( r )
def ewma_filter ( y , p =0.15) :
y = np . a s a r r a y ( y )
r = [ y [0] ]
r a n g e _ a r r a y = range ( 1 , y . s h a p e [ 0 ] )
p r i n t ( ’ \ n−> EWMA f i l t e r i n g d a t a \ n ’ )
p r o g r e s s _ b a r = tqdm ( t o t a l = l e n ( r a n g e _ a r r a y ) , n c o l s =
COLS_NUMBER)
for i in range_array :
r . a p p e n d ( p*y [ i ] + (1−p ) * r [ −1] )
progress_bar . update (1)
progress_bar . close ()
r e t u r n np . a r r a y ( r )
def s o r t ( data ) :
d a t a . s o r t ( key =lambda i t e m : i t e m [ ” t i m e ” ] )
71
return data
d e f median_window ( d a t a , window =100 , d i v i d e r = 2) :
data . sort ()
r e t u r n d a t a [ i n t ( round ( i n t ( window ) / i n t ( d i v i d e r ) ) ) ]
d e f m e d i a n _ f i l t e r ( d a t a , window =100 , d i v i d e r = 2 ) :
result = []
l a s t _ i n d e x = len ( data )
window = i n t ( window )
w i n d o w _ c o r r e c t e d = window
p r i n t ( ’ \ n−> Median f i l t e r i n g d a t a \ n ’ )
p r o g r e s s _ b a r = tqdm ( t o t a l = l a s t _ i n d e x , n c o l s =
COLS_NUMBER)
f o r i i n range ( 0 , l a s t _ i n d e x ) :
window_corrected = window_corrected i f l a s t _ i n d e x
− i > window_corrected e l s e l a s t _ i n d e x − i
c o r r e c t i o n _ s i z e = window − w i n d o w _ c o r r e c t e d
subset = data [ i : i + window_corrected ] + data [ 0 :
correction_size ]
r e s u l t . a p p e n d ( median_window ( s u b s e t ,
window_corrected , d i v i d e r ) )
progress_bar . update (1)
progress_bar . close ()
return r e s u l t
def g e t _ d i f f _ t i m e _ a r r a y ( data ) :
i = 1
diff_time_array = []
while i < len ( data ) :
prev = int ( data [ i − 1][ ’ time ’ ] )
cur = int ( data [ i ] [ ’ time ’ ] )
d i f f _ t i m e _ a r r a y . append ( ( cur − prev ) )
i += 1
return d i f f _ t i m e _ a r r a y
72
d e f g e t _ a v g _ s a m p l i n g _ i n t e r v a l ( d a t a , window =100 , d i v i d e r
=2) :
diff_time_array = get_diff_time_array ( data )
filtered_diff_time_array = median_filter (
d i f f _ t i m e _ a r r a y , window , d i v i d e r )
return average ( f i l t e r e d _ d i f f _ t i m e _ a r r a y )
def g e t _ s p l i n e _ a p p r o x i m a t i o n _ v a l u e ( point1 , point2 , time ) :
i f p o i n t 1 [ 0 ] > t i m e or p o i n t 2 [ 0 ] < t i m e :
r e t u r n None
k = ( point1 [1] − point2 [1]) / ( point1 [0] − point2 [0])
b = point1 [1] − k * point1 [0]
r e t u r n k* t i m e + b
d e f n o r m a l i s e _ s a m p l i n g ( d a t a , s a m p l i n g _ i n t e r v a l =1000 ,
v a l u e _ f i e l d = ’ speed ’ ) :
min_time = d a t a [ 0 ] [ ’ time ’ ]
max_time = d a t a [ l e n ( d a t a ) −1][ ’ t i m e ’ ]
d i f _ t i m e = max_time − m i n _ t i m e
count_of_points = int ( dif_time / sampling_interval ) +
1
p r i n t ( ’ M e t r i c s : \ n \ tMin t i m e −>\ t { m i n _ t i m e } \ n \ tMax
t i m e −>\ t { max_time } \ n \ t D i f −>\ t \ t { d i f } \ n ’ . format (
m i n _ t i m e = min_time ,
max_time =max_time ,
dif=dif_time ) )
p r i n t ( ’ Count o f p o i n t o f n o r m a l i s e d d a t a −> \ t {
c o u n t _ o f _ p o i n t s } ’ . format ( c o u n t _ o f _ p o i n t s =
count_of_points ) )
result = []
data_iterator = 0
new_point_index_iterator = 0
time_of_new_point = 0
point1 = [0 , 0]
point2 = [0 , 0]
p r i n t ( ’ \ n−> N o r m a l i s i n g s a m p l i n g \ n ’ )
73
p r o g r e s s _ b a r = tqdm ( t o t a l = c o u n t _ o f _ p o i n t s , n c o l s =
COLS_NUMBER)
while d a t a _ i t e r a t o r < len ( data ) − 1:
point1 [0] = data [ d a t a _ i t e r a t o r ] [ ’ time ’ ] −
min_time
point1 [1] = data [ d a t a _ i t e r a t o r ][ value_field
point2 [0] = data [ d a t a _ i t e r a t o r + 1][ ’ time ’ ] −
min_time
point2 [1] = data [ d a t a _ i t e r a t o r + 1][ value_field ]
new_point_value = get_spline_approximation_value (
point1 , point2 , time_of_new_point )
i f n o t n e w _ p o i n t _ v a l u e i s None :
r e s u l t . append ( n e w _ p o i n t _ v a l u e )
t i m e _ o f _ n e w _ p o i n t = math . f l o o r (
new_point_index_iterator *
sampling_interval )
progress_bar . update (1)
n e w _ p o i n t _ i n d e x _ i t e r a t o r += 1
w h i l e ( d a t a _ i t e r a t o r < l e n ( d a t a ) − 1 ) and ( i n t (
d a t a [ d a t a _ i t e r a t o r + 1 ] [ ’ time ’ ] − min_time ) <
time_of_new_point ) :
d a t a _ i t e r a t o r += 1
progress_bar . close ()
return r e s u l t [ 1 : ]
75
ИНФОРМАЦИОННО-ПОИСКОВАЯ ХАРАКТЕРИСТИКА
ДОКУМЕНТА НА ЭЛЕКТРОННОМ НОСИТЕЛЕ
Наименование
группы атрибутов
атрибута
Характеристики документа
на электронном носителе
1. Описание
документа
Обозначение документа
Презентация.pdf
(идентификатор(ы)
файла(ов))
Наименование документа Демонстрационные
плакаты к выпускной
квалификационной работе
Класс документа
ЕСКД
Вид документа
Оригинал документа
на электронном носителе
Аннотация
Демонстрационный
материал, отображающий
основные этапы
выполнения выпускной
квалификационной работы
Использование
Windows, Linux, PDF
документа
2. Даты и время
Дата и время
копирования документа
Дата создания документа
Дата утверждения
документа
28.06.2018 12:13
3. Создатели
Автор
Создатель
А. А. Арбузов
А. А. Арбузов
4. Внешние
ссылки
Ссылки на другие
документы
Удостоверяющий лист
№165134
5. Защита
Санкционирование
Классификация защиты
ОГУ имени И. С. Тургенева
По законодательству РФ
6. Характеристики Объем информации
содержания
документа
13.06.2018
19.06.2018
466 944 Б
76
7. Структура
документа(ов)
Наименование плаката
(слайда) №1
Наименование плаката
(слайда) №2
Наименование плаката
(слайда) №3
Наименование плаката
(слайда) №4
Наименование плаката
(слайда) №5
Наименование плаката
(слайда) №6
Наименование плаката
(слайда) №7
Титульный лист
Цель и задачи
Диаграмма вариантов
использования
Диаграмма компонентов
Алгоритм поиска
Методы пресказания тренда
Результаты вычисления
сигнатуры
1/--страниц
Пожаловаться на содержимое документа