Метрические методы

Основная идея

Метрические методы основаны на гипотезе компактности: объекты одного класса находятся близко, объекты разных классов — далеко.

Ближайший центроид (Nearest Centroid)

Алгоритм:
Для каждого класса вычисляется центроид (среднее значение признаков).
Новый объект относится к классу, чей центроид ближе.

Плюсы:

  • Простота реализации.
  • Мало параметров.
  • Быстрая классификация.

Минусы:

  • Чувствителен к выбросам.
  • Подходит только для “колоколообразных” распределений.

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

Алгоритм:

  1. Храним всю обучающую выборку.
  2. Для нового объекта находим ( k ) ближайших соседей.
  3. Класс — наиболее частый среди соседей.

Гиперпараметры:

  • ( k ) — число соседей.
  • Метрика расстояния.
  • Весовая функция.

Особенности:

  • Ленивое обучение: модель не обучается заранее, все вычисления происходят при классификации.
  • Требует хранения всей выборки.
  • Медленный на больших данных.

Весовые обобщения kNN

Можно учитывать не только количество соседей, но и их расстояние до объекта:

[ a(x) = \arg \max \sum_{t=1}^{k} w_t \cdot I[y(x_t) = a] ]

где ( w_t ) — вес, зависящий от расстояния.

Примеры весовых схем:

  • Обратное расстояние: ( w_t = \frac{1}{\rho(x, x_t)} )
  • Ядерные веса: ( w_t = K\left(\frac{\rho(x, x_t)}{h}\right) )

Регрессия Надарая–Ватсона

Обобщение kNN для регрессии:

[ a(x) = \frac{\sum_{i=1}^{m} w_i(x) y_i}{\sum_{i=1}^{m} w_i(x)} ]

где ( w_i(x) ) — вес, зависящий от расстояния до объекта обучения.

Проблемы метрических методов

  1. Зависимость от масштаба признаков
    Решение: нормировка (например, StandardScaler).

  2. Проклятие размерности
    В больших размерностях все объекты становятся “одинаково далекими”.
    Но на реальных данных есть низкоразмерная структура.

  3. Медленная классификация
    Решение: эффективные структуры данных (KD-tree, Ball tree, HNSW).

Метрики расстояния

  • Евклидова: ( \sqrt{\sum (x_i - z_i)^2} )
  • Манхэттенская: ( \sum |x_i - z_i| )
  • Минковского: ( \left( \sum |x_i - z_i|^p \right)^{1/p} )
  • Махаланобиса: учитывает ковариацию признаков.
  • Косинусная мера: для текстов и векторов.
  • Джаккарда: для множеств.
  • DTW (Dynamic Time Warping): для временных рядов.
  • Левенштейна: для строк.

Пример: kNN на Python (scikit-learn)

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(n_neighbors=5, metric='euclidean')
model.fit(X_train, y_train)
predictions = model.predict(X_test)

Итог

Метрические методы — простые, интерпретируемые и мощные инструменты, особенно когда:

  • Нет явных признаковых описаний.
  • Данные имеют геометрическую структуру.
  • Нужна быстрая прототипизация.

Главный недостаток — вычислительная сложность на больших данных, но это решается выбором эффективных метрик и структур данных.