автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование фрактальных структур в задачах многомерной классификации

На правах рукописи

Биргочинская Татьяна Яковлевна

МОДЕЛИРОВАНИЕ ФРАКТАЛЬНЫХ СТРУКТУР В ЗАДАЧАХ МНОГОМЕРНОЙ КЛАССИФИКАЦИИ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

1 г; ¡1/ ! | ¿и и'

Воронеж - 2013

005059396

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный аграрный университет имени императора Петра I».

Научный руководитель: доктор технических наук, доцент

Буховец Алексей Георгиевич

Официальные оппоненты: Сумин Александр Иванович

доктор физико-математических наук, профессор, ВУНЦ ВВС «Военно-воздушная академия имени профессора Н.Е.Жуковского и Ю.А.Гагарина» (г. Воронеж), заведующий кафедрой математики

Леденева Татьяна Михайловна

доктор технических наук, профессор, Воронежский государственный университет, зав. кафедрой вычислительной математики и прикладных информационных технологий

Ведущая организация: ФГБОУ ВПО «Тамбовский государственный

университет имени Г.Р. Державина»

Защита диссертации состоится 2013 года в 15.10 часов на заседании

диссертационного совета Д 212.038.20 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская пл., д.1, ауд. 335.

С диссертацией можно ознакомиться в научной библиотеке Воронежского государственного университета.

Автореферат разослан <4Н » Р Ч_2013 года.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент "" Шабров С. А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования и степень проработанности.

В настоящее время теория фракталов является одной из наиболее актуально и стремительно развивающейся теорий, которая находит самое широкое приложение в различных областях практической деятельности. Использование фрактальных моделей позволило значительно продвинуться в решении таких практически значимых задач как обработка цифровой информации, изучение вопросов турбулентного движения жидкостей, радиолокации, исследование финансовых рынков, получение новых наноматериалов с заданными свойствами и пр. Значительный вклад в развитие фрактальной теории был внесен зарубежными учеными: Mandelbrot В., Barnsley М. F., Crownover R.M., Devaney R.L., Falconer К., Schroeder М. и др. В России этими проблемами занимались С.В. Божокин, А.Д. Морозов, В.П. Паршин, А.А. Потапов, Б.М. Смирнов и другие.

Интенсивное развитие теории фракталов не только выдвигает новые вопросы, но и позволяет искать подходы к решению задач, ранее сформулированных, но не получивших до настоящего времени удовлетворительных решений. Одной из таких задач является классификационная задача. Изучению проблем, связанных с этой задачей были посвящены работы таких ученых, как С.А. Айвазяна, В-.М. Буштабера, А.А. Дорофеюка, Ю.И.Журавлёва, Н.Г. Загоруйко, И.И. Елисеевой, А.И. Орлова и др. Важность классификационной задачи обусловлена как широким спектром её практических приложений, так и той ролью, которую играет эта задача в теориях распознавания образов и искусственного интеллекта. Предлагаемый в диссертационной работе подход к решению указанной выше задачи основывается на современных представлениях фрактальной теории и вместе с тем в значительной степени учитывает опыт и полученные ранее результаты.

В связи с этим, тема диссертационной работы, посвященная моделированию решений классификационной задачи в рамках фрактальной теории, является актуальной.

Диссертационная работа выполнена в соответствии с научно-исследовательскими работами Воронежского государственного аграрного университета имени императора Петра I « «Построение и численная реализация новых математических моделей технологических и производственных процессов в АПК» № г.р. 01.200.1003987.

Объект исследования - структуры многомерных данных, полученные с помощью кластерного анализа и применения алгоритмов, в основе которых лежит фрактальный подход.

Предмет исследования — процедура, основу которой составляют рандомизированные системы итерированных функций (РСИФ), позволяющая при решении классификационных задач воспроизводить структурные особенности многомерных данных.

Целью диссертационной работы является разработка фрактальных моделей, позволяющих аппроксимировать эмпирические структуры многомерных данных в классификационных задачах.

Для достижения поставленной цели решались следующие задачи:

1) анализ современных алгоритмов кластерного анализа с целью исследования возможностей применения теории фрактальных множеств в задачах классификации;

2) разработка алгоритма моделирования многомерных фрактальных структур на основе численного метода построения фрактальных множеств, оценка характеристик РСИФ-алгоритма, а также свойств множеств, порождаемых предложенным алгоритмом;

3) разработка программного комплекса средствами языка программирования статистической обработки данных R для проведения вычислительного эксперимента и исследования структур многомерных данных на основе фрактальных моделей, полученных с использованием предложенных алгоритмов. ■

4) тестирование разработанного программного обеспечения при решении содержательных прикладных задач.

Научная новизна результатов диссертационной работы заключается в следующем:

1. Представлен способ моделирования многомерных фрактальных структур, отличающийся от стандартных методов построения фрактальных множеств использованием процедуры, основанной на обобщении задачи об определении суммы ряда со случайной расстановкой знаков.

2. Разработан численный метод аппроксимации многомерных данных, отличающиеся от известных тем, что основан на моделях фрактальных множеств, порождаемых рандомизированными системами итерированных функций.

3. Предложена модификация метода выделения эталонных объектов в классификационных задачах, отличительной чертой которой является учет системных свойств классифицируемой совокупности, что позволяет дать новую интерпретацию типичных объектов в рамках системного подхода.

4. Создан и апробирован метод моделирования многомерных фрактальных структур с помощью рандомизированных систем итерированных функций, реализованный в виде библиотеки прикладных программ «RIFS: Random Iterated Function System», написанной средствами языка статистической обработки данных и программирования R.

Диссертационная работа соответствует паспорту специальности 05.13.18 -«Математическое моделирование, численные методы и комплексы программ»: п. 5. «Реализация эффективных численных методов и алгоритмов в виде •комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента», п. 6. «Комплексное исследование научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента», п. 8. «Разработка новых

математических методов и алгоритмов интерпретации натурного эксперимента на основе его математической модели».

Теоретическая и практическая значимость работы.

Теоретическая значимость диссертационной работы заключается в том, что предложенный в ней фрактальный подход позволяет более глубоко исследовать механизмы формирования структуры многомерных данных и методы выделения типичных объектов в рамках системного подхода.

Практическая значимость результатов диссертационного исследования состоит в том, что на основе разработанных алгоритмов и методов становится возможным описание механизмов формирования многомерных фрактальных структур и проверка гипотез о соответствии между генерируемыми и эмпирическими данными. В перспективе развитие данных методов позволит осуществить прогноз эволюции системы исследуемых данных.

Основные научные результаты диссертационного исследования могут быть использованы для оценки фрактальных свойств эмпирических данных, а также при решении задач, связанных с построением районированных (стратифицированных) выборок, которые широко используются при социологических исследованиях.

Исследование фрактальности изучаемой структуры влечет за собой установление её критических состояний. Это может быть использовано при решении задач управления, связанных с прогнозированием и количественным описанием состояний открытых экономических систем, для своевременного принятия мер при планировании и антикризисном управлении.

Результаты работы могут быть использованы в учебном процессе на экономических факультетах вузов при изучении дисциплин «Эконометрика», «Компьютерное моделирование», «Математическое моделирование социально-экономических процессов» а также в специальных курсах подготовки магистров по экономическим специальностям.

Теоретическая часть диссертации основана на использовании современных методов дискретной математики, теории вероятностей и теории фракталов. Адекватность разработанных математических моделей и проведенных вычислительных экспериментов подтверждается сопоставлением результатов теоретических исследований с результатами эмпирических исследований на реальных объектах.

Методология и методы исследования.

В работе использованы методы и средства системного анализа, теории вероятностей, математической статистики и прикладного статистического анализа, теории фрактальных множеств, имитационного моделирования и теории оптимизации.

Положения выносимые на защиту:

1. Модифицированный алгоритм, реализующий процедуру построения многомерных предфрактальных множеств с помощью вычисления сумм,

образованных путем случайного отбора членов абсолютно сходящегося числового ряда;

2. Исследования основных свойств многомерных предфрактапьных множеств, генерируемых с помощью определения сумм, случайно отобранных членов абсолютно сходящегося ряда;

3. Статистические оценки параметров рандомизированных систем итерированных функций, получаемые по эмпирическим данным;

4. Метод практического применения рандомизированных систем итерированных функций в задачах классификации (на примере содержательных задач экономики и социологии).

Апробация работы. Материалы диссертационной работы докладывались и обсуждались на следующих международных и всероссийских научных конференциях: Международной конференции «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2010); XI, XII Международной научно-практической конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2011, 2012); V Международной научно-практической конференции «Социологические методы в современной исследовательской практике» (Москва, 2011); Международной научно-практической конференции «Математика и ее приложения (Орёл, 2011); XII Международной молодежной научной конференции «Севергеоэкотех- 2011» (Ухта, 2011); Воронежская зимняя математическая школа С.Г. Крейна-2012 (Воронеж); III, VI, VIII Международной конференции «Экономическое прогнозирование: модели и методы» (Воронеж, 2007, 2010, 2012); Всероссийской научно-практической конференции «Современные проблемы и перспективные направления развития комплексов и систем военного назначения, форм и способов их боевого применения» (Воронеж, 2011).

Публикации. По результатам исследования опубликовано 22 печатных работ, в том числе 4 в изданиях, рекомендованных ВАК РФ для публикации основных результатов диссертационных исследований.

Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: 1) разработка и реализация алгоритмов [1]; 2) исследование свойств множеств, генерируемых рандомизированными системами итерированных функций [2]; 3) получение и интерпретация результатов решения классификационных задач [3], [4].

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, двух приложений и списка литературы, включающего 180 наименований, изложена на 146 страницах и включает 21 рисунков и 7 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы, рассматривается предмет и объект исследования, формулируются цель и задачи диссертационной работы, излагается научная новизна, теоретическая и практическая значимость работы.

В первой главе были рассмотрены общая постановка задач классификации и методы её возможных решений. Анализ классификационных алгоритмов

позволяет прийти к заключению, что в рамках геометрического подхода алгоритмы кластерного анализа в зависимости от классификационного критерия и выбранной метрики выделяют в многомерном признаковом пространстве различные структуры. Проведенный анализ позволяет формулировать классификационную задачу как задачу изучения структур многомерных данных на основе сравнения классификационных разбиений, производимыми различными алгоритмами.

Наряду с этим были рассмотрены результаты построения различных фрактальных множеств. Выявленные сходства классификационных структур и генерируемых фрактальных множеств позволило выдвинуть предположение о возможности аппроксимации классификационных разбиений фрактальными образованиями.

Во второй главе рассмотрен метод, относящийся к РСИФ. В результате его выполнения формируется множество, имеющее фрактальную структуру.

Предложенный подход к моделированию многомерных данных отличается от стандартных методов тем, что позволяет изучаемое множество аппроксимировать с помощью фрактальных структур.

В рамках данной работы предлагается ввести следующие определения.

Протофракттом будем называть множество точек Ъ вместе с заданным на них распределением вероятностей Р(2), которые участвуют в порождении фрактального множества.

Предфракталом X назовем счетное множество точек, которое появляется в ходе реализации РСИФ. Фракталом будем называть предельное множество, содержащее (потенциально) все возможные точки, которые могут появиться в ходе выполнения РСИФ.

В диссертации предложена модификация метода РСИФ, который которая позволяет обобщить его на многомерный случай:

1. В многомерном пространстве йр определены некоторое множество точек

2 = {¿у}^, которое будет называться протофракталом, параметр ц и

распеределение Р(2) =

2. В пространстве Яр произвольным образом определяется точка Х0.

