Содержание к диссертации
Введение
ГЛАВА I. Математическое описание алгоритма «кристалл» 33
1.1. Введение 33
1.2. Оптический подход
1.2.1. Свет 34
1.2.2. Плотность освещения 37
1.2.3. Характеристики множества 40
1.3. Глобальный «кристалл» 42
1.3.1. Блок-схема 43
1.3.2. Блок «Основа» 43
1.3.3. Блок «Рост 1» 51
1.3.4.Блок «Рост II» 52
1.3.5. Блок «Завершение» 55
1.4. Локальный «кристалл» 55
1.4.1. Локальная плотность 56
1.4.2. Блок «Основа» 57
1.4.3. Блок «Рості» 58
1.4.4. Блок «Рост II» 62
1.4.5. Блок «Завершение»
1.5. Примеры работы алгоритма 64
1.6. Сравнительный анализ алгоритма «кристалл» с алгоритмом кластеризации «роден»
1.6.1. Алгоритм кластеризации «Роден» 68
1.6.2. «Роден» и «Кристалл»
1.7. Программная реализация алгоритма «кристалл» 78
1.8. Выводы 81
ГЛАВА II. Приложения алгоритма «кристалл» к анализу геомагнитных данных 83
2.1. Постановка задачи 83
2.2. Метод деконволюции эйлера
2.2.1. Описание метода 86
2.2.2. Определение магнитного момента эквивалентных источников 89
2.2.3. Отбраковка решений 90
2.3. Расчет статистических оценок для сгущения. Поиск мер неопределенности полученных оценок 91
2.4. Приложение алгоритма «кристалл» к синтетическим магнитным данным: определение глубин и углов намагниченности аномалеобразующих тел 93
2.4.1. Описание исходных данных 93
2.4.1.1. Параметры точечных диполей 93
2.4.1.2. Расчет аномального магнитного поля АГдля математического диполя 95
2.4.1.3. Результаты применения метода деконволюции Эйлера
2.4.2. Обработка эйлеровых решений алгоритмом «Кристалл» 102
2.4.3. Синтетический пример с добавленным в исходные данные случайным шумом 104
2.4.4. Выводы 106
2.5. Приложение алгоритма «кристалл» к интерпретации магнитных аномалий в районе массива ахагтар (алжир) 107
2.5.1. Геологическое строение региона 107
2.5.2. Описание исходных данных ПО
2.5.3. Определение направления намагниченности при помощи МДЭ и алгоритма «Кристалл». Интерпретация результатов 112
2.5.4. Определение глубин залегания верхних кромок возмущающих тел с помощью МДЭ и алгоритма «Кристалл». Интерпретация результатов 121
2.5.5. Выводы 129
Заключение 131
Список литературы
- Блок «Основа»
- Определение магнитного момента эквивалентных источников
- Расчет аномального магнитного поля АГдля математического диполя
- Определение глубин залегания верхних кромок возмущающих тел с помощью МДЭ и алгоритма «Кристалл». Интерпретация результатов
Введение к работе
Обоснование постановки задачи. Актуальность работы
Методы интерпретации потенциальных полей и, в частности, магнитных аномалий в настоящее время широко применяются при решении многих задач, включая изучение строения и развития структур земной коры и поиск месторождений полезных ископаемых. Круг применяемых методов интерпретации крайне широк: от экспресс-методов, позволяющих получить некоторые общие данные о строении изучаемых структур без привлечения ответственных априорных предположений, до сложных методов подбора с учетом большого объема априорной информации.
Метод деконволюции Эйлера, развитию которого посвящена данная работа, относится к экспресс-методам. Он основан на определении положения эквивалентных источников (эйлеровых решений) в скользящих «окнах». В благоприятных ситуациях (изолированные тела, низкий уровень помех и т.д.) эти решения трассируют контуры аномалообразующих тел и дают оценку глубины их залегания. Метод весьма чувствителен к уровню помех, точности вычисления производных аномального поля, интерференции сигналов от близко расположенных источников и т.д., поэтому в реальных ситуациях эйлеровы решения обычно образуют размытые облака, что затрудняет определение положения аномалообразующих тел. Разработан целый ряд критериев, позволяющих отбраковывать «плохие» решения, однако ситуацию удается улучшить далеко не всегда. В то же время расчеты на теоретических примерах показывают, что даже в ситуациях, когда эйлеровы решения не образуют плотных скоплений вблизи аномалообразующих тел, в их окрестности плотность распределения решений оказывается большей. Поэтому применение в таких задачах методов формализованной кластеризации представляется естественным и перспективным.
Кластеризация, как математическая конструкция, является достаточно универсальным методом анализа данных и успешно применяется в самых разнообразных областях: медицине, астрономии, археологии, маркетинге, экологии, лингвистике. Необходимо отметить, что кластеризация может выполняться не только по пространственным переменным. Методы кластеризации различаются:
способом определения близости между объектами, принадлежащими кластеру, и
между кластерами,
правилом распределения объектов по классам,
предположением является ли кластер четким или нечетким подмножеством
исследуемой совокупности объектов,
фиксацией или настройкой в ходе классификации набора управляющих
параметров,
порядком обработки объектов: по одному или группами (последовательные
алгоритмы) или всей совокупности одновременно (параллельные методы) и т.д. Несмотря на широкое применение кластер-анализа [Мандель, 1988; Миркин, 1980; Олдендерфер и др., 1989; Ту и др., 1978; Эндрю, 1985; Хейс-Рог и др., 1987; Заде, 1980; Дуда и др., 1976; Гвишиани и др., 1988; Айвазян и др., 1989; Арефьев, 2003; Perkowitz et al., 2000], общепринятого однозначного определения кластера не существует. Среди большинства разработчиков имеется интуитивное понимание, что элементы одного кластера в выбранном пространстве параметров ближе друг к другу, чем к другим элементам, однако особенности этих отношений явно не формулируются. Для определения кластеров использовались различные параметры: плотность в метрическом пространстве, объем, занимаемый кластером, связанность элементов внутри кластера, промежутки между соседними кластерами в сравнении с их диаметрами и т.п.
Обычно кластер понимается как подмножество, которое характеризует одновременное сочетание повышенной плотности и отделимости. Однако практика показывает, что массивы анализируемых данных, в частности, совокупность решений, полученных методом деконволюции Эйлера, как правило, содержат плотные неизолированные сгущения, не поддающиеся однозначной идентификации. Настоящая работа, в рамках который был создан алгоритм «Кристалл», посвящена выделению в массивах данных областей с повышенной плотностью (сгущений). При построении этого алгоритма мы исходили из толкования кластер-анализа, как инструмента для изучения взаимного расположения объектов в некотором метрическом пространстве. В частности, результатом применения кластер-анализа может быть список всех возможных кластеров, полученных при некотором заданном определении кластера. При этом любые два кластера могут пересекаться по любому числу элементов. Такой подход допускает пересечение кластеров и не ограничивает число общих элементов для любых двух кластеров.
Данный подход позволил применить в «Кристалле» технику нечеткой логики и теории нечетких множеств, что согласуется с нечетким характером геофизических данных. По своей природе данные и знания о Земле неполны и нечетки, поэтому наиболее
адекватное их представление и формальный аппарат работы с ними также должен быть
нечетким. Процитируем в этой связи создателя теории нечетких множеств американского математика Л. Заде: «Образно говоря, теории о природе должны отражать то, что природа «пишет» скорее произвольными мазками, чем шариковой ручкой».
При пространственно-временном анализе геолого-геофизической информации присутствуют среди прочих два вида неопределенности, обусловленные: а) погрешностями в исходных данных из-за ошибок измерений и погрешности введения различных поправок; б) неточностью моделей среды, вызванных неизбежно упрощенным описанием сложных природных объектов (линеаризация, дискретизация и др.). Нечеткая математика и нечеткая логика позволяют учитывать неопределенность в данных, дать строгое математическое описание расплывчатых утверждений и преодолеть барьер между экспертом, суждения и оценки которого чрезвычайно важны, но являются приближенными и нечеткими, и компьютером, который может выполнять только четкие инструкции. Настоящая диссертация вносит свой вклад как в развитие соответствующего математического языка геофизики, так и его приложений в конкретных геофизических задачах.
В диссертации алгоритм «Кристалл» был применен для отбора плотных сгущений во множестве эйлеровых решений. Он проверен на модельных данных и применен для анализа магнитного поля в районе массива Ахаггар (Алжир). Предложенный метод показал на модельных и реальных данных свою эффективность при определении положения, глубины залегания и направления намагниченности аномалообразующихтел.
Цель работы
При работе с геофизическими массивами данных возникает задача поиска областей
с повышенной плотностью объектов. Плотные сгущения, носящие изолированный
характер, являются предметом кластерного анализа [Мандель, 1988; Миркин, 1980;
Олдендерфер и др., 1989; Ту и др., 1978; Everitt, 1980; Эндрю, 1985; Хейс-Рог и др., 1987;
Заде, 1980; Аверкин, 1998; Дуда и др., 1976; Тгуоп, 1939; Айвазян и др., 1989]. В настоящее
время разработаны многочисленные методы поиска такого рода сгущений. В диссертации
была поставлена более сложная задача нахождения плотных областей в произвольном
случае, поскольку во многих задачах интерес представляет поиск неизолированных
сгущений. Поэтому главной целью настоящей работы являлось создание, тестирование и
практическое применение принципиально нового математического аппарата,
предназначенного для выделения плотных сгущений в конечных метрических
пространствах. Это обстоятельство потребовало формального определения плотности в
конечном метрическом пространстве, что было сделано с помощью использования теории нечетких множеств.
Разработанный в диссертации алгоритм «Кристалл» является универсальным инструментом и может быть применен к различным типам геофизических данных, представленных в виде массивов объектов в «-мерном пространстве. Реализованы и описаны приложения алгоритма «Кристалл» к классификации эйлеровых решений, полученных на синтетических моделях, для проверки возможности его применения к реальным геомагнитным данным, полученным в районе массива Ахаггар, расположенного на юге Алжира.
Постановка задачи
Для достижения поставленной цели в ходе работы потребовалось решить следующие основные задачи:
-
Разработать метод выделения плотных неизолированных сгущений в конечных метрических пространствах на базе математического аппарата нечетких множеств и «оптического» подхода к метрическим пространствам (алгоритм «Кристалл»).
-
Создать на основе разработанного алгоритма «Кристалл» технологичное Windows-приложение для анализа и поиска сгущений в произвольных массивах данных, представленных в виде координат точек в двух- или трехмерном пространстве.
-
Исследовать эффективность работы алгоритма «Кристалл» на синтетических примерах геомагнитных данных, приближенных к реальным условиям, и сопоставить результаты алгоритма с известной информацией об анализируемых данных (параметрами моделей).
-
Исследовать на синтетических и практических примерах возможности определения геометрических характеристик и параметров вектора намагниченности для наборов решений, отобранных алгоритмом «Кристалл»; исследовать точность и разрешающую способность метода.
-
Применить алгоритм «Кристалл» к интерпретации геомагнитных аномалий в районе массива Ахаггар (Алжир), материалы по которому были получены в рамках программы сотрудничества между Институтом физики Земли в Париже (Франция) и ИФЗ РАН. '
Научная новизна
Автором создан принципиально новый алгоритм «Кристалл», предназначенный для выделения плотных сгущений в конечных метрических пространствах. Разработанный алгоритм выходит за рамки концепции классического кластерного анализа, поскольку алгоритмы кластерного анализа ориентированы на кластерность - одновременное сочетание повышенной плотности и отделимости, в то время как алгоритм «Кристалл» решает более сложную задачу, связанную только с первым свойством. В связи с этим, его можно считать посткластеризационным. Это обстоятельство потребовало формального определения плотности в конечном метрическом пространстве, что было достигнуто благодаря применению методов теории нечетких множеств. Разработанный алгоритм позволяет гибко решать задачу поиска сгущений с помощью свободных параметров и имеет широкий спектр возможных применений. Рассмотрено приложение алгоритма к анализу и классификации эйлеровых решений полученных по геомагнитным данным. На синтетических примерах продемонстрировано, что алгоритм «Кристалл» в совокупности с методом деконволюции Эйлера позволяет определять как геометрические характеристики аномалообразующих тел (положение в плане и по глубине), так и параметры вектора намагниченности. Это возможно для локализованных объектов, расстояние между которыми не меньше глубины их залегания. С использованием разработанного метода получены оценки направления вектора намагниченности аномалообразующих тел в районе массива Ахаггар (Алжир) и построена прогнозная карта глубин главной магнитоактивной поверхности.
Основные защищаемые положения
-
Разработан принципиально новый алгоритм «Кристалл», позволяющий осуществлять гибкое выделение плотных сгущений в конечных метрических пространствах. Алгоритм основан на формальном определении плотности в конечном метрическом пространстве, полученном с использованием математического аппарата нечетких множеств.
-
На основе применения алгоритма «Кристалл» для поиска сгущений во множестве эйлеровых решений создана новая методика, позволяющая определять положение и направление вектора намагниченности локализованных аномалообразующих объектов. Эффективность, разрешающая способность и
устойчивость метода по отношению к шуму в исходных данных исследованы на целом ряде синтетических и реальных примеров. 3. В результате применения алгоритма «Кристалл» к эйлеровым решениям, рассчитанным по данным геомагнитных наблюдений, получены оценки направления вектора намагниченности геологических тел в районе массива Ахаггар (Алжир), согласующиеся с имеющимися геологическими данными и доставляющие новую информацию о строении региона. Построена прогнозная карта глубин кровли кристаллического фундамента для данного региона.
Практическая ценность работы
Созданный алгоритм «Кристалл» может применяться для решения широкого круга задач. В частности, он весьма эффективен при анализе и интерпретации геомагнитных данных. Сопоставление результатов вычислений с параметрами синтетических моделей показало, что алгоритм «Кристалл» в совокупности с методом деконволюции Эйлера позволяет уверенно определять как геометрические характеристики (положение в плане и по глубине) аномалообразующих объектов, так и параметры вектора намагниченности. Для устойчивого определения последних достаточно, чтобы расстояние между возмущающими объектами было не меньше глубины их залегания, т.е. метод демонстрирует хорошую разрешающую способность.
При работе с реальными геофизическими данными получены результаты,
допускающие новое геолого-геофизическое истолкование. В частности, впервые было
показано, что сходные в тектоническом отношении участки, входящие в состав массива
Ахаггар (Алжир), характеризуются общим для каждого из участков направлением
намагниченности пород. Фрагментам коры неопротерозойского возраста и вулканитам
периода панафриканского орогенеза соответствуют участки инверсной намагниченности,
тогда как для фрагментов архейского и палеопротерозойского возраста преимущественно
характерно прямое направление намагниченности. Для группы высокоамплитудных
изолированных магнитных аномалий в южной части массива получены устойчивые оценки
направления намагниченности, близкие к направлению современного магнитного поля
Земли, что позволяет сделать предположение о значительном вкладе индуктивной
намагниченности в поле этих объектов и делать дальнейшие предположения об их составе.
Построена прогнозная карта глубин кровли главной магнитоактивной поверхности
(кристаллического фундамента), согласующаяся с имеющимися геологическими данными
и дополняющая их.
Программный комплекс, реализующий алгоритм «Кристалл», имеет удобный и простой пользовательский интерфейс. Имеется возможность визуализации исходных данных и данных, полученных в результате работы алгоритма, в трех проекциях одновременно - хОу, yOz, xOz. В качестве исходных данных программа использует файл, предоставляемый пользователем, в котором содержится массив исходных точек. Основным требованием к файлу с исходными данными является наличие в нем трех столбцов с координатами точек (х, у, т). После обработки данных у пользователя, помимо визуализации результатов, есть возможность сохранения результатов в новом файле. В случае приложения к геофизическим данным, существует дополнительный модуль, входящий в разработанный программный комплекс, который позволяет рассчитывать статистические оценки для каждого из найденных сгущений. В результате работы данного модуля, полученные данные сохраняются в отдельном файле. Поскольку программный комплекс полностью реализован на языке Java, он может быть инкорпорирован в любой веб-сайт, что дает возможность пользователю обрабатывать имеющиеся у него данные в удаленном интерактивном режиме.
Доклады и публикации
Результаты работы регулярно докладывались на семинарах Центра исследования геофизических данных и сетевых технологий (ЦИГЕД) ИФЗ РАН. Всего по теме диссертации опубликовано 16 работ, включая статьи и тезисы докладов, сделанных на международных конференциях (в Киеве 24-25 апреля 2003, Таллинне 19-20 июня 2003, Москве 15-17 сентября 2003, Перми 24-29 января 2005 и др.). Кроме того, основные положения работы были доложены на международном семинаре «Распознавание образов и кластеризация в геофизических приложениях», проходившем в Институте физики Земли в Париже (Франция) 3-5 ноября 2004 г. Статья «Определение вектора магнитного моменгэ при помощи кластерного анализа результатов локальной линейной псевдоинверсии аномалий AT» (А.А. Соловьёв, Д.Ю. Шур, А.Д Гвишиани, В.О. Михайлов, С.А. Тихоцкий) представлена в журнал «Доклады РАН».
Структура и объем работы
Блок «Основа»
В блоке «Завершение» происходит идентификация окончательных стадий роста кристаллов X=K1u...uX/, I=I(a,5x(y),F).
В конце главы приведен сравнительный анализ алгоритма «Кристалл» и алгоритма кластеризации «Роден» [Mikhailov et al., 2003; Гвишиани и др., 2002а; Гвишиани и др., 20026] и даны иллюстрации работы обоих алгоритмов.
Поскольку программный комплекс, реализующий алгоритм «Кристалл», полностью выполнен на языке Java, он может быть с легкостью инкорпорирован в любой веб-сайт, что позволит пользователю обрабатывать имеющиеся у него данные в удаленном интерактивном режиме. Дело в том, что зачастую центры геофизических данных и исследователи, которым эти данные требуются для изучения и обработки, расположены друг от друга на большом расстоянии. При этом программные средства для обработки геофизических данных могут находиться совершенно в другом месте. В связи с этим, встает необходимость создания так называемых виртуальных лабораторий. Именно поэтому в настоящее время активно разрабатываются программные средства, обеспечивающие работу и позволяющие эффективно сотрудничать в таких лабораториях исследователям, людям, занимающимся сбором данных, а также разработчикам алгоритмов обработки данных, доступных в режиме удаленного запуска. В частности, для обеспечения работы виртуальной лаборатории, предоставляющей удаленный доступ к так называемому «телематическому алгоритмическому ресурсу», в который входит алгоритм «Кристалл», и позволяющей удаленно обрабатывать геофизические данные с помощью этих алгоритмов, была создана «Система Виртуального Присутствия» [Christein et al., 2002а,б; Soloviev, 2002а,б; Soloviev, 2003а,б; Соловьев и др., 2003; Soloviev et al., 2002]. Эта система была разработана и позволяла осуществлять совместный «браузинг» в Интернете в рамках европейского проекта WISTCIS («Продвижение новых методов работы Программы "Технологии Информационного Общества" в страны Содружества Независимых Государств») [Bonnin et al., 2003а,б; Kedrov et al., 2002]. Система создавалась совместно ЦИГЕД ИФЗ РАН, Ульмским университетом (Германия) и Ассоциацией EDNES (Франция). Основной ее целью является предоставление людям возможности «встречаться» на том или ином веб-сайте и общаться друг с другом, тем самым, объединяя группы людей по их интересам. В рамках проекта WISTCIS «Система Виртуального Присутствия» в основном использовалась с целью проведения международных виртуальных конференций. Подобная утилита является одним из основных инструментов при организации виртуальных лабораторий, являясь техническим средством для обеспечения связи и сотрудничества между учеными, работающими в одной и той же сфере, но находящимися на большом расстоянии друг от друга.
В главе сформулирована постановка геофизической задачи по приложению алгоритма «Кристалл» к анализу решений, полученных по методу деконволюции Эйлера (МДЭ). Этот известный в практике метод основан на аппроксимации измеренного аномального гравитационного или магнитного поля в скользящем «окне» полем некоторого элементарного источника однородной плотности или намагниченности, аномалия от которого является функцией Эйлера. Как известно, вещественнозначная функция f(x,y,z) в трехмерном координатном пространстве называется однородной функцией (функцией Эйлера) степени я, если для любого положительного / выполняется равенство f(tx,ty,tz) = t"f(x,y,z). В настоящей работе (x,y,z) - декартовы координаты, ось Oz направлена вертикально вниз, ось Ох - на север. Параметр N = -п принято называть структурным индексом. МДЭ позволяет получать оценки геометрических параметров элементарных аномалообразующих тел, используя значения аномальных потенциальных полей (гравитационного или магнитного) и их горизонтальных и вертикальных производных (измеренных или вычисленных). МДЭ можно применить к аномалиям, удовлетворяющим уравнению Эйлера, т.е. являющимся однородными функциями степени п. Можно показать, что этому уравнению удовлетворяют магнитные или гравитационные аномалии от тел, положение которых в пространстве определяется единственной точкой (x0,y0,z0) для трехмерного случая или (x0,z0) для двумерного случая. Такими телами являются точечный полюс или точечный диполь, а также линия полюсов или диполей. Отдельные элементарные тела удовлетворяют уравнению Эйлера при особых условиях: дайка (вертикальная или наклонная), если ее толщина существенно меньше ее глубины; конечный уступ, если его размер меньше глубины его верхней кромки и т.д. Для всех этих тел уравнение Эйлера может быть представлено в виде (x-x0) — + (y-y0) — + (z-zQ) — = N(A-f(x,y,z)), где (x0,yQ,z0) - координаты точки, характеризующей положение элементарного источника (эйлерово решение); (x,y,z) - координаты точки наблюдения, в которой заданы значения потенциального поля и его производных; А - постоянная, которую требуется определить. МДЭ заключается в определении четырех неизвестных параметров (x0,y0,z0) и А в скользящем «окне», содержащем более четырех точек, путем решения системы линейных уравнений. Система состоит из этих уравнений, выписанных для каждой точки (x,y,z) «окна». Таким образом, каждому «окну» соответствует одно найденное эйлерово решение.
После того как рассчитано положение эйлерового решения по магнитным аномалиям, могут быть рассчитаны параметры вектора намагниченности. Компоненты магнитного момента тх, ту, тг эквивалентного источника определяются из соотношения, определяющего поле AT диполя в точках «окна»: A?;= з г, \ г, ) где m - магнитный момент диполя, /j - радиус-вектор, направленный из точки наблюдения к диполю, //0 =47С-10"7 Гн/м - магнитная проницаемость вакуума.
Из этого выражения можно получить, как и при определении координат, переопределённую систему линейных уравнений с тремя неизвестными. Число уравнений равно числу точек в «окне». Из представления магнитного момента как трех величин ищутся модуль магнитного момента М, склонения D и наклонения /: м = J/w + /и„ + /я ; / = arcsin—-; D = arctan——. v у М mx
В результате обработки всей совокупности эйлеровых решений алгоритмом «Кристалл» выделяются плотные сгущения. Каждую точку, входящую в одно из найденных сгущений, можно считать оценкой положения некоторой особой точки объекта, например центра масс. Эти оценки искажены влиянием случайных факторов (погрешность наблюдений, влияние других объектов), поэтому они характеризуются некоторым разбросом. Согласно закону больших чисел средние величины координат эйлеровых точек, а также магнитного момента, склонения и наклонения будут более точными (обладающими меньшей дисперсией) оценками положения особых точек и свойств объекта. Расчет статистических оценок и мер неопределенности для этих оценок для каждого из сгущений, полученных в результате обработки эйлеровых решений алгоритмом «Кристалл», был проведен по следующим образом.
Для каждого К-го сгущения оценивались средние координаты и средний магнитный момент xf,yf,zf,М?, а также их среднеквадратическая погрешность. Кроме того, рассчитывались оценки средних углов, кучность векторов намагниченности и среднеквадратичные погрешности этих величин, а именно: для каждого из сгущений были рассмотрены единичные вектора у, в трехмерном пространстве с углами /, и Dt (і = l,...N). Затем для каждого сгущения был найден суммарный вектор J. Для этого рассчитывались составляющие по осям координат для суммарного вектора J:
Определение магнитного момента эквивалентных источников
Опыт работы с геофизическими массивами данных показывает, что большое значение имеют области повышенной плотности в них. В двумерном массиве X на рис.2 они выделены специальным образом. Сгущения, носящие изолированный характер, являются предметом кластерного анализа [Мандель, 1988; Миркин, 1980; Олдендерфер и др., 1989; Ту и др., 1978; Everitt, 1980; Эндрю, 1985; Хейс-Рог и др., 1987; Заде, 1980; Аверкин, 1998; Дуда и др., 1976; Тгуоп, 1939; Айвазян и др., 1989]. Сейчас же нас будет интересовать вопрос нахождения плотных областей в произвольном случае.
В настоящей работе предлагается дуальная стратегия присоединения сильнейших, наиболее плотных точек в X, своего рода кристаллизация в X (алгоритм «Кристалл»). Неформальная суть ее состоит в следующем: в качестве основы кристалла выбираются наиболее плотные точки в X (на рис.2 они помечены звездочками). Возьмем одну из них и обозначим через х . Затем устроим «борьбу» между х и ее дополнением Х-х за право обладания другой точкой у є Х-х Если основа кристалла х победила в некоторых точках из дополнения Х-х, то к ней присоединяется та из них, в которой эта победа была особенно убедительной. Обозначим ее через хь Так получается рост кристалла К от его начальной версии Ко к следующей версии Кі: Ко = {хо=х } - Ki = {хо, xi}
Далее за свои точки с первой версией кристалла Ki борется уже его дополнение Х-Кь И опять рост кристалла К произойдет благодаря присоединению к Ki точки xj, в которой победа Ki над К, = Х-К, будет наиболее убедительной: К,- Кг={К,,х2}. Если дополнение К, сохранило в борьбе с первой версией Ki кристалла К все свои точки, то рост К считается законченным и кристалл К полагается равным Kj: К = К\. Это и будет наиболее плотной в X частью, содержащей х . На следующих стадиях действует та же логика: кристалл К растет в своей n-ой версии К„, если в К„ существуют точки, в которых К„ побеждает Кв, и прекращает свой рост, останавливаясь на К„ в противном случае. Формализация кристаллизации будет выполнена на основе оптического подхода [Mikhailov et al., 2003; Гвишиани и др., 2002а; Гвишиани и др., 20026; Агаян и др., 2004; Soloviev et al., 2003а; Соловьев и др., 2005]: введенный в конечном метрическом пространстве X свет 6х(у) позволит придать точный смысл всем встречавшимся выше понятиям: плотность, борьба и победа.
Пусть X - конечное метрическое пространство с расстоянием d(x,y). Закон распространения света 5Х(-) от источника в точке хєХ является свободным параметром изложения и имеет различную математическую конструкцию. Функция 5х(у) моделирует близость в X точки у к точке х и может считаться нечеткой мерой принадлежности у к х. Таким образом, в общем случае 6х(у) не только убывает с ростом расстояния d(x,y), но и зависит от топологии X вокруг х.
Приведем несколько примеров. 1.2.1.1. Пример. С каждой на [0,оо) неотрицательной функцией "потенциального" типа 0 : (О) = !,# (/,) (/2),f, /2 связан свет S (y) (просто Sx(y))\ Sx(y) = P(d( y)) Vye О) В дальнейшем наиболее употребительна модель света Sx(y), ассоциированная с функцией (0 = V Также интересны модели: "круговой конус" дх и "гауссова шапочка" S", построенные по потенциалам pr(t) и (p"(f):
Пример. В силу неравенства треугольника между любыми "векторами" ху и xz в X определен угол ( ху , xz ) , косинус которого дается классической теоремой: 2d(x,y)d(x,z) Следовательно, в X существуют "полярные" координаты с центром в произвольной Л точке "х": если ху - направление "полярной" оси, z є X, то p(z) = d(x,y), p(z) = (ху, xz). С совокупным выбором таких направлений ср :Х -» X, х Ф ср{х) можно связать "дипольный" нормированный свет: ад= l + d(x,z) COS(JC (JC) , xz) 1.2.1.3. Обычная эксклюзивная максимальность: именно такие у є X говорят в пользу близости у к х в X: yX:d(x,y) d(x y)+l ш 1x1 1.2.1.4. Обозначим через X(x)=Ujf Cx(rf) - центрированное представление X вокруг х, def где С,(Г;) = {у еХ: d(x,y)=r;} - окружности радиусов ГІ, на которых располагаются точки в X относительно х, Г(х) = {0 гі гП(х)} - «группа нормирования» X в х. Перейдем от Х(х) к наиболее его адекватному одномерному выражению, а именно неотрицательному распределению масс на прямой: ГХ(х)={(гі,ті=С)[(гі))1" }.
Приводимые ниже меры бх(у) связаны с движением на рис.3 слева направо, начиная от нуля, расстояния d(x,y) сквозь распределение ГХ(х): 5х(у) - степень непроникновения d(x,y) в ГХ(х) (= 1 - степень глубины d(x,y) в ГХ(х)). Разное моделирование движения приводит к разным мерам.
Нам понадобится нечеткое сравнение n: R+xR+ -»[0,1] на неотрицательных числах а, b 0: n(a,b) - мера превосходства b над а со свойствами: n(0,b)=l,Vb, п(а,0) а 0, Va, n(a,b) Уг z а b, n(a,b) Уг О а Ь, n(a,b) = Уг = а = Ь. В качестве п мы возьмем , ,, b-a + max(a,b) n(a»b) = 1 гл 2max(a,b) 1.2.1.5. Движение в ГХ(х) через моменты М (у) и М (у). Положим для уєХ М+(у) = (S(d(x,y) - гдпц: г, d(x,y)), М-(у) = (Е(г; - d(x,y))mi: Гі d(x,y)). Моменты M (y) (М"(у)) можно считать доводом за максимальность (минимальность) d(x,y) в ГХ(х). Их нечеткое сравнение даст нужную меру: 5х(у) = п(М-(у),М+(у)).
Расчет аномального магнитного поля АГдля математического диполя
Алгоритм «Роден» призван искать кластеры в произвольном конечном метрическом пространстве. Он базируется на двух вещах - конструктивном определении кластера (17) и принципе высекания: понимая, что такое кластер заданного качества и заданной отделимости, «Роден» ищет его в исходном пространстве X, отсекая при этом от X все лишнее. Этим объясняется название алгоритма. Приступим к его описанию.
Сперва задаются характеристики высекаемого кластера: уровень качества а (1.2.3.1.) и уровень отделимости /? (18). Обозначим через Кп текущую версию кластера, получившуюся из пространства X после выбрасывания из него п точек (xt\":Kn = X-(х1+... + хп). Начальной версией К0 считается все пространство X:К0 =Х. Высекание из Кп точки xn+J может происходить по двум причинам: во-первых, по причине неудовлетворительного качества Р(Кп) а, и тогда хп+1 - слабейшая по качеству точка в Кп :xn+l =argminPAr (х); во-вторых, по причине неудовлетворительной отделимости Cl(Kn) fi, и тогда хп+1 слабейшая по отделимости точка в Kn :JC„+I = argmin ClK (х).
Глобальный "Роден" завершает работу при встрече первого кластера с заданными характеристиками. Вполне вероятно, что внутри него может быть еще один кластер более высокого качества а а 0- "Роден" найдет его (рис.27), если повысить начальный уровень качества до а и скорректировать /? - /3. Таким образом, настраивая "Роден" на тот или иной уровень характеристик, мы имеем возможность диагностировать (X, d) на предмет сгущений, получая при этом весь спектр существующих в X кластеров
Необходимость локального «Родена» имеет ту же причину, что и локального «Кристалла» (1.4.), а именно, размеры сгущений: обратимся к рис.28.
Пример необходимости применения локального «Родена». Безусловно, А - хороший в интуитивном понимании кластер, но благодаря своим большим размерам, его плотность Рл в отмеченной точке будет слабее внешнего света ЕА в ней, так что глобальный «Роден» не будет считать множество А кластером.
Чтобы исправить такое положение, мы должны во внутреннем освещении освободится от глобальных размеров А. Другими словами, конструкция внутреннего света должна носить локальный характер (1.4.1.). Так от глобальной кластеризации мы приходим к совокупности локальных кластеризации в шарах (рис.29). Результатом ее будет множество А в X, локально устроенное, как кластер, которое мы и будем называть локальным кластером.
Поиск локальных кластеров в X осуществляет локальный «Роден». 1.6.2. «Роден» и «Кристалл» «Роден» и «Кристалл» ищут в X подмножества К через определенные соотношения на производные от них функции Рк(0 Ек(-) и Рк(-): «Роден»: Рк (х) а л Рк (х) РЕК (х), Vx є К, (19) «Кристалл»: Рк(х) аРх(х) Рк(х) , af" / Pg(x),VxeK. (20) Но достигают эти алгоритмы своей цели по-разному: если К„ - текущее приближение для К, то в «Кристалле» к Кп точка добавляется, а в «Родене» вычитается: «Роден»: Kn+1 =Kn -xn+1,Kn+] =Kn +xn+1, «Кристалл»: Kn+1 = Kn +xn+1,Kn+1 = Kn -xn+1.
В этом заключается дуализм между «Роденом» и «Кристаллом». Приведем пример (рис.30; слева - результаты «Кристалла», справа - результаты «Родена»):
Формально «Роден» и «Кристалл» ищут разные К: если «Роден» имеет дело с абсолютной плотностью и отделимостью, то «Кристалл» - с относительной плотностью на общем фоне. Но реально (19) и (20) часто совпадают и поэтому работу алгоритмов можно сравнить.
По представленным рисункам необходимо сделать следующие выводы. Прежде всего, примеры показывают высокое качество работы обоих алгоритмов. При этом «Кристалл» отличает большая тщательность, способность целостной передачи сгущения, в частности, трассирование. Происходит это благодаря наличию в нем блока «Основы». С другой стороны, «Роден» более прост с вычислительной точки зрения.
Упомянутый выше дуализм «Родена» и «Кристалла» имеет теоретическое обоснование. Рассмотрим процесс кристаллизации с постоянной отделимостью (3: {х0} = К0сК]е... =Кп,РкДх1+1) ЗРкДх1+,Х ХІ+1ЄКІ, i = 0,...,n-l. Неспособность Кп оторвать у Кп точку хп+1 равносильно неравенству Р (х) Р 1Рк (x),VxeKn, то есть, так называемой квазикластерности Кп. Если р 1, то процесс кристаллизации {К; Я приведет к уплотнению Кп в виде квазикластера с обратной стороны.
Таким образом, «Кристалл» дает логику высекания, отличную от логики высекания «Родена». Примеры показывают, что она не может быть взята за основу в «Родене», уступает его более строгой и сбалансированной логике высекания и необходимо имеет предварительный характер: квазикластеры надо проверять на кластерность - в простых случаях (рис.38, Р = 0.23) они совпадают, в более сложных - нет (рис.39; Р = 0.85, 0.9, 0.95).
Определение глубин залегания верхних кромок возмущающих тел с помощью МДЭ и алгоритма «Кристалл». Интерпретация результатов
Предложенный метод обработки данных с помощью МДЭ в совокупности с алгоритмом «Кристалл» продемонстрировал высокую эффективность не только при работе с синтетическими примерами, но также и при работе с реальными геофизическими данными.
Удалось получить результаты, допускающие геологическое истолкование. В частности, впервые было показано, что сходные в тектоническом отношении участки, входящие в состав массива Ахаггар, характеризуются общим для каждого из участков направлением намагниченности пород. Фрагментам коры неопротерозойского возраста и вулканитам периода панафриканского орогенеза соответствуют участки инверсной намагниченности, тогда как для фрагментов архейского и палеопротерозойского возраста преимущественно характерно прямое направление намагниченности. Для группы высокоамплитудных изолированных магнитных аномалий в южной части площади получены устойчивые оценки направления намагниченности, близкие к направлению современного МПЗ, что позволяет сделать предположение о значительном вкладе индуктивной намагниченности в поле этих объектов и делать дальнейшие предположения об их составе.
Построена прогнозная карта глубин кровли кристаллического фундамента, также согласующаяся с имеющимися геологическими данными и дополняющая их.
Опыт работы с массивами геофизических данных показывает, что часто большое значение в них имеют области повышенной плотности. Именно выделению таких подмножеств и посвящен алгоритм «Кристалл». Его можно считать посткластеризационным, поскольку алгоритмы классического кластерного анализа ориентированы на кластерность -одновременное сочетание повышенной плотности и отделимости, в то время как «Кристалл» решает более трудную задачу, связанную только с первым свойством. Это обстоятельство потребовало формального определения плотности в конечном метрическом пространстве. Она служит базой первой половины «Кристалла» - выбора основ кристаллизации - наиболее плотных точек в массиве, вокруг которых он группируется сильнее всего. Произвольное плотное подмножество не всегда обязательно состоит из основ. Полное его исчерпывание (заполнение) получается при помощи второй половины алгоритма, а именно кристаллизацией вокруг основ. Формальным фундаментом «Кристалла» является нечеткая мера близости в исходном массиве (пространстве). Именно она дает возможность придать точный смысл понятиям «плотность», «основа», «кристаллизация».
Таким образом, можно сделать следующие выводы:
1. Алгоритм «Кристалл» предназначен для выделения областей повышенной плотности в многомерных массивах данных. Его можно считать посткластеризационным, поскольку алгоритмы классического кластерного анализа ориентированы на кластерность - одновременное сочетание повышенной плотности и отделимости. В то время как «Кристалл» решает задачу, связанную только с первым свойством.
2. «Кристалл» имеет две фазы: «Выбор основ» и «Кристаллизация». В первой из них ищутся основы кристаллизации - наиболее плотные точки в исходном массиве, вокруг которых он группируется сильнее всего. Произвольное плотное подмножество не всегда обязано состоять только из основ. Полное его заполнение происходит во время второй фазы, а именно кристаллизация вокруг основ.
3. Формальным фундаментом «Кристалла» является нечеткая мера близости в исходном массиве. Именно она дает возможность придать точный смысл понятиям, участвующим в «Кристалле»: плотность на общем фоне, основа, кристаллизация.
В рамках геофизических приложений, сопоставление результатов обработки синтетических геомагнитных данных с параметрами моделей показывает, что метод деконволюции Эйлера в совокупности с алгоритмом «Кристалл» позволяет уверенно определять как геометрические характеристики аномалеобразующих тел (положение в плане и по глубине), так и модули направления вектора магнитного момента. Это, в частности, справедливо для случая, когда расстояние между возмущающими диполями равно глубине их залегания, то есть метод демонстрирует высокую разрешающую способность.
Успешные результаты, которые были получены при приложении алгоритма к синтетическим магнитным данным, свидетельствуют о том, что алгоритм «Кристалл» работает корректно в рамках классификации геомагнитных данных и может в дальнейшем быть использован для анализа реальных магнитных данных. Подчеркнем, что в частности нами были выполнены исследования при параметрах нормального поля, отвечающих нормальному полю района массива Ахаггар (Алжир), также исследуемого в работе.
Предложенный метод обработки данных с помощью метода деконволюции Эйлера в совокупности с алгоритмом «Кристалл» продемонстрировал высокую эффективность не только при работе с синтетическими примерами, но также и при работе с реальными геофизическими данными (массив Ахаггар, Алжир). Удалось получить результаты, допускающие геологическое истолкование. В частности, впервые было показано, что сходные в тектоническом отношении участки, входящие в состав массива Ахаггар, характеризуются общим для каждого из участков направлением намагниченности пород. Фрагментам коры неопротерозойского возраста и вулканитам периода панафриканского орогенеза соответствуют участки инверсной намагниченности, тогда как для фрагментов архейского и палеопротерозойского возраста преимущественно характерно прямое направление намагниченности. Для группы высокоамплитудных изолированных магнитных аномалий в южной части площади получены устойчивые оценки направления намагниченности, близкие к направлению современного магнитного поля Земли, что позволяет сделать предположение о значительном вкладе индуктивной намагниченности в поле этих объектов и делать дальнейшие предположения об их составе.
Благодаря предложенному методу для района массива Ахаггар (Алжир) построена прогнозная карта глубин кровли кристаллического фундамента, также согласующаяся с имеющимися геологическими данными и дополняющая их.
