1.2. МЕТОД ДИНАМИЧЕСКИХ СГУЩЕНИЙ (МДС)

Перед тем как определить основные этапы этого метода, необходимо ввести некоторые понятия и прежде всего понятия пространства покрытий и пространства представительств.

1.2.1. Пространство покрытий S

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

1.2.2. Структура и пространство представительств

Определение. Говорят, что обладает структурой представительства, если ему сопоставлены множество и отображение множества Тогда называется пространством представительств, а каждый из его элементов I есть одно «представительство» (или один «представитель»); если то называется мерой сходства между объектом х и представителем

Примеры.

а) есть евклидово расстояние в пространстве от х до есть, например, центр тяжести в подмножества из (см. гл. 2).

б) , где X есть семейство евклидовых расстояний. Пусть тогда может быть определено как (см. гл. 5).

Замечание. Мы будем иногда называть (в этом есть, видимо, некоторая языковая неточность, но это часто позволяет избежать двусмысленности) «представительством покрытия» всякое -кратное представительство позволяющее каждому классу покрытия поставить в соответствие представителя

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

Представительство подмножества элементов множества осуществляется обычно в два этапа: а) выбор пространства представительств; б) выбор функции которая позволяет всякому подмножеству множества поставить в соответствие единственное представительство, принадлежащее а именно если то говорят, что I есть представительство подмножества

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

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

представительства, определяемой Найти которое минимизирует в пространстве где есть заданное подмножество

1.2.4. Функция назначения (отнесения объекта к классу)

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

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

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

1.2.5. Основные составные части и структура метода

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

1) выбор пространства покрытий

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

3) определение оптимизируемого критерия; этот критерий представляет собой отображение, обозначенное принимающее лишь положительные значения; это отображение позволяет, используя отображение измерить «степень адекватности» между всяким покрытием и всяким представительством этого покрытия;

4) формулировку задачи оптимизации, целью которой является минимизация критерия эта задача формулируется следующим образом: требуется построить одновременно покрытие и представительство этого покрытия таким образом, чтобы имели наибольшую возможную «степень адекватности» в смысле критерия есть, например, множество разбиений, есть множество разбиений на классов);

5) построение алгоритма (называемого «алгоритмом динамических сгущений»); этот алгоритм состоит в последовательном итеративном

Рис. 1.1

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

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