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

Метод $k$$k$-ближайших соседей (англ. k-nearest neighbors algorithm, k-NN) — метрический алгоритм для автоматической классификации объектов или регрессии.

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

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

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

НормализацияПравить

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

Минимакс-нормализация осуществляется следующим образом:

$x^{\prime }=(x-<!--\; -\; -->min[X])/(max[X]-<!--\; -\; -->min[X])$$x'=(x-\min[X])/(\max[X]-\min[X])$ ,

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

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

$x^{\prime }=(x-<!--\; -\; -->M[X])/\mathrm{\sigma <!--\; \sigma \; -->}[X]$$x'=(x-M[X])/\sigma [X]$ 

где $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  — среднеквадратичное отклонение; в этом случае большинство значений попадёт в диапазон $(-<!--\; -\; -->3\mathrm{\sigma <!--\; \sigma \; -->};3\mathrm{\sigma <!--\; \sigma \; -->})$$(-3\sigma ;3\sigma )$ .

Выделение значимых атрибутовПравить

Некоторые значимые атрибуты могут быть важнее остальных, поэтому для каждого атрибута может быть задан в соответствие определённый вес (например вычисленный с помощью тестовой выборки и оптимизации ошибки отклонения). Таким образом, каждому атрибуту $k$$k$  будет задан в соответствие вес $z_k$$z_{k}$ , так что значение атрибута будет попадать в диапазон $[0;z_{k}max(k)]$$[0;z_{k}\max(k)]$  (для нормализованных значений по минимакс-методу). Например, если атрибуту присвоен вес 2,7, то его нормализованно-взвешенное значение будет лежать в диапазоне $[0;2,7]$$[0;2,7]$ 

Взвешенный способПравить

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

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

$Q_j=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{1}{d(x,a_i{)}^2}$$Q_{j}=\sum _{{i=1}}^{n}{\frac {1}{d(x,a_{i})^{2}}}$ ,

где $d(x,a_i)$$d(x,a_{i})$  — расстояние от нового значения $x$$x$  до объекта $a_i$$a_{i}$ .

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

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

$x_k=\frac{\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{k}_{i}d(x,a_i{)}^2}{\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}d(x,a_i{)}^2}$$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$$a_{i}$  — $i$$i$ -ый объект, попавший в область, $k_i$$k_i$  — значение атрибута $k$$k$  у заданного объекта $a_i$$a_{i}$ , $x$$x$  — новый объект, $x_k$$x_k$  — $k$$k$ -ый атрибут нового объекта.

СсылкиПравить

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