5.3. АЛГОРИТМЫ КЛАССИФИКАЦИИ

Для обеспечения оптимальной классификации необходимо рассмотреть все возможные ее варианты. При больших вычислить эффективность метасистемы для всех вариантов нереально. Поэтому, как правило, приходится использовать алгоритмы автоматической классификации [1, 25, 48], которые реализуются с помощью ЭВМ. Известно несколько подходов к построению таких алгоритмов [1, 25], которые можно по основному признаку разделить на две группы: при заданном числе классов М и неизвестном.

5.3.1 КЛАССИФИКАЦИЯ ПРИ ЗАДАННОМ ЧИСЛЕ КЛАССОВ

Когда число классов задано заранее, классификация сводится к распределению объектов типов по М классам так, чтобы экстремизировать выбранный метакритерий эффективности

Эту задачу можно решить с помощью итеративных поисковых алгоритмов [1, 25]. Идея, положенная в их основу, с учетом особенностей формулировки задачи (§ 5.2) может быть представлена следующим образом.

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

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

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

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

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

1. Выбрать начальное

2. Для итерации, вычислить

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

4. Если возвратиться к . В противном случае классификация завершена.

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

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