kNN, деревья решений, ансамбли

Зачем это нужно

Курс ведёт к LLM, так зачем инженеру деревья решений? Причин три.

Первая — таблицы. Большая часть данных в бизнесе — строки и столбцы: транзакции банка, заказы, логистика. Здесь градиентный бустингградиентный бустингEN gradient boosting (GBDT)Реализации — XGBoost, LightGBM, CatBoost. над деревьями до сих пор чаще всего лучший выбор. Он обучается за секунды на ноутбуке и обычно точнее нейросети. Инженер, который на задачу «предсказать отток (уход клиентов) по 30 столбцам» несёт LLM, тратит больше денег и, скорее всего, проигрывает в качестве.

Вторая — идеи возвращаются. Поиск ближайших соседей — это ядро RAG: найти в базе фрагменты текста, чьи эмбеддинги (векторы-«отпечатки» смысла, урок 1.1.1) ближе всего к вопросу (ступень 8). Попросить модель ответить несколько раз и выбрать самый частый ответ (self-consistency) — это ансамбль, о котором речь ниже в этом уроке.

Третья — на этих моделях отлично видно всё, что вы узнали в модуле 2.1: смещение и разброс, переобучение, регуляризацию и утечки данных.

Как проходить этот урок

Это обзорный урок: три семейства алгоритмов за одно занятие. Обязательное ядро — идея kNN и выбор $k$, зачем масштабировать признаки, расчёт индекса Джини и прироста информации на числах, разница между бэггингом и бустингом (таблица-сравнение) и правило «для таблиц сначала пробуйте бустинг». Формулу разброса ансамбля, внутреннее устройство XGBoost, LightGBM и CatBoost и «Китайский угол» при первом чтении можно пробежать глазами.

kNN: спроси соседей

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

Пример: $k = 3$, три ближайших соседа новой точки — два «спам» и одно «не спам». Голосование: 2 против 1, ответ — «спам». Для регрессии: если три ближайшие квартиры стоят 10, 11 и 15 млн ₽, прогноз — их среднее, 12 млн ₽.

Обучения как такового нет: модель просто хранит всю выборку. Вся работа — при предсказании: посчитать расстояние до каждой из $n$ точек, это $O(n \cdot d)$ операций на запрос («О большое» из урока 2.2.1: работа растёт пропорционально числу точек $n$, умноженному на число признаков $d$). Поэтому kNN называют «ленивым» алгоритмом.

Расстояние обычно евклидовоевклидово расстояниеEN Euclidean distanceL2-норма разности двух векторов ‖a − b‖₂ — обычное расстояние «по прямой».: $\lVert a - b \rVert_2$ — длина отрезка между точками, как по линейке. Для $a = (1, 2)$ и $b = (4, 6)$ это $\sqrt{(4-1)^2 + (6-2)^2} = \sqrt{9 + 16} = 5$. Для эмбеддингов текста чаще берут косинусное сходство из урока 1.1.1.

Число соседей — это смещение и разброс

Проверим на двух зашумлённых «полумесяцах» — классическом игрушечном датасете: точки двух классов на плоскости образуют две дуги-«полумесяца», зацепившиеся друг за друга, и прямой их не разделить. 200 точек для обучения, 1000 для теста. Код — в практике.

$k$	Точность на train	Точность на test
1	1.000	0.877
5	0.935	0.897
15	0.925	0.907
51	0.870	0.874
199	0.505	0.461

При $k = 1$ каждая точка — сама себе сосед, на train 100%. Это запоминание, и каждый выброс создаёт вокруг себя «островок» неправильного класса — высокий разброс. При $k = 199$ из 200 модель почти всегда отвечает самым частым классом — высокое смещение. Лучшее $k$ где-то посередине, и выбирают его кросс-валидацией.

Масштаб признаков решает всё

Расстояние складывает разности по всем признакам. Если один признак измеряется в тысячах (площадь в квадратных сантиметрах), а другой в единицах (число комнат), первый полностью определит соседей. Эксперимент (код — в практике): полезный признак порядка 1 и бесполезный шум порядка 1000, $k = 15$.

• Без масштабирования: точность kNN — 0.51, уровень монетки. Соседей выбирает шум.
• После стандартизациистандартизация признаковEN feature standardization (z-score)(x − μ)/σ. Не путайте с нормализацией (normalization) — обычно это min-max масштабирование в [0, 1]; в китайских текстах эти термины иногда смешивают. (вычесть среднее, поделить на стандартное отклонение; статистики считаем только по train): 0.83.

Деревьям, о которых речь дальше, масштаб безразличен: они сравнивают признак с порогом.

