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


Что такое дерево решений и где его используют? — Личный опыт на vc.ru

Ребята, привет! Сегодня команда ProductStar подготовила для вас статью, в которой мы рассмотрели общие принципы работы и области применения дерева решений.

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

Дерево решений представляет собой иерархическую древовидную структуру, состоящую из правила вида «Если …, то ...». За счет обучающего множества правила генерируются автоматически в процессе обучения.

В отличие от нейронных сетей, деревья как аналитические модели проще, потому что правила генерируются на естественном языке: например, «Если реклама привела 1000 клиентов, то она настроена хорошо».

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

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

Дерево решений для принятия решений

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

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

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

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

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

Проблема Stygian Chemical, даже слишком упрощенная, иллюстрирует неопределенности и проблемы, которые руководство бизнеса должно решать при принятии инвестиционных решений.(Я использую термин «инвестиции» в широком смысле, имея в виду затраты не только на новые заводы и оборудование, но и на крупные и рискованные заказы, специальные маркетинговые объекты, исследовательские программы и другие цели.) Эти решения становятся все более важными в в то же время, когда они усложняются. Бесчисленное количество руководителей хотят сделать их лучше, но как?

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

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

Отображение альтернатив

Предположим, что это довольно пасмурное субботнее утро, а днем ​​к вам на коктейли приходят 75 человек. У вас красивый сад, и ваш дом не слишком большой; поэтому, если позволяет погода, вы бы хотели приготовить закуски в саду и устроить там вечеринку. Так было бы приятнее, и вашим гостям было бы комфортнее.С другой стороны, если вы устроите вечеринку в саду, и после того, как все гости будут собраны, начнется дождь, закуски испортятся, ваши гости промокнут, и вы от всей души пожалеете, что решили устроить вечеринку. в доме. (Мы могли бы усложнить эту проблему, рассмотрев возможность частичной приверженности тому или иному курсу и возможности корректировать оценки погоды в течение дня, но простая проблема - это все, что нам нужно.)

Это конкретное решение можно представить в виде таблицы «выплат»:

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

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

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

Приложение I. Схема принятия решений для коктейльной вечеринки

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

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

Цепочки принятия решений

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

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

Приложение II. Дерево решений с цепочками действий и событий

Ваше первоначальное решение показано слева. После принятия решения о продолжении проекта, если разработка будет успешной, это второй этап принятия решения в пункте A. Если не произойдет никаких серьезных изменений в ситуации с настоящего момента до момента достижения пункта A, вы решаете сейчас, какие альтернативы будут важны для вас. в это время.Справа от дерева представлены результаты различных последовательностей решений и событий. Эти результаты также основаны на вашей текущей информации. Фактически вы говорите: «Если то, что я знаю сейчас, правда, то вот что произойдет».

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

Добавление финансовых данных

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

Приложение III. Решения и события для Stygian Chemical Industries, Ltd.

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

1. Крупный завод с большими объемами производства будет приносить денежный поток в размере 1 000 000 долларов в год.

2. Большой завод с малым объемом производства принесет всего 100 000 долларов из-за высоких постоянных затрат и неэффективности.

3. Небольшой завод с низким спросом будет экономичным и принесет годовой денежный доход в размере 400 000 долларов.

4. Небольшой завод в начальный период высокого спроса будет давать 450 000 долларов в год, но в долгосрочной перспективе этот показатель упадет до 300 000 долларов в год из-за конкуренции.(Рынок будет больше, чем при альтернативе 3, но будет разделен между большим количеством конкурентов.)

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

6. Если небольшой завод был расширен, но высокий спрос не поддерживался, расчетный годовой денежный поток составил бы 50 000 долларов.

Когда вышеупомянутые данные включены, у нас есть дерево решений, показанное в Приложении IV. Имейте в виду, что здесь не показано ничего, о чем руководители Stygian Chemical не знали раньше; никаких цифр из шляп не вытащили. Тем не менее, мы начинаем видеть убедительные доказательства ценности деревьев решений в , излагающих то, что знает руководство, таким образом, чтобы сделать возможным более систематический анализ и привести к лучшим решениям.Обобщая требования к созданию дерева решений, руководство должно:

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

2. Определите точки неопределенности и тип или диапазон альтернативных результатов в каждой точке.

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

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

Приложение IV. Дерево решений с финансовыми данными

Выбор курса действий

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

Конечно, прибыль нужно рассматривать вместе с рисками. В Stygian Chemical, как и во многих корпорациях, менеджеры имеют разные точки зрения на риск; следовательно, они сделают разные выводы в обстоятельствах, описанных в дереве решений, показанном в Приложении IV. Многие люди, участвующие в принятии решения - те, кто предоставляет капитал, идеи, данные или решения и имеют разные ценности, подверженные риску, - по-разному увидят неопределенность, окружающую это решение. Если эти различия не будут признаны и устранены, те, кто должен принять решение, заплатить за него, предоставить ему данные и проанализировать его, и жить с ним, будут судить о проблеме, релевантности данных, необходимости анализа и критерии успеха в различных и противоречивые пути.

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

Наличие множества неустановленных и противоречащих друг другу целей, безусловно, внесет свой вклад в «политику» решения Stygian Chemical, и можно быть уверенным, что политический элемент существует всякий раз, когда затрагиваются жизни и амбиции людей. Здесь, как и в аналогичных случаях, неплохо было бы подумать, кто является сторонами инвестиционного решения, и попытаться сделать эти оценки:

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

