Содержание к диссертации
Введение
Глава 1. Обзор методов моделирования и исследования многомерных данных 12
1.1 Особенности предмета исследования и область применения 12
1.2 Обзор методов восстановления пропущенных значений в многомерных данных 14
1.2.1 Классические методы восстановления пропущенных значений 14
1.2.2 Неклассические методы восстановления пропущенных значений 21
1.3 Численные и статистические методы анализа многомерных данных 27
1.4 Методы классификации многомерных данных 34
1.5 Пространственный анализ данных с применением геоинформационных систем 36
1.6 Программно-инструментальные средства анализа многомерных данных 38
1.7 Постановка задач диссертационных исследований 41
Глава 2. Разработка методики комплексного анализа многомерных данных 42
2.1 Схема проведения комплексного анализа многомерных данных 42
2.2 Алгоритмическое обеспечение 43
2.2.1 Алгоритмы нечеткого моделирования 43
2.2.2 Алгоритм восстановления данных 63
2.2.3 Алгоритм факторного анализа с вращением 65
2.2.4 Алгоритм классификации многомерных данных 68
2.3 Методические вопросы пространственного анализа данных с применением ГИС 69
Выводы по главе 2 71
Глава 3. Программная реализация разработанной методики 72
3.1 Выбор средства реализации 72
3.2 Архитектура программного комплекса 72
3.3 Визуальная часть программного комплекса 74
3.3.1 Блок "Моделирование" 75
3.3.2 Блок "Восстановление данных" 81
3.3.3 Блок "Анализ данных" 83
Выводы по главе 3 87
Глава 4. Практическое применение результатов диссертационного исследования 88
4.1 Исследование адекватности результатов моделирования 88
4.2 Анализ точности алгоритмов восстановления пропущенных значений 93
4.3 Комплексный анализ многомерных данных о микробиологических и физико-химических свойствах нефти 95
Заключение 106
Список литературы 109
- Классические методы восстановления пропущенных значений
- Пространственный анализ данных с применением геоинформационных систем
- Алгоритм восстановления данных
- Визуальная часть программного комплекса
Введение к работе
Актуальность работы. Научно-исследовательская деятельность сопряжена с обработкой постоянно увеличивающегося массива разрозненной совокупной информации об объектах исследования. Аналитические процессы предполагают обработку огромного количества материалов и включают такие трудоемкие процессы как систематизация, выявление каких-либо закономерностей, преобразование данных для последующего математического моделирования. Модели данных – это важнейшая составляющая для анализа, так как то, насколько полно и детально модель может представить предметную область и ее явления, в значительной степени определяет функциональные возможности создаваемой системы. Однако построение модели и последующего анализа осложняется проблемой неточного или неполного описания изучаемых объектов. Одним из подходов к решению данной проблемы является применение методов статистического и нечеткого моделирования.
Нечеткое моделирование используется при построении сложных моделей, когда трудно сформировать аналитическую модель объекта, когда модель слишком сложна, или когда имеется неполнота экспертных данных для статистического моделирования. Нечеткие системы (НС) применяются в таких проблемных областях науки и техники как прогнозирование, распознавание образов, автоматическое управление, системы принятия решений, робототехника. Преимуществами НС является невысокая стоимость разработки, гибкость, интуитивно понятная логика функционирования.
Важным моментом, решаемым в процессе построения НС, является идентификация ее параметров. Актуальной является задача повышения точности вывода НС на реальных данных. Для настройки параметров НС используются различные методы оптимизации, наряду с методами, основанными на производных, применяются генетические алгоритмы, эволюционные стратегии и нейронные сети. Эволюционные стратегии совместно с эволюционным программированием и генетический алгоритм представляют три главных направления развития эволюционного моделирования. Несмотря на то, что каждый из методов возник независимо от других, они характеризуются рядом общих свойств. Для любого из них формируется исходная популяция, которая подвергается селекции и воздействию различных генетических операторов, что позволяет находить лучшие решения. Построение алгоритмов на основе метода эволюционной стратегии основываются на трудах Ingo Rechenberg, Hans-Paul Schwefel, H.-G. Beyer, J, Klockgether, S, Kern, A.Auger, Д. Рутковской, S.L. Luke, N. Hansen, A. Ostermeir, а алгоритмы нечеткого моделирования на работах А.Н. Аверкина, И.А. Ходашинского, И.З. Батыршина, Л.С. Берштейна, Л.Г. Комар-цовой, А.В. Язенина, Н.Г., Ярушкиной, P.H. Ishibuchi,n, R.R. Yager, T.Yasukawa, L.-X. Wang, L. Zadeh, H. Bahrami, M. Abdechiri, M.R. Meybodi, Y. Zhang, X. Wu, Z. Xing, W. Hu.
Ввиду многомерности изучаемых данных для проведения анализа появляется потребность в их более компактном описании, то есть в сжатии информа-3
ции до более важных характеристик. Факторный анализ (ФА) позволяет учитывать эффект существенной многомерности данных и дает возможность более простого, лаконичного объяснения многомерной структуры. Сжатие информации получается за счет того, что число факторов значительно меньше, чем было исходных параметров. Отсюда основными целями ФА является понижение числа используемых переменных и наглядная визуализация полученных данных.
При исследовании природных объектов, таких как нефть, для повышения наглядности результатов и помощи в их интерпретации требуют включения в анализ пространственных свойств объектов исследования – географические координаты, глубина залегания и др. Для учета и анализа пространственных данных применяются геоинформационные системы (ГИС), позволяющие визуализировать большие объемы информации с пространственными свойствами, включая связанную с ними количественную информацию об объектах.
Выявленные особенности широкого класса природных объектов требуют комплексного подхода к анализу. Комплексность понимается как возможность проведения исследований многомерных неполных данных на основе сочетания методов нечеткого моделирования и многомерного статистического анализа с целью восстановления пропущенных значений, проведения анализа структуры данных, выявления скрытых взаимосвязей между свойствами, а также исследования пространственных свойств объектов, отображая результаты анализа средствами ГИС в едином комплексе программ.
В настоящее время методические вопросы комплексного анализа многомерных данных о природных объектах, решающие одновременно вопросы восстановления неполных данных, редукции исходных данных, выявления значимых характеристик объектов исследования, а так же визуализации с географической привязкой, разработаны недостаточно. В связи с этим возникла необходимость разработки новой методики, основанной на сочетании методов нечеткого и статистического моделирования.
Объект исследования – природные пространственно-распределенные объекты, например нефти, для описания свойств которых используются многомерные массивы данных.
Предмет исследования – комплекс алгоритмов и программ определения зависимостей между различными свойствами природных объектов (например, между физическими, химическими и пространственными свойствами).
Цель работы – разработка алгоритмов и комплекса программ анализа многомерных данных о различных свойствах природных объектов, основанных на сочетании методов нечеткого моделирования, многомерного статистического анализа и методов пространственного анализа с применением геоинформационных систем.
Задачи исследования:
-
Анализ предметной области и обзор существующих решений в области комплексного анализа многомерных неполных данных.
-
Разработка методики проведения комплексного анализа многомерных неполных данных с применением нечеткого и статистического моделирования.
-
Разработка алгоритмов комплексного анализа многомерных неполных данных.
-
Проведение исследований разработанных алгоритмов на типовых контрольных примерах и тестовых выборках.
-
Проектирование и разработка программного комплекса.
-
Применение и внедрение программного комплекса анализа многомерных неполных данных.
Методы исследований: методы нечеткого моделирования, нечетких множеств, математической статистики, линейной алгебры, метод факторного анализа, численные методы, метод кластеризации, методы пространственного анализа средствами ГИС, методы объектно-ориентированного программирования.
Достоверность результатов обеспечивается строгостью применения математических методов, результатами проведенных численных экспериментов, которые сопоставлены с данными, полученными другими авторами.
Научная новизна. В диссертационной работе получены следующие новые научные результаты:
-
Предложена методика проведения комплексного анализа многомерных данных о природных пространственно-распределенных объектах, обеспечивающая выявление новых закономерностей между свойствами исследуемых объектов.
-
Модифицированный алгоритм идентификации нечеткой системы с заданной структурой, включающий генерацию структуры НС с заданными параметрами функции принадлежности и оптимизацию параметров НС, основанную на методе эволюционной стратегии и методе наименьших квадратов.
-
Впервые разработан алгоритм восстановления пропущенных значений, основанный на разработанном модифицированном алгоритме идентификации нечеткой системы, отличающийся от известных алгоритмов и статистических методов снятием требований к знанию закона распределения.
Практическая ценность.
Созданный программный комплекс внедрен в ИХН СО РАН и применялся при выполнении Бюджетного проекта V.39.3.1. Исследование физико-химических свойств гетерогенных нефтесодержащих систем и их структурной организации на микро- и наноуровне с целью развития научных основ экологически безопасных технологий извлечения вязких парафинистых нефтей по теме «Разработка методических вопросов восстановления пропущенных значений в выборочном массиве из базы данных по свойствам вязких парафинистых нефтей с использованием методов вероятностного моделирования и кластерного анализа данных» и проекта РФФИ 11-05-98023 «Исследование влияния химического состава и условий залегания нефтей на численность, распространение и активность пластовой микрофлоры для повышения нефтеотдачи».
Разработанный программный комплекс внедрен в Федеральном государственном бюджетном учреждении науки Институте мониторинга климатических и экологических систем Сибирского отделения Российской академии наук (ИМКЭС СО РАН) и используется в рамках выполнения работ по программе интеграционного проекта № 70 Сибирского отделения РАН «Анализ и прогноз
проявлений вынуждающего воздействия в ритмике метеорологических полей Северного полушария Земли» для анализа разнородной междисциплинарной информации о состоянии и изменениях климатообразующих параметров исследуемых территорий.
Разработанные алгоритмы и программный комплекс используются при выполнении научно-исследовательских работ (задание № 2014/225) в рамках базовой части государственного задания Минобрнауки России для проведения комплексного анализа многомерных характеристик, описывающих процесс принятия решений в производственно-экономических и социальных системах, для решения задач определения границ объектов территориального устройства на основе многомерных данных об инфраструктурной среде и социально-экономических характеристиках в условиях нормативных ограничений.
Алгоритмы блока «Анализ данных» программного комплекса используются в учебном процессе при проведении лабораторных работ по дисциплине «Качество программных систем» на кафедре АОИ ТУСУР, являясь инструментом анализа показателей качества программных систем.
Апробация работы. Основные положения работы докладывались на научных конференциях различного уровня. На VII и VIII международных конференциях "Химии нефти и газа" г. Томск, 2009, 2012 г.; на VII всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии», г. Томск, 2009 г.; на IV Всероссийской конференции молодых ученых «Материаловедение, технологии и экология в 3-м тысячелетии», г. Томск, 2009 г.; на IX всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии», г. Томск, 2011 г.; на XVIII Международной научно-практической конференции студентов, аспирантов и молодых ученых "Современные техника и технологии", г. Томск, 2012 г.; на III Всероссийской молодежной научной конференции «Современные проблемы математики и механики», г. Томск, 2012 г.; на Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР», г. Томск, 2010, 2011, 2012 г, так же опубликованы работы в сборнике «Доклады ТУСУР» (г. Томск, 2013 г.), в журнале «Информационные технологии» (г. Москва, 2013-2014 г.).
Защищаемые положения:
1. Методика проведения комплексного анализа многомерных данных о
природных пространственно-распределенных объектах, обеспечивающая выяв
ление новых закономерностей между свойствами исследуемых объектов.
Соответствуют пункту 5 паспорта специальности: Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента .
2. Модифицированный алгоритм идентификации нечеткой системы с за
данной структурой, включающий генерацию структуры НС с заданными пара
метрами функции принадлежности и оптимизацию параметров НС, основанную
на методе эволюционной стратегии и методе наименьших квадратов. Модель
позволяет детально учитывать структуру входных данных объекта моделирования, снимая требования к знанию закона распределения.
3. Алгоритм восстановления пропущенных значений на основе модифици
рованного алгоритма идентификации НС с заданной структурой позволяет уве
личить точность восстановления пропущенных значений по сравнению с алго
ритмами, предлагаемыми другими авторами как минимум в 1,5 раза на тесто
вых данных.
Соответствуют пункту 1 и 3 паспорта специальности: 1)Разработка новых математических методов моделирования объектов и явлений. 3)Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.
4. Программный комплекс анализа многомерных неполных данных о при
родных объектах, позволяющий выявлять существующие закономерности
между различными свойствами исследуемых объектов.
Соответствует пункту 4 паспорта специальности: Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.
Личный вклад соискателя. Постановка задачи, а также подготовка материалов к печати велась совместно с научным руководителем. Все основные результаты диссертации получены лично автором. Автор самостоятельно разработал алгоритмы и программный комплекс для проведения комплексного анализа многомерных неполных данных.
Публикации. Основные положения диссертации отражены в 19 опубликованных работах. В том числе 5 статей напечатаны в ведущих рецензируемых научных журналах и изданиях РФ, в которых ВАК рекомендует публикацию основных результатов диссертационных работ, и получено 1 свидетельство об официальной регистрации программы для ЭВМ (свидетельство № 2013619931 от 21.10.2013 г.).
Структура и объем работы. Диссертация состоит из введения, основной части, включающей в себя четыре главы, заключения, списка используемой литературы из 113 источников, 5 приложений. Объем диссертационной работы состовляет 122 страницы. Работа иллюстрируется 33 рисунками и 24 таблицами.
Классические методы восстановления пропущенных значений
Рассмотрим алгоритмы импутирования (заполнения пропусков в данных) по группам [3]: Простые алгоритмы – неитеративные алгоритмы, основанные на простых арифметических операциях, расстояниях между объектами, регрессионном моделировании. К ним относятся заполнение пропусков средним арифметическим, регрессионное моделирование пропусков, метод ближайших соседей и метод подбора в группе. Сложные алгоритмы – итеративные алгоритмы, предполагающие оптимизацию некоторого функционала, отражающего точность расчета подставляемых на место пропуска значений. Их можно разделить на глобальные и локальные методы. Глобальные алгоритмы – алгоритмы, предусматривающие, что в оценивании (предсказании) каждого пропущенного значения участвуют все объекты рассматриваемой совокупности: метод Бартлетта, ЕМ - оценивание и метод главных компонент (МГК).
Локальные алгоритмы – алгоритмы, в которых для оценивания (предсказания) каждого пропущенного значения участвуют полные наблюдения, находящиеся в некоторой окрестности предсказываемого объекта. К данной группе относятся алгоритмы множественного импутирования, Zet и ZetBraid.
Кратко рассмотрим методы импутирования входящие в состав перечисленных групп (в порядке исследования).
Метод (безусловного) среднего, предполагает, что все пропущенные значения заменяются средним значением данного признака. Самый простой, но не самый точный метод заполнения пропусков в данных [3,4].
Регрессионные модели. Термин "регрессия" [5] был введен Ф. Гальтоном в конце 19 века. Гальтон обнаружил, что дети родителей с высоким/низким ростом обычно не наследуют выдающийся рост и назвал этот феномен "регрессия к посредственности". Сначала этот термин использовался исключительно в биологическом смысле. После работ К. Пирсона этот термин стали использовать и в статистике. В статистической литературе различают регрессию с участием одной свободной переменной и с несколькими свободными переменными — одномерную и многомерную регрессию. Также различают линейную и нелинейную регрессию. Если регрессионная модель не является линейной комбинацией функций от параметров, то говорят о нелинейной регрессии. При этом модель может быть произвольной суперпозицией функций g из некоторого набора. Нелинейными моделями являются: экспоненциальные, тригонометрические и другие (например, радиальные базисные функции или персептрон Розенблатта), полагающие зависимость между параметрами и зависимой переменной нелинейной. Еще различают параметрическую и непараметрическую регрессию. Строгую границу между этими двумя типами регрессий провести сложно. Сейчас не существует общепринятого критерия отличия одного типа моделей от другого. Например, считается, что линейные модели являются параметрическими, а модели, включающие усреднение зависимой переменной по пространству свободной переменной - непараметрическими.
В большинстве случаев, регрессионные модели в задаче импутирования осуществляются в два этапа [3]:
1. На первом этапе по совокупности полных наблюдений отстраивается регрессионная модель, и оцениваются коэффициенты в уравнении, где в качестве зависимой переменной выступает целевая переменная, пропущенные значения по которой необходимо восстановить;
2. По полученному на предыдущем этапе уравнению, в которое подставляются известные значения независимых переменных предикторов, для каждого целевого объекта рассчитывается отсутствующее значение по зависимой целевой переменной. В случае интервальных и абсолютных переменных рассчитывается конкретное значение, а для порядковых и номинальных переменных с некоторой вероятностью предсказывается категория, к которой должен быть отнесен объект.
Выбор регрессионной модели для расчета пропущенных значений переменной определяется уровнем измерения целевой зависимой переменной (значения которой необходимо восстановить) и независимых переменных, по которым будут предсказываться отсутствующие значения.
Например, метод многомерной регрессии строит модель линейной зависимости переменной, в которой необходимо заполнить пропуски от ряда других имеющихся признаков. Регрессионные коэффициенты для каждого из предикторов находятся методом наименьших квадратов на массиве с полными данными, который был сформулирован еще в 1794 -1795 годах немецким математиком И.К. Гауссом (1777-1855). При подстановке значения предикторов в регрессионное уравнение получим прогноз пропущенного показателя.
Проблема применения этого метода заключается в том, что у некоторых случаев могут быть пропущены не только значения переменной, которую необходимо предсказать с помощью регрессии, но и значения предикторов, тогда предсказание непосредственно на основе коэффициентов уравнения оказывается невозможным. Сложность применения данного метода еще и в том, что исследователь должен выбрать переменные, которые коррелируют [6] с рабочей переменной и хорошо объясняют ее вариацию. В массиве может просто не оказаться достаточного количества предикторов. Наконец, предсказанные значения не содержат остатков, характерных для любых данных. И, например, метод кусочно-линейной регрессии используется как методика восстановления данных при анализе технологических индексов мустьерских комплексов Средней Азии, который проводили Ю.П. Холюшкин и Г.Ю. Жилицкая в 1998 году [7].
Метод главных компонент (изобретен К. Пирсоном в 1901г.). Пусть задана таблица с пропусками A=(aij). Ставится задача поиска наилучшего приближения A матрицей вида xiyj+bj методом наименьших квадратов. Для данной матрицы A ищем наилучшее приближение матрицей P1 вида xiyj+bj. Далее, для A–P1 ищем наилучшее приближение этого же вида P2 и т.д. В результате строится последовательность матриц Pq вида xiyj+bj ( ), исчерпывающая исходную матрицу A с заданной точностью. Если пробелы отсутствуют, то описанный метод приводит к обычным главным компонентам – сингулярному разложению исходной таблицы данных. Также следует учесть, что при отсутствии пробелов, полученные прямые будут ортогональны. Исходя из этого, при неполных данных возможен процесс ортогонализации полученной системы факторов. Процесс заключается в том, что исходная таблица восстанавливается при помощи полученной системы, после чего эта система пересчитывается заново, но уже на полных данных [3].
Метод Бартлетта - алгоритм импутирования, предложенный М.С. Бартлеттом (1937г), заключается в подстановке начальных значений вместо пропусков и проведении ковариационного анализа, то есть метод включает два этапа: 1. Вместо пропусков выполняется подстановка начальных значений. 2. Проводится ковариационный анализ целевой переменной и дихотомического индикатора полноты наблюдения по целевой переменной.
Метод Бартлетта имеет следующие преимущества: он не итеративный и, следовательно, снимает вопрос о сходимости. Если структура пропусков обладает вырожденностью (ситуация, когда нельзя оценить некоторые параметры при отсутствии всех значений для какой-то обработки), то метод предупреждает исследователя об этом. Кроме того, метод дает правильные оценки и остаточные суммы квадратов, а также верные стандартные ошибки, суммы квадратов и критерии Фишера [3].
Алгоритм ближайшего соседа был изобретён в 1950 годах математиком Г. Штейнгаузом. В основе лежит предположение, что если объекты близки по значениям n-1 свойств, то они близки по значению n-го свойства. Заполнение пропусков в таблице данных методом ближайших соседей выглядит следующим образом: среди всех строк таблицы (объектов) находят k-строк, наиболее "похожих" на строку, содержащую пробел. В качестве меры "похожести" строк фигурирует декартово расстояние между строками в пространстве столбцов (свойств). Чем меньше декартово расстояние между объектами в пространстве свойств, тем более они "похожи" друг на друга. Столбец, содержащий предсказываемое значение принято называть целевым столбцом. Для получения предсказания неизвестного элемента значения целевого свойства у k-ближайших соседей усредняются с весами, обратно пропорциональными их декартовому расстоянию до строки, содержащей пробел [3].
Метод подбора внутри групп предполагает, что вся совокупность объектов разбивается на группы по определенному признаку, внутри каждой группы для заполнения пропусков используются только присутствующие в ней значения.
Методы подбора используются в одномоментных исследованиях, и представляют собой подстановку вместо пропуска значения по данной переменной у наиболее близкого объекта с полной информацией. Причем подбор может осуществляться как из всей совокупности полных наблюдений, так из ее некоторой подгруппы – кластера, к которому принадлежит целевой объект. Тип функции расстояния для определения наблюдения выбирается исходя из типа используемых данных, представлений исследователя о характере связи между переменными и задач каждого конкретного исследования [3].
Zet - метод. Данный метод широко представлен Н.Г. Загоруйко в 1975 году. Суть метода заключается в подборе для каждого пропуска импутируемого значения не из всей совокупности полных наблюдений, а из некоторой ее части, называемой компетентной матрицей (рис. 1.1). Данная матрица состоит из компетентных строк и столбцов.
Пространственный анализ данных с применением геоинформационных систем
Факторный анализ (ФА) основан на представлении о комплексном характере изучаемых объектов, выражающемся, в частности, во взаимосвязях и взаимообусловленности их отдельных признаков. Особое внимание в ФА уделяется исследованию внутренних причин, формирующих специфику изучаемых объектов. ФА не требует априорного разделения признаков на зависимые и независимые – все признаки рассматриваются как равноправные. Цель ФА – выразить большое число анализируемых признаков через меньшее число более емких внутренних характеристик объекта исследования, которые могут не поддаваться непосредственному измерению. При этом предполагается, что наиболее емкие характеристики окажутся наиболее существенными, значимыми.
ФА основан на многомерном нормальном распределении – каждый из используемых признаков изучаемого объекта должен иметь нормальный закон распределения. ФА исследует внутреннюю структуру ковариационной и корреляционной матриц системы признаков изучаемого объекта [42]. Рассмотрим его подробнее.
Пусть в изучаемом объекте отобрано N записей. В каждой из них измерены значения K параметров и получены значения случайных многомерных нормально распределенных величин. Эти значения случайных многомерных величин обусловлены различными причинами, которые называются факторами. Предполагается, что число этих факторов всегда меньше, чем число K измеряемых параметров изучаемого объекта. Эти факторы являются скрытыми, их нельзя непосредственно измерить и поэтому они представляются гипотетическими. Однако имеются методы их выявления, которые и составляют сущность факторного анализа.
В факторном анализе решаются следующие задачи [39 - 44, 78 - 82]: 1. Определение количества действующих факторов и указание относительной ёмкости. 2. Выявление признаковой структуры факторов – рассмотрение, какими признаками объекта обусловлено действие того или иного фактора и в какой относительной мере. 3. Выявление факторной структуры изучаемых параметров объекта – анализ доли влияния каждого из факторов на значение того или иного параметра этого объекта. 4. Воссоздание в факторном координатном пространстве облика изучаемого объекта, с помощью использования вычисляемых значений факторов для каждого наблюдения исходной выборочной совокупности.
В основе ФА лежит математический метод нахождения собственных значений и собственных векторов корреляционной матрицы [53], для нахождения которых используются различные численные методы работы с матрицами. Рассмотрим наиболее популярные методы:
1. Разложение Холецкого [84, 85] – это представление симметричной положительно-определённой матрицы в виде , где - нижняя треугольная матрица со строго положительными элементами на диагонали. Разложение Холецкого всегда существует и единственно для любой симметричной положительно-определенной матрицы. Существует также обобщение этого разложения на случай комплекснозначных матриц. Если матрица - положительно-определенная эрмитова матрица, то существует разложение , где - нижняя треугольная матрица с положительными действительными элементами на диагонали, а - эрмитово-сопряженная к ней матрица.
Алгоритм разложения Холецкого: Элементы матрицы можно вычислить, начиная с верхнего левого угла, по формулам: Выражение под корнем всегда положительно: если - действительная положительно-определенная матрица, то вычисление происходит сверху вниз, слева направо (вначале , а затем ). Для комплекснозначных эрмитовых матриц используются формулы: Данный метод используется для решения системы линейных уравнений, так как он обладает численной устойчивостью и небольшим числом арифметических операций. 2. LU-разложение [85, 86] – это представление матрицы в виде произведения двух матриц , где - нижняя треугольная матрица, а - верхняя треугольная матрица. Данное разложение используется для вычисления определителя матрицы.
Для улучшения решения ФА, то есть для более четкого выявления структуры факторов, необходима процедура вращения, которая позволит сделать окончательное решение ФА наиболее адаптированными к области исследуемых данных и обеспечит возможность легче интерпретировать полученную факторную структуру.
Для процедуры вращения был выбран наиболее часто используемый на практике метод "Варимакс" [79], в котором для каждого признака добиваются того, чтобы дисперсия квадратов нагрузок факторов была максимальна.
В разделе 1.4 были представлены различные методы классификации, из которых был выбран метод k-средней кластеризации, так как он относится к последовательным алгоритмам, а значит хорошо подходит для классификации большого числа объектов. Рассмотрим подробнее данный метод.
Основная идея метода k-средних [87, 88] заключается в том, что он последовательно уточняет эталонные точки и стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров: где k - число кластеров, Si - полученные кластеры, и - центр масс элементов , которому на j-ой итерации приписался элемент xj.
Методические вопросы пространственного анализа данных с применением ГИС В разделе 1.1 были описаны характерные особенности анализируемых объектов исследования, отличительным свойством которых было наличие пространственных характеристик у объектов. Для учета пространственных характеристик было предложено (п. 1.5) использовать экспортирование результатов предыдущих этапов комплексного анализа в ГИС для проведения пространственного анализа.
Схема проведения пространственного анализа в ГИС предполагает проведение визуального анализа объектов в пространстве выбранных факторов, согласно результатам классификации (рис. 2.10).
Пространственный анализ результатов комплексного анализа средствами ГИС позволяют выявить закономерности, связанные с взаиморасположением объектов на цифровых картах. Это необходимо, когда проводится анализ значительного количества объектов, и отображение результатов в пространстве выбранных факторов не позволяет оценить значимость отличительных особенностей между ними, согласно их географическому расположению (рис. 2.11).
Для проведения пространственного анализа в ГИС используется процедура сохранения результатов классификации в дополнительный столбец "CLASS", то есть создается выходная таблица вида "объект-свойство", состоящая из исходных данных и дополнительного столбца результата классификации данных.
Пространственный анализ полученных классов объектов проводится средствами ArcGis 9.3.1 с применением легенды "цветовая шкала" или "градуированный символ", где все классы объектов отображаются различным цветом и формой. Проведение формализованного пространственного анализа требуется для выявления пространственных особенностей объектов различных классов, также установить закономерности в их распределении по классам.
В результате решения методических и алгоритмических вопросов комплексного анализа многомерных неполных данных о природных объектах на основе методов нечеткого и статистического моделирования, получен ряд новых научных результатов, основными из которых являются следующие: ь разработана методика проведения комплексного анализа многомерных данных о природных пространственно-распределенных объектах, обеспечивающая выявление новых закономерностей между свойствами исследуемых объектов. ь представлен модифицированный алгоритм идентификации нечеткой системы с заданной структурой, включающий генерацию структуры НС с заданными параметрами функции принадлежности и оптимизацию параметров НС, основанную на методе эволюционной стратегии и методе наименьших квадратов. ь представлен алгоритм восстановления пропущенных значений, основанный на разработанном модифицированном алгоритме идентификации нечеткой системы, отличающийся от известных алгоритмов и статистических методов снятием требований к знанию закона распределения.
Алгоритм восстановления данных
Разработанный в диссертации комплексный подход к анализу многомерных данных о природных объектах был применен в рамках работ по проекту РФФИ 11-05-98023 "Исследование влияния химического состава и условий залегания нефтей на численность, распространение и активность пластовой микрофлоры для повышения нефтеотдачи".
Нефть является одним из основных энергетических и химических сырьевых ресурсов. Однако по некоторым прогнозам мировые запасы "легкой" нефти могут быть исчерпаны уже в течение ближайших 50 лет. В связи с этим в настоящее время заметно возрос интерес к поиску путей и средств повышения нефтедобычи и извлечения трудноизвлекаемой нефти, и особое внимание уделяется физико-химическим и микробиологическим методам. Практическое применение биотехнологии позволяет на 5 - 7 % увеличить вовлекаемые в разработку запасы, в 1.5 - 2 раза повысить продуктивность скважин, а текущую добычу нефти - на 15 - 25 %.
Объектами исследований являлись нефти России, Монголии, Китая, Вьетнама и пластовые воды залежей. Для проведения анализа в научно-исследовательском информационном центре ИХН СО РАН был сформирован многомерный массив данных о физико-химических свойствах нефти, в лаборатории коллоидной химии СО РАН сформирован многомерный массив данных о микробиологических свойствах пластовых вод (табл. 4.12).
Анализ и подготовка данных Первоначальный анализ многомерного массива [93] данных о свойствах нефти и пластовой воды (включающий 18 образцов, табл. 4.12) показал, что из 234 значений пропущено 19 значений (8 %).
Согласно предложенной методике для достижения наилучшего результата моделирования необходимо придерживаться следующего алгоритма действий:
1 этап - "тестовая выборка". Данный этап заключается в подготовке тестового массива (без пропущенных значений) из исходного массива данных – формируется тестовая выборка путем удаления объектов исследования, у которых присутствует хотя бы одно пропущенное значение исследуемых свойств.
2 этап - "идентификация параметров". На тестовой выборке осуществляется подбор оптимальных параметров для нечеткой системы и эволюционной стратегии. Оптимальными параметрами считаются те, при которых вычисленные параметры адекватности системы (СКО, САО) минимальны.
В таблицах 4.13 - 4.14 представлены результаты найденных оптимальных параметров: для всех исследований был выбран алгоритм селекции - элитаризм, количество итераций - 100. алгоритм эволюционной стратегии - ( ). Таблица 4.13 - Определение оптимальных параметров для восстановления микробиологических свойств пластовой воды № Кол-во термов Нечеткая система Вероятность мутации Кол-во точек скрещивания Нечеткая системы + эволюционная стратегия Из табл. 4.13 видно, что оптимальными параметрами для восстановления микробиологических характеристик стали следующие: разбиение на 5 термов, вероятность мутации 0.15 и количество точек скрещивания – две.
1 этап - "Проверка подобранных параметров". На данном этапе в тестовом массиве вводились искусственные пропуски, и проводился ряд экспериментов по восстановлению пропущенных значений с подобранными параметрами на шаге 1 и оценивались критерии адекватности выбранной модели восстановления (СКО, САО).
2 этап - "Восстановление параметров" предполагает проведение процедуры восстановления пропущенных значений в исходном массиве с подобранными параметрами.
Средствами разработанного программного комплекса (блок "Анализ данных") был проанализирован полный (восстановленный) массив данных. Рассмотрим полученные результаты. Корреляционная матрица нормированных признаков представлена в табл. 4.15.1 – 4.15.2. Нумерация признаков соответствует списку в табл. 4.12.
Анализ коэффициентов корреляции показывает, что признак плотности нефти связан одновременно с вязкостью нефти (0.82), содержанием смол (0.57), серы (0.52), микробиологическими данными УОБ (0.68), СВБ (0.67), сухим остатком (0.48) и ДНБ (0.47), но не связан и биполярен со следующими признаками: содержание парафина, асфальтенов, pH, концентрацией гетеротрофов и Eh. При этом концентрации гетеротрофов связаны с УОБ (0.46).
Вязкость нефти также связана с микробиологическими признаками - СВБ (0.86), УОБ (0.87), ДНБ (0.67) и сухим остатком (0.62), но с остальными признаками биполярна и не связана. Содержание серы и смол связаны между собой (0.88), а с остальными признаками не связаны или биполярны.
Анализ корреляционной матрицы признаков позволяет выявить структуру взаимосвязей признаков, которая графически может быть представлена в виде иерархической дендрограммы (рис. 4.2).
Анализ признаковой структуры фактора F1 показывает, что нагрузка этого фактора значимо определяется концентрациями СВБ (0.959), УОБ (0.946), вязкостью нефти (0.895), ДНБ (0.790), плотностью нефти (0.781), количеством сухого остатка (0.692), гетеротрофов (0.516), содержанием серы (0.503) и также имеет значимую отрицательную связь с Eh (-0.840).
Самое значимое влияние оказывают сульфатвосстанавливающие бактерии (СВБ), концентрация которых влияет на процессы и качество нефтедобычи [94]. Так, адаптация СВБ в нефтяном пласте вызывает интенсивные процессы образования сероводорода, который усиливает коррозию нефтяного оборудования, ухудшает товарное качество добываемой нефти и создает дополнительные технологические сложности при очистке и переработке добытой нефти.
Значимость же углеводородокисляющих бактерий (УОБ) объясняется тем, что продукты жизнедеятельности этих бактерий служат источниками питания для СВБ. В комплексном развитии с другими группами аэробных и анаэробных микроорганизмов СВБ участвуют в разложении простых и сложных субстратов. В сообществе с УОБ они принимают участие в окислении углеводородов [94]. Это в свою очередь объясняет большую связь с параметром сухого остатка (минерализации) [95-97]. Выделение сульфатов показывает, что исследуемые месторождения обладают солоноватыми пластовыми водами.
Значимость денитрифицирующих бактерий (ДНБ) объясняется тем, что они в большей степени способны к использованию жидких легкокипящих n-алканов и ароматических углеводородов. Другой причиной их преимущественного распространения в нефтяных пластах является принадлежность к факультативным анаэробам, то есть способности существовать в анаэробных и микроаэрофильных условиях.
Отрицательную связь окислительно-восстановительного потенциала (Eh) можно объяснить тем, что окислительно-восстановительные процессы зависят от концентрации окисленной и восстановленной формы элемента, температуры и особенно сильно от степени кислотности (рН) раствора. У окислителей, молекулы которых содержат кислород, окислительно-восстановительный потенциал возрастает с увеличением концентрации ионов водорода, а F1 практически не обладает связью с концентрацией рН.
Анализ признаковой структуры фактора F2 наоборот показывает именно значимость степени кислотности рН. Влияние содержания твердого парафина выявляется факторами F3 и F4.
Определим минимальное число факторов, адекватно воспроизводящих наблюдаемые корреляции. Наиболее часто число выделяемых факторов определяется количеством собственных чисел больше единицы. В нашем случае это факторы с 1 по 9. Но, как видно из табл. 4.16.1 – 4.16.2. факторы с 5 по 9 не обладают значимыми коэффициентами исследуемых свойств и три-четыре фактора наиболее полно характеризуют признаковую структуру данных месторождений (рис. 4.3), так как описывают более 82 % совокупной информации. В двумерном факторном пространстве отображены результаты классификации. Методом k-средней кластеризации позволил разделить объекты исследования на 3 класса месторождений. "Класс 1" включает в себя 3 месторождения: это Северное, Усинское и Урманское, которые сильно выделяются по параметру концентрации гетеротрофов. В "Класс 2" вошло 11 месторождений: Вахское, Самотлорское, Советское (проба 2004 .г), Вахское (проба 2004 г.), Зуунбаян, Тамсагбулаг, Русское, Ульяновское, Фуларти, Шингинское и Арчинское, отличающиеся максимальным содержанием смол и асфальтенов. А "Класс 3" содержит 4 месторождения: Советское, Крапивинское, Белый Тигр и Цаган-Элс, которые обладают максимальными концентрациями УОБ, ДНБ, гетеротрофов, наибольшим содержанием парафинов и наибольшей вязкостью, при этом данные характеристики в 2 - 55 раз выше, чем у образцов "Класса 2".
Визуальная часть программного комплекса
В качестве средства реализации программного комплекса выбран язык объектно-ориентированного программирования C#, а средой разработки - Microsoft Visual Studio 2012.
Обзор средств реализации показал, что C# - это объектно-ориентированный язык программирования общего назначения. C# дает разработчикам, занимающимся написанием кода, широкие возможности и языковую поддержку для создания сложных приложений. C# - один из языков программирования, который может использоваться для создания приложений, выполняемых в среде .NET CLR. Этот язык является результатом эволюции языков C и C++, созданный компанией Microsoft специально для использования на платформе .NET. Данный язык включает в себя полную поддержку структурного, компонентно-ориентированного и объектно-ориентированного программирования, которую только можно ожидать от современного языка [89, 90].
Среда разработки Microsoft Visual Studio 2012 - это набор инструментов и средств, предназначенных для помощи разработчикам программ любого уровня квалификации в решении сложных задач. Visual Studio улучшает процесс разработки и упрощает разработку высокоэффективных программ. Средства Visual Studio позволяют разработчикам работать с большей отдачей и затрачивать меньше усилий на повторяющиеся задачи. В версиях Visual Studio постоянно появляются новые средства, позволяющие разработчикам сосредоточиться на решении основных проблем, а не на рутинной работе. Например, дополнение ReSharper [91] созданное для повышения эффективности работы, проводит статистический анализ кода в масштабе всего решения, предусматривает дополнительные средства автозаполнения, навигации, поиска, подсветки синтаксиса, форматирования, оптимизации и генерации кода. Также Visual Studio разрабатывается таким образом, чтобы обеспечить высокую надежность и совместимость. Visual Studio обладает удачным сочетанием безопасности, масштабируемости и взаимодействия. В Visual Studio всегда поддерживаются новейшие технологии, и по возможности, обеспечивается обратная совместимость.
После изучения основных задач исследования, особенностей анализируемых данных, выбранных алгоритмов и методов, было спроектировано и реализовано приложение, имеющее простую систему классов.
Согласно схеме проведения комплексного анализа (раздел 2.1) и требованиям к системе, программный комплекс будет состоять из 4 основных блоков, каждый из которых будет включать в себя все необходимые классы, методы и функции для решения своей задачи, а также методы для взаимодействия между блоками. Архитектура программного комплекса представлена на рис. 3.1.
Блок "Моделирование" выполняет задачу идентификации нечеткой системы на основе метода эволюционной стратегии. Входными данными являются записи из тестовой выборки исследуемой таблицы "объект-свойство", которая состоит из всех полных записей (полными записями считаются те, в которых нет пропущенных значений). На основе тестовой выборки будут подбираться оптимальные параметры нечеткой системы и метода эволюционной стратегии. Данный блок обладает визуальным отображением результатов построения нечеткой системы, то есть можно просмотреть базу правил, функцию принадлежности и значения критерия приспособленности элементов системы. Выходными данными блока являются подобранные параметры системы.
Блок "Восстановление" отвечает за задачу восстановления пропущенных значений, включая в себя тестовое восстановление с помощью методики скользящего экзамена (раздел 1.2.2) и восстановление на основе полученной модели в блоке "Моделирование". Входными данными для тестового восстановления являются записи из той же тестовой выборки, что использовалась в блоке "Моделирование". Выходным значением тестового восстановления является оценка подобранной модели (точность), с которой будут восстанавливаться пропущенные значения. Входными данными для восстановления являются данные из исходной таблицы "объект-свойство" с пропущенными значениями, а выходными – данные "полной" таблицы – таблицы с исходными данными и восстановленными значениями.
Блок "Анализ" отвечает за задачу анализа многомерных данных методами ФА с вращением и классификацией. Входными данными являются данные из восстановленной или полной исследуемой таблицы. Блок включает возможности отображения результатов вычисления в виде таблиц (ковариационная и корреляционная матрицы, собственные значения, собственные вектора и т.д.), гистограмм нагрузок факторов, дендрограмм и графиков (пространственное отображение в пространстве выбранных факторов и прочее). Отображаемые выходные данные позволяют интерпретировать полученные результаты.
Блок "Пространственный анализ" используется для учета пространственных характеристик исследуемых объектов с применение средств ArcGis 9.3.1. В блоке "Анализ" реализована функция экспортирования результатов, которая формирует выходную таблицу. Таблица состоит из исходных данных блока "Анализ" и результатов классификации. Входными же данными блока "Пространственный анализ" является исходная таблица с пространственными характеристиками объектов и экспортированная таблица с результатами классификации. Выходными данными является картографическое отображение объектов с результатами анализа.
Интерфейс блока "Моделирование" (рис. 3.3) включает в себя меню, с помощью которого можно загрузить тестовые данные, сохранить полученную нечеткую систему. Также, через меню можно просмотреть "базу правил", графическое представление функции принадлежности входных переменных и сводную таблицу результатов (до загрузки данных доступна только функция "загрузить таблицу").
На форме представлены все необходимые параметры для моделирования, а именно, параметры нечеткой системы, функции принадлежности, метода эволюционной стратегии и критерия оптимальности.
Перечисленные параметры и методы включают: количество термов на параметр, количество хромосом для начальной популяции, количество итераций, количество хромосом будущих популяций; предлагается выбрать алгоритмы селекции, скрещивания и мутации; вид эволюционной стратегии и вид ошибки для расчета.
После загрузки входных данных на форме можно увидеть: таблицу наблюдений (рис. 3.4), также, появляется кнопка "дополнительные параметры" (рис. 3.5), которые позволяют выбрать "количество термов на параметр" и "диапазон" (минимальное и максимальное значение исследуемого свойства) индивидуально для каждой переменной.
После выбора параметров необходимо построить нечеткую систему, после чего на форме отобразятся рассчитанные ошибки для всех хромосом начальной популяции, и значение лучшей хромосомы. Кнопка "Вычислить" (рис. 3.4) задействует выбранные параметры эволюционной стратегии, которые оптимизируют построенную модель нечеткой системы.
При "двойном нажатии" на значения ошибки хромосом открывается форма (рис. 3.6) с ее видом функции принадлежности. Переключение между переменными происходит с помощью выпадающего списка.
Результирующие значения – это таблица, включающая входные и выходные значения в следующей последовательности: таблица наблюдений, соответствующие значения, вычисленные нечеткой системой, модифицированные значения методом наименьших квадратов и ошибка между этими значениями (тип ошибки определяет пользователь на главной форме, по умолчанию – абсолютная). Кроме того, есть отдельно вынесенные ошибки системы для лучшей хромосомы.
Дополнительно в меню (рис. 3.3) и в окне "Результатов" (рис. 3.8) можно сохранить построенную нечеткую модель, если есть в этом необходимость. Сохранение параметров нечеткой системы выполняется в формате XML. Запись в файл происходит путем сериализации объекта данного класса, а чтение путем десериализации. Такой способ работы с файлами обеспечивает надежность, расширяемость и простоту [92].
