§ 11. О выборе оптимальной совокупности признаков

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

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

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

Теперь естественно принять в качестве критерия выбора величину доверительного интервала

,               (6.20')

где

.

Здесь как величина , так и  зависят от подпространства  поскольку и расстояние между выпуклыми оболочками классов и их диаметры изменяются при проектировании в подпространство. Процедура второго уровня должна выбрать то решающее правило из числа предложенных первым уровнем, для которого оценка (6.20') минимальна.

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

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

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

.

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

и т. д.

Иначе говоря, к -му классу относятся такие гиперплоскости, для которых минимум двух величин равен , т. е.

.

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

.               (6.19')

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

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

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

,                     (6.20")

где

.

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

.

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

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

Рассмотрим следующий способ упорядочения: к -му классу отнесем те правила, для которых выполняется равенство

,

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

При таком способе упорядочения оценка качества выбранного решающего правила также определяется критериями (6.19), (6.20).

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

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

Часто множество отобранных признаков называют информативным набором признаков. «Информативность» этого набора может быть оценена числом, равным минимальной величине критерия (6.19'), которая достигается в пространстве этих признаков. Можно оценивать «вклад» каждого признака в информативность набора признаков как разность между величиной оценки набора признаков, из которого исключен данный признак, и информативностью набора признаков.

Однако, вероятно, понятие «информативность набора признаков» или «информативность данного признака» не несет достаточно глубокого содержания. И вот почему:

1) понятие «информативность пространства признаков» определяется не само по себе, а в связи с конкретным алгоритмом опознания;

2) информативность набора признаков зависит от конкретной обучающей последовательности.

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