Тема 4. Классификация

В теме 3 мы построили общий каркас обучения с учителем: выборка, функция потерь, разделение данных, оценка качества и baseline. Теперь применим этот каркас к первому конкретному семейству задач — классификации. Это та область, с которой исторически началось машинное обучение как практическая инженерная дисциплина: фильтрация спама, распознавание рукописных цифр, медицинская диагностика, кредитный скоринг. Все эти задачи сводятся к одной формальной постановке — приписать объекту одну из конечного числа меток.

В рамках темы мы разберём четыре опорных алгоритма: логистическую регрессию, метод $k$ ближайших соседей, деревья решений и метод опорных векторов. Они выбраны не как «самые лучшие», а как методически взаимодополняющие — каждый воплощает отдельный принцип построения классификатора. На сравнительном примере мы увидим, чем они различаются, и научимся выбирать метрику качества, адекватную задаче.

Задача классификации

Постановка задачи

Сохраняя обозначения темы 3, рассмотрим обучающую выборку $D = \{(x_i, y_i)\}_{i=1}^{n}$, где $x_i \in \mathbb{R}^d$ — вектор признаков объекта, а ответ $y_i$ принимает значения из конечного множества меток $\mathcal{Y} = \{c_1, \ldots, c_K\}$. Если $K = 2$, говорят о бинарной классификации (англ. binary classification) — две метки, обычно обозначаемые $\{0, 1\}$ или $\{-1, +1\}$; при $K > 2$ задача называется многоклассовой (англ. multiclass classification). Бинарный случай содержательно богаче, чем кажется: к нему сводится множество практических задач — «отказ / одобрение», «болен / здоров», «мошенничество / норма». Многие алгоритмы изначально формулируются для бинарного случая, а многоклассовая постановка получается обёртками: «один против всех» (англ. one-vs-rest) обучает $K$ бинарных моделей, каждая отделяет свой класс от остальных; «один против одного» (англ. one-vs-one) обучает $K(K-1)/2$ попарных классификаторов и агрегирует их голоса.

Геометрически работа классификатора — это разбиение признакового пространства на области, каждая из которых отвечает за свой класс. Граница между областями называется разделяющей поверхностью (англ. decision boundary). В двумерном случае она — кривая на плоскости; в $d$-мерном — поверхность размерности $d-1$. Форма этой поверхности — главный различительный признак алгоритмов классификации: у логистической регрессии и линейного SVM она линейна, у $k$-NN и деревьев — кусочно-постоянна, у SVM с ядром или нейронной сети — произвольно гладкая.

Помимо самой метки, классификатор часто выдаёт апостериорную вероятность (англ. posterior probability) — оценку $\hat{P}(y = c_k \mid x)$. Эта величина отвечает на более информативный вопрос, чем просто метка: «насколько модель уверена в своём ответе». Из вероятности легко получить метку — взяв класс с максимальным значением; из метки получить вероятность нельзя. На вероятностных выходах построены пороговые правила (применять модель только при $\hat{P}(y = 1 \mid x) > 0{,}8$), вычисление ожидаемой полезности при разных стоимостях ошибок, методы калибровки и большая часть метрик качества бинарной классификации.

Не все алгоритмы дают вероятностные оценки естественным образом. Логистическая регрессия по построению выдаёт $\hat{P}(y = 1 \mid x)$, наивный байесовский классификатор — тоже, но SVM в исходной формулировке возвращает только знак расстояния до разделяющей плоскости; для перехода к вероятностям применяется отдельная процедура калибровки ¹. Эту разницу между «решающим» и «вероятностным» классификатором мы ещё используем при разговоре про метрики.

Основные алгоритмы классификации

Логистическая регрессия

Несмотря на название, логистическая регрессия (англ. logistic regression) — алгоритм классификации, а не регрессии. Историческая инверсия восходит к работам Дэвида Кокса ², предложившего этот метод для анализа бинарных исходов задолго до того, как машинное обучение оформилось как отдельная дисциплина.

Идея простая. Сначала строится линейная комбинация признаков $z = w^\top x + b$, где $w \in \mathbb{R}^d$ — вектор весов, $b \in \mathbb{R}$ — смещение. Величина $z$ может принимать любые вещественные значения и сама по себе не интерпретируется как вероятность. Чтобы получить вероятность принадлежности к классу 1, $z$ пропускается через сигмоиду (англ. sigmoid) — функцию

$\sigma(z) = \frac{1}{1 + e^{-z}}.$

Сигмоида монотонно возрастает на $\mathbb{R}$, принимает значения в интервале $(0, 1)$ и симметрична относительно точки $(0,\, 0{,}5)$. Получаем вероятностную модель: $\hat{P}(y = 1 \mid x) = \sigma(w^\top x + b)$. Решающее правило очевидно: $\hat{y} = 1$, если $\sigma(w^\top x + b) > 0{,}5$, то есть если $w^\top x + b > 0$. Разделяющая поверхность — гиперплоскость $w^\top x + b = 0$; за это логистическую регрессию относят к линейным классификаторам.

Обучение сводится к подбору $(w, b)$, минимизирующих функцию логарифмических потерь (англ. log loss, или cross-entropy loss):

$\mathcal{L}(w, b) = -\frac{1}{n} \sum_{i=1}^{n} \left[ y_i \log \sigma(z_i) + (1 - y_i) \log (1 - \sigma(z_i)) \right].$

Эта функция эквивалентна максимизации правдоподобия в предположении, что метки — независимые реализации Бернулли с параметром $\sigma(z_i)$. У неё есть свойство, важное практически: $\mathcal{L}$ выпукла по параметрам, значит у задачи единственный глобальный минимум, и градиентный спуск гарантированно к нему сходится. Это резко контрастирует с нейронными сетями, где задача невыпуклая и оптимизация может застрять в локальном минимуме.

К функции потерь добавляют регуляризующий член — обычно $L_2$-норму $\lambda \|w\|^2$ (ridge) или $L_1$-норму $\lambda \|w\|_1$ (lasso). Первый штрафует большие веса, не давая модели перенастроиться на шум; второй обнуляет малозначимые признаки и работает как встроенный отбор. Реализация в scikit-learn по умолчанию использует $L_2$, что для большинства задач — разумный старт ³.

Сильные стороны логистической регрессии — интерпретируемость (знак и величина $w_j$ говорят, в какую сторону и насколько признак $x_j$ влияет на класс 1), вычислительная дешевизна, устойчивость к небольшому шуму в данных. Главное ограничение — линейность: если истинная разделяющая поверхность нелинейна, никакая настройка $(w, b)$ не даст хорошего качества. Частичный обход — переход к расширенному признаковому пространству: добавление квадратичных или взаимодействующих признаков $x_j x_k$, полиномиальных преобразований, индикаторов категорий. Тогда модель остаётся линейной в новом пространстве, но нелинейна в исходном — приём, идейно близкий ядровому трюку, к которому мы вернёмся в разговоре про SVM.

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

Метод $k$ ближайших соседей (англ. k-nearest neighbors, kNN) — едва ли не самый прозрачный по логике алгоритм классификации. Чтобы определить класс нового объекта $x$, мы находим в обучающей выборке $k$ объектов, ближайших к $x$ по выбранной метрике, и приписываем $x$ тот класс, который встречается среди соседей чаще. В случае равенства голосов используется одно из соглашений: ближайший сосед, наименьший класс, случайный выбор.

Метод предложен Фиксом и Ходжесом ещё в 1951 году ⁴, а классический результат об асимптотических свойствах принадлежит Ковер и Харт ⁵: ошибка одного ближайшего соседа ($k = 1$) при $n \to \infty$ не превосходит удвоенной байесовской ошибки. Для метода без обучения и без модели в обычном смысле слова — результат удивительно сильный.

Формально решающее правило записывается так. Зафиксируем метрику расстояния $d(\cdot, \cdot)$ — обычно евклидову $d(x, x') = \sqrt{\sum_j (x_j - x'_j)^2}$, иногда манхэттенскую $\sum_j |x_j - x'_j|$ или косинусную для разреженных текстовых признаков. Пусть $N_k(x) \subset D$ — множество $k$ объектов обучающей выборки, ближайших к $x$ по $d$. Тогда

