itmo_conspects

Машинное обучение

Лекция 1. Описательный анализ данных

Пусть дана случайная величина $\xi$. Из курсов теории вероятности и математической статистики мы знаем, что:

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

Перед тем как датасет (набор данных) применяется в обучении, его необходимо подготовить

Данные могут быть:

Чаще всего, формируя датасет, получается, что некоторых характеристик у объекта нет. Тогда можно прибегнуть к таким способам:

  1. Удалить строки с неизвестной переменной или не принимать их во внимание
  2. Заполнить средним/медианой/модой (обычно так делать не стоит)
  3. Интерполяция
  4. Заполнение на основе соседних данных

Далее данные очищаются от выбросов (аутлаеров, от outlier) - группы значений, выделяющихся из общей выборки

Примеры выбросов

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

Можно представить категориальную переменную в бинарный вектор. Например, цвета “красный”, “зеленый”, “синий” можно превратить в вектор из трех переменных: is_red, is_green, is_blue. Если цвет красный, то is_red = 1, is_green = 0, is_blue = 0

Если просто пронумеровать цвета, то в нашу переменную вносится порядок, что на самом деле не так

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

Методов нормализации существует много, разберем 3 основных:

  1. Минимальная-максимальная нормализация

    Минимальная-максимальная нормализация - подход, при котором величины в выборке приводятся к диапазону $[0, 1]$. Такая нормализация полезна, если алгоритм принимает числа в некотором диапазоне

    \[x_{\text{норм}} = \frac{x - x_{\text{мин}}}{x_{\text{макс}} - x_{\text{мин}}}\]

  2. Стандартизация

    Стандартизация (или Z-масштабирование) преобразует выборка так, что бы среднее было равно 0, а дисперсия - 1:

    \[x_{\text{норм}} = \frac{x - \overline{x}}{\sigma_x}\]

    Выбросы очень сильно влияют на среднее значение выборки, так как изменяют выборочное среднее

  3. Robust-масштабирование

    Robust-масштабирование (от robust - устойчивый) - метод нормализации, похожий на стандартизацию. Вместо выборочного среднего robust-масштабирование использует устойчивую к выбросам медиану, а вместо отклонения - разницу между 25-ым и 75-ым квантилем

    $x_{\text{норм}} = \frac{x - \mathrm{median}(x)}{\mathrm{IQR}(x)}$, где $\mathrm{median}(x)$ - медиана, $\mathrm{IQR}(x)$ - разница между 25-ым и 75-ым квантилем

    Также формулу можно представить так: $x_{\text{норм}} = \frac{x - \mathrm{Q_2}(x)}{\mathrm{Q_3}(x) - \mathrm{Q_1}(x)}$, где $\mathrm{Q_1}(x), \mathrm{Q_2}(x), \mathrm{Q_3}(x)$ - квантили выборки уровней $0.25$, $0.5$, $0.75$ соответственно

Примеры работы этих методов:

Методы нормализации

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

Одним из способов визуализации распределения является ящик с усами (или box plot)

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

По сторонам прямоугольника располагаются отрезки, так называемые усы. Усы могут строиться как:

За пределами усов могут располагать точки, обозначающие выбросы. Ящик с усами позволяет наглядно сравнить распределения:

Ящик с усами

Лекция 2. Статистические гипотезы

Доверительный интервал уровня $\alpha$ - диапазон значений такой, что вероятность попадания значения в него равна $1 - \alpha$. Интервалы бывают двухсторонними $(a; b)$ и односторонними $(a; +\infty)$

Например, при нормальном распределении почти все значения (99.73%) попадают в доверительный интервал $(a - 3\sigma; a + 3\sigma)$

Статистической гипотезой $H$ называется предположение о распределении наблюдаемой случайной величины. Обычно гипотезы формулируют в паре $H_0$ и $H_1$, где $H_0$ - основная гипотеза, а $H_1$ - альтернативная

Пример: среднее количество лет работы американца до выхода на пенсию равно 64. Нулевой гипотезой будет утверждение “матожидание распределения равно 34”, то есть $H_0 \ : \ \mu = 64$

Гипотезы бывают:

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

Ошибка первого рода состоит в том, что $H_0$ отклоняется, хотя она верна. Аналогично, ошибка второго рода состоит в том, что $H_1$ отклоняется (то есть $H_0$ принимается), хотя она верна

Вероятность $\alpha$ ошибки первого рода называется уровнем значимости критерия. Вероятность ошибки второго рода обозначаем $\beta$. Мощностью критерия называется вероятность $1 - \beta$ (вероятность недопущения ошибки второго рода)

P-значение (P-value, от probability) - это вероятность (при условии, что нулевая гипотеза верна) получить такое же или более экстремальное значение какой-либо статистики (например, математического ожидания)

Малое p-значение (обычно меньше 0.05) говорит о том, что наблюдаемые данные маловероятны при справедливости основной гипотезы. В таком случае часто отвергают нулевую гипотезу.
Большое p-value означает, что данные согласуются с основной гипотезой, и оснований отвергать её нет

Пример: пусть есть стандартное нормальное распределение и выборка из него. Для выборки нашли среднее и получили $2$

Проверим гипотезу, что математическое ожидание выборки равно $0$:

\[\begin{cases} H_0 \ : \ a = a_0 = 0, & \text{ если } |K| < t_\text{кр} \\ H_1 \ : \ a \neq a_0, & \text{ если } |K| \geq t_\text{кр} \end{cases}\]

Здесь $K = \sqrt{n} \frac{\overline{x} - a_0}{\sigma}$ - критерий, а $t_\text{кр}$ - квантиль стандартного нормального распределения уровня $1 - \frac{\alpha}{2}$

Пусть размер выборки $n = 4$, тогда $K = 4$

Вероятность получить выборочное среднее, равное или большее $2$, при условии, что нулевая гипотеза верна (то есть $a = 0$), равна

$P(X \leq -K) + P(X \geq K) = 2 P(|X| \geq K) = 2 (\Phi(+\infty) - \Phi(K)) = 1 - 2 \Phi(K)$

