Метод k-ближайших соседей

В распознавание образов, метод k-ближайших соседей представляет собой непараметрический метод, который используется для классификации и регрессии. Выход зависит от того, для чего именно используется метод k-ближайших соседей:

• · Если для классификации, то выходными данными являтся информация о принадлежности к одному из классов. Объект классифицируется в зависимости от своих соседей: объекту присваивается класс, наиболее распространенный среди его k ближайших соседей (k — это положительное целое число, как правило, небольшое). Если k = 1, то объект просто относим к классу, к которому относится ближайший сосед.
• · Если для регрессии, то на выходе результатом этого метода будет значение объекта. Это значение вычисляется как среднее из значений его k ближайших соседей.

Метод k-ближайших соседей является одним из самых простых из всех алгоритмов машинного обучения.

Как для классификации, так и для регрессии, может быть полезно ввести понятие веса соседей. Другими словами, те соседи, которые ближе к объекту, вносят в среднем больший вклад, чем более отдаленные. Например, общая весовая схема заключается в предоставлении каждому соседу вес 1/d, где d — расстояние до соседа. 10].

Алгоритм Обучающая выборка — вектора в многомерном пространстве признаков, каждый с меткой класса. Этап обучения алгоритма состоит только из хранения пространственных векторов и вектора меток обучающей выборки.

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

Для непрерывных переменных наиболее широко используется Евклидово расстояние. Для дискретных переменных, например, для классификации текстов, может быть использована другая метрика, например, метрика Хэмминга Расстояние Хэмминга — число позиций, в которых соответствующие символы двух слов одинаковой.

длины различны. Рассчитывается как: .

Выбор параметра k.

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

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

В классификации с двоичной системой счисления (где два класса), полезно k выбрать нечетным числом, чтобы избежать привязанности голосов.