Глава 16. АДАПТИВНЫЕ УЛЬТРАМЕТРИКИ И ПОИСК ОПТИМАЛЬНОЙ ИЕРАРХИИ

16.1. ВВЕДЕНИЕ

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

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