28. Построение списка решений и дерева решений. Редукция деревьев решений. Понятие бэггинга и бустинга для деревьев решений. Случайный лес и способы его построения.

Построение списка решений и дерева решений. Список решений – это простой, но эффективный метод классификации. Он состоит из последовательности правил "если – то", где каждое правило задает условие на входные признаки и соответствующий прогнозируемый класс.

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

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

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

Коэффициент информационного выигрыша (IGR – Information Gain Ratio) для условия определяется следующим образом:

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

Энтропия набора данных – это мера примеси или, иначе говоря, неопределенности в метках классов.

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

Аналогично, энтропия с учетом условия рассчитывается как:

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

II (Intrinsic Information) отражает меру внутренней энтропии отделяемой подвыборки и выражается следующим образом:

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

Заметим, что IGR не единственный возможный критерий принятия решений. Например, можно использовать индекс примеси Джини:

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

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

где – количество экземпляров в подмножестве ;

– общее количество наблюдений в наборе данных.

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

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

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

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

1. Создать корневой узел, который содержит весь набор данных.

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

3. Выбрать признак, максимизирующий критерий разбиения.

4. Создать новый внутренний узел, используя выбранный признак.

5. Разделить набор данных на основе значений выбранного признака.

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

7. Присвоить наиболее распространенную метку класса образцам в листе.

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

Т.к. деревья относятся к жадным алгоритмам, им свойственно разрастаться и переобучаться. Чтобы этого не произошло, можно использовать разные критерии остановки алгоритма, о которых упоминалось ранее, или же использовать алгоритмы усечения деревьев. Алгоритмов усечения много, но мы рассмотрим только метод усечения слабых связей (Weakest Link Pruning).

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

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

Для того чтобы ответить на вопрос по какому принципу выбирается какие узлы следует обрезать обратимся к критерию Tree Score.

где – штраф за сложность дерева, может быть рассчитан как количество листьев;

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

– сумма квадратов остатков.

В результате, выбирается дерево имеющее наименьшее рассчитанное значение Tree Score.

Понятие бэггинга и бустинга для деревьев решений.

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

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

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

Приведем наиболее общие шаги для построения модели случайного леса:

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

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

3. Построить дерево решений, используя выбранные выборки и признаки.

4. Повторять шаги 1-3, чтобы создать лес деревьев решений.

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