Выбрать решение по указанному дереву вариантов

Добавил пользователь Дмитрий К.
Обновлено: 19.09.2024

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

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

Дерево решений состоит из следующих элементов: дуг, узлов решений, узлов событий и конечных узлов (исходов).

Рассмотрим сначала простейший пример применения метода дерева решений и решим следующую задачу.

Пример 1. Решить методом дерева решений, какую сумму вы потратите на продукты в определённый день.

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

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

Дерево решений для этой задачи будет следующим:

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

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

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

Продолжим двигаться к более сложным примерам. Определим дерево решений более подробно. Дерево решений строится в виде графа-дерева, обладающего следующими свойствами:

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

Анализ дерева решений

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

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

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

Строительная фирма собирается принять решение о строительстве жилого комплекса (ЖК) в элитном районе. Сначала требуется принять решение: проводить ли информационно-рекламную кампанию. Она стоит 500000 условных единиц (у.е.). Опыт показывает, что лишь в 25 % случаев этот шаг обеспечивает успех на рынке.

Если информационно-рекламная кампания успешна, требуется принять решение: строить ли большой или малый ЖК. Строительство малого ЖК обойдётся в 50000000, при этом можно построить 300 квартир. Строительство большого ЖК обойдётся в 200000000, при этом можно построить 900 квартир.

Имеются исследования прогноза спроса. Они показывают, что существует вероятность в 40 % того, что произойдёт падение спроса на элитное жильё.

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

Большой ЖК	Малый ЖК
Спрос снизится	100 000	150 000
Спрос не снизится	250 000	400 000

Рассчитано, что расходы фирмы перед и в период продажи всех квартир в ЖК составят 5000000, независимо от величины ЖК.

Требуется принять решение: проводить ли информационно-рекламную кампанию и начинать строительство ЖК.

Строим дерево решений:

Последствия альтернативных решений получены при расчётах, которые приведены ниже.

Шаг 1 (не учитываются вероятности событий).

Малый ЖК

Спрос не снизится

Доходы	Расходы	Прибыль
400000 * 300 = 120000000	50000000 + 5000000 = 55000000	120000000 - 55000000 = 65000000

Спрос снизится

Доходы	Расходы	Прибыль
150000 * 300 = 45000000	50000000 + 5000000 = 55000000	45000000 - 55000000 = -10000000

Большой ЖК

Спрос не снизится

Доходы	Расходы	Прибыль
250000 * 900 = 225000000	200000000 + 5000000 = 205000000	225000000 - 205000000 = 20000000

Спрос снизится

Доходы	Расходы	Прибыль
100000 * 900 = 90000000	200000000 + 5000000 = 205000000	90000000 - 205000000 = -115000000

Шаг 2 (учитываются вероятности событий).

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

Теперь следует рассчитать приобретения при вершине 3 дерева решений (проводить информационно-рекламную кампанию). Для этого нужно рассчитать приобретения при вершинах 4 (неуспешная информационно-рекламная кампания) и 5 (успешная информационно-рекламная кампания).

Наступление события при вершине 5 (строительство ЖК) означает максимальную прибыль 35000000, которую только можно получить при выборе данного решения. Наступление события при вершине 4 (неуспешная информационно-рекламная кампания) означает убытки в 500000.

Теперь можно рассчитать приобретения при вершине 3 дерева решений (проводить информационно-рекламную кампанию): 0,25 * 35000000 + 0,75 * (-500000) = 8750000 - 375000 = 8375000.

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

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

Дерево игры

Дерево игры очень похоже на дерево решений.

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

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

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

Пример 4. Число, связанное с каждым ходом, указывает, какой игрок делает выбор на данном ходе. Следовательно, если имеется n игроков, то будут употребляться числа от 1 до n. Пусть n=4, тогда каждый ход, за исключением первого, назначается одному из игроков. Первому ходу приписывается обозначение "0". Ход с обозначением "0" является случайным ходом, как, например, тасовка карт перед партией покера. С каждым случайным ходом, который необязательно должен быть первым ходом, нужно связать распределение вероятностей или весов по нескольким альтернативным выборам. Если случайным ходом является бросание уравновешенной монеты, то в ходе имеются две альтернативы, и каждая из них может осуществиться с вероятностью 1/2.

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

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

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

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

Любая математическая модель предполагает наличие объектов и взаимосвязей между ними.

Сформулируем основные принципы моделирования.

Выбор модели существенно влияет на процесс решения задачи и на само решение.
Степени детализации модели могут быть разными.
Более подробная детализация означает бОльшую сложность модели.
Лучшие модели - те, которые лучше отображают реальность.
Желательно использовать одновременно несколько моделей.

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

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

Есть два условия создания эффективной математической модели системы в виде графа:

определены важнейшие подсистемы или состояния моделируемой системы, которые отображаются в виде вершин графа;
определены важнейшие отношения между объектами-вершинами.

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

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

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

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

Виды математических моделей в виде графа

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

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

Некоторые преимущества деревьев решений:

Просто понять и интерпретировать. Деревья можно визуализировать.
Требуется небольшая подготовка данных. Другие методы часто требуют нормализации данных, создания фиктивных переменных и удаления пустых значений. Однако обратите внимание, что этот модуль не поддерживает отсутствующие значения.
Стоимость использования дерева (т. Е. Прогнозирования данных) является логарифмической по количеству точек данных, используемых для обучения дерева.
Может обрабатывать как числовые, так и категориальные данные. Однако реализация scikit-learn пока не поддерживает категориальные переменные. Другие методы обычно специализируются на анализе наборов данных, содержащих только один тип переменных. См. Алгоритмы для получения дополнительной информации.
Способен обрабатывать проблемы с несколькими выходами.
Использует модель белого ящика. Если данная ситуация наблюдаема в модели, объяснение условия легко объяснить с помощью булевой логики. Напротив, в модели черного ящика (например, в искусственной нейронной сети) результаты могут быть труднее интерпретировать.
Возможна проверка модели с помощью статистических тестов. Это позволяет учитывать надежность модели.
Работает хорошо, даже если его предположения несколько нарушаются истинной моделью, на основе которой были сгенерированы данные.

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

Обучающиеся дереву решений могут создавать слишком сложные деревья, которые плохо обобщают данные. Это называется переобучением. Чтобы избежать этой проблемы, необходимы такие механизмы, как обрезка, установка минимального количества выборок, необходимых для конечного узла, или установка максимальной глубины дерева.
Деревья решений могут быть нестабильными, поскольку небольшие изменения в данных могут привести к созданию совершенно другого дерева. Эта проблема смягчается за счет использования деревьев решений в ансамбле.
Как видно из рисунка выше, предсказания деревьев решений не являются ни гладкими, ни непрерывными, а являются кусочно-постоянными приближениями. Следовательно, они не годятся для экстраполяции.
Известно, что проблема обучения оптимальному дереву решений является NP-полной с точки зрения нескольких аспектов оптимальности и даже для простых концепций. Следовательно, практические алгоритмы обучения дереву решений основаны на эвристических алгоритмах, таких как жадный алгоритм, в котором локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать возврат глобального оптимального дерева решений. Это можно смягчить путем обучения нескольких деревьев в учащемся ансамбля, где функции и образцы выбираются случайным образом с заменой.
Существуют концепции, которые трудно изучить, поскольку деревья решений не выражают их легко, например проблемы XOR, четности или мультиплексора.
Ученики дерева решений создают предвзятые деревья, если некоторые классы доминируют. Поэтому рекомендуется сбалансировать набор данных перед подгонкой к дереву решений.

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

DecisionTreeClassifier — это класс, способный выполнять мультиклассовую классификацию набора данных.

Как и в случае с другими классификаторами, DecisionTreeClassifier принимает в качестве входных данных два массива: массив X, разреженный или плотный, формы (n_samples, n_features), содержащий обучающие образцы, и массив Y целочисленных значений, формы (n_samples,), содержащий метки классов для обучающих образцов:

После подбора модель можно использовать для прогнозирования класса образцов:

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

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

DecisionTreeClassifier поддерживает как двоичную (где метки — [-1, 1]), так и мультиклассовую (где метки — [0,…, K-1]) классификацию.

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

После обучения вы можете построить дерево с помощью plot_tree функции:

Мы также можем экспортировать дерево в формат Graphviz с помощью export_graphviz экспортера. Если вы используете Conda менеджер пакетов, то Graphviz бинарные файлы и пакет питон может быть установлен conda install python-graphviz .

В качестве альтернативы двоичные файлы для graphviz можно загрузить с домашней страницы проекта graphviz, а оболочку Python установить из pypi с помощью pip install graphviz .

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

Экспортер export_graphviz также поддерживает множество эстетических вариантов, в том числе окраски узлов их класс (или значение регрессии) и используя явные имена переменных и классов , если это необходимо. Блокноты Jupyter также автоматически отображают эти графики встроенными:

В качестве альтернативы дерево можно также экспортировать в текстовый формат с помощью функции export_text . Этот метод не требует установки внешних библиотек и более компактен:

1.10.2. Регрессия

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

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

1.10.3. Проблемы с несколькими выходами

Задача с несколькими выходами — это проблема контролируемого обучения с несколькими выходами для прогнозирования, то есть когда Y — это 2-й массив формы (n_samples, n_outputs) .

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

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

Сохранять n выходных значений в листьях вместо 1;
Используйте критерии разделения, которые вычисляют среднее сокращение для всех n выходов.

Этот модуль предлагает поддержку для задач с несколькими выходами, реализуя эту стратегию как в, так DecisionTreeClassifier и в DecisionTreeRegressor . Если дерево решений соответствует выходному массиву Y формы (n_samples, n_outputs), то итоговая оценка будет:

Вывести значения n_output при predict ;
Выведите список массивов n_output вероятностей классов на predict_proba .

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

1.10.4. Сложность

В общем, время выполнения для построения сбалансированного двоичного дерева составляет $O(n_n_\log(n_))$ и время запроса $O(\log(n_))$. Хотя алгоритм построения дерева пытается генерировать сбалансированные деревья, они не всегда будут сбалансированными. Предполагая, что поддеревья остаются примерно сбалансированными, стоимость на каждом узле состоит из перебора $O(n_)$ найти функцию, обеспечивающую наибольшее снижение энтропии. Это стоит $O(n_n_\log(n_))$ на каждом узле, что приводит к общей стоимости по всем деревьям (суммируя стоимость на каждом узле) $O(n_n_^\log(n_))$

1.10.5. Советы по практическому использованию

Деревья решений имеют тенденцию чрезмерно соответствовать данным с большим количеством функций. Получение правильного соотношения образцов к количеству функций важно, поскольку дерево с небольшим количеством образцов в многомерном пространстве, скорее всего, переоборудуется.
Предварительно рассмотрите возможность уменьшения размерности (PCA, ICA, или Feature selection), чтобы дать вашему дереву больше шансов найти отличительные признаки. поможет лучше понять, как дерево решений делает прогнозы, что важно для понимания важных функций данных.
Визуализируйте свое дерево во время тренировки с помощью export функции. Используйте max_depth=3 в качестве начальной глубины дерева, чтобы понять, насколько дерево соответствует вашим данным, а затем увеличьте глубину.
Помните, что количество образцов, необходимых для заполнения дерева, удваивается для каждого дополнительного уровня, до которого дерево растет. Используйте max_depth для управления размером дерева во избежание переобучения.
Используйте min_samples_split или, min_samples_leaf чтобы гарантировать, что несколько выборок информируют каждое решение в дереве, контролируя, какие разделения будут учитываться. Очень маленькое число обычно означает, что дерево переоборудуется, тогда как большое число не позволяет дереву изучать данные. Попробуйте min_samples_leaf=5 в качестве начального значения. Если размер выборки сильно различается, в этих двух параметрах можно использовать число с плавающей запятой в процентах. В то время как min_samples_split может создавать произвольно маленькие листья, min_samples_leaf гарантирует, что каждый лист имеет минимальный размер, избегая малодисперсных, чрезмерно подходящих листовых узлов в задачах регрессии. Для классификации с несколькими классами min_samples_leaf=1 это часто лучший выбор.

1.10.6. Алгоритмы дерева: ID3, C4.5, C5.0 и CART

Что представляют собой различные алгоритмы дерева решений и чем они отличаются друг от друга? Какой из них реализован в scikit-learn?

ID3 (Iterative Dichotomiser 3) был разработан Россом Куинланом в 1986 году. Алгоритм создает многостороннее дерево, находя для каждого узла (т. Е. Жадным образом) категориальный признак, который даст наибольший информационный выигрыш для категориальных целей. Деревья вырастают до максимального размера, а затем обычно применяется этап обрезки, чтобы улучшить способность дерева обобщать невидимые данные.

C5.0 — это последняя версия Quinlan под частной лицензией. Он использует меньше памяти и создает меньшие наборы правил, чем C4.5, но при этом является более точным.

CART (Classification and Regression Trees — деревья классификации и регрессии) очень похож на C4.5, но отличается тем, что поддерживает числовые целевые переменные (регрессию) и не вычисляет наборы правил. CART строит двоичные деревья, используя функцию и порог, которые дают наибольший прирост информации в каждом узле.

scikit-learn использует оптимизированную версию алгоритма CART; однако реализация scikit-learn пока не поддерживает категориальные переменные.

1.10.7. Математическая постановка

Данные обучающие векторы $x_i \in R^n$, i = 1,…, l и вектор-метка $y \in R^l$ дерево решений рекурсивно разбивает пространство признаков таким образом, что образцы с одинаковыми метками или аналогичными целевыми значениями группируются вместе.

Пусть данные в узле m быть представлен $Q_m$ с участием $N_m$ образцы. Для каждого раскола кандидатов $\theta = (j, t_m)$ состоящий из функции $j$ и порог $t_m$, разделите данные на $Q_m^(\theta)$ а также $Q_m^(\theta)$ подмножества
$$Q_m^(\theta) = <(x, y) | x_j predict_proba для этого региона установлено значение $p_$. Общие меры примеси следующие.

Энтропия:
$$H(Q_m) = — \sum_k p_ \log(p_)$$

Неверная классификация:
$$H(Q_m) = 1 — \max(p_)$$

1.10.7.2. Критерии регрессии

Если целью является непрерывное значение, то для узла m, общими критериями, которые необходимо минимизировать для определения местоположений будущих разделений, являются среднеквадратичная ошибка (ошибка MSE или L2), отклонение Пуассона, а также средняя абсолютная ошибка (ошибка MAE или L1). MSE и отклонение Пуассона устанавливают прогнозируемое значение терминальных узлов равным изученному среднему значению $\bar_m$ узла, тогда как MAE устанавливает прогнозируемое значение терминальных узлов равным медиане $median(y)_m$.

Половинное отклонение Пуассона:
$$H(Q_m) = \frac \sum_ (y \log\frac<\bar_m> — y + \bar_m)$$

Настройка criterion="poisson" может быть хорошим выбором, если ваша цель — счетчик или частота (количество на какую-то единицу). В любом случае, y>=0 является необходимым условием для использования этого критерия. Обратите внимание, что он подходит намного медленнее, чем критерий MSE.

Обратите внимание, что он подходит намного медленнее, чем критерий MSE.

1.10.8. Обрезка с минимальными затратами и сложностью

Сокращение с минимальными затратами и сложностью — это алгоритм, используемый для сокращения дерева во избежание чрезмерной подгонки, описанный в главе 3 [BRE] . Этот алгоритм параметризован $\alpha\ge0$ известный как параметр сложности. Параметр сложности используется для определения меры затрат и сложности, $R_\alpha(T)$ данного дерева $T$:
$$R_\alpha(T) = R(T) + \alpha|\widetilde|$$

где $|\widetilde|$ количество конечных узлов в $T$ а также $R(T)$ традиционно определяется как общий коэффициент ошибочной классификации конечных узлов. В качестве альтернативы scikit-learn использует взвешенную общую примесь конечных узлов для $R(T)$. Как показано выше, примесь узла зависит от критерия. Обрезка с минимальными затратами и сложностью находит поддеревоT что сводит к минимуму $R_\alpha(T)$.

Оценка сложности стоимости одного узла составляет $R_\alpha(t)=R(t)+\alpha$. Ответвление $T_t$, определяется как дерево, в котором узел $t$ это его корень. В общем, примесь узла больше, чем сумма примесей его конечных узлов, $R(T_t) ccp_alpha параметра.

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

Этот пример хорошо демонстрирует дерево решений в реальной жизни. Мы построили дерево и смоделировали ряд последовательных, иерархических решений, которые, в конечном итоге, приводят к некоторому результату. Обратите внимание, что мы выбрали максимально общие варианты решения, чтобы дерево было маленьким. Дерево будет просто огромным, если мы установить много возможных вариантов погоды, например: 25 градусов, солнечно; 25 градусов, дождливо; 26 градусов, солнечно; 26 градусов, дождливо; 27 градусов, солнечно; 27 градусов, дождливо и т.д. Конкретная температура не важна. Нам нужно лишь знать, будет ли погода хорошей или нет.

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

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

Индукция

Индукция дерева решений проходит 4 главных этапа построения:

Первый этап простой. Просто соберите свой набор данных!

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

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

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

Где pk — это доля обучающих примеров класса k в определенном узле прогнозирования. В идеале узел должен иметь значение ошибки, равное нулю, означающее, что каждое разбиение выводит один класс 100% времени. Это именно то, что нам нужно, так как добравшись до конкретно этого узла принятия решения, мы будем знать, каким будет вывод в зависимости от того, на какой стороне границы мы находимся.

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

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

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

Отсечение

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

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

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

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

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

Кроме того, в Scikit-learn можно указать несколько параметров для модели дерева решений. Ниже приведем некоторые из таких параметров, позволяющих получить лучший результат:

max_depth: максимальная глубина дерева — точка, на которой останавливается разбиение узлов. Это похоже на выбор максимального количества слоев в глубокой нейронной сети. Меньшее количество сделает модель быстрой, но не точной. Большее количество увеличивает точность, но создает риски переобучения и замедляет процесс.
min_samples_split: необходимое минимальное количество выборок для разбиения узлов. Мы уже обсуждали это выше вместе с тем, как настроить высокое значение, чтобы минимизировать переобучение.
max_features: число признаков для поиска лучшей точки для разбиения. Чем больше число, тем лучше результат. Но в этом случае обучение займет больше времени.
min_impurity_split: порог для ранней остановки роста дерева. Узел разобьется только в том случае, если его точность будет выше указанного порога. Такой метод может служить в качестве компромисса между минимизацией переобучения (высокое значение, маленькое дерево) и высокой точностью (низкое значение, большое дерево).
presort: выбор того, нужно ли предварительно сортировать данные для ускорения поиска наилучшего разбиения при подборе. Если данные заранее отсортируются по каждому признаку, то алгоритму обучения будет гораздо проще найти хорошие значения для разбиения.

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

Как увидеть лес за деревьями: что такое Decision Tree и зачем это нужно в Big Data

Автор Анна Вичугова Категория Use Cases, Статьи, Цифровая трансформация

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

Как растут деревья решений: базовые основы

Начнем с определения: дерево решений – это математическая модель в виде графа, которая отображает точки принятия решений, предшествующие им события и последствия. Этот метод Data Mining широко используется в машинном обучении, позволяя решать задачи классификации и регрессии [1].

Аналитические модели в виде деревьев решений более вербализуемы, интерпретируемы и понятны человеку, чем другие методы Machine Learning, например, нейронные сети. Дополнительное достоинство Decision Tree – это быстрота за счет отсутствия этапа подготовки данных (Data Preparation), поскольку не нужно очищать и нормализовать датасет [2].

В бизнес-анализе, менеджменте и экономике Decision Tree – это отличный инструмент для наглядного отображения всех возможных альтернатив (сценариев), прогнозирования будущих событий, а также оценки их потенциальной выгоды и рисков. Для этого дерево решений представляют в виде графической схемы, чтобы его проще воспринимать и анализировать. Данный граф состоит из следующих элементов [3]:

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

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

Строим дерево решений на примере обучения Big Data

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

поручить каждому сотруднику самостоятельно освоить нужные подходы, фреймворки и языки программирования в свободное от работы время. Фактические затраты на реализацию такого решения равны нулю, а вероятность успешного освоения технологии для быстрого выпуска продукта оценивается на уровне 30%.
выделить w рабочих дней на самостоятельное обучение каждого сотрудника на его рабочем месте. Фактические затраты на реализацию такого решения составляют стоимость рабочего дня каждого сотрудника в день (Z), умноженное на количество дней (w) и число сотрудников (k). Успех ожидается в 50% случаев.
организовать корпоративное обучение всех сотрудников в специализированном учебном центре в течении n дней. Затраты на обучения составят совокупную стоимость курсов (Y), а также цену рабочего дня каждого сотрудника в день (Z)*количество дней (n)*число сотрудников (k). При этом сотрудники освоят технологию с вероятностью 98% за n дней (n

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

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

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

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

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

Энтропия

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

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

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

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

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

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

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