ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Институт математики и компьютерных наук Кафедра информационной безопасностиДопустить к защите в ГАКЗаведующий кафедройинформационной безопасности,д.т.н., профессор А.А. Захаров “____” _________ 2010 г.Присяжнюк Александр Сергеевич Создание адаптивного алгоритма выявления аномального поведения трафика сети на основании характерных изменений оценок параметров альтернирующего потока (выпускная квалификационная работа)Научный руководитель: к.ф.- м.н., доцент кафедры информационной безопасности __________ Ниссенбаум О. В. Автор работы: __________ Присяжнюк А.С. Тюмень 2010 Введение. 3Глава 1. 6Актуальные математические модели трафика компьютерной сети 6 1.1. Состояние проблемы. 6 1.2. Общее описание моделей ДС потоков. 8 1.3. Модель асинхронного альтернирующего потока событий. 11Глава 2. 14Построение алгоритма 14 2.1. Основная идея алгоритма. 14 2.2. Статистика сетевой активности 16 2.2.1 Сбор статистики. 17 2.2.2. Приложение для сбора и анализа статистики. 18 2.3. Получение оценок параметров. 21 2.4. Сглаживание оценок. 21 2.4.1. Подходы к сглаживанию данных. 23 2.4.2. Вейвлет-анализ и его применение. 23 2.4.3. Сглаживание экспериментальных данных. 27 2.5 Стратификация данных. 30 Одним из наиболее простых и эффективных статистических методов анализа данных является метод стратификации (очень широко используется в социологии). В соответствии с этим методом производят стратификацию статистических данных, то есть группируют данные в зависимости от условий их получения и производят обработку каждой группы данных в отдельности. Данные, разделенные на группы в соответствии с их особенностями, называют стратами (классами), а сам процесс разделения на страты – стратификацией. 30 2.6 Нейронные сети. 30 2.7 Перспективы дальнейших исследований. 32Заключение. 33Список литературы. 34Приложение. Исходные коды. 36 Введение. С тех пор, как распространение компьютеров приобрело массовый характер, они стали настолько неотъемлемой частью жизни человека, что сегодня совершенно невозможно представить существование без них. Компьютерные системы и сети стали неотъемлемым атрибутом комфорта жизни человека, таким как электричество и водоснабжение. Поэтому, несмотря на то, что существует множество программных и аппаратных комплексов обеспечения безопасности компьютерных систем, на сегодняшний день, эта проблема является достаточно актуальной. Почти все современные средства обеспечения безопасности, работают по сигнатурному принципу, то есть когда модель поведения угрозы известна заранее. Но существует и другой принцип – статистический, при котором предварительно собираются статистические параметры активности пользователя в сети. Затем, на основании этих оценок выявляется аномальная активность. Для получения этих параметров необходимо построить математическую модель сетевого трафика. Еще в начале ХХ века датский ученный А. К. Эрланг, установил, что процессы, происходящие в телефонных сетях, а конкретно, в потоке входящих звонков, имеют вероятностный характер [1]. Методы, примененные Эрлангом – теория вероятностей и математическая статистика, математическое моделирование, теория случайных процессов – до сих пор являются основным инструментарием теории массового обслуживания (ТМО). Позже выяснилось, что теория массового обслуживания применима не только к процессам обработки телефонного трафика, но и ко многим другим областям науки и техники, в частности, модель сетевого взаимодействия в компьютерных системах может успешно быть описана с помощью ТМО [2]. В основном, в работах по системам массового обслуживания, делается упор на нахождение различных стационарных характеристик системы обслуживания в условиях известных параметров входящих потоков и обслуживающих приборов. В реальности они могут быть известны лишь частично или неизвестны совсем. Обычно, такие входящие потоки событий имеют переменную интенсивность, и изменение интенсивности, как правило, стохастическое. Такие потоки называются дважды стохастическими. Так как в них наблюдаются два случайных процесса: во-первых, поступление событий в потоке происходит в случайные моменты времени; во-вторых, изменение интенсивности потока имеет случайный характер. Сама интенсивность может изменяться непрерывно или дискретно. Среди ДС потоков с дискретной интенсивностью выделяют потоки с двумя состояниями, в одном из которых имеет место нулевая интенсивность (т.е. в одном из состояний события отсутствуют). Такие потоки называют альтернирующими. Такие потоки, подходят для описания сетевой активности пользователей в компьютерных сетях. Модель альтернирующего потока событий является простейшей среди дважды стохастических потоков и в то же время должна более точно отражать реальную ситуацию чем пуассоновская (простейшая модель потока с постоянной интенсивностью).^ Актуальность проблемы. На сегодняшний день существует множество программных и аппаратных комплексов обеспечения безопасности компьютерных систем. Существует два основных метода выявления информационных угроз – сигнатурный и статистический. Почти все современные средства обеспечения безопасности, работают по сигнатурному принципу, то есть когда модель поведения угрозы известна заранее. Статистический же принцип используется крайне редко, в том числе по причине того, что использующиеся модели случайных потоков, такие как пуассоновский, слабо соответствуют реальному трафику сети. В тоже время, последние 30 лет ведутся активные исследования моделей потоков с переменной интенсивностью, которые более точно соответствуют реальному трафику компьютерной сети. В свете сказанного, представляется актуальным исследование вопросов обнаружения угроз в сети в рамках статистического метода, на основании актуальных моделей сетевого трафика. ^ Цель работы. Целью моей работы является создание адаптивного алгоритма выявления аномального поведения трафика в компьютерной сети на основе статистических данных с использование модели альтернирующего потока.^ Постановка задачи. Задачи, поставленные и решённые в рамках данной работы: Изучение существующих моделей дважды стохастических потоков, в частности, альтернирующего потока. Разработка общей идеи алгоритма. Сбор статистики сетевой активности пользователей локальной сети. Применение модели альтернирующего потока к собранной статистике, оценка параметров потока. Анализ динамики полученных параметров альтернирующего потока. Исследование возможных методов выявления аномальной активности в сети.^ Глава 1. Актуальные математические модели трафика компьютерной сети 1.1. Состояние проблемы. Развитие теории массового обслуживания, с помощью которой, возможно успешно описать модель сетевого трафика, насчитывает очень длительный период времени. Первые работы в этой области были опубликованы датским ученым А.К. Эрлангом в 1908-1922 годах [1]. Эти работы уже тогда определили основную область применения новой теории - обслуживание телетрафика. Весомый вклад в развитие ТМО внесли такие ученые как В. Феллер, Д. Кенделл, А.Я. Хинчин и др. [3, 4]. В частности, один из основных методов теории - метод вложенных цепей Маркова - был разработан А.Я. Хинчиным [5] в начале 30-х гг. Входящие потоки событий в системах массового обслуживания (СМО), рассмотренных в тот период времени, аппроксимировались одной из трех моделей: регулярный поток (системы с таким потоком относятся к детерминированным и рассматриваются в теории оптимизации как системы конвейерного типа), простейший (пуассоновский) поток и эрланговский (поток, полученный из пуассоновского путем разрежения) поток событий. При этом особое внимание уделяется системам с простейшим входящим потоком, тем более что СМО с входящим потоком Эрланга можно моделировать системой с входящим пуассоновским потоком. В шестидесятые годы появились первые работы в области так называемых управляемых СМО [6, 7]. Исключительная актуальность оптимизационных задач, приведших к возникновению таких систем, объясняет дальнейшее бурное развитие этой тематики. Широта области применения управляемых систем и разнообразие задач, которые оказалось возможным решить с их помощью, повлекли более тщательную разработку этого направления. Ставились и решались все более частные задачи. Несмотря на довольно широкую область применения ТМО, главными областями использования теории являются автоматизированные системы управления (АСУ) и сети связи, в том числе компьютерные сети. Наиболее сложные модели систем массового обслуживания создаются и исследуются именно для этих двух областей. До середины 80-х годов относительная простота систем связи, изолированность разных видов связи друг от друга, низкая пропускная способность каналов, их дороговизна и, следовательно, высокая их загруженность приводили к тому, что для входящих потоков заявок использовались все те же относительно простые модели, что и во времена К.А. Эрланга - простейший поток. Реже - регулярный и эрланговский потоки. Усложнение структуры информационных систем, интеграция различных систем связи, разнообразие программного и аппаратного обеспечения, протоколов передачи информации приводят к тому, что теория, существовавшая до 80-х годов, во многом становится непригодной для анализа случайных процессов, существующих в современных сетях связи. В то же время, ТМО предлагает надежные, хорошо изученные общие математические методы теории вероятностей для детального анализа таких систем. 1.2. Общее описание моделей ДС потоков. Модель пуассоновского потока соответствует реальному трафику компьютерной сети только на сравнительно небольших отрезках времени, так как интенсивность трафика, как правило, меняется со временем. Вообще, загрузка сетей связи зависит от многих факторов. Она может изменяться как циклически в течение суток (недели, года), так и в зависимости от того, какие компьютерные приложения в данный момент используют сеть. С одной стороны, локальная сеть организации загружена больше днем, чем ночью, с другой стороны сеть используется по-разному различными пользователями. В частности, можно различить сетевую активность делопроизводителя, который работает с электронными документами и пользуется сетью только для их отправки и получения данных, и системного администратора, на чей компьютер постоянно поступают данные о состоянии компьютеров и сетевых устройств офиса. Трафик первого пользователя представляет собой чередование долгих периодов "молчания" и кратковременных периодов, когда пакеты информации следуют один за другим. Трафик второго пользователя более равномерен. Однако, и в том и в другом случае имеется дело с потоками переменной интенсивности, причем изменения интенсивности таких потоков, как правило, носят стохастический характер. Такие потоки принято называть дважды стохастическими. Такая случайная зависимость интенсивности входящих потоков от времени на практике встречается чаще, чем постоянная интенсивность, поэтому модели дважды стохастических потоков представляют определенный интерес с точки зрения практических приложений. Интенсивность дважды стохастического потока является случайным процессом. В зависимости от характера этого процесса выделяют два больших класса таких потоков: 1) потоки, интенсивность которых является непрерывным (диффузионным) процессом; 2) потоки, интенсивность которых является кусочно-постоянным процессом. Рис.1. Изменение интенсивности дважды стохастического потока событий а) с непрерывно изменяемой интенсивностью; б) с кусочно-постоянной интенсивностью. Потоки, интенсивность которых есть кусочно-постоянный процесс, в свою очередь, подразделяются на потоки с конечным числом состояний (с конечным числом значений, которое может принять процесс) и потоки со счетным числом состояний. Смена состояний происходит в случайные моменты времени, а на интервалах постоянства интенсивности поток ведет себя как простейший. Такие потоки наиболее пригодны для описания реальных потоков в сетях связи и цифровых сетях интегрального обслуживания. А также выделяют потоки с двумя состояниями, одно из которых соответствует нулевой интенсивности. Такие потоки называют альтернирующими. Проводя наиболее общую классификацию альтернирующих потоков, выделяют следующие основные типы потоков: 1) асинхронные потоки событий, то есть потоки, изменение интенсивности которых происходит в случайные моменты времени, не связанные с моментами наступления событий; 2) полусинхронные потоки событий, то есть потоки, у которых переход из второго состояния в первое происходит в моменты наступления событий, а из первого во второе - независимо от моментов наступления событий. Альтернирующие потоки, асинхронные и полусинхронные, могут являться моделями потоков, поступающих в общую сеть с одного источника. Например, источник может отправлять информацию на обслуживающий прибор порциями по мере ее накопления, что сформирует полусинхронный поток с двумя состояниями от источника (либо информация пересылается с максимальной интенсивностью, либо не пересылается вовсе, начало и конец окон передачи информации совпадают с моментами пересылки первого и последнего пакетов в "порции"). Если же интервалы времени, когда источник может проводить передачу, определяет обслуживающее или иное устройство, исходя из загруженности сети или сервера, то имеем асинхронный поток с двумя состояниями. В цифровых сетях, в частности, в компьютерных сетях, такими моделями может быть аппроксимирован трафик, исходящий от определенного порта компьютера (браузерный Интернет-трафик, трафик почтового сервиса, файловый трафик и т.п.). Для таких моделей были решены задачи оценивания состояний и параметров [8, 9, 10, 11]. Следует отметить, что характеристики потока, исходящего от одного источника, являются важными в свете некоторых практических задач. Например, поток исходящих информационных пакетов по какому-либо виду трафика в компьютерной сети характеризуется набором параметров потока, а значит, оценив эти параметры, можно составить определенный "портрет" источника, который, в свою очередь, может быть использован при анализе безопасности трафика на предмет выявления аномальной активности (вызванной, например, деятельностью сетевого вируса). В то же время, не только в научной, но и в учебной и популярной литературе по информационным сетям всё чаще упоминаются вопросы разработки теоретических положений и необходимость научно обоснованных технических решений, обеспечивающих эффективность и повышение качества администрирования информационных сетей на основе исследования циркулирующих в них потоков. На данный момент проведено достаточно большое количество исследований дважды стохастических потоков событий с точки зрения задач определения характеристик СМО, оценивания параметров и состояний потока. Также часто в литературе решается задача оптимального оценивания состояний дважды стохастического потока событий [8, 9, 10]. Таким образом, развитие телекоммуникационных сетей, информационных технологий, интегрирование различных видов связи, вычислительных систем и сетей породило множество задач по моделированию и анализу обслуживания информационных потоков, циркулирующих в сетях. В частности, такие информационные потоки достаточно адекватно описываются моделями дважды стохастических потоков событий [12, 13]. ^ 1.3. Модель асинхронного альтернирующего потока событий. Для оценки параметров рассматривался трафик в реальной компьютерной сети. Каждый пакет данных рассматривался как событие потока. Материалом для оценки служили интервалы между соседними пакетами. Модель альтернирующего потока событий, является простейшей среди дважды стохастических потоков и в то же время должна более точно отражать реальную ситуацию, чем пуассоновская. Тем более уже были успешные попытки применения модели альтернирующего потока к компьютерным сетям [14]. Опишем более подробно данную модель. Рассматривается асинхронный альтернирующий поток событий, интенсивность которого есть кусочно-постоянный стационарный случайный процесс λ(t) с двумя состояниями λ1 = λ и λ2 = 0. В течении временного интервала, когда процесс λ(t) находится в первом состоянии, поток событий представляет собой пуассоновский поток с интенсивностью λ. Во втором состоянии процесса, поток событий отсутствует. Моменты перехода процесса из состояния в состояние не связаны с моментами наступления событий в пуассоновском потоке, поэтому, во-первых поток называется асинхронным потоком событий и, во-вторых, так как λ2 = 0 – альтернирующим. Длительность нахождения процесса в i-ом состоянии является случайной величиной, распределённой по закону с параметром , i=1,2. Стохастический граф переходов такого случайного процесса λ(t) представлен на рисунке 2. Рис. 2. Граф переходов случайного процесса λ(t). Этот граф имеет две вершины. Вершина 1 соответствует первому состоянию, вершина 2 – второму состоянию процесса. Каждая дуга имеет вес, равный интенсивности перехода из одного состояния в другое. Петли в вершинах опущены. Рис.3. Альтернирующий поток. Плотность распределения интервала между соседними событиями в альтернирующем потоке есть, (1) где ; . Оценки параметров λ, α1 , α2 по наблюдениям за потоком методом моментов могут быть получены по следующим формулам:; ; , (2) Где , ,, . В (2) константы , , суть первые 3 начальных момента . Результаты статистического эксперимента показывают достаточно хорошее качество оценок (2). Кроме того, эти оценки, очевидно, эффективно вычислимы, поэтому оценивание параметров асинхронного потока может осуществляться в режиме реального времени. ^ Глава 2. Построение алгоритма 2.1. Основная идея алгоритма. Суть алгоритма заключается в том чтобы, предварительно накопить данные о поведении пользователя в сети, а затем, отталкиваясь от этих данных, выявлять несвойственную пользователю активность. Для того чтобы алгоритм функционировал корректно, необходимо, производить накопление статистики в режиме работы, который, точно является нормальным, как технически (пропускная способность сети), так и по поведению пользователя (различные виды деятельности в сети). Если невозможно утверждать, когда активность пользователя является нормальной, то и невозможно гарантировать адекватную работу алгоритма. В работе алгоритма можно выделить 2 режима: 1. В первом режиме происходит накопление статистических данных о трафике пользователя. Эти данные в последующем будут своеобразным “портретом” пользователя в сети. 2. Во втором режиме происходит непосредственно анализ текущей деятельности пользователя, ее сравнение с ранее собранными данными и оценка на основании уже собранной статистики. Сравнивая накопленные данные о модели поведения пользователя в сети с его текущей активностью, представляется возможным выявить несвойственные ему отклонения. В соответствии с моделью альтернирующего потока, трафик на конечном временном интервале характеризуется значениями трех параметров: λ, α1, α2. Эту тройку можно представить, как точку в трехмерном пространстве (рис. 4). На смежном интервале времени если характер трафика не изменился существенно, то значения λ, α1, α2 также не должны существенно измениться, и тогда имеет место точка достаточно близкая к предыдущей (рис. 4). Если же в следующий момент времени характер трафика резко изменится (например, пользователь включит закачку, после простого перехода по веб-ресурсам), то следующая точка будет значительно удалена от предыдущей. Рис. 4 Проведя наблюдения достаточно долго, получим несколько областей, в которых группируются точки (рис. 5). Если полагать, что весь период наблюдения трафик функционировал в нормальном режиме, то такие группы точек представляют собой эталон нормального поведения трафика для данного пользователя. Если же в некоторый момент начнут наблюдаться оценки, группирующиеся в области, достаточно удаленно от ранее полученных областей, то это может служить сигналом об аномальной активности. Рис. 5 Также анализ динамики полученных оценок может дать информацию о резком изменении характера сетевой активности. И при предварительном сборе данных можно будет выделить несколько периодов, каждый из которых будет соответствовать определенному характеру сетевой активности. На основании этих периодов и зависимости оценок на них, можно будет говорить о выявлении аномальности характера сетевой активности. В свою очередь резкое изменение одной, двух или всех трех оценок может говорить об изменении характера сетевой активности, то есть о переходе потока в др. режим работы. Адаптивный алгоритм может переходить в режим отслеживания аномальной активности, только в момент резкого изменения оценок параметров, а в другое время находится в режиме накопления статистики, что улучшит его быстродействие и позволит применять его в режиме реального времени.^ 2.2. Статистика сетевой активности Для работы над построением алгоритма, который можно было бы использовать для достижения нужного результата, в первую очередь, нужны были данные обычной сетевой активности пользователей. Для решения данной задачи было написано программное обеспечение, которое позволило собрать нужные данные и продолжить работу по разработке алгоритма.^ 2.2.1 Сбор статистики. Статистика собиралась с компьютеров различных пользователей. Причем снимались данные о работе определенного типа: просто посещение веб-ресурсов, скачивание торрентов, онлайн-игра и т. д. Каждая отдельная выборка производилась по одному часу работы. Моменты поступления пакетов на сетевую карту принимались в качестве событий потока. По полученным данным в соответствии с формулами (2) были получены оценки параметров потока с шагом в 10 сек. Графики динамики оценки приведены на рисунках 6 и 7.Рис. 6. Динамика оценки параметра λ при различных типах сетевой активности Рис. 7. Динамика оценки параметров α1, α2 при различных типах сетевой активности^ 2.2.2. Приложение для сбора и анализа статистики. Для реализации приложения был выбран язык программирования C#, так он довольно прост и предоставляет массу возможностей. В ходе разработки было написано 2 приложения – одно для сбора статистики, другое для анализа накопленных данных. При разработке приложения главной задачей являлся сбор статистики сетевой активности конкретного сетевого адаптера компьютера, на котором будет использоваться программа. Это легко достигается при использовании драйвера перехвата трафика WinPCap (www.winpcap.org). Приложение “отлавливает” только ip-пакеты, обрабатываемые конкретным сетевым адаптером, и записывает данные о них в лог. Так как о каждом пакете записываются подробные сведения, то потом довольно легко отфильтровать их по нужному критерию, например по ip-адресу отправителя и получить нужные сведения для статистики, такие как временные интервалы между пакетами. Так как приложение разрабатывалось на платформе .net, то также использовался, набор классов SharpPCap (http://sourceforge.net/projects/sharppcap/), предоставляющий возможности библиотеки WinPCap для языка C#.На главной вкладке приложения можно выбрать сетевой адаптер, с которого будет идти сбор статистики и папку, куда будет сохраняться статистика. Подробные сведения о перехваченных пакетах выводятся во вкладке “Мониторинг”. А во вкладке “Расписание”, можно задавать временные интервалы, когда будет проводиться сбор статистики. Программно перехват трафика выполняется очень просто, благодаря WinPCap и SharpPCap. Изначально получается список сетевых адаптеров на компьютере - Pcap.GetAllDevices(). Затем у выбраннного адаптера вызывается метод Open(), а далее запускается бесконечный цикл в выделенном потоке где, у этого же адаптера, вызывается метод GetNextPacket(). Сохранение данных происходит с периодичностью, выбранной в приложении для сбора данных. Периодичность может быть выбрана в размере трёх, четырех или пяти минут. Этого промежутка времени хватает, чтобы собрать необходимый объём статистики, но при этом, чтобы этот объём не был слишком велик. Рис.8. Главное окно приложения для сбора статистики. Стоит отметить, что в приложении также реализована возможность сбора данных с разных сетевых адаптеров, установленных в системе. К примеру, данные могут приниматься не только по LAN, но и по сетям Wi-Fi, либо через интерфейс Bluetooth и с помощью данного приложения они все могут успешно обрабатываться. В приложении по анализу статистики реализованы процедуры, которые считывают данные выборок, сохраненные приложением для сбора статистики, вычисляют для каждой выборки параметры λ , α1, α2. В этом же приложении реализована возможность вывода графиков по обработанным данным, что позволяет более наглядно изучить механизм работы, как данного приложения, так и математической модели в целом.^ 2.3. Получение оценок параметров. Для работы алгоритма, следует привести данные сетевой активности, к более подходящему, для обработки, виду. В рамках данной дипломной работы было решено использовать математическую модель альтернирующего потока, так как модель альтернирующего потока событий является простейшей среди дважды стохастических потоков и в то же время должна более точно отражать реальную ситуацию, чем пуассоновская. Оценки параметров λ, α1, α2 по наблюдениям за потоком методом моментов получаются по формулам (2), которые указаны в пункте 1.3. Для получения одной оценки брались данные с промежутка в одну минуту, а интервал между оценками составлял 10 секунд (рис. 9.). Таким образом, данные новой оценки накладываются на данные от предыдущей, что позволяет снизить погрешности оценок, так как при оценивании учитывается больший объем данных, чем если бы оценки считались на независимых промежутках. Рис. 9.^ 2.4. Сглаживание оценок. При наличии временных рядов оценок параметров, можно приступать к непосредственно самой задаче анализа активности пользователя в сети. Как видно из рисунка 10, как правило графики оценок достаточно близки к графику кусочно-постоянной функции. Интервалы постоянства можно квалифицировать как интервалы, на которых характер трафика достаточно стабилен и однороден. Момент окончания такого интервала и начала следующего интервала постоянства есть момент, когда ситуация в сети изменяется, то есть характер трафика становится другим. Рис. 10. Несглаженный временной ряд оценки λ. Но также на графике присутствуют небольшие “всплески” – высокочастотная составляющая. Причиной таких высокочастотных колебаний является, во-первых, то, что математическая модель альтернирующего потока не в точности соответствует реальному трафику, как никакая идеальная модель не может соответствовать реальному явлению. Во-вторых, метод оценки параметров потока λ, α1, α2 имеет небольшую погрешность [8], которая также является причиной отклонений на графике. Такие колебания оценок могут затруднить определение моментов изменения характера трафика, маскируя их и затрудняя выделение интервалов постоянства на графике. Поэтому для упрощения последующей работы с временными рядами оценок, необходимо отфильтровать высокочастотные составляющие.^ 2.4.1. Подходы к сглаживанию данных. На сегодняшний день наиболее используемыми способами фильтрации данных являются: преобразование Фурье и вейвлет-преобразование. Оба этих подхода можно применить для фильтрации данных в рассматриваемом случае, однако преобразование Фурье имеет несколько недостатков: во-первых: исходный сигнал заменяется на периодический, с периодом равным длительности исследуемого образца; во-вторых: преобразование Фурье плохо работает при изменении параметров процесса со временем (нестационарности), поскольку дает усредненные коэффициенты для всего исследуемого образца. Вейвлет-преобразование по базису Хаара лишено этих недостатков.^ 2.4.2. Вейвлет-анализ и его применение. Основы вейвлет-анализа были разработаны в середине 80-х годов Гроссманом и Морле [15] как альтернатива преобразованию Фурье для исследования временных (пространственных) рядов с выраженной неоднородностью. В отличие от преобразования Фурье, локализующего частоты, но не дающего временного разрешения процесса, и от аппарата d-функций, локализующего моменты времени, но не имеющего частотного разрешения, вейвлет-преобразование, обладающее самонастраивающимся подвижным частотно-временным окном, одинаково хорошо выявляет как низко-частотные, так и высокочастотные характеристики сигнала на разных временных масштабах. По этой причине вейвлет-анализ часто сравнивают с "математическим микроскопом", вскрывающим внутреннюю структуру существенно неоднородных объектов. Указанная универсальность обеспечила вейвлет-анализу широкое использование в самых различных областях знаний. Семейства анализирующих функций, называемых вейвлетами, применяются при анализе изображений различной природы, для изучения структуры турбулентных полей, для сжатия больших объемов информации, в задачах распознавания образов, при обработке и синтезе сигналов, например, речевых, для определения характеристик фрактальных объектов. Подобно тому, как в основе аппарата преобразований Фурье лежит единственная функция w(t)=exp(it), порождающая ортонормированный базис пространства L2(0,2p) путем масштабного преобразования, так и вейвлет-преобразование строится на основе единственной базисной функции y(t), имеющей солитоноподобный характер и принадлежащей пространству L2(R), т.е. всей числовой оси. В западной литературе за этой функцией закрепилось название "вейвлет", что означает "маленькая волна", в отечественной – иногда ее называют "всплеском". Самый распространенный набор дискретных вейвлет-преобразований был сформулирован бельгийским математиком Ингрид Добеши (Ingrid Daubechies)[16] в 1988 году. Он основан на использовании рекуррентных соотношений для вычисления всё более точных выборок неявно заданной функции материнского вейвлета с удвоением разрешения при переходе к следующему уровню (масштабу). В своей основополагающей работе Добеши выводит семейство вейвлетов, первый из которых является вейвлетом Хаара. Примеры часто используемых вейвлетов HAAR - вейвлет: FHAT - вейвлет ("Французская шляпа" - French hat): Wave - вейвлет: MHAT - вейвлет ("Мексиканская шляпа" - Mexican hat): Вейвлет Морле (образует комплексный базис): Применение вейвлет-преобразования:^ Обработка экспериментальных данных. Поскольку вейвлеты появились именно как механизм обработки экспериментальных данных, их применение для решения подобных задач представляется весьма привлекательным до сих пор. Вейвлет-преобразование дает наиболее наглядную и информативную картину результатов эксперимента, позволяет очистить исходные данные от шумов и случайных искажений, и даже "на глаз" подметить некоторые особенности данных и направление их дальнейшей обработки и анализа. Кроме того, вейвлеты хорошо подходят для анализа нестационарных сигналов, возникающих в медицине, анализе фондовых рынков и других областях. ^ Обработка изображений. Наше зрение устроено так, что мы сосредотачиваем свое внимание на существенных деталях изображения, отсекая ненужное. Используя вейвлет-преобразование, мы можем сгладить или выделить некоторые детали изображения, увеличить или уменьшить его, выделить важные детали и даже повысить его качество! ^ Сжатие данных. Особенностью ортогонального многомасштабного анализа является то, что для достаточно гладких данных полученные в результате преобразования детали в основном близки по величине к нулю и, следовательно, очень хорошо сжимаются обычными статистическими методами. Огромным достоинством вейвлет-преобразования является то, что оно не вносит дополнительной избыточности в исходные данные, и сигнал может быть полностью восстановлен с использованием тех же самых фильтров. Кроме того, отделение в результате преобразования деталей от основного сигнала позволяет очень просто реализовать сжатие с потерями – достаточно просто отбросить детали на тех масштабах, где они несущественны! Достаточно сказать, что изображение, обработанное вейвлетами, можно сжать в 3-10 раз без существенных потерь информации (а с допустимыми потерями – до 300 раз!). В качестве примера отметим, что вейвлет-преобразование положено в основу стандарта сжатия данных MPEG4. ^ Нейросети и другие механизмы анализа данных. Большие трудности при обучении нейросетей (или настройке других механизмов анализа данных) создает сильная зашумленность данных или наличие большого числа "особых случаев" (случайные выбросы, пропуски, нелинейные искажения и т.п.). Такие помехи способны скрывать характерные особенности данных или выдавать себя за них и могут сильно ухудшить результаты обучения. Поэтому рекомендуется очистить данные, прежде чем анализировать их. По уже приведенным выше соображениям, а также благодаря наличию быстрых и эффективных алгоритмов реализации, вейвлеты представляются весьма удобным и перспективным механизмом очистки и предварительной обработки данных для использования их в статистических и бизнес-приложениях, системах искусственного интеллекта и т.п. ^ Системы передачи данных и цифровой обработки сигналов. Благодаря высокой эффективности алгоритмов и устойчивости к воздействию помех, вейвлет-преобразование является мощным инструментом в тех областях, где традиционно использовались другие методы анализа данных, например, преобразование Фурье. Возможность применения уже существующих методов обработки результатов преобразования, а также характерные особенности поведения вейвлет-преобразования в частотно-временной области позволяют существенно расширить и дополнить возможности подобных систем. ^ 2.4.3. Сглаживание экспериментальных данных. Для упрощения обработки данных необходимо произвести сглаживание, что позволит отфильтровать высокочастотную составляющую, которая ошибочно может быть принята, за изменения характера трафика. Алгоритм по сглаживанию временных рядов вейвлет-преобразованием по базису Хаара был успешно реализован, результат его действия представлен на рисунке 11. Рис 11. а) несглаженные временные ряды параметров. б) сглаженные временные ряды параметров Чтобы получить сглаженный временной ряд, при помощи вейвлет-преобразования производилось частотное разложение исходного временного ряда. Затем разложение, содержащее самую высокую частоту, удалялось и проводилась обратная сборка ряда. Результатом такой обработки временных рядов, изображенных на рисунке 11а, стали сглаженные ряды c более четкими моментами изменения характера трафика (рис. 11б). В ходе преобразования при разложении временного ряда значений λ, изображенном на рисунке 11а, вейвлет-преобразованием по базису Хаара были получены следующие разложения (рис. 12): Рис. 12. Частотные разложения временного ряда параметра λ.^ 2.5 Стратификация данных. Одним из наиболее простых и эффективных статистических методов анализа данных является метод стратификации (очень широко используется в социологии). В соответствии с этим методом производят стратификацию статистических данных, то есть группируют данные в зав