Разбираемся в ML без воды: от базы до Attention. Часть 4:...

В третьей части мы закончили с линейной регрессией. Теперь пора перейти к задаче классификации․

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

Сфера применения задач классификации довольно обширна:

кликнет ли пользователь по рекламному баннеру
банковская транзакция мошенническая или валидная
опухоль доброкачественная или злокачественная
письмо является спамом или нет

На первый взгляд может показаться, что здесь можно просто взять линейную регрессию и попытаться предсказывать классы через неё. Например: всё что больше 0.5 — считаем классом 1, а всё что меньше — классом 0.

Но довольно быстро выясняется, что линейная регрессия для таких задач подходит плохо.

Для задачи классификации это неудобно: линейная регрессия может предсказывать любые вещественные числа — например 100500, или -0.3. Формально через порог такие значения всё ещё можно превратить в классы, но интерпретировать их становится сложнее. Особенно, когда у нас несколько классов.

Кроме того, нас обычно интересует не просто номер класса, а вероятность принадлежности объекта к нему. Например: модель уверена в диагнозе на 99%, или лишь на 50.01%?

Из-за этих соображений оставим в покое пространство линейных функций и перейдем к другому классу $\mathcal{F}$ .
Пока что договоримся, что классов у нас всего два: класс (1) и класс (0). Задачу многоклассовой классификации разберем позже.

kNN (k-nearest neighbors)

Начнём, наверное, с одной из самых простых моделей классификации.
Разберём основную идею на простом примере.

Представьте ситуацию: мы играем в игру, где нам сказали, что числа 17, 100 и 840 являются “маленькими”, а числа 123456, 150000 и 9999999999 — “большими”. Затем нам дают число 100500 и просят определить, к какому классу оно относится.

Мы не знаем точной границы, после которой числа считаются большими (это может быть и 1000, и 110000), поэтому не можем опереться на одно правило.
Но мы смотрим на ближайшие известные примеры и “спрашиваем их мнение”:

если взять 1 ближайшее число к 100500 — это 123456 (“большое”) → ответ: “большое”
если взять 2 ближайших числа — это 123456 и 150000 (оба “большие”) → ответ: “большое”
если взять 5 ближайших чисел — это 123456, 150000, 840, 100, 17 (2 “больших” и 3 “маленьких”) → выбираем большинство → ответ: “маленькое”

Именно в этом и заключается идея kNN: мы не задаём правило, а смотрим на k ближайших известных примеров и выбираем класс по большинству.

Теперь попробуем формализовать это дело. Для математического описания "близости" двух элементов, будем использовать понятие метрики.

метрическое пространство

Пусть дано множество. Если на нем задана функция $\rho : M \times M \to R$ такое, что $\forall a,b,c \in M$

$\rho(a,b) \ge 0, \rho(a,b) = 0 \iff a=b$ (неотрицательность)
$\rho : M \times M \to R$ (симметричность)
$\rho(a,b) \le \rho(a,c) + \rho(b,c)$ (неравенство треугольника)

то пара $(M, \rho)$ будет называться метрическим пространством, а сама функция $\rho$ — метрикой (или функцией расстояния)

Как пример можно привести одну из самых популярных метрик: евклидово расстояние.

$\rho(x,y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}$

В частности для $R^{2}$ получается знаменитая школьная формула:

Дальше дело нехитрое. Если определить в пространстве метрику $\rho$ , (т.е. функцию, измеряющее расстояние между объектами) то для нового объекта можно найти множество из ближайших соседей: $N_{k}(x) = \arg\!\min_{x_{n}}{\rho(x_i, x_n)}$ .
После чего объекту присваиваем класс, наиболее часто встречающийся среди элементов .

Фактически метод уже работает, но у нас остаётся одна большая проблема.

Что, если мы рассмотрели 3 ближайших объекта и выяснили, что один из них относится к классу , а два других — к классу , но объект класса находится буквально “на расстоянии вытянутой руки”, тогда как бедолаги из класса оказались где-то за тридевять земель?

К какому классу отнести зеленый ромб: треугольники или квадраты?

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

Weighted kNN

В нём каждый сосед имеет некоторый вес, зависящий от расстояния до нового объекта. Чем ближе сосед расположен, тем сильнее его вклад в итоговое решение модели.

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

