Метод k-ближайших соседей
Метод [math]\displaystyle{ k }[/math]-ближайших соседей (англ. k-nearest neighbors algorithm, k-NN) — метрический алгоритм для автоматической классификации объектов или регрессии.
В случае использования метода для классификации объект присваивается тому классу, который является наиболее распространённым среди [math]\displaystyle{ k }[/math] соседей данного элемента, классы которых уже известны. В случае использования метода для регрессии, объекту присваивается среднее значение по [math]\displaystyle{ k }[/math] ближайшим к нему объектам, значения которых уже известны.
Алгоритм может быть применим к выборкам с большим количеством атрибутов (многомерным). Для этого перед применением нужно определить функцию расстояния; классический вариант такой функции — евклидова метрика[1][2].
Нормализация
Разные атрибуты могут иметь разный диапазон представленных значений в выборке (например атрибут А представлен в диапазоне от 0.1 до 0.5, а атрибут Б представлен в диапазоне от 1000 до 5000), то значения дистанции могут сильно зависеть от атрибутов с бо́льшими диапазонами. Поэтому данные обычно подлежат нормализации. При кластерном анализе есть два основных способа нормализации данных: минимакс-нормализация и Z-нормализация.
Минимакс-нормализация осуществляется следующим образом:
- [math]\displaystyle{ x' = (x - \min[X]) / (\max[X] - \min[X]) }[/math],
в этом случае все значения будут лежать в диапазоне от 0 до 1; дискретные бинарные значения определяются как 0 и 1.
Z-нормализация:
- [math]\displaystyle{ x' = (x - M[X]) / \sigma[X] }[/math]
где [math]\displaystyle{ \sigma }[/math] — среднеквадратичное отклонение; в этом случае большинство значений попадёт в диапазон [math]\displaystyle{ (-3\sigma ; 3\sigma) }[/math].
Выделение значимых атрибутов
Некоторые значимые атрибуты могут быть важнее остальных, поэтому для каждого атрибута может быть задан в соответствие определённый вес (например вычисленный с помощью тестовой выборки и оптимизации ошибки отклонения). Таким образом, каждому атрибуту [math]\displaystyle{ k }[/math] будет задан в соответствие вес [math]\displaystyle{ z_k }[/math], так что значение атрибута будет попадать в диапазон [math]\displaystyle{ [0;z_k\max(k)] }[/math] (для нормализованных значений по минимакс-методу). Например, если атрибуту присвоен вес 2,7, то его нормализованно-взвешенное значение будет лежать в диапазоне [math]\displaystyle{ [0;2,7] }[/math]
Взвешенный способ
При взвешенном способе во внимание принимается не только количество попавших в область определённых классов, но и их удалённость от нового значения.
Для каждого класса [math]\displaystyle{ j }[/math] определяется оценка близости:
- [math]\displaystyle{ Q_j = \sum_{i=1}^n\frac{1}{d(x,a_i)^2} }[/math],
где [math]\displaystyle{ d(x,a_i) }[/math] — расстояние от нового значения [math]\displaystyle{ x }[/math] до объекта [math]\displaystyle{ a_i }[/math].
У какого класса выше значение близости, тот класс и присваивается новому объекту.
С помощью метода можно вычислять значение одного из атрибутов классифицируемого объекта на основании дистанций от попавших в область объектов и соответствующих значений этого же атрибута у объектов:
- [math]\displaystyle{ x_k = \frac{\sum_{i=1}^n{k_i d(x,a_i)^2}}{\sum_{i=1}^n{d(x,a_i)^2}} }[/math],
где [math]\displaystyle{ a_i }[/math] — [math]\displaystyle{ i }[/math]-ый объект, попавший в область, [math]\displaystyle{ k_i }[/math] — значение атрибута [math]\displaystyle{ k }[/math] у заданного объекта [math]\displaystyle{ a_i }[/math], [math]\displaystyle{ x }[/math] — новый объект, [math]\displaystyle{ x_k }[/math] — [math]\displaystyle{ k }[/math]-ый атрибут нового объекта.
Ссылки
- ↑ S. Madeh Piryonesi, Tamer E. El-Diraby. Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems (англ.) // Journal of Transportation Engineering, Part B: Pavements. — 2020-06. — Vol. 146, iss. 2. — P. 04020022. — ISSN 2573-5438 2573-5438, 2573-5438. — doi:10.1061/JPEODX.0000175. Архивировано 12 апреля 2020 года.
- ↑ Hastie, Trevor. The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. — New York: Springer, 2001. — xvi, 533 pages с. — ISBN 0-387-95284-5, 978-0-387-95284-0. Архивная копия от 9 августа 2020 на Wayback Machine
- 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)
