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

Добавил пользователь Владимир З.
Обновлено: 19.09.2024

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

Читается за 8 мин.

Хотите создать собственную диаграмму? Попробуйте Lucidchart. Это быстро, легко и совершенно бесплатно.

Что такое дерево решений?

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

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

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

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

Символы дерева решений

Фигура	Название	Значение
Узел решения	Решение, которое необходимо принять
Узел вероятности	Указывает несколько возможных результатов
Ветви альтернативы	Каждая ветвь символизирует возможный результат или действие
Отклоненная альтернатива	Вариант, который не был выбран
Конечный узел	Символизирует конечный результат

Как составить дерево решений

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

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

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

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

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

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

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

Пример анализа дерева решений

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

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

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

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

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

Деревья решений в машинном обучении и добыче данных

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

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

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

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

Принято считать, что идеальное дерево решений должно передавать максимум информации при минимальном количестве вопросов или уровней. Среди алгоритмов для создания оптимизированных деревьев решений можно выделить CART, ASSISTANT, CLS и ID3/4/5. Дерево решений также можно выстроить при помощи набора ассоциативных правил и целевой переменной, которая помещается в правой части схемы.

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

Использование деревьев решений в машинном обучении имеет следующие преимущества:

Тем не менее, у деревьев решений есть и недостатки:

Шаблоны и примеры деревьев решений

Пустое дерево решений

Шаблон дерева решений с формулами

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

Шаблон дерева решений с данными

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

Шаблон вертикального дерева решений

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

Даже если перед вами стоят сложные вопросы, найти подходящую схему для их решения просто. Используйте Lucidchart для наглядного анализа сложных решений прямо онлайн!

Хотите создать собственную диаграмму? Попробуйте Lucidchart. Это быстро, легко и совершенно бесплатно.

Общий принцип построения деревьев решений был дан в статье "Деревья решений – основные принципы работы".

В этой статье речь пойдет об алгоритме CART. CART, сокращение от Classification And Regression Tree, переводится как "Дерево Классификации и регрессии" – алгоритм бинарного дерева решений, впервые опубликованный Бриманом и др. в 1984 году [1]. Алгоритм предназначен для решения задач классификации и регрессии. Существует также несколько модифицированных версий – алгоритмы IndCART и DB-CART. Алгоритм IndCART, является частью пакета Ind и отличается от CART использованием иного способа обработки пропущенных значений, не осуществляет регрессионную часть алгоритма CART и имеет иные параметры отсечения. Алгоритм DB-CART базируется на следующей идее: вместо того чтобы использовать обучающий набор данных для определения разбиений, используем его для оценки распределения входных и выходных значений и затем используем эту оценку, чтобы определить разбиения. DB, соответственно означает – "distribution based". Утверждается, что эта идея дает значительное уменьшение ошибки классификации, по сравнению со стандартными методами построения дерева. Основными отличиями алгоритма CART от алгоритмов семейства ID3 являются:

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

Бинарное представление дерева решений

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

Предлагаемое алгоритмическое решение.

Оно вполне очевидно. Каждый узел (структура или класс) должен иметь ссылки на двух потомков Left и Right – аналогичные структуры. Также узел должен содержать идентификатор правила (подробнее о правилах см. ниже), каким либо образом описывать правую часть правила, содержать информацию о количестве или отношении примеров каждого класса обучающей выборки "прошедшей" через узел и иметь признак терминального узла – листа. Таковы минимальные требования к структуре (классу) узла дерева.

Функция оценки качества разбиения

Обучение дерева решений относится к классу обучения с учителем, то есть обучающая и тестовая выборки содержат классифицированный набор примеров. Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения нечистоты (неопределённости) в узле. Рассмотрим задачу с двумя классами и узлом, имеющим по 50 примеров одного класса. Узел имеет максимальную "нечистоту". Если будет найдено разбиение, которое разбивает данные на две подгруппы 40:5 примеров в одной и 10:45 в другой, то интуитивно "нечистота" уменьшится. Она полностью исчезнет, когда будет найдено разбиение, которое создаст подгруппы 50:0 и 0:50. В алгоритме CART идея "нечистоты" формализована в индексе Gini. Если набор данных Т содержит данные n классов, тогда индекс Gini определяется как:

$Gini\,(T) = 1 - \sum\limits_^\ p_i^2$ ,

где p_i – вероятность (относительная частота) класса i в T.

