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

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

КЛИМОВА АНЖЕЛИКА СЕРГЕЕВНА

МОДЕЛИ И МЕТОДЫ ГИБРИДНОЙ РЕЛЯЦИОННОЙ КЛАСТЕРИЗАЦИИ ДАННЫХ

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

АВТОРЕФЕРАТ

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

13 , :;0Ч ¿У 13

Казань-2013

005061691

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

Научный руководитель: доктор физико-математических наук, профессор, заслуженный деятель науки Республики Татарстан Батыршин Ильдар Закирзянович

Официальные оппоненты: Ярушкина Надежда Глебовна, доктор технических наук, профессор, заведующий кафедрой «Информационные системы» ФГБОУ ВПО «Ульяновский государственный технический университет»

Ибятов Равиль Ибрагимович, доктор технических наук, профессор, заведующий кафедрой прикладной информатики и математики ФГБОУ ВПО «Казанский государственный аграрный университет»

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

университет», г. Тверь

Защита состоится 28 июня 2013 года в 16.00 часов на заседании диссертационного совета Д 212.080.13 при Казанском национальном исследовательском технологическом университете по адресу: 420015, г.Казань, ул. К. Маркса, 68, зал заседаний Ученого совета (А-330).

Отзыв на автореферат в двух экземплярах, заверенный гербовой печатью, просим направлять по адресу: 420015, г. Казань, ул. К. Маркса, 68, Казанский национальный исследовательский технологический университет, ученому секретарю диссертационного совета Д 212.080.13.

С диссертацией можно ознакомиться в фундаментальной библиотеке Казанского национального исследовательского технологического университета. Автореферат разослан 28 мая_2013 г.

Ученый секретарь диссертационного Клинов

совета Д 212.080.13, доктор Александр Вячеславович

технических наук, профессор

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

Актуальность. Кластеризация данных играет большую роль в анализе данных в технике, в экономике, в социальных науках, биологии, геологии, астрономии и в других научных областях. Кластеризация позволяет представить исследуемые данные в виде разбиения на классы сходных объектов, что является одним из важных этапов формирования знаний об исследуемой предметной области, ее моделирования и анализа. Но структура реальных данных не всегда может быть адекватно представлена в виде разбиения на классы сходных объектов, также данные могут допускать различные разбиения на классы сходных объектов, кроме того, помимо структуры классов сходства, формируемой кластерным алгоритмом, часто желательно выявить дополнительную информацию о связях между объектами. Поэтому актуальной является задача разработки гибридных методов кластеризации, дающих новые методы представления структуры данных на основе кластерного анализа. В настоящее время активно развиваются методы сочетания нескольких кластерных процедур, методы комбинирования кластеризации с визуализацией данных и др. [Strehl, Jain, Murty, Babu, Крускал, Ярушкина и др.]. При этом важным является использование кластерных алгоритмов, удовлетворяющих условиям инвариантности относительно исходной нумерации (перестановки) кластеризуемых объектов и инвариантности относительно монотонных преобразований значений сходства [Jardine, Johnson, Батыршин и др.]. К сожалению, эти условия инвариантности не выполняются для большинства известных кластерных алгоритмов. Поэтому важной является задача разработки гибридных кластерных алгоритмов, удовлетворяющих указанным условиям инвариантности. В работах Батыршина И.З. и др. разработана реляционная схема иерархических инвариантных процедур кластеризации, основанная на преобразовании заданного взвешенного отношения сходства во взвешенное (нечеткое) отношение эквивалентности, определяющее иерархию разбиения множества объектов на кластеры определенного типа. Перспективной является задача расширения этой схемы для выделения кластеров новых типов и разработки гибридных кластерных процедур на ее основе.

Цель работы: Разработка моделей, методов и комплекса программ гибридной кластеризации данных на основе реляционных инвариантных процедур кластеризации.

Автор выражает благодарность к.т.н. Богомолову В.А. за помощь, оказанную при работе над диссертацией.

Задачи исследования.

1. Теоретическое исследование свойств реляционной схемы инвариантных иерархических кластерных процедур с целью исследования возможности ее расширения на новые типы кластеров.

2. Разработка и реализация новых реляционных инвариантных процедур иерархической кластеризации.

3. Разработка методов гибридной кластеризации на основе реляционных кластерных процедур.

4. Создание комплекса программ гибридной реляционной кластеризации данных.

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

Научная новизна работы.

1. Получено теоретическое обоснование реляционной схемы инвариантных иерархических кластерных процедур.

2. Предложено расширение реляционной схемы инвариантных иерархических кластерных процедур, содержащее новые кластерные процедуры.

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

4. Разработаны численные методы поиска оптимальных представлений данных в виде кластеров и визуализации этих кластеров.

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

