12.3. ОБОБЩЕНИЕ МЕТОДА АДАПТИВНЫХ РАССТОЯНИЙ

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

12.3.1. Обозначения

Пусть

множество элементов, подлежащих классификации;

множество разбиений на классов;

множество, элементами которого являются наборы вида где А определяется в каждом конкретном случае;

— множество показателей сходства между элементами и элементами

множество, элементы которого имеют вид

функция, определенная в со значениями в

функция, определенная в со значением в

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

Критерием является функция определенная в пространстве со значениями в

где

Мы ищем тройку минимизирующую этот критерий.

12.3.3. Алгоритм

Алгоритм может быть сведен к схеме, приведенной на рис. 12.5. Он сконструирован на основе трех функций.

Рис. 12.5

1) Функция назначения определенная на со значениями в позволяет по формировать классы по правилу:

2) Функция представительства g, определенная на со значениями в позволяет по находить представительство в котором удовлетворяют условию:

3) Функция определенная на со значениями в определяет метрики в где удовлетворяют условию:

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

где

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

12.3.4.1. Сходимость

В работе [5] доказывается следующий результат. Предложение. Если I выражается через так что выполнены условия из 12.3.5, хотя бы одно из множеств А или 3) конечно, отображение инъективно, то последовательность сходится, а соответствующая последовательность значений критерия убывает.

12.3.5. Ограничения на конструкцию алгоритма

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