На практике это реализуется очень просто.

Сначала, для нашего как и в классическом kNN находим ближайших соседей

После этого каждому из них присваиваем вес, зависящий от расстояния. Чаще всего используют обратную зависимость:

$w_i = \frac{1}{\rho(x, x_i) + \varepsilon}$

где $\varepsilon$ — произвольное малое число (например $10^{-15}$ ). Мы помним, что расстояние может равняться нулю, потому и вводим это слагаемое, чтобы случайно не заниматься делением на ноль.

Далее вместо простого подсчёта и сравнения соседей класса А и класса Б вычисляем

$S_A = \sum_{x_i \in N_k(x)} w_i \cdot \mathcal{I}(y_i = A)$

и, аналогично

$S_B = \sum_{x_i \in N_k(x)} w_i \cdot \mathcal{I}(y_i = B)$

где через $\mathcal{I}(\cdot)$ обозначен так называемый индикатор.

$\mathcal{I}(y_i = A) =\begin{cases}1, & y_i = A \\0, & y_i \ne A\end{cases}$

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

Небольшой пример

Допустим мы выбрали , нашли 5 ближайших соседей, посчитали веса. Получили такое:

2 соседа относятся к классу и имеют веса 3 и 5.
остальные 3 соседа относятся к классу B и имеют веса 10, 15 и 20.

В классическом kNN мы бы сказали что $x \in B$ , т.к. большинство ближайших соседей из .

В weighted kNN же считаем сумму весов элементов из: и, аналогично, .

Так как , делаем вердикт. $x \in A$ .

Особенности kNN, итоги и заключение

Теперь разберем некоторые особенности классического kNN.

Во-первых, заметим, что его результат напрямую зависит от выбора числа соседей.

Особенно ярко это проявляется при .
В этом случае для каждого объекта ищется один ближайший сосед. Но в обучающей выборке у каждого объекта его ближайшим соседом фактически оказывается он сам.

В результате модель начинает присваивать объекту его же класс, то есть по сути просто запоминает обучающую выборку без какого-либо обобщения.

Именно поэтому когда вас попросят привести пример переобучения, можете смело сказать 1NN
Точность на обучающей выборке 105%, на тестовой — дырка от бублика (если чудо не произойдет, конечно).

Во-вторых, раз для нового объекта мы ищем ближайших, то стало быть нам каждый раз нужно пройтись по всему множеству $X$ и посчитать расстояние. Это неудобно.
К слову, человечество придумало методы (например, KD-tree, или Ball Tree), который сужает круг поиска, но это уже не классический kNN.

В-третьих, метод очень чувствителен к масштабу признаков.

Так как алгоритм опирается на расстояние, признаки с большими числовыми значениями начинают доминировать в метрике. Например, если один признак измеряется в тысячах, а другой в единицах, то вклад второго практически теряется при вычислении расстояния.

Поэтому перед применением kNN рекомендуется привести признаки к одинаковому масштабу (например, с помощью StandardScaler).

В-четвертых, (и это, на мой взгляд главное), нет обучения. Нельзя сказать что этот метод учиться на данных, он просто из запоминает.

Так когда применить kNN?

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

Также, если в данных присутствует стабильная локальная структура (то есть похожие объекты, как правило, имеют одинаковый ответ), kNN работает особенно хорошо и может быть неожиданно сильным решением.

В реальных системах kNN считается некоторым Brute-force методом, так что, чаще используют его модификации: KD-tree и Ball Tree — для задач с относительно невысокой размерностью, а Approximate Nearest Neighbors (ANN, например HNSW) — для больших данных и задач поиска похожих объектов. Тот же HNSW может незначительно уступать точному kNN по точности, но при этом работает на порядки быстрее, особенно на больших датасетах, где полный перебор становится слишком дорогим удовольствием.

В этой короткой статье мы разобрали kNN, чтобы на простом примере увидеть, как вообще работает классификация.

В следующих частях перейдём к более “классическим” подходам — логистической регрессии, SVM и другим методам, где модель уже не запоминает данные, а учится строить явную границу между классами.

推荐订阅源

Все публикации подряд на Хабре

kNN (k-nearest neighbors)

Weighted kNN

Особенности kNN, итоги и заключение