Концепция «Откат»

Вот как работает откат в описанной ситуации. Во время принятия Решения №1 (см. Приложение IV), руководство не обязано принимать Решение №2 и даже не знает, будет ли у него возможность это сделать. Но если бы были , чтобы иметь возможность в Решении № 2, компания расширила бы завод с учетом своих текущих знаний.Анализ показан в Приложении V. (на данный момент я проигнорирую вопрос дисконтирования будущей прибыли; он будет представлен позже). Мы видим, что общая ожидаемая стоимость альтернативы расширения на 160 000 долларов больше, чем альтернатива без расширения, сверх оставшаяся восьмилетняя жизнь. Следовательно, это альтернативный вариант, который руководство выбрало бы, если бы столкнулось с Решением № 2 с имеющейся информацией (и думая только о денежной прибыли в качестве стандарта выбора).

Приложение V. Анализ возможного решения № 2 (с использованием максимального ожидаемого общего денежного потока в качестве критерия)

Читатели могут задаться вопросом, почему мы начали с Решения №2, когда сегодняшняя проблема - Решение №1.Причина заключается в следующем: мы должны иметь возможность оценить Решение № 2 в денежном выражении, чтобы «откатиться» к Решению № 1 и сравнить выигрыш от перехода на нижнюю ветвь («Строить малый завод») с выигрышем. от взятия верхней ветви («Построй большой завод»). Назовем это денежное выражение для Решения №2 его значением позиции . Значение позиции решения - это ожидаемая стоимость предпочтительной ветви (в данном случае вилки расширения предприятия). Ожидаемое значение - это просто своего рода среднее значение результатов, которых вы ожидали бы, если бы вы повторяли ситуацию снова и снова - получение доходности в размере 5600 тысяч долларов в 86% случаев и доходности в 400 тысяч долларов в 14% случаев.

Другими словами, Stygian Chemical стоит 2 672 тысячи долларов, чтобы добраться до позиции, на которой она сможет принять Решение № 2. Возникает вопрос: с учетом этого значения и других данных, показанных в Приложении IV, что теперь кажется лучшим действием в Решении №1?

Обратитесь к приложению VI. Справа от ветвей в верхней половине мы видим урожайность для различных событий, если будет построен большой завод (это просто числа в Приложении IV, умноженные на них). В нижней половине мы видим данные о малых предприятиях, включая значение позиции в Решении №2 плюс урожайность за два года до принятия Решения №2.Если уменьшить все эти урожаи на их вероятности, мы получим следующее сравнение:

Построить большой завод: (10 × 0,60 доллара) + (2,8 × 0,10 доллара) + (1 доллар × 0,30) - 3 доллара = 3600 тысяч долларов

Построить небольшой завод: (3,6 доллара × 0,70) + (4 доллара × 0,30) - 1,3 доллара = 2400 тысяч долларов

Приложение VI. Анализ движения денежных средств для решения № 1

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

Учет времени

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

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

Для простоты предположим, что ставка дисконтирования 10% в год для всех стадий определяется руководством Stygian Chemical. Применяя принцип отката, мы снова начинаем с Решения №2. Взяв те же цифры, что и в предыдущих экспонатах, и дисконтировав денежные потоки на уровне 10%, мы получаем данные, показанные в Части А Приложения VII.Обратите внимание, что это текущая стоимость на момент принятия Решения № 2 .

Приложение VII. Анализ Решения № 2 с дисконтированием Примечание: для простоты денежный поток за первый год не дисконтируется, денежный поток за второй год дисконтируется через один год и так далее.

Теперь мы хотим пройти ту же процедуру, что и в Приложении V, когда мы получили ожидаемые значения, только на этот раз с использованием значений дисконтированной доходности и получения дисконтированного ожидаемого значения.Результаты показаны в Части B Приложения VII. Поскольку дисконтированная ожидаемая стоимость альтернативы без расширения выше, , эта цифра становится на этот раз значением позиции Решения №2.

Сделав это, мы снова возвращаемся к работе над Решением №1, повторяя ту же аналитическую процедуру, что и раньше, только с дисконтированием. Расчеты показаны в Приложении VIII. Обратите внимание, что значение позиции в Решении №2 обрабатывается во время Решения №1, как если бы это была единовременная выплата в конце двух лет.

Приложение VIII. Анализ Решения № 1

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

Альтернативы неопределенности

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

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

Заключение

Питер Ф. Друкер лаконично выразил связь между текущим планированием и будущими событиями: «Долгосрочное планирование не имеет отношения к будущим решениям.Он касается будущего нынешних решений ». 2 Сегодняшнее решение должно быть принято с учетом ожидаемого эффекта, а исход неопределенных событий окажет влияние на будущие ценности и решения. Поскольку сегодняшнее решение закладывает основу для завтрашнего решения, сегодняшнее решение должно уравновешивать экономию с гибкостью; он должен уравновешивать необходимость использования возможностей получения прибыли, которые могут существовать, со способностью реагировать на будущие обстоятельства и потребности.

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

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

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

1. Оптимальные инвестиционные решения: правила действий и критерии выбора (Энглвуд Клиффс, Нью-Джерси, Prentice-Hall, Inc., 1962), стр. 250.

2. «Долгосрочное планирование», Management Science, , апрель 1959 г., стр. 239.

