Основы теории систем и системного анализа. Матвеев Ю.Н. - 40 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

40
Число способов разбиения
n объектов на m классы определяется как
∑
=
−−=
m
j
njj
m
jmC
m
mnS
0
)()1(
!
1
),( , (1.30)
где
j
m
C – число сочетаний j объектов из m.
При полном переборе целевую функцию W придется вычислять S
раз, а затем искать такое разбиение, которое приводит к минимуму W.
Несомненным достоинством данного алгоритма является то, что в
конце работы он дает оптимальный результат. Однако при большом
количестве классов и объектов затраты вычислительных и временных
ресурсов настолько велики, что
алгоритм становится непригодным.
1.12.4. Классический последовательный алгоритм
Классический последовательный алгоритм относится к
иерархическим алгоритмам группирования, основанным на понятиях
«сходство» и «расстояние».
Основная идея всех иерархических алгоритмов заключается в
следующем. На первом шаге каждый из
n объектов считается отдельным
кластером. Затем два наиболее близких объекта (кластера) объединяются в
один новый кластер, и число кластеров становится равным
n-1. Эта
процедура повторяется, пока все объекты не объединятся в один кластер.
Результаты работы иерархических алгоритмов обычно оформляются
в виде дендрограммы (рис. 1.10), в которой приведены номера
объединяемых объектов и значения меры сходства, при которых эти
объекты были объединены.
Рис. 1.10. Иерархическое группирование
По такой дендрограмме можно определить:
• составы кластеров при заданном уровне сходства;
• составы кластеров при их заданном количестве.

Страницы