Cтраница 2
Удивительные результаты классификации методом ближайшего соседа получены в работе Ковера и Харта ( 1967), авторы которой установили также границы действия правила k ближайших соседей. Поскольку уровень ошибки правила ближайшего соседа ограничивает уровень Байеса, его можно использовать для измерения трудности, присущей задаче классификации образов. Ковер ( 1969) высказывает предположение, что даже в случае с небольшим числом выборок результаты будут свидетельствовать о том, насколько хорошо будет работать любая непараметрическая процедура, использующая те же самые выборки. Фрелик и Скотт ( 1971) проводят экспериментальное сравнение использования правил окна Парзена и ближайшего соседа для оценки уровня ошибки Байеса. [16]
Решающее правило, основанное на методе k ближайших соседей, является очень простым и не требует знания плотностей вероятности. Его недостаток заключается в необходимости хранить в памяти машины все объекты и сравнивать каждый из них с неизвестным объектом. В этом случае решающее правило называют правилом ближайшего соседа. [17]
Для распознавания образов интерес представляют несколько различных видов непараметрических методов. Если эти оценки удовлетворительны, то при проектировании оптимального классификатора ими можно заменить истинные значения плотности распределения. Этот метод близок такому методу непараметрических решающих процедур, как правило ближайшего соседа, в котором, обходя вероятностные оценки, сразу переходят к решающим функциям. И наконец, есть непараметрические процедуры, преобразующие пространство признаков так, чтобы в преобразованном пространстве можно было использовать параметрические методы. К этим методам дискриминантного анализа относится хорошо известный метод линейного дискриминанта Фишера, являющийся связующим звеном между параметрическими методами, описанными в гл. [18]
Когда вероятность P ( wjx) близка к единице, выбор с помощью правила ближайшего соседа почти всегда будет таким же, как и байесовский, это значит, что когда минимальная вероятность ошибки мала, то вероятность ошибки правила ближайшего соседа также мала. Когда Р ( сода х) близка к 1 / с, так что все классы одинаково правдоподобны, то выборы, сделанные с помощью этих двух правил, редко бывают одинаковыми, но вероятность ошибки в обоих случаях составляет приблизительно 1 - 1 / с. Не исключая необходимости в более тщательном анализе, эти замечания позволяют меньше удивляться хорошим результатам правила ближайшего соседа. [19]
У всех этих методов есть один общий недостаток - для них следует хранить полное множество выборок, поиск по которому производится каждый раз, когда нужно классифицировать новый вектор признаков. Предлагался ряд методов уменьшения числа выборок, но только для немногих из них известны какие-либо статистические свойства. Барус ( 1966) предложил интересную аппроксимацию для процедуры Фикса и Ходжеса, а Харт ( 1968) - сжатое правило ближайшего соседа. [20]
Серьезные вопросы имеются относительно эффективности запоминания информации в персептроне ( или любых других нейронных сетях) по сравнению с обычной компьютерной памятью и методами поиска информации в ней. Компьютер должен найти требуемый образ и дать его классификацию. Различные хорошо известные методы могли бы быть использованы для ускорения поиска. Если точное соответствие не найдено, то для ответа может быть использовано правило ближайшего соседа. [21]
Таким образом, границы, заданные ( 28), являются максимально близкими в том смысле, что для любой Р существуют условные и априорные вероятности, дли которых эти границы Достигаются. На рис. 4.4 графически представлены эти границы. Байесовский уровень Р может находиться в любом месте между О и ( с - 1) 1 с. Границы сходятся В этих двух крайних точках. Когда байесовский уровень мал, верхняя граница превышает его почти в два раза. В общем значение ошибки правила ближайшего соседа должно находиться в заштрихованной области. [22]