Практическая значимость работы состоит в разработке в среде МАТ-ЛАБ пакета программ гибридной реляционной кластеризации данных, позволяющего исследовать инвариантные структуры сходства в задачах кластеризации данных и анализа структуры систем, в разработке методов визуализации и гибридной кластеризации данных, в разработке методов анализа взаимодействия скважин нефтяного месторождения на основе данных добычи нефти и сопутствующей воды. Результаты работы внедрены в Институте проблем информатики АН РТ, Министерстве образования и науки РТ и введены в состав учебной дисциплины СД.04 "Нечеткая логика и мягкие вычисления" на кафедре информатики и прикладной математики Казанского государственного технологического университета.

Апробация работы. Основные положения и результаты работы обсуждены на международых конференциях "East West Fuzzy Colloquium" (Германия, Циттау, 2002, 2006) и "Fuzzy Sets and Soft Computing in Economics and Finance" (Санкт-Петербург, 2004, 2006), на П Всероссийской научно-

технической конференции "Проблемы информатики в образовании, управлении, экономике и технике" (Пенза, 2002), III Международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2005), на Всероссийской конференции "Нечеткие системы и мягкие вычисления" (Тверь, 2006).

Публикации результатов работы. Основные выводы и положения диссертации изложены в 17 печатных работах. Среди них 3 статьи в журналах из перечня ВАК, 8 - в материалах конференций, 6 - в журналах и сборниках научных работ академических и центральных изданий.

Ряд результатов диссертационной работы получен в рамках проектов фонда НИОКР и АН РТ (05-5.2-173/2002) и РФФИ (03-01-96-245-р200) по теме "Разработка методов моделирования процессов и систем на основе нечеткой логики, нечетких отношений и нейронных сетей", 02-01-00092-а "Разработка моделей и методов вычисления словами на основе гранулирования информации о нечетких зависимостях и оптимизации нечетких моделей по параметрам операций", а также совместных исследований с учеными Мексиканского нефтяного института.

Структура и объем работы.

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, изложенных на 105 страницах машинописного текста. Содержит 3 таблицы, 18 рисунков, список литературы из 96 наименований.

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

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

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

Задача гибридной кластеризации в реляционной форме формулируется в данной работе следующим образом. Пусть X - множество исследуемых объектов, S - отношение сходства, заданное на X, (S может быть получено из матрицы расстояний между объектами), RC - множество обыкновенных или взвешенных (нечетких) отношений на X, содержащее отношение эквивалентности, PC - множество описаний элементов из X в пространствах различной размерности. Гибридной реляционной кластеризацией X называется преобразование

HC(S) = <RC; PO. (1)

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

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

В качестве исходной информации для кластерной процедуры рассматривается взвешенное отношение сходства 8:ХхХ—>Я, где X - множество из п объектов, Я- [0,1], I - некоторое положительное вещественное число, и 5 удовлетворяет условиям рефлексивности: 8(х,х) = I, и симметричности: Б(х,у)=8(у,х) для всех х,у из X. Взвешенное отношение сходства называется взвешенным отношением эквивалентности, если оно удовлетворяет условию (к/^-транзитивности: Б(х,2)>Б(х,у) у8(у,г) для всех х,у из X.

Для любого значения (уровня) а из Л взвешенное отношение 5 определяет отношение уровня и взвешенное отношение Ба следующим образом: $[аг{(х,у)еХ | Б(х,у)>а}; 8а(х,у)=\, если8(х,у)>а; 8а(х,у)=0, если Б(х,у)<а.

Подмножество А множества X называется классом сходства отношения сходства 5 наX, если Б(х, у)>8(х, г) для всех х, уеАигёА.

Утверждение 1. Множество классов сходства взвешенного отношения эквивалентности 5 совпадает с множеством классов эквивалентности отношений уровня Б[а], аеЯ.

Реляционная схема иерархических кластерных процедур, удовлетворяющих условиям инвариантности относительно исходной нумерации объектов и инвариантности относительно монотонных преобразований значений сходства, была введена в работах Батырппша И.З. Схема (1) для данного случая имеет вид: #С(5') = <Е; 0>, где Е - взвешенное отношение эквивалентности. Преобразование НС(Б) задается процедурой кластеризации ()(8)=Е, которая определяется так: Е = (2(Б) - ТС(Р(Б)), где Г это некоторая "коррекция" данного отношения сходства 5 такая, что Р(Б)с£>, и ТС обозначает процедуру транзитивного замыкания значений отношения сходства.

Утверждение 2. Отношение сходства 8, определенное на X, будет взвешенным отношением эквивалентности тогда и только тогда, когда все объекты в 5 неразличимы в 5.

Утверждение 3. Для кластерных процедур 2 с тождественными функциями Л ~/з выполнено (2(Б)=8 тогда и только тогда, когда 5 -взвешенное отношение эквивалентности.

Утверждение 4. Кластерные процедуры из представленной схемы "сохраняют классы сходства", если функции fj и f2, используемые в этой процедуре, суть тождественные функции.

В разделе 2.5 описывается новый метод, основанный на идее "обрыва мостов между кластерами". Эта кластерная процедура использует другой тип множества поддерживающих точек. Вместо функции сходства S будем использовать функцию различия DXxX->[0,1], удовлетворяющую на X условиям: D(y,x) = D(x,y), D(y,y) = 0. Если D удовлетворяет на X ультраметрическому неравенству, двойственному (V,/^-транзитивности: D(x,y) < max{(D(x,z),D(z,y)}, то D называется ультраметрикой.

Две точки считаются точками из "моста", если отсутствуют поддерживающие точки "вдоль граней моста", соединяющего эти точки. Дополнительно к отсутствию поддерживающих точек мы используем также некоторое топологическое восприятие точек моста. Этот метод использует следующие множества: V*y(xMzeVy(x)\f2(D(x, y))<D(x, z)},

V*x(y) ={zeV<(y) \f2(D(x, y))< D(y, z)}, mef2(D(x,y)) <fi(D(x,y)). Множество поддерживающих точек ^определяется равенством: W(x, у)= V*y(x)n V*x(y). Определение топологии точек мостов использует следующие множества:

U(x)={zeX\{x, у}| D(x, z)<f3(D(x, у))}, U(y)={zeX\{x, y}\D(y, z)<f3(D(x, y))}.

Мы будем говорить, что точки хну различны на уровне к, если Н(х, у)>к, где Н(х,у) = abs(\U(x)\-\U(y)\), и к- некоторый параметр. Процедура коррекции выглядит следующим образом:

штм Ъ И*'^)' если W{x,y)\>t или Н{х,у)>к, у), в остальных случаях,

где / - некоторый параметр и F/x, у) определяется коррекциями, описанными выше для значений j=l, 2, 3.

В разделе 2.6 изложен, разработанный в диссертации новый метод гибридной кластеризации, сочетающий инвариантную кластеризацию с визуализацией сильных связей между объектами. Идея метода заключается в визуализации сильных связей между объектами в виде графа сходства таким образом, что объекты с взаимным сходством не меньше, чем некоторый уровень сходства а, были соединены ребром. Уровень сходства выбирается из соображений минимизации расхождения графа сходства с полученной кластеризацией. Способ нахождения оптимального уровня а определяется ниже. Обозначим Et характеристическую функцию отношения эквивалентности Е:

il, если (x,y)sE Ех{х,у) = \

[О, в противном случае

Пусть А!"содержит «х объектов. Обозначим Ыа = пх общее

х,уеХ

число «сильных» связей 8а(х,у)- 1 в 5а за вычетом рефлексивных связей Ба(х,х)= 1. Пусть {Аи---Ж} - классы эквивалентности (кластеры) отношения Е, содержащие по п\,...,пи объектов, соответственно. Обозначим

г

к-Л

I,Sa(x,y) *.УеАк

-пх - тесло внутри-кластерных сильных связей

отношения Sa. Тогда Na=Na-равно числу межкластерных сильных

связей. Обозначим N% = (х,у)-пх число связей в за вычетом

х.уеХ

рефлексивных связей. В гибридной процедуре кластеризации оптимальное значение а выбирается таким образом, чтобы минимизировать число рассогласований между сильными связями в Sa и сильными связями в Ех: G = NE-N+ + N-=NE+NA -2 N+.

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

Задача визуализации рассматривается как задача минимизации искажений исходных расстояний между объектами, при их представлении в двух-или трехмерном пространстве. В работе предложено применение генетического алгоритма оптимизации. Схема (1) имеет вид: HC(S) = <0; Р>, где Р задает координаты объектов в двух- или трехмерном пространстве.

Рассмотрим процедуру двумерной визуализации данных. Предположим, что R — расстояние между объектами л-мерного пространства признаков М, п>3. Ищем двумерное представление этих объектов. Генерируем начальную матрицу координат объектов в двумерном пространстве с осями XwY. Основываясь на этой матрице, с помощью стандартной процедуры оптимизации определяем матрицу координат Р объектов с минимальной ошибкой аппроксимации начальной матрицы D расстояниями матрицы R, вычисленными для матрицы координат Р. Обычно полученное представление дает локальный оптимум. Затем определяем два объекта а(ах, ау) и Ь(Ь„ by) из множества М, с максимальным значением R(a, b). Систему координат <Х, Y> перемещаем и поворачиваем так, чтобы центр «новой» системы координат <Х\ Y> находился в точке a, a точка b располагалась на оси X.

Перемещение объектов осуществляется параллельным переносом вдоль оси X на величину -ах и вдоль оси Y на величину -аг Затем осуществляется поворот системы координат на угол между вектором (а, Ь) и осью X.

Затем выбираем объект с с максимальным по абсолютной величине значением уа в зависимости от значения координаты по оси У которого осуществляется зеркальное отображение всех объектов относительно оси У. Объекты а, Ь, с будут опорными элементами для всех последующих матриц координат объектов. Полученную матрицу координат Р* объектов из М назовем решением и ошибку аппроксимации матрицы Б матрицей расстояний 7?, вычисленной на основе матрицы координат Р*, назовем ошибкой решения.

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

Для каждой матрицы из элиты применяем перемещение и поворот относительно опорных точек а, Ь, с так, чтобы их расположение было таким же, как и в матрице Р*. Полученные решения затем используем для генерации новых решений, называемых потомками. Потомков получаем в результате применения следующих шагов. Из элиты случайным образом выбирается пара решений («родители»), которые впоследствии используются для построения новых решений («потомков») с помощью операций рекомбинации и мутации, осуществляемых следующим образом.

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

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

Новая популяция получается с помощью добавления к старой элите: 1) потомков, полученных применением операции рекомбинации к старой элите; 2) потомков, полученных из элиты применением операции мутации; 3) потомков, полученных с помощью применения мутации после применения операции рекомбинации к старой элите.

Для новых элементов элиты, определяющих матрицы координат объектов в двумерном пространстве, вычисляются матрицы расстояний и ошибка аппроксимации исходной матрицы расстояний в и-мерном пространстве. Новая элита выбирается из полученной популяции следующим образом: половина элиты состоит из наилучших решений популяции, а вторая половина выбирается из популяции случайным образом. Для новой элиты повторяются все шаги, описанные выше. Генерация популяции повторяется заданное число раз или до тех пор, пока ошибка аппроксимации не будет меньше заданного значения.

Поиск трехмерного представления объектов осуществляется по аналогичной схеме. Отличие данного метода состоит в том, что в данном случае

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

Рассмотрим структуру генетического алгоритма для двумерного представления результатов классификации.

Рассмотрим первый этап алгоритма. Если кластер состоит из двух объектов, то эти объекты получают координаты (0, 0) и (с1, 0), соответственно, где в. есть расстояние между этими объектами в и-мерном пространстве. Если кластер состоит более чем из двух объектов, то к множеству этих объектов применяется генетический алгоритм, описанный выше.

На втором этапе расстояния между двумя классами, которые объединяются вместе в кластерной процедуре, оптимизируются следующим образом. Координаты объектов из одного из них остаются неизменными. Этот класс будем называть фиксированным классом. Второй класс будем перемещать, так чтобы расстояния между объектами внутри этого класса, полученные на первом этапе, не изменялись. Этот класс будем называть перемещаемым классом. Координаты объектов из этого класса изменим следующим образом: Хяеи,= Х*соа(А)+У*5т(А)+с1Х, У„с,„= -Х**1п(А)+У*сои(А)+(1У, где X* У* - это координаты объектов в двумерном пространстве до перемещения класса, Хпет Упт - координаты объектов после перемещения, с1Х, <1У-величины сдвига объектов вдоль осей X и У, А - угол поворота класса вокруг начала координат. Строка параметров (ЛХ, ¿У, А) представлена как элемент популяции в генетическом алгоритме.

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

Х^ = X* соб( А) + У* зш(Л) + ах, У'=-Х* Бт( А) + У* со з(А)+с/У, = У'соз(А)+2 * бшСЛ)+¿У, 2^ = -Гзт(Л)+2* соб(Л) + ¿2, где X, У, 2 суть ЗБ координаты объектов до перемещения класса, Хпт., Уппл 2„еуг — координаты объектов после перемещения, (ИХ, йУ, ей?- значения сдвига объектов из перемещаемого класса вдоль осей X, У, 2, А - угол поворота класса. Строка параметров (¿X, с1У, <12, А) рассматривается как элемент популяции в генетическом алгоритме.

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

плекс программ гибридной кластеризации реализован в пакете МаШЬ. На рис 1. представлена совокупность методов, реализованных в этом пакете (обозначены М1-М7).

Разбиение исходного множества объектов на классы осуществляется инвариантными процедурами реляционной иерархической кластеризации (М1, М2), описанными в главе 2. Для представления исходного множества объектов в пространстве размерности два или три используются эволюционные процедуры двух- и трехмерной визуализации данных (МЗ, М4) из разделов 3.2 и 3.3. Метод гибридной кластеризации с визуализацией сильных связей между объектами (М5), из раздела 2.6, позволяет анализировать отклонения полученной кластеризации от структуры данных. Эволюционные процедуры двух- и трехмерной визуализации результатов кластеризации (Мб, М7) из разделов 3.4 и 3.5 позволяют дополнить кластеризацию объектов визуализацией их взаимного расположения.

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

Рис. 1

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

АМ(у,х) = тах^^^у,*)) = тах(соз54(з;,д:)), где К = {2,3} задает

кеК

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

для значения порога 0,468. Это значение равно величине ассоциации между нагнетающей скважиной П и добывающей скважиной 2р. Выбор такого порога для представления ассоциативного графа дает нетривиальное разбиение графа на связные компоненты и позволяет выявить ассоциации между нагнетающими и добывающими скважинами. Вершины ассоциативной сети расположены так, чтобы минимизировать пересечения дуг. В соответствии с этим порядком приведены также временные ряды на Рис.2, что позволяет увидеть сходство между формой временных рядов с высоким значением ассоциации локальных трендов (например между 6р и 6а, Зр и За, 1\ и 6а).

Рис.2

На Рис. 4 представлены результаты гибридной кластеризации скважин на основе меры ассоциаций локальных трендов. Две скважины X и У считаются взаимосвязанными, если существует значимая ассоциативная связь между хотя бы одной парой временных рядов (Ха, У а), (Ха, Ур), (Хр,Уа), (Хр, Ур). Получено следующее разбиение скважин на 5 кластеров: {И},{2,3,4,9},{5},{6,71},{8}. На Рис. 4 одиночные кластеры помечены кружком, а скважины из кластеров {2,3,4,9} и {6,71} квадратом и ромбом соответственно. Значимые ассоциативные связи между скважинами (5, 3 и Н, 2), принадлежащим разным кластерам, показаны пунктиром. Интерпретация полученных результатов позволяет судить о характере взаимодействия между скважинами рассматриваемого месторождения. В частности, установлено хорошее взаимодействие между нагнетающей скважиной 7 и добывающей скважиной 6, объединенными в один кластер, что может объясняться высокой проницаемостью пластов в окрестности этих скважин. Отсутствие значимого взаимодействия между скважиной 8, попавшей в одиночный кластер, и другими скважинами, может характеризоваться разными приничами, и ввиду этого служить основой для дополнительного анализа свойств пород вокруг этих скважин. Объединение скважин 2, 3, 4, 9 в один кластер также может

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

