Знание классики - база любых собеседований на все грейды в DS!

Этот материал не рассчитан на изучение тем с нуля. Это чеклист и тренажёр, по которому стоит пройтись перед техническим интервью по классическому ML. Кратко, по делу, с акцентом на то, что действительно спрашивают.

Это вторая часть вопросов по classic ML, если вы не видели первую, то обязательно читайте (там разобрал основы мл, линейные модели, метрики классификации и регресии).

А в этой части разберем:

• деревья

• ансамбли

• метрические модели

• кластеризацию

Параллельно доступно видеоинтервью с разбором тех же вопросов — обязательно смотрите и закрепляйте материал.

В Telegram-канале — регулярный контент по ML и DL, а на Boosty — разборы реальных собеседований.

Подписывайтесь, в следующих частях будем разбирать NLP и LLM - самые востребованные области в ML.

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

Как выглядит жадный алгоритм построения решающего дерева?

Алгоритм:

• Начинаем с корня — берём весь обучающий датасет

• Выбираем лучший признак и значение для сплита (критерия ветвления)

• Разбиваем данные на две части по этому сплиту

• Повторяем шаги для каждой части — рекурсивно строим поддеревья

• Останавливаемся, если выполнен критерий остановки; тогда вершина становится листом

Критерии ветвления:

• gini или entropy - классификация

• mse или mae - регрессия

Критерий остановки:

• достигнута максимальная глубина

• в узле мало или много объектов

• прирост информации от нового сплита слишком мал

Какие есть критерии сплиттинга?

Gini

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

где p_i - доля i-го класса в листе.

Особенности:

• Быстро считается.

• Часто используется по умолчанию (например, в DecisionTreeClassifier из sklearn).

Entropy

Интуиция: мера "неопределённости" или "хаоса" — насколько непредсказуемо распределение классов.

где p_i - доля i-го класса в листе.

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

В чём разница между классификацией и регрессией в деревьях?

Классификация:

• предсказываем метки классов

• Используем gini или энтропию

• самый популярный класс по объектам в листе (мода)

Регрессия:

• предсказываем числовое значение

• Оптимизируем mse/mae во время сплита

• Используем среднее / медиану в листе как предсказание

Какие есть плюсы и минусы решающего дерева?

Плюсы:

• Хорошо работают с нелинейными зависимостями

• Интерпретируемость: легко объяснить, почему модель приняла решение

• Работает с категориальными и числовыми признаками

• Не требует нормализации данных

Минусы:

• Легко переобучается, особенно при большой глубине

• Плохо работает с трендами, так как не умеют экстраполировать

• Очень чувствительны к гиперпараметрам

Сможет ли дерево предсказать значение меньше нуля, если оно обучалось на положительных таргетах?

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

Почему деревья не чувствительны к масштабированию признаков?

Потому что они не используют расстояния. Сплиты происходят по порогам типа: "если x > 3, то идти влево", и не важно, в каком масштабе заданы значения — хоть в сантиметрах, хоть в метрах.

Как оценить важность признаков по дереву?

Обычно важность признака измеряется как суммарное снижение impurity (Gini или энтропии), которое произошло благодаря разбиениям по этому признаку, по всем уровням дерева.

В ансамблях деревьев (например, в Random Forest) эти значения усредняются по всем деревьям.

Как глубина влияет на дерево?

Маленькая глубина → недообучение (underfitting): модель слишком простая, плохо захватывает зависимости.

Слишком большая глубина → переобучение (overfitting): модель подстраивается под шум в данных, плохо обобщает. Крайний случай, например, когда дерево поместила каждый объект обучающей выборки в отдельный лист, в таком случае у нас идеальные метрики на трейне и очень плохие на тесте.

Обычно глубина дерева — один из основных гиперпараметров для настройки

Как можно регуляризировать решающее дерево?

• Ограничить максимальную глубину дерева (max_depth)

• Задать минимальное количество объектов в узле (min_samples_split, min_samples_leaf)

• Ограничить максимальное число признаков для выбора сплита (max_features)

• Использовать pruning (обрезку лишних веток после обучения)

• max_leaf_nodes — ограничивает общее число листьев в дереве

• min_impurity_decrease - минимальный прирост критерия сплита

Ансамбли

Что такое бэггинг?

Бэггинг (Bagging) — это метод ансамблирования, в котором используется несколько одинаковых моделей, обученных на разных случайных подмножествах обучающих данных. Модели обучаются параллельно, а затем их прогнозы усредняются (для регрессии) или берётся мода (для классификации), чтобы получить итоговое решение.