$\hat{y}(x) = \arg\max_{c \in \mathcal{Y}} \sum_{(x_i, y_i) \in N_k(x)} \mathbb{1}[y_i = c].$

Голосование можно сделать взвешенным: вес соседа обратно пропорционален расстоянию, тогда более близкие объекты влияют сильнее.

Выбор $k$ — главный гиперпараметр. При $k = 1$ модель идеально подгоняется под обучающую выборку (нулевая ошибка обучения), но крайне чувствительна к шуму: один ошибочно размеченный объект меняет класс целой окрестности. С ростом $k$ граница становится глаже, а модель — устойчивее к шуму, но рискует размыть малочисленные классы. Типичные значения — от $3$ до $\sqrt{n}$; конкретный выбор — через валидационную выборку или кросс-валидацию (тема 7).

Метод имеет два неустранимых ограничения. Первое — проклятие размерности (англ. curse of dimensionality): в пространствах высокой размерности расстояния между точками концентрируются вокруг общего среднего, и понятие «ближайший» теряет содержательный смысл. На датасете из миллиона изображений в исходных пиксельных признаках kNN работает плохо, и здесь нужна предварительная редукция размерности (тема 6) или обучение представлений. Второе — чувствительность к масштабу признаков: евклидова метрика суммирует квадраты разностей по всем координатам, и признак с большим разбросом подавляет признак с малым. Если возраст измерен в годах ($20$–$80$), а зарплата — в рублях ($30\,000$–$300\,000$), второй полностью определит расстояние. Стандартное лекарство — масштабирование (англ. standardization) каждого признака к нулевому среднему и единичной дисперсии, выполненное до обучения и применённое к тестовым данным с теми же статистиками (см. тему 3 про утечку через нормализацию).

Платой за простоту обучения становится дороговизна предсказания: чтобы классифицировать один новый объект, нужно вычислить расстояние до всех $n$ обучающих точек. На больших выборках это требует структур пространственного индексирования — KD-деревьев, ball-деревьев, локально-чувствительного хеширования; в библиотеке scikit-learn они реализованы и автоматически выбираются по размеру данных.

Деревья решений

Дерево решений (англ. decision tree) задаёт классификатор как иерархию вложенных условий на признаках. Каждый внутренний узел дерева содержит условие вида «$x_j \leq t$» (для непрерывных признаков) или «$x_j \in S$» (для категориальных). От узла идут две ветви — «истинно» и «ложно»; в каждом листе записан класс или распределение вероятностей по классам. Чтобы предсказать класс нового объекта, мы спускаемся от корня к листу, на каждом шаге выбирая ветвь по условию.

Геометрически дерево разбивает признаковое пространство на прямоугольники, оси которых параллельны осям координат, и каждому прямоугольнику приписывает класс. Это даёт характерную «ступенчатую» границу решения, заметную на сравнительной иллюстрации в начале темы.

Алгоритм построения — жадный и рекурсивный. На каждом шаге для текущего узла перебираются все пары «признак $j$, порог $t$», и выбирается та, что максимально «улучшает» однородность дочерних узлов. Степень однородности измеряется одним из критериев. Индекс Джини (англ. Gini impurity) для узла $S$, в котором доля объектов класса $c$ равна $p_c$, определяется как $G(S) = \sum_c p_c (1 - p_c) = 1 - \sum_c p_c^2$ и принимает значение $0$ для чистого узла. Энтропия (англ. entropy) задаётся формулой $H(S) = -\sum_c p_c \log_2 p_c$ и тоже минимальна, когда все объекты узла принадлежат одному классу. Информационный выигрыш разбиения — взвешенная разность исходного критерия и средневзвешенного критерия в потомках. На практике различия между Джини и энтропией невелики, обе ведут к похожим деревьям; CART ⁶ использует Джини, C4.5/ID3 ⁷ — энтропию.