3. В соответствии с заданным распределением Р(2) определяется номер точки выборки 2^ е 2.

4. Вычисляются координаты новой Хг точки по формуле

= 1.....Р)- 0)

5. В дальнейшем полученная точка принимается за исходную, а затем пункты

3 и 4 повторяются столько раз, сколько точек предфрактала необходимо получить.

В результате выполнения такой процедуры будет построено множество точек Еп — {ХП,ХП_1,... ,Хг,Хг}, которое было названо предфракталом. На рис.1

представлены результаты выполнения процедуры Р1 при различных значениях параметра /ц.

Процедура может быть обобщена для случая, когда параметры ди /> могут быть различными для каждой из точек протофрактала.

Заметим, что в одномерном случае при 2 — {ОД}, Р — {1/2,1/2}, //=2 применение данной процедуры приводит к построению канторова множества, которое может быть рассмотрено как общепризнанный классический фрактал.

А=0,5

ДА

А А АД ДА

АА ДА ДА

АА А А АД АА

АА

А А АД АА

АА ДА ДА ДД

/^=1,5 /.1=3

Рис. 1. Примеры выполнения процедуры Зависимость результатов выполнения от параметра ¡1 (N=10 ООО, рг = р2= р3 = */з> в качестве протофрактала Ъ взяты вершины

треугольника).

В работе исследуются основные свойства множеств, генерируемых предложенной процедуры.

Утверждение I. Неподвижными точками преобразования (1) при ^ 0 может выступать любая точка протофрактала 2 = Показано, что эти точки

будут устойчивыми при ц > 0.

Утверждение 2. Зависимость построенной структуры от значений параметра ц следующее: 1) при ц -» 0 будет наблюдаться сходимость к начальной точке Х0;

2) в случае неограниченного увеличения значения параметра ¡х предельные точки будут совпадать с точками исходного протофрактала Z =

3) при промежуточных значениях ц можно наблюдать, что каждая исходная точка становится основанием некоторого фрагмента, вокруг которой формируется группа точек, воспроизводящая структуру исходных данных. Причём исходная точка, вокруг которой формируется новая реплика, занимает в последней то же самое положение, какое она занимала в исходной.

Утверждение 3. Значение каждой точки предфрактала Еа ~ {-Xn.Xn-i. является выпуклой комбинацией точек протофрактала

Рассмотрим выполнение процедуры F1 более подробно в одномерном случае. Пусть Х0 = (х0) - начальная точка (п.1), тогда последовательные шаги выполнения процедуры можно представить следующим образом:

где ^ = гЬ'Yo = х°+

^ = ^ = + ¡"П = *> + Гг\

(2)

где Yi = /iz|

*з = = тЬг (*2 + ^3))= + ^ +

(3)

где у2 = fizj

= f (■■■ f (f (f Уо + Уг) + Уг) + ' • ■ + Уп-i)

Полученное выражение представляет собой запись схемы Горнера для многочлена п-й степени от переменной f без свободного члена с коэффициентами Yn-vYn-2' —>Yo> которые получены путем случайного отбора из совокупности точек протофрактала Z — {£/} на каждом шаге. Раскрыв скобки, получим

71-1

*П = УоГ + У1Г-1 + y2r~2 + -Yn-if = f £

т=О

Перепишем, изменив порядок суммирования, и оценим полученную сумму сверху

*» = f £ nz-^r = ^ 2 zf—>r < м £ г.

т=0 т=0 т=О

где М = тахДг}\, 0 < £ < 1 при/1 > 1.

ТТ51 «чГ-г - + * X*' ♦ ~+*

т-О

или

I у I 1=1

где о, = причем а; > 0, а; = 1,

Таким образом, предельное значение хп является, во-первых, конечным значением, а во-вторых, представляет собой выпуклую комбинацию точек

протофрактала 1 = ^

Приведенные рассуждения лежат в основе модифицированной процедуры ¥2. При заданном множестве 2 = {¿¡}К.=1, распределении вероятностей значений Ру и значении ¡1 построение требуемого множества фактически можно свести к выполнению следующих действий:

1. В соответствии с распределением Р(£) = [^}у=1 0' = 1.2, ...,/0 вычисляются К сумм а,- О' = 1. образованных из элементов абсолютно сходящегося ряда вида

^=^=1. (4)

Эти К значений записываются в строку как элементы матрицы А — ГДе ^ ~ число требуемых точек предфрактала, К - число точек

протофрактала.

2. Полученная в результате вычислений матрица А умножается на матрицу 2КуМ, составленную из координат точек протофрактала. Результат - матрица X = А х 1 будет представлять собой список координат точек предфрактала X в заданном пространстве /?р.

В результате исследования множеств, генерируемых алгоритмом, были установлены следующие свойства:

Утверждение 4. Мощности множеств, генерируемых РСИФ в ходе выполнения процедуры Р1, будет счетным, в то время как предельное множество X = и„=1 Еп будет иметь мощность континуума.

Существует гомеоморфизм отображающий множество точек, получаемых в результате выполнения процедуры Р1 в канторово множество.

Утверждение 5. Для того чтобы набор а = {а^=1 был набором, полученным посредством Р2, необходимо и достаточно, чтобы среди его элементов существовал доминирующий элемент, т.е. элемент ау а^

величина которого превосходит сумму всех остальных.

Таким образом, чтобы получить все точки предфрактала, достаточно зафиксировать доминирующую компоненту а;- и произвольным образом формировать оставшиеся компоненты из членов ряда (4). При этом очевидно, что все перестановки элементов Ф ]) образуют группу преобразований.

Утверждение 6. Полученное предельное множество является плотным в себе. Это означает, что любая точка фрактального множества X является предельной точкой, и множество X не содержит изолированных точек, т.е. множество X является совершенным.

Если рассматривать оба представленных подхода как потенциально неограниченные конструктивные процессы, то результаты выполнения не являются фундаментальной последовательностью в силу случайности выбора