Если набор Т разбивается на две части Т₁ и Т₂ с числом примеров в каждом N₁ и N₂ соответственно, тогда показатель качества разбиения будет равен:

Наилучшим считается то разбиение, для которого Gini_split(T) минимально.

Обозначим N – число примеров в узле – предке, L, R – число примеров соответственно в левом и правом потомке, l_i и r_i – число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:

Чтобы уменьшить объем вычислений формулу можно преобразовать:

Так как умножение на константу не играет роли при минимизации:

В итоге, лучшим будет то разбиение, для которого величина максимальна. Реже в алгоритме CART используются другие критерии разбиения Twoing, Symmetric Gini и др., подробнее см. [1].

Правила разбиения

Вектор предикторных переменных, подаваемый на вход дерева может содержать как числовые (порядковые) так и категориальные переменные. В любом случае в каждом узле разбиение идет только по одной переменной. Если переменная числового типа, то в узле формируется правило вида x_i n-1 – 1). На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него.

Предлагаемое алгоритмическое решение.

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

Каждый шаг построения дерева фактически состоит из совокупности трех трудоемких операций.

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

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

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

Третья операция, занимающая 60–80% времени выполнения программы – вычисление индексов для всех возможных разбиений. Если у Вас n – числовых атрибутов и m – примеров в выборке, то получается таблица n*(m-1) – индексов, которая занимает большой объем памяти. Этого можно избежать, если использовать один столбец для текущего атрибута и одну строку для лучших (максимальных) индексов для всех атрибутов. Можно и вовсе использовать только несколько числовых значений, получив быстрый, однако плохо читаемый код. Значительно увеличить производительность можно, если использовать, что L = N – R, l_i – r_i , а l_i и r_i изменяются всегда и только на единицу при переходе на следующую строку для текущего атрибута. То есть подсчет числа классов, а это основная операция, будет выполняться быстро, если знать число экземпляров каждого класса всего в таблице и при переходе на новую строку таблицы изменять на единицу только число экземпляров одного класса – класса текущего примера.

Все возможные разбиения для категориальных атрибутов удобно представлять по аналогии с двоичным представлением числа. Если атрибут имеет n – уникальных значений. 2 n – разбиений. Первое (где все нули) и последнее (все единицы) нас не интересуют, получаем 2 n – 2. И так как порядок множеств здесь тоже неважен, получаем (2 n – 2)/2 или (2 n-1 – 1) первых (с единицы) двоичных представлений. Если – все возможные значения некоторого атрибута X, то для текущего разбиения, которое имеет представление, скажем получаем правило X in для правой ветви и [ not = = X in ] для левой ветви.

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

Механизм отсечения дерева

Механизм отсечения дерева, оригинальное название minimal cost-complexity tree pruning, – наиболее серьезное отличие алгоритма CART от других алгоритмов построения дерева. CART рассматривает отсечение как получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочной классификации.

Основная проблема отсечения – большое количество всех возможных отсеченных поддеревьев для одного дерева. Более точно, если бинарное дерево имеет |T| – листов, тогда существует ~[1.5028369 |T| ] отсечённых поддеревьев. И если дерево имеет хотя бы 1000 листов, тогда число отсечённых поддеревьев становится просто огромным.

Базовая идея метода – не рассматривать все возможные поддеревья, ограничившись только "лучшими представителями" согласно приведённой ниже оценке.

Обозначим |T| – число листов дерева, R(T) – ошибка классификации дерева, равная отношению числа неправильно классифицированных примеров к числу примеров в обучающей выборке. Определим $C_\,(T)$ – полную стоимость (оценку/показатель затраты-сложность) дерева Т как:

$C_\,(T) = R\,(T)\,+\,\alpha\,*\,|T|$, где |T| – число листов (терминальных узлов) дерева, – некоторый параметр, изменяющийся от 0 до + $\infty$. Полная стоимость дерева состоит из двух компонент – ошибки классификации дерева и штрафа за его сложность. Если ошибка классификации дерева неизменна, тогда с увеличением полная стоимость дерева будет увеличиваться. Тогда в зависимости от менее ветвистое дерево, дающее бОльшую ошибку классификации может стоить меньше, чем дающее меньшую ошибку, но более ветвистое.

Определим T_max – максимальное по размеру дерево, которое предстоит обрезать. Если мы зафиксируем значение $\alpha$, тогда существует наименьшее минимизируемое поддерево $\alpha$, которое выполняет следующие условия:

$C_\Bigl(T\,(\alpha)\Bigr) = min_>\,C_(T)$
$if\,\,C_\,(T) = C_\Bigl(T\,(\alpha)\Bigr)\,then\,\,T\,(\alpha)\leq\,T$

Первое условие говорит, что не существует такого поддерева дерева T_max , которое имело бы меньшую стоимость, чем $T\,(\alpha)$ при этом значении $\alpha$. Второе условие говорит, что если существует более одного поддерева, имеющего данную полную стоимость, тогда мы выбираем наименьшее дерево.

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

Хотя имеет бесконечное число значений, существует конечное число поддеревьев дерева Tmax. Можно построить последовательность уменьшающихся поддеревьев дерева T_max:

(где t₁ – корневой узел дерева) такую, что T_k – наименьшее минимизируемое поддерево для $[\alpha_k,\,\alpha_)$. Это важный результат, так как это означает, что мы можем получить следующее дерево в последовательности, применив отсечение к текущему дереву. Это позволяет разработать эффективный алгоритм поиска наименьшего минимизируемого поддерева при различных значениях $\alpha$. Первое дерево в этой последовательности – наименьшее поддерево дерева T_max имеющее такую же ошибку классификации, как и T_max, т.е. $T_1 = T(\alpha=0)$. Пояснение: если разбиение идет до тех пор, пока в каждом узле останется только один класс, то T₁ = T_max, но так как часто применяются методы ранней остановки (prepruning), тогда может существовать поддерево дерева T_max имеющее такую же ошибку классификации.

Предлагаемое алгоритмическое решение.

Алгоритм вычисления T₁ из T_max прост. Найти любую пару листов с общим предком, которые могут быть объединены, т.е. отсечены в родительский узел без увеличения ошибки классификации. R(t) = R(l) + R(r), где r и l – листы узла t. Продолжать пока таких пар больше не останется. Так мы получим дерево, имеющее такую же стоимость как T_max при = 0, но менее ветвистое, чем T_max.

Как мы получаем следующее дерево в последовательности и соответствующее значение $\alpha$? Обозначим T_t – ветвь дерева Т с корневым узлом t. При каких значениях дерево T – T_t будет лучше, чем Т? Если мы отсечём в узле t, тогда его вклад в полную стоимость дерева T – T_t станет $C_(\) = R\,(t)\,+\,\alpha$, где R(t) = r(t)* p(t), r(t) – это ошибка классификации узла t и p(t) – пропорция случаев, которые "прошли" через узел t. Альтернативный вариант: R(t)= m/n, где m – число примеров классифицированных некорректно, а n – общее число классифицируемых примеров для всего дерева.

Вклад T_t в полную стоимость дерева Т составит $C_(T_t) = R\,(T_t)\,+\,\alpha\,|T_t|$, где

Дерево T – T_t будет лучше, чем Т, когда $C_\<(t\>) = C_\,(T_t)$, потому что при этой величине они имеют одинаковую стоимость, но T – T_t наименьшее из двух. Когда $C_\<(t\>) = C_\,(T_t)$ мы получаем:

решая для $\alpha$, получаем:

Так для любого узла t в Т₁ ,если мы увеличиваем $\alpha$, тогда когда

дерево, полученное отсечением в узле t, будет лучше, чем Т₁.

Основная идея состоит в следующем: вычислим это значение для каждого узла в дереве Т₁, и затем выберем "слабые связи" (их может быть больше чем одна), т.е. узлы для которых величина

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

Алгоритм вычисления последовательности деревьев.

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

Рассмотрим метод подробнее на примере.

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

Очевидно, что Т₁ = Т_max , так как все листы содержат примеры одного класса и отсечение любого узла (t₃ или t₅) приведёт к возрастанию ошибки классификации.
Затем мы вычисляем g₁(t) для всех узлов t в Т₁.

R(t₁) – ошибка классификации. Если превратить t₁ в лист, то следует сопоставить ему какой либо класс; так как число примеров обоих классов одинаково (равно 100), то класс выбираем наугад, в любом случае он неправильно классифицирует 100 примеров. Всего дерево обучалось на 200 примеров (100+100=200 для корневого узла). R(t₁) = m/n. m=100, n=200. R(t₁) = 1/2.

$R\,(T_1,\,t_1)$– сумма ошибок всех листов поддерева. Считается как сумма по всем листам отношений количества неправильно классифицированных примеров в листе к общему числу примеров для дерева. В примере все делим на 200. Так как для поддерева с корнем в t₁ оно же дерево Т₁ все листы не имеют неправильно классифицированных примеров, поэтому

