4.6.1. ОБЩИЕ ЗАМЕЧАНИЯ

Пусть ^”={хі, . . ., х„} будет множеством п помеченных выборок, и пусть X ^ ^ будет выборкой, ближайшей к х. Тогда правило ближайшего соседа для классификации х заключается в том, что х присваивается метка, ассоциированная с х„. Правило ближайшего соседа является почти оптимальной процедурой; его применение обычно приводит к уровню ошибки, превышающему минимально возможный байесовский. Как мы увидим, однако, при неограниченном количестве выборок уровень ошибки никода не будет хуже байесовского более чем в два раза.

прежде чем вдаваться в детали, давайте попытаемся эвристически разобраться в том, почему правило ближайшего соседа дает такие хорошие результаты. Для начала отметим, что метка Ѳ'„, ассоциированная с ближайшим соседом, является случайной величиной, а вероятность того, что Ѳ'=(Оь есть просто апостериорная вероятность P(coj|x^). Когда количество выборок очень велико, следует допустить, что х'„ расположено достаточно близко к х, чтобы /’((Oj|x')«Р(мі|х). В этом случае можем рассматривать правило ближайшего соседа как рандомизированное решающее правило, которое классифицирует х путем выбора класса со,- с вероятностью Р(соі|х). Поскольку это точная вероятность того, что природа находится в состоянии coj, значит, правило ближайшего соседа эффективно согласует вероятности с реальностью.

Если мы определяем со„(х) как

то байесовское решающее правило всегда выбирает со^. Когда вероятность P(w„|x) близка к единице, выбор с помощью правила ближайшего соседа почти всегда будет таким же, как и байесовский, это значит, что когда минимальная вероятность ошибки мала, то вероятность ошибки правила ближайшего соседа также мала. Когда Р(Мда|х) близка к 1/с, так что все классы одинаково правдоподобны, то выборы, сделанные с помощью этих двух правил, редко бывают одинаковыми, но вероятность ошибки в обоих случаях составляет приблизительно 1—1/с. Не исключая необходимости в более тщательном анализе, эти замечания позволяют меньше удивляться хорошим результатам правила ближайшего соседа.

Наш анализ поведения правила ближайшего соседа будет направлен на получение условной средней вероятности ошибки Р(е|х) при большом количестве выборок, где усреднение производится по выборкам. Безусловная средняя вероятность ошибки будет найдена путем усреднения Р(е\\) по всем х:

Заметим, что решающее правило Байеса минимизирует Р{е) путем минимизации Р(е|х) для каждого х.

Если Р* (ejx) является минимально возможным значением Р{е\\), а Р* — минимально возможным значением Р(е), то

и