элементов 2 = и, следовательно, не имеют определенного предела в

классическом понимании этого значения.

Для практического применения РСИФ необходимо оценить параметры процедуры.

Оценки параметров рандомизированных систем итерированных функций. Представим, что имеющийся в распоряжении набор точек X получен в результате выполнения указанных выше процедур (Р1 или Р2), однако некоторые

параметры генерирующей процедуры - (р1,р2, ~.,Рк}, Я = и ц неизвестны

и их требуется оценить. Решение этой задачи связано с возможностью аппроксимации имеющихся данных посредством множества точек, генерируемых рандомизированными системами итерированных функций.

Оценивание параметров Ру Полученное в результате классификации разбиение множества Л'на попарно непересекающиеся подмножества 51(52,... ,5^, такие, что 5;П5";=0, / Фу, ¿ = 1,2,...,К и = X, позволяет получить

значения ру = V/,/ = 1,..., К, где Пу- число объектов класса 5у, которые будем рассматривать как статистические оценки набора {ри р2,...,рк].

Оценивание параметра ¡1 по методу моментов. Для удобства преобразований вводится следующее обозначение: £ = В этом случае

процедура может быть представлена как последовательное выполнение действий

+ = .....). (5)

Находя начальные моменты первого и второго центрального порядка от обеих частей равенства, получаем

0{2)-Р{Х)

Легко показать, что

. _ тх)

В качестве иллюстрирующего примера в работе представлен результат определения параметра ц для такого классического фрактала, как треугольник (салфетка) Серпинского.

Таблица 1 — Значения параметра ц и ММ-оценок его, полученных в результате машинного эксперимента т1 и т2

№ Значение Значение Значение Значение Оценки Оценки

М а 0,(Х) D2(X) ш, т2

1 0.100 0.909 0.029 0.051 0.083 0.150

2 0.250 0.800 0.071 0.088 0.217 0.276

3 0.500 0.667 0.123 0.130 0.406 0.437

4 0.750 0.571 0.184 0.182 0.678 0.669

5 1.000 0.500 0.221 0.250 0.876 1.047

6 1.500 0.400 0.303 0.307 1.432 1.461

7 2.000 0.333 0.324 0.372 1.610 2.099

8 3.000 0.250 0.376 0.435 2.139 2.975

9 4.000 0.200 0.448 0.471 3.210 3.688

10 5.000 0.167 0.453 0.534 3.303 5.535

11 6.000 0.143 0.511 0.533 4.721 5.487

12 7.000 0.125 0.510 0.559 4.686 6.665

13 8.000 0.111 0.535 0.574 5.562 7.478

14 9.000 0.100 0.564 0.575 6.910 7.540

15 10.000 0.091 0.545 0.608 5.981 10.260

Оценивание множества точек протофрактала после того, как будет сформирована матрица А (в соответствии с процедурой ¥2) на основании оценки параметра ц, получено в виде

2 =А+Х = (АТА)~1АТХ (8)

где А+ — (АТА)~1АГ - матрица обобщенного МП-преобразования (Мура -Пенроуза).

После того, как будет определена матрица ¿, строки которой представляют координаты оценок точек протофрактала, можно опять перейти к оценке параметра ¡1.

В третьей главе представлены результаты практического применения теоретических разработок, позволяющие продемонстрировать работоспособность предложенного фрактального подхода в решении содержательных задач.

В первой задаче предлагается рассмотреть подход к оценке фрактального характера типологии стран мировой экономической системы в предкризисный период.

Математическое моделирование и количественное описание состояний открытых экономических систем относится к важным задачам экономической математики, которые определяют своевременность решений при планировании и антикризисном управлении, гибкость финансового регулирования и возможность предупреждения экономических кризисов. Одним из свойств, на которые в последнее время все чаще и чаще обращают внимание специалисты, является

фрактальность структур системы, наличие которой в изучаемых данных говорит об устойчивости системы в целом, а её нарушение приводит к критическим и кризисным событиям. Рассмотрение объектов исследования как системных конструкций позволяет сделать ряд выводов о характере поведения объекта.

Предложенный в работе подход основан на проверке утверждения, что полученное в результате классификации распределение классов является ципфовым, зависящим от параметра а, т.е. значимо отличается от рангового распределения, случайным образом полученным из равномерного. Фактически это соответствует утверждению основной гипотезы: Н0\а = 0, при конкурирующей Нг:а< 0.

Для сравнительного анализа стран мировой экономической системы были отобраны 9 основных показателей, характеризующих современное экономическое состояние. Для проведения классификационных построений были взяты значения отобранных показателей за 2006 и 2007 годы. Результаты проверки сформулированной гипотезы, выполненные средствами имитационного моделирования, позволяют сделать вывод, что кризис был практически спровоцирован иными - не экономическими механизмами. Другими словами, фрактальность изучаемой структуры указывает на отсутствие кризисных состояний в мировой экономической системе.

Вторая содержательная задача, рассмотренная в диссертационной работе, связана с использованием фрактального подхода в проектировании районированных выборок при исследовании уровня жизни в регионах РФ.

Для этого предварительно была проведена типология 83 регионов России по отобранным блокам показателей, характеризующих уровень и качество жизни в регионах, и с использованием алгоритмов кластерного анализа (к-средних, Форель, агломеративные иерархические). В итоге было получено 8 классов регионов, которые можно было охарактеризовать как: «самые благополучные», «потенциально неблагополучные», «самые неблагополучные», «неблагополучные», «потенциально благополучные», «средине» и 2 изолированных класса, состоящих из отдельных регионов. По результатам классификации была построена матрица А размеров 83x8 при значении // = 17,8. С помощью матрицы А были получены точки признакового пространства, представляющие оценки точек протофрактал г, которые отражают структуру распределения объектов - регионов России, в пространстве выбранных для классификации признаков. В рамках системного анализа использования фрактальных моделей классификационной задачи позволяет по- новому определить типичный объект, который в отличие от традиционного подхода максимально выражает свойства выделенного класса.

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

