Методы машинного обучения

 Шестаков Андрей (avshestakov@hse.ru)


Деревья решений, случайные леса

Пример 1

  • Некоторая кoмпания открыла курс по разработке приложений на Andriod для (всех) студентов МГУ
  • Прошло уже несколько наборов
  • По результатам каждого отбора слушатели отставляют отзыв (+1|-1)
  • О слушателях известно
    • Пол
    • Возраст
    • Курс
    • Факультет
    • Посещаемость
    • Оценки за ДЗ
    • ...

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

В идеальном мире исследователь должен прийти с чем-то вроде

  • [Пол = Ж][Возраст > 21][Факультет = Экономика][Посещаемость < 50%] - не нравится в 82% случаев
  • [Пол = М][Возраст >= 20][Факультет = ВМК][Средний балл > 4.5] - не нравится в 10% случаев
  • ...

Пример 2

  • Вы приходите в банк за кредитом не дай бог, подаете анкету со всеми необходимыми документами
  • Сотрудник банка проверяет вашу анкету:
    1. Если объем сбережений <= 200 тыс., то перейти к шагу 2, иначе - к шагу 3.
    2. Если стаж больше года - дать кредит, иначе - не давать
    3. Если продолжительность займа < 30 месяцев - не давать кредит, иначе - к шагу 4
    4. ...

Формально, дерево решений - это связный ациклический граф. В нем можно выделить 3 типа вершин:

  1. Корневая вершина (root node) - откуда все начинается
  2. Внутренние вершины (intermediate nodes)
  3. Листья (leafs) - самые глубокие вершины дерева, в которых содержится "ответ"

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

Обобщенный псевдокод алгоритма построения дерева

{python}
1. function decision_tree(X, y):

2.    if stopping_criterion(X, y) == True:

3.        S = create_leaf_with_prediction(y)

4.    else:

5.        S = create_node()
6.        (X_1, y_1) .. (X_L, y_L) = best_split(X, y)

7.        for i in 1..L:
8.            C = decision_tree(X_i, y_i)
9.            connect_nodes(S, C)
10.   return S

Как определяются лучшие разбиения (best splits)?

Меры неопределенности (impurity measures)

По какому мешку лучше классифицировать?

Как определяются лучшие разбиения (best splits)?

Меры неопределенности (impurity measures)

Пусть $p_k$ - это доля класса $C_k$ в узле дерева $S$.

  1. Missclassification error
    $$I(S) = 1 - \max\limits_k p_k $$
  2. Gini index $$I(S) = 1 - \sum\limits_k (p_k)^2 = \sum\limits_{k'\neq k} p_{k'} p_k$$
  3. Entropy $$I(S) = -\sum\limits_k p_k \log(p_k)$$
In [4]:
plot_impurities()

Как определяются лучшие разбиения (best splits)?

Прирост информации

Выберем признак $A$ и пороговое значение $t$ на нем таким образом, чтобы уменьшить неопределенность:

Насколько уменьшится неопределенность:
$$ Gain(S, A) = I(S) - \left(\frac{|S_L|}{|S|}\cdot I(S_L) + \frac{|S_R|}{|S|}\cdot I(S_R) \right),$$ где $S_R$ и $S_L$ - это потомки узла $S$ c объектами, удовлетворяющим соответствующим условиям.

  • Стратегия выбора - жадная
  • Как определяется порог при вещественных признаках?
  • Что если категорий у признака много? Breiman, et al
  • Локальная оптимизация - уменьшение Impurity внутри узла
  • Результаты не сильно зависят от выбора самой меры неопределенности
In [18]:
def impurity(p): 
    # p - массив из долей каждого из классов
    # Имплементируйте любую меру неопределенности
    return 1 - (p**2).sum()
#     return 1 - np.max(p)
#     return -np.sum(p*np.log2(p))
wine_demo() 

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

In [8]:
try:
    fig = interact(demo_dec_tree, depth=IntSlider(min=1, max=5, value=1))
except:
    print('Что-то не так. Посмотрите на доску')

Критерии останова (регуляризация)

  • Никогда
  • Задать порог по мере неопределенности: $I(S) \leq \theta$
  • Задать порог по размеру узла: $|S| \leq n$
  • Задать порог на глубину: $Depth(S) = d$
  • Задать порог на размер потомков: $|S_L| \leq n_1 \& |S_R| \leq n_2$
  • ...

Регрессия

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

  • Среднее квадратичное отклонение от среднего $$ I(S) = \frac{1}{|S|}\sum\limits_{i \in S}(y_i - \bar{y_S})^2 $$
  • Среднее абсолютное отклонение от медианы $$ I(S) = \frac{1}{|S|}\sum\limits_{i \in S}|y_i - \bar{y_S}| $$
In [10]:
try:
    fig = interact(plot_dec_reg, depth=IntSlider(min=1, max=5, value=1), criterion=['mse', 'mae'])
except:
    print('Что-то не так. Посмотрите на доску')

Как определяется ответ?

  • Классификация
    • Класс с большинством в листе
    • Доли каждого из классов в листе
  • Регрессия
    • Среднее (медиана) целевой переменной в листе

Важность признаков

В деревьях решений производится автоматический отбор признаков.

Пусть $v(S)$ - это признак, который использовался для ветвления в узле $S$

$$ \text{imp}(A) = \sum\limits_{i: v(S_i) = A} \frac{|S_i|}{|S|} Gain(S_i, A) $$

Работа с пропусками

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

Специальные алгоритмы построения деревьев

ID 3

  • Только категориальные признаки
  • Количество потомков = количеству значений признака
  • Строится до максимальной глубины

С 4.5

  • Поддержка вещественных признаков
  • Категриальные как в ID3
  • При пропуске значения переход по всем потомкам
  • Удаляет избыточные ветвления

СART

  • В основном сегодняшнее занятие про него
  • Специальная процедура усещения дерева после построения (post prunning)

Преимущества / Недостатки

Преимущества

  • Простота построения
  • Интерпретируемость (при небольшой глубине)
  • Требуются минимальная предобработка признаков
  • Встроенный отбор признаков

Недостатки

  • Границы строяется только параллельно или перпендикулярно осям признаков
  • При изменении набора данных надо полностью перестраивать и результат может получится совершенно иным
  • Жадность построения

Случайный лес (Random Forest)

Мотивация 1

Дерево решений очень чувствительно к данным

In [12]:
demo_2dec_tree()

Мотивация 2

Возможно, если строить несколько немного разных деревьев, то в среднем

  • Они будут "сглаживать" общий результат
  • Точность будет лучше чем у отдельных деревьев

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

Пример из идеального мира:

  • Пусть решается задача бинарной классификации
  • Пусть у нас есть $M$ независимых базовых моделей, которые выдают верное предсказание с вероятностью $p \in (1/2, 1]$
  • Финальный ответ определяется простым большинством
  • Оказывается, что чем больше классификаторов в ансамбле - тем больше вероятность угадать ответ
$$ P_{ens} = \sum\limits_{k=[M/2+1]}^M \binom{M}{k} p^{k}(1-p)^{M-k} $$
In [22]:
M = 100
T = int(M/2 + 1)
p = 0.6
p_ens = sum([scipy.special.comb(M,k)*(p**k)*((1-p)**(M-k)) for k in range(T, M+1)])
p_ens
Out[22]:
0.972900802242991

Bagging - это параллельный способ построения ансамбля.

  1. Обучающая выборка сэмплируется $k$ раз с помощью bootstrap'a (выборка с возвратом)
  2. На каждом сэмпле обучается отдельная базовая модель
  3. Ответы моделей усредняются (возможно с весом)

Почему усреднение работает?

  • Какая высота у Эйфелевой башни?
  • Чему равен МРОТ?
  • Кто здесь леопард?

Так же есть некоторые обобщения бэггинга:

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

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

In [15]:
try:
    fig = interact(rf_demo, n_est=IntSlider(min=1, max=101, value=1, step=5))
except:
    print('Что-то не так. Посмотрите на доску')

Интерпретация деревьев и лесов

  • На небольшие деревья можно просто посмотреть
  • Для каждого наблюдения можно запомнить путь, которое оно прошло по дереву
  • А если дерево очень глубокое?
  • А если у нас лес?

Доп. Материалы

  • Mohammed J. Zaki. Data Mining and Analysis: Fundamental Concepts and Algorithms. Ch19
  • Trevor Hastie, et al. The Elements of Statistical Learning. Ch9.2
  • Random Forests Home