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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод k ближайших соседей (англ. k-nearest neighbor algorithm, kNN) - метод автоматической классификации объектов. Основным принципом метода ближайших соседей является то, что объект присваивается тому классу, который является наиболее распространённым среди соседей данного элемента.

Соседи берутся исходя из множества объектов, классы которых уже известны, и, исходя из ключевого для данного метода значения k высчитывается, какой класс наиболее многочислен среди них. Каждый объект имеет конечное количество атрибутов (размерностей)

Предполагается, что существует определенный набор объектов с уже имеющейся классификацией.

Определение дистанции[править | править вики-текст]

Алгоритм может быть применим к выборкам с большим количеством атрибутов (многомерным). Для этого перед применением нужно определить функцию дистанции. Классический вариант определения дистанции - дистанция в евклидовом пространстве.

Нормализация[править | править вики-текст]

Однако разные атрибуты могут иметь разный диапазон представленных значений в выборке (например атрибут А представлен в диапазоне от 0.1 до 0.5, а атрибут Б представлен в диапазоне от 1000 до 5000), то значения дистанции могут сильно зависеть от атрибутов с бо́льшими диапазонами. Поэтому данные обычно подлежат нормализации. При кластерном анализе есть два основных способа нормализации данных:

  • Мини-макс нормализация.

x' = (x - MIN[X]) / (MAX[X] - MIN[X])

В этом случае все значения будут лежать в диапазоне от 0 до 1. Дискретные бинарные значения определяются как 0 и 1.

  • Z-нормализация.

x' = (x - M[X]) / \sigma[X]

где σ — стандартное отклонение. В этом случае большинство значений попадет в диапазон (-3;3)

Выделение значимых атрибутов[править | править вики-текст]

Некоторые значимые атрибуты могут быть важнее остальных, поэтому для каждого атрибута может быть задан в соответствие определенный вес (например вычисленный с помощью тестовой выборки и оптимизации ошибки отклонения). Таким образом, каждому атрибуту k будет задан в соответствие вес z_k, так что значение атрибута будет попадать в диапазон [0;z_kmax(k)] (для нормализованных значений по методу мини-макс). Например, если атрибуту присвоен вес 2.7, то его нормализованно-взвешенное значение будет лежать в диапазоне [0;2.7]

Взвешенный способ[править | править вики-текст]

Определение класса[править | править вики-текст]

При таком способе во внимание принимается не только количество попавших в область определенных классов, но и их удаленность от нового значения.

Для каждого класса j определяется оценка близости:

Q_j = \sum_{i=1}^n\frac{1}{d(x,a_i)^2}, где d(x, a) — дистанция от нового значения x до объекта а.

У какого класса выше значение близости, тот класс и присваивается новому объекту.

Определение непрерывной величины[править | править вики-текст]

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

x_k = \frac{\sum_{i=1}^n{k_i d(x,a_i)^2}}{\sum_{i=1}^n{d(x,a_i)^2}},

где

a_i — i-ый объект, попавший в область

k_i — это значение атрибута k у заданного объекта a_i (примечание для корректоров: было бы неплохо заменить k_i на значение вложенного индекса (a_k_i))

x — новый объект

x_k — k-ый атрибут нового объекта

Пример классификации k ближайших соседей. Тестовый образец (зеленый круг) должен быть классифицирован как синий квадрат (класс 1) или как красный треугольник (класс 2). Если k = 3, то она классифицируется как 2ой класс, потому что внутри меньшего круга 2 треугольника и только 1 квадрат. Если k = 5, то он будет классифицирован как 1ый класс (3 квадрата против 2ух треугольников внутри большего круга).

Ссылки[править | править вики-текст]