В диссертационной работе на основе выполненных теоретических и прикладных исследований в области моделирования фрактальных структур в задачах многомерной классификации получены следующие результаты:

1. Были проанализированы современные алгоритмы кластерного анализа, на основании чего был сделан вывод о возможности использования фрактального подхода решении классификационных задач.

2. Разработана процедура, являющаяся обобщением РСИФ и отличающаяся от них способом формирования структур многомерных данных, основанного на обобщении задачи об определении суммы ряда со случайной расстановкой знаков, позволяющей получать статистические оценки параметров РСИФ.

3. Предложенная процедура генерирования многомерных фрактальных структур была реализована в виде библиотеки прикладных программ «RIFS: Random Iterated Function System», написанной средствами языка статистической обработки данных и программирования R, позволяющей совершенствовать предложенные методы построения фрактальных множеств в исследовании структур многомерных данных. Пакет RIFS доступен на правах лицензий GPL-3 по адресу URL: http://cran.r-project.org/web/packages/RIFS/index.html.

4. В результате исследования генерируемых процедурой дискретных множеств были установлены свойства, характеризующие мощность, разрешимость, перечислимость и совершенство фрактальных множеств, а так же получены оценки параметров рандомизированных систем итерированных функций и множеств точек протофрактала позволяющие использовать эти результаты в решении клаассифкационных задач.

5. Продемонстрирована работоспособность и эффективность предложенной методики при решении прикладных задач.

Основные публикации по теме диссертации

Публикации в рецензируемых изданиях, рекомендованных ВАК

1.Буховец А.Г. Использование фрактальных моделей в задачах классификации / А.Г. Буховец, Е.А. Буховец, Т. Я. Бирючинская // Системы управления и информационные технологии.-2009.- №1(37).- С. 117-121.

2. Буховец А.Г. Моделирование фрактальных свойств системных объектов / А.Г. Буховец, Т. Я. Бирючинская// Вестник ВГУ. Системный анализ и информационные технологии.- 2011.- №2 - С. 22-26.

3. Буховец А.Г. Фрактальный подход к анализу данных в моделях многомерной классификации / А.Г. Буховец, Т. Я. Бирючинская // Современная экономика: проблемы и решения.-2011.- №7(19). - С. 149-160.

4. Буховец А.Г. Типология стран мировой экономической системы в предкризисный период / А.Г. Буховец, Т. Я. Бирючинская, Р.Ю. Клишин // Вестник Воронежского государственного аграрного университета. — 2011. -№1(28).-С. 139-146.

Статьи и материалы конференций

5. Бирючинская Т. Я. Моделирование фрактальных структур системами итерированных функций / Т. Я. Бирючинская II Севергеоэкотех-2011: материалы XII Международной молодежной научной конференции. Ухта, 16-18 марта 2011 г. -Ухта, 2011.-С.227-230.

6. Бирючинская Т. Я. Исследование фрактальных структур, моделируемых рандомизированными системами итерированных функций / Т. Я. Бирючинская // Воронежская зимняя математическая школа С.Г. Крейна-2012, Воронеж- Изд-во ВГУ, 2012. - С.32-34.

7. Буховец А.Г. Представление оценки плотности в классификационных задачах / А.Г. Буховец, А. Ю. Головко, Т. Я. Бирючинская // Современные проблемы прикладной математики и математического моделирования. Материалы И международной научной конференции. Воронеж, 2007, С. 50.

8. Буховец А.Г. Аналитические оценки плотности в многомерных классификационных задачах / А.Г. Буховец, Т.Я. Бирючинская // Современные методы теории краевых задач. Материалы Воронежской весенней математической школы. Воронеж: ВГУ, 2008, С.59-60.

9. Буховец А.Г. Использование систем итеративных функций в решении прикладных задач / А.Г. Буховец, П.В. Москалев, Т.Я. Бирючинская // Актуальные проблемы прикладной математики, информатики и механики: сборник трудов Международной конференции. - Воронеж: ВГУ, 2010. - С. 84-87.

10. Буховец А.Г. Модели, учитывающие влияние доминирующего фактора/ А.Г. Буховец, Т.Я. Бирючинская, Н. А. Кораблина // Экономическое прогнозирование: модели и методы: материалы VI Международной научно-практической конференции. Воронеж, 6 апреля 2010 г. - Воронеж: ВГУ 2010 -4.1.-С. 61-66.

11. Буховец А.Г. О сопоставлении решений краевых задач с аттракторами систем итеративных функций/ А.Г. Буховец, П.В. Москалев, В.В. Шитов, Т.Я. Бирючинская // Современные методы теории краевых задач. Материалы Воронежской весенней математической школы. Воронеж, 2010, С. 47-48.

12. Буховец А.Г. Использование системы К в научных исследованиях и учебном процессе / А.Г. Буховец, Р.В. Мосвкалев, Т.Я Бтрючинская //Информатика: проблемы, методологи, технологии:метериалы XI международной научно-практической конференции 10-11 февраля 2011 г. - Воронеж: ВГУ 2011 -т.З, С. 43-47.

13. Буховец А.Г. Исследование фрактальной размерности в сингулярно-спектральном разложении / А.Г. Буховец, Т.Я. Бирючинская // Математика и её приложения. Экономическое прогнозирование: материалы Международной научно-практической конференции. Орёл, 20-21 мая 2011г. - Орел, 2011 - С 192196.

14. Буховец А.Г. О разрешимости множеств, генерируемых рандомизированной системой итеративных функций/ А.Г. Буховец, Т.Я. Бирючинская//Актуальные проблемы прикладной математики, информатики и механики: сборник трудов международной конференции. Воронеж, 26-28 сентября 2011 г. - Воронеж: ВГУ. - С. 90-93.

15. Буховец А.Г. О сходимости рандомизированных систем итеративных функций/ А.Г. Буховец, Т.Я. Бирючинская// Современные проблемы прикладной математики, теории управления и математического моделирования (ПМТУММ-

20011). Материалы IV международной научной конференции. Воронеж, 12-17 сентября 2011, С. 49-50.

16. Буховец А.Г. Выбор типичных объектов в классификационных задачах/ А.Г. Буховец, Т.Я. Бирючинская, Е.О. Лаврова // Социологические методы в современной исследовательской практике: сборник статей, посвященный памяти первого декана факультета социологии НИУ ВШЭ А.О. Крыштановского. -Москва: НИУ ВШЭ, 2011. - С. 13-19.

17. Буховец А.Г. Построение фрактальных множеств с помощью систем итерированных функций/ А.Г. Буховец, Т.Я. Бирючинская, О.И. Канищева, Д.В. Грачиков // Современные проблемы и перспективные направления развития авиационных комплексов и систем военного назначения, форм и способов их боевого применения: сборник материалов Всероссийской научно-практической конференции. Воронеж, 22-23 ноября 2011г. - Ч. 3. - Воронеж: ВАИУ, 2011. - С. 12-13.

18. Буховец А.Г. Оценка параметров рандомизированных систем итерированных функций в классификационных задачах/ А.Г. Буховец, Т.Я. Бирючинская, О.И. Канищева, Д.В. Грачиков // Современные проблемы и перспективные направления развития авиационных комплексов и систем военного назначения, форм и способов их боевого применения: сборник научных статей Всероссийской научно-практической конференции. Воронеж, 22-23 ноября 2011г. - Ч. 3 .-Воронеж: ВАИУ, 2011. - С. 26-31.

19. Буховец А.Г. Геометрическое представление результатов выполнения рандомизированных систем итерированных функций./ А.Г. Буховец, Т. Я. Бирючинская, К.К. Горностаев // Информатика: проблемы, методология, технологии: материалы XII Международной научно-методической конференции. Воронеж, 9-10 февраля 2012 г. - Воронеж: Издательско-полиграфический центр ВГУ, 2012. - Т. 2. - С.75-77.

20. Буховец А.Г. Оценка точности аппроксимации многомерных данных рандомизированной системой итерированных функций / А.Г. Буховец, Т. Я. Бирючинская, П.В. Москалев // Воронежская зимняя математическая школа С.Г. Крг»на-2012, Воронеж: Изд-во ВГУ, 2012. - С.39-41.

21. Буховец А.Г. Фрактальный подход в классификационных задачах./ А.Г. Буховец, Т. Я. Бирючинская // Экономическое прогнозирование: модели и методы: материалы VIII Международной научно-практической конференции. Воронеж, 12 мая 2012 г. - Воронеж: ВГУ, 2012. - С. 31 -34.

Библиотека прикладных программ

22. Moskalev P.V., Bukhovets A.G., Biruchinskay Т.Ya. - RIFS: Random iterated function system. - CRAN, 2012. - R package version 0.1-5. URL: http://cran.r-project.org/web/packages/RIFS/ (online; accessed: 04.06.2012).

Подписано в печать 22.04.2013 г. Формат 60х80'/|б. Бумага кн.-журн.

Усл. п.л. 1,0. Гарнитура Тайме. Тираж 120 экз. Заказ № 7697.

Типография ФГОУ ВПО ВГАУ 394087, Воронеж, ул. Мичурина, 1

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ ИМЕНИ ИМПЕРАТОРА ПЕТРА I»

П4УП1 '.4« \

На правах рукописи

Бирючинская Татьяна Яковлевна

МОДЕЛИРОВАНИЕ ФРАКТАЛЬНЫХ СТРУКТУР В ЗАДАЧАХ МНОГОМЕРНОЙ КЛАССИФИКАЦИИ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научный руководитель: доктор технических наук, доцент Буховец А.Г.

Воронеж - 2013

СОДЕРЖАНИЕ

Введение............................................................................................................3

1 Методы многомерной классификации и фрактального анализа в типологических задачах....................................................................................9

1.1 Понятие многомерной классификации. Общая постановка задачи......9

1.2 Алгоритмы построения классификационных разбиений.....................26

1.3 Фрактальные структуры в классификационных задачах.....................33

2 Построение фрактальных множеств рандомизированными системами итерированных функций................................................................................43

2.1 Системы итерированных функций и их численные реализации.........43

2.2 Основные свойства генерируемых множеств........................................58

2.2.1 О мощности генерируемых множеств............................................58

2.2.2 Разрешимость полученных множеств.............................................61

2.2.3 О совершенстве фрактальных множеств........................................68

2.2.4 Исследование сходимости процедур РСИФ..................................70

2.3 Оценка параметров рандомизированных систем итерированных функций....................................................................................................72

2.3.1 Оценивание параметра д по методу моментов..............................72

2.3.2 Оценивание множества точек протофрактала...............................75

3 Приложения фрактальной теории в решении классификационных задач ...................................................................................................................81

3.1 Оценка фрактального характера типологии стран мировой экономической системы..........................................................................81

3.2 Использование фрактальных подходов в построении районированной выборки...................................................................................................107

Заключение......................................................................................................119

Список литературы.......................................................................................121

Приложения.....................................................................................................136

ВВЕДЕНИЕ

Актуальность темы.

В настоящее время теория фракталов является одной из наиболее актуальных и стремительно развивающихся теорий, которые находят самое широкое применение в различных областях деятельности человека. Использование фрактальных моделей позволило значительно продвинуться в решении различных практически значимых задач как обработка цифровой информации, изучение вопросов турбулентного движения жидкостей, исследовании финансовых рынков, получении новых наноматериалов с заданными свойствами, в радиолокации и пр. Значительный вклад в развитие фрактальной теории был внесен такими зарубежными учеными; как Mandelbrot В., Barnsley M.F., Crownover R.M., Devaney R.L., Falconer К., Schroeder M. и др. В России этими проблемами занимались С.В. Божокин, А.Д. Морозов, В.П. Паршин, А.А. Потапов, Б.М. Смирнов и другие.