Проклятие размерности

Возьмём 1000 случайных точек в единичном кубе (в $d$ измерениях: все $d$ координат — от 0 до 1), ещё одну случайную точку-запрос и посмотрим, во сколько раз самая далёкая от запроса точка дальше самой близкой. Медианы по 200 повторам:

Размерность $d$	2	10	100	1000
max / min расстояния	73	3.8	1.43	1.12

На плоскости ближайший сосед в десятки раз ближе самого далёкого. В 1000 измерениях разница — всего 12%.

В высоких размерностях все точки почти одинаково далеки друг от друга, и понятие «ближайший» теряет смысл. Это проклятие размерностипроклятие размерностиEN curse of dimensionality. Почему же тогда поиск по эмбеддингам размерности 1024 работает в RAG? Реальные данные не разбросаны по пространству равномерно. Обученные эмбеддинги лежат вблизи «поверхностей» малой размерности, где близость осмысленна. А чтобы не считать расстояние до миллионов векторов, используют приближённый поиск ближайших соседей (ANN-индексы, от approximate nearest neighbors) — об одном из них, IVF, в уроке 2.3.2.

Дерево решений

дерево решенийдерево решенийEN decision tree устроено как игра в «20 вопросов» или блок-схема врача. Во внутренних узлах вопросы вида «узор чёткий?» или «площадь ≤ 54 м²?», в листьях — ответы. Чтобы сделать предсказание, идём от корня по ответам до листа: это $O(\text{глубина})$ операций.

Как выбрать вопрос

Найти оптимальное дерево — NP-трудная задача: быстрого точного способа для неё не известно, а перебор всех возможных деревьев занял бы астрономическое время. Поэтому деревья строят жадно: в каждом узле берут лучший вопрос «здесь и сейчас», не заглядывая вперёд. Перебираем все признаки и пороги и выбираем разбиение, после которого дочерние узлы «чище» всего, то есть в каждом из них примеры в основном одного класса. Затем повторяем то же самое в каждом потомке (это рекурсия из урока 0.2.2). Остановка: узел чистый, достигнута максимальная глубина или в узле слишком мало примеров.

Нечистоту узла с долями классов $p_k$ измеряют двумя способами. Доля $p_k$ — какая часть примеров узла относится к классу $k$: в узле из 10 арбузов, где 7 хороших, $p_{\text{хор}} = 0.7$ и $p_{\text{плох}} = 0.3$.

Энтропия из урока 1.3.3: $H = -\sum_k p_k \log_2 p_k$. В чистом узле она равна 0, при равных долях двух классов — 1 (максимум неопределённости). прирост информацииприрост информацииEN information gainКритерий разбиения в алгоритме ID3 — насколько разбиение уменьшает энтропию меток. — насколько разбиение уменьшило энтропию:

$$\mathrm{IG}(D, a) = H(D) - \sum_{v} \frac{|D_v|}{|D|} H(D_v),$$

где $D$ — примеры в узле, $D_v$ — примеры, у которых признак $a$ принял значение $v$, а $|D|$ и $|D_v|$ — их количества. Словами: энтропия до разбиения минус средняя энтропия веток после него, где каждая ветка весит пропорционально числу своих примеров. Это критерий алгоритма ID3. У него есть перекос: признак с уникальным значением у каждого примера (например, номер арбуза) даёт максимальный прирост и бесполезен для предсказания. Алгоритм C4.5 исправляет это нормировкой — отношением прироста (gain ratio).

Индекс Джинииндекс Джини (неопределённость Джини)EN Gini impurityКритерий разбиения в CART. Не путать с коэффициентом Джини из экономики.: $G = 1 - \sum_k p_k^2$ — вероятность, что два примера, случайно вытянутых из узла с возвращением (вытянули, посмотрели, вернули обратно и тянем снова), окажутся разных классов. В узле «5 хороших, 5 плохих» $G = 1 - 0.5^2 - 0.5^2 = 0.5$ — максимум для двух классов, в чистом узле $G = 0$. Его использует CART, который строит только бинарные разбиения. Считается быстрее энтропии (нет логарифма), а на практике оба критерия выбирают почти одинаковые деревья.

Пример: арбузы из «Арбузной книги»

В датасете «Арбузы 2.0» из учебника Чжоу Чжихуа 17 арбузов: 8 хороших и 9 плохих. Энтропия корня:

$$H(D) = -\tfrac{8}{17}\log_2\tfrac{8}{17} - \tfrac{9}{17}\log_2\tfrac{9}{17} \approx 0.998 .$$

