6.2.2. Решающее правило, основанное на методе k ближайших соседей.

Оценка (6.53) может использоваться для классификации следующим образом. Когда требуется классифицировать неизвестный объект X, среди имеющихся объектов, из которых объектов принадлежат классу объектов — классу находят к ближайших в точке X объектов.

Пусть — соответственно числа объектов из класса среди этих к ближайших соседей. Тогда оценка (6.53) принимает вид

Так как объектов извлечены из одного и того же гипершара, то объем А — один и тот же как для класса со 1, так и для класса Следовательно, байесовский критерий, минимизирующий ошибку, будет иметь вид

или, подставляя (6.57) в (6.58), получим

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

Решающее правило, основанное на методе к ближайших соседей, является очень простым и не требует знания плотностей вероятности. Его недостаток заключается в необходимости хранить в памяти машины все объекты и сравнивать каждый из них с неизвестным объектом. Посмотрим, какова зффектйвность этого алгоритма [Ковер, 1967]. Рассмотрим вначале простейший случай: . В этом случае решающее правило называют правилом ближайшего соседа.

Вероятность ошибки при использовании правила ближайшего соседа.

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

Если предположить, что велико, так что объект X и его ближайший сосед X очень близко расположены друг к другу, то можно воспользоваться следующим приближенным равенством:

Тогда условная вероятность ошибки (6.60) примет вид

является функцией только объекта X. Легко показать, что (6.60) сходится к (6.62) с вероятностью 1, когда

С другой стороны, как следует из (3.1), условная вероятность ошибки байесовского решающего правила (при данном X) определяется как

Таким образом, связаны соотношением

Так как вероятность ошибки есть математическое ожидание условной вероятности ошибки то

где — вероятность ошибки байесовского решающего правила, определяемая как математическое ожидание условной вероятности ошибки

Следовательно, вероятность ошибки при использовании правила ближайшего соседа в качестве решающего правила меньше, чем удвоенная вероятность ошибки байесовского решающего правила в предположении, что является достаточно большим для выполнения условия (6.61).

В табл. 3.4 было показано, что граница Чернова в примере с нормальными распределениями дает ошибку 4,6% при фактической ошибке 1,9% (т. е. в 2,4 раза больше). Учитывая, что правило ближайшего соседа не требует какой-либо информации о распределении, его можно считать весьма эффективным.

Нижнюю границу вероятности ошибки при использовании правила ближайшего соседа можно получить следующим образом:

Последнее неравенство справедливо, так как из (6.63) следует Таким образом, вероятность ошибки ограничена снизу вероятностью ошибки байесовского решающего правила, а равенство между ними имеет место, когда почти всюду, т. е. или почти всюду.

Вероятность ошибки при использовании правила к ближайших соседей.

Рассмотрение эффективности правила ближайшего соседа легко обобщается на случай правила к ближайших соседей. Условная вероятность ошибки при фиксированном объекте X определяется следующим образом:

где первый второй члены представляют собой соответственно условную вероятность ошибки для Для того чтобы выражение (6.68) имело смысл, к должно быть нечетным числом. Равенство (6.68) можно переписать следующим образом:

Так как условная вероятность ошибки байесовского решающего правила определяется формулой (6.63), то можно представить как функцию от

Для получения безусловной вероятности ошибки нужно усреднить условную вероятность ошибки (6.70) по всем X. Для

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

Для получения границы вероятности ошибки ей как функции от вероятности ошибки байесовского решающего правила введем функцию -наименьшую вогнутую функцию, такую, что для всех X

Воспользовавшись неравенством Иенсена, получим

Так как условная вероятность ошибки определяемая формулой (6.69), монотонно уменьшается с ростом наименьшая вогнутая функция также монотонно уменьшается с ростом к. Поэтому

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

мы получаем границу вероятности ошибки как функцию от которую можно экспериментально оценить.

Пример 6.2. Для правила ближайшего соседа имеем

Условная вероятность ошибки является вогнутой функцией, и, следовательно, ее можно использовать в качестве в неравенстве (6.71). Применяя неравенство (6.72), получим

Обращая это неравенство, имеем

Таким образом, неравенство (6.77) дает границы вероятности ошибки байесовского решающего правила в виде функций от асимптотической вероятности ошибки метода ближайшего соседа,