1. Введение
В этом руководстве мы разберем, как работают два популярных алгоритма классификации — k-ближайших соседей (kNN) и взвешенных k-ближайших соседей (kwNN) — на примере набора данных Iris (цветы ириса).
Почему это полезно?
kNN — один из самых простых алгоритмов машинного обучения, но он отлично объясняет базовые принципы классификации.
kwNN — его улучшенная версия, где соседи учитываются с разным весом.
Мы напишем алгоритмы с нуля, без использования готовых библиотек (вроде `sklearn.neighbors`), чтобы понять, как всё работает внутри.
2. Подготовка данных
Используем классический набор данных Iris, который содержит информацию о трех видах ирисов:
Setosa
Versicolor
Virginica
Каждый цветок описывается четырьмя признаками, но для простоты мы возьмем только два:
Длина лепестка (Petal.Length)
Ширина лепестка (Petal.Width)
Загрузка данных
from sklearn.datasets import load_iris
import numpy as np
iris = load_iris()
features = iris.data[:, 2:4] # Берём только длину и ширину лепестка
labels = iris.target_names[iris.target] # Названия видов
3. Как работает kNN?
Алгоритм kNN( k Nearest Neighbors) классифицирует объект на основе k ближайших к нему точек из обучающей выборки.
Пример
У нас есть новый цветок с длиной лепестка = 3 см и шириной = 1 см.
Алгоритм находит k ближайших известных цветков и смотрит, к какому виду они относятся.
Если среди них больше Setosa, то и новый цветок будет Setosa.
Шаги алгоритма
Вычисляем расстояния от нового объекта до всех точек в данных.
Сортируем точки по расстоянию.
Выбираем k ближайших.
Определяем класс по большинству голосов.
Реализация на Python
Функция расстояния (Евклидова метрика)
def distance(u, v):
"""Вычисляет расстояние между двумя точками."""
return np.sqrt(np.sum((u - v) ** 2))Сортировка объектов по расстоянию
def sort_objects_by_dist(xl, z):
"""Сортирует все точки по удалённости от z."""
features, labels = xl
distances = [distance(x, z) for x in features] # Расстояния до всех точек
sorted_indices = np.argsort(distances) # Индексы отсортированных точек
return features[sorted_indices], labels[sorted_indices] # Возвращаем отсортированные данныеСам алгоритм kNN
def kNN(xl, z, k):
"""Классифицирует точку z на основе k ближайших соседей."""
features, labels = xl
sorted_features, sorted_labels = sort_objects_by_dist((features, labels), z)
top_k_labels = sorted_labels[:k] # Берём k ближайших
unique, counts = np.unique(top_k_labels, return_counts=True) # Считаем голоса
return unique[np.argmax(counts)] # Возвращаем самый частый классПример работы
new_flower = np.array([3.0, 1.0]) # Новый цветок (длина=3, ширина=1)
predicted_class = kNN((features, labels), new_flower, k=5)
print(f"Этот цветок, скорее всего, {predicted_class}")Вывод:
Этот цветок, скорее всего, versicolor
4. Улучшенная версия: kwNN (взвешенные k ближайших соседей)
Проблема kNN
Обычный kNN даёт одинаковый вес всем соседям, даже если некоторые из них очень далеко. Это может ухудшить качество классификации.
Решение: kwNN
В kwNN (weighted kNN) ближайшие соседи учитываются с разными весами:
Близкие объекты имеют больший вес.
Далекие объекты — меньший.
Реализация kwNN
def w_kwnn(i, k, q):
"""Весовая функция: чем дальше сосед, тем меньше его вес."""
return (i <= k) * (q ** i)
def kwNN(xl, z, k, q):
"""Классификация с учётом весов соседей."""
features, labels = xl
sorted_features, sorted_labels = sort_objects_by_dist((features, labels), z)
# Считаем веса для каждого соседа
weights = np.array([w_kwnn(i+1, k, q) for i in range(len(sorted_features))])
# Суммируем веса по классам
sum_by_class = {}
for cls, weight in zip(sorted_labels, weights):
if cls not in sum_by_class:
sum_by_class[cls] = 0
sum_by_class[cls] += weight
# Выбираем класс с максимальным весом
return max(sum_by_class.items(), key=lambda x: x[1])[0]Пример работы
new_flower = np.array([5.0, 1.8]) # Новый цветок (длина=5, ширина=1.8)
predicted_class = kwNN((features, labels), new_flower, k=5, q=0.5)
print(f"Этот цветок, скорее всего, {predicted_class}")Вывод:
Этот цветок, скорее всего, virginica
Как выбрать лучшие k и q? Метод LOO (скользящий контроль)
Проблема
Если взять k слишком маленьким, алгоритм будет чувствителен к шуму.
Если k слишком большое, он может учитывать лишние, ненужные точки.
Решение: Leave-One-Out (LOO)
По очереди убираем одну точку из данных.
Обучаем модель на оставшихся.
Проверяем, правильно ли она классифицировала удалённую точку.
Выбираем k и q, при которых ошибка минимальна.
Реализация LOO
def lOO(xl, method='knn'):
"""Подбирает оптимальные параметры методом LOO."""
features, labels = xl
l = len(features)
if method == 'knn':
errors = np.zeros(l-1) # Ошибки для разных k
for i in range(l):
# Убираем i-ю точку
xl_minus_i = (np.delete(features, i, axis=0), np.delete(labels, i))
# Сортируем оставшиеся точки по расстоянию до i-й
ordered_features, ordered_labels = sort_objects_by_dist(xl_minus_i, features[i])
# Проверяем для разных k
for k in range(1, l):
if kNN((ordered_features, ordered_labels), features[i], k) != labels[i]:
errors[k-1] += 1 / l
return errors
else: # kwNN
q_values = np.arange(0.1, 1.1, 0.1) # Возможные q (0.1, 0.2, ..., 1.0)
errors = np.zeros((l-1, len(q_values))) # Ошибки для разных k и q
for i in range(l):
xl_minus_i = (np.delete(features, i, axis=0), np.delete(labels, i))
ordered_features, ordered_labels = sort_objects_by_dist(xl_minus_i, features[i])
for k in range(1, l):
for q_idx, q in enumerate(q_values):
if kwNN((ordered_features, ordered_labels), features[i], k, q) != labels[i]:
errors[k-1, q_idx] += 1 / l
return errors6. Анализ результатов работы алгоритмов
На основе проведенных вычислений мы получили следующие оптимальные параметры:
Для kNN: k = 6 (см. Рисунок 1)
Для kwNN: k = 12, q = 1.0 (см. Рисунок 2)
На примере классификации ирисов мы видим, что оба алгоритма демонстрируют хорошие результаты и kwNN ведет себя аналогично kNN (см Рисунок 3)
Полный код: GitHub
