17
правок
Изменения
Нет описания правки
'''Метод ближайших соседей''' {{---}} простейший метрический классификатор, основанный на оценивании сходства объектов. Классифицируемый объект относится к тому классу, которому принадлежат ближайшие к нему объекты обучающей выборки.
'''Метод <tex>k </tex> ближайших соседей''' (англ. knn - <tex>k </tex> nearest neighbours) {{---}} Для повышения надёжности классификации объект относится к тому классу, которому принадлежит большинство из его соседей {{---}} <tex>k </tex> ближайших к нему объектов обучающей выборки <tex>x_i</tex>. В задачах с двумя классами число соседей берут нечётным, чтобы не возникало ситуаций неоднозначности, когда одинаковое число соседей принадлежат разным классам.
'''Метод взвешенных ближайших соседей''' {{---}} в задачах с числом классов 3 и более нечётность уже не помогает, и ситуации неоднозначности всё равно могут возникать. Тогда <tex>i</tex>-му соседу приписывается вес <tex>w_i</tex>, как правило, убывающий с ростом ранга соседа <tex>i</tex>. Объект относится к тому классу, который набирает больший суммарный вес среди <tex>k </tex> ближайших соседей.
== Описание алгоритма ==
<tex>a(u) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^m \bigl[ x_{i; u}=y \bigr] w(i,u)</tex>,
где <tex>w(i,u)</tex> {{---}} заданная весовая функция, которая оценивает степень важности <tex>i</tex>-го соседа для классификации объекта <tex>u</tex>. Естественно полагать, что эта функция неотрицательна и не возрастает по <tex>i</tex>(поскольку чем дальше объект, тем меньший вклад он должен вносить в пользу своего класса).
По-разному задавая весовую функцию, можно получать различные варианты метода ближайших соседей.
<tex>w(i,u) = [i\leq k]</tex> {{---}} метод <tex>k</tex> ближайших соседей;
<tex>w(i,u) = [i\leq k] q^i</tex> {{---}} метод <tex>k</tex> экспоненциально взвешенных ближайших соседей, где предполагается константа <tex>q < 1</tex>;
== Использование ядер сглаживания ==
При использовании ленейной линейной функции в качестве <tex>w(i, u)</tex> возможно совпадение суммарного веса для нескольких классов. Это приводит к неоднозначности ответа при классификации. Чтобы такого не происходило используют функцию [[Ядра]]<sup>[на 15.01.18 не создан]</sup>.
Будем обозначать функцию ядра <tex>K(r)</tex>
<tex>a_h</tex> не будет учитывать соседей на расстояние больше чем h, а всех остальных учтет в соответствии с функций ядра <tex>K</tex>.
<tex>a_k</tex> является аналогом метода <tex>k </tex> ближайших соседей (т.к. для всех <tex>k+i</tex>-ых соседей функция <tex>K</tex> вернет 0), но при этом чем ближе <tex>k-i</tex>-ый сосед, тем больший вклад в сторону своего класса он даст.
Часто используют окно переменной ширины т.е. классификатор <tex>a_k</tex>, по следующим причинам:
