Правило - ближайший сосед
Cтраница 1
Правило ближайшего соседа является почти оптимальной процедурой; его применение обычно приводит к уровню ошибки, превышающему минимально возможный байесовский. Как мы увидим, однако, при неограниченном количестве выборок уровень ошибки никода не будет хуже байесовского более чем в два раза. [1]
 |
Границы ошибки правила ближайшего соседа. [2] |
Явным расширением правила ближайшего соседа является правило k ближайших соседей. Как видно из названия, это правило классифицирует х, присваивая ему меткуs наиболее часто представляемую среди k ближайших выборок; другими словами, решение принимается после изучения меток k ближайших соседей. Мы не будем подробно анализировать это правило. [3]
Рассмотрение эффективности правила ближайшего соседа легко обобщается на случай правила k ближайших соседей. [4]
Учитывая, что правило ближайшего соседа не требует какой-либо информации о распределения, его можно считать весьма эффективным. [5]
Наш анализ поведения правила ближайшего соседа будет направлен на получение условной средней вероятности ошибки Р ( е х) при большом количестве выборок, где усреднение производится по выборкам. [6]
Особый интерес возникает к правилу ближайшего соседа ( БС), для которого удалось построить вероятностно-статистическую модель. Для его использования необходимо и достаточно наличие обучающих выборок для каждого класса. [7]
 |
Границы ошибки правила ближайшего соседа. [8] |
Естественно задаться вопросом, насколько хорошо правило ближайшего соседа в случае конечного числа выборок и как быстро результат сходится к асимптотическому значению. К сожалению, ответы для общего случая неблагоприятны. Так же, как это происходит с другими непараметрическими методами, трудно получить какие-либо еще результаты, кроме асимптотических, не делая дальнейших допущений о вероятностных свойствах. [9]
Каждый следующий объект классифицируется с помощью правила ближайшего соседа; при этом используются только те объекты, которые находятся в массиве ПАМЯТЬ. Если классификация произведена правильно, объект выбрасывают в ОТСЕВ. Если объект классифицирован неправильно, его заносят в ПАМЯТЬ. [10]
Каждый следующий объект классифицируется с помощью правила ближайшего соседа; при этом используются только те объекты, которые находятся в массиве ПАМЯТЬ. Если классификация произведена правильно, объект выбрасывают в ОТСЕВ. Если объект классифицирован неправильно, его заносят в ПАМЯТЬ. [11]
Когда вероятность P ( wjx) близка к единице, выбор с помощью правила ближайшего соседа почти всегда будет таким же, как и байесовский, это значит, что когда минимальная вероятность ошибки мала, то вероятность ошибки правила ближайшего соседа также мала. Когда Р ( сода х) близка к 1 / с, так что все классы одинаково правдоподобны, то выборы, сделанные с помощью этих двух правил, редко бывают одинаковыми, но вероятность ошибки в обоих случаях составляет приблизительно 1 - 1 / с. Не исключая необходимости в более тщательном анализе, эти замечания позволяют меньше удивляться хорошим результатам правила ближайшего соседа. [12]
Прежде чем вдаваться в детали, давайте попытаемся эвристически разобраться в том, почему правило ближайшего соседа дает такие хорошие результаты. Поскольку это точная вероятность того, что природа находится в состоянии со г, значит, правило ближайшего соседа эффективно согласует вероятности с реальностью. [13]
Когда вероятность P ( wjx) близка к единице, выбор с помощью правила ближайшего соседа почти всегда будет таким же, как и байесовский, это значит, что когда минимальная вероятность ошибки мала, то вероятность ошибки правила ближайшего соседа также мала. Когда Р ( сода х) близка к 1 / с, так что все классы одинаково правдоподобны, то выборы, сделанные с помощью этих двух правил, редко бывают одинаковыми, но вероятность ошибки в обоих случаях составляет приблизительно 1 - 1 / с. Не исключая необходимости в более тщательном анализе, эти замечания позволяют меньше удивляться хорошим результатам правила ближайшего соседа. [14]
Прежде чем вдаваться в детали, давайте попытаемся эвристически разобраться в том, почему правило ближайшего соседа дает такие хорошие результаты. Поскольку это точная вероятность того, что природа находится в состоянии со г, значит, правило ближайшего соседа эффективно согласует вероятности с реальностью. [15]
Страницы: 1 2