§ 11.1. Алгоритм автоматической классификации

11.1.1. Распределение объектов по М классам.

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

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

X — вектор, составленный из т. е.

и

Критерий качества классификации является функцией от и X:

По определению, наилучшая классификация удовлетворяет условию

либо

В этом параграфе мы будем рассматривать лишь условие (11.4), так как для условия (11.5) рассуждение проводится аналогично.

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

Пусть на итерации мы имеем классификацию где

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

Если величина отрицательна, то перенесение объекта в класс дает улучшение классификации. На этом основан следующий алгоритм:

Шаг 1. Выбрать начальную классификацию

Шаг 2. Для данной I-й классификации явычислить для

Шаг 3. Для всех перенести объект в класс где определяется из условия

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

Шаг 4. Если возвратиться к шагу 2; в противном случае работа алгоритма закончена.

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