II. ПОДХОД К ПОСТРОЕНИЮ ОБЩЕЙ ТЕОРИИ АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ

Отсутствие достаточно полных и глубоких монографий по автоматической классификации объясняется, на наш взгляд, тем, что теория, на базе которой можно было бы «навести порядок» в огромном множестве алгоритмов АК, возникающих из нужд разнообразных приложений, еще не создана. Отсутствие теории означает, по существу, отсутствие подходов к систематизации и развитию идей АК, а это в свою очередь препятствует разработке новых алгоритмов, их сравнительному анализу. Предлагаемая книга вносит существенный вклад в развитие такой теории. В частности, она дает достаточно общий способ описания разнообразных алгоритмов АК. Однако, позволяя генерировать широкий класс алгоритмов АК, структура МДС не содержит такого набора управляемых параметров метода, который давал бы возможность устанавливать конструктивные связи между различными алгоритмами, производить их сопоставление и сравнительный анализ. К тому же существуют важные классы алгоритмов А К, не укладывающихся в схему МДС (например, «Форель», см. [15]). Ниже, следуя [61, [7], мы излагаем подход к построению общей теории АК. В частности, будет показано, как в рамках этого подхода преодолеваются указанные трудности. Описываемый подход опирается на следующую идею. Все многообразие алгоритмов АК представляется в виде иерархической структуры. На самом верхнем уровне находится универсальная математическая модель, компоненты которой образуют средство для единообразной постановки задач АК и описания алгоритмов их решения. На самом нижнем располагаются «движения» конкретных алгоритмов (определение «движения» алгоритма дано ниже). Переход на более низкие Уровни происходит за счет конкретизаций, наполняющих компоненты структуры модели информацией о характере данных, конечной цели классификации, априорных гипотезах, результатах предварительной обработки и т. п.

Предлагаемый подход имеет три аспекта:

А. Исследование модели АК как математической структуры с целью получения условий сходимости алгоритмов и описания класса Функционалов, оптимизируемых ими.

Б. Сопоставление различных известных алгоритмов и разработка методов целенаправленного конструирования новых алгоритмов,

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

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

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

В описании нашей математической конструкции мы используем терминологию и результаты книги [2].

Начнем с описания компонент универсальной математической модели АК.

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

— множество состояний, в которых выборка участвует в алгоритме. Содержательно эта компонента описывает допустимые классификации, возникающие на шагах алгоритма. В терминологии книги это пространство покрытий, но мы более конкретизируем эту компоненту, считая каждый элемент отображением выборки в множество множество значений классификаций. Состав и структура определяют тип решаемой задачи, т. е., по существу, дают средство ответить на вопрос: Какую задачу классификации предполагается решить? Например, когда список номеров классов, то множество совпадает с множеством разбиений выборки на К непересекающихся классов: где Если упорядоченное множество, то это соответствует классификации с предпочтением или иерархической классификации. Задачам нечеткой классификации отвечает где — вещественные числа, такие, что более формально в этом случае симплекс, вершины которого соответствуют номерам классов, а координаты точек симплекса — вероятностям (или степеням) принадлежности к классам. Очевидно, что наличие априорных сведений о типе задачи АК, о допустимых классификациях приводят к ограничениям, выделяющим множество в множестве всех отображений. Например, наличие в обучающей (верифицированной) подвыборки приводит к условиям вида для Итак, чтобы задать необходимо формализовать задачу, т. е. указать и сформулировать условия, выделяющие в множестве всех отображений

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

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

Если предполагается описывать классы эталонными множествами, то в качестве берется соответствующая часть множества всех подмножеств в Множество может иметь совершенно иную природу, чем пространство измеряемых признаков. Например, в факторном типологическом анализе (см. гл. 6) точкой является -мерное аффинное подмногообразие в Более того, само может быть составлено из пространств различной природы соответственно требованиям к эталонам различных классов. Отметим, что на этом пути удалось включить в нашу модель известные алгоритмы, формально не описываемые методом динамических сгущений (например, «Форель» [13]), а также построить новые алгоритмы (подробнее см. ниже).

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

оператор из называемый классификатором, поскольку он определяет, что нужно сделать с имеющимися средствами для данного типа задачи АК, чтобы из предыдущего состояния выборки с описанием перейти в другое состояние при поступлении очередной порции т. е. провести переклассификацию. Частным случаем оператора является функция назначения (см. гл. 1). Обычно оператор X строится исходя из функционала оценивающего качество классификации, согласно априорному представлению исследователя о «хорошей» классификации. Рассмотрим, например, как строится оператор в исторически одном из первых и наиболее общем алгоритме разбиения на К классов методом локальной оптимизации. Пусть некоторая классификация и Обозначим через новую классификацию: если Фиксируем критерий качества классификации и определим оператор для алгоритмов последовательного типа (т. е. когда формулой

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

Тогда

Отметим, что приведенный классификатор используется в алгоритме равномерного распределения объектов по К классам, где функционал имеет вид (см. [2])

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

где описывает, насколько объект х близок ядру В этом случае классификатор можно взять в виде

Отметим, что когда функционал не завйсит от приведенный классификатор совпадает с функцией назначения

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

К классов оператор строится исходя из функционала вида

по формуле

Таким образом, вычисление значений дескриптора является процедурой минимизации функционала на Здесь основная идея МДС сталкивается с серьезной проблемой. Нетривиальные примеры выбора представительств классов приводят к необходимости брать в качестве достаточно сложные многообразия (см., например, для факторного типологического анализа). Стандартные функционалы позволяющие эффективно вычислять значения дескриптора в случае алгоритма -средних, когда при переносе на многообразия аффинных подмногообразий в теряют свойство единственности решения задачи на минимум. Авторам книги приходится прибегать к искусственным приемам выбора одного из возможных значений дескриптора, что в свою очередь вызывает усложнение условий остановки алгоритма. В связи с этим отметим, что в работах [4], [5] развиты методы оптимизации широкого класса функционалов на многообразиях аффинных подмногообразий евклидова пространства .

G — оператор из (где множество натуральных чисел), который можно рассматривать как генератор порций.

Определение 1. Моделью алгоритма называется набор компонент, наделенных описанной выше структурой.

Определение 2. Движением алгоритма, отвечающим начальным данным называется последовательность

где

Определение 3. Функционал называется интерпретирующим для модели, если

для всех начиная с некоторого причем

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

«покоординатной» минимизации функционала на Но даже в этом случае, очевидно, существует много других функционалов, интерпретирующих данное движение алгоритма, т. е. если операторы и 3) уже заданы, то функционал восстанавливается по ним далеко не однозначно.

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