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

Для построения иерархического разбиения множества задач А могут быть использо­ваны методы [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.