Главная > Интеллектуальные системы > Введение в статистическую теорию распознавания образов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 6.2. Метод k ближайших соседей

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

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

двумя распределениями, нам достаточно решить лишь вопрос о том, какая из двух плотностей вероятности больше в данной точке.

6.2.1. Асимптотическая несмещенность и состоятельность

В методе Парзена каждый объект является центром, вокруг которого строится некоторое фиксированное ядро. Похожую оценку можно получить и иначе, а именно следующим образом. Используя выборку, состоящую из объектов, найдем расстояние от точки X до ближайшего к X объекта ближайшего соседа). Для измерения «близости» можно воспользоваться любой подходящей метрикой. Тогда в качестве оценки плотности вероятности в точке X можно принять

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

Величина А является случайной величиной, зависящей от выбранного множества объектов. Если параметр фигурирующий в (6.53), удовлетворяет условиям

и

то можно доказать, что является асимптотически несмещенной и состоятельной оценкой плотности вероятности [Ловтсгарден, 1965]. Доказательство здесь не приводится.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление