3.2.3. Обобщение принципов классификации по минимуму расстояния

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

где — любое расстояние, определение которого допустимо на пространстве образов.

Эту процедуру классификации можно назвать 1-БС-правилом, так как при ее применении учитывается принадлежность некоторому классу только одного ближайшего соседа образа . Нет, однако, причин, которые могли бы воспрепятствовать введению 1-БС-правила, предусматривающего определение ближайших к образов и зачисление его в тот класс, к которому относится наибольшее число образов, входящих в эту группу. Сопоставление соотношений (3.2.10) и (3.2.6) показывает, что 1-БС-правило есть не что иное, как рассмотренный в предыдущем разделе случай множественности эталонов, если в качестве выбирается евклидово расстояние.

Интересный результат, относящийся к сравнению 1-БС- и q-БС-правил, можно получить, обратившись к рис. 3.5. Допустим, что вероятность появления образов обоих представленных классов одинакова и, как показано на рисунке, образы классов равномерно распределены в пределах соответствующих

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

где — число способов, которыми выборку объема можно разделить на два класса, содержащих а и а элементов соответственно; определяет общее число способов разбиения элементов на два класса. Очевидно, что вероятность принадлежности а из элементов выборки классу равна вероятности .

Рис. 3.5. Два класса, покрывающие идентичные области, в которых образы распределены равномерно.

Допустим, что классифицируемый образ принадлежит классу . При этом применение 1-БС-правила приведет к ошибке только в том случае, если ближайший сосед образа входит в класс , следовательно, расположен в круге . С другой стороны, если образ принадлежит классу а его ближайший сосед находится в круге то в этом круге должны быть расположены все образы, что абсолютно очевидно из рис. 3.5. Это означает, что вероятность ошибки при применении 1-БС-правила равна в этом случае вероятности принадлежности всех образов классу которую можно определить, положив в выражении (3.2.11), т. е.

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

Допустим, что образ принадлежит классу и он, следовательно, расположен в круге . В таком случае применение

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

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

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

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

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

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