3. Мы ожидаем еще одной статьи мистера Маги в следующем номере. - The Editors

Версия этой статьи появилась в июльском выпуске журнала Harvard Business Review за 1964 год. .

деревьев решений в машинном обучении | Прашант Гупта

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

Как можно представить алгоритм в виде дерева?

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

Изображение взято из wikipedia

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

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

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

Рекурсивное двоичное разделение

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

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

Стоимость разделения

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

Регрессия: сумма (y - прогноз) ²

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

Классификация: G = сумма (pk * (1 - pk))

Оценка Джини дает представление о том, насколько хорошо разбито, насколько смешаны классы ответов в группах, созданных с помощью разбиения.Здесь pk - это доля входов одного и того же класса, присутствующих в определенной группе. Идеальная чистота класса достигается, когда группа содержит все входные данные из одного и того же класса, и в этом случае pk равно 1 или 0 и G = 0, где, поскольку узел, имеющий 50–50 разбиение классов в группе, имеет наихудшую чистоту, поэтому для двоичной классификации у него будет pk = 0,5 и G = 0,5.

Когда прекратить деление?

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

Обрезка

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

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

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

Недостатки CART

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

.

Оцените модели дерева решений с помощью RevoScaleR (сервер машинного обучения)

В этой статье

Функция rxDTree в RevoScaleR соответствует древовидным моделям с использованием алгоритма рекурсивного разделения на основе биннинга. Полученная модель аналогична той, что производится рекомендованным пакетом R rpart .Поддерживаются деревья как классификационного типа, так и деревья регрессионного типа; как и в случае с rpart , разница определяется характером переменной ответа: факторный ответ генерирует дерево классификации; числовой ответ генерирует дерево регрессии.

Алгоритм rxDTree

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

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

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

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

Простое дерево классификации

В предыдущей статье мы сопоставили простую модель логистической регрессии с данными о кифозе rpart. Эту модель легко преобразовать в дерево классификации с использованием rxDTree следующим образом:

  данные ("кифоз", пакет = "rpart") kyphTree <- rxDTree (Kyphosis ~ Возраст + Start + Number, data = kyphosis, cp = 0,01) kyphTree Вызов: rxDTree (формула = Кифоз ~ Возраст + Начало + Число, данные = кифоз, cp = 0,01) Данные: кифоз Количество действительных наблюдений: 81 Количество пропущенных наблюдений: 0 Представление в виде дерева: n = 81 узел), разделение, n, потеря, yval, (yprob) * обозначает конечный узел 1) корень 81 17 отсутствует (0.746 0.20987654) 2) Start> = 8,5 62 6 отсутствует (0,

581 0,09677419) 4) Start> = 14,5 29 0 отсутствует (1.00000000 0,00000000) * 5) Старт <14,5 33 6 отсутствует (0,81818182 0,18181818) 10) Возраст <55 12 0 отсутствует (1.00000000 0.00000000) * 11) Возраст> = 55 21 6 отсутствует (0,71428571 0,28571429) 22) Возраст> = 111 14 2 отсутствует (0,85714286 0,14285714) * 23) Возраст <111 7 3 присутствует (0,42857143 0,57142857) * 3) Старт <8,5 19 8 присутствует (0.42105263 0,57894737) *

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

Модель rxDTree, кажется, подтверждает эти более ранние выводы - для Start <8.5, у 11 из 19 наблюдаемых субъектов развился кифоз, в то время как ни у одного из 29 субъектов с Start> = 14,5 не было. Для остальных 33 испытуемых возраст был основным фактором расщепления, и, как мы наблюдали ранее, возраст от 5 до 9 лет имел самую высокую вероятность развития кифоза.

Возвращенный объект kyphTree является объектом класса rxDTree . Класс rxDTree тесно смоделирован на основе класса rpart , поэтому объекты класса rxDTree имеют наиболее важные компоненты объекта rpart : frame, cptable, splits и т. Д.Однако по умолчанию объекты rxDTree не наследуются от класса rpart . Однако вы можете использовать функцию rxAddInheritance , чтобы добавить наследование rpart к объектам rxDTree .

Простое дерево регрессии

В качестве простого примера дерева регрессии рассмотрим набор данных mtcars и подберем расход топлива ( миль на галлон, ), используя смещение ( disp ) в качестве предиктора:

  # Простое дерево регрессии mtcarTree <- rxDTree (миль на галлон ~ disp, данные = mtcars) mtcarTree Вызов: rxDTree (формула = миль на галлон ~ disp, данные = mtcars) Данные: mtcars Количество действительных наблюдений: 32 Количество пропущенных наблюдений: 0 Представление в виде дерева: n = 32 узел), split, n, отклонение, yval * обозначает конечный узел 1) корень 32 1126.0470 20.09063 2) disp> = 163,5 18 143,5894 15,99444 * 3) disp <163,5 14 292,1343 25,35714 *  

Существует четкое разделение на автомобили большего размера (с объемом двигателя более 163,5 кубических дюймов) и автомобили меньшего размера.

Модель большего дерева регрессии

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

  # Модель дерева регрессии большего размера censusWorkers <- файл.путь (rxGetOption ("sampleDataDir"), "CensusWorkers.xdf") rxGetInfo (censusWorkers, getVarInfo = TRUE) доходTree <- rxDTree (incwage ~ возраст + пол + wkswork1, pweights = "perwt", maxDepth = 3, minBucket = 30000, data = censusWorkers) доходДерево Вызов: rxDTree (формула = заработная плата ~ возраст + пол + работа1, данные = censusWorkers, pweights = "perwt", minBucket = 30000, maxDepth = 3) Файл: C: \ Program Files \ Microsoft \ MRO-for-RRE \ 8.0 \ R-3.2.2 \ library \ RevoScaleR \ SampleData \ CensusWorkers.xdf Количество действительных наблюдений: 351121 Количество пропущенных наблюдений: 0 Представление в виде дерева: n = 351121 узел), split, n, отклонение, yval * обозначает конечный узел 1) корень 351121 1.177765e + 16 35788.47 2) пол = Женский 161777 2.271425e + 15 26721.09 4) wkswork1 <51,5 56874 5,757587e + 14 19717,74 * 5) wkswork1> = 51,5 104903 1.608813e + 15 30505,87 10) возраст <34,5 31511 2,500078e + 14 25836,32 * 11) возраст> = 34,5 73392 1,338235e + 15 32576,74 * 3) пол = Мужской 189344 9.008506e + 15 43472.71 6) возраст <31,5 48449 6.445334e + 14 27577.80 * 7) возраст> = 31,5 140895 8,010642e + 15 49221,82 14) wkswork1 <51,5 34359 1,550839e + 15 37096.62 * 15) wkswork1> = 51,5 106536 6,326896e + 15 53082,08 *  

Основное разделение здесь (неудивительно, учитывая наш анализ этого набора данных в Руководстве: Анализ данных переписи США с помощью RevoScaleR) - это пол; женщины в среднем зарабатывают существенно меньше мужчин. Дополнительные расколы также не удивительны; пожилые работники зарабатывают больше, чем молодые, а те, кто работает больше часов, как правило, зарабатывают больше, чем те, кто работает меньше часов.

Контроль соответствия модели

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

Для больших наборов данных (100000 или более наблюдений) вам может потребоваться настроить следующие параметры для получения значимых моделей:

Модели больших деревьев данных

Масштабирование деревьев решений до очень больших наборов данных возможно с помощью rxDTree , но следует делать это с осторожностью - неправильный выбор параметров модели может легко привести к моделям, оценка которых может занять часы или больше времени, даже в распределенной вычислительной среде. Например, в Учебнике: загрузка и анализ большого набора данных об авиакомпании с помощью RevoScaleR мы оценили линейные модели с использованием данных о крупных авиакомпаниях и использовали переменную Origin в качестве предиктора в нескольких моделях.Переменная Origin - это факторная переменная с 373 уровнями без очевидного порядка. Включение этой переменной в модель rxDTree , которая выполняет более чем двухуровневую классификацию, может легко занять часы вычислительного времени. Чтобы предотвратить такие непредвиденные последствия, rxDTree имеет параметр maxUnorderedLevels , который по умолчанию равен 32; в случае Origin этот параметр помечает ошибку. Однако факторная переменная «Регион», которая группирует аэропорты Origin по местоположению, вполне может быть полезным заместителем и может быть сконструирована так, чтобы иметь только ограниченное количество уровней.Числовые и упорядоченные факторные предикторы гораздо легче включить в модель.

В качестве примера большого дерева классификации данных рассмотрим следующую простую модель, использующую 7% -ную подвыборку полных данных авиакомпании (используется переменная ArrDel15 , указывающая на рейсы с задержкой прибытия 15 минут или более):

  # Модели больших деревьев данных bigDataDir <- "C: / MRS / Data" sampleAirData <- путь к файлу (bigDataDir, "AirOnTime7Pct.xdf") AirlinesTree <- rxDTree (ArrDel15 ~ CRSDepTime + DayOfWeek, data = sampleAirData, blocksPerRead = 30, maxDepth = 5, cp = 1e-5)  

Аргумент blocksPerRead игнорируется, если выполняется локально с использованием R-клиента.Узнать больше ...

Значение cp по умолчанию, равное 0, приводит к очень большому количеству разбиений; указание cp = 1e-5 дает более управляемый набор разделений в этой модели:

  авиакомпанияTree Вызов: rxDTree (формула = ArrDel15 ~ CRSDepTime + DayOfWeek, data = sampleAirData, maxDepth = 5, cp = 1e-05, blocksPerRead = 30) Файл: C: \ MRS \ Data \ AirOnTime7Pct.xdf Количество действительных наблюдений: 10186272 Количество недостающих наблюдений: 213483 Представление в виде дерева: n = 10186272 узел), split, n, отклонение, yval * обозначает конечный узел 1) корень 10186272 1630331.000 0,20008640 2) CRSDepTime <13,1745 4941190 642452,000 0,15361830 4) CRSDepTime <8,3415 1777685 189395.700 0,12123970 8) CRSDepTime> = 0,658 1717573 178594,900 0,11787560 16) CRSDepTime <6,7665 599548 52711.450 0,09740671 32) CRSDepTime> = 1,625 578762 49884,260 0,09526714 * 33) CRSDepTime <1,625 20786 2750,772 0,15698070 * 17) CRSDepTime> = 6.7665 1118025 125497.500 0.12885220 34) DayOfWeek = Вс 134589 11722,540 0.09638975 * 35) DayOfWeek = Пн, Вт, Среда, Чт, Пт, Сб 983436 113613,80 0,13329490 * 9) CRSDepTime <0,658 60112 10225,960 0,21736090 18) CRSDepTime> = 0,2415 9777 1429,046 0,17776410 * 19) CRSDepTime <0,2415 50335 8778,609 0,22505220 * 5) CRSDepTime> = 8,3415 3163505 450145,400 0,17181290 10) CRSDepTime <11,3415 1964400 268472,400 0,16335320 20) DayOfWeek = Вс 271900 30839,160 0,13043400 40) CRSDepTime <9,7415 126700 13381,800 0.12002370 * 41) CRSDepTime> = 9,7415 145200 17431,650 0,13951790 * 21) DayOfWeek = Пн, Вт, Среда, Чт, Пт, Сб 1692500 237291,300 0,16864170 42) DayOfWeek = Вт, Ср, Сб 835355 113384.500 0,16196470 * 43) DayOfWeek = Пн, Чт, Пт 857145 123833.200 0,17514890 * 11) CRSDepTime> = 11,3415 1199105 181302,000 0,18567180 22) DayOfWeek = пн, вт, ср, сб, вс 852016 124610,900 0,17790390 44) DayOfWeek = Вт, Вс 342691 48917,520 0,17250230 * 45) DayOfWeek = пн, ср, сб 509325 75676.600 0,18153830 * 23) DayOfWeek = Thur, Fri 347089 56513,560 0,20474000 * 3) CRSDepTime> = 13,1745 5245082 967158,500 0,24386220 6) DayOfWeek = пн, вт, ср, сб, вс 3708992 651771,300 0,22746990 12) DayOfWeek = Сб 635207 96495,570 0,18681000 24) CRSDepTime> = 20,2745 87013 12025,600 0,16564190 * 25) CRSDepTime <20,2745 548194 84424.790 0,190 * 13) DayOfWeek = пн, вт, ср, вс 3073785 554008.600 0,23587240 26) CRSDepTime <16,508 1214018 203375.700 0,21281150 52) CRSDepTime <15,1325 709846 114523.300 0,20223400 * 53) CRSDepTime> = 15,1325 504172 88661,120 0,22770400 * 27) CRSDepTime> = 16,508 1859767 349565,800 0,25092610 54) DayOfWeek = Пн, Вт 928523 168050,900 0,23729730 * 55) DayOfWeek = ср, вс 931244 181170,600 0,26451500 * 7) DayOfWeek = Thur, Fri 1536090 311984.200 0,28344240 14) CRSDepTime <15,608 445085 82373.020 0,24519140 28) CRSDepTime <14,6825 273682 49360,240 0.23609880 * 29) CRSDepTime> = 14,6825 171403 32954,030 0,25970960 * 15) CRSDepTime> = 15,608 1091005 228694,300 0,29904720 30) CRSDepTime> = 21,9915 64127 11932,930 0,24718140 * 31) CRSDepTime <21,9915 1026878 216578.100 0,30228620 62) CRSDepTime <17.0745 264085 53451.260 0.28182970 * 63) CRSDepTime> = 17.0745 762793 162978.000 0.30936830 *  

Глядя на компонент подгоняемых объектов cptable, мы можем посмотреть, переоборудовали ли мы модель:

  авиакомпанияTree $ cptable Ошибка CP nsplit rel xerror xstd 1 1.270950e-02 0 1.0000000 1.0000002 0.0004697734 2 2,087342e-03 1 0,9872905 0,9873043 0,0004629111 3 1,785488e-03 2 0,9852032 0,9852215 0,0004625035 4 7.772395e-04 3 0.9834177 0.9834381 0.0004608330 5 6.545095e-04 4 0.9826404 0.9826606 0.0004605065 6 5.623968e-04 5 0.9819859 0.9820200 0.0004602950 7 3,525848e-04 6 0,9814235 0,9814584 0,0004602578 8 2.367018e-04 7 0.9810709 0.9811071 0.0004600062 9 2.274981e-04 8 0.9808342 0.9808700 0.0004597725 10 2,112635e-04 9 0,9806067 0,9806567 0,0004596187 11 2.097651e-04 10 0.9803955 0.9804365 0.0004595150 12 1.173008e-04 11 0.9801857 0.9803311 0.0004594245 13 1.124180e-04 12 0.9800684 0.9800354 0.0004592792 14 1.089414e-04 13 0.9799560 0.9800354 0.0004592792 15 9.8e-05 14 0.9798471 0.9799851 0.0004592187 16 9.125152e-05 15 0.9797482 0.9798766 0.0004591605 17 4.687397e-05 16 0.9796569 0.9797504 0.0004591074 18 4.510554e-05 17 0.9796100 0,9797292 0,0004590784 19 3.603837e-05 18 0.9795649 0.9796812 0.00045
20 2.771093e-05 19 0.9795289 0.9796383 0.00045

21 1,577140e-05 20 0,9795012 0,9796013 0,00045

22 1.122899e-05 21 0.9794854 0.9795671 0.0004589736 23 1.025944e-05 22 0.9794742 0.9795560 0.0004589678 24 1.000000e-05 23 0.9794639 0.9795455 0.0004589660

Мы видим устойчивое уменьшение ошибки перекрестной проверки (xerror) по мере увеличения количества разделений, но обратите внимание, что примерно при nsplit = 11 скорость изменения резко замедляется.Оптимальная модель, наверное, здесь совсем рядом. (Общее количество проходов по данным равно основанию maxDepth + 3, плюс xVal раз ( maxDepth + 2), где xVal - количество складок для перекрестной проверки, а maxDepth - максимальная глубина дерева. Таким образом, дерево глубины 10 с 4-кратной перекрестной проверкой требует 13 + 48, или 61, проходит через данные.)

Чтобы обрезать дерево, используйте функцию prune.rxDTree :

  авиакомпанияTree4 <- чернослив.rxDTree (название авиакомпании, cp = 1e-4) авиакомпанияTree4 Вызов: rxDTree (формула = ArrDel15 ~ CRSDepTime + DayOfWeek, data = sampleAirData, maxDepth = 5, cp = 1e-05, blocksPerRead = 30) Файл: C: \ MRS \ Data \ AirOnTime7Pct.xdf Количество действительных наблюдений: 10186272 Количество недостающих наблюдений: 213483 Представление в виде дерева: n = 10186272 узел), split, n, отклонение, yval * обозначает конечный узел 1) корень 10186272 1630331.00 0.20008640 2) CRSDepTime <13,1745 4941190 642452.00 0,15361830 4) CRSDepTime <8,3415 1777685 189395,70 0,12123970 8) CRSDepTime> = 0,658 1717573 178594,90 0,11787560 16) CRSDepTime <6,7665 599548 52711,45 0,09740671 * 17) CRSDepTime> = 6,7665 1118025 125497,50 0,12885220 * 9) CRSDepTime <0,658 60112 10225,96 0,21736090 * 5) CRSDepTime> = 8,3415 3163505 450145,40 0,17181290 10) CRSDepTime <11,3415 1964400 268472,40 0,16335320 20) DayOfWeek = вс 271900 30839,16 0,13043400 * 21) DayOfWeek = пн, вт, ср, чт, пт, сб 1692500 237291.30 0,16864170 * 11) CRSDepTime> = 11,3415 1199105 181302,00 0,18567180 22) DayOfWeek = пн, вт, ср, сб, вс 852016 124610,90 0,17790390 * 23) DayOfWeek = Thur, Fri 347089 56513,56 0,20474000 * 3) CRSDepTime> = 13,1745 5245082 967158,50 0,24386220 6) DayOfWeek = пн, вт, ср, сб, вс 3708992 651771.30 0,22746990 12) DayOfWeek = Сб 635207 96495,57 0,18681000 * 13) DayOfWeek = пн, вт, ср, вс 3073785 554008,60 0,23587240 26) CRSDepTime <16,508 1214018 203375.70 0,21281150 52) CRSDepTime <15,1325 709846 114523,30 0,20223400 * 53) CRSDepTime> = 15,1325 504172 88661,12 0,22770400 * 27) CRSDepTime> = 16,508 1859767 349565,80 0,25092610 54) DayOfWeek = Пн, Вт 928523 168050,90 0,23729730 * 55) DayOfWeek = ср, вс 931244 181170,60 0,26451500 * 7) DayOfWeek = Thur, Fri 1536090 311984.20 0.28344240 14) CRSDepTime <15,608 445085 82373.02 0,24519140 * 15) CRSDepTime> = 15,608 1091005 228694,30 0,29904720 30) CRSDepTime> = 21.9915 64127 11932,93 0,24718140 * 31) CRSDepTime <21,9915 1026878 216578,10 0,30228620 *  

Если установлен rpart, prune.rxDTree действует как метод для функции prune , поэтому вы можете вызвать его проще:

  airlinesTree4 <- prune (AirlinesTree, cp = 1e-4)  

Для моделей с двукратной или большей перекрестной проверкой полезно использовать стандартную ошибку перекрестной проверки (часть компонента cptable) в качестве руководства по сокращению.Для этого может пригодиться функция rpart plotcp:

  plotcp (rxAddInheritance (AirlinesTree))  

Это дает следующий график:

Из этого графика кажется, что мы можем сократить еще больше, возможно, до семи или восьми делений. Снова посмотрев на cptable, можно увидеть, что cp 2,5e-4 кажется разумным выбором для сокращения:

  airlinesTreePruned <- prune.rxDTree (AirlinesTree, cp = 2.5e-4) авиакомпанияTreePruned Вызов: rxDTree (формула = ArrDel15 ~ CRSDepTime + DayOfWeek, data = sampleAirData, maxDepth = 5, cp = 1e-05, blocksPerRead = 30) Файл: C: \ MRS \ Data \ AirOnTime7Pct.xdf Количество действительных наблюдений: 10186272 Количество недостающих наблюдений: 213483 Представление в виде дерева: n = 10186272 узел), split, n, отклонение, yval * обозначает конечный узел 1) корень 10186272 1630331.00 0.2000864 2) CRSDepTime <13,1745 4941190 642452,00 0,1536183 4) CRSDepTime <8,3415 1777685 189395,70 0,1212397 8) CRSDepTime> = 0,658 1717573 178594,90 0,1178756 * 9) CRSDepTime <0,658 60112 10225,96 0,2173609 * 5) CRSDepTime> = 8,3415 3163505 450145.40 0,1718129 * 3) CRSDepTime> = 13,1745 5245082 967158,50 0,2438622 6) DayOfWeek = пн, вт, ср, сб, вс 3708992 651771.30 0,2274699 12) DayOfWeek = Сб 635207 96495,57 0,1868100 * 13) DayOfWeek = пн, вт, ср, вс 3073785 554008,60 0,2358724 26) CRSDepTime <16,508 1214018 203375,70 0,2128115 * 27) CRSDepTime> = 16,508 1859767 349565,80 0,2509261 * 7) DayOfWeek = Thur, Fri 1536090 311984.20 0.2834424 14) CRSDepTime <15,608 445085 82373.02 0,2451914 * 15) CRSDepTime> = 15.608 1091005 228694,30 0,2990472 *  

Обработка отсутствующих значений

Аргумент removeMissings для rxDTree , как и в большинстве функций анализа RevoScaleR, управляет тем, как функция обрабатывает недостающие данные в соответствии с моделью. Если ИСТИНА , все строки, содержащие отсутствующие значения для ответа или любую переменную-предиктор, удаляются перед подгонкой модели. Если FALSE (по умолчанию), удаляются только те строки, для которых значение ответа или все значения переменных-предикторов отсутствуют.Использование removeMissings = TRUE примерно эквивалентно эффекту функции na.omit для rpart , в том смысле, что если файл записан, все строки, содержащие NA, удаляются. Для rxDTree нет эквивалента функции na.exclude , которая дополняет вывод НА для наблюдений, которые невозможно предсказать. Использование removeMissings = FALSE эквивалентно использованию функций na.rpart или na.pass ; данные передаются без изменений, но строки, в которых нет данных ни для всех предикторов, ни для ответа, исключаются из модели.

Прогноз

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

Набор данных для взрослых - это широко используемый набор данных машинного обучения, аналогичный уже проанализированным нами данным censusWorkers. Набор данных доступен в репозитории данных машинного обучения в UC Irvine (http: // archive.ics.uci.edu/ml/datasets/Adult) (и состоит из двух частей: набора обучающих данных (adult.data) и набора тестовых данных (adult.test). Это делает его готовым для использования в прогнозировании. Чтобы запустить следующие примеры, загрузите эти данные и добавьте расширение .txt, чтобы у вас были adult.data.txt и adult.test.txt. (Третий файл, adult.names, дает описание переменных; мы используем это в приведенном ниже коде в качестве источника имен переменных, которые не являются частью файлов данных):

  # Прогноз if (bHasAdultData) { bigDataDir <- "C: / MRS / Data" adultDataFile <- файл.путь (bigDataDir, "adult.data.txt") adultTestFile <- file.path (bigDataDir, "adult.test.txt") newNames <- c ("возраст", "рабочий класс", "fnlwgt", "образование", «education_num», «marital_status», «профессия», «отношения», "этническая принадлежность", "пол", "capital_gain", "capital_loss", "hours_per_week", "native_country", "доход") adultTrain <- rxImport (adultDataFile, stringsAsFactors = ИСТИНА) имена (adultTrain) <- newNames adultTest <- rxImport (adultTestFile, rowsToSkip = 1, stringsAsFactors = ИСТИНА) имена (adultTest) <- newNames adultTree <- rxDTree (доход ~ возраст + пол + hours_per_week, pweights = "fnlwgt", data = adultTrain) adultPred <- rxPredict (adultTree, data = adultTest, type = "vector") сумма (adultPred == as.целое число (adultTest $ доход)) / длина (adultTest $ доход) } # Конец bHasAdultData [1] 0,7734169  

Результат показывает, что подобранная модель точно классифицирует около 77% тестовых данных.

При использовании rxPredict с объектами rxDTree следует помнить, чем он отличается от predict с объектами rpart . Во-первых, всегда требуется аргумент data - это могут быть либо исходные данные, либо новые данные; нет аргумента newData , как в rpart .Прогнозирование с использованием исходных данных предоставляет подогнанные значения, а не прогнозы, но имя прогнозируемой переменной по-прежнему имеет значение по умолчанию varname_Pred .

Визуализация деревьев

Пакет RevoTreeView можно использовать для построения деревьев решений из rxDTree или rpart на HTML-странице. Поддерживаются деревья классификации и регрессии. Создавая в браузере объекты дерева, возвращаемые функцией RevoTreeView createTreeView , вы можете взаимодействовать со своим деревом решений.HTML-страница результирующего дерева также может быть предоставлена ​​другим людям или отображаться на разных машинах с помощью функции пакета zipTreeView .

В качестве примера рассмотрим классификационное дерево, построенное на основе данных kyphosis , включенных в пакет rpart . Он производит следующий текстовый вывод:

  данные ("кифоз", пакет = "rpart") kyphTree <- rxDTree (Кифоз ~ Возраст + Начало + Число, данные = кифоз, cp = 0,01) kyphTree Вызов: rxDTree (формула = Кифоз ~ Возраст + Начало + Число, данные = кифоз, cp = 0.01) Данные: кифоз Количество действительных наблюдений: 81 Количество пропущенных наблюдений: 0 Представление в виде дерева: n = 81 узел), разделение, n, потеря, yval, (yprob) * обозначает конечный узел 1) корень 81 17 отсутствует (0.746 0.20987654) 2) Start> = 8,5 62 6 отсутствует (0,

581 0,09677419) 4) Start> = 14,5 29 0 отсутствует (1.00000000 0,00000000) * 5) Старт <14,5 33 6 отсутствует (0,81818182 0,18181818) 10) Возраст <55 12 0 отсутствует (1.00000000 0.00000000) * 11) Возраст> = 55 21 6 отсутствует (0.71428571 0,28571429) 22) Возраст> = 111 14 2 отсутствует (0,85714286 0,14285714) * 23) Возраст <111 7 3 присутствует (0,42857143 0,57142857) * 3) Старт <8,5 19 8 присутствует (0,42105263 0,57894737) *