Здесь $P(X \leq a)$ - вероятность того, что случайная величина $X \in N(0, 1)$ будет меньше или равна $a$, $\Phi(x) = \frac{1}{\sqrt{2\pi}} \int_0^x e^{-\frac{z^2}{2}} dz$ - функция Лапласа. Так как тест в гипотезе учитывает модуль, то мы считаем сумму интервалов с двух сторон

Полученное значение называют p-значением. В нашем случае оно равно $0.00008$ - данные маловероятны при такой принятой гипотезе

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

Некоторые часто используемые гипотезы называются тестами:

Для определения связи между распределениями двух выборок существует понятие корреляции. Коэффициент корреляции $r$ - величина в диапазоне от -1 до 1, показывающая силу и направления связи

Лекция 3. Методы понижения размерности, метод главных компонент

Зачастую данные нам данные имеют очень много переменных. Это может привести к “проклятью размерности”:

Поэтому нужно уменьшить размерность, не разрушая структуру данных

Существуют несколько методов уменьшения размерности:

Метод главных компонент

Метод главных компонент (Principal Component Analysis, PCA) строится на создании прямых (осей, или главных компонент), которые будут иметь наибольшее отклонение от других осей

Выбирается число этих компонент $n$ - зачастую $n = 2$, так как проще отобразить на графике - и ищутся столько прямых, дисперсия которых максимальна

Для этого:

  1. Строится матрица ковариаций $D \vec X = {\mathrm{cov} (X_i, X_j)}_{i, j}$

  2. Далее для нее находятся собственные числа $\lambda_i$ (такие, что $\lvert (D \vec X) - E \cdot \lambda \rvert = 0$)

    Найденные собственные числа показывают долю дисперсии по одной из компонент (умноженную на сумму всех собственных чисел)

  3. Берутся $n$ наибольших собственных чисел, для них вычисляются собственные вектора $\vec b$ (такие, что $(D \vec X) \cdot \vec b = \lambda_i \vec b$, при этом $\vec b \neq 0$)

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

  4. Далее формируется матрица проекций, где столбцы - выбранные собственные вектора. Далее вектор из выборки умножается на матрицу проекции и получается точка в новом пространстве

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

Пример использования PCA: пусть имеется датасет студентов с параметрами hours_studied (среднее время обучения в часах за день), practice_problems (среднее количество решенных задач) и sleep_hours (среднее время сна в часах)

Номер студента hours_studied practice_problems sleep_hours
0 5.80159 6.10648 7.39829
1 5.16314 3.63228 9.85228
2 7.01063 4.53442 7.9865
3 4.65311 3.35642 6.94229
4 3.17847 3.18283 8.82254
5 4.92243 3.96921 6.77916
6 6.05997 3.72426 8.20886
7 7.23881 4.98804 6.04033
8 4.16849 2.9506 6.67181
9 4.4241 4.02976 8.19686

После стандартизации получаем такую матрицу ковариаций:

  hours_studied practice_problems sleep_hours
hours_studied 1 0.65042 -0.274431
practice_problems 0.65042 1 -0.241426
sleep_hours -0.274431 -0.241426 1

Для нее находятся собственные числа 2.01551082, 0.93050171 и 0.38732081

Далее находятся собственные вектора:

  PC1 PC2 PC3
hours_studied 0.649822 0.258358 0.71483
practice_problems 0.640601 0.320023 -0.698008
sleep_hours -0.409098 0.911502 0.0424537

Получаем матрицу проекций

     
0.649822 0.258358 0
0.640601 0.320023 0
-0.409098 0.911502 0

Далее умножаем вектора из датасета на матрицу, получаем 10 точек на плоскости:

Пример PCA

Код примера - machlearn_pca_example.py

Результат PCA часто используется для:

Так как главные компоненты - линейные комбинации исходных признаков, метод главных компонент плохо подходит для нелинейных связей

Для визуализации лучше всего выбрать 2-3 компоненты

Для обучения лучше оставить как можно больше компонент. Для стандартизованных данных можно выбрать столько компонент, для которых собственные числа больше единицы (правило Кайзера) или пока доля объясненной дисперсии не составит не меньше порога (обычно 85%-95%)

Лекция 4. Нелинейные методы уменьшения размерности

Стохастическое вложение соседей с t-распределением

Стохастическое вложение соседей с t-распределением (t-distributed Stochastic Neighbor Embedding, t-SNE) - алгоритм, хорошо подходящий для визуализации данных в низкой размерности

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

Для этого:

  1. Для каждой пары точек $x_i$ и $x_j$ вычисляется евклидово расстояние $d_{ij} = |x_i - x_j|$

  2. Далее определяется вероятность того, что точка $x_j$ будет соседом точки $x_i$:

    \[p_{j|i} = \frac{e^{-\frac{d^2_{ij}}{2\sigma_i^2}}}{\sum_{k \neq i} e^{-\frac{d^2_{ik}}{2\sigma^2_i}}}\]

    То есть доля $F_\xi (d_{ij})$ от суммы $\sum_{k \neq i} F_\xi (d_{ik})$ для всех точек, где $\xi$ - случайная величина из $N(0, \sigma_i^2)$

  3. Для метода задается параметр перплексии $\mathrm{Perp}$. От него определяется значение $\sigma_i$ такое, что $\mathrm{Perp}(P_i) = 2^{H(P_i)}$, где $H(P_i) = - \sum_{j\neq i} p_{j|i} \log_2 p_{j|i}$ - энтропия Шеннона

    В t-SNE функция перплексии $\mathrm{Perp}(P_i)$ устанавливается на какое-то число (оно называется perplexity, обычно от 1 до 100), благодаря которому можно вывести $\sigma_i$

    Чем больше перплексия, тем больше вероятность того, что некоторая точка будет соседом для другой точки

    При этом перплексия не должна быть больше $n - 1$, где $n$ - размер датасета

  4. Совместная вероятность $p_{ij}$ определяется как $p_{ij} = \frac{p_{j|i} + p_{i|j}}{2n}$, при этом $p_{ii} = 0$

    Заметим, что $p_{j|i} \neq p_{i|j}$

  5. Пусть точки $y_i$ и $y_j$ - отображения точек $x_i$ и $x_j$ на целевом пространстве низкой размерности. Тогда установим, что вероятность того, что $y_i$ и $y_j$ - соседи, равна

    \[q_{ij} = \frac{(1 + \|y_i - y_j\|^2)^{-1}}{\sum_{k \neq l} (1 + \|y_k - y_l\|^2)^{-1}}\]

    При этом $q_{ii} = 0$

    Здесь берется функция плотности $F_t = \frac{\Gamma\left(\frac{n + 1}{2}\right) \left(1 + \frac{x^2}{n}\right)^{-\frac{n + 1}{2}}}{\sqrt{n\pi} \Gamma\left(\frac{n}{2}\right)}$ случайной величины $t$ из распределения Стьюдента $T_n$ при степени свободы $n = 1$, тогда

    \[q_{ij} = \frac{F_t(\|y_i - y_j\|)}{\sum_{k \neq l} F_t(\|y_k - y_l\|)}\]

  6. Если вы дочитали до этого момента, то тут берется функция расстояния Кульбака-Лейблера (или сумма дивергенций Кульбака-Лейблера)

    \[\mathrm{KL}(P \| Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}},\]

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

    Точки $y_i$ в ходе градиентного спуска “притягиваются” к своим местам

    Количеством итераций алгоритма t-SNE называется количество шагов градиентного спуска - чем больше, тем точнее. На больших датасетах берется 500-2000, для приблизительной быстрой оценки 250-500