Интенсивное развитие теории фракталов не только выдвигает новые вопросы, но и позволяет искать подходы к задачам, ранее сформулированных, но не получивших до настоящего времени удовлетворительных решений. Одной из таких задач является классификационная задача. Изучению проблем, связанных с этой задачей, были посвящены работы С.А. Айвазяна, В.М. Буш-табера, А.А. Дорофеюка, Ю.И. Журавлёва, Н.Г. Загоруйко, И.И. Елисеевой, А.И. Орлова и др. Важность классификационной задачи обусловлена как широким спектром её практических приложений, так и той ролью, которую играет эта задача в теориях распознавания образов и искусственного интеллекта. Предлагаемый в диссертационной работе подход к решению указанной выше задачи основывается на современных представлениях фрактальной теории и вместе с тем в значительной степени учитывает уже накопленный опыт и полученные ранее результаты.

В связи с этим тема диссертационной работы, посвященная моделированию решений классификационной задачи в рамках фрактальной теории, является актуальной.

Диссертационная работа выполнена в соответствии с перспективным планом научно-исследовательских работ ФГБОУ ВПО «Воронежский государственный аграрный университет имени императора Петра I» по теме ««Построение и численная реализация новых математических моделей технологических и производственных процессов в АПК», номер государственной регистрации 01.200.1003987.

Целью работы является разработка и исследование процедуры генерирования фрактальных данных, позволяющих аппроксимировать эмпирические структуры многомерных данных в классификационных задачах.

Для достижения поставленной цели сформулированы следующие задачи:

1) анализ современных алгоритмов кластерного анализа с целью исследования возможностей применения теории фрактальных множеств в задачах классификации;

2) разработка алгоритма моделирования многомерных фрактальных структур на основе численного метода построения фрактальных множеств, оценка характеристик РСИФ-алгоритма, а также свойств множеств, порождаемых предложенным алгоритмом;

3) разработка программного комплекса средствами языка программирования статистической обработки данных Я для проведения вычислительного эксперимента и исследования структур многомерных данных на основе фрактальных моделей, полученных с использованием предложенных алгоритмов;

4) тестирование разработанного программного обеспечения при решении содержательных прикладных задач.

Объект исследования - фрактальные структуры многомерных данных, полученные с помощью кластерного анализа и применения алгоритмов, в основе которых лежит фрактальный подход.

Предмет исследования - процедура, основу которой составляют рандомизированные системы итерированных функций (РСИФ), позволяющая при решении классификационных задач воспроизводить структурные особенности многомерных данных.

Методы исследования. В работе использованы методы и средства системного анализа, теории вероятностей, математической статистики и прикладного статистического анализа, теории фрактальных множеств, имитационного моделирования и теории оптимизации.

Научная новизна и значимость результатов диссертационной работы.

1. Представлен способ моделирования многомерных фрактальных структур, отличающийся от стандартных методов построения фрактальных множеств использованием процедуры, основанной на обобщении задачи об определении суммы ряда со случайной расстановкой знаков.

2. Разработан численный метод аппроксимации многомерных данных, отличающийся от известных тем, что основан на моделях фрактальных множеств," порождаемых рандомизированными системами итерированных функций.

3. Предложена модификация метода выделения эталонных объектов в классификационных задачах, отличительной чертой которой является учет системных свойств классифицируемой совокупности, что позволяет дать новую интерпретацию типичных объектов в рамках системного подхода.

4. Создан и апробирован метод моделирования многомерных фрактальных структур с помощью рандомизированных систем итерированных функций, реализованный в виде библиотеки прикладных программ «RIFS: Random Iterated Function System», написанной средствами языка статистической обработки данных и программирования R.

Теоретическая и практическая значимость. Теоретическая значимость диссертационной работы заключается в том, что предложенный фрактальный подход позволяет глубже исследовать механизмы формирования структуры многомерных данных и методы выделения типичных объектов в рамках системного подхода.

Практическая значимость результатов диссертационного исследования состоит в том, что на основе разработанных алгоритмов и методов становится

возможным описание механизмов формирования многомерных фрактальных структур и проверка гипотез о соответствии между генерируемыми и эмпирическими данными. В перспективе развитие данных методов позволит осуществить прогноз эволюции системы исследуемых данных.

Основные научные результаты диссертационного исследования могут быть использованы для оценки фрактальных свойств эмпирических данных, а также при решении задач, связанных с построением районированных (стратифицированных) выборок, которые широко применяются при социологических исследованиях.

Исследование фрактальности изучаемой структуры влечет за собой установление её критических состояний, что может найти применение при решении задач управления, связанных с прогнозированием и количественным описанием состояний открытых экономических систем, для своевременного принятия мер при планировании и антикризисном управлении.

Результаты диссертационной работы могут быть использованы в учебном процессе на экономических факультетах вузов при изучении дисциплин «Эконометрика», «Методы принятия управленческих решений », «Методы исследования в менеджменте» а также в специальных курсах подготовки магистров по экономическим специальностям.

Теоретическая часть диссертации основана на использовании современных методов дискретной математики, теории вероятностей и теории фракталов. Адекватность разработанных математических моделей и проведенных вычислительных экспериментов подтверждается сопоставлением результатов теоретических исследований с результатами эмпирических исследований на реальных объектах.

