Мини-проект: ближайшие соседи

Как сервисы угадывают, что вам понравится? Один из самых простых и понятных способов — k ближайших соседей (k-nearest neighbors, kNN): найти k самых похожих на вас людей и посмотреть, что нравится им. «Похожие» — это близкие по расстоянию, если каждого человека записать строкой чисел. Метод хорошо разобран, например, в книге «Грокаем алгоритмы» (глава 10). Здесь соберём его сами из того, что уже знаем: разности с транслированием, np.linalg.norm, np.argsort.

Шаг 1. Похожие гости

Восемь постоянных гостей кофейни оценили шесть напитков по шкале от 1 до 5. Столбцы: эспрессо, капучино, латте, раф, чай, какао. Новая гостья Оля оценила первые пять, а какао не пробовала. Понравится ли оно ей?

import numpy as np

drinks = np.array(["эспрессо", "капучино", "латте", "раф", "чай", "какао"])
ratings = np.array([
    [5, 4, 2, 1, 2, 1],
    [2, 3, 5, 5, 3, 5],
    [4, 5, 3, 2, 1, 2],
    [1, 2, 4, 5, 4, 4],
    [5, 5, 3, 2, 2, 1],
    [3, 3, 3, 3, 5, 3],
    [2, 2, 5, 4, 3, 5],
    [4, 3, 2, 2, 4, 2],
])
olya = np.array([2, 3, 5, 4, 3])     # без какао
print(ratings.shape, olya.shape)
print(drinks[:5])

(8, 6) (5,)
['эспрессо' 'капучино' 'латте' 'раф' 'чай']

dists = ...

dists = np.linalg.norm(ratings[:, :5] - olya, axis=1)

Шаг 2. Три ближайших

np.argsort возвращает номера в порядке возрастания — первые k из них и есть ближайшие соседи.

neighbors = ...

neighbors = np.argsort(dists)[:3]

Шаг 3. Предсказание

Прогноз для Оли — средняя оценка какао у её соседей. Массив номеров выбирает строки таблицы так же, как элементы одномерного массива в уроке о сортировке: ratings[neighbors] — таблица из трёх строк.

cocoa_pred = ...

cocoa_pred = ratings[neighbors][:, 5].mean()

Ниже первая строка — средние оценки трёх соседей Оли по всем шести напиткам, вторая — средние всех гостей:

print(np.round(ratings[neighbors].mean(axis=0), 1))
print(np.round(ratings.mean(axis=0), 1))

[1.7 2.3 4.7 4.7 3.3 4.7]
[3.2 3.4 3.4 3.  3.  2.9]

Шаг 4. Прогноз продаж

Тот же метод предсказывает числа. Кофейня записывала для каждого дня три признака — температуру, выходной ли это (1 или 0) и была ли акция (1 или 0) — и сколько чашек продали. Завтра будний день, +17 °C, без акции. Сколько варить?

days = np.array([
    # температура, выходной, акция
    [5, 0, 0],
    [12, 0, 1],
    [18, 1, 0],
    [22, 1, 1],
    [8, 1, 0],
    [25, 0, 0],
    [15, 0, 1],
    [19, 0, 0],
    [3, 1, 1],
    [16, 1, 0],
    [28, 1, 0],
    [10, 0, 0],
])
cups = np.array([140, 190, 260, 330, 250, 150, 200, 155, 280, 265, 240, 145])
tomorrow = np.array([17, 0, 0])
print(days.shape, cups.shape)

(12, 3) (12,)

naive_dists = ...
naive_nb = ...
naive_pred = ...

naive_dists = np.linalg.norm(days - tomorrow, axis=1)
naive_nb = np.argsort(naive_dists)[:4]
naive_pred = cups[naive_nb].mean()

print(days[naive_nb])
print(cups[naive_nb])

[[18  1  0]
 [16  1  0]
 [19  0  0]
 [15  0  1]]
[260 265 155 200]

Шаг 5. Нормализация

Решение — привести каждый признак к одной шкале 0–1, как в уроке о нормализации: (x - min) / (max - min) по каждому столбцу. Минимум и максимум берутся по прошлым дням, и завтрашний день приводится теми же числами.

lo = ...
hi = ...
days_n = ...
tomorrow_n = ...
scaled_nb = ...
scaled_pred = ...

lo = days.min(axis=0)
hi = days.max(axis=0)
days_n = (days - lo) / (hi - lo)
tomorrow_n = (tomorrow - lo) / (hi - lo)
scaled_nb = np.argsort(np.linalg.norm(days_n - tomorrow_n, axis=1))[:4]
scaled_pred = cups[scaled_nb].mean()

print("соседи без нормализации:", days[naive_nb][:, 1].sum(), "выходных из 4 →", naive_pred, "чашек")
print("соседи после нормализации:", days[scaled_nb][:, 1].sum(), "выходных из 4 →", scaled_pred, "чашек")

соседи без нормализации: 2 выходных из 4 → 220.0 чашек
соседи после нормализации: 0 выходных из 4 → 147.5 чашек

Выводы