Метод 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ух треугольников внутри большего круга).

Ссылки

• kNN и Потенциальная энергия (апплет), Е. М. Миркес и университет Лейстера. Апплет позволяет сравнивать два метода классификации.
• Daniel T. Larose, Discovering Knowledge in Data: An Introduction to Data Mining (http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471666572.html)
• Метод K-ближайших соседей и распознавание рукописных цифр