Жадное построение продолжается, пока не выполнится одно из условий остановки: лист стал чистым, число объектов в узле меньше порога, достигнута максимальная глубина. Без этих ограничений дерево разрастается до тех пор, пока каждому обучающему объекту не достанется собственный лист — модель идеально подгоняется под обучающую выборку и катастрофически переобучается. Это явная иллюстрация компромисса смещения и разброса (тема 3) на одном алгоритме: при глубине $1$ — высокое смещение, при неограниченной глубине — высокий разброс.

Управление сложностью реализуется двумя способами. Предупреждение роста (англ. pre-pruning) ограничивает дерево заранее: максимальная глубина, минимальное число объектов в листе, минимальное улучшение критерия для разрешения сплита. Обрезка (англ. post-pruning) сначала строит дерево до конца, а затем удаляет ветви, не дающие выигрыша на отложенной выборке; типичный вариант — обрезка с штрафом за число листьев (англ. cost-complexity pruning).

Деревья решений интерпретируемы — по обученному дереву читается набор правил вида «если возраст > 30 и доход > 50000, то одобрить». Они работают с категориальными признаками без предварительного кодирования, нечувствительны к масштабу (на пороги не влияет, измерять ли зарплату в рублях или в копейках), естественно обрабатывают пропуски через специальные сплиты. Тем не менее одиночное дерево редко даёт хорошее качество в реальных задачах: оно неустойчиво — небольшое изменение обучающей выборки порождает дерево совсем другой структуры; ступенчатая граница плохо приближает гладкие функции; полностью раскрытое дерево переобучается. Эти ограничения снимаются ансамблевыми методами — случайным лесом и градиентным бустингом, — которые мы разберём в теме 7.

Метод опорных векторов (SVM)

Метод опорных векторов (англ. support vector machine, SVM), предложенный Кортес и Вапником в середине 1990-х ⁸, — алгоритм, в котором геометрия задачи поставлена в центр. Идея в следующем. Если две группы точек линейно разделимы, между ними существует не одна, а целое семейство разделяющих прямых; SVM выбирает ту, что максимально удалена от ближайших точек обоих классов. Это гиперплоскость максимального зазора (англ. maximum-margin hyperplane), а ближайшие к ней объекты обучающей выборки — опорные векторы (англ. support vectors), которые целиком определяют положение разделяющей плоскости.

Формально, для бинарной задачи с метками $y_i \in \{-1, +1\}$ ищется $(w, b)$, минимизирующее $\frac{1}{2} \|w\|^2$ при условиях $y_i (w^\top x_i + b) \geq 1$ для всех $i$. Расстояние от точки до плоскости $w^\top x + b = 0$ равно $|w^\top x + b| / \|w\|$, ширина зазора — $2 / \|w\|$, и минимизация $\|w\|^2$ соответствует максимизации зазора. Оптимизация выпуклая (квадратичное программирование), решение единственно.

Если данные не разделимы линейно (а реальные данные практически никогда не разделимы), вводят мягкий зазор (англ. soft margin) — штраф за нарушение условий: задача переписывается как минимизация $\frac{1}{2} \|w\|^2 + C \sum_i \xi_i$ при $y_i (w^\top x_i + b) \geq 1 - \xi_i$, $\xi_i \geq 0$. Параметр $C$ балансирует ширину зазора и допустимый объём нарушений: большое $C$ — узкий зазор, мало ошибок; малое $C$ — широкий зазор, нарушения допускаются.

Для нелинейных границ применяется ядровой трюк (англ. kernel trick). Алгоритм формально работает с признаковым пространством через скалярные произведения $\langle x_i, x_j \rangle$; если заменить их функцией ядра $K(x_i, x_j) = \langle \varphi(x_i), \varphi(x_j) \rangle$, соответствующей какому-то нелинейному отображению $\varphi$ в более многомерное пространство, мы получим линейный классификатор в этом новом пространстве — а в исходном он окажется нелинейным. Главное, что само $\varphi$ вычислять не приходится: достаточно знать функцию $K$. Наиболее популярны полиномиальное ядро $K(x, x') = (\langle x, x' \rangle + 1)^p$ и радиально-базисное ядро (англ. radial basis function, RBF) $K(x, x') = \exp(-\gamma \|x - x'\|^2)$. RBF-ядро универсально и для большинства задач даёт сильный baseline, но его выбор означает два гиперпараметра одновременно — $C$ и $\gamma$, — которые нужно подбирать совместно.

