1.3. ИССЛЕДОВАНИЕ ОДНОГО ВАЖНОГО ЧАСТНОГО СЛУЧАЯ

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

Пространство покрытий есть т. е. множество разбиений на классов.

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

Допущение 1. Предположим, что минимум существует и он является единственным, каково бы ни было А из

Допущение 2. .

Замечание 1. В записи допущения 2 мы применили для упрощения обозначений знак суммы. Однако на самом деле закон с можно было бы заменить любым другим законом с при условии, что он будет ассоциативным, коммутативным и удовлетворяющим следующему условию монотонности:

1.3.2. Критерий и задача оптимизации

Пусть (k - кратное прямое произведение), возьмем в качестве критерия отображение такое, что или, иначе, Отображение измеряет таким образом «степень адекватности» между разбиением и представительством его классов

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

Замечание 2. В отношении определения критерия можно сделать то же замечание 1 для суммы

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

Это есть преобразование такое, что при и где элемент пространства который минимизирует

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

Это есть преобразование такое, что где в случае

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

1.3.5. Построение алгоритма

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

1.3.6. Изучение свойств алгоритма

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

Предложение 1. Последовательность сходится убывая.

Доказательство. Мы покажем, что Первое неравенство справедливо, поскольку для любого

откуда при суммировании по

Второе неравенство записывается следующим образом:

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

Предложение 2. Последовательность сходится.

Доказательство. Известно, что всякая последовательность, сходящаяся на конечном множестве, достигает своего предела. Это относится как раз к последовательности поскольку рассматриваемое нами пространство конечно.

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

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

1.3.7. Свойства полученного решения

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

б) Полученное представительство позволяет построить функцию назначения. Эта функция каждому элементу из ставит в соответствие такой класс с индексом что (В случае неединственности минимума следует брать наименьший индекс.)

в) Можно получить несколько решений, меняя выбор исходного разбиения Если же следует выбрать всего одно решение, то в качестве такового должно быть принято решение, дающее наилучшее значение критерия. Интересно исследовать множество решений с тем, чтобы извлечь из него информацию, которая может быть использована на практике; таковы, например, группы объектов (мы называем их «устойчивые (или сильные) формы»), которые находятся всегда в одном и том же классе независимо от того, какое решение рассматривается. Более подробно этот вопрос освещен в [1].