3.7. КЛАССИФИКАЦИЯ ПРИ ТРЕБОВАНИИ РАВЕНСТВА ОБЪЕМОВ КЛАССОВ

3.7.1. Задача

Рассмотрим подробный пример практического использования ММДС. Речь идет об определении разбиения на классов одинакового объема высокой плотности.

В целях упрощения рассмотрим евклидово пространство где любое определяется парой чисел:

В терминах математического программирования наша задача состоит в следующем:

где

и центр тяжести класса, т. е.

Другими словами, мы ищем разбиение на классы одного и того же объема такое, чтобы сумма внутриклассовых дисперсий была минимальна. Эту задачу можно представить разными способами; в частности, в [8] она была исследована с помощью динамического программирования. Можно сформулировать задачу, выражая ограничение на объемы классов в форме второго критерия тогда приходим к следующему:

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

3.7.2. Выбранный порядок

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

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

3.7.3. Представительство

Для первого критерия (минимизация дисперсии) определим представительство следующим образом:

где множество центров тяжести всевозможных подмножеств

Пространство представительств для второго критерия (выражающего ограничение на объем классов) опишем в виде

где пространство есть совокупность всех троек

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

3.7.4. Мультисходство

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

Вторая координата определяет отображение пространства на

Иными словами, элементы, находящиеся вне круга, определяемого тройкой «штрафуются».

3.7.5. Мультикритерий W2 и оптимизационная задача

В данном случае мультикритерий задает отображение пространства на положительную четверть плоскости а именно

Другими словами, штрафу подвергаются точки каждого класса внешние по отношению к кругу

Для сравнения величин используем обратный лексикографический порядок на который был определен в 3.7.2.

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

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

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

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

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

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

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

3.7.7. Описание алгоритма

Алгоритм реализуется следующим образом. Отправляются как от исходной точки от некоторого начального разбиения как-то подобранного или выбранного случайно. Каждому классу соответствует круг который содержит число точек множества равное заданному или наиболее близкое к нему, и имеет минимально возможный радиус. Затем каждая точка относится к ближайшему «представителю», для определения которого используется расстояние до центров тяжести классов если точка находится внутри пересечения или вне двух некоторых кругов, например, определенных тройками В противном случае точка назначается в класс, соответствующий кругу, в котором она находится. С новым разбиением, полученным таким образом, повторяется тот же процесс, и так до достижения сходимости, которая имеет место в соответствии с теоремой 1. Заметим, что если существует покрытие множества непересекающимися кругами, каждый из которых содержит точек то глобальный минимум критерия является нулевым (нулевое значение получается по крайней мере с помощью этого покрытия).

3.7.8. Искусственный пример

Пусть множество состоит из 8 точек (рис. 3.3 (а)). Требуется найти разбиение на 2 класса с минимальной внутриклассовой дисперсией и одинаковым объемом классов

На рис. 3.3 (б) схематически дается произвольное начальное разбиение Элементы класса 1 обозначены точками, а класса 2 — крестиками. Каждая итерация состоит в вычислении нового разбиения и его представительства. Во время 1-й итерации определяются центры тяжести, для обозначения которых используются те же символы, но очерченные кругом.

Рис. 3.3

После вычисления ядер на следующей итерации получаем разбиение с 2 неравными группами (рис. 3.3 (в)). Однако в ходе 2-й итерации вычисляются наилучшие ядра, а решение, полученное в результате 3-й итерации, является оптимальным (рис. 3.3 (г)).

3.7.9. Выбор других геометрических конструкций

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

3.7.10. Область применения

Задача поиска классов, обладающих слабой инерцией и равными объемами, часто встречается на практике: в информатике для реструктуризации программ [5], при перенумерации в системах виртуальной памяти [2], при реорганизации баз данных [6], так же как при локализации процессоров центрального устройства в сетях ЭВМ [3]. Во всех этих примерах всегда имеется набор данных, на которых определяются критерий (иногда несколько) и ограничения, имеющие вид, описанный

в 3.1.2. Несмотря на разнообразие свойств различных приложений, все эти задачи можно сформулировать в терминах многокритериальной классификации и использовать для решения алгоритма ММДС.

3.7.11. Программная реализация алгоритма

Программа решения задачи разбиения заданного множества элементов на классы равного объема была записана на языке Фортран Ханани (1979 г.), который в [7] описал пример ее использования. Имеющийся экспериментальный опыт свидетельствует, что объем необходимой памяти для реализации такой программы приблизительно является линейной функцией числа классифицируемых точек

3.8. заключение

Мы дали формулировку алгоритма динамических сгущений с несколькими критериями и показали, что его свойства сходимости те же самые, что свойства классического алгоритма динамических сгущений. Более того, мы продемонстрировали с помощью детального примера, что ММДС дает общий подход к решению большого семейства задач по классификации при наличии ограничений. Таким образом, ММДС открывает возможности широкого спектра исследований: изучение различных проблем с ограничениями, обеспечивающими соответствие критерия и используемого представительства классов; изучение различных отношений порядка исследование других структур помимо разбиений, например многокритериальных иерархий, и т.д. Наконец, было бы интересно установить связь с бикритериальным подходом, предложенным Делаттром в [4].