Попробуем разбить по признаку «узор». Чёткий узор у 9 арбузов (7 хороших), слегка размытый у 5 (1 хороший), размытый у 3 (ни одного хорошего). Энтропия ветки «чёткий»: $-\tfrac{7}{9}\log_2\tfrac{7}{9} - \tfrac{2}{9}\log_2\tfrac{2}{9} \approx 0.282 + 0.482 = 0.764$. Так же для «слегка размытого» ($\tfrac{1}{5}$ и $\tfrac{4}{5}$) получается 0.722, а чистая ветка «размытый» даёт 0. Взвешиваем по размерам веток и вычитаем из энтропии корня:

$$\mathrm{IG} = 0.998 - \Big(\tfrac{9}{17}\cdot 0.764 + \tfrac{5}{17}\cdot 0.722 + \tfrac{3}{17}\cdot 0\Big) \approx 0.381 .$$

То же для всех шести признаков:

Признак	окраска	хвостик	звук	узор	«пупок»	на ощупь
Прирост информации	0.108	0.143	0.141	0.381	0.289	0.006

Корнем становится «узор». Критерий Джини (CART) выбирает тот же признак: разбиение «узор чёткий / не чёткий» даёт взвешенный Джини 0.286 — минимум среди всех вариантов. А вот «на ощупь» почти ничего не говорит о спелости: прирост 0.006. Если сверяетесь с «Арбузной книгой»: там у окраски 0.109, потому что промежуточные значения округлены до трёх знаков.

flowchart TD
R["17 арбузов<br/>8 хороших, 9 плохих<br/>H = 0.998"] -->|"узор = чёткий"| A["9 арбузов<br/>7 хороших<br/>H = 0.764 → делим дальше"]
R -->|"узор = слегка размытый"| B["5 арбузов<br/>1 хороший<br/>H = 0.722 → делим дальше"]
R -->|"узор = размытый"| C["3 арбуза<br/>0 хороших<br/>лист: «плохой»"]

Первое разбиение дерева ID3 на датасете арбузов из «Арбузной книги»

Числовые признаки разбивают порогом. Сортируем значения и пробуем пороги посередине между соседними различными значениями. Это вы реализуете в задании. Регрессионное дерево отвечает в листе средним значением, а разбиения выбирает по уменьшению MSE.

Сильные и слабые стороны

Плюсы	Минусы
Интерпретируемость: дерево можно прочитать	Ответ кусочно-постоянный, тренд за пределы обучающих данных не продолжит
Масштабирование признаков не нужно	Нестабильность: чуть другие данные — другое дерево (высокий разброс)
Смешанные типы признаков и пропуски	Глубокое дерево переобучается: по примеру на лист — и на train 100%
Само находит взаимодействия признаков	Границы только «параллельно осям»

Регуляризация дерева — ограничения на глубину и размер листа и обрезка (prune). В «Арбузной книге» её называют буквально «подрезкой ветвей», как в садоводстве. Но главное лекарство от нестабильности — не одно дерево, а много.

Ансамбли: мудрость толпы

Пусть у нас $n$ классификаторов, каждый прав с вероятностью 0.6, и они ошибаются независимо. Ансамбль отвечает то, за что проголосовало большинство. Ошибётся он, только если ошиблось больше половины моделей сразу, а при независимых ошибках это всё менее вероятно с ростом $n$. Точность голосования большинством (посчитана по биномиальному распределению из урока 1.3.1 — числу «успехов» в $n$ независимых попытках):

Моделей в ансамбле	1	5	11	25	101
Точность большинства	0.600	0.683	0.753	0.846	0.979

Главное слово — «независимо». Модели, обученные на одних и тех же данных, ошибаются похоже, и выигрыш намного скромнее. Вся наука ансамблейансамблевое обучение, ансамбль моделейEN ensemble learning — как сделать модели разными. Два главных подхода противоположны.

Бэггинг и случайный лес

Бэггинг (bootstrap aggregating) обучает каждую модель на своей бутстрэп-выборкебутстрэп (выборка с возвращением)EN bootstrap samplingОснова бэггинга (bagging) и случайного леса.: $n$ примеров, вытянутых с возвращением из $n$ исходных. В каждую попадает около $1 - 1/e \approx 63.2\%$ уникальных примеров. Остальные 36.8% (out-of-bag) служат бесплатной валидацией для этой модели.

Почему усреднение помогает? Интуиция: случайные промахи разных деревьев в разные стороны при усреднении частично гасят друг друга. (Для любознательных — точная формула.) Если у каждой из $B$ моделей разброс $\sigma^2$, а попарная корреляция ошибок $\rho$ («ро»: 0 — модели ошибаются независимо, 1 — ошибаются одинаково), то разброс среднего

$$\mathrm{Var}\Big(\frac{1}{B}\sum_{b=1}^{B} \hat f_b\Big) = \rho\,\sigma^2 + \frac{1-\rho}{B}\,\sigma^2 .$$

Пример: $\sigma^2 = 1$, $\rho = 0.3$, $B = 100$ деревьев. Разброс среднего $0.3 + 0.7 / 100 = 0.307$ — втрое меньше, чем у одного дерева, но не меньше 0.3, сколько деревьев ни добавляй. Второе слагаемое гасится числом деревьев. Первое — только снижением корреляции. случайный лесслучайный лесEN random forest (Брейман, 2001) добавляет вторую случайность: в каждом узле дерево выбирает разбиение лишь среди случайного подмножества признаков (для классификации обычно $\sqrt{d}$ из $d$). Деревья становятся непохожими, $\rho$ падает.

Деревья в лесу глубокие: у каждого низкое смещение и высокий разброс, а усреднение убирает разброс. Лес почти не переобучается от добавления деревьев, легко параллелится и хорошо работает «из коробки».

Градиентный бустинг

Бустинг устроен наоборот: модели учатся последовательно, и каждая новая исправляет ошибки уже построенного ансамбля. Обозначим $F_m(x)$ предсказание ансамбля из первых $m$ деревьев. Начинаем с константы $F_0$ (например, среднего $y$), затем на шаге $m$:

1. считаем остатки $r_i = y_i - F_{m-1}(x_i)$ — насколько ансамбль пока ошибается на каждом примере;
2. учим неглубокое дерево $h_m$ предсказывать остатки;
3. обновляем ансамбль: $F_m(x) = F_{m-1}(x) + \nu \cdot h_m(x)$, где $\nu$ («ню») — скорость обучения (обычно 0.01–0.3).

На числах. Квартира стоит $y = 5$ млн ₽, стартовый прогноз $F_0 = 3$, остаток $5 - 3 = 2$. Пусть первое дерево выучило остаток точно: $h_1 = 2$. При $\nu = 0.1$ новый прогноз $F_1 = 3 + 0.1 \cdot 2 = 3.2$. Остаток стал 1.8, следующее дерево снова сдвинет прогноз на десятую часть, и так шаг за шагом прогноз подползает к 5. Маленький $\nu$ — как маленький learning rate: медленнее, но надёжнее.

Почему «градиентный»? Для потерь $L = \frac{1}{2}(y - F)^2$ производная по предсказанию $F$ равна $F - y$, значит, остатки $y - F$ — это антиградиент, то есть градиент со знаком минус: направление, в котором loss убывает быстрее всего (урок 1.2.3). Каждое дерево делает шаг градиентного спуска, только не в пространстве весов, а в пространстве функций (Фридман, 2001). Для других функций потерь (log-loss — бинарная cross-entropy из урока 2.2.2, функции для ранжирования) дерево учится на соответствующий антиградиент.

Деревья в бустинге мелкие (глубина 3–8): каждое по отдельности сильно смещено, а сумма сотен деревьев смещение снимает. Обратная сторона — бустинг переобучается, если добавить слишком много деревьев. Число деревьев выбирают ранней остановкой по валидации из урока 2.1.2. Бустинг из «пней» (деревьев глубины 1) на синусоиде с шумом $\sigma^2 = 0.04$:

Деревьев	1	10	50	100	300
MSE на train	0.422	0.158	0.065	0.044	0.032
MSE на test	0.477	0.183	0.080	0.057	0.046

	Бэггинг / случайный лес	Градиентный бустинг
Обучение	параллельно, независимо	последовательно, каждое дерево исправляет предыдущие
Базовые деревья	глубокие (низкое смещение)	мелкие (низкий разброс)
Что уменьшает	разброс	смещение
Много деревьев	не вредит	переобучает — нужна ранняя остановка
Настройка	почти не нужна	важны $\nu$, глубина, число деревьев

Три главные библиотеки

Технические подробности ниже можно не запоминать: важно знать три названия и то, что у CatBoost российские корни. Как бустинг устроен изнутри — log-loss и шаг Ньютона, регуляризованная цель XGBoost, гиперпараметры LightGBM, важность признаков и SHAP — подробно в уроке 2.4.3.

• XGBoost (Тяньци Чэнь и Карлос Гестрин, статья 2016 года). Регуляризованная цель с учётом вторых производных, поддержка разреженных данных (где большинство значений — нули или пропуски), быстрая реализация. По данным авторов, из 29 решений-победителей Kaggle (платформы соревнований по ML), опубликованных в 2015 году, 17 использовали XGBoost.
• LightGBM (Microsoft Research Asia, NeurIPS 2017). Гистограммы вместо перебора всех порогов, рост дерева «по листьям» и приёмы ускорения GOSS и EFB. Обучается заметно быстрее на больших данных.
• CatBoost (Яндекс, открыт в 2017). Умеет работать с категориальными признаками (город, марка автомобиля) без ручного кодирования. Категорию заменяет средним значением целевой переменной по ней, но для каждого примера считает это среднее только по «предыдущим» примерам в случайной перестановке (ordered target statistics). Тот же принцип в ordered boosting: остаток для примера вычисляется моделью, которая этот пример не видела. Оба приёма защищают от утечки целевой переменной, той самой из урока 2.1.2. Использует симметричные (oblivious) деревья: на каждом уровне один и тот же вопрос, поэтому предсказание очень быстрое. Хорошие настройки по умолчанию.

Как это выглядит в работе

Набросок для знакомства, запускать его сейчас не нужно: для него нужны библиотека catboost и таблицы pandas — библиотеки для таблиц, которую мы разберём в уроке 2.4.1.

from catboost import CatBoostClassifier   # pip install catboost

# X_train, X_val — таблицы pandas, среди столбцов есть категориальные "city" и "tariff"
model = CatBoostClassifier(iterations=1000, learning_rate=0.05, depth=6,
                           cat_features=["city", "tariff"], verbose=200)
model.fit(X_train, y_train, eval_set=(X_val, y_val), early_stopping_rounds=100)

Обратите внимание на eval_set и early_stopping_rounds: та самая ранняя остановка по валидации.

На соревнованиях из этих идей собирают финальное решение: в ансамбль берут разные модели, а веса смеси подбирают на out-of-fold-предсказаниях — прогнозах для фолдов кросс-валидации, которых модель не видела при обучении. Как это делают — в уроке 11.4.3.

Когда классика лучше нейросетей

Лео Гринштайн и соавторы (2022) сравнили деревья и нейросети на 45 табличных датасетах. На данных среднего размера (порядка 10 тысяч строк) лучшими остались модели на деревьях: XGBoost и случайный лес. Причины, по мнению авторов, в индуктивных смещенияхиндуктивное смещение (априорные предпочтения модели)EN inductive biasКакие решения модель «предпочитает» при прочих равных. В «арбузной книге» Чжоу Чжихуа — «индуктивное предпочтение». — встроенных «предпочтениях» модели, то есть в том, какие закономерности ей выучить легко, а какие трудно (то же, что «пространство гипотез» из урока 2.1.1):

• нейросети тяготеют к гладким функциям, а целевая переменная в таблицах часто меняется скачками («льгота с 65 лет»);
• нейросети страдают от бесполезных признаков, а дерево их просто не выберет;
• столбцы таблицы осмысленны по отдельности, а нейросеть их «перемешивает». Деревья работают с каждым признаком отдельно, вдоль осей.

Данные	Что брать первым
Таблицатабличные данныеEN tabular data, до сотен тысяч строк, разнородные признаки	градиентный бустинг (CatBoost, LightGBM, XGBoost)
Изображения, звук, текст	нейросеть, обычно предобученная
Таблица + текстовые поля	эмбеддинги текста от языковой модели как признаки для бустинга
Очень мало данных (сотни строк)	простые модели, сильная регуляризация, кросс-валидация
Нужно объяснить решение регулятору	дерево, линейная модель или бустинг с анализом важности признаков

Фронтир сдвигается. Появились табличные foundation-модели (большие предобученные модели общего назначения, как LLM для текста), обученные на миллионах синтетических таблиц, например TabPFN (публикация в Nature, 2025). На маленьких таблицах они конкурируют с бустингом без настройки. Но бейзлайн для таблицы в 2026 году по-прежнему — градиентный бустинг.

Практика

Задание: Джини, лучший порог и kNN

Реализуйте на чистом Python три кирпича этого урока: индекс Джини, поиск лучшего порога для числового признака и предсказание kNN. NumPy здесь не нужен. Пригодятся Counter из урока 0.2.4 (считает, сколько раз встречается каждый элемент), sorted и zip из урока 0.2.2 и math.dist(p, q) — готовое евклидово расстояние между двумя точками.

Порог для числового признака ищут так. Пусть $x = 1, 2, 3, 10, 11, 12$, а метки $0, 0, 0, 1, 1, 1$. Кандидаты — середины между соседними значениями: 1.5, 2.5, 6.5, 10.5, 11.5. Порог 6.5 делит данные на «$x \le 6.5$» (три нуля) и «$x > 6.5$» (три единицы): оба узла чистые, взвешенный Джини 0. Это лучший порог. А порог 2.5 даёт слева $\{0, 0\}$ (Джини 0) и справа $\{0, 1, 1, 1\}$ (Джини $1 - 0.25^2 - 0.75^2 = 0.375$), взвешенно $\frac{2}{6} \cdot 0 + \frac{4}{6} \cdot 0.375 = 0.25$ — хуже.

Индекс Джини, лучший порог и kNN7 тестов

import math
from collections import Counter


def gini(labels):
    """Индекс Джини: 1 − Σ p_k², где p_k — доля класса k. Для пустого списка — 0.

    gini([0, 0, 1, 1]) → 0.5;  gini(['a', 'a']) → 0.0
    """
    # TODO: ваш код (подсказка: Counter(labels) считает, сколько раз встречается каждый класс)
    ...


def best_split(xs, ys):
    """Лучший порог t для одного числового признака по взвешенному Джини.

    Левая часть: x <= t, правая: x > t. Кандидаты — середины между соседними
    РАЗЛИЧНЫМИ значениями отсортированного xs. Взвешенный Джини:
        n_left / n · gini(left) + n_right / n · gini(right).
    Возвращает (t, взвешенный_джини). Если у нескольких порогов Джини одинаков, верните
    меньший порог. Если делить нечего (все x равны) — (None, gini(ys)).
    """
    # TODO: ваш код
    ...


def knn_predict(train_X, train_y, x, k):
    """Класс точки x голосованием k ближайших соседей (евклидово расстояние).

    train_X — список точек (кортежей чисел), train_y — их классы (любые значения).
    При равенстве голосов побеждает класс, который встречается раньше среди
    отсортированных по расстоянию соседей (то есть более близкий).
    """
    # TODO: ваш код (math.dist(p, q) — евклидово расстояние)
    ...


# «Запустить»: ожидаемые ответы — в комментариях справа; None значит «функция ещё не дописана»
print("Джини корня:", gini(["хороший"] * 8 + ["плохой"] * 9))          # ≈ 0.498
print("Лучший порог:", best_split([1, 2, 3, 10, 11, 12], [0, 0, 0, 1, 1, 1]))  # (6.5, 0.0)
print("kNN:", knn_predict([(0, 0), (1, 0), (5, 5), (6, 5)], ["A", "A", "B", "B"], (0.4, 0.2), k=3))  # A

ЗапуститьПроверитьПодсказкаСбросить

kNN и бустинг на NumPy

Запустите локально — это эксперименты из таблиц урока. Здесь kNN написан на NumPy без циклов: все расстояния считаются разом через broadcasting, как попарные расстояния в уроке 0.3.2. Как устроена функция make_moons, можно не вникать: она просто рисует два зашумлённых полумесяца.

import numpy as np

rng = np.random.default_rng(0)

def make_moons(n, noise, rng):
    """Два «полумесяца» — классический игрушечный датасет (детали генерации не важны)."""
    t = rng.uniform(0, np.pi, n)                         # положение точки вдоль дуги
    y = rng.integers(0, 2, n)                            # класс 0 или 1
    x1 = np.where(y == 0, np.cos(t), 1 - np.cos(t))      # класс 0 — верхняя дуга, класс 1 — нижняя
    x2 = np.where(y == 0, np.sin(t), 0.5 - np.sin(t))
    X = np.c_[x1, x2] + rng.normal(0, noise, (n, 2))     # склеиваем координаты и добавляем шум
    return X, y

def knn_predict(X_tr, y_tr, X, k):
    """kNN для двух классов 0/1: голосуют k ближайших обучающих точек."""
    d = ((X[:, None, :] - X_tr[None, :, :]) ** 2).sum(-1)   # (n_query, n_train) квадраты расстояний
    nearest = np.argsort(d, axis=1)[:, :k]                  # в каждой строке — номера k ближайших соседей
    votes = y_tr[nearest].mean(1)                            # доля соседей класса 1
    return (votes > 0.5).astype(int)                         # больше половины голосов за 1 → класс 1

X_tr, y_tr = make_moons(200, 0.3, rng)
X_te, y_te = make_moons(1000, 0.3, rng)
for k in [1, 5, 15, 51, 199]:
    acc_tr = (knn_predict(X_tr, y_tr, X_tr, k) == y_tr).mean()   # точность на самих обучающих точках
    acc_te = (knn_predict(X_tr, y_tr, X_te, k) == y_te).mean()   # точность на новых точках
    print(f"k = {k:3d}: train {acc_tr:.3f}   test {acc_te:.3f}")

k =   1: train 1.000   test 0.877
k =   5: train 0.935   test 0.897
k =  15: train 0.925   test 0.907
k =  51: train 0.870   test 0.874
k = 199: train 0.505   test 0.461

Эксперимент с масштабом признаков — допишите в конец того же скрипта (функция knn_predict уже определена):

def make_scaled(n, rng):
    y = rng.integers(0, 2, n)
    useful = y + rng.normal(0, 0.5, n)        # полезный признак: порядка 1
    junk = rng.normal(0, 1000, n)             # бесполезный шум: порядка 1000
    return np.c_[useful, junk], y

rng = np.random.default_rng(1)
X_tr, y_tr = make_scaled(200, rng)
X_te, y_te = make_scaled(1000, rng)
acc_raw = (knn_predict(X_tr, y_tr, X_te, 15) == y_te).mean()
mu, sd = X_tr.mean(0), X_tr.std(0)            # статистики — только по train!
acc_std = (knn_predict((X_tr - mu) / sd, y_tr, (X_te - mu) / sd, 15) == y_te).mean()
print(f"без масштабирования: {acc_raw:.3f}   после стандартизации: {acc_std:.3f}")

без масштабирования: 0.510   после стандартизации: 0.827

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

Градиентный бустинг из «пней» — меньше 40 строк. «Пень» — дерево с одним-единственным вопросом «$x \le t$?» и двумя листьями. В каждом листе он отвечает средним значением целей, попавших туда (так устроено регрессионное дерево), а порог $t$ выбирает тем же перебором середин, что и в задании выше, только по MSE вместо Джини.

import numpy as np

def fit_stump(x, r):
    """Лучший «пень» (дерево глубины 1) для 1D-признака x и целей r по MSE."""
    order = np.argsort(x)                    # сортируем точки по x
    xs, rs = x[order], r[order]
    best = (np.inf, None, None, None)        # (ошибка, порог, ответ слева, ответ справа)
    for i in range(1, len(xs)):              # пробуем порог между точками i-1 и i
        if xs[i] == xs[i - 1]:
            continue                         # между равными x порог не поставить
        left, right = rs[:i], rs[i:]
        # сумма квадратов ошибок, если в каждом листе отвечать средним своих целей
        sse = ((left - left.mean()) ** 2).sum() + ((right - right.mean()) ** 2).sum()
        if sse < best[0]:
            best = (sse, (xs[i - 1] + xs[i]) / 2, left.mean(), right.mean())
    _, t, a, b = best
    return lambda z: np.where(z <= t, a, b)  # готовый «пень» как функция: слева ответ a, справа b

rng = np.random.default_rng(0)
x_tr = rng.uniform(0, 1, 200); y_tr = np.sin(2 * np.pi * x_tr) + rng.normal(0, 0.2, 200)
x_te = rng.uniform(0, 1, 1000); y_te = np.sin(2 * np.pi * x_te) + rng.normal(0, 0.2, 1000)

lr = 0.1
F_tr = np.full_like(y_tr, y_tr.mean())      # шаг 0: константа — среднее
F_te = np.full_like(y_te, y_tr.mean())
for m in range(1, 301):
    residual = y_tr - F_tr                  # антиградиент MSE = остатки
    h = fit_stump(x_tr, residual)           # новое дерево учится на ошибках ансамбля
    F_tr += lr * h(x_tr)
    F_te += lr * h(x_te)
    if m in (1, 10, 50, 100, 300):
        print(f"деревьев {m:3d}: train MSE {np.mean((y_tr - F_tr)**2):.3f}   test MSE {np.mean((y_te - F_te)**2):.3f}")

деревьев   1: train MSE 0.422   test MSE 0.477
деревьев  10: train MSE 0.158   test MSE 0.183
деревьев  50: train MSE 0.065   test MSE 0.080
деревьев 100: train MSE 0.044   test MSE 0.057
деревьев 300: train MSE 0.032   test MSE 0.046

Попробуйте lr = 1.0 и lr = 0.01. При большом шаге ансамбль быстрее подгоняет train, но и быстрее начинает переобучаться. При маленьком нужно больше деревьев. Это тот же компромисс, что и learning rate в нейросетях.

Китайский угол: две из трёх библиотек бустинга — с китайскими корнями

Три главные библиотеки градиентного бустинга — российская и две с китайскими корнями.