$|T_1,\,t_1|$ количество листов поддерева с корнем в узле t₁. Итого их – 5.

Узлы t₃ и t₅ оба хранят минимальное значение g₁, мы получаем новое дерево Т₂, обрезая Т₁ в обоих этих узлах. Мы получили дерево изображенное на рис.2.

Далее мы продолжаем вычислять g-значение для Т₂.

g₂(t₁) = (100/200 – (0/200 + 10/200 + 10/200)) / (3 – 1) = 2/10.

Минимум хранится в узле t₁, поэтому мы обрезаемы в t₁ и получаем корень дерева (T₃ = 1>). На этом процесс отсечения заканчивается.

Последовательность значений получается: $\alpha$₁ = 0, $\alpha$₂ = 1/20, $\alpha$₃ = 2/10. Итак, Т₁ является лучшим деревом для [0, 1/20), T₂ – для [1/20, 2/10) и Т₃ = 1> для [2/10, $\infty$).

Выбор финального дерева

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

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

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

Данные состоят из 1797 объектов для каждого из которых заданы 64 признака и соответсвующие метки классов:

Попробуем нарисовать чиселки из датасета.

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

Хорошо, теперь можно приступать к обучению. Сначала начинам с дерева решения.

Создайте DecisionTreeClassifier с настройками по умолчанию и измерьте качество его работы с помощью cross_val_score.

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

Получили примерно 82 процента точности что в принципе неплохо и по некоторым картинкам не совсем понятно какое число изображено. Идем дальше.

Воспользуйтесь BaggingClassifier из sklearn.ensemble, чтобы обучить бэггинг над DecisionTreeClassifier. Используйте в BaggingClassifier параметры по умолчанию, задав только количество деревьев равным 100.

У нас уже есть решающее дерево и нам нужно обучить беггинг над ним. Вспомним, что беггинг это среднее значение всех алгоритмов на бутстрепе подвыборок. Значит нам нужно создать класс BaggingClassifier и передать ему в параметры дерево решений. Так и сделаем

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

Теперь изучите параметры BaggingClassifier и выберите их такими, чтобы каждый базовый алгоритм обучался не на всех d признаках, а на $\sqrt$ случайных признаков.

Сейчас нужно выбрать $\sqrt$ для построения всего дерева за что отвечает параметр max_features

Качество чуть выросло, но тут мы использовали рандомную выборку из $\sqrt$ признаков для построения всего дерева. Теперь нужно будет использовать рандомные $\sqrt$ признаков для построения каждого ветвления.

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

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

Полученный в пункте 4 классификатор - бэггинг на рандомизированных деревьях (в которых при построении каждой вершины выбирается случайное подмножество признаков и разбиение ищется только по ним). Это в точности соответствует алгоритму Random Forest, поэтому почему бы не сравнить качество работы классификатора с RandomForestClassifier из sklearn.ensemble. Сделайте это, а затем изучите, как качество классификации на данном датасете зависит от количества деревьев, количества признаков, выбираемых при построении каждой вершины дерева, а также ограничений на глубину дерева. Для наглядности лучше построить графики зависимости качества от значений параметров

Давайте сначала оценим работу RF от количества деревьев.

Интересные получились результаты. Во первых, так как мы не ограничивали деревья в глубину, то алгоритм долго работал на тестовом датасете. Во вторых, средняя точность при разном кол-ве деревьев такая же, как и в случае беггинга на рандомных признаках, что и показывает применение всей вышеизложенной теории. А что касается зависимости точности от кол-ва деревьев, то судя по графику можно смело сказать, что алгоритм выходит на константу и дальнейшее увеличение деревьев не влияет на результат (вообще у меня сильно зависит от random_state). Посмотрим теперь как зависит качество от кол-ва рандомных признаков.

Интересно, что предположение о том, что нужно брать где то $\sqrt$ рандомных признаков неплохо подтверждается. У класса RandomForestClassifier параметр max_features по умолчанию стоит auto, и алгоритм сам решает, какой ему выбрать. Теперь посмотрим глубину дерева.

Из графика видно, что чем больше глубина, тем больше точность предсказания. Но у нас время обучения значительно упало.

Итак, теперь можно ответить на вопросы в задании:

1) Случайный лес сильно переобучается с ростом количества деревьев

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