Наконец-то, мы получили точки $y_i$, которые можно отобразить на плоскости

Распределение Стьюдента с одной степенью свободы имеет более тяжелые хвосты, чем нормальное распределение. Это позволяет близким точкам оставаться очень близкими,а далеким точкам быть очень далекими

Алгоритмическая сложность вычисляется так:

где $d$ - размерность исходного пространства, $k$ - размерность целевого

Пример: есть датасет с 15 фруктами (яблоки и цитрусы), для них мы знаем кислотность, сладость и сочность

Алгоритм t-SNE с perplexity=4 явно отделит их и расположит на плоскости:

t-SNE фрукты 1

При этом также явно можно заметить, что на проекции они кластеризовались по своим признакам

t-SNE фрукты 2

Код примера - machlearn_tsne_example.py

Другой пример - есть датасет с изображениями цифр от 0 до 9. Изображение состоит из сетки 8 на 8 (256 пикселей), где один пиксель - число от 0 до 1, обозначающий оттенок серого

Тогда можно понаблюдать, что происходит при разных perplexity:

t-SNE цифры 2

При маленьком perplexity образуются маленькие кластеры, а при большом - они “слипаются”

Метод t-SNE используется для:

Однако надо учитывать его недостатки:

Алгоритм UMAP

Алгоритм UMAP (Uniform Manifold Approximation and Projection) - алгоритм, похожий на t-SNE. Алгоритм UMAP был создан в 2018 году (статья - *тык*) с целью получить более сильное математическое обоснование

Работает он так:

  1. Даны параметры $k = \text{n\_neighbors}$ - заданное число ближайших соседей у точки и $\text{min\_dist}$ - минимальное расстояние между точками в целевом пространстве

  2. Далее для каждое точки $x_i$ ищется $k$ ближайших соседей $T = {t_1, \dots, t_k}$, используя в качестве расстояния любимую метрику $\mathrm{dist}(x_i, t_i)$ (например, евклидово расстояние \(\mathrm{dist}(x_i, t_i) = \|x_i - t_i\|\))

  3. Теперь для каждой точки вычисляет расстояние до самого ближнего соседа $\displaystyle \rho_i = \min_{t \in T} \mathrm{dist}(x_i, t)$

    Также вычисляется $\sigma_i$ из уравнения $\displaystyle \sum_{t \in T} e^{-\frac{\mathrm{dist}(x_i, t) - \rho_i}{\sigma_i}} = \log_2 k$

  4. Теперь строится взвешенный ориентированный граф, где вес ребра из точки $x_i$ в точку $x_j$ определяется как $v(x_i \to x_j) = e^{-\frac{\mathrm{dist}(x_i, x_j) - \rho_i}{\sigma_i}}$

  5. Этот граф превращается в взвешенный неориентированный, тогда вес ребра из точки $x_i$ в точку $x_j$ определяется как $v_{ij} = v(x_i \to x_j) + v(x_j \to x_i) - v(x_i \to x_j) \cdot v(x_j \to x_i)$

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

    \[w_{ij} = \frac{1}{1 + a \cdot \mathrm{dist}(y_i, y_j)^{2b}}\]

    Параметры $a$ и $b$ подбираются так, что бы $\frac{1}{1 + a \cdot \text{min \_ dist}^{2b}} = 0.5$, а значение производной $\frac{\partial w_{ij}}{\partial \mathrm{dist} (y_i, y_j)} = -1$ в точке $\mathrm{dist}(y_i, y_j) = \text{min \_ dist}$

  7. Теперь составляется функция расстояний Кульбака-Лейбнера

    \[\mathrm{KL}(P \| Q) = \sum_{i \neq j} v(x_i, x_j) \log \frac{v(x_i, x_j)}{w(y_i, y_j)} + (1 - v(x_i, x_j)) \log \left(\frac{1 - v(x_i, x_j)}{1 - w(x_i, x_j)}\right),\]

    которая с помощью стохастического градиентного спуска минимизируется

    Алгоритм градиентного спуска работает фиксированное число итераций (так называемых эпох)

Теперь мы получаем координаты точек $y_i$ в пространстве меньшей размерности

Алгоритмическая сложность UMAP вычисляется так:

Получается $O(n \log n + Tnk)$

Алгоритм UMAP выходит быстрее на больших выборках данных (при $n > T$)

Пример: возьмем этот же датасет с 15 фруктами (яблоки и цитрусы). Алгоритм UMAP с n_neighbors=5 и min_dist=0.1 отделит фрукты с разными параметрами

UMAP фрукты 1

UMAP фрукты 2

На маленьких датасетах, как можно заметить, при правильно подобранных параметрах результат UMAP мало отличим от t-SNE

Код примера - machlearn_umap_example.py

Посмотрим, что происходит при разных n_neighbors и min_dist на датасете с изображениями цифр:

UMAP цифры 1

Малое значение n_neighbors подчеркивает локальную структуру, а большое - связи между кластерами, то есть n_neighbors влияет на масштаб. Расстояние min_dist влияет на плотность кластера на графика

На практике параметры n_neighbors и min_dist определяются методом тыка, но хорошими начальными значениями являются $\text{n\_neighbors} = \sqrt{n}$, $\text{min\_dist} = 0.1$

Таким образом, алгоритм UMAP

  1. Обладает высокой скоростью работы на больших наборах данных
  2. Сохраняет глобальную структуру
  3. Устойчив к разной плотности (что видно на примере выше)
  4. Более универсален, в отличии от t-SNE

Также стоит учесть недостатки:

  1. Чувствительность к параметрам, результаты сильно зависят от выбора n_neighbors
  2. Случайность
  3. Сложность интерпретации расстояний

Лекция 5. Метрики, метод k ближайших соседей

Во время обучения модели возникает компромисс отклонение-дисперсия (Bias-variance tradeoff): ошибку модели, то есть то, насколько ее предсказывание неверно от реального результата, можно поделить на три части:

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

Поэтому данные делят на три части:

Главная цель - проверить, насколько модель обобщается на новые, невиданные данные. Это нужно, чтобы:

В том числе для предотвращения переобучения используется перекрестная проверка (K-Fold Cross Validation):

  1. Выборка делится на k частей
  2. Далее каждая из частей становится тестовыми данными, а остальные - тренировочными
  3. Модель обучается на тренировочных, проверяется на тестовых, получаем k определенных метрик для k обученных моделей
  4. Берется общее этих метрик (например, среднее арифметическое), чтобы оценить точность и эффективность с наиболее равномерным использованием имеющихся данных

Перекрестная проверка

Зачастую датасеты могут быть несбалансированными, то есть намного чаще обладать одним признаком А, нежели другим признаком B (например, список транзакций, где чаще всего будут успешные), что помешает обучению модели. Для решения этого есть такие методы:

  1. Добавление примеров меньшего класса (Oversampling)

    Добавление примеров может привести к переобучению, если просто дублировать данные

    Самый известный метод добавления - SMOTE (о нем позже)

  2. Уменьшение примеров большего класса (Undersampling)

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

  3. Взвешивание классов: увеличиваем вес редкому классу в функции потерь

  4. Изменение порога классификации

Метрики

Методы машинного обучения в основном решают две задачи:

Чтобы понять, насколько хороша наша модель классификации, допустим, что наша модель выводит 0 или 1 в качестве результата, посчитаем, столько таких результатов:

Тогда составим следующие метрики:

Зачастую, модель возвращает не 0 или 1, а вероятность того, насколько принадлежит объект к классу. Если вероятность выше установленного порога $\alpha$, то считается, что объект принадлежит классу

ROC- и PR-кривые

Если модель решает задачу регрессии, то полезны другие метрики:

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

Метод $k$ ближайших соседей (K-Nearest Neighbors Method) - алгоритм для автоматической классификации объектов

Как он работает:

  1. Отмечаем точки $x_i$ из нашей выборки на пространстве
  2. Раскрашиваем их в соответствии с классом (для простоты у нас будут классы 1 и 0)
  3. Далее отмечаем точку $A$, класс которой мы хотим предсказать

  4. Вычисляем расстояния от точки $A$ до точек $x_i$. Это можно делать с помощью:

    • Евклидова расстояния $\displaystyle \mathrm{dist}(x, y) = \sqrt{\sum_{i} (x_i - y_i)^2}$

    • Метрики Манхеттена $\displaystyle \mathrm{dist}(x, y) = \sum_{i} \vert x_i - y_i \vert$ - лучше устойчива к выбросам в пространствах высокой размерности

    • Метрики Минковского $\displaystyle \mathrm{dist}(x, y) = \sqrt[p]{\sum_{i} (x_i - y_i)^p}$

    • Косинусного расстояния $\displaystyle \mathrm{dist}(x, y) = 1 - \frac{x \cdot y}{| x | \cdot | y |}$

  5. Далее находим $k$ ближайших точек $x_i$ к точке $A$, используя выбранную метрику - назовем их $t_i$

  6. Пусть $I(t_i, p)$ - индикатор принадлежности к классу $p$. Предсказываем, что точка $A$ принадлежит к классу 1, если среди ее $k$ ближайших соседей больше точек, принадлежащих к 1, чем к 0, то есть $\displaystyle \sum_{i = 1}^k I(t_i, 1) > \sum_{i = 1}^k I(t_i, 0)$

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

Иногда простой подсчет соседей может не точно предсказывать. Тогда можем применить веса к каждой точке, например $w_i = \frac{k + 1 - i}{k}$ - вес точки линейно уменьшается от порядка в наборе ближайших точек, или $w_i = q^i$, где $q \in (0, 1)$

Однако лучше всего учитывать в весе расстояния до точки. Для этого определим ширину окна $h$ (если расстояние до точки за пределами окна, то считаем ее незначимой) и ядерную функцию $K(x)$

Тогда весом для точки считаем $\displaystyle w_i = K\left(\frac{\mathrm{dist}(A, t_i)}{h}\right)$, а в условии будет $\displaystyle \sum_{i = 1}^k K\left(\frac{\mathrm{dist}(A, t_i)}{h}\right) I(t_i, 1)$

В качестве ядерной функции могут быть:

Помимо этого метод $k$-ближайших соседей может использоваться для нахождения регрессии. Тогда предсказанное значение $\hat y$ вычисляется как взвешенное среднее $\displaystyle \frac{\sum_{i = 1}^k w_i y_i}{\sum_{i = 1}^k w_i}$ для $k$ ближайших соседей

Регрессия методом k ближайших соседей

Код примера - machlearn_knn_regression.py

Преимущества метода $k$-ближайших соседей:

Недостатки:

Метод $k$ ближайших соседей позволяет расширить выборку точками, принадлежащих редкому классу - такая техника известна как SMOTE (Synthetic Minority Over-sampling Technique)

Для этого:

  1. Для точки из редкого класса выбираются $k$ ближайших соседей из того же класса
  2. Выбирается случайный сосед из этих $k$
  3. Новая точка создается на отрезке между точкой и этим соседом

Лекция 6. Линейная регрессия

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

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

Рассмотрим линейную регрессию, которая предполагает, что зависимость между данными линейная. Модель линейной регрессии формулируется так:

\[a(x) = \sum_i w_i x_i = (\vec w, \vec x),\]

где $a(x)$ - предсказанный результат, $\vec w$ - вектор весов, а $\vec x$ - вектор факторов, для которых предсказывается результат

Чтобы регрессия насколько можно хорошо предсказывала результат, нужно уменьшиться количество ошибок - для этого вводят функцию потерь $L(w)$. Значения весов находятся в результате минимизации функции потерь. За функцию потерь можно взять:

Чтобы найти минимум функции, продифференцируем ее, но продифференцировать нужно по всем компонентам $w$, то есть взять градиент:

\[\nabla L(w) = \begin{pmatrix}\frac{\partial L}{\partial w_0} \\ \frac{\partial L}{\partial w_1} \\ \vdots \\ \frac{\partial L}{\partial w_d} \end{pmatrix}\]

Для метода наименьших квадратов это превращается в такую систему линейных алгебраических уравнений: $\nabla L(\hat w) = 2 \sum_{i = 1}^n \vec x_i (\vec x_i \cdot \hat w - y_i) = 0$, где ищем вектор $\hat w$

Или $\hat w \sum_{i = 1}^n \vert \vec x_i \vert^2 = \sum_{i = 1}^n \vec x_i y_i$

В матричной форме это $\hat w = (X^T X)^{-1} X^T Y$

Такой подход, аналитический, дает оптимальное решение, однако очень медленно вычисляется (инверсия матрицы занимает $O(n \cdot d^2 + d^3)$), а если матрица $X$ линейно зависима (то есть в выборке две одинаковых строки или один признак линейно зависит от других), то определитель будет равен 0, что делает невозможным вычисление обратной матрицы

Градиент указывает на направление наибольшего роста, тогда в противоположном направлении будет находится локальный минимум функции

В итоге численный метод вычисления локального минимума вектора $w$ будет выглядеть так:

\[w^{(k + 1)} = w^{(k)} - \alpha_{k} \Delta L(w^{(k)})\]

где $w^{(k)}$ - веса на текущей итерации, $w^{(k + 1)}$ - веса на следующей итерации, $\alpha_{k}$ - коэффициент, определяющий скорость сходимости (так называемый learning rate)

Скорость спуска $\alpha_{k}$ подбирается эмпирически, и его эффективность зависит от характера функции потерь. Например, в простейшем случае для вектора $w$ из одного элемента и функции $L(w)$ при разных $\alpha_{k}$ можем получить такую картину:

Градиентный спуск

Здесь при lr = 0.3 (синяя ломаная) алгоритм нашел локальный минимум функции в точке -5, но не глобальный. Также и при lr = 2 (красная ломаная) алгоритм перепрыгнул глобальный минимум. При lr = 1 (желтая ломаная) минимум был найден, но при lr = 1.5 (зеленая ломаная) алгоритму было недостаточно 8 итераций, чтобы его найти

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

Градиентный спуск при непостоянных скоростях

Код примера - machlearn_gradient_descent.py

Помимо скорости спуска, сходимость градиентного спуска также зависит от:

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

Сравнение спусков

Также начальная точка спуска может выбираться случайно, чтобы наиболее вероятно найти глобальный минимум

Ключевой метрикой линейной регрессии является $R^2 = 1 - \frac{\sum (y_i - \hat y_i)^2}{\sum (y_i - \overline{y})^2}$ - коэффициент детерминации, показывающий, какую долю дисперсии предсказываемого признака способна модель объяснить

На основе его вводят другую метрику $R^2_{\text{adj}} = 1 - \left(\frac{(1 - R^2) (n - 1)}{n - p - 1}\right)$ - скорректированный коэффициент детерминации, где $n$ - размер выборки, $p$ - число независимых признаков. Такая метрика сильно понижается, если параметров слишком много, тем самым, предотвращая переобучение

Чтобы сделать модель проще, введем штраф за число весов. Есть несколько подходов:

Также с помощью регрессии можно решить задачу классификации. Пусть положительное $y_i$ означает, что точка $x_i$ принадлежит классу 1, а отрицательное - классу -1. Тогда $\hat y = \mathrm{sign}((\vec w, \vec x))$

Помимо этого мы хотим быть уверены в предсказании, поэтому нужна функция, которая для $(\vec w, \vec x) \in \mathbb{R}$ даст вероятность принадлежности из отрезка $[0, 1]$. В качестве нее можно взять сигмоиду: $f(\vec w, \vec x) = \frac{1}{1 + e^{-(\vec w, \vec x)}}$

Сигмоида

Отсюда $(\vec w, \vec x) = \ln \left(\frac{p}{1 - p}\right)$

Тогда функция потерь формулируется так: $L(w) = \sum_{i = 1}^n \left(y_i \ln(p) + (1 - y_i) \ln(1 - p)\right)$

Такой подход решения классификации с помощью регрессии называется логистической регрессией

Лекция 7. Метод опорных векторов

Метод опорных векторов (Support Vector Machine, SVM) - это алгоритм классификации, который ищет гиперплоскость, разделяющую данные разных классов с максимальным зазором (margin)

Пусть дана выборка из переменных $X$ и класс для каждой точки $y_i \in {-1, 1}$

Гиперплоскость мы будем искать в виде $w^T x + b = 0$, где $w$ - вектор весов, $x$ - точка в пространстве

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

Так как гиперплоскость разделяет точки по их классам, то выполняется условие $y_i (w^T x_i + b) \geq 1$. Для опорных векторов $y_i (w^T x_i + b) = 1$

