3.1.2. Правила классификации

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

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

Формальные выражения для параллельной и последовательной процедур достаточно прозрачны.

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

где

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

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

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

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

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

Название класса связывается с концом каждой ветви, например узел А на рис. 3.2.

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

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

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