8.4. Приложения общей рекуррентной формулы для мер близости между классами

8.4.1. Расчет матрицы взаимных близостей классов данного уровня иерархии.

Рассмотрим более подробно переход от разбиения к разбиению на шаге агломеративного алгоритма.

Имеем Вычислим матрицу взаимных расстояний между классами разбиения и найдем пару классов , такую, что

Пусть где Тогда положим

Следовательно, для получения матрицы взаимных расстояний можно воспользоваться матрицей вычислив дополнительно только расстояния при фиксированном i. Так как то для этого оказывается полезной рекуррентная формула Жамбю [248]:

обобщающая формулу Ланса и Вильямса (5.9).

8.4.2. Условия на меру близости, обеспечивающие отсутствие инверсий.

Эти условия дает результат, полученный Г. Миллиганом [248].

Теорема 8.1. Пусть s — иерархия на множестве X, полученная при помощи меры близости Для которой верна формула (8.9). Тогда, если для то отображение задаваемое формулой и условием , является индексацией.

Пример 8.5. Пусть — набор точек в евклидовом пространстве и

где — центры классов . Тогда верна формула

с формулой (5.10), где . В обозначениях формулы (8.9) имеем:

Имеем т. е. все условия теоремы Г. Милигана выполняются и поэтому мера близости (8.10) не имеет инверсий.

Замечание. Из (8.10) следует, что

где Таким образом, введение множителя позволяет исправить инверсию меры близости из примера 8.4, которая удовлетворяет формуле (8.9) с параметрами:

Здесь

8.4.3. Алгоритм гибкой стратегии иерархической классификации.

Формула Жамбю (8.9) позволяет обобщить гибкую стратегию Ланса и Вильямса [150].

Пусть исходная информация о классифицируемых объектах представлена в форме матрицы взаимных расстояний

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

Напомним, что v на нулевое отображение. Тогда, подобрав любым способом параметры удовлетворяющие теореме 8.1, получаем возможность при помощи формулы Жамбю вычислить матрицу взаимных расстояний между классами разбиения а при помощи формулы — индексирующее отображение

8.4.4. Процедуры иерархической классификации, использующие пороговые значения.

Как уже отмечалось выше, трудности реализации классических алгоритмов иерархической классификации (см. п. 8.2.2) быстро растут с ростом числа классифицируемых объектов. Это объясняется тем, что на шаге алгоритма для каждого приходится искать минимальный элемент в матрице взаимных расстояний т. е. находить минимальный элемент в массиве из чисел. Ясно, что минимальный элемент в матрице достаточно искать среди ее элементов, не превосходящих некоторый порог с, а массив таких элементов при соответствующем выборе порога с содержит элементов намного меньше, чем . В связи с этим разрабатываются процедуры иерархической классификации, использующие пороговые значения. Общая схема подобных процедур следующая: задается или формируется в процессе классификации последовательность порогов . На первом этапе алгоритма попарно объединяются элементы, а затем и классы, меры близости которых не превосходят На втором этапе — и т. д., пока все элементы не объединятся в один класс. Эффективность таких процедур существенно зависит от внутренней структуры исследуемого множества объектов, от выбора последовательности пороговых значений и меры близости между классами. Сравнительно недавно было показано, что если мера близости обладает свойством редуктивности (см. определение 8.7), то процедуры иерархической классификации, использующие пороговые значения, позволяют построить точно такую иерархию, что и классические агломеративные процедуры, но рабо-. тают они существенно быстрее последних Этим вопросам посвящен § 8.5.

Опишем свойство редуктивности мер близости и способ его проверки.

Пусть — бинарная иерархия, полученная агломеративным алгоритмом при помощи меры близости пара классов, которая объединяется в один класс на уровне иерархии.

Определение 8.7. Мера близости обладает свойством редуктивности (является редуктивной), если для любого класса и порога такого, что с, из условий вытекает, что

Для мер близости удовлетворяющих формуле Жамбю (8.9), свойство редуктивности проверяется при помощи следующего теоретического результата:

Теорема 8.2 (Диде). Если параметры , меры близости удовлетворяют условиям , то мера близости является редуктивной.

Сравнивая утверждения теорем 8.1 и 8.2, получаем, что для каждой редуктивной меры близости отображение является индексацией соответствующей ей иерархии

Пример 8.6. Для меры близости из примера

8.5 имеем: при рещение внутриклассового разброса при объединении классов является редуктивной мерой близости между классами. Другие важные примеры рассмотрены в § 8.5.