Глава 8. ИЕРАРХИЧЕСКАЯ КЛАССИФИКАЦИЯ

8.1. Основные определения

Пусть — конечное множество.

Определение 8.1. Иерархией s на X называется система подмножеств (классов) такая, что

1)

2)

3) если классы S и 5 из s имеют не пустое пересечение, то либо

Пример 8.1. Пусть Тогда система подмножеств является иерархией на X. Исследование структуры иерархий удобно вести в терминах теории графов [83].

Определение 8.2. Графом иерархии s на X называется ориентированный граф , вершины которого соответствуют множествам , а ребра —парам , таким, что: не существует для которого .

Ребро изображается стрелкой с началом S и концом

Пример 8.2. Граф иерархии s из примера 8.1 имеет множество вершин: (рис 8 1). В графе иерархии вершина может быть концом нескольких стрелок, но, как следует из определения 8 1, она является началом только одной стрелки.

Определение 8.3. Иерархия называется бинарной, если любое множество , содержащее более одного элемента, является объединением множеств из s, где

Рис. 8.1. Граф иерархии s из примера 8.1

Иерархия s из примера 8.1 не является бинарной, так как множество нельзя представить в виде объединения двух множеств . Нетрудно показать, что в любой бинарной иерархии s разбиение множества на подмножества S и S" из 6, т. е. представление однозначно. Иерархия является бинарно» тогда и только тогда, когда в ее графе каждая вершина, соответствующая множеству, содержащему более одного элемента, является концом двух стрелок.

Определение 8.4. Иерархическом классификацией данного множества объектов называется построение иерархии s на X, отражающей наличие однородных, в определенном смысле, классов X и взаимосвязи между классами.

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

Графы иерархий, полученных при помощи этих алгоритмов, называются соответственно дивизимными и агломеративными Если их изобразить на плоскости так, как на рис 8.2, то видно, что они описывают процедуру классификации при движении вверх по оси ординат Поэтому дивизимные алгоритмы называют также нисходящими (движение против стрелок), а агломеративные — восходящими (движение вдоль стрелок).