15.2. МЕТОД, ИСПОЛЬЗУЮЩИЙ ЦЕНЫ СОЗДАНИЯ КЛАССОВ

15.2.1. Введение

Один из возможных подходов к определению числа классов, на которые следует разбить множество состоит во включении в критерий цены создания класса. Таким образом, мы приходим к задаче о назначении [2], [8]. В наиболее простой форме ее можно представить как определение оптимального положения К центров обслуживающих клиентов разбросанных по некоторой территории. Каждому центру ставится в соответствие — цена его размещения. Каждому клиенту соответствует Цена прикрепления клиента к центру. Если в качестве решения взять некоторое подмножество центров то цена этого решения будет состоять из

— цены размещения центров и

— цены прикрепления клиентов к центрам

Задача заключается в определении такого что

Оптимальное решение всегда является компромиссом между двумя крайними решениями:

1) N = L. При этом цена минимальна, но достигает максимума;

2) множество состоит из единственного центра который имеет минимальную цену Однако при этом сильно возрастает цена

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

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

15.2.2. Описание метода

Введем следующие обозначения: множество, состоящее из элементов расстояние на подмножество содержащее элементов; система весов на . В задаче о назначении имеет смысл множества клиентов, множества центров.

В дальнейшем будет играть роль пространства представительств. Определим меру адекватности элементов следующим образом:

где цена элемента у.

Алгоритм, описанный в гл. 2, позволяет оптимизировать критерий

где разбиение на классов и множество элементов пространства представительств

определяется по формуле (1) при Формулу (2) можно представить в виде

или

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

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

1. Начальный шаг. Выбираются элементов Выбор может быть случайным или заданным пользователем.

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

в случае равенства

Заметим, что на этом шаге уменьшается только первая сумма в выражении (3), вторая сумма не меняется, так как она зависит только от выбора элементов из

3. Функция представительства. Для каждого класса выбирается новый представитель

4. Критерий остановки итерационного процесса. Если выполняется одно из следующих трех условий, то надо перейти к шагу 5:

а) для всех классов представители не изменились;

б) классы, полученные на двух последних итерациях, идентичны;

в) -где заданное число, значение критерия на итерации.

5. Изменение числа классов. Цена исключения элемента

где минимальное из расстояний между х и элементами кроме

Цена создания нового класса

где расстояние между х и наиболее близким к нему элементом

Если для некоторого то исключение центра вызывает уменьшение критерия. Если для то уменьшения критерия можно достичь созданием нового центра Итак, на этом шаге вычисляются:

Если то ни создание новых классов, ни ликвидация уже имеющихся не могут вызвать уменьшения критерия, т. е. мы достигли локального минимума и должны прекратить работу алгоритма. Если же то следует соответствующим образом изменить число классов и продолжить оптимизацию, вернувшись к шагу 2.

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

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

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

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

где у — элемент из минимизирующий критерий При этом требование влечет

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