|
Правило выбора одного ближайшего соседа естественным образом обобщается на случай N ближайших соседей. Итоговое решение принимается с помощью какойнибудь схемы голосования. Имеется также возможность сформулировать правила для отказа от классификации в ситуациях, когда четкое предпочтение отдать невозможно. Доказано [49], что классификация по ближайшему соседу при наличии бесконечного числа обучающих векторов дает не более чем удвоенную ошибку по сравнению с оптимальным Байесовским классификатором: р < 9р1 «тог. NN0 — егтог.Вауе* • (2.16) Классификатор по ближайшему соседу часто используется для быстрой оценки сложности задачи, так как его достаточно просто реализовать, и он позволяет оценить точность, которую можно ожидать в данном случае. Практическое же использование этого классификатора обычно ограничивается не его точностью, а необходимыми для его работы вычислительными ресурсами компьютера [50]. Существует много обобщений и улучшений базовой схемы работы классификатора по ближайшему соседу. Их можно условно разделить на три группы: выбор функции расстояния, выбор решающего правила и выбор прототипов. Выбор функции расстояния важен в силу того обстоятельства, что выбор окрестности по евклидову расстоянию предполагает равноправные измерения. Поэтому, как минимум, необходимо нормализовать масштаб осей. В случае сильно коррелированных признаков, вместо евклидова расстояния часто используется расстояние Махаланобиса. Выбор решающего правша возможен тогда, когда в рассматриваемую окрестность включается более одного изображения. Обычно применяется простое голосование по мажоритарной схеме, возможно, с взвешиванием изображений по удаленности от точки. В зависимости от типа задачи, можно также сформулировать 44 |
Классификация по ближайшему соседу Классификация по ближайшему соседу [47] несомненно является одним из важнейших базовых методов построения классификатора и имеет многолетнюю историю успешного применения ко многим задачам классификации. Для начала рассмотрим базовый вариант классификатора по ближайшему соседу. Входной вектор признаков сравнивается с набором векгоров эталонных изображений, про которые известно, к какому классу они принадлежат. Выходной класс определяется по классу ближайшего (по евклидову расстоянию) эталонного вектора: * л«с (у) = с1а^} <=> т1п1у " Г/1 (2.15) В базовой схеме этап обучения фактически отсутствует все вектора из обучающей выборки становятся эталонными. Правило выбора ближайшего соседа в некотором смысле является попыткой непосредственно оценить а постер иорную вероятность Р(^ку), так как относительные вероятности появления эталонных векторов в окрестности данного определяются именно апостериорной вероятностью. Это правило также тесно связано с подходом, при котором вероятности оцениваются путем подсчета числа событий в определенных фиксированных интервалах, т. е. с помощью гистограмм. Принципиальный недостаток использования гистограмм заключается в том, что конфигурацию системы (число, положение и размер ячеек) необходимо определять заранее. Правило выбора ближайшего соседа элегантно избегает этих проблем, выбирая размер ячейки (окрестности) динамически, опираясь на входной вектор. Правило с выбором одного ближайшего соседа естественным образом обобщается на случай N ближайших соседей. Итоговое решение принимается с помощью какойнибудь схемы голосования. Также имеется возможность сформулировать правила для отказа от классификации в ситуациях, когда четкое предпочтение отдать невозможно. Доказано [48], что классификация по ближайшему соседу при наличии бесконечного числа обучающих векгоров дает не более чем удвоенную ошибку по сравнению с оптимальным Байесовским классификатором: Р < э. ргсггог,МНС~^гетг,Вау*х (2.16) Классификатор по ближайшему соседу1 часто используется для быстрой оценки сложности задачи, так как его достаточно просто реализовать и он позволяет оценить 25 точность, которую можно ожидать в данном случае. Практическое же использование этого классификатора обычно ограничивается не его точностью, а вычислительными ресурсами компьютера, необходимыми для его работы [49]. Существует много обобщений и улучшений базовой схемы работы классификатора. Их можно условно разделить на три группы: выбор функции расстояния, выбор решающего правила и выбор прототипов. Выбор функции расстояния важен в силу того обстоятельства, что выбор окрестности по евклидову расстоянию предполагает равноправные измерения. Поэтому, как минимум, необходимо нормализовать масштаб осей. В случае сильно коррелированных признаков вместо евклидова часто используется расстояние Махаланобиса. Выбор решающего правила возможен тогда, когда в рассматриваемую окрестность включается более одного изображения. Обычно применяется простое голосование по мажоритарной схеме, возможно, с взвешиванием изображений по удаленности отточки. В зависимости от типа задачи, можно также сформулировать правило отказа, например, на основе требования достаточного превышения количества «своих» изображений над «чужими». Наибольшее влияние на классификатор по ближайшему соседу оказывает правильный выбор набора прототипов. Для распознавания образов, как правило, используются признаковые пространства высокой размерности. С ростом размерности, с одной стороны, экспоненциально возрастает число прототипов, необходимое для покрытия пространства с заданной плотностью. С другой стороны, число возможных прототипов обычно лимитируется размером оперативной памяти компьютера и требованиями к скорости классификации. В результате подобного конфликта возникает задача компромиссного поиска на множестве имеющихся эталонных векторов такого их подмножества, которое в «рабочем» режиме дает наилучшие показатели в условиях заведомой недостаточности данных. Для решения этой задачи предлагались различные приемы, однако подавляющее большинство из них базируется на идее кластерного анализа, который рассмотрен в следующем разделе. 26 |