Сильные стороны SVM — теоретически обоснованный принцип максимума зазора, эффективность в пространствах высокой размерности (когда $d > n$), способность работать с нелинейными границами через ядра. Слабости — плохая масштабируемость на больших $n$ (квадратичная программа решается за $O(n^2)$ или хуже), отсутствие вероятностных выходов в исходной формулировке, чувствительность к подбору $C$ и параметров ядра. На современных датасетах с миллионами объектов SVM встречается реже, чем в 2000-е, уступая место градиентному бустингу и нейронным сетям; но как методологически строгий алгоритм с прозрачной геометрией он остаётся важной частью курса.

Метрики качества классификации

Основные метрики

Задача оценки качества классификатора кажется тривиальной — посчитать долю правильных ответов — но на практике именно здесь чаще всего ошибаются. Доля правильных ответов, или точность распознавания (англ. accuracy), на несбалансированных данных вводит в заблуждение, а в задачах с разной стоимостью ошибок просто не отвечает на вопрос заказчика. Обратимся к основной структуре, на которой строятся все метрики бинарной классификации.

Матрица ошибок (англ. confusion matrix) сравнивает истинные метки и предсказания модели и сводит их в таблицу $2 \times 2$. Для класса 1 как «положительного» (это всегда соглашение) принято обозначать четыре ячейки:

• TP (англ. true positives) — объекты класса 1, предсказанные как 1;
• TN (англ. true negatives) — объекты класса 0, предсказанные как 0;
• FP (англ. false positives) — объекты класса 0, ошибочно предсказанные как 1 (ошибка I рода);
• FN (англ. false negatives) — объекты класса 1, ошибочно предсказанные как 0 (ошибка II рода).

Из этих четырёх чисел собираются все остальные метрики. Точность распознавания $\text{accuracy} = (TP + TN) / (TP + TN + FP + FN)$ — доля правильных ответов. На сбалансированных данных она информативна; на сильно перекошенных — нет. Если в выборке 99% объектов класса 0 и 1% класса 1, тривиальный классификатор «всегда 0» даёт accuracy 99%, не различая классы вовсе. Это та же логика baseline, что обсуждалась в теме 3: метрика без контекста ни о чём не говорит.

Содержательная пара метрик — точность и полнота. Точность (англ. precision) $= TP / (TP + FP)$ отвечает на вопрос «среди объектов, которые модель назвала положительными, какая доля действительно положительна?». Полнота (англ. recall, или sensitivity) $= TP / (TP + FN)$ — «какую долю реально положительных объектов модель нашла?». Конкуренция между ними фундаментальна: повышая порог отсечения, мы делаем модель «осторожнее» — растёт точность, падает полнота; снижая порог, ловим больше положительных за счёт большего числа ложных срабатываний.

Выбор между ними диктует задача. В фильтрации спама дорого попасть письмом в папку «спам» по ошибке — ценится точность. В медицинском скрининге дорого пропустить больного — ценится полнота. В мошеннической транзакции и то и другое плохо, и приходится искать компромисс. Численный компромисс задаётся F1-мерой (англ. F1 score) — гармоническим средним точности и полноты:

$F_1 = \frac{2 \cdot \text{precision} \cdot \text{recall}}{\text{precision} + \text{recall}}.$

Гармоническое среднее (а не арифметическое) выбрано потому, что оно сильно проседает, если одна из метрик мала: классификатор с точностью 0.99 и полнотой 0.01 имеет F1 ≈ 0.02, а не 0.5. Существует обобщение $F_\beta$, где $\beta > 1$ повышает вес полноты, $\beta < 1$ — точности; на практике $F_1$ — стандартный выбор.

