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