Что такое случайные лес? Где там случайность?

Случайный лес (Random Forest) — это ансамбль решающих деревьев, построенных на случайных подмножествах данных и признаков. Случайность здесь проявляется как в процессе бутстрэппинга (создание случайных подмножеств данных), так и в случайном выборе подмножества признаков на каждом сплите дерева.

Что такое бустинг?

Бустинг — это метод ансамблирования, в котором модели обучаются последовательно. Каждая последующая модель пытается исправить ошибки предыдущих. Например, слабые модели (например, слабые деревья) обучаются на ошибках предыдущих моделей, усиливая их предсказания на тяжёлых объектах.

Почему нельзя в качестве базовых алгоритмов использовать линейные модели, например?

Потому что будет линейная комбинация линейных моделей - это бессмысленно, будет просто та же самая линейная комбинация.

Почему градиентный бустинг называется градиентным? Где там градиент?

Когда мы говорим, что обучаемся на ошибках предыдущих моделей, мы:

• Мы фиксируем функцию потерь. Она зависит от целевых значений и от текущей композиции
  L(y, F(x))

• Добавляя новый базовых алгоритм в наш ансамбль / композицию, хотим минимизировать функцию потерь

• Для этого можем посчитать градиент этой функции потерь

• И обучать следующее дерево на антиградиент

Таким образом мы обучаемся на ошибках, но не совсем на остатках (разницы между предсказанием и таргетом), а на значение антиградиента, что, например, для функции потерь mse одно и то же.

Что такое стекинг?

Стекинг (Stacking) — это метод ансамблирования, при котором несколько моделей обучаются на исходных данных, а затем их предсказания используются как входные данные для мета-модели (вторичного уровня). Мета-модель учится на прогнозах базовых моделей и даёт итоговое предсказание.

Как делать трейн/тест сплит для стекинга?

Для стекинга важен out-of-fold split. Каждый базовый классификатор обучается на части данных (например, с использованием кросс-валидации), а затем делает предсказания на оставшихся данных, которые не использовались в обучении. Эти предсказания (out-of-fold) используются для тренировки мета-модели.

Часто делают кросс-валидацию, чтобы в итоге обучаться на всех данных.

Что такое bias-variance decomposition? Какой тип ансамблирования, что оптимизирует?

Bias-Variance Decomposition — это концепция, которая помогает понять, как ошибки модели можно разделить на две основные составляющие:

• Bias (смещение) — ошибка, возникающая, когда модель слишком простая и не может захватить все закономерности в данных. Это приводит к систематической ошибке в предсказаниях.

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

• Noise (шум) — это неизбежная ошибка, которая не может быть уменьшена ни с помощью улучшения модели, ни с помощью большого объёма данных.

Полная ошибка модели может быть разложена на три части:

Бэггинг - уменьшает вариенс (в столько раз, сколько базовых алгоритмов в теории) и уже обладает низким смещением.

Бустинг имеет низкий вариенс и уменьшает смещение.

Стекинг явно ничего из этого не призван минимизировать.

Почему в Random Forest при выборе признаков на каждом сплите используют случайное подмножество признаков?

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

С точки зрения bias-variance decomposition мы хотим строить максимально разнообразные деревья и как можно больше их. То есть мы строим экспертов в своей области (по подмножеству данных и признаков), а потом их усредняем.

Да и просто с точки зрения логики - зачем нам строить одинаковые деревья?)

Где деревья глубже бустинг/бэггинг?

• В бэггинге обычно деревья глубже, а бустинге с ограничением, чтобы не переобучаться.

• Если в бустинге в какой-то момент будет переобучение - вырулить из этого никак не получится.

• А в бэггинге даже если будет несколько переобученных деревьев, эффект от них может быть некритичным, так как мы берем несколько алгоритмов и усредняем их предсказаниях.

Что если сделать первое дерево очень глубоким в бэггинге/бустинге?

В бэггинге:

Если первое дерево очень глубокое, оно будет склонно к переобучению на обучающих данных, так как оно будет слишком подстраиваться под шум и выбросы в данных. Однако, поскольку в бэггинге используются ансамбли деревьев, остальные деревья будут обучаться на других подмножествах данных, и, возможно, это частично уменьшит влияние переобучения первого дерева. Но в целом такое дерево может немного ухудшить стабильность ансамбля (на сколько сильно - зависит от общего числа деревьев).

В бустинге:

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

Что если убрать первое дерево в бэггинге/устинге?

В бэггинге:

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

В бустинге:

Если удалить первое дерево в бустинге, это сломает всю последовательность обучения, так как каждое следующее дерево пытается исправить ошибки предыдущего. Без первого дерева у модели не будет фундамента для исправления ошибок. Это нарушает основной принцип бустинга, и результат будет сильно хуже.

Можно ли переобучить бустинг? а бэггинг?

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

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

В чем отличия LightGBM, XGBoost, CatBoost?

В основном в форме деревьев.

LightGBM

• На каждом шаге выбираем вершину для ветвления с наилучшим скором

• Дерево получается несимметричным

• В этом алгоритме быстро подстраиваемся под трейн данные, поэтому можно быстрее переобучиться

• Основной критерий остановки - максимальная глубина

XGBoost

• Строим дерево последовательно по уровням до достижения максимальной глубины

• Дерево получается симметричным, а иногда и бинарным

• Такому алгоритму тяжелее переобучиться, чем LightGBM

CatBoost

• Все вершини одного уровня имеют одинаковых предикат (см картинку ниже). предикат = условие ветвления

• Такое жесткое ограничение является сильным регуляризатором

• Также из-за отсутствия вложенных if-else ускоряется инференс дерева

Как распараллелить обучение бэггинга и бустинга

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

В бустинге деревья строятся последовательно, так как каждое новое дерево исправляет ошибки предыдущего. Поэтому распараллелить обучение по деревьям нельзя.
Однако современные библиотеки реализуют внутреннюю параллелизацию — внутри одного дерева:

• по узлам

• при поиске сплитов

• при вычислении градиентов

Как распараллелить инференс бэггинга и бустинга

В бэггинге всё просто - модели независимы, поэтому инференс можно распараллелить по деревьям и затем усреднить/проголосовать результаты.

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

Метрические модели

Что такое метрические модели?

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

Основная идея, Если два объекта «близки» друг к другу по признаковому пространству (то есть расстояние между ними мало), то их целевые значения тоже должны быть похожи.

Как работает k-nn?

1. Обучение:

• Обучения как такового нет.

• Модель просто запоминает все обучающие объекты и их метки классов (или значения, если это регрессия). 

• Чтобы классифицировать новый объект, модель ищет k ближайших объектов в обучающей выборке и голосует по их меткам.

• Для регрессии — берется среднее значение у k ближайших соседей.

2. Предсказание:

Когда приходит новый объект, происходит следующее:

1. Вычисляется расстояние до всех объектов из обучающей выборки
   
   — обычно Евклидово, но может быть любое (манхэттенское, косинусное и т.п.)

2. Выбираются k ближайших соседей

3. Классификация:

   • Класс — тот, за который проголосовало большинство соседей (majority vote)

   • Можно взвешивать по расстоянию: ближние — весомее

4. Регрессия:

   • Предсказывается среднее значение по соседям

   • Или взвешенное среднее (опять же — ближние весомее)

Какое у knn время обучения и предсказания?

Обучение:

• O(1) — просто запоминаем данные.

• Очень быстро.

Предсказание:

• O(n × d) на каждый запрос
  
  где:

  • n — число обучающих примеров

  • d — размерность признаков

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

Как можно считать расстояние?

1. Евклидово расстояние (Euclidean Distance)

Формула:

• Корень из суммы квадратов разницы координат

• Подходит, если признаки числовые и сравнимы по масштабу.

• Обязательно делать стандартизацию, иначе один большой признак “перетянет” всё расстояние на себя. Евклидово расстояние чувствительно к масштабу признаков. Если один признак выражен в километрах, а другой — в метрах, то первый будет доминировать. Поэтому перед использованием часто нормализуют данные

2. Манхэттенское расстояние (Manhattan / L1)

Формула:

• Сумма разности координат по модулю

• Более устойчиво к выбросам.

• Используется, когда важно учитывать абсолютные отклонения.

3. Косинусное расстояние (Cosine Distance / Similarity)

Расстояние:

• Показывает угол между векторами, а не их длину. То есть оно показывает, насколько направления двух векторов похожи.

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

• Используется в рекомендательных системах, NLP, кластеризации текстов.

Какие есть плюсы и минусы метрических моделей и knn в особенности?

Плюсы:

1. Простота — легко реализовать, легко объяснить.

2. Нет обучения — не нужно долго тренировать модель.

3. Интерпретируемость — можно объяснить решение через похожие примеры: “мы присвоили этот класс, потому что рядом был вот этот объект”.

4. Работают на любых признаках (если выбрать подходящую метрику): числовые, бинарные, категориальные.

Минусы:

1. Медленные предсказания — при большом количестве данных или признаков тормозят.

2. Чувствительность к масштабу признаков — без нормализации всё ломается.

3. Проклятие размерности — в высоких размерностях расстояния теряют смысл.

4. Чувствительность к шуму и выбросам — особенно при маленьком k.

5. Хранение всей выборки — нужны память и ресурсы для хранения и поиска.

Как масштабирование признаков влияет на K-NN? Почему?

Это критически важно. Потому что в k-NN всё зависит от расстояний между точками. Если признаки не находятся в одинаковом масштабе, один из них может целиком доминировать, даже если он вообще не важен.

Как ускорить K-NN для большого датасета?

Понижение размерности перед k-NN

• Используй PCA, UMAP, TSNE, TruncatedSVD и т.п.

• Уменьшаешь размерность данных → быстрее считается расстояние

• Главное — сохранить "структуру близости" между точками

Можно использовать Approximate Nearest Neighbors. Annoy, HNSW (Approximate Nearest Neighbors)

• Для приближенного поиска ближайших — быстрее, но с небольшой потерей точности

• Например, Annoy: Можем представить обучающую выборку в виде дерева и считаем уже не по всей области, а по части выборки. Другие методы используют другие методы ограничения выборки для подсчета.

• Очень хорошо работают для больших объемов данных

Где можно применять метрические модели?

• Использовать в качестве бейзлайна

• Если два пользователя похожи — можно рекомендовать одному, что понравилось другому

• Или искать похожие товары, изображения и так далее. 

• Или можно искать не ближайших, а наоборот:
  Если объект далеко от всех остальных — возможно, он аномален. Например, мошенническая транзакция

Кластеризация

Что такое кластеризация? Примеры задач, которые решаются с помощью кластеризации?

Это unsupervised learning, то есть обучение без учителя: нет правильных меток, и модель должна сама найти структуру в данных.

Примеры задач: Сегментация пользователей, поиск аномалий, кластеризация документов или изображений.

Объясните различия между soft и hard кластеризацией.

Hard-кластеризация (жёсткая):

• Каждый объект относится только к одному кластеру.

• Пример: алгоритм KMeans — каждая точка назначается ближайшему центроиду.

• Подходит, когда кластеры чётко разделимы, и пересечения нет.

Soft-кластеризация (мягкая, вероятностная):

• Объект может принадлежать одновременно нескольким кластерам с некоторой степенью уверенности (вероятностью).

• Пример: GMM (Gaussian Mixture Models) — точка может принадлежать, например, на 70% одному кластеру и на 30% другому.

• Это особенно полезно, когда границы между кластерами размытые, и данные — шумные или перекрывающиеся.

Как работает метод К-средних?

Алгоритм KMeans — это итеративный метод кластеризации, который разбивает данные на K непересекающихся кластеров, минимизируя внутрикластерную дисперсию (сумму квадратов расстояний до центроидов).

Основные шаги:

1. Инициализация:

   Выбираются K случайных центров (центроидов) кластеров.

2. Присвоение:

   Каждая точка назначается ближайшему центру кластера (обычно по евклидовому расстоянию).

3. Обновление:

   Центры кластеров пересчитываются как среднее всех точек, попавших в кластер.

4. Повторение:

   Шаги 2–3 повторяются, пока центры не перестают изменяться (или изменение меньше ε) либо не достигнуто максимальное число итераций.

Во время этого алгоритма мы минимизируем внутрикластерную дисперсию:

или сумму квадратов расстояний каждой точки до центра своего кластера

Какие есть проблемы с начальной инициализацией центров? Как можно улучшить ее?

Если инициализацию центров делать просто случайно выбирая точки в пространстве, то может возникнуть проблема того, что все центры попадут в одну место - это приводит к:

• застреванию в плохих локальных минимумах

• и к большему кол-ву итераций оптимизации

Поэтому придумали способ более оптимального выбора начальных центров, работает следующим образом (KMeans++ инициализация):

• Первый центр выбирается случайным образом из всех точек.

• Для каждой точки x, вычисляется расстояние до ближайшего уже выбранного центра — D(x)^2.

