Содержание к диссертации
Введение
ГЛАВА 1. Технология и системы data mining в геофизике 14
1.1. Системы Data Mining 14
1.1.1. Понятие системы Data Mining 14
1.1.2. Data Mining в обработке сигнальной информации 16
1.1.3. Типовая структура системы Data Mining 18
1.2. Классы задач Data Mining 19
1.2.1. Задачи регрессии и классификации 20
1.2.2. Задача поиска ассоциативных правил 21
1.2.3. Задача кластеризации 22
1.3. Обзор подходов к исследованиям геофизических сигналов 23
1.4. Качественный анализ сигналов геофизических полей 26
1.5. Требования к системе обработки сигналов в геофизике 30
1.5.1. Требования к структуре 30
1.5.2. Требования к математическому обеспечению 31
1.5.3. Требования к информационному обеспечению 31
1.5.4. Требования к эргономике и технической эстетике 32
Выводы 32
ГЛАВА 2. Формализация задач обработки сигналов геофизических полей и методы их решения 34
2.1. Структурная модель сигнала 34
2.2. Методика обработки геофизических сигналов с использованием технологии Data Mining 36
2.3. Формулировка задачи сегментации геофизических сигналов 39
2.4. Задача классификации 42
Выводы 43
ГЛАВА 3. Разработка алгоритма сегментации сигналов на основе вейвлет-пакетов 45
3.1. Вейвлет-пакетная модель элементарного блока 45
3.2. Структура кратномасштабного анализа 46
3.3. Структура вейвлет-пакетного разложения 48
3.4. Алгоритм выбора наилучшего дерева разложения на основе энтропии 56
3.5. Алгоритм сегментации на основе вейвлет-пакетного разложения 59
3.6. Параметры алгоритма и рекомендации по их выбору 66
Выводы 67
ГЛАВА 4. Анализ последовательностей сегментов 69
4.1. Анализ последовательностей сегментов 69
4.2. Ассоциативные правила и анализ последовательностей 70
4.2.1. Основные понятия 70
4.2.2. Характеристики правил 70
4.2.2. Понятие транзакции для последовательности
сегментов 72
4.3. Алгоритмы построения ассоциативных правил 73
4.3.1. Алгоритм Apriori 73
4.3.2. Модифицированные алгоритмы Apriori 74
4.4. Статистический анализ 75
4.5. Формы представления структурной модели 76
Выводы 77
ГЛАВА 5. Программный комплекс моделирования, обработки и анализа сигналов геофизических полей 79
5.1. Структура программного комплекса 79
5.1.1. Описание комплекса 79
5.1.2. Структура комплекса 79
5.2. Структура подсистемы моделирования 85
5.2.1. Этапы генерации сигнала 85
5.2.2. Генерация элементарного блока 86
5.3. Структура подсистемы анализа 88
Выводы 89
ГЛАВА 6. Вычислительные эксперименты по анализу сигналов 90
6.1. Анализ модельных сигналов 90
6.1.1. Методика проведения эксперимента 90
6.1.2. Описание экспериментальных сигналов 91
6.1.3. Результаты экспериментов 99
6.2. Анализ сигналов сейсмоакустической эмиссии 101
6.2.1. Описание экспериментальных данных 101
6.2.2. Методика эксперимента 106
6.2.3. Результаты эксперимента 106
6.2.3.1. Суточные вариации сигнала 106
6.2.3.2. Сравнительный анализ датчиков S1 и S2 109
6.3. Анализ волновых возмущений в атмосфере на основании данных катастрофического извержения вулкана Шивелуч 12
ноября 1964 г 112
6.3.1. Описание экспериментальных данных 112
6.3.2. Методика эксперимента 114
6.3.3. Результаты эксперимента 115
6.4. Анализ волновых возмущений в атмосфере, сопровождавших эксплозию вулкана Карымский 21 августа 1997г 116
6.4.1. Описание экспериментальных данных 116
6.4.2. Результаты эксперимента 118
Выводы 119
Заключение , 120
Список литературы
- Data Mining в обработке сигнальной информации
- Методика обработки геофизических сигналов с использованием технологии Data Mining
- Структура вейвлет-пакетного разложения
- Ассоциативные правила и анализ последовательностей
Введение к работе
Актуальность. Большое значение в геофизических и геохимических исследованиях имеют методы и средства сбора и анализа данных наблюдений. К настоящему времени геофизика почти полностью перешла к применению современных цифровых систем сбора, передачи, хранения и обработки данных. Развитие методологической, теоретической и инструментальной базы геофизики позволяет получать принципиально новые знания о геодинамических процессах и строении Земли.
Классическим подходом к анализу сигналов в геофизике является экспертный метод, который обладает рядом недостатков, связанных с субъективностью мнения эксперта. Всевозрастающий объем данных, получаемых в настоящее время в ходе исследований геодинамических процессов, требует принципиально нового подхода к их обработке. Обнаружение и выделение в геофизических сигналах особенностей, повторяющихся процессов, скрытых аномалий и закономерностей, обусловленных процессами, происходящими в недрах Земли, требуют определенной формализации, которая возможна при использовании современных методов математического моделирования. Огромный поток данных делает необходимым разработку автоматических систем, формирующих описание исследуемых сигналов и выделение в них особенностей, связанных с изменениями в структуре геологической среды или в таких геодинамических процессах как землетрясения и извержения вулканов. Целью таких систем является повышение производительности обработки регистрируемых данных, возможность формализовать и повысить эффективность выделения различного вида особенностей сигнала, а также облегчить интерпретацию получаемых данных.
Построение модели геологической среды является сложной и, зачастую, не решаемой задачей, вследствие многофакторности объекта моделирования. Получаемые модели не могут применяться для достоверного прогноза поведения моделируемой системы. В связи с этим, в настоящее время в геофизике делается упор на разработку методов анализа результатов наблюдения за поведением реальной среды на основании записей сигналов геофизических полей с последующим построением расчетных и эмпирических зависимостей, которые отражают состояние геологической среды. Так, известно, изменения в структуре сигналов геофизических полей являются следствием изменения напряженно-деформированного состояния среды. Последнее является основой в задачах поиска предвестниковых аномалий землетрясений и прочих природных катастроф.
Основная задача анализа сигналов заключается в представлении сигнала в такой форме, на основании которой можно получить новую информацию о процессах, протекающих в исследуемой системе. В этом плане нашли широкое применение методы параметрического моделирования, которые имеют свои достоинства и недостатки. Так, например, модель авторегрессии - проинтегрированного скользящего среднего и ее частные случаи, сложна для интерпретации, так как лишь косвенно отражает структуру сигнала. В связи с этим перспективным представляется подход структурного моделирования, когда модель сигнала формируется из компонент с заданными свойствами, которые задаются на основе представлений о физике процесса, причем формулировка данных свойств, требует применения математических методов, позволяющих описать сигнал, поведение которого меняется с течением времени (нестационарные сигналы). По мнению автора, наиболее эффективно данную задачу позволяют решать методы, основанные на теории вейвлет-преобразования, для которой в настоящее время хорошо развита математическая база, и которая нашла широкое применение в обработке сигналов различной природы. Для решения поставленной задачи предлагается применить один из видов вейвлет-преобразования, а именно обобщение конструкции кратномасштабного анализа - вейвлет-пакетное разложение. В отличие от кратномасштабного анализа, вейвлет-пакеты описывают локальное поведение сигнала во всей полосе частот и обладают рядом полезных свойств, к которым относятся:
-линейность вейвлет-преобразования;
- возможность к частотно-временной локализации;
- широкие возможности настройки алгоритмов, основанных на вейв-лет-пакетах, путем выбора различных базисных функций и критериев выбора лучшего базиса.
К сожалению, вейвлет-преобразование не является инвариантным к сдвигу. В связи с этим в диссертации предлагается использовать блочный алгоритм сегментации.
При решение аналогичных задач (поиска закономерностей и особенностей в данных) в экономических, медицинских и социальных исследованиях хорошо зарекомендовала себя технология Data Mining, которая аккумулирует в себе концепцию, методы и средства анализа данных.
К основным задачам технологии Data Mining относятся: классификация, кластеризация, регрессия, поиск ассоциативных правил. В работе проводится формулировка данных задач, которые в том или ином виде решаются в теории обработки сигналов.
Универсальность Data Mining позволяет ее применить к исследованию сигнальной информации во многих областях науки, но ориентированность ее методов на обнаружение знаний в специализированных базах данных (экономических и пр.) требует адаптации этой технологии к обработке сигналов геофизических и геохимических полей с целью выделения аномалий, обусловленных геодинамическими процессами.
Обобщая сказанное выше, можно сделать вывод, что актуальность предлагаемого подхода при анализе геофизических и геохимических данных определяется возможностью решения таких задач, как поиск предвестников сильных землетрясений, выделение отдельных этапов в динамике вулканических извержений, обнаружение волновых возмущений в атмосфере при вулканических взрывах и т.д.
Актуальность предлагаемой работы определяется важностью прогноза природных явлений по наблюдаемым изменениям геофизических
-10-полей в рамках программы по обеспечению безопасности населения и народно-хозяйственных объектов при возникновении природных катастроф.
Целью диссертационного исследования является разработка методики анализа сигналов геофизических полей с использованием технологии Data Mining с целью выявления их аномального поведения.
В ходе достижения цели решались следующие задачи:
1. Качественный анализ сигналов и формулировка требований к разрабатываемой системе автоматической обработки.
2. Разработка методологии анализа сигналов с использованием технологии Data Mining на основе сформулированных требований.
3. Разработка формы представления сигнала - его структурной модели.
4. Разработка алгоритмов сегментации сигналов, классификации их элементов и построения структурной модели.
5. Разработка программного обеспечения, реализующего алгоритмы.
6. Проведение экспериментов по установлению эффективности разработанной системы.
Методы исследования. В диссертационной работе использовался аппарат теории цифровой обработки сигналов, теории распознавания образов, математического моделирования, методы дискретной и вычислительной математики, основы функционального анализа.
Научную новизну работы составляют следующие положения:
1. Использование технологии Data Mining для анализа геофизической информации и построения моделей сигналов.
2. Структурная модель сигналов геофизических полей, описывающая изменение свойств сигнала как последовательности классов сегментов, позволяющая эффективно интерпретировать результаты экспериментов.
3. Алгоритм сегментации и классификации сигналов на основе разложения, отличающийся адаптивностью к свойствам сигнала.
Научные положения, выносимые на защиту:
1. Методика анализа сигналов геофизических полей с использованием технологии Data Mining.
2. Способ описания структуры и классификации сигналов на основе лучшего вейвлет-пакетного разложения.
3. Структурная модель сигнала геофизических полей и методы ее исследования.
4. Алгоритм сегментации сигналов на основе вейвлет-пакетов.
Практическую значимость работы составляют:
1. Разработанные алгоритмы для сегментации сигналов геофизических полей.
2. Разработанный комплекс прикладных программ, автоматизирующий построение и исследование структурной модели сигналов геофизических полей.
3. Предложенные алгоритмы и методы могут служить основой для создания новых систем анализа нестационарных сигналов в различных прикладных областях.
Основные положения диссертационного исследования докладывались на следующих научных мероприятиях:
Вторая Всероссийская научная конференция «Проектирование инженерных и научных приложений в среде MATLAB», Москва, 2004 г.
Ежегодная конференция, посвященная Дню вулканолога, Петропавловск-Камчатский, 2004, 2005 г.г.
- Международная конференция по мягким вычислениям и измерениям SCM, Санкт-Петербург, 2004, 2006 г.г.
7-я международная конференция по распознаванию образов и анализу изображения PRIA 7, Санкт-Петербург, 2004 г. Конференция профессорско-преподавательского состава СПбГЭ-ТУ «ЛЭТИ», Санкт-Петербург, 2005, 2006 г.г. Четвертый всероссийский симпозиум «Сейсмоакуетика переходных зон», Владивосток, 2005 г.
Ежегодная региональная молодёжная конференция «Исследования в области наук о Земле (география, геология, геофизика, геоэкология, вулканология), Петропавловск-Камчатский, 2005 г.
- Конференция Комплексные сейсмологические и геофизические исследования Камчатки 17-18 января 2006 г., Петропавловск Камчатский, 2006г.
По теме диссертации опубликовано 11 научных работ, из них 1 статья, 10 докладов в материалах и трудах международных и всероссийских конференций.
Результаты диссертационного исследования внедрены в лаборатории комплексных исследований предвестников землетрясений и извержений вулканов Института вулканологии и сейсмологии ДВО РАН и в учебный процесс кафедры прикладной математики Камчатского государственного университета им. В. Беринга, подтвержденные актами о внедрении.
Общее содержание диссертационной работы соответствует научному направлению "Распознавание образов и обработка изображений" Государственной научно-технической программы "Перспективные информационные
-13-технологии". Исследование выполнялось в рамках научно-исследовательской работы «Современная геодинамика и новейшая тектоника зоны сочленения Курило-Камчатской и Алеутской островных дуг», проводимой в Институте вулканологии и сейсмологии Дальневосточного отделения РАН. Исследование выполнено при финансовой поддержке гранта РФФИ 02-05-64467-а (2004 г.) и грантов Президиума Дальневосточного отделения РАН 05-Ш-Г-08-140 (2005 г.), 06-Ш-А-08-335 (2006 г.).
Data Mining в обработке сигнальной информации
Технология Data Mining пока не нашла широкого применения в обработке сигнальной информации. Это связано с тем, что изначально методы Data Mining создавались для работы с большими базами данных, применяемых в экономике, медицине и т.д. Обработка сигналов требует применения принципиально нового подхода к представлению исходных данных для алгоритмов интеллектуального подхода. Существующие методы интеллектуального анализа в чистом виде сложно применить к обработке сигнальной информации.
Интеллектуальный анализ сигнальной информации базируется [69, 73] на концепциях Data Mining, классического и адаптивного анализа временных рядов, хаотической и нелинейной динамики и теории динамических систем. Методы Data Mining ставят основную задачу интеллектуального анализа сигнальной информации - обнаружение скрытых образов (patterns) [69, 71, 74].
Сложность в исследовании сигнальной информации научного характера заключается в априорной неопределенности в целях анализа [30].
Исходя из определения Data Mining, любая автоматическая (автоматизированная) система, предназначенная для выявления ранее неизвестных особенностей сигналов и способствующая их интерпретации с целью формирования новых знаний, может быть отнесена к системам Data Mining.
С позиции обработки сигналов, сырыми (исходными) данными являются файлы цифровых записей регистрируемых сигналов с описанием условий наблюдения. «Знание — форма существования и систематизации результатов познавательной деятельности человека. Знание - это проверенный практикой результат познания действительности, верное ее отражение в мышлении человека, обладание опытом и понимание, которые являются правильными и в субъективном и в объективном отношении и на основании которых можно построить суждения и выводы, кажущиеся достаточно надежными, для того чтобы рассматриваться как знания» [59].
Получаемые знания должны удовлетворять определенным требованиям. Рассмотрим их с точки зрения применения Data Mining к обработке геофизических сигналов.
1. Знания должны быть новыми, ранее неизвестными. Специалисты в области геофизики обладают опытом в исследовании сигналов. Этот опыт может породить множество новых знаний К (рис. 1.1). Система Data Mining должна обладать методами, которые позволяют порождать знания, в том числе отличные от К.
Следует отметить желательную цель системы Data Mining, заключающуюся в том, что множество KDM знаний, порождаемых системой Data Mining, должно пересекаться с множеством К, получаемых из человеческого опыта, а также множеством Ко, уже существующих знаний. Это условие позволяет верифицировать (проверить) знания, получаемые автоматически.
2. Знания должны быть нетривиальными. Это свойство накладывает ограничения на качество получаемых знаний. Получаемые знания считаются оправдывающими затраты на построение системы Data Mining, если они не могут быть получены более простыми методами. Так, в геофизике существуют хорошо отработанные методы обнаружения сейсмических событий во временной области.
3. Знания должны быть практически значимыми. Получаемые знания должны служить основой для получения новой информации об объекте исследования, позволять более полно его описывать и судить о его природе.
4. Знания должны быть доступны для понимания человеком, то есть система Data Mining должна представлять информацию в доступном для интерпретации человеком виде, поэтому сами знания должны обладать возможностью быть интерпретированными.
Общая схема системы Data Mining [12] представлена на рис. 1.2. Основой для формирования параметров алгоритмов Data Mining являются сведения, полученные в результате применения классических методов анализа и известной информации об объекте исследования (источнике данных).
Технология Data Mining включает в себя ряд компонентов: 1. Концепции и принципы, определяющие структуру решения задач. 2. Методы решения частных задач. 3. Средства - алгоритмы и программы, реализующие методы. 1.2. Классы задач Data Mining
Выделяют следующие классы задач Data Mining: - задача регрессии (определение параметров объекта); - задача классификации (отнесение объекта к определенному классу, классы считаются известными; частный случай задачи регрессии); - поиск ассоциативных правил (поиск частных зависимостей); - задача кластеризации (поиск независимых групп (кластеров) и их характеристик во множестве анализируемых данных).
Данные задачи можно разделить на две группы: описательные и предсказательные.
Описательные задачи направлены на создание модели, способствующей улучшению понимания анализируемых данных. К описательным относятся задачи кластеризации и поиска ассоциативных правил.
Предсказательные задачи направлены на создание модели, позволяющей по известным данным сформировать новый набор данных, описывающих будущее поведение объекта исследования. К предсказательным задачам относят классификацию и регрессию, а также, в некоторых случаях, задачу поиска ассоциативных правил.
Рассмотрим формальную постановку задач Data Mining [б]. Отметим, что для решения конкретной прикладной задачи требуется провести адаптацию ее формальной постановки.
Методика обработки геофизических сигналов с использованием технологии Data Mining
Ниже описан предлагаемый подход к обработке сигналов геофизических полей, состоящий их нескольких этапов. Схема этапов предлагаемого метода представлена на рис.2.2. Данный подход предполагает решение (явно или не явно) следующих формальных задач: 1. Задача сегментации. 2. Задача классификации. 3. Задача анализа последовательностей. Этап 1. Сбор и обработка сырых данных.
Задача сбора данных решается на аппаратном уровне и включает в себя регистрацию сигналов и подготовку их цифровых записей.
Далее на данном этапе происходит подготовка сырых данных к применению методов Data Mining.
Процесс предобработки включает в себя различные операции цифровой обработки сигналов [3, 5, 52]: 1. Преобразование форматов данных. 2. Удаление тренда. 3. Удаление аномальных значений (выбросов). 4. Фильтрация и шумоочистка.
Также на этом этапе может быть выполнен предварительный анализ данных - анализ спектрального состава, определение основных статистических параметров.
Помимо описанных действий, на этапе интерпретации результатов может быть полезным наличие базы данных, содержащей параметры и условия регистрации данных.
На данном этапе рассматриваются задачи, решение которых невозможно или представляет сложность при применении классических методов. К этим задачам относятся: 1. Выделение скрытых особенностей сигнала. 2. Выделение фоновых процессов. 3. Классификация особенностей.
Выявление скрытых закономерностей в последовательности условно стационарных участков сигнала. Явное решение этих задач в геофизике затруднительно вследствие неопределенности в структуре наблюдаемых данных. Решение перечисленных задач предлагается проводить по следующей схеме: 1) Выделения особенностей и формирование признакового описания сегментов;
Эта задача решается посредствам применения методов сегментации сигналов и является одним из вариантов задачи регрессии.
Алгоритмы сегментации довольно разнообразны. Предлагаемые автором алгоритмы подробно описаны ниже.
Сегментацию можно рассматривать как процесс преобразования сигнала к дискретной последовательности сегментов с известными свойствами.
В связи с тем, что выделенные в первом пункте сегменты являются разнородными, как по длине, так и по структуре, необходимо выбрать единые для всех сегментов признаки (представление сегментов).
2) Классификация сегментов;
После получения подготовленного материала необходимо его систематизировать. В зависимости от выбранного алгоритма сегментации выделенные участки сигнала (сегменты) могут быть разделены по классам автоматически, либо может потребоваться применение методов автоматической кластеризации.
В результате мы получаем последовательность сегментов, каждому из которых поставлена в соответствие строка (код), определяющая класс сегмента. Данный код включает номер (название или другой идентификатор) класса и длительность сегмента.
Построенная последовательность подлежит дальнейшему анализу. 3) Анализ последовательностей;
На третьем этапе выполняется решение задачи поиска ассоциативных правил (в частности, методом анализа последовательностей), т.е. поиск закономерностей в последовательности.
Теперь в имеющейся последовательности, отражающей порядок следования участков сигнала с известными свойствами, можно проводить поиск закономерностей.
С этой целью предлагается вести анализ последовательности сегментов по двум направлениям:
1. Поиск повторяющихся групп.
2. Построение статистической модели.
Вторая стратегия предполагает рассмотреть последовательность как реализацию случайного процесса, обладающего марковским свойством. Для описания системы требуется определить множество состояний и вероятности перехода из одного состояния в другое, а также параметры потока, приводящего систему в действие.
Этап 3. Интерпретация и визуализация.
Данный этап связан с представлением результатов конечному пользователю в удобном для него виде, и предполагает использование методов когнитивной графики и прочих средств визуализации, упрощающих пользователю понимание полученных результатов.
Структура вейвлет-пакетного разложения
Вейвлет-преобразование является мощным инструментом в исследовании сигналов. Использование вейвлетов позволяет выявлять аномалии сигналов и оценивать их некоторые характеристики. В приложении 1 приведено описание метода, предложенного автором, использования вейвлет-преобразования в оценке показателя Гельдера сигналов.
Как описано в п. 2.1, алгоритм сегментации должен выделить момент смены модели элементарного блока.
Одной из особенностей сигналов геофизических полей является их нестационарная частотная структура [21, 29, 56]. С течением времени можно проследить динамику информативного диапазона частот.
Конструкция кратномаштабного анализа позволяет разбить частотную область на диапазоны, но разбиение происходит лишь в сторону низкочастотного диапазона. При построении модели элементарного блока больший интерес представляет структура всего частотного диапазона. Вейвлет-пакеты обладают лучшей частотной локализацией по сравнению с другими методами. В связи с этим, для построения модели будут использоваться свойства вейвлет-пакетного разложения.
В основе вейвлет-пакетного разложения лежит понятие кратномасштабного анализа [24, 32,67]. Ортогональным кратномасштабным анализом в L2(R) называется последовательность замкнутых подпространств Vі с L2(R), ieZ, таких, что:
Существует элемент (х)єГ, интеграл которого не равен нулю, такой, что последовательность {ср(х - j)}JeZ является ортонормированным базисом в Vй; элемент ср{х) называется порождающей скейлинг-функцией.
Рассмотрим некоторые свойства кратномасштабного анализа, вытекающие непосредственно из данного определения.
1. Из подпунктов 1 и 4-6 определения следует, что найдутся такие числа hk є R,k є К,К с Z, что р(х) = у[2 к р(2і-к). Пі) Это выражение называется масштабным соотношением для скейлинг-функций.
2. Для любого / є Z последовательность\р)} , где р)(/) = 4 hk(p\2!t-j), является ортонормированным базисом в пространстве Vі. Функции p j(t) называются скейлинг-функциями.
3. Если порождающая скейлинг-функция (х) принадлежит множеству L2(R) и нормирована, т.е. со \ p{f)dt = 1. -со то с точностью до значений на множестве меры нуль эта функция единственным образом определяется уравнением (3.1), т.е. набором значений
Мык Для каждой пары подпространств Vі czVM,ieZ, кратномасштабного анализа должно существовать подпространство W такое, что Vі 1W ,VM=V W .
Такие подпространства можно назвать уточняющими или детализирующими в том смысле, что они содержат уточняющую информацию, необходимую для перехода от уровня разрешения /к уровню / +1. Справедливо следующее: W =L2(R). І= оо
Если существует элемент if/(t)eW такой, что последовательность {y(x-j)}jeZ является ортонормированным базисом в W, то этот элемент называется порождающим вейвлетом.
Если y/(t)eW - порождающий вейвлет, то набор функций wit)).. ортонормированный базис в L2(R). Здесь (f) = V2y (27-/). Функции из этого набора называются вейвлетами. Детализирующие подпространства W ,ieZ, принято также называть вейвлет-пространствами.
Очевидно, что порождающий вейвлет ;//(0 является элементом пространства Vі. Следовательно, найдутся такие числа g, eR,!eL,Lc:Z, что у/{х) = 7g,i/r(2t - к). (3.2) /ЄІ
Это соотношение является масштабным соотношением для вейвлетов. Оно похоже на масштабное соотношение для скейлинг-функций (3.1), но имеет важное отличие: (3.1) является уравнением (в левой и правой части -находится одна и та же функция), (3.2) — выражением одной функции через другую. Таким образом, порождающий вейвлет y/(t) с точностью до значений на множестве меры нуль определяется коэффициентами {g;}/ei, если определена порождающая скейлинг-функция cp{t), а она, в свою очередь, определяется коэффициентами \ик}ык соотношения (3.1). Следовательно, система скейлинг-функций и вейвлетов может быть полностью определена двумя наборами коэффициентов: {hk}keK и {g,}leL
Так как набор функций \y j(t)).. является ортонормированным базисом в L2(R), то любую функцию /(х) є Z,2(i?)можно единственным образом представить в виде разложения
Ассоциативные правила и анализ последовательностей
Будем исследовать сигнал S. Разобьем S на окна с перекрытием. Размеры окон будут определять разрешение алгоритма сегментации. Все действия алгоритма будут проводиться последовательно над каждым окном. Сравнение характеристик, полученных в каждом окне, будет производиться для соседних пар окон. Первый этап заключается в анализе свойств сигнала в j-м окне. Пусть s. ={S-W} - участок сигнала, соответствующий j-му окну (W сдвинутая функция-окно).
Выполним вейвлет-пакетное разложение S. с заранее выбранным базисом у/ до уровня N В результате имеем граф - полное бинарное дерево высотой N, число листьев у которого равно 2N. Каждой вершине этого графа соответствуют вейвлет-коэффициенты. Обозначим этот граф разложения Gy.-Вершины Gj можно частотно упорядочить, т.е. все левые потомки 1-Й вершины соответствуют низшей частоте, правые - высшей. Теперь имеем разбиение частотной оси; диапазон каждого из элементов разбиения определяется в соответствии с (3.5). На рис.3.9 схематично изображен принцип частотного упорядочивания и разбиения частотной области.
Далее получим лучшее дерево разложения (основанное на энтропии) -Gj. Дерево Gj, в общем случае, является неполным.
Графу Gj (листьям дерева) соответствует разбиение частотной области на интервалы, но, в отличие от Gj, на неравные - {(fk,fM]}. А/ зависит от уровня, на котором расположен к-и лист (рис. 3.10). Аналогичные действия производим над j+І окном. Имеем наилучшее дерево разложения для j+І окна - G,.+1.
Деревья Gj и Gj+l, а точнее, порождаемые ими разбиения частотной оси, отражают структуру спектра сигнала, заключенного в соответствующем окне. То есть, если два разбиения структурно совпадают, то они имеют диапазоны частот, обладающие одинаковым свойством (рис. 3.11).
Таким образом, два окна/ иу+7 относятся к одному сегменту сигнала с позиции описанного выше критерия равенства структур спектров, если их лучшие деревья вейвлет-пакетного разложения типологически совпадают.
Алгоритм может быть снабжен блоком выделения аномалий. Здесь аномалия - блок, длина которого равна шагу алгоритма, который не образуют отдельного элементарного блока или сегмента. Пусть Р - есть отображение некоторой последовательности в конечное множество Z: P:{M,.}- Z. Пусть данное отображение обладает аддитивностью по времени, т.е. если P(UJ)=PJ иP(U2)=Pj, то P(UJ+U2)=PJ. (3.7)
Рассмотрим последовательность (сигнал) {xj-. Выделим в сигнале подпоследовательность длиной п Л] fXi, Xf+j, ...Xi+W.]f.
Пусть на данной подпоследовательности Р принимает значение Р(Х])=Р]. X] - есть начало сегмента Sj. Подпоследовательность А2 №+» Xi+s+i, ...Xi+S+W.i/. где s 0 - шаг, отнесем к сегменту Sj, если Р(Х2)= P(XJ)=PJ. Т.е. если Р(Х2)= P(X0=Ph то SJ=XJ+X2. Отметим, что вследствие (3.7) P(SJ)=PJ.
Предположим, что данное условие не выполняется, т.е. Р(Х2)= Р2. Это значит, что в Х2 содержатся точки меняющие значение критерия Р. Эти точки могут быть выделены в аномальную подпоследовательность А={ Xj+w-i, Xj+j, ...Xi+S+W.]f.
Данный аномальный участок может относиться либо к началу нового сегмента, либо быть некоторой особенностью. Для определения этого факта предлагается проверить значение критерия Р на блоке непересекающемся с Х2. Л-3 i%i+s+w Xi+s+w+І i+s+lw -If Если P(Xj)=P(X3)=Pi, то считаем, что Sj=Xj+X2, т.е. продолжаем сегмент Sj. В противном случае (Р(Хз)=Рз) нужно принять решение о начале нового сегмента. Для этого проверим значение критерия на участке
Если Р(Х3)=Р(Х4) Рз, то начинаем сегмент S2=X3, иначе, аномальный блок А выделяем в отдельный сегмент SA, а сегмент S2 начинаем с подпоследовательности Х4.