Метод сочетания иерархической кластеризации с одномерной визуализацией данных по некоторому показателю был использован в задаче анализа уровня потребления электроэнергии странами бывшего Советского Союза за 1992-2004 [World Energy Consumption in Standard U.S. Physical Units. http://www.eia.doe.gov/iea/wec.html.]. Рассмотрим применение метода гибридной кластеризации для анализа данных по потреблению гидроэлектроэнергии (World Net Hydroelectric Power Consumption). На Рис. 5 представлены результаты иерархической кластеризации временных рядов потребления гидроэлектроэнергии методом Ml. В качестве расстояния между временными рядами использовалось Евклидово расстояние между ними.

Рис.3

Рис.4

0.0122

Э.ЦИиэпа 10.Moldova

о 7.Kvrgyzstan о 14.Ukraine о e.Kazakhstan 15. Uzbekistan 5.Georgia

Рис. 5

Рис. 6

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

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

Основные результаты работы и выводы

1. Разработана общая схема гибридной реляционной кластеризации.

2. Получено обоснование реляционной схемы инвариантных иерархических кластерных процедур и разработана новая инвариантная иерархическая кластерная процедура этой схемы.

3. Разработаны методы построения моделей данных в виде инвариантных кластеров сходных объектов, сетей сходства и их визуализация в двухмерном и трехмерном пространствах.

4. Разработан пакет программ гибридной кластеризации данных в среде МаЙаЬ.

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

6. Алгоритмы визуализации позволяют представить многомерные данные в пространстве размерности два или три с ошибкой аппроксимации исходной матрицы расстояний матрицей расстояний двумерного или трехмерного представления объектов, меньшей чем ошибка аппроксимации представления, полученного другими методами (например, методами неметрического шкалирования, методами оптимизации (разделы 3.2 и 3.3)).

Основные результаты работы представлены в публикациях Публикации в рецензируемых научных журналах и изданиях Перечня ВАК

1. Климова A.C. Гибридная кластеризация на основе реляционной схемы инвариантных кластерных процедур/Батыршин И.З., Климова А.С.//Вестник Тверского государственного университета. - 2007. - вып. 7 - С. 27-42. - Серия: Прикладная математика.

2. Климова A.C. Методы гибридной реляционной кластеризации в анализе среднего потребления электроэнергии странами бывшего Советского Союза/Климова А.С.//Известия высших учебных заведений. Проблемы энергетики. -2008. - вып. 5-6 - С. 124-127.

3. Климова A.C. Применение методов гибридной кластеризации к анализу нефтяных скважин/ Климова A.C., Батыршин И.З., Шайдуллина Н.К.//Вестник Казанского технологического университета. - Казань, 2013,-Т. 8.-С.241-245.

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

4. Батыршин И.З. О визуализации результатов классификации/ Батыршин И.З., Климова А.С//Труды Международн. научно-технических конференций «Интеллектуальные системы (IEEE AIS'03» и «Интеллектуальные САПР (CAD-2003)» - Москва: Физматлит, 2003. - Т. 2 - С. 172-177.

5. Батыршин И.З. Эволюционные процедуры иерархической двухмерной визуализации данных/ Батыршин И.З., Климова А.С//В сб.: Исследования по информатике. Институт проблем информатики АН РТ. - Казань, Отечество, 2004. - N 7 - С. 119-124.

6. Батыршин И.З Инвариантные кластерные процедуры, основанные на нечетком отношении сходств/ Батыршин И.З., Климова А.С//В. кн.: Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сб. научн. трудов Ш-го Межд. научно-практич. семинара - Москва: Физматлит, 2005 - С. 119 -125.

7. Батыршин И.З. Гибридная реляционная кластеризация и визуализация данных/ Батыршин И.З., Климова А.С//Труды Всеросс. научн. конф. по нечетким системам и мягким вычислениям, НСМВ-2006. - Москва: Физматлит, 2006 - С. 193-209.

8. Батыршин И.З. Преобразование скользящих аппроксимаций и ассоциативные сети в сравнительном анализе статистических рядов динамики/ Батыршин И.З., Шереметов Л.Б., Панова A.M., Климова А.С.//В сб.: Исследования по информатике. Институт проблем информатики АН РТ -Казань, Отечество, 2006. - вып. 11 - С. 35-48.

9. Батыршин И.З. Анализ взаимодействия нефтяных скважин на основе гибридной кластеризации временных рядов продуктивности скважин/ Ба-

тыршин И.З., Кошульски А., Шереметов Л.Б., Климова A.C., Панова А.М.//Нечёткие системы и мягкие вычисления. - 2007. - том 2, №4 - С. 63-73.

Публикации в трудах международных и Российских конференций

10. Батыршин И.З. О визуализации многомерных данных/ Батыршин И.З., Климова А.С.//в кн.: Проблемы информатики в образовании, управлении, экономике и технике. II Всероссийская научно-технич. конф. - Пенза,

2002. - С. 156 - 158.

11. Batyrshin I.Z. New invariant relational clustering procedures/ Batyrshin I.Z., Klimova A.S.//In: Proceedings of East West Fuzzy Colloquium 2002, 10th Zittau Fuzzy Colloquium - Zittau, Germany, 2002 - P. 264 - 269.

12. Batyrshin I.Z. On two dimensional visualization of hierarchical cluster-ing/Batyrshin I.Z., Klimova A.S., Sheremetov L.B.//In: IEEE International Conference on Computational Cybernetics, ICCC 2003. - Siofok, Hungary,

2003.-P. 337-342.

13. Батыршин И.З. Трехмерная визуализация результатов кластериза-ции/Батыршин И.З., Климова A.C.//XIV Международная научно-техническая конференция «Математические методы и Пенза, 2004. - С. 272-275.

14. Klimova A.S. Evolutionary procedures of visualization of multidimensional data./Klimova A.S.//In: FSSCEF 2004, Proc. Intern. Conf. on Fuzzy Sets and Soft Computing in Economics and Finance - St. Petersburg, Russia, 2004. -vol. I - P. 130- 139.

15. Batyrshin I.Z. On general scheme of invariant clustering procedures based on fuzzy similarity relation./Batyrshin I.Z., Rudas Т., Klimova A.S.//In: FSSCEF

2004. Proc. Internat. Conf. on Fuzzy Sets and Soft Computing in Economics and Finance - St. Petersburg, Russia, 2004. - vol. I - P. 122-129.

16. Batyrshin I.Z. Combining local trend association network and clustering in visualization of relationships in time series data bases./ Batyrshin I.Z., Klimova A.S., Sheremetov L.B., Velasco-Hernandez J.X.// In: FSSCEF 2006, Proc. Intern. Conf. Fuzzy Sets and Soft Computing in Economics and Finance - St. Petersburg, Russia, 2006. - P. 242-251.

17. Batyrshin I.Z. Hybrid clustering of time series/ Batyrshin I.Z., Sheremetov L.B., Velasco-Hernandez J.X., Klimova A.S.//In: East West Fuzzy Colloquium 2006, 13th Zittau Fuzzy Colloquium - HS Zittau/Görlitz, Germany, 2006. - P. 140-146.

Соискатель A.C. Климова

Заказ №167_Тираж 100 экз.

Отпечатано в типографии «Деловая полиграфия», 420111, г.Казань, ул.М.Межлаука, 6

Министерство образования России Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Казанский национальный исследовательский

технологический университет»

04 СП з 5 ^ (? ( На правах рукописи

Климова Анжелика Сергеевна

МОДЕЛИ И МЕТОДЫ ГИБРИДНОЙ РЕЛЯЦИОННОЙ КЛАСТЕРИЗАЦИИ ДАННЫХ

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

Диссертация

на соискание ученой степени кандидата технических наук

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

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

профессор Батыршин И. 3.

Казань-2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.......................................................................................................................4

ГЛАВА 1. ОБЗОР МЕТОДОВ КЛАСТЕРИЗАЦИИ И ВИЗУАЛИЗАЦИИ

ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ....................................11

ГЛАВА 2. ИНВАРИАНТНЫЕ ПРОЦЕДУРЫ РЕЛЯЦИОННОЙ ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИИ....................................................................30

2.1. Нечеткие отношения сходства...........................................................................30

2.2. Инвариантные кластерные процедуры..............................................................33

2.3. Общая схема инвариантных иерархических кластерных алгоритмов...........35

2.4. Кластерные процедуры с тождественными функциями ^ - Гз........................41

2.5. Кластерные процедуры, основанные на идее «обрыва мостов»....................43

2.6. Гибридная процедура реляционной кластеризации с визуализацией сильных связей между объектами............................................................................................46

ГЛАВА 3. ЭВОЛЮЦИОННЫЕ ПРОЦЕДУРЫ ВИЗУАЛИЗАЦИИ МНОГОМЕРНЫХ ДАННЫХ.......................................................................................48

3.1. Постановка задачи визуализации данных.........................................................48

3.2. Эволюционная процедура двумерной визуализации данных.........................50

3.3. Эволюционная процедура трехмерной визуализации данных.......................56

3.4. Гибридная кластеризация с двухмерной визуализацией результатов кластеризации данных................................................................................................61

3.5. Гибридная кластеризация с трехмерной визуализацией результатов кластеризации данных................................................................................................68

ГЛАВА 4. ОПИСАНИЕ КОМПЛЕКСА ПРОГРАММ ГИБРИДНОЙ КЛАСТЕРИЗАЦИИ.......................................................................................................72

4.1. Описание комплекса программ..........................................................................72

4.2. Преобразование скользящих аппроксимаций...................................................78

4.3. Применение метода гибридной кластеризации с визуализацией сильных связей для исследования связей между инвестициями регионов Приволжского Федерального Округа.................................................................................................83

4.4. Применение метода гибридной кластеризации к анализу взаимодействия нефтяных скважин......................................................................................................88

4.5. Применение метода гибридной кластеризации к анализу среднего потребления электроэнергии странами бывшего Советского Союза...................91

ЗАКЛЮЧЕНИЕ..............................................................................................................94

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ....................................................96

ВВЕДЕНИЕ

Актуальность. Кластеризация данных играет большую роль в анализе данных в экономике, в социальных науках, в технике, биологии, геологии, астрономии и в других научных областях. Кластеризация позволяет представить исследуемые данные в виде разбиения на классы сходных объектов, что является одним из важных этапов формирования знаний об исследуемой предметной области, ее моделирования и анализа [1, 2, 3, 4, 5, 6-8]. Кластерный анализ активно развивается последние десятилетия, однако «идеальных» алгоритмов кластеризации до сих пор не разработано и, по-видимому, разработано быть не может, что можно объяснить следующими причинами. Во-первых, структура реальных данных не всегда может быть адекватно представлена в виде разбиения на классы сходных объектов; во-вторых, данные могут допускать различные разбиения на классы сходных объектов; в-третьих, помимо структуры классов сходства, формируемой кластерным алгоритмом, часто желательно выявить дополнительную информацию о связях между объектами. Поэтому актуальной является задача разработки гибридных методов кластеризации, дающих новые методы представления структуры данных на основе кластерного анализа. В настоящее время активно развиваются методы сочетания нескольких кластерных процедур, методы комбинирования кластеризации с визуализацией данных и др. [9-13]. При этом важным является использование кластерных алгоритмов, удовлетворяющих условиям инвариантности относительно исходной нумерации (перестановки) кластеризуемых объектов и инвариантности относительно монотонных преобразований значений сходства [14-26]. К сожалению, эти условия инвариантности не выполняются для большинства известных кластерных алгоритмов. Поэтому важной является задача разработки гибридных кластерных алгоритмов, удовлетворяющих указанным условиям инвариантности. В работах Батыршина И.З. и др. разработана реляционная схема иерархических инвариантных процедур кластеризации, основанная на преобразовании заданного взвешенного отношения сходства во взвешенное (нечеткое) отношение

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

Цель работы: Разработка моделей, методов и комплекса программ гибридной кластеризации данных на основе реляционных инвариантных процедур кластеризации.

Задачи исследования.

1. Теоретическое исследование свойств реляционной схемы инвариантных иерархических кластерных процедур с целью исследования возможности ее расширения на новые типы кластеров.

2. Разработка и реализация новых реляционных инвариантных процедур иерархической кластеризации.

3. Разработка методов гибридной кластеризации на основе реляционных кластерных процедур.

4. Создание комплекса программ гибридной реляционной кластеризации данных.

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

Научная новизна работы.

1. Получено теоретическое обоснование реляционной схемы инвариантных иерархических кластерных процедур.

2. Предложено расширение реляционной схемы инвариантных иерархических кластерных процедур, содержащее новые кластерные процедуры.

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

4. Разработаны численные методы поиска оптимальных представлений данных в виде кластеров и визуализации этих кластеров.

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

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

Апробация работы. Основные положения и результаты работы обсуждены на международых конференциях "East West Fuzzy Colloquium" (Германия, Циттау, 2002, 2006) и "Fuzzy Sets and Soft Computing in Economics and Finance" (Санкт-Петербург, 2004, 2006), на II Всероссийской научно-технической конференции "Проблемы информатики в образовании, управлении, экономике и технике" (Пенза, 2002), III Международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2005), на Всероссийской конференции "Нечеткие системы и мягкие вычисления" (Тверь, 2006).

Публикации результатов работы. Основные выводы и положения диссертации изложены в 17 печатных работах. Среди них 3 статьи в журналах из перечня ВАК, 8 - в материалах конференций, 6 - в журналах и сборниках научных работ академических и центральных изданий.

Ряд результатов диссертационной работы получен в рамках проектов фонда НИОКР и АН РТ (05-5.2-173/2002) и РФФИ (03-01-96-245-р200) по теме "Разработка методов моделирования процессов и систем на основе нечеткой логики, нечетких отношений и нейронных сетей", 02-01-00092-а "Разработка моделей и методов вычисления словами на основе гранулирования информации о нечетких зависимостях и оптимизации нечетких моделей по параметрам

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

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

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

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

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

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

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

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

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

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

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

Четвертая глава "Описание комплекса программ гибридной кластеризации" содержит описание комплекса программ, реализующего разработанные методы, описание нового подхода к анализу экономических и статистических временных рядов, основанного на использовании меры ассоциаций локальных трендов [27] и процедур гибридной кластеризации. Данный подход использовался для исследования связей между динамикой инвестиций в основной капитал за 1999 - 2004 гг. на примере 14 регионов Приволжского Федерального округа, для исследования взаимодействия нефтяных скважин на примере одного из Мексиканских месторождений и для анализа уровня потребления электроэнергии странами бывшего Советского Союза за 1992-2004.

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

Основные результаты работы и выводы

1. Разработана общая схема гибридных реляционных кластерных алгоритмов.

2. Получено обоснование реляционной схемы инвариантных иерархических кластерных процедур и разработана новая инвариантная иерархическая кластерная процедура этой схемы.

3. Разработан метод гибридной кластеризации с визуализацией сильных связей.

4. Разработаны и реализованы новые инвариантные процедуры иерархической кластеризации.

5. Разработаны генетические алгоритмы 2-х и 3-х мерной визуализации данных.

6. Разработаны и реализованы методы гибридной кластеризации с генетическими алгоритмами 2-х и 3-х мерной визуализации данных.

7. Разработан пакет программ гибридной кластеризации данных в ИС Ма^аЬ.

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

9. Алгоритмы визуализации позволяют представить многомерные данные в пространстве размерности два или три с ошибкой аппроксимации исходной матрицы расстояний матрицей расстояний двумерного или трехмерного представления объектов, меньшей чем ошибка аппроксимации представления, полученного другими методами (например, методами неметрического шкалирования, методами оптимизации (разделы 3.2 и 3.3)).

ГЛАВА 1. ОБЗОР МЕТОДОВ КЛАСТЕРИЗАЦИИ И ВИЗУАЛИЗАЦИИ ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ

Целями кластерного анализа обычно являются: 1) формирование классов сходных объектов и представление структуры множества объектов в виде совокупности кластеров; 2) интерпретация построенных кластеров и структуры множества объектов. В зависимости от того, какая из этих целей является определяющей, можно говорить о "декомпозиционном" и "когнитивном" кластерном анализе. В первом случае декомпозиция множества объектов на кластеры производится на основе некоторого критерия оптимальности, и достижение оптимальности разбиения на кластеры, а не их интерпретация является основной. Декомпозиционный подход используется, когда информа