• Следующий центр выбирается случайным образом, с вероятностью, пропорциональной D(x)^2. То есть, чем дальше точка от уже выбранных центров, тем выше шанс, что она станет новым центром.

• Повторяем шаг 2–3, пока не выбрано K центров.

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

Как можно ускорить алгоритм к-средних?

• MiniBatch KMeans

  • Вместо использования всего датасета на каждой итерации, берётся маленький случайный минибатч точек.

  • Обновления центров проводятся только по этим батчам.

  • Значительно снижает время одной итерации, и в среднем сходится быстрее. 

• KMeans++ инициализация

• Уменьшение размерности

• Также существуют разные эвристики, чтобы не пересчитывать расстояния до всех центров на каждом шаге

• Распараллеливание

Что такое иерархическая агломеративная кластеризация, чем отличается от дивизионных алгоритмов?

Это тип кластеризации, при котором мы постепенно объединяем объекты в кластеры, начиная с того, что каждая точка — отдельный кластер, и в итоге объединяем всё в один.

Алгоритм:

• Старт: каждая точка — это свой кластер.

• Вычисляется расстояние между всеми кластерами.

• Находим два ближайших кластера и объединяем их.

• Обновляем матрицу расстояний.

• Повторяем шаги 2–4, пока не останется один кластер (или не достигнут критерий остановки).

Как можно посчитать расстояние между кластерами в иерархической кластеризации?

Что такое дендрограмма?

Дендрограмма — это дерево, которое показывает, как и в каком порядке происходило объединение объектов в кластеры в процессе иерархической кластеризации.

Что показывает дендрограмма:

• Ось X: объекты или кластеры.

• Ось Y: расстояние между кластерами в момент их объединения.

• Высота ветвей: насколько "далеки" были кластеры, когда их объединили.

• Обрезка дендрограммы на нужной высоте → даёт итоговые кластеры.

Какие есть критерии остановки работы иерархической кластеризации?

• Фиксированное число кластеров (n_clusters)

• Разрыв (gap) в дендрограмме

• Порог по расстоянию между кластерами

• Минимальный прирост внутрикластерной дисперсии (Ward)

Как работает алгоритм DBSCAN?

DBSCAN — это алгоритм, который ищет области с высокой плотностью точек и определяет их как кластеры, а всё остальное — как шум или выбросы.

2 гиперпараметра:

• e - радиус окрестности точки

• minPts - минимальное количество точек в окрестности, чтобы считать точку "основной"

3 вида точек:

• внутренние / основные точки (core points)
  в их окрестности больше чем minPts объектов выборки

• граничные (border points)
  не подходят под основные, но находятся в их окрестности

• шумовые точки (noise points)
  точки не входящие в окрестность к основным

Алгоритм работает следующим образом:

• убираем все шумовые точки

• начинаем поиск в глубину из основных точек и соединяем все соседние точки и их окрестности, если соседняя точка основная

Плюсы:

• Не нужно задавать число кластеров.

• Устойчив к выбросам.

• Хорошо находит кластер любой формы.

Минусы:

• Плохо работает в высоких размерностях — из-за "проклятия размерности" плотность становится неинформативной.

Какие метрики существуют для оценки качества кластеризации?

• Без учёта разметки (unsupervised)

• С учётом разметки (supervised)

Среднее внутрикластерное расстояние

Сумма расстояний между точками из одного и того же кластера делится на количество пар точек, принадлежащих к одному кластеру.

Среднее межкластерное расстояние

Тут уже не максимизация, а минимизация

Коэффициент силуэта

Считаем его для каждого объекта выборки, а потом усредняем между по всей выборки.

А - среднее расстояние между объектом и всеми элементами его кластера

В - среднее расстояние между объектом и всеми элементами из ближайшего чужого кластера

Также есть и метрики для оценки качества с учетом разметки:

Гомогенность и полнота, а также их среднее гармоническое - V-мера

Как выбрать оптимальное количество кластеров?

• метод локтя

• коэффициент силуэта

• по дендрограмме

• посмотреть глазами (или LLM-кой на получившиеся кластера)

Полезные материалы, на которые я опирался для составления поста:
Учебник ШАДа

На этом в этих темах — все, смотрите разбор вопросов на ютубе!

Разборы реальных собеседований на бусти и еще больше полезного контента в тг канале, подписывайтесь, чтобы не пропустить следующие части, а они уже скоро будут)