Содержание к диссертации
Введение
Глава 1. Обзор методов кластеризации и визуализации данных и постановка задачи исследования 11
Глава 2. Инвариантные процедуры реляционной иерархической кластеризации 30
2.1. Нечеткие отношения сходства 30
2.2. Инвариантные кластерные процедуры 33
2.3. Общая схема инвариантных иерархических кластерных алгоритмов 35
2.4. Кластерные процедуры с тождественными функциями fi - f? 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
- Обзор методов кластеризации и визуализации данных и постановка задачи исследования
- Общая схема инвариантных иерархических кластерных алгоритмов
- Гибридная кластеризация с двухмерной визуализацией результатов кластеризации данных
- Применение метода гибридной кластеризации к анализу взаимодействия нефтяных скважин
Введение к работе
Актуальность. Кластеризация данных играет большую роль в анализе данных в технике, в экономике, в социальных науках, биологии, геологии, астрономии и в других научных областях. Кластеризация позволяет представить исследуемые данные в виде разбиения на классы сходных объектов, что является одним из важных этапов формирования знаний об исследуемой предметной области, ее моделирования и анализа. Но структура реальных данных не всегда может быть адекватно представлена в виде разбиения на классы сходных объектов, также данные могут допускать различные разбиения на классы сходных объектов, кроме того, помимо структуры классов сходства, формируемой кластерным алгоритмом, часто желательно выявить дополнительную информацию о связях между объектами. Поэтому актуальной является задача разработки гибридных методов кластеризации, дающих новые методы представления структуры данных на основе кластерного анализа. В настоящее время активно развиваются методы сочетания нескольких кластерных процедур, методы комбинирования кластеризации с визуализацией данных и др. [Strehl, Jain, Murty, Babu, Крускал, Ярушкина и др.]. При этом важным является использование кластерных алгоритмов, удовлетворяющих условиям инвариантности относительно исходной нумерации (перестановки) кластеризуемых объектов и инвариантности относительно монотонных преобразований значений сходства [Jardine, Johnson, Батыршин и др.]. К сожалению, эти условия инвариантности не выполняются для большинства известных кластерных алгоритмов. Поэтому важной является задача разработки гибридных кластерных алгоритмов, удовлетворяющих указанным условиям инвариантности. В работах Батыршина И.З. и др. разработана реляционная схема иерархических инвариантных процедур кластеризации, основанная на преобразовании заданного взвешенного отношения сходства во взвешенное (нечеткое) отношение эквивалентности, определяющее иерархию разбиения множества объектов на кластеры определенного типа. Перспективной является задача расширения этой схемы для выделения кластеров новых типов и разработки гибридных кластерных процедур на ее основе.
Цель работы: Разработка моделей, методов и комплекса программ гибридной кластеризации данных на основе реляционных инвариантных процедур кластеризации.
Задачи исследования.
-
Теоретическое исследование свойств реляционной схемы инвариантных иерархических кластерных процедур с целью исследования возможности ее расширения на новые типы кластеров.
-
Разработка и реализация новых реляционных инвариантных процедур иерархической кластеризации.
-
Разработка методов гибридной кластеризации на основе реляционных кластерных процедур.
-
Создание комплекса программ гибридной реляционной кластеризации данных.
Методы исследования: кластерный анализ, теория нечетких множеств, теория графов, теория генетических алгоритмов.
Научная новизна работы.
-
-
Получено теоретическое обоснование реляционной схемы инвариантных иерархических кластерных процедур.
-
Предложено расширение реляционной схемы инвариантных иерархических кластерных процедур, содержащее новые кластерные процедуры.
-
Разработаны методы построения моделей данных в виде инвариантных (относительно исходной нумерации и относительно монотонных преобразований значений сходства) кластеров сходных объектов, сетей сходства и их визуализации в двумерном и трехмерном пространствах.
-
Разработаны численные методы поиска оптимальных представлений данных в виде кластеров и визуализации этих кластеров.
Достоверность результатов диссертационной работы подтверждается результатами экспериментов и практического использования материалов диссертации, и разработанного пакета программ.
Практическая значимость работы состоит в разработке в среде МАТ- ЛАБ пакета программ гибридной реляционной кластеризации данных, позволяющего исследовать инвариантные структуры сходства в задачах кластеризации данных и анализа структуры систем, в разработке методов визуализации и гибридной кластеризации данных, в разработке методов анализа взаимодействия скважин нефтяного месторождения на основе данных добычи нефти и сопутствующей воды. Результаты работы внедрены в Институте проблем информатики АН РТ, Министерстве образования и науки РТ и введены в состав учебной дисциплины СД.04 "Нечеткая логика и мягкие вычисления" на кафедре информатики и прикладной математики Казанского государственного технологического университета.
Апробация работы. Основные положения и результаты работы обсуждены на международых конференциях "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-p200) по теме "Разработка методов моделирования процессов и систем на основе нечеткой логики, нечетких отношений и нейронных сетей", 02-01-00092-а "Разработка моделей и методов вычисления словами на основе гранулирования информации о нечетких зависимостях и оптимизации нечетких моделей по параметрам операций", а также совместных исследований с учеными Мексиканского нефтяного института.
Структура и объем работы.
Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, изложенных на 105 страницах машинописного текста. Содержит 3 таблицы, 18 рисунков, список литературы из 96 наименований.
Обзор методов кластеризации и визуализации данных и постановка задачи исследования
Целями кластерного анализа обычно являются: 1) формирование классов сходных объектов и представление структуры множества объектов в виде совокупности кластеров; 2) интерпретация построенных кластеров и структуры множества объектов. В зависимости от того, какая из этих целей является определяющей, можно говорить о "декомпозиционном" и "когнитивном" кластерном анализе. В первом случае декомпозиция множества объектов на кластеры производится на основе некоторого критерия оптимальности, и достижение оптимальности разбиения на кластеры, а не их интерпретация является основной. Декомпозиционный подход используется, когда информация о близости объектов характеризует функциональные или пространственные (территориальные) связи между объектами. Подобный подход более типичен в задачах анализа социально-экономических данных, в задачах синтеза структуры управления, поиска, обработки данных и т. д. Результаты декомпозиции множества объектов могут служить для оптимального размещения информационных единиц на внешних носителях, минимизация времени поиска информации, размещения центра управления объектами каждого кластера.
При когнитивном кластерном анализе основной целью кластеризации данных является формирование понятийной структуры множества объектов, выявление скрытых факторов, лежащих в основе исследуемых явлений, выявление семантической общности исследуемых объектов. Подобный подход является определяющим в задачах представления знаний, анализа структуры семантических пространств, обобщения информации.
При декомпозиционном кластерном анализе состав формируемых кластеров обычно не играет большой роли, и, если возможны оптимальные классификации, в качестве решения задачи выбирается любая из них. При когнитивном подходе разные классификации будут определять разные интерпретации данных. Желательно использовать методы кластеризации, инвариантные к различным преобразованиям исходных данных, чтобы на выходе алгоритма кластеризации получить не одну из возможных интерпретаций данных, а некоторую устойчивую кластеризацию, присущую множеству исследуемых объектов.
Требования инвариантности кластерных процедур относительно монотонных преобразований значений сходства между объектами и инвариантности относительно перестановки объектов представлены в кластерном анализе как наиболее важные требования к кластерным алгоритмам [14, 28-34]. Первое требование необходимо, если значения сходства измерены экспертами или могут быть выражены только в порядковой шкале. Это требование также желательно для нечувствительности результатов кластеризации к выбору меры сходства или различий. Второе требование необходимо, если мы хотим получить как результат кластерной процедуры кластеризацию данных, которые не зависят от выбора начальной нумерации объектов. Последнее свойство очень важно, когда абстрактная интерпретация кластеров используется после применения кластерного алгоритма.
В работах [35-37] исследовались процедуры иерархической кластеризации, инвариантные к исходной нумерации объектов и к монотонным преобразованиям значений сходства между объектами. Наиболее важным условием инвариантности кластерных алгоритмов является условие инвариантности относительно нумерации объектов. Это условие требует, чтобы результаты кластеризации рассматриваемого множества объектов не зависели от того, как эти объекты будут занумерованы. Невыполнение этого условия может привести к появлению ошибок второго рода в кластерном анализе (когда алгоритм кластеризации строит кластеры, заведомо отсутствующие в исходных данных).
Покажем на простом примере множества из семи объектов, равномерно распределенных по окружности (Рис. 1), когда начальная информация для кластеризации задана матрицей расстояний между объектами. Только два разбиения А={{а, Ъ, с, d, e,f,g}} и В={{а}, {Ь}, {с}, {d}, {е}, {/}, {g}}, построенных алгоритмом "ближний сосед", сохраняют симметричную структуру данных. Так как любое разбиение этого множества на 2, 3, 4, 5 или 6 кластеров не будет отражать внутреннюю симметрию в структуре и, следовательно, будет зависеть от начальной нумерации объектов или от выбора начальной точки кластерной процедуры. Например, если, для разбиения на два кластера, разбиение С={{а, Ъ, с, dj, {е, f, g}} оптимально по некоторому критерию, тогда из-за симметрии данных разбиение D={{b, с, d, е}, {a, f, g}} будет так же оптимально, так же как и другие пять разбиений, полученных из D последовательным поворотом на угол 2п/7. Кластерный алгоритм дает С как оптимальное разбиение, но не инвариантное относительно нумерации объектов и не может найти свойственную им структуру. Для кластерных алгоритмов, строящих оптимальные "нечеткие кластеры" для этого простого примера ситуация похожа.
В литературе были представлены различные подходы к построению инвариантных иерархических кластерных алгоритмов, но только некоторые из известных алгоритмов удовлетворяют обоим требованиям. Один из таких алгоритмов это алгоритм "ближний сосед", который обсуждался во многих публикациях. Этот алгоритм строит цепочки кластеров и по этой причине отражает только особую точку зрения на "кластер", которая не всегда приемлема. Тем не менее, этот алгоритм представлен как один из самых важных кластерных алгоритмов [14]. Для анализа определенных данных с разных точек зрения наиболее пригодными являются параметрические кластерные алгоритмы, которые содержат различные кластерные алгоритмы, зависящие от параметров. Очень популярная параметрическая схема кластерных алгоритмов, включенная во многие статистические пакеты, была представлена в [38] и обобщена некоторыми авторами [39]. Дополнительно к алгоритму "ближний сосед" эта схема содержит алгоритм "дальний сосед", который инвариантен относительно монотонных преобразований значений сходства, но не инвариантен относительно нумерации объектов. Модификации этого алгоритма, которые инвариантны относительно нумерации объектов, были обсуждены в [40, 41] Другая параметрическая схема кластерных алгоритмов представлена в [29, 42], состоящая из двух шагов: 1) г раз применяется некоторое преобразование исходной функции различий; 2) для полученной функции используется алгоритм "дальний сосед". Эта схема содержит различные кластерные алгоритмы, инвариантные относительно монотонного преобразования значений различий, зависящие от параметра г. Алгоритм "ближний сосед" может быть рассмотрен как частный случай этой схемы.
Некоторые общие связанные подходы к построению и исследованию иерархических кластерных алгоритмов используют как начальную информацию об объектах значения функции близости между ними. Функция близости может быть определена на множестве объектов X как неотрицательная вещественная функция S: XxX— R, удовлетворяющая на X условию симметричности S(x,y)=S(y,x). Обычно функции близости могут быть заданы как функция сходства или различий, или взвешенным графом. Функция близости называется функцией различий, если S(x,x)=0 для всех х из X. В этом случае S(x,y) определяется значениями различий или расстояний между объектами х и у. Иерархические кластерные процедуры строящие иерархию группы разбиений множества объектов могут быть представлены как преобразования данной функции различий S в ультраметрику, то есть функция различий удовлетворяет ультраметрическому неравенству: S(x,y) max{S(x,z), S(z,y)}. Свойства ультраметрик изучены во многих работах [29, 39, 41, 43-46]. Этот подход дает хорошие возможности описания метрических свойств функций различий. Вопросы аппроксимации функций различий ультраметрикой был обсужден в [29].
Другой подход основан на понятии взвешенного графа [29, 41, 47, 48]. Этот подход очень подходит для изучения проблем кластерного анализа в терминах связей. В этом случае, например, понятия связанного подграфа и полного подграфа могут быть использованы для описания кластеров, построенных соответственно кластерными алгоритмами "ближний сосед" и "дальний сосед". Кластерный алгоритм может быть представлен как преобразование данного взвешенного графа во взвешенный граф, который может быть представлен как группа последовательностей графов, все компоненты которой связные.
Общая схема инвариантных иерархических кластерных алгоритмов
Неинвариантная оптимальная кластеризация может быть результатом наличия равных значений сходства у функции сходства. На практике равные значения сходства часто появляются как результат округления вещественных чисел или использования шкал сходства с предельным значением или как результат топологической структуры анализируемых данных. В этом случае должны применяться методы, которые дают инвариантные кластеризации с маленьким, но, возможно, не минимальным расстоянием между начальным и конечным отношением. Как результат, инвариантное решение может быть найдено среди не оптимальных решений или мы должны искать оптимальное решение среди всех инвариантных решений.
Общая схема иерархических кластерных процедур, удовлетворяющих условиям инвариантности относительно исходной нумерации объектов и инвариантности относительно монотонных преобразований значений сходства исследовалась в работах [16, 37, 70, 79]. Схема (1) имеет вид: HC(S) = Е; 0 . где Е - взвешенное отношение эквивалентности. Преобразование HC(S) задается процедурой кластеризации Q(S)=E, которая определяется так: E = Q(S) = TC(F(S)) = F$S), где F это некоторая "коррекция" данного отношения сходства S, такая что F(S)cS, и ТС обозначает процедуру транзитивного замыкания значений отношения сходства. Процедура транзитивного замыкания определена и может быть реализована алгоритмом "ближний сосед" [28, 43, 49, 54]. Эта процедура обладает обоими типами инвариантности. Если возможно представить некоторую процедуру коррекции F также обладающую обоими типами инвариантности, то мы построим кластерную процедуру Q, удовлетворяющую желаемым свойствам инвариантности.
Для построения подходящей процедуры коррекции, желательно решить: для каких пар объектов (х, у) значения сходства S(x, у) должны быть скорректированы и как эти значения должны быть уменьшены. Для этих целей может быть использована следующая оценка неразличимости. Будем говорить, что два объекта х и у неразличимы с согласия объекта z, когда S(x, z) S(x, у) тогда и только тогда, когда S(y, z) S(x, у). В этом случае мы будем говорить, что объект z "поддерживает" значение сходства S(x, у). Чем больше объектов в X поддерживают значение сходства S(x, у), тем больше степень неразличимости х и у. Наша задача изменить значение S(x, у) так, чтобы число объектов поддерживающих сходство между х и у и, следовательно, степень неразличимости увеличились. В результате мы можем сказать, что если объекты х и у неразличимы только с согласия маленькой части объектов и, следовательно, они показывают различное поведение на большой части объектов, то значение сходства S(x, у) не подтверждается или не поддерживается объектами множества X и в результате значение сходства S(x, у) может быть скорректировано (уменьшено).
Рассматриваемая процедура коррекции зависит от следующих множеств и параметров: Vy(x)={zeX\{x, y}\S(x, z)2f,(S(x, у))}, Vx(y)={zeX\{x, y}\S(y, z) f](S(x, у))}, где fi:R— R — монотонная неотрицательная неубывающая функция. Множества Vy(x) и Vx(y) обозначают множества объектов "похожих" на х и на у соответственно, где значение fi(S(x, у)) служит как критерий этого сходства. Множество V(x, y)={zeX\.{x, y}\max{S(x, z), S(y, z)} f2(S(x, y))} содержит объекты из X, которые "похожи" по крайней мере на один из объектов х и у. Когда/;=/? мы имеем V(x, y) = Vy(x)uVx(y). Это множество будет представлено как множество "соседей" х и у. "Голоса" объектов из V(x, у) будут приниматься во внимание, когда будет приниматься решение о коррекции значения S(x, у). Следующее множество W(x, y)={zeX\{x, y}\min{S(x, z), S(y, z)} f3(S(x, y))} обозначает множество "сильных" или "общих" соседей, т. е. объекты, которые "похожи" на оба объекта хиу. Объекты из W(x, у) будут "поддерживать" значение S(x, у). Когда/і=/з мы имеем W(x, y)=Vy(x)nVx(y).
Два объекта называются идентичными в S, если S(x,y) =1 и S(x,z) = S(y,z) для всех z из М\{х,у}. Два объекта хиу называются неразличимыми на уровне аєЬ если S(x,y) аи для всех ze Мвыполняется S(x,z) а тогда и только, когда S(y,z) а. Ясно, что два объекта неразличимые на некотором уровне а будут идентичными в отношении сходства Sa. Ясно также, что все объекты неразличимы на минимально возможном уровне 0, и максимально возможный уровень неразличимости двух объектов хиув отношении .Sравен а = S(x,y). Два объектах и у неразличимые на уровне а= S(x,y) будут называться неразличимыми в S.
Решение о коррекции значения S(x, у) будет зависеть от соответствующей части объектов "поддерживающих" значение сходства S(x, у), которое может быть представлено как мера неразличимости объектов хну. Мы можем представить следующие методы вычисления для каждой пары объектов х и у этой соответствующей части обозначенной h,:
Пусть Ly(x, у) обозначает упорядоченный в убывающем порядке список всех значений S(x, z), S(y, z), (zeV), которые имеют значение меньше чем S(x, у). Обозначим количество элементов в Ly(x, у) как m=\Ly(x, у)\ и элементы Ly(x, у) как Ik (к=1, ..., т). Если пь 1, то h h+i для всех к=1, ..., т-1. Порядковое обобщение процедур коррекции F/x, у) получено Батыршиным, Шустером в [37], и Батыршиным и Хабибуллиным в [30].
Возможные коррекции, когда т 1 определяются параметрому: j=l: F/x, y)=lm, т. е. F/x, у) минимальное значение в Ly(x, у); j=2: F/x, у)=1], т. е. Fj(x, у) максимальное значение в Lv(x, у); j=3: Fj(x, у)=(Пк)/т, т. е. F}(x, у) есть среднее всех значений из Ly(x, у); j=4: F/x, y)=lk, где кє{1, ..., т} - параметр, Fi и F2 это частные случаи К/. j=5: Fj(x, y)=median(Lv(x, у)).
Все процедуры коррекции при j=l, 2, 3, 4, 5 инвариантны относительно нумерации объектов и все F/x, у) для j=l, 2, 4, 5 инвариантны относительно монотонного преобразования значений сходства.
Когдар=0, из hj 0 следует, что F(S(x, y))=Sc(x, y)=S(x, у), т. е. для всех х, у из X значения S(x, у) не будут корректироваться и Q(S)=TC(F(S))=TC(S), т. е. кластерный алгоритм будет совпадать с алгоритмом "ближний сосед".
Вместо соответствующей части поддерживающих соседей h, можно подставить число поддерживающих соседей, которое может быть вычислено как: gi=\W(x, у)\ или g2=\W(x, y)\ + \X\V\-2. В этом случае процедура коррекции может быть определена следующим образом
Процедура транзитивного замыкания постоянна в представленной схеме кластерных процедур. Эта процедура может быть реализована алгоритмом "ближний сосед" или алгоритмами транзитивного замыкания, представленными в теории графов [27, 43, 54, 80, 81]. Так как процедура транзитивного замыкания инвариантна относительно нумерации объектов и монотонных преобразований функций сходства, представленные кластерные процедуры будут обладать обоими этими свойствами, если процедура коррекции будет обладать этими свойствами. Чтобы быть инвариантной процедура коррекции должна быть применена ко всем парам объектов (х, у) независимо от их нумерации или порядка рассмотрения и параметры, использованные в процедуре коррекции, должны быть фиксированы или не зависеть от нумерации объектов. Свойство инвариантности относительно монотонных преобразований значений сходства является дополнительным к свойству инвариантности относительно нумерации объектов.
Утверждение 2. Отношение сходства S, определенное на X будет взвешенным отношением эквивалентности тогда и только тогда, когда все объекты в S неразличимы в S.
Доказательство. Так как S будет взвешенным отношением эквивалентности тогда и только тогда, когда для всех х, у, гєХдва наименьших из трех значений S(x, у), S(y, z), S(z, х) равны, то выполнено одно из двух: S(x, y) S(y, z)=S(z, х) или S(y, z) S(x, у) и S(z, x) S(x, у), т.е. каждая пара объектов х, у неразличима.
Из свойств процедуры транзитивного замыкания ТС следует, что преобразования любого отношения сходства S во взвешенное отношение эквивалентности Е, такое что SczE и Е минимальное взвешенное отношение эквивалентности, содержащее S. Следовательно, процедура транзитивного замыкания дает минимальное увеличение значений S(x, у) для преобразования S во взвешенное отношение эквивалентности Е. Из утверждения 2 мы можем заключить, что эта процедура преобразует не неразличимые пары объектов в неразличимые. Следовательно, мы можем предположить, что суммарное значение преобразования S в Е, полученное ТС, зависит от числа не неразличимых пар элементов в S и от "степени неразличимости" этих элементов, если мы можем измерить эту степень. Следовательно, процедура коррекции F, уменьшающая значения сходства S(x, у), должна давать такие минимальные изменения этих значений, которые будут увеличивать число неразличимых пар объектов или увеличивать "степень неразличимости" пар объектов. В этом случае преобразование TC(F(S)), полученное процедурой транзитивного замыкания, будет маленьким.
Свойства описанных кластерных процедур зависят от всех параметров, представленных выше. Все процедуры разделяются на классы в зависимости от функций/; -/з, используемых в кластерных процедурах.
Гибридная кластеризация с двухмерной визуализацией результатов кластеризации данных
Выше кластеризация и визуализация многомерных данных описывались независимо. Здесь мы рассмотрим совместное использование методов иерархической кластеризации с методами визуализации данных. Цель этого подхода расширить информацию о кластеризации объектов с помощью визуализации на столько, на сколько это позволяют исходные расстояния между объектами внутри построенных кластеров. Потому что все кластеры, в конечном счете, будут объединены в один кластер, расстояния между объектами из разных кластеров так же будут последовательно оптимизированы, когда эти кластеры объединяться вместе на высшем уровне иерархии. Необходимо отметить, что обычно невозможно преобразовать данные из «-мерного в двумерное пространство без изменений значений расстояния. По этой причине второй подход к двумерной визуализации пытается уменьшить изменения расстояний между объектами внутри маленьких классов за счет увеличения изменений расстояний между объектами из разных классов на высших уровнях иерархии. Схема гибридной кластеризации (1) имеет вид: HC(S) = Е;Р , где Е - взвешенное отношение эквивалентности, получаемое реляционной процедурой иерархической кластеризации, а Р - описание объектов множества М в двух- или трехмерном пространстве, согласованное в определенном смысле с реляционной процедурой иерархической кластеризации.
Рассмотрим структуру генетического алгоритма. На первом этапе алгоритма все маленькие кластеры иерархической кластеризации сосредоточены на нижних уровнях построенной иерархии. Генетический алгоритм пытается найти координаты объектов из некоторого класса, так чтобы расстояния между ними отличались от соответствующих расстояний в «-мерном пространстве на минимальную величину.
На втором этапе минимизируются изменения расстояний между кластерами, объединяющимися вместе в соответствии с последовательностью построения иерархии кластеров кластерным алгоритмом. Один кластер остается неподвижным, а другой перемещается, так чтобы расстояния между объектами из неподвижного кластера и объектами из поворачиваемого кластера стали как можно более похожи на расстояния между этими объектами в «-мерном пространстве.
Рассмотрим более подробно первый этап алгоритма. Если кластер состоит из двух объектов, то эти объекты получают координаты (0, 0) и (d, 0), соответственно, где d есть расстояние между этими объектами в «-мерном пространстве. Если кластер состоит более, чем из двух объектов, то к множеству этих объектов применяется генетический алгоритм, описанный выше в разделе 3.2.
На втором этапе расстояния между двумя классами, которые объединяются вместе в кластерной процедуре, оптимизируются следующим образом. Координаты объектов из одного из них остаются неизменными. Этот класс будем называть фиксированным классом. Второй класс будем перемещать, так чтобы расстояния между объектами внутри этого класса, полученные на первом этапе, не изменялись. Этот класс будем называть перемещаемым классом. Координаты объектов из этого класса изменим следующим образом: Xnew=X cos(a)+Y sin(A) +dX, Ynew=-X sin(a)+Y cos(A) +dY, где X , Y - это координаты объектов в двумерном пространстве до перемещения класса, Xnew, Ynew — координаты объектов после перемещения, dX, dY - величины сдвига объектов вдоль осей X и Y, А - угол поворота класса вокруг начала координат. Строка параметров (dX, dY, А) представлена как элемент популяции в генетическом алгоритме.
Были использованы следующие характеристики генетического алгоритма: размер начальной популяции (количество строк) равен 500, количество строк, отбираемых в элиту равно 15, количество генераций новых популяций равно 300. Элементы строк начальной популяции - случайные нормально распределенные числа из интервала [-100, 100] для dXn dY, [-тг, ж] для угла А. Для каждой из 500 сгенерированных строк было вычислено среднее изменение расстояний между рассматриваемыми классами следующим образом: E=sumJ(suml(abs(Rij-Dlj)))/(n m), где R,j и Dv - расстояния между объектами / из фиксированного класса и объектами j из перемещаемого класса, вычисленными соответственно в двумерном и «-мерном пространствах. Наилучшие 15 строк параметров с минимальным значением Е были отобраны в элиту. Генерация новых строк из строк, отобранных в элиту, основана на операциях мутации и рекомбинации.
Две строки-родители из элиты и один параметр из (dX, dY, А) выбираются случайно. Две новых строки-потомки, полученные из двух строк-родителей как результат обмена значениями выбранного параметра между строками-родителями. Этот процесс повторяется 15 раз и, в результате, мы имеем 30 строк-потомков.
Новая популяция получается объединением элиты, потомков и мутированной элиты, так что размер популяции становится равным 90.
Была использована следующая операция мутации. Каждому параметру мутируемых строк добавляется маленькая нормально распределенная ошибка: e=K S/T, где S - случайное число и Т - номер текущей генерации, принимающий значения от 1 до 300. Для dX и dY коэффициент К равен 1000. Для А он равен 0.2 71.
Для каждой новой популяции выбирается новая элита, с помощью которой генерируется новая популяция и т. д.
Результатом этой процедуры является оптимальный сдвиг и поворот перемещаемого класса относительно фиксированного класса. Если перемещаемый класс состоит более чем из двух объектов, то трех операций, определяемых параметрами (dX, dY, А) может быть не достаточно, для наилучшего расположения этого класса, потому что может быть необходимо так же сделать зеркальное отображение этого класса относительно одной из осей X или Y. По этой причине эволюционная процедура применяется так же к множеству 2D координат, полученных из множества координат объектов перемещаемого класса заменой всех координат 7 на -Y.
Наилучшие решения, полученные после применения генетического алгоритма к перемещаемому классу и зеркального отображения, дают оптимальные координаты перемещаемого класса.
Описанная процедура применялась для визуализации результатов классификации 15 объектов в пространстве размерности 10. Координаты объектов - числа, нормально распределенные в интервале [0, 100].
Применение метода гибридной кластеризации к анализу взаимодействия нефтяных скважин
Применение методов гибридной кластеризации к анализу взаимодействия нефтяных скважин описывается на примере одного из Мексиканских месторождений. Рассматривались 9 скважин, расположенных на общей территории, из которых 2 были нагнетающими. Анализ проводился на основе временных рядов объемов помесячной добычи нефти и сопутствующей воды, а также объемов нагнетания воды за 32 месяца, начиная с января 2004 года. Объемы месячной добычи получены в результате суммирования посуточной добычи, поэтому данные не нуждаются в сглаживании, а для анализа ассоциаций применялись скользящие окна размером 2 и 3. В качестве меры ассоциаций временных рядов [94] использовалась мера AM (у, х) = max(AFK (у, х)) = max(cos sk (у, х)), кєК где К = {2,3} задает размер скользящих окон. Так как мера ассоциации инвариантна к линейным преобразованиям данных в расчетах и визуализации данных использовались пронормированные значения временных рядов, имеющие безразмерные величины. На Рис. 14 приведены графики этих временных рядов, где li и 7і обозначают временные ряды, соответствующие нагнетающим скважинам (инъекторы), кр и ка означают, соответсвенно, временные ряды добычи нефти и сопутствующей воды в скважине к.
Рис.15 дает графическое представление найденного ассоциативного графа между временными рядами, для значения порога 0,468. Это значение равно величине ассоциации между нагнетающей скважиной П и добывающей скважиной 2р. Выбор такого порога для представления ассоциативного графа дает нетривиальное разбиение п" афа на связные компоненты и позволяет выявить ассоциации между нагнетающими и добывающими скважинами. Вершины ассоциативной сети расположены так, чтобы минимизировать пересечения дуг. В соответствии с этим порядком приведены также временные ряды на Рис.14, что позволяет визуально увидеть сходство между формой временных рядов с высоким значением ассоциации локальных трендов (например между 6р и 6а, Зр и За, 7i и 6а).
На Рис. 16 представлены результаты гибридной кластеризации скважин на основе меры ассоциаций локальных трендов. Две скважины X и Y считаются взаимосвязанными, если существует значимая ассоциативная связь между хотя бы одной парой временных рядов (Ха, Ya), (Ха, Yp), (Xp,Ya), (Хр, Yp). Получено следующее разбиение скважин на 5 кластеров: {1і},{2,3,4,9},{5},{6,7і},{8}. На Рис. 16 одиночные кластеры помечены кружком, а скважины из кластеров {2,3,4,9} и {6,7i} квадратом и ромбом соответственно. Значимые ассоциативные связи между скважинами (5, 3 и И, 2), принадлежащим разным кластерам, показаны пунктиром. и др. Результаты гибридной кластеризации дают основы для выдвижения различных гипотез о характере взаимодействия между скважинами и в результате этого служить основанием для проведения дополнительных специфических исследований на скважинах и в месторождении, а также для изменения режимов закачки воды в скважины.
Похожие диссертации на Модели и методы гибридной реляционной кластеризации данных
-
