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

Метод k-ближайших соседей (англ. k-nearest neighbors algorithm, k-NN) — метрический алгоритм для автоматической классификации объектов или регрессии.
- В случае использования метода для классификации объект присваивается тому классу, который является наиболее распространённым среди соседей данного элемента, классы которых уже известны.
- В случае использования метода для регрессии, объекту присваивается среднее значение по ближайшим к нему объектам, значения которых уже известны.
Содержание
Определение дистанции[править | править код]
Алгоритм может быть применим к выборкам с большим количеством атрибутов (многомерным). Для этого перед применением нужно определить функцию дистанции. Классический вариант определения дистанции — дистанция в евклидовом пространстве.
Нормализация[править | править код]
Однако разные атрибуты могут иметь разный диапазон представленных значений в выборке (например атрибут А представлен в диапазоне от 0.1 до 0.5, а атрибут Б представлен в диапазоне от 1000 до 5000), то значения дистанции могут сильно зависеть от атрибутов с бо́льшими диапазонами. Поэтому данные обычно подлежат нормализации. При кластерном анализе есть два основных способа нормализации данных:
- Мини-макс нормализация.
В этом случае все значения будут лежать в диапазоне от 0 до 1. Дискретные бинарные значения определяются как 0 и 1.
- Z-нормализация.
где σ — стандартное отклонение. В этом случае большинство значений попадет в диапазон (-3;3)
Выделение значимых атрибутов[править | править код]
Некоторые значимые атрибуты могут быть важнее остальных, поэтому для каждого атрибута может быть задан в соответствие определенный вес (например вычисленный с помощью тестовой выборки и оптимизации ошибки отклонения). Таким образом, каждому атрибуту будет задан в соответствие вес , так что значение атрибута будет попадать в диапазон (для нормализованных значений по методу мини-макс). Например, если атрибуту присвоен вес 2.7, то его нормализованно-взвешенное значение будет лежать в диапазоне
Взвешенный способ[править | править код]
Определение класса[править | править код]
При таком способе во внимание принимается не только количество попавших в область определенных классов, но и их удаленность от нового значения.
Для каждого класса j определяется оценка близости:
, где d(x, a) — дистанция от нового значения x до объекта а.
У какого класса выше значение близости, тот класс и присваивается новому объекту.
Определение непрерывной величины[править | править код]
С помощью этого метода можно вычислять значение одного из атрибутов классифицируемого объекта на основании дистанций от попавших в область объектов и соответствующих значений этого же атрибута у объектов.
,
где
— i-ый объект, попавший в область
— это значение атрибута у заданного объекта (примечание для корректоров: было бы неплохо заменить на значение вложенного индекса (a_k_i))
— новый объект
— k-ый атрибут нового объекта
Ссылки[править | править код]
- kNN и Потенциальная энергия (апплет), Е. М. Миркес и университет Лейстера. Апплет позволяет сравнивать два метода классификации.
- Daniel T. Larose, Discovering Knowledge in Data: An Introduction to Data Mining (http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471666572.html)