Апробация работы. Материалы диссертационной работы докладывались и обсуждались на следующих международных и всероссийских научных конференциях: Международная конференция «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2010); XI и XII Международные научно-практические конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2011, 2012); V Международная научно-практическая конференция «Социологические методы в современной исследовательской практике» (Москва, 2011); Международная научно-практическая конференция «Математика и ее приложения (Орёл, 2011); XII Международная молодежная научная конференция «Севергеоэкотех- 2011» (Ухта, 2011); Воронежская зимняя математическая школа С.Г. Крейна-2012 (Воронеж); III, VI, VIII Международные конференции «Экономическое прогнозирование: модели и методы» (Воронеж, 2007, 2010, 2012); Всероссийская научно-практическая конференция «Современные проблемы и перспективные направления развития комплексов и систем военного назначения, форм и способов их боевого применения» (Воронеж, 2011).

Публикации. По результатам исследования опубликовано 22 научных работы, в том числе 2 самостоятельно; 4 - в научных журналах и изданиях, которые включены в перечень рецензируемых научных журналов и изданий для опубликования основных результатов диссертаций. Личный вклад автора в этих работах, состоит в следующем: 1) разработка и реализация алгоритмов [1]; 2) исследование свойств множеств, генерируемых рандомизированными системами итерированных функций [2]; 3) получение и интерпретация результатов решения классификационных задач [3,4].

Структура и объем работы Диссертационная работа изложена на 146 страницах компьютерного текста и состоит из введения, 3 глав, заключения, списка литературы из 180 наименований, включает 2 приложения, 21 рисунков и 7 таблиц.

В первой главе проводится обзор методов кластерного анализа, рассматривается постановка классификационной задачи, ее математическая формули-

ровка. Обсуждаются особенности метрики в признаковом пространстве, классификационные алгоритмы, их свойства, достоинства и недостатки.

Наряду с этим были представлены результаты построения различных фрактальных множеств. Выявленные сходства классификационных структур и генерируемых фрактальных множеств позволили выдвинуть предположение о возможности аппроксимации классификационных разбиений фрактальными образованиями.

Во второй главе рассмотрена реализация рандомизированной системы итерированных функций. Предложенный метод отличается от стандартных тем, что изучаемое множество может быть аппроксимировано с помощью фракталов. Исследуются свойства, помогающие оценивать точность аппроксимации.

В третьей главе описаны вычислительные эксперименты в ходе практического применения фрактального подхода к анализу результатов классификационных разбиений. Проиллюстрировано, каким образом с помощью генерирования фрактального множества можно «увидеть» структуру данных, выделить типичные объекты с точки зрения системного подхода.

В заключении приведены основные результаты диссертационной работы, указаны перспективные направления дальнейших исследований.

1 МЕТОДЫ МНОГОМЕРНОЙ КЛАССИФИКАЦИИ И ФРАКТАЛЬНОГО АНАЛИЗА В ТИПОЛОГИЧЕСКИХ ЗАДАЧАХ

1.1 Понятие многомерной классификации. Общая постановка задачи

За время своего существования человечество накопило огромный потенциал знаний в различных сферах деятельности, в том числе и научной. Эти знания содержат множество объектов для изучения. Они могут быть представлены в виде элементов, предметов или явлений.

Наиболее характерно для инстинктивных действий человека - это желание разложить все по своим местам (желание, чтобы каждый предмет имел свое место), определить положение каждого объекта в каком-либо классе. По мнению ученых [162], каждому индивиду в процессе его деятельности свойственно классифицировать предметы, явления, события. Это дает ему основное преимущество для выживания, постепенно вырабатывая определенную систему, позволяющую справиться со сложностью окружающего мира. Классифицирование - это один из элементов мыслительной деятельности, которое выступает как метод освоения действительности, без которого невозможно дальнейшее развитие познания.

Классифицируя различные явления, их можно разбить на группы, эти группы вновь разделить, т.е. логическая операция, которая ведет к разбиению элементов, какого-либо множества на классы, виды или типы по интересующему одному или нескольким признакам, является классификацией. Понимать под этим словом будем состоявшуюся систему знания, понятия которой означают упорядоченные группы, по которым распределены объекты некоторой предметней области на основании их сходства в определенных свойствах [139]. Классификация играет огромную роль в систематизации любой области человеческой деятельности, позволяя обнаруживать закономерности, устанавливать связи между объектами, определять местоположение классов в системе [56, 57]. При этом надо четко уяснить, что описание объектов не является их классификацией.

Классификацию от описания отличает наличие множества установленных групп подобных объектов, оснований, по которым объекты объединяются в группы, принципов или закона, согласно которому все группы соединяются, организуются в единую систему [139]. Поэтому содержательно интерпретируемую классификацию будем называть типологией или типологическим анализом.

При составлении классификации необходимо уделить внимание ее видам, о существовании которых писали многие ученые, в том числе создатели знаменитых систем классификации: Линней и Бэр, Бутлеров и Менделеев, Ветт-штейн и Майр.

Различают вспомогательную (искусственную) и естественную классификацию.

Искусственная классификация создается в целях регистрации и удобного распознавания классифицируемых объектов, а также служит для придания изучаемому множеству необходимого порядка. Примером может служить справочник номеров, где разбиение на группы будет зависеть от того, на какую букву начинается фамилия абонента.

Естественную классификацию выделяют по существенным признакам, характеризующим внутреннюю общность предметов и явлений. Применяется в целях выявления полноты их существенных свойств и связей, постижения природы изучаемых объектов, получения о них максимальной информации [139]. Известными примерами естественных научных классификаций являются: в химии - периодическая система элементов Д.И. Менделеева, в биологии - классификация животных и растений К. Линнея. Хорошо известны классификации кристаллов A.B. Шубникова, элементарных частиц - в современной физике и др. Эти работы в значительной мере подвинули развитие различных направлений в соответствующих науках. В отличие от точных наук, классификации отводится огромная роль в дальнейшем изучении и развитии неформализованных знаний.

В свою очередь классификация может быть одномерной (по одному признаку) и многомерной (по двум и более признакам). Многомерная классификация была разработана биолог