§ 4. Метод последовательного добавления признаков (алгоритм Add) [2]

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

Трудоемкость этого алгоритма приблизительно такая же, как и алгоритма Del, однако результаты, получаемые алгоритмом Add, обычно лучше, чем у Del. Объясняется этот факт влиянием малой представительности обучающей выборки: при одном и том же объеме выборки чем выше размерность признакового пространства, тем меньше обоснованность получаемых статистических выводов (в нашем случае — оценки информативности). Средняя размерность выборочного пространства в алгоритме Del равна , а в алгоритме Add — , так что риск ошибочного признания информативного признака неинформативным в Del выше, чем в Add.

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

Для ослабления влияния ошибок на первых шагах алгоритма применяется релаксационный метод. В алгоритме Add набирается некоторое количество  информативных признаков и затем - часть из них  исключается методом Del. После этого алгоритмом Add размерность информативных признаков наращивается на величину  и становится равной . В этот момент снова включается алгоритм Del, который исключает из системы  «наименее ценных» признаков. Такое чередование алгоритмов Add и Del, которое получило название алгоритма AddDel, продолжается до достижения заданного количества признаков .

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