16.2. АДАПТИВНЫЕ УЛЬТРАМЕТРИКИ

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

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

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

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

16.2.2.1. Ультраметрика на множестве Е

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

16.2.2.2. Представитель подмножества относительно ультраметрики

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

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

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

16.2.2.4. Критерий

Введем критерий отображающий

где

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

Требуется найти такие, чтобы выражение (1) обратилось в минимум. В 16.2.3.1 будет показано, что вместо можно искать набор ультраметрик такой, что

16.2.3. Алгоритм

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

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

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

Замечание. Получается, что не что иное, как где если

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

Функция представительства является отображением пространства и каждому ставит в соответствие

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

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

16.2.3.3. Сходимость алгоритма

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

Теорема 1. Последовательность убывает.

Доказательство. В самом деле, по построению

где, если

16.2.4. Примеры применения МДС с использованием адаптивных ультраметрик

16.2.4.1. Деревья

Пусть на определено множество деревьев и введена мера сходства Это позволяет каждому дереву поставить в соответствие ультраметрику [5]. При этом 3) является множеством всех таких ультраметрик Функции определяются в работе [5]. Отображение в этом случае характерно тем, что при образ разбиения такой, что для всех является максимальной субдоминантной ультраметрикой, определенной на

Замечание. Один из недостатков описанного в 16.1.3 алгоритма заключается в том, что для рассматриваемого случая он требует вычисления максимальной субдоминантной ультраметрики на множестве Поэтому рассматриваемый алгоритм можно применять лишь к небольшим множествам данных. В работе [11] для решения данной задачи используется другой алгоритм. Он не требует вычисления и запоминания максимальной субдоминантной ультраметрики, поэтому освобождается память для обработки больших массивов данных и сокращается время работы алгоритма.

16.2.4.2. Дихотомические иерархии

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

Каждой иерархии дихотомического разбиения множества поставим в соответствие ультраметрику определенную на Тогда множество 3) будет состоять из всех таких ультраметрик. Подробно этот пример рассматривается в работе [5]. Обратим внимание лишь на то, что отображение имеет тот же вид, что и в предыдущем примере, и замечание о недостатках алгоритма также сохраняет силу.

16.2.4.3. Пример с искусственными данными

Талица данных (см. скан)

Исходные ядра были взяты наугад: точки с номерами 10 и 15. Разбиение, полученное по начальным ядрам, приводится на рис. 16.1.

Рис. 16.1

Рис. 16.2

Единицам соответствуют точки, попавшие в первый класс, а двойкам — во второй. Окончательное разбиение изображено на рис. 16.2. Полученные ядра обведены кружками. Если при разбиении на два

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

(см. скан)

На рис. 16.3, 16.4 приводится иерархия на множестве и ее разбиение.

(кликните для просмотра скана)

Рис. 16.6. Иерархии, соответствующие деревьям полученные в результате работы программы

На рис. 16.5, 16.6 приводится иерархия А, составленная из иерархий полученных классов, и ее разбиение на

16.2.5. Заключение

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