Для классификаторов, выдающих не метку, а оценку вероятности или score, есть метрики, не зависящие от выбора порога. ROC-кривая (англ. receiver operating characteristic) строится в координатах «доля ложных срабатываний» (FPR $= FP / (FP + TN)$) по горизонтали и «доля верных обнаружений» (TPR $= TP / (TP + FN) =$ recall) по вертикали; точки кривой соответствуют разным порогам отсечения ⁹. AUC (англ. area under the curve) — площадь под этой кривой. У случайного классификатора AUC = 0.5 (диагональ), у идеального — 1.0. AUC имеет интерпретацию вероятности: для случайно взятой пары «положительный объект, отрицательный объект» это вероятность того, что классификатор присвоит положительному объекту более высокий score, чем отрицательному.

ROC-кривая удобна как метрика, не зависящая ни от порога, ни от базового распределения классов. Это же — её слабость на сильно несбалансированных данных: при доминирующем отрицательном классе даже большое число FP даёт малое изменение FPR, и AUC завышает реальное качество. В таких задачах информативнее PR-кривая (англ. precision-recall curve) в координатах «полнота — точность», а её площадь (PR-AUC, или average precision) — более честная оценка ¹⁰.

Для многоклассовой классификации матрица ошибок становится $K \times K$, а точность и полнота рассчитываются для каждого класса отдельно. Агрегируют их либо макро-усреднением (англ. macro-average) — простое среднее метрик по классам, не зависит от размеров классов и подходит, когда все классы одинаково важны, — либо взвешенным усреднением (англ. weighted average), где вес класса пропорционален его размеру. Микро-усреднение, эквивалентное общей accuracy, тоже встречается, но содержательно мало добавляет.

Подытоживая: выбор метрики — это часть формулировки задачи, а не вспомогательный шаг. Объявить «будем оптимизировать accuracy» в задаче с 1%-ной редкостью класса — значит фактически разрешить модели не находить редкий класс вовсе. В лабораторной работе по этой теме мы сравним несколько классификаторов на одном датасете и подберём ту метрику, которая разводит модели по содержательному различию, а не по статистическому шуму.

Литература

1. Platt J. C. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. — Advances in Large Margin Classifiers, 1999, С. 61–74.
2. Cox D. R. The Regression Analysis of Binary Sequences. — Journal of the Royal Statistical Society. Series B (Methodological), 1958, С. 215–242, DOI: 10.1111/j.2517-6161.1958.tb00292.x.
3. Pedregosa F., Varoquaux G., Gramfort A., Michel V., Thirion B., Grisel O., Blondel M., Prettenhofer P., Weiss R., Dubourg V., Vanderplas J., Passos A., Cournapeau D., Brucher M., Perrot M., Duchesnay {. Scikit-learn: Machine Learning in Python. — Journal of Machine Learning Research, 2011, С. 2825–2830.
4. Fix E., Hodges J. L. Discriminatory Analysis. Nonparametric Discrimination: Consistency Properties. — USAF School of Aviation Medicine, Randolph Field, Texas, 1951.
5. Cover T. M., Hart P. E. Nearest Neighbor Pattern Classification. — IEEE Transactions on Information Theory, 1967, С. 21–27, DOI: 10.1109/TIT.1967.1053964.
6. Breiman L., Friedman J. H., Olshen R. A., Stone C. J. Classification and Regression Trees. — Wadsworth and Brooks/Cole, 1984.
7. Quinlan J. R. Induction of Decision Trees. — Machine Learning, 1986, С. 81–106, DOI: 10.1007/BF00116251.
8. Cortes C., Vapnik V. Support-Vector Networks. — Machine Learning, 1995, С. 273–297, DOI: 10.1007/BF00994018.
9. Fawcett T. An Introduction to ROC Analysis. — Pattern Recognition Letters, 2006, С. 861–874, DOI: 10.1016/j.patrec.2005.10.010.
10. Saito T., Rehmsmeier M. The Precision-Recall Plot Is More Informative than the ROC Plot When Evaluating Binary Classifiers on Imbalanced Datasets. — PLOS ONE, 2015, С. e0118432, DOI: 10.1371/journal.pone.0118432.