Теперь вы можете отобразить HTML-версию дерева вывода, построив объект, созданный функцией createTreeView . После выполнения предыдущего кода R запустите следующее, чтобы загрузить пакет RevoTreeView и отобразить интерактивное дерево решений в браузере:

  библиотека (RevoTreeView) сюжет (createTreeView (kyphTree))  

В этом интерактивном дереве щелкните узлы кругового разбиения, чтобы развернуть или свернуть ветвь дерева.Щелчок по узлу развернет и свернет узел до последнего вида этой ветви. Если вы используете CTRL + Click , дерево отображает только дочерние элементы выбранного узла. Если вы щелкните ALT + щелкните , в дереве отобразятся все уровни ниже выбранного узла. Узлы квадратной формы, называемые листами или конечными узлами, не могут быть расширены.

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

Вы также можете использовать методы rpart plot и text с объектами rxDTree , если вы используете функцию rxAddInheritance для обеспечения наследования rpart:

  # Рисование деревьев участок (rxAddInheritance (AirlinesTreePruned)) текст (rxAddInheritance (AirlinesTreePruned))  

Предоставляет следующий участок:

.

Классификация и регрессионный анализ с деревьями решений | Лоррейн Ли

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

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

Итак, как нам узнать, какова оптимальная точка разделения на каждом узле?

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

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

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

Здесь f - это функция для выполнения разбиения, Dp , Dleft и Dright - это наборы данных родительского и дочернего узлов, I - это мера примеси , Np - общее количество выборок в родительском узле, а Nleft и Nright - количество выборок в дочерних узлах.

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

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

Мы начнем с обсуждения деревьев решений классификации (также известных как деревья классификации ). В этом примере мы будем использовать набор данных Iris , классический в области машинного обучения. Он содержит размеры 150 Ирис трех разных видов - Setosa , Versicolor и Virginica . Это будут наши цели . Наша цель - предсказать, к какой категории относится цветок Iris .Длина и ширина лепестка в сантиметрах хранятся в виде столбцов, которые мы также называем характеристиками набора данных.

Давайте сначала импортируем набор данных и назначим функции как X и цель как y :

Используя scikit-learn , мы теперь обучим дерево решений с максимальной глубиной 4. Код выглядит следующим образом. следует:

Обратите внимание, что мы установили критерий как « энтропия ». Этот критерий известен как мера примеси (упоминалась в предыдущем разделе).В классификации энтропия является наиболее распространенной мерой примеси или критерием расщепления. Он определяется следующим образом:

Здесь p (i | t) - это доля выборок, принадлежащих классу c для конкретного узла t . Следовательно, энтропия равна 0, если все выборки в узле принадлежат к одному классу, и энтропия максимальна, если у нас есть равномерное распределение классов.

Для более наглядного понимания энтропии, давайте изобразим индекс примеси для диапазона вероятности [0, 1] для класса 1.Код выглядит следующим образом:

Как видите, энтропия равна 0, если p (i = 1 | t) = 1 . Если классы распределены равномерно с p (i = 1 | t) = 0,5 , энтропия равна 1.

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

Хорошей особенностью scikit-learn является то, что он позволяет нам экспортировать дерево решений как файл .dot после обучения, которое мы можем визуализировать, например, с помощью GraphViz.В дополнение к GraphViz мы будем использовать библиотеку Python под названием pydotplus , которая имеет возможности, аналогичные GraphViz, и позволяет нам преобразовывать файлы данных .dot в файл изображения дерева решений.

Вы можете установить pydotplus и graphviz , выполнив следующие команды в своем Терминале:

 pip3 install pydotplus 
apt install graphviz

Следующий код создаст изображение нашего дерева решений в формате PNG:

tree.png

Глядя на получившуюся фигуру дерева решений, сохраненную в файле изображения tree.png , мы можем теперь хорошо отследить разбиения, которые дерево решений определило из нашего обучающего набора данных. Мы начали со 150 образцов в корне и разделили их на два дочерних узла по 50 и 100 образцов, используя ширину лепестка , отсечка ≤ 1,75 см. После первого разделения мы видим, что левый дочерний узел уже является чистым и содержит только образцы из класса setosa (энтропия = 0).Дальнейшие разделения справа затем используются для разделения образцов из классов versicolor и virginica .

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

Мы будем использовать набор данных Boston Housing для нашего примера регрессии. Это еще один очень популярный набор данных, который содержит информацию о домах в пригородах Бостона. Всего 506 образцов и 14 атрибутов.Для простоты и наглядности мы будем использовать только два - MEDV (среднее значение домов, занимаемых владельцами в 1000 долларов) в качестве цели и LSTAT (процент более низкого статуса населения) в качестве функции.

Давайте сначала импортируем необходимые атрибуты из scikit-learn в pandas DataFrame.

Давайте воспользуемся DecisionTreeRegressor , реализованным в scikit-learn для обучения дерева регрессии:

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

Здесь , Nt - количество обучающих выборок в узле t , Dt - обучающее подмножество в узле t , y (i) - истинное целевое значение, а ŷt - прогнозируемое целевое значение. значение (выборочное среднее):

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

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

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

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

.

Смотрите также

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

Содержание, карта сайта.