Кластерный анализ в задачах социально-экономического прогнозирования - (реферат)
p>Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров:d2 ij = (`X –`Y)Т(`X –`Y) Кластеризация идет поэтапно на каждом из n–1 шагов объединяют два кластера G и p, имеющие минимальное значение d2ij Если n1 много больше n2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп.
1. 4 Алгоритм последовательной кластеризации.
Рассмотрим Й = (Й1, Й2, … Йn) как множество кластеров {Й1}, {Й2}, …{Йn}. Выберем два из них, например, Й i и Й j, которые в некотором смысле более близки друг к другу и объединим их в один кластер. Новое множество кластеров, состоящее уже из n-1 кластеров, будет: {Й1}, {Й2}…, {Й i , Й j}, …, {Йn}.
Повторяя процесс, получим последовательные множества кластеров, состоящие из (n-2), (n-3), (n–4)и т. д. кластеров. В конце процедуры можно получить кластер, состоящий из n объектов и совпадающий с первоначальным множествомЙ = (Й1, Й2, … Йn). В качестве меры расстояния возьмем квадрат евклидовой метрики di j2. и вычислим матрицу D = {di j2}, где di j2 - квадрат расстояния между Й i и ? j:
Й1
Й2
Й3
….
Йn
Й1
0
d122
d132
….
d1n2
Й2
0
d232
….
d2n2
Й3
0
….
d3n2
….
….
….
Йn
0
Пусть расстояние между Й i и Й j будет минимальным:
di j2 = min {di j2, i № j}. Образуем с помощью Й i и Й j новый кластер {Й i , Й j}. Построим новую ((n-1), (n-1)) матрицу расстояния
{Й i , Й j}
Й1
Й2
Й3
….
Йn
{Й i ; Й j}
0
di j21
di j22
di j23
….
di j2n
Й1
0
d122
d13
….
d12n
Й2
0
di j21
….
d2n
Й3
0
….
d3n
Йn
0
(n-2)строки для последней матрицы взяты из предыдущей, а первая строка вычислена заново. Вычисления могут быть сведены к минимуму, если удастся выразитьdi j2k, k = 1, 2, …, n; (k № i № j) через элементы первоначальной матрицы. Исходно определено расстояние лишь между одноэлементными кластерами, но надо определять расстояния и между кластерами, содержащими более чем один элемент. Это можно сделать различными способами, и в зависимости от выбранного способа мы получают алгоритмы кластер анализа с различными свойствами. Можно, например, положить расстояние между кластеромi + j и некоторым другим кластером k, равным среднему арифметическому из расстояний между кластерами i и k и кластерами j и k: di+j, k = Ѕ (di k + dj k).
Но можно также определить di+j, k как минимальное из этих двух расстояний: di+j, k = min (di k + dj k).
Таким образом, описан первый шаг работы агломеративного иерархического алгоритма. Последующие шаги аналогичны.
Довольно широкий класс алгоритмов может быть получен, если для перерасчета расстояний использовать следующую общую формулу:
di+j, k = A(w) min(dik djk) + B(w) max(dik djk), где
A(w) = , если dik Ј djk
A(w) = , если dik > djk
B(w) =, если dik Ј djk
B(w) = , если dik > djk
где ni и nj - число элементов в кластерах i и j, а w –свободный параметр, выбор которого определяет конкретный алгоритм. Например, приw = 1 мы получаем, так называемый, алгоритм “средней связи”, для которого формула перерасчета расстояний принимает вид: di+j, k =
В данном случае расстояние между двумя кластерами на каждом шаге работы алгоритма оказывается равным среднему арифметическому из расстояний между всеми такими парами элементов, что один элемент пары принадлежит к одному кластеру, другой - к другому.
Наглядный смысл параметра w становится понятным, если положить w ® Ґ. Формула пересчета расстояний принимает вид: di+j, k = min (di, k djk)
Это будет так называемый алгоритм “ближайшего соседа”, позволяющий выделять кластеры сколь угодно сложной формы при условии, что различные части таких кластеров соединены цепочками близких друг к другу элементов. В данном случае расстояние между двумя кластерами на каждом шаге работы алгоритма оказывается равным расстоянию между двумя самыми близкими элементами, принадлежащими к этим двум кластерам.
Довольно часто предполагают, что первоначальные расстояния (различия) между группируемыми элементами заданы. В некоторых задачах это действительно так. Однако, задаются только объекты и их характеристики и матрицу расстояний строят исходя из этих данных. В зависимости от того, вычисляются ли расстояния между объектами или между характеристиками объектов, используются разные способы. В случае кластер анализа объектов наиболее часто мерой различия служит либо квадрат евклидова расстояния
(где xih, xjh - значения h-го признака для i-го и j-го объектов, а m- число характеристик), либо само евклидово расстояние. Если признакам приписывается разный вес, то эти веса можно учесть при вычислении расстояния
Иногда в качестве меры различия используется расстояние, вычисляемое по формуле:
которые называют: "хэмминговым", "манхэттенским" или "сити-блок" расстоянием. Естественной мерой сходства характеристик объектов во многих задачах является коэффициент корреляции между ними
где mi , mj , di , dj - соответственно средние и среднеквадратичные отклонения для характеристик i и j. Мерой различия между характеристиками может служить величина 1 - r. В некоторых задачах знак коэффициента корреляции несуществен и зависит лишь от выбора единицы измерения. В этом случае в качестве меры различия между характеристиками используетсяф1 - ri j ф
1. 5 Число кластеров.
Очень важным вопросом является проблема выбора необходимого числа кластеров. Иногда можно m число кластеров выбирать априорно. Однако в общем случае это число определяется в процессе разбиения множества на кластеры. Проводились исследования Фортьером и Соломоном, и было установлено, что число кластеров должно быть принято для достижения вероятностиaтого, что найдено наилучшее разбиение. Таким образом, оптимальное число разбиений является функцией заданной долиbнаилучших или в некотором смысле допустимых разбиений во множестве всех возможных. Общее рассеяние будет тем больше, чем выше доляbдопустимых разбиений. Фортьер и Соломон разработали таблицу, по которой можно найти число необходимых разбиений. S(a, b) в зависимости от a и b (где a - вероятность того, что найдено наилучшее разбиение, b - доля наилучших разбиений в общем числе разбиений) Причем в качестве меры разнородности используется не мера рассеяния, а мера принадлежности, введенная Хользенгером и Харманом. Таблица значенийS(a, b) приводится ниже. Таблица значений S(a, b)
b \ a
0. 20
0. 10
0. 05
0. 01
0. 001
0. 0001
0. 20
8
11
14
21
31
42
0. 10
16
22
29
44
66
88
0. 05
32
45
59
90
135
180
0. 01
161
230
299
459
689
918
0. 001
1626
2326
3026
4652
6977
9303
0. 0001
17475
25000
32526
55000
75000
100000
Довольно часто критерием объединения (числа кластеров) становится изменение соответствующей функции. Например, суммы квадратов отклонений: Процессу группировки должно соответствовать здесь последовательное минимальное возрастание значения критерияE. Наличие резкого скачка в значении Eможно интерпретировать как характеристику числа кластеров, объективно существующих в исследуемой совокупности.