Несложно показать, что ширина зазора равна $\frac{2}{| w |}$ ($\frac{2}{| w |} = \frac{\vert w^T x + b + 1 \vert - \vert w^T x + b - 1 \vert}{|w|}$ - расстояние между точками, удаленных на один от точки $x$ на гиперплоскости)

Тогда, чтобы увеличить ширину, нужно уменьшить $| w |$, то есть метод опорных векторов решает задачу:

\[\frac{1}{2} \|w\|^2 \longrightarrow \min \text{ при условии, что } y_i (w^T x_i + b) \geq 1\]

Такой подход называется методом опорных векторов с жестким зазором (Hard-margin SVM)

Здесь мы минимизируем $|w|^2$, так как $| w | = \sqrt{w_1^2 + \dots + w_n^2}$ не дифференцируема в $\vec 0$

Веса ищутся с помощью градиентного спуска

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

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

Код примера - machlearn_svm_hard_margin.py

Если данные линейно не разделимы, то есть их нельзя разделить плоскостью, то можно применить два трюка:

  1. Метод опорных векторов с мягким зазором (Soft-margin SVM)

    Добавляем штраф $\xi_i$ для каждой точки:

    • Если точка на границе зазора или за пределами, то она классифицирована правильно, и для нее $\xi_i = 0$
    • Если точка внутри зазора, но на правильной стороне от гиперплоскости, то она классифицирована правильно, и для нее $0 < \xi_i \leq 1$
    • Если точка по другую сторону от гиперплоскости и классифицирована неправильно, то для нее $\xi_i > 1$

    Тогда условие становится таким: $y_i (w^T x_i + b) \geq 1 - \xi_i$

    Теперь будем минимизировать такое выражение:

    \[\frac{1}{2} \|w\|^2 + C \sum_{i = 1}^n \xi_i \longrightarrow \min \text{ при условии, что } y_i (w^T x_i + b) \geq 1 - \xi_i\]

    Здесь $C$ - гиперпараметр, управляющий штрафом за ошибки. При большом $C$ модель пытается строго разделить данные, а при меньшем $C$ модель допускает больше ошибок

    МОВ с мягким зазором

    Код примера - machlearn_svm_soft_margin.py

    Очевидно, что при большом $C$ также уменьшается ширина зазора. В пределе $C \to \infty$ метод опорных векторов с мягким зазором превращается в метод опорных векторов с жестким зазором

  2. Нелинейный метод опорных векторов

    Если данные вообще жесть как не разделимы, то можно прибегнуть

    • К увеличению размерности пространства, например, представить двухмерные точки $(x_1, x_2)$ как $(x_1^2, x_2^2, \sqrt{2} x_1 x_2)$ и искать гиперплоскость в трехмерном пространстве:

      Увеличение размерности

      Код примера - machlearn_svm_dimension_increase.py

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

    • Или к переопределению скалярного произведения через ядерные функции

      Вместо линейного скалярного произведения $K(x, y) = (x, y) = \sum_{i = 1}^n x_i y_i$ (так называемое линейное ядро, linear kernel) можно взять:

      • Полиномиальное ядро (Polynomial kernel): $K(x, y) = (\gamma (x, y) + r)^d$, где $\gamma$ - масштаб, $r$ - смещение, $d$ - степень полинома

      • Гауссовское ядро (или RBF, Radial Basis Function): $K(x, y) = e^{-\gamma |x - y|^2}$, где $\gamma$ - регулирует масштаб функции. При маленьких $\gamma$ граница гладкая (функция сходится к 0 медленнее), а при больших $\gamma$ - более изогнутая. Самое такое мейнстримное ядро

      • Сигмоидное ядро (Sigmoid kernel): $K(x, y) = \mathrm{tanh}(\gamma (x, y) + r)$

      Тогда мы не вычисляем новые признаки явно, а сразу считаем скалярное произведение в этом новом пространстве, то есть экономим время и память (так называемый Kernel Trick)

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

Нелинейный метод опорных векторов с мягким зазором

Еще пример:

Спиралька

Код примера - machlearn_svm_nonlinear.py, machlearn_svm_nonlinear_2.py

Лекция 8. Деревья, лес, бустинг

Закономерность $\varphi$ называется интерпретируемой, если:

  1. Она сформулирована естественным языком
  2. Зависит от небольшого числа параметров (от одного до семи)

Закономерность $\varphi$ называется информативной, если число истинно положительных результатов предсказаний \(p(x) = \vert \{ x_i \ \vert \ \varphi(x_i) = 1, y_i = c \} \vert\) максимально, а число ложноположительных результатов \(n(x) = \vert \{ x_i \ \vert \ \varphi(x_i) = 1, y_i \neq c \} \vert\) минимально

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

№ Погода Температура Влажность Ветер Можно играть
1 Солнечная Жарко Высокая Слабый ❌ Нет
2 Солнечная Жарко Высокая Сильный ❌ Нет
3 Облачная Жарко Высокая Слабый ✅ Да
4 Дождливая Тепло Высокая Слабый ✅ Да
5 Дождливая Холодно Средняя Слабый ✅ Да
6 Дождливая Холодно Средняя Сильный ❌ Нет
7 Облачная Холодно Средняя Сильный ✅ Да
8 Солнечная Тепло Высокая Слабый ❌ Нет
9 Солнечная Холодно Средняя Слабый ✅ Да
10 Дождливая Тепло Средняя Слабый ✅ Да
11 Солнечная Тепло Средняя Сильный ✅ Да
12 Облачная Тепло Высокая Сильный ✅ Да
13 Облачная Жарко Средняя Слабый ✅ Да
14 Дождливая Тепло Высокая Сильный ❌ Нет

Закономерность можно представить в виде дерева решений:

Дерево решения для примера

Такое дерево называется деревом решений - это дерево, для которого:

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

Оптимальное дерево

Из этого возникает вопрос: как его построить оптимальный способом?

Это определяется с помощью величины энтропии для каждого признака. Энтропия показывает меру неопределенности эксперимента и считается так:

\[H(S) = - \sum_{k = 1}^d p_k \log_2 p_k,\]

где $d$ - число классов, $p_k$ - доля класса $k$ в выборке $S$

Тогда для всей нашей выборки $H(S) = - \frac{9}{14} \log_2 \frac{9}{14} - \frac{5}{14} \log_2 \frac{5}{14} \approx 0.94$

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

Признак Значение Энтропия
Погода Солнечная $-\frac{2}{5} \log_2 \frac{2}{5} - \frac{3}{5} \log_2 \frac{3}{5} \approx 0.97$
  Облачная $-\frac{4}{4} \log_2 \frac{4}{4} - \frac{0}{4} \log_2 \frac{0}{4} = 0$
  Дождливая $-\frac{2}{5} \log_2 \frac{2}{5} - \frac{3}{5} \log_2 \frac{3}{5} \approx 0.97$
Температура Тепло $-\frac{2}{6} \log_2 \frac{2}{6} - \frac{4}{6} \log_2 \frac{4}{6} \approx 0.92$
  Жарко $-\frac{2}{4} \log_2 \frac{2}{4} - \frac{2}{4} \log_2 \frac{2}{4} = 1$
  Холодно $-\frac{3}{4} \log_2 \frac{3}{4} - \frac{1}{4} \log_2 \frac{1}{4} \approx 0.81$
Влажность Высокая $-\frac{3}{7} \log_2 \frac{3}{7} - \frac{4}{7} \log_2 \frac{4}{7} \approx 0.98$
  Средняя $-\frac{6}{7} \log_2 \frac{6}{7} - \frac{1}{7} \log_2 \frac{1}{7} \approx 0.59$
Ветер Слабый $-\frac{3}{6} \log_2 \frac{3}{6} - \frac{3}{6} \log_2 \frac{3}{6} = 1$
  Сильный $-\frac{6}{8} \log_2 \frac{6}{8} - \frac{2}{8} \log_2 \frac{2}{8} \approx 0.81$

Далее для каждого признака считается информационный выигрыш (IG, Informational Gain) по формуле:

\[\mathrm{IG}(S, A) = H(S) - \sum_{v \in A} \frac{\vert S_v \vert}{\vert S \vert} H(S_v),\]

где $S_v$ - подвыборка, где у всех элементов значение $v$ признака $A$

Получаем следующие значения:

Признак Информационный выигрыш
Погода 0.247
Влажность 0.152
Ветер 0.048
Температура 0.029

Информационный выигрыш показывает, насколько важен признак в выборке и насколько сильно он снизит энтропию при разделении

Как можно заметить, “Погода” имеет наиболее сильный информационный выигрыш, поэтому первая вершина в дереве будет разделять дерево по “Погоде”

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

Останавливать разбиение можно, используя несколько критериев:

Если после остановки в выборке осталось несколько классов, то выбираем наиболее вероятный

Деревья решения можно использовать в регрессии - получатся регрессионные деревья. В листе вместо класса возвращается среднее значение:

Регрессионные деревья

Здесь хорошо видно, что дерево с высотой 5 имеет небольшое переобучение. Структура деревьев выглядит так:

Структура регрессионных деревьев

Код примера: machlearn_regression_tree.py

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

Проблема в глубоких деревьях - переобучение. Однако невысокие деревья не смогут показать хорошие результаты при больших признаках. Поэтому появилась теорема Шапире, сформулированная в 1990 году (ссылка на статью - *тык*):

Слабая обучаемость эквивалентна сильной обучаемости

Здесь

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

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

Случайный лес

Такой подход называется лесом деревьев решений. Работает лес так:

  1. Бутстрэппинг (или бэггинг, от bootstrap aggregating) данных

    Из исходной обучающей выборки случайно выбираются подвыборки. Каждое дерево обучается на своей подвыборке

  2. Случайный выбор признаков

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

  3. Обучение множества деревьев

    Строится, например, 100 или 500 деревьев, причем каждое независимо

  4. Агрегация результатов:

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

    В регрессии берётся среднее значение предсказаний деревьев

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

Дерево vs Лес

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

Бустинг

Веса можно уточнять с помощью градиентного спуска. Рассмотрим 3 реализации градиентного бустинга:

Также есть еще один ансамблевый подход - стекинг. В стекинге (stacking)

  1. Сначала обучаются модели одного типа на исходном датасете
  2. На новой выборке получаем предсказания
  3. Другая модель на этом наборе предсказаний обучается

Лекция 9. Вероятностные подходы

Допустим, есть задача фильтрации спама в письмах

Тогда, вспомнив формулу Байеса:

\[P(A \vert B) = \frac{P(B \vert A) P(A)}{P(B)},\]

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

\[P(\text{письмо - спам} \vert \text{есть слова «выиграли» и др.}) = \frac{P(\text{есть слова «выиграли» и др.} \vert \text{письмо - спам}) P(\text{письмо - спам})}{P(\text{есть слова «выиграли» и др.})}\]

Обозначим $x_i$ - индикатор нахождения $i$-ого слова из спам-словаря в письме, а $y$ - является ли письмо спамом. Мы хотим увеличить апостериорную вероятность $P(y \vert \vec x) = \frac{P(\vec x \vert y) P(y)}{P(\vec x \vert y) P(y) + P(\vec x \vert \overline{y}) P(\overline{y})}$, где $P(\vec x \vert y) = \prod_{i = 1}^n P(x_i \vert y)$, $P(\vec x \vert \overline{y}) = \prod_{i = 1}^n P(x_i \vert \overline{y})$

Вероятность $P(y)$ находится как доля спам-писем от общего числа писем (аналогично $P(\overline{y})$). $P(x_i \vert y)$ может определяться по-разному, например, доля количества спам-писем с $i$-ым словом от числа всех писем $\frac{N_{i,y}}{N_y}$

Такой метод называется наивным байесовский классификатором (Naive Bayes classifier). Такие классификаторы бывают разными в зависимости от выбора $P(x_i \vert y)$:

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

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

Байесовская сеть

