Дерево решений (Decision Trees)
Дерево решений — классификатор, построенный на основе решающих правил вида «если, то», упорядоченных в древовидную иерархическую структуру.
В основе работы дерева решений лежит процесс рекурсивного разбиения исходного множества объектов на подмножества, ассоциированные с предварительно заданными классами. Разбиение производится с помощью решающих правил, в которых осуществляется проверка значений атрибутов по заданному условию.
Строятся на основе обучения с учителем. В качестве обучающего набора данных используется множество наблюдений, для которых предварительно задана метка класса.
Структурно дерево решений состоит из объектов двух типов — узлов (node) и листьев (leaf). В узлах расположены решающие правила и подмножества наблюдений, которые им удовлетворяют. В листьях содержатся классифицированные деревом наблюдения: каждый лист ассоциируется с одним из классов, и объекту, который распределяется в лист, присваивается соответствующая метка класса.
Визуально узлы и листья в дереве хорошо различимы: в узлах указываются правила, разбивающие содержащиеся в нем наблюдения, и производится дальнейшее ветвление. В листьях правил нет, они помечаются меткой класса, объекты которого попали в данный лист. Ветвление в листьях не производится, и они заканчивают собой ветвь дерева (поэтому их иногда называют терминальными узлами).
Если класс, присвоенный деревом, совпадает с целевым классом, то объект является распознанным, в противном случае — нераспознанным. Самый верхний узел дерева называется корневым (root node). В нем содержится весь обучающий или рабочий набор данных.
Дерево решений является линейным классификатором, т.е. производит разбиение объектов в многомерном пространстве плоскостями (в двумерном случае — линиями).
Дерево, представленное на рисунке, решает задачу классификации объектов по двум атрибутам на три класса.
На рисунке кружки представляют объекты класса 1, квадраты — класса 2, а треугольники — класса 3. Пространство признаков разделено линиями на три подмножества, ассоциированных с классами. Эти же подмножества будут соответствовать и трем возможным исходам классификации. В классе «треугольников» имеются нераспознанные примеры («квадраты»), т.е. примеры, попавшие в подмножества, ассоциированные с другим классом.
Теоретически, алгоритм может генерировать новые разбиения до тех пор, пока все примеры не будут распознаны правильно, т.е. пока подмножества, ассоциированные с листьями, не станут однородными по классовому составу. Однако это приводит к усложнению дерева: большое число ветвлений, узлов и листьев усложняет его структуру и ухудшает его интерпретируемость. Поэтому на практике размер дерева ограничивают даже за счет некоторой потери точности. Данный процесс называется упрощением деревьев решений и может быть реализован с помощью методов ранней остановки и отсечения ветвей.
Деревья решений являются жадными алгоритмами. Могут быть дихотомичными (бинарными), имеющими только два потомка в узле, и полихотомичными — имеющими более 2-х потомков в узле. Дихотомичные деревья являются более простыми в построении и интерпретации.
В настоящее время деревья решений стали одним из наиболее популярных методов классификации в интеллектуальном анализе данных и бизнес-аналитике. Поэтому они входят в состав практически любого аналитического ПО.
Разработано большое количество различных алгоритмов построения деревьев решений. Наиболее известным является семейство алгоритмов, основанное на критерии прироста информации (information gain) — ID3, C4.5, С5.0, — предложенное Россом Куинленом в начале 1980-х.
Также широкую известность приобрел алгоритм CART (Classification and Regression Tree — дерево классификации и регрессии), который, как следует из названия, позволяет решать не только задачи классификации, но и регрессии. Алгоритм предложен Лео Брейманом в 1982 г.
Широкая популярность деревьев решений обусловлена следующими их преимуществами:
- правила в них формируются практически на естественном языке, что делает объясняющую способность деревьев решений очень высокой;
- могут работать как с числовыми, так и с категориальными данными;
- требуют относительно небольшой предобработки данных, в частности, не требуют нормализации, создания фиктивных переменных, могут работать с пропусками;
- могут работать с большими объемами данных.
Вместе с тем, деревьям решений присущ ряд ограничений:
- неустойчивость — даже небольшие изменения в данных могут привести к значительным изменениям результатов классификации;
- поскольку алгоритмы построения деревьев решений являются жадными, они не гарантируют построения оптимального дерева;
- склонность к переобучению.
В настоящее время деревья решений продолжают развиваться: создаются новые алгоритмы (SHAID, MARS, Random Forest) и их модификации, изучаются проблемы построения ансамблей моделей на основе деревьев решений.
Деревья решений становятся важным инструментом управления бизнес-процессами и поддержки принятия решений. Общие принципы работы и области применения описаны в статье «Деревья решений: общие принципы».
Источник
Деревья или линейная регрессия?
Дерево решений — одна из известных моделей машинного обучения с учителем. Его можно использовать как для регрессии, так и для классификации, поэтому он также известен как CART (деревья классификации и регрессии). Одним из основных преимуществ деревьев является то, что мы можем визуально генерировать дерево решений с решениями, принятыми моделью, что помогает нам лучше понять модель. Основное внимание в этой статье уделяется пониманию деревьев решений, их преимуществ и недостатков по сравнению с регрессионной моделью OLS.
Дерева решений
Модель дерева решений выглядит как перевернутое дерево. Он состоит из трех частей. Сначала мы начинаем с корневого узла, за которым следует узел решения, а затем, наконец, заканчиваем конечными узлами. Это непараметрическая модель, что означает, что структура модели полностью зависит от данных. Во-первых, модель структурируется на основе обучающих данных, которые мы предоставляем, следуя выбранным нами критериям разделения. Когда мы протестируем его на тестовых данных, модель будет следовать ранее созданной древовидной структуре на основе точек разделения, и любое значение y, которое имеет конечный узел, будет предсказанием модели.
На самом деле это похоже на упражнение по выборке, означающее, что прогноз не является проекцией будущего, прогноз входит в историческую выборку и принимает среднее или модовое значение этой выборки.
Вы можете думать о деревьях, задавая своему другу 20 вопросов «да/нет», чтобы угадать, о чем он думает. Каждый вопрос, который вы задаете, помогает вам получить некоторую информацию, на основе которой вы разделите свое решение о том, какой вопрос задать следующим, и к концу ваших 20 вопросов вы сможете предсказать объект, о котором думает ваш друг.
Точно так же в моделях дерева решений разделение происходит на основе определенных критериев, которые гарантируют, что эти области разделения являются отдельными и непересекающимися областями. Для каждого наблюдения, попадающего в область, мы делаем прогноз как среднее значение переменных отклика в обучающем наборе этой конкретной области в случае непрерывных переменных (т. е. регрессии), и мы будем использовать режим, если у нас есть дискретные переменные ( т. е. классификация). Мы можем думать о каждом листовом узле как о образце.
Критерии выбора атрибутов
Решение о том, как модель определяет точку разделения, будет очень важным, поэтому мы не можем позволить ей выбрать какой-либо случайный атрибут в качестве узла, поскольку это приведет к плохим результатам с низкой точностью.
Энтропия и прирост информации — это один из критериев выбора атрибутов, которые мы обычно используем.
Энтропия — это количество случайностей в данных, чем выше энтропия, тем сложнее делать выводы из данных.
Прирост информации — это статистическое свойство, которое может измерять, насколько хорошо данный атрибут может разделять данные в соответствии с целевой переменной.
«Построение дерева решений — это поиск атрибутов, которые дают нам наибольший прирост информации и самую низкую энтропию».
Еще одним известным критерием выбора атрибута, который мы используем, является индекс Джини.
Индекс Джини — это функция стоимости, которая оценивает разбиения, она отдает предпочтение более крупным разделам, тогда как прирост информации отдает предпочтение меньшим разделам с разными значениями.
Мы можем выбрать один из этих критериев разделения, используя параметр критерия дерева решений. Параметр по умолчанию — «джини», который выбирает индекс Джини, мы можем выбрать прирост информации в качестве нашего критерия разделения, указав критерий = «энтропия».
Проблема переобучения
Дерево решений с большим количеством расщеплений может привести к переоснащению, а малое количество расщеплений может привести к недостаточному соответствию. Глубина дерева — это параметр настройки, который дает нам оптимальное дерево. значение по умолчанию для этого параметра — None, что заставит дерево расти до тех пор, пока каждый конечный узел не будет иметь меньше минимальной выборки или одного наблюдения, что дает нам 100% точность обучения, что приводит к переоснащению.
Как мы видим на приведенной выше диаграмме, поскольку максимальная глубина не упоминается, дерево продолжало расти, разделяя обучающие данные, пока каждый листовой узел не стал настолько чистым, насколько это возможно.
Обрезка и случайный лес
Чтобы избежать переобучения, мы можем использовать обрезку или случайный лес.
В методе обрезки мы обрезаем ветви дерева, удаляя некоторые узлы решений, которые присутствуют с обеих сторон, чтобы общая точность не распределялась. По сути, здесь мы гипернастроим параметр максимальной глубины, который удалит некоторые узлы из исходного дерева.
Случайный лес является примером ансамблевого обучения (т. е. объединения нескольких моделей для повышения общей производительности), в данном случае он объединяет несколько деревьев решений для повышения эффективности прогнозирования.
- Каждое дерево модели будет использовать случайную выборку данных для обучения.
- Каждое дерево использует случайное подмножество функций, гарантируя, что модель ансамбля не сильно зависит от конкретной функции и использует все потенциальные прогностические функции.
Давайте оставим модель случайного леса для другой статьи, а пока продолжим с деревьями.
Преимущества дерева решений по сравнению с OLS
- Для работы линейной регрессии нам нужно нормальное распределение, а функции не должны иметь корреляции, но деревья решений не чувствительны к базовому распределению, поэтому они более надежны.
- Слишком много функций усложнит регрессию МНК, чего нельзя сказать о деревьях.
- Во многих случаях, когда мы делаем прогноз с помощью OLS, наиболее распространенная проблема, с которой мы сталкиваемся, заключается в слишком далекой экстраполяции нашего прогноза, но в случае деревьев прогнозы более надежны, потому что они исторически проверены.
Недостатки деревьев решений
- Трудно придумать хорошие точки разделения во всех случаях.
- Целевая функция здесь состоит в том, чтобы свести к минимуму прогнозируемую ошибку, которая зависит от того, на сколько листьев мы разрешаем разветвляться (чем больше у нас нет листовых узлов, тем меньше будет ошибка, но мы столкнемся с проблемой переобучения). Таким образом, будет компромисс между тем, сколько узлов мы можем разветвить, и ошибкой, которую мы можем получить.
Несмотря на то, что регрессия OLS проста в использовании и прямолинейна, мы не можем использовать ее для всех задач. Когда мы подгоняем данные с помощью OLS, мы оптимизируем функцию стоимости. Проблема с оптимизацией в том, что мы можем оптимизировать ошибку, увеличив ее. Поэтому мы должны убедиться, что мы предсказываем правильно, потому что, если мы предсказываем неправильно, оптимизация увеличит ошибку. Другими альтернативными моделями регрессии, которые мы можем использовать, являются деревья решений и случайные леса.
Источник