Алгоритм построения иерархического разбиения (дендограмм) задач управления СОТС

Для построения иерархического разбиения множества задач А могут быть использо­ваны методы [2, 4, 8]соединительного иерархического кластерного анализа, общий алго­ритм которых может быть представлен в следующем виде:

Шаг 0. За исходное разбиение R₀принять тривиальное разбиение множества задач A на n одноэлементных кластеров R₀ ={A_i, i=1, 2, …,n}, где A_i={a_i}. Положить начальный уровень раз­биения l=0.

Шаг 1. Для заданного уровня разбиений lнайти наибольшее зна­чение (в частности, целевого или функционального) сходства между кластерами

. Значение сходства определяется с использованием отображений соответственного целевого и функционального сходства g и f.

Шаг 2. Объединить соответствующие кластеры с наибольшим сходс­твом в один кластер и образовать новое разбиение A_s=A_q È A_t. Положить l равное l+1.

Шаг 3. Проверить выполнение условия: card R_l=1 – мощность множества R_l(все задачи объединены в один кластер). Если оно выполняется, то завершить выполнение алгоритма. Если не выполняется, то пе­рейти на шаг 4.

Шаг 4.Пересчитать значения сходства для кластеров нового раз­биения по одной из приведенных ниже формул и перейти на шаг 1.

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

1) метод ближайшего соседа (сильной связи):

2) метод дальнего соседа (слабой связи):

3) метод простого среднего (средней связи):

Для построения иерархического разбиения по целевому сходству T_gв качестве y используется отображение g, а по функциональному сходству T_f – отображение f.

Пример.

Проиллюстрируем работу описанного алгоритма с использованием метода ближайшего соседа для следующих исходных данных:

А={а₁, а₂, а₃, а₄}, отображение целевого сходства gзадано матрицей

Начальное разбиение R₀={{а₁}, {а₂}, {а₃}, {а₄}}. Максимальное сходство между А₃ и А₄ равно 0.9, что требует объединения указанных кластеров в один и построение нового разбиения R₁={{а₁}, {а₂}, {а_3, а₄}}. Произведем пересчет целевого сходства для нового разбиения методом ближайшего соседа:

.

Максимальное сходство между А₁={а₁} и А^’₃={ а_3, а₄} равно 0.8, что требует объединения указанных кластеров в один и построение нового разбиения R₂={{а₂}, {а₁, а_3, а₄}}. Произведем пересчет целевого сходства для нового разбиения методом ближайшего соседа:

.

Последнее объединение всех задач в исходное множество А={а₁, а₂, а₃, а₄} со значением целевого сходства 0.7.

Полученное иерархическое разбиения T_g изображается графичес­ки (рис. 7) в виде графа специального вида, получившего название дендрограммы (ребра графа идут параллельно вертикаль­ной оси, которая изображает целевое сходство кластеров разби­ений различных уровней).