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

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

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

${\displaystyle x'=(x-\min[X])/(\max[X]-\min[X])}$,

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

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

${\displaystyle x'=(x-M[X])/\sigma [X]}$

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

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

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

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

${\displaystyle Q_{j}=\sum _{i=1}^{n}{\frac {1}{d(x,a_{i})^{2}}}}$,

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

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

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

${\displaystyle x_{k}={\frac {\sum _{i=1}^{n}{k_{i}d(x,a_{i})^{2}}}{\sum _{i=1}^{n}{d(x,a_{i})^{2}}}}}$,

где ${\displaystyle a_{i}}$ — ${\displaystyle i}$-ый объект, попавший в область, ${\displaystyle k_{i}}$ — значение атрибута ${\displaystyle k}$ у заданного объекта ${\displaystyle a_{i}}$, ${\displaystyle x}$ — новый объект, ${\displaystyle x_{k}}$ — ${\displaystyle 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)