Глава 10. ТЕОРИЯ АВТОМАТИЧЕСКОЙ КЛАССИФИКАЦИИ

10.1. Математическая модель алгоритма автоматической классификации (ААК)

Как и выше, предполагаем, что исходная информация об исследуемой совокупности (выборке) объектов представлена либо в форме матрицы «объект — свойство» либо матрицы взаимных близостей . В случае числовых признаков отождествляем объект с точкой евклидова пространства

Начнем с развернутой характеристики компонент математической модели алгоритма автоматической классификации (АК) [10, 41].

10.1.1. Пространство состояний.

Эта компонента описывает допустимые классификации, возникающие на шагах алгоритма. Так, если результатом шага является разбиение совокупности О на k непересекающихся классов, то — это пространство всех разбиений множества из элементов на фиксированное или нефиксированное число классов в зависимости от того, не зависит или зависит k от номера шага. В алгоритмах метода динамических сгущений роль играет пространство покрытий (см. § 7.4).

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

Например, когда — список номеров классов, то совпадает с множеством разбиений выборки О на k непересекающихся классов

Определение 10.1. Будем считать, что классификация s: выборки О согласована с информацией, выражаемой функцией (обозначение s , если для любого i. В этом случае пространство допустимых классификаций будет иметь вид:

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

10.1.2. Пространство описаний L.

Эта компонента связана с выбором средств информативного описания классов для достижения цели классификации. Например, в алгоритмах метода динамических сгущений роль L играет пространство представительств (см. п. 7.4.1).

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

Пример 10.1. Пусть Тогда, если описывать каждый класс его средним то

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

Роль опорных точек могут играть как реальные представители классов, так и точки, построенные на основе дополнительных сведений — формальные представители классов.

Пример 10.3. Пусть предполагается описывать класс набором из т. его представителей. Тогда — совокупность всех — элементных подмножеств в О.

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

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

10.1.3. Множество порций Р, в которых выборка поступает на классификацию и генератор порций G.

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

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

10.1.4. Классификатор К.

Эта компонента представляет собой оператор из называемый классификатором, поскольку он определяет, что нужно сделать с имеющимися средствами для данного типа Z задачи АК, чтобы из предыдущего состояния выборки О с описанием перейти в другое состояние при поступлении очередной порции , т. е. провести переклассификацию. Частным случаем оператора К. является функция назначения (см. § 7.4). Обычно оператор К. строят исходя из функционала F, оценивающего качество классификации согласно априорному представлению исследователя о «хорошей» классификации.

Пример 10.4. Опишем, как строится оператор К. в исторически одном из первых и наиболее общем алгоритме разбиения на k классов методом локальной оптимизации.

Пусть — некоторая классификация и . Обозначим через новую классификацию: , если Фиксируем критерий качества классификации и определим оператор Для алгоритмов последовательного типа, т. е. когда формулой

Формула 10.1 для классификатора К не налагает практически никаких ограничений на вид функционала F, но в общем случае приводит к довольно медленной процедуре классификации, реализующей минимизацию функционала F способом перебора на дискретном множестве

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

Положим

Опишем алгоритм равномерного распределения объектов по классам, в котором классификатор К. действует по формуле (10.3). В этом алгоритме критерием качества разбиения выборки О на классы является сумма попарных внутриклассовых расстояний между объектами (см. п. 5.4.1), т. е. , где

Пусть ) — статистический разброс класса — центр этого класса — число элементов в нем. Заметим, что

Пусть классификация s относит данный объект к классу

Положим Непосредственно из формул (10.2) и (10.4) получаем:

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

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

Тогда классификация относит элемент X к ближайшему классу в смысле меры близости (10.5).

Классификатор применим и в случае, когда имеется дополнительная информация о допустимой принадлежности элементов к классам, т. е. имеется функция (см. определение 10.1). Тогда, например в алгоритме равномерного распределения объектов классификатор отнесет элемент X к ближайшему из классов , где

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

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

Если функционал не зависит от номера класса то классификатор (10.6) совпадает с функцией назначения (см. § 7.4).

10.1.5. Дескриптор D.

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

по формуле:

Таким образом, для вычисления значений (дескриптора D необходимо применить некоторую процедуру минимизации функционала на Наибольшее распространение получили алгоритмы АК, в которых в качестве используется статистический разброс класса относительно так как в этом случае удается получить явное решение задачи минимизации и заменить формулу (10.7) явной формулой расчета ядра класса по элементам этого класса.

Пример 10.6. В алгоритме -средних имеем

Поэтому

Пример 10.7. Опишем алгоритм типологического главного фактора [106]. Пусть и . Ядро класса Y описывается парой , а мерой близости от точки X до ядра считается квадрат расстояния от точки X до прямой, проходящей через точку Y с направляющим вектором v, т. е.

Допустим, что на шаге алгоритма совокупность О разбита на классов

Статистический разброс класса относительно вычисляется по формуле:

Минимизируя функционал (10.9) на пространстве получаем, что где — центр класса , — собственный вектор с наибольшим собственным значением ковариационной матрицы класса , т. е. главная компонента этого класса. На шаге этого алгоритма применяется классификатор (10.6), т. е. строится минимальное дистанционное разбиение, порождаемое набором ядер для меры близости (10.8). Алгоритм останавливается, если новое разбиение имеет тот же набор ядер, что предыдущее.

10.1.6. Основные понятия и определения, используемые при исследовании математической модели АК.

Опираясь на материал п. 10.1.1 — 10.1.5, естественно дать следующие определения.

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

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

Определение 10.4. Алгоритм АК называется сходящимся, если для его движения последовательность описаний сходится в метрике пространств L к некоторому предельному описанию

Алгоритм АК называется стабилизирующимся, если существует номер такой, что для всех

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

(10.10)

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

Таким образом, если функционал F рассматривать как меру потерь при задании выборки О в состоянии (классификации) s ее описанием I, то неравенства (10.10) и (10.11) служат объяснением, почему от состояния при фиксированном переходим к состоянию и от описания выборки О при фиксированном переходим к Для данной модели алгоритма АК, очевидно, может существовать много интерпретирующих функционалов, причем роль их при исследовании данного алгоритма может быть различной

Пример 10.8. Рассмотрим алгоритм Форель (см. п. 7 2.1), выделяющий в выборке несмещенную подвыборку где — параметр алгоритма, а К — центр класса О, который находится как результат стабилизации последователь ности описаний

При исследовании этого алгоритма используются два интерпретирующих функционала:

где если если Здесь — класс, выделенный на шаге алгоритма, — описание класса (его центр) на этом шаге и

Используя получаем, что стабилизируемость движения алгоритма Форель является следствием легко доказываемой стабилизируемости движения алгоритма -средних (см. [41, 42]). В терминах доказать стабилизируемость труднее [27], но зато, используя этот функционал, получаем, что предельное описание К является точкой локального максимума оценки плотности распределения случайного вектора по выборке О (см. § 7.6).