Здесь нам известны явные зависимости, и, исходя из данных, можно найти вероятности

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

  1. Структурное обучение по ограничениям (constraint-based)

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

    1. Берём все переменные $(X_1, X_2, \dots, X_n)$
    2. Проверяем условные независимости двух переменных с помощью критерия “хи-квадрат” или проверки на нулевую корреляцию
      • Если переменные независимы при данном условии - ребра между ними нет
      • Если зависимы - ребро есть
    3. Далее применяется набор правил, чтобы определить направления стрелок

    Алгоритм Peter-Clark (PC) реализует поиск зависимостей между переменными

    Достоинства:

    • Гарантирует корректную структуру при очень больших данных
    • Основан на строгих статистических тестах

    Недостатки:

    • Плохо работает при малом датасете
    • Экспоненциально растущая сложность при многих переменных, нужно проверять множество условных независимостей

  2. Структурное обучение по оценке качества (score-based)

    Структурное обучение по оценке качества не проверяет независимости, а ищет граф, максимизирующий некоторую функцию качества

    1. Задаём функцию качества Например, $\mathrm{BIC} = k \ln n - 2 \ln \hat L$ - информационный критерий Байеса (Bayesian Information Criterion), где $k$ - число параметров, $n$ - размер выборки, $\hat L$ - максимальное значение функции правдоподобия

      Функцию $\mathrm{BIC}$ можно пересчитывать для измененного участка, а не для всего графа

    2. Перебираем графы или локально улучшаем текущий граф
    3. Выбираем лучший

    Алгоритмы, реализующие обучение по оценке качества: Tabu Search, Genetic Algorithms, Simulated Annealing

    Достоинства:

    • Гибкость, устойчивость к шуму
    • Даёт хорошую структуру при реальных данных

    Недостатки:

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

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

Также используется цепь Маркова - вероятностный автомат, переходы между состояниями которого определяются с некоторой вероятностью

Например, пусть состояния показывают погоду в $i$-ом часу: солнечную, облачную или дождливую. Если погода сейчас солнечная, то с вероятностью $p = 0.8$ она останется такой же, $p = 0.15$ - станет облачной, и $p = 0.05$ - пойдет дождь. Аналогично с другими переходами, тогда получаем такую цепь:

Цепь Маркова

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

Цепь Маркова используется в методе Монте-Карло с марковскими цепями (Markov chain Monte Carlo, MCMC) для моделирования вероятностей зависимых событий, например, интенсивность распада в ядерной реакции или наиболее вероятное следующее слово в тексте

Лекция 10. Кластеризация

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

Кластеризацию не стоит путать с уменьшением размерности данных: кластеризация - это поиск общих групп, а уменьшение размерности - поиск нового представления данных

Можно выделить 4 подхода:

  1. Разделение, основанное на центах (Centroid-based partitioning clustering)
  2. Кластеризация, основанная на плотности (Density-based clustering)
  3. Иерархическая кластеризация (Hierarchical clustering)
  4. Кластеризация, основанная на модели (Model-based clustering) - методы не всегда универсальные, поэтому они не будут здесь разбираться

Кластеризация, основанная на центрах

В методах, основанных на центрах, алгоритмы ищут центроиды - точки, которые описывают центры будущих кластеров

Центроид - это такая точка, сумма квадратов расстояний до точек в кластере минимальна

В методе $k$ средних (k-means):

Алгоритм повторяется до тех пор, пока положение центроидов меняется

Метод k средних

Выбор точек может быть таким:

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

Кластеризация, основанная на плотностях

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

Популярным таким методом является DBSCAN (Density-Based Spatial Clustering of Applications with Noise, Основанная на плотности пространственная кластеризация для приложений с шумами) и работает так:

DBSCAN

Наивно DBSCAN работает за квадрат (считаем все расстояния между точками), однако с помощью деревьев и индексов можно получить асимптотику лучше

Иерархическая кластеризация

Иерархическая кластеризация - это метод кластеризации, который строит иерархию кластеров в виде дерева, которое называется дендрограммой. Такие методы делятся на агломеративные (от меньших кластеров к большим) и дивизивные (от больших к меньшим)

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

Агломеративный метод

Кластеры

Если расстояния между точками тривиально вычисляется, то расстояния между кластерами (так называемый linkage) можно считать разными способами

Также сами расстояния между точками можно вычислять по-разному: евклидово, манхеттенское, косинусное и так далее

Иерархическая кластеризация позволяет взглянуть, как кластеры друг к другу относятся, однако:

Код примера - machlearn_agglomerative_clustering.py

Методы можно комбинировать - так появился HDBSCAN (Hierarchical DBSCAN). В нем:

Здесь не используется параметр $\varepsilon$, что позволяет хорошо выделять кластера с разными плотностями. Однако, можно задать $\text{min \_ cluster \_ size}$ - минимальный размер устойчивого кластера

Устойчивыми кластерами считаются те, которые долго не распадаются. Для этого вводится метрика $\displaystyle \mathrm{Stability}(C) = \sum_{i \in C} (\lambda_{i} - \mu_{C})$, где $\mu_{C} = \frac{1}{\mathrm{mreach}(x, y)}$ - обратное к весу ребра, удаление которого привело к появлению кластера, а $\lambda_{i} = \frac{1}{\mathrm{mreach}(x_i, x_j)}$ - обратное к весу ребра, удаление которого привело к отделению $i$-ой точки

Для такой иерархии кластеров

Пример HDBSCAN

стабильность кластера 1 определяется как сумма $(0.067 - 0.034) + (0.067 - 0.034) + (0.069 - 0.034) + (0.069 - 0.034) + (0.073 - 0.034) + (0.073 - 0.034) + (0.059 - 0.034) = 0.239$ 😲

А стабильность кластера 3 равна $(0.059 - 0.055) + (0.073 - 0.055) + (0.073 - 0.055) = 0.04$

Дополнительная информация о HDBSCAN: https://lanselin.github.io/introbook_vol1/HDBSCAN.html

Метрики кластеризации

Чтобы оценить, насколько хороша кластеризация выборки, можно использовать следующие метрики:

This site is open source. Improve this page.