Составители:
Рубрика:
14
Шаг 0. За исходное разбиение R
0
принять тривиальное разбиение
множества задач A на n одноэлементных кластеров R
0
= {A
i
, i = 1, 2,…, n},
где A
i
= {a
i
}. Положить начальный уровень разбиения l = 0.
Шаг 1. Для заданного уровня разбиений l найти наибольшее зна"
чение (в частности, целевого или функционального) сходства между
кластерами
,
(,) max (,)
ij l
qt ij
AA R
AA AA121
. Значение сходства опреде"
ляется с использованием отображений соответственного целевого и
функционального сходства g и f.
Шаг 2. Объединить соответствующие кластеры с наибольшим сход"
ством в один кластер и образовать новое разбиение A
s
= A
q
È A
t
. Поло"
жить l, равное l+1.
Шаг 3. Проверить выполнение условия: card R
l
= 1 – мощность
множества R
l
(все задачи объединены в один кластер). Если оно вы"
полняется, то завершить выполнение алгоритма. Если не выполня"
ется, то перейти на шаг 4.
Шаг 4. Пересчитать значения сходства для кластеров нового раз"
биения по одной из приведенных ниже формул и перейти на шаг 1.
Пересчет значений сходства для кластеров нового разбиения мож"
но осуществлять по следующим формулам, каждая из которых ассо"
циируется с названием соответствующего метода иерархического
кластерного анализа:
1) метод ближайшего соседа (сильной связи):
(,)max{(,),(,)}, .
sk qk tk k l
AA AA AA A R121 1 34
2) метод дальнего соседа (слабой связи):
(, )min{(, ),(, )}, .
sk qk tk k l
AA AA AA A R121 1 34
3) метод простого среднего (средней связи):
(, )((, ) (, ))/2, .
sk qk tk k l
AA AA AA A R1213 1 4 5
Для построения иерархического разбиения по целевому сходству
T
g
в качестве y используется отображение g, а по функциональному
сходству T
f
– отображение f.
Пример
Проиллюстрируем работу описанного алгоритма с использовани"
ем метода ближайшего соседа для следующих исходных данных:
A = {a
1
, a
2
, a
3
, a
4
}, отображение целевого сходства g задано матри"
цей
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