XGBoost начал Чэнь Тяньци (Tianqi Chen). Он учился в ACM-классе Шанхайского университета Цзяотун, затем защитил PhD в Вашингтонском университете. Проект вырос в сообществе DMLC (github.com/dmlc/xgboost), статья вышла в 2016 году (arXiv:1603.02754). Чэнь — один из инициаторов фреймворка MXNet и компилятора нейросетей TVM, с 2020 года преподаёт в Университете Карнеги — Меллона. LightGBM создан в Microsoft Research Asia в Пекине, статья (первый автор — Кэ Голинь) вышла на NeurIPS 2017. Третья библиотека, CatBoost, — разработка Яндекса.

Учебники. В «Арбузной книге» Чжоу Чжихуа деревьям посвящена глава 4 «Деревья решений» с теми самыми арбузами, ансамблям — глава 8 «Ансамблевое обучение» (Boosting, Bagging, случайный лес), а kNN открывает главу 10 «Понижение размерности и обучение метрик». В «Тыквенной книге» (Datawhale) по шагам разобрано построение CART на датасете «Арбузы 2.0»: индекс Джини для разбиения «узор = чёткий» равен 0.286, это минимум, отсюда корень дерева. У Ли Хана в «Методах статистического обучения» kNN — глава 3, деревья — глава 5, бустинг — глава 8 «Методы бустинга».

Глубокий лес. Сам Чжоу Чжихуа (Нанкинский университет) в 2017 году предложил Deep Forest (gcForest, arXiv:1702.08835, IJCAI 2017) — каскад ансамблей деревьев как альтернативу глубоким нейросетям. Идея: повторить три свойства, которые, по гипотезе авторов, делают глубокое обучение успешным, — послойную обработку, преобразование признаков внутри модели и достаточную сложность, — но без градиентов и с гораздо меньшим числом гиперпараметров. Нейросети deep forest не вытеснил, но это хороший пример исследовательского вопроса: обязательно ли «глубокое» значит «нейросетевое»?

Проверь себя

Проверь себя6 вопросов·

1 kNN с $k = 1$ даёт 100% точности на train и 82% на test. Как, скорее всего, изменится картина при $k = 15$?

Train вырастет, test упадётTrain упадёт, test, вероятно, вырастет: модель меньше подстраивается под шумНичего не изменится: $k$ влияет только на скоростьОбе точности упадут до 50%

2 В узле 6 примеров класса A и 2 примера класса B. Чему равен индекс Джини? Округлите до трёх знаков.

3 Какие утверждения верны?Можно выбрать несколько ответов

Случайный лес в основном уменьшает разброс, градиентный бустинг — смещениеДеревьям решений нужна стандартизация признаковВ градиентном бустинге с MSE каждое новое дерево учится на остатки $y - F(x)$В случайном лесу добавление деревьев почти не приводит к переобучениюБустинг невозможно переобучить

4 Почему kNN плохо работает на 1000 «сырых» случайных признаках?

Не хватает памятиВ высокой размерности расстояния до всех точек почти одинаковы, и «ближайший сосед» теряет смыслkNN работает только в двумерном пространствеЕвклидово расстояние нельзя посчитать в 1000 измерениях

5 Вы делаете бутстрэп-выборку размера $n$ из $n$ примеров. Какая доля исходных примеров в неё НЕ попадёт при большом $n$? Округлите до двух знаков.

6 Нужно предсказать отток клиентов по таблице из 50 тысяч строк и 40 столбцов (числа, город, тариф). Что разумнее попробовать первым?

Дообучить LLM на строках таблицы, переведённых в текстГрадиентный бустинг (например, CatBoost) с ранней остановкой по валидацииСвёрточную нейросетьkNN без масштабирования признаков

Проверить ответы

Итоги

• kNN голосует ближайшими соседями: малое $k$ — разброс, большое — смещение. Масштабируйте признаки и помните о проклятии размерности.
• Дерево решений жадно выбирает вопросы, сильнее всего уменьшающие энтропию (ID3, C4.5) или индекс Джини (CART). На арбузах из «Арбузной книги» корнем становится «узор» с приростом 0.381.
• Случайный лес усредняет глубокие деревья на бутстрэп-выборках со случайными признаками и уменьшает разброс. Градиентный бустинг складывает мелкие деревья, обученные на антиградиент, и уменьшает смещение.
• XGBoost, LightGBM и CatBoost — стандарт для табличных данных. Нейросети выигрывают на изображениях, звуке и тексте.

Дальше: обучение без учителя — k-means, метод главных компонент и то, как увидеть облако эмбеддингов на плоскости.