2) При очень маленьком числе деревьев (5, 10, 15), случайный лес работает хуже, чем при большем числе деревьев

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

3) С ростом количества деревьев в случайном лесе, в какой-то момент деревьев становится достаточно для высокого качества классификации, а затем качество существенно не меняется.

Да, это в точности отражено на графике.

4) При большом количестве признаков (для данного датасета - 40, 50) качество классификации становится хуже, чем при малом количестве признаков (5, 10). Это связано с тем, что чем меньше признаков выбирается в каждом узле, тем более различными получаются деревья (ведь деревья сильно неустойчивы к изменениям в обучающей выборке), и тем лучше работает их композиция.

Все абсолютно верно. Чем меньше признаков, тем менее коррелированы становятся деревья. Но надо понимать, что слишком малое кол-во признаков не позволит “поймать” зависимость в данных.

5) При большом количестве признаков (40, 50, 60) качество классификации лучше, чем при малом количестве признаков (5, 10). Это связано с тем, что чем больше признаков - тем больше информации об объектах, а значит алгоритм может делать прогнозы более точно.

Нет, это не верно. Почему это неверно, написано выше.

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

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

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

Да, это так, что и подтверждают графики выше.

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

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

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

Всего у нас 506 объектов. Мы 25% выборки откладываем на тест. Отлично, теперь можно приступать к заданию. Нужно построить градиентный бустинг для 50 деревьев DecisionTreeRegressor(max_depth=5, random_state=42) на датасете. Из теории мы помним, что каждое новое дерево обучается на антиградиенте ошибки композии по прошлым деревьям. Ошибка в этом случае считается как квадрат отклонения предсказания композиции от истинного ответа. Значит, что бы обучать каждое новое дерево нужно считать градиент квадратичной функции потерь. Далее, после обучения нового дерева его нужно с неким коэффициентом добавить в композицию. После 50 итераций это и будет наш бустинг.

Итак, начнем с производной. Нам нудно найти такой вектор $\bar<\xi>$, чтобы он минимизировал среднеквадратичную ошибку:

\[\sum_^ \mathbb(y_i, a_(x_i) + \xi_i) = \sum_^ (y_i - (a_(x_i) + \xi_i))^2 \to \min_<\xi>.\]

Этот вектор будет равен вектору антиградиента, где каждая компонента это частная производная по $\xi_i$ (знак + потому что антиградиент уже учтен):

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

Для каждого элемента в выборке $X$ считается сумма предсказаний алгоритма algo из массива алгоритмов base_algorithms_list вместе коэффициентами из массива coefficients_list. Что бы нам посчитать градиенты, нам нужны ответы и предсказания композиции для прошлого шага. Так и запишем (двойка в производной опущена по рекомендации):

Эта функция будет возвращать пересчитанный антиградиент композиции. Теперь нужно обучить 50 деревьев на этих градиентах:

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

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

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

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

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

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

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

Алгоритм построения дерева решений

Главный вопрос – как выбирать атрибуты. В соответствии с идеей подхода, когда в концевых узлах дерева (листьях) будет искомый нами класс целевого атрибута, необходимо, чтобы при разбиении набора данных в каждом узле получавшиеся наборы данных были все более однородны в плане значений классов (например, большинство объектов в наборе принадлежало бы к классу Арбуз). И необходимо определить количественный критерий, чтобы оценить однородность разбиения.

Энтропия

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

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

Где values(A) – все принимаемые значения атрибута A, Xa – подмножество набора данных, где A = a, |X| – количество элементов во множестве. Данная величина описывает ожидаемое уменьшение энтропии после разбиения набора данных по выбранному атрибуту. Второе слагаемое – это сумма энтропий для каждого подмножества, взятая со своим весом. Общая разница описывает, как уменьшится энтропия, сколько мы сэкономим бит для кодирования класса случайного объекта из набора X, если мы знаем значения атрибута A и разобьем набор данных на подмножества по данному атрибуту.

Алгоритм выбирает атрибут, соответствующий максимальному значению прироста информации.

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

Процесс останавливается, когда созданные подмножества стали достаточно однородны (преобладает один класс), а именно когда max(Gain(X,A)) становится меньше некоторого заданного параметра Θ (величина, близкая к 0). Как альтернативный вариант, можно контролировать само множество X, и когда оно стало достаточно мало или стало полностью однородным (только один класс), останавливать процесс.

Читайте также: