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

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

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

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

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

Нормализация[править | править код]

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

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

,

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

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

где  — среднеквадратичное отклонение; в этом случае большинство значений попадёт в диапазон .

Выделение значимых атрибутов[править | править код]

Некоторые значимые атрибуты могут быть важнее остальных, поэтому для каждого атрибута может быть задан в соответствие определённый вес (например вычисленный с помощью тестовой выборки и оптимизации ошибки отклонения). Таким образом, каждому атрибуту будет задан в соответствие вес , так что значение атрибута будет попадать в диапазон (для нормализованных значений по минимакс-методу). Например, если атрибуту присвоен вес 2,7, то его нормализованно-взвешенное значение будет лежать в диапазоне

Взвешенный способ[править | править код]

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

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

,

где  — расстояние от нового значения до объекта .

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

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

,

где  — -ый объект, попавший в область,  — значение атрибута у заданного объекта ,  — новый объект,  — -ый атрибут нового объекта.

Ссылки[править | править код]

  1. 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.
  2. 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.