16.3. АЛГОРИТМ ПОИСКА ОПТИМАЛЬНОЙ ИЕРАРХИИ

16.3.1. Постановка задачи

Методы восходящей иерархической автоматической классификации предназначены для определения на всяком конечном множестве объектов иерархии частей этого множества, иначе говоря, такого разбиения чтобы одни классы включали в себя другие. В этом параграфе мы рассмотрим дихотомические иерархии, определенные на и оптимальные в том смысле, что сумма инерций всех составляющих их классов минимальна. Будем предполагать, что на множестве введена квадратичная метрика

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

16.3.2. Формализация задачи

16.3.2.1 Дихотомическая иерархия на Е

Дихотомической иерархией, определенной на множестве называется такое множество состоящее из подмножеств что

(Первые три условия определяют просто иерархию, четвертое является условием ее дихотомичности.)

Обозначим множество всех дихотомических иерархий на Будем далее предполагать, что на множестве введено квадратичное расстояние

16.3.2.2. Инерция подмножества

Инерцией множества называется величина

где центр тяжести В.

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

достигала минимального значения.

16.3.2.3. Пространство покрытий и пространство представительств

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

16.3.2.4. Оптимизируемый критерий

Критерием является такое отображение что

16.3.2.5. Задача оптимизации

Таким образом, требуется найти и такие, что

В работе [5] доказывается, что такое определение оптимальной иерархии эквивалентно приведенному выше.

16.3.3. Алгоритм

16.3.3.1. Функция представительства

Функцией представительства называется отображение ставящее элементу в соответствие причем

Замечание. Если то где центр тяжести множества

16.3.3.2. Функция назначения

Множество называется цепью иерархии проходящей через элемент у. Пусть

Расстоянием от элемента до цепи иерархии относительно называется величина

Иерархией относительно тройки называется иерархия полученная в результате следующих операций:

1) вычитания из элементов отличных от где В — элемент минимальной мощности, строго содержащий

2) прибавления х ко всем элементам

3) замены В на

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

такой элемент, что

16.3.3.3. Алгоритм

Теперь, имея некоторую иерархию можно построить последовательность где

Этой последовательности будет соответствовать последовательность значений критерия

В работе [5] доказывается теорема о том, что последовательность убывает и сходится.

Замечание. В работах, посвященных рассматриваемой теме, найдены функции назначения которые лучше, чем только что определенная нами функция, поскольку при их использовании алгоритм сходится в более разнообразных ситуациях.