Методы кластерного анализа

1.3. Методы кластерного анализа.

Сегодня существует достаточно много методов кластерного анализа. Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).

Пусть Х - матрица наблюдений: Х = (Х₁, Х₂,..., Х_u) и квадрат евклидова расстояния между Х_ и Х_j определяется по формуле:

1) Метод полных связей.

Суть данного метода в том, что два объекта, принадлежащих одной и той же группе (кластеру), имеют коэффициент сходства, который меньше некоторого порогового значения S. В терминах евклидова расстояния d это означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения h. Таким образом, h определяет максимально допустимый диаметр подмножества, образующего кластер.

2) Метод максимального локального расстояния.

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

3) Метод Ворда.

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

4) Центроидный метод.

Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров:

d²_ij = (X –Y)^Т(X –Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и , имеющие минимальное значение d²_ij Если n₁ много большеn_2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп.

1.4 Алгоритм последовательной кластеризации.

Рассмотрим Ι = (Ι₁, Ι₂, … Ι_n) как множество кластеров {Ι₁}, {Ι₂},…{Ι_n}. Выберем два из них, например, Ι_ и Ι _j, которые в некотором смысле более близки друг к другу и объединим их в один кластер. Новое множество кластеров, состоящее уже из n-1 кластеров, будет:

{Ι₁}, {Ι₂}…, {Ι_ , Ι _j}, …, {Ι_n}.

Повторяя процесс, получим последовательные множества кластеров, состоящие из (n-2), (n-3), (n–4) и т.д. кластеров. В конце процедуры можно получить кластер, состоящий из n объектов и совпадающий с первоначальным множеством Ι = (Ι₁, Ι₂, … Ι_n).

В качестве меры расстояния возьмем квадрат евклидовой метрики d_{ j}². и вычислим матрицу D = {d_{i j}²}, где d_{i j}² - квадрат расстояния между

Ι_ и Ι _j:

Пусть расстояние между Ι_i и Ι_j будет минимальным:

d_{ j}² = min {d_{i j}², i  j}. Образуем с помощью Ι_i и Ι_j новый кластер

{Ι_i , Ι _j}. Построим новую ((n-1), (n-1)) матрицу расстояния

(n-2) строки для последней матрицы взяты из предыдущей, а первая строка вычислена заново. Вычисления могут быть сведены к минимуму, если удастся выразить d_{i j}²_k,k = 1, 2,…, n; (k  i  j) через элементы первоначальной матрицы.

Исходно определено расстояние лишь между одноэлементными кластерами, но надо определять расстояния и между кластерами, содержащими более чем один элемент. Это можно сделать различными способами, и в зависимости от выбранного способа мы получают алгоритмы кластер анализа с различными свойствами. Можно, например, положить расстояние между кластером i + j и некоторым другим кластером k, равным среднему арифметическому из расстояний между кластерами i и k и кластерами j и k:

d_i+j,k = Ѕ (d_{i k} + d_{j k}).

Но можно также определить d_i+j,k как минимальное из этих двух расстояний:

d_i+j,k = min (d_{i k} + d_{j k}).

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

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

d_i+j,k = A(w) min(d_ikd_jk) + B(w) max(d_ik d_jk), где

A(w) = , если d_ik  d_jk

A(w) = , если d_ik  d_jk

B(w) =, если d_k  d_jk

B(w) = , если d_ik  d_jk

где n_i и n_j - число элементов в кластерах i и j, а w – свободный параметр, выбор которого определяет конкретный алгоритм. Например, при w = 1 мы получаем, так называемый, алгоритм «средней связи», для которого формула перерасчета расстояний принимает вид:

d_i+j,k =

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

Наглядный смысл параметра w становится понятным, если положить w  . Формула пересчета расстояний принимает вид:

d_i+j,k = min (d_,k d_jk)

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

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

В случае кластер анализа объектов наиболее часто мерой различия служит либо квадрат евклидова расстояния

(где x_ih, x_jh - значения h-го признака для i-го и j-го объектов, а m - число характеристик), либо само евклидово расстояние. Если признакам приписывается разный вес, то эти веса можно учесть при вычислении расстояния

Иногда в качестве меры различия используется расстояние, вычисляемое по формуле:

которые называют: "хэмминговым", "манхэттенским" или "сити-блок" расстоянием.

Естественной мерой сходства характеристик объектов во многих задачах является коэффициент корреляции между ними

где m_i ,m_j ,_i ,_j - соответственно средние и среднеквадратичные отклонения для характеристик i и j. Мерой различия между характеристиками может служить величина 1 - r. В некоторых задачах знак коэффициента корреляции несуществен и зависит лишь от выбора единицы измерения. В этом случае в качестве меры различия между характеристиками используется 1 - r_{i j}

Похожие работы

Кластерный анализ

Скачать

31766

3

1

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

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

Скачать

34425

10

7

... пятого кластера стали Санкт-Петербург, Свердловская область. А вот шестой кластер состоит лишь из одного региона России- Республики Ингушетии. Для создания качественного представления о социально-экономическом положении (различиях в имущественном обеспечении и неравенстве в доходах) очень полезно будет рассмотреть таблицу окончательных кластерных центров. Таблица 9 «Окончательные кластерные ...

Анализ эффективности инвестиционных проектов и проблемы оптимизации капиталовложений

Скачать

33711

11

8

... . Работа имеет три раздела: В первой главе характеризируются и рассматриваются основные принципы анализа капиталовложений. Вторая глава представляет собой анализ эффективности инвестиционных проектов. Третья глава состоит из рассмотрения проблем оптимизации капиталовложений. РАЗДЕЛ 1. ОСНОВНЫЕ ПРИНЦИПЫ АНАЛИЗА ИНВЕСТИЦИОННЫХ ПРОЕКТОВ   1.1. Характеристика видов инвестиционных проектов ...

Кластерный анализ в портфельном инвестировании

Скачать

30624

3

2

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