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

Описание

• Википедия
• GeekForGeeks
• Habr (код на Python)
• YouTube
• GitHub

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

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

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

Использование теоремы Пифагора для вычисления евклидова расстояния на плоскости

Принцип работы

• проверяется валидность данных и меток
• вычисляется евклидово расстояние между тестовым (целевым) и всеми обучающими образцами
• расстояния вместе с классами сортируются в возрастающем порядке
• выбирается k ближайших образцов (соседей), где число k задается заранее (как правило, выбирается нечетное число - 3, 5 и т.д.)
• итоговым прогнозом среди выбранных k ближайших соседей будет мода в случае классификации и среднее арифметическое в случае регрессии
• возвращается наиболее похожий класс (для классификации) или среднее значение (для регрессии)

Визуализация k-NN для лучшего понимания:

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

Еще одна визуализация:

Здесь k = 7, поэтому тестовый образец классифицируется как зеленый треугольник

И еще одна:

Звездочкой обозначен целевой образец

k=3

k=10

k=20

Как видим, во всех трех случаях целевой образец классифицируется как синий круг.

Реализация

// algorithms/machine-learning/k-nn.js
// Функция для вычисления евклидова расстояния
import euclideanDistance from '../math/euclidean-distance'

/** Функция принимает:
 * data   - данные
 * labels - метки
 * target - тестовый/целевой образец
 * k      - количество ближайших соседей
 */
export default function kNN(data, labels, target, k = 3) {
  if (!data || !labels || !target) {
    throw new Error('Отсутствует обязательный параметр')
  }

  // Вычисляем расстояние от `target` до каждой точки `data`.
  // Сохраняем расстояние и метку точки в списке
  const distances = []

  for (let i = 0; i < data.length; i++) {
    distances.push({
      distance: euclideanDistance([data[i]], [target]),
      label: labels[i],
    })
  }

  // Сортируем расстояния по возрастанию (от ближайшего к дальнему).
  // Берем `k` значений
  const kn = distances
    .sort((a, b) => {
      if (a.distance === b.distance) {
        return 0
      }
      return a.distance < b.distance ? -1 : 1
    })
    .slice(0, k)

  // Считаем количество экземпляров каждого класса
  const _labels = {}
  let topClass = 0
  let topClassCount = 0

  for (let i = 0; i < kn.length; i++) {
    if (kn[i].label in _labels) {
      _labels[kn[i].label] += 1
    } else {
      _labels[kn[i].label] = 1
    }

    if (_labels[kn[i].label] > topClassCount) {
      topClassCount = _labels[kn[i].label]
      topClass = kn[i].label
    }
  }

  // Возвращает класс с наибольшим количеством экземпляров
  return topClass
}

// algorithms/machine-learning/__tests__/k-nn.test.js
import kNN from '../k-nn'

describe('kNN', () => {
  it('при неправильных данных должно выбрасываться исключение', () => {
    expect(() => {
      kNN()
    }).toThrowError('Отсутствует обязательный параметр')
  })

  it('при неправильных метках должно выбрасываться исключение', () => {
    const noLabels = () => {
      kNN([[1, 1]])
    }
    expect(noLabels).toThrowError('Отсутствует обязательный параметр')
  })

  it('при отсутствии целевого образца должно выбрасываться исключение #1', () => {
    const noClassification = () => {
      kNN([[1, 1]], [1])
    }
    expect(noClassification).toThrowError('Отсутствует обязательный параметр')
  })

  it('при отсутствии целевого образца должно выбрасываться исключение #2', () => {
    const inconsistent = () => {
      kNN([[1, 1]], [1], [1])
    }
    expect(inconsistent).toThrowError('Матрицы имеют разную форму')
  })

  it('должен выполнить классификацию целевых образцов', () => {
    let dataSet
    let labels
    let toClassify
    let expectedClass

    dataSet = [
      [1, 1],
      [2, 2],
    ]
    labels = [1, 2]
    toClassify = [1, 1]
    expectedClass = 1
    expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)

    dataSet = [
      [1, 1],
      [6, 2],
      [3, 3],
      [4, 5],
      [9, 2],
      [2, 4],
      [8, 7],
    ]
    labels = [1, 2, 1, 2, 1, 2, 1]
    toClassify = [1.25, 1.25]
    expectedClass = 1
    expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)

    dataSet = [
      [1, 1],
      [6, 2],
      [3, 3],
      [4, 5],
      [9, 2],
      [2, 4],
      [8, 7],
    ]
    labels = [1, 2, 1, 2, 1, 2, 1]
    toClassify = [1.25, 1.25]
    expectedClass = 2
    expect(kNN(dataSet, labels, toClassify, 5)).toBe(expectedClass)
  })

  it('должен выполнить классификацию целевого образца с соседями на одинаковых расстояниях', () => {
    const dataSet = [
      [0, 0],
      [1, 1],
      [0, 2],
    ]
    const labels = [1, 3, 3]
    const toClassify = [0, 1]
    const expectedClass = 3
    expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)
  })

  it('должен выполнить классификацию целевого образца с соседями в трехмерном пространстве', () => {
    const dataSet = [
      [0, 0, 0],
      [0, 1, 1],
      [0, 0, 2],
    ]
    const labels = [1, 3, 3]
    const toClassify = [0, 0, 1]
    const expectedClass = 3
    expect(kNN(dataSet, labels, toClassify)).toBe(expectedClass)
  })
})

Запускаем тесты:

npm run test ./algorithms/machine-learning/__tests__/k-nn