Дерево решений имеет много аналогий в реальной жизни и, как оказалось, повлияло на широкую область машинного обучения, охватывающую как классификацию, и Регрессия. В анализе решений дерево решений можно использовать для визуального и явного представления решений и принятия решений.
Итак, схема того, что я буду освещать в этом блоге, выглядит следующим образом.
- Что такое дерево решений?
- Преимущества и недостатки дерева решений
- Создание дерева решений
Что такое дерево решений?
Дерево решений — это карта возможных результатов ряда связанных выборов. Это позволяет человеку или организации сопоставлять возможные действия друг с другом на основе их затрат, вероятностей и выгод.
Как следует из названия, он использует древовидную модель решений. Их можно использовать либо для ведения неформального обсуждения, либо для составления алгоритма, математически предсказывающего наилучший выбор.
Дерево решений обычно начинается с одного узла, который разветвляется на возможные результаты. Каждый из этих результатов приводит к дополнительным узлам, которые разветвляются на другие возможности. Это придает ему древовидную форму.
Существует три различных типа узлов: случайные узлы, узлы принятия решений и конечные узлы. Узел шансов, представленный кружком, показывает вероятности определенных результатов. Узел решения, представленный квадратом, показывает решение, которое необходимо принять, а конечный узел показывает окончательный результат пути принятия решения.
Преимущества и недостатки деревьев решений
Преимущества
- Деревья решений генерируют понятные правила.
- Деревья решений выполняют классификацию, не требуя больших вычислений.
- Деревья решений способны обрабатывать как непрерывные, так и категориальные переменные.
- Деревья решений дают четкое представление о том, какие поля наиболее важны для прогнозирования или классификации.
Недостатки
- Деревья решений менее подходят для задач оценки, целью которых является прогнозирование значения непрерывного атрибута.
- Деревья решений склонны к ошибкам в задачах классификации со многими классами и относительно небольшим количеством обучающих примеров.
- Обучение деревьев решений может быть дорогостоящим в вычислительном отношении. Процесс выращивания дерева решений требует значительных вычислительных ресурсов. В каждом узле каждое поле разбиения-кандидата должно быть отсортировано, прежде чем можно будет найти его наилучшее разбиение. В некоторых алгоритмах используются комбинации полей и необходимо производить поиск оптимальных комбинационных весов. Алгоритмы обрезки также могут быть дорогостоящими, поскольку необходимо сформировать и сравнить множество поддеревьев-кандидатов.
Создание дерева решений
Давайте рассмотрим сценарий, в котором новая планета открыта группой астрономов. Теперь вопрос в том, может ли она быть «следующей землей»? Ответ на этот вопрос изменит образ жизни людей. Ну буквально!
Существует n решающих факторов, которые необходимо тщательно изучить, чтобы принять разумное решение. Этими факторами могут быть наличие воды на планете, какова температура, подвержена ли поверхность непрерывным штормам, выживает ли флора и фауна в климате или нет и т. д.
Давайте создадим дерево решений, чтобы узнать, обнаружили ли мы новую среду обитания.
Пригодная для жизни температура находится в диапазоне от 0 до 100 градусов по Цельсию.
Вода есть или нет?
Процветает ли флора и фауна?
Планета имеет бурную поверхность?
Таким образом, у нас есть дерево решений.
Правила классификации:
Правила классификации — это случаи, когда учитываются все сценарии и каждому присваивается переменная класса.
Переменная класса:
Каждому листовому узлу назначается переменная класса. Переменная класса — это конечный результат, который приводит к нашему решению.
Выведем правила классификации из созданного Дерева решений:
1. Если температура не находится в пределах от 273 до 373 К, -> трудно выжить.
2. Если температура находится в диапазоне от 273 до 373 К, а воды нет, -> сложно выжить.
3. Если температура находится в диапазоне от 273 до 373 К, вода присутствует, а флора и фауна отсутствуют -> выживание сложно
4. Если температура находится в диапазоне от 273 до 373 К, вода присутствует, флора и фауна присутствуют, а штормовая поверхность отсутствует -> Вероятность выживания
5. Если температура находится в диапазоне от 273 до 373 К, присутствует вода, флора и фауна, а также штормовая поверхность -> выживание сложно
Древо решений
Дерево решений состоит из следующих компонентов:
- Корневой узел: в этом случае фактор «температура» считается корнем.
- Внутренний узел: узлы с одним входящим ребром и 2 или более исходящими ребрами.
- Листовой узел: это конечный узел без исходящего края.
Поскольку дерево решений теперь построено, начиная с корневого узла, мы проверяем тестовое условие и назначаем управление одному из исходящих ребер, таким образом, снова проверяется условие и назначается узел. Говорят, что дерево решений завершено, когда все условия проверки приводят к конечному узлу. Листовой узел содержит метки классов, которые голосуют за или против решения.
Теперь вы можете подумать, почему мы начали с атрибута «температура» в корне? Если вы выберете любой другой атрибут, построенное дерево решений будет другим.
Правильный. Для определенного набора атрибутов может быть создано множество различных деревьев. Нам нужно выбрать оптимальное дерево, что делается с помощью алгоритмического подхода. Теперь мы увидим «жадный подход» для создания идеального дерева решений.
Жадный подход
«Жадный подход основан на концепции эвристического решения проблем путем оптимального локального выбора в каждом узле. Делая эти локальные оптимальные выборы, мы достигаем приблизительного оптимального решения в глобальном масштабе».
Алгоритм можно обобщить так:
1. На каждом этапе (узле) выберите лучшую функцию в качестве тестового условия.
2. Теперь разделите узел на возможные исходы (внутренние узлы).
3. Повторяйте вышеуказанные шаги до тех пор, пока все условия тестирования не будут исчерпаны в листовых узлах.
Когда вы начинаете реализовывать алгоритм, первый вопрос: Как выбрать начальное условие теста?
Ответ на этот вопрос заключается в значениях Энтропии и Прироста информации. Давайте посмотрим, что это такое и как они влияют на создание нашего дерева решений.
Энтропия. Энтропия в дереве решений означает однородность. Если данные полностью однородны, энтропия равна 0, иначе, если данные разделены (50–50%), энтропия равна 1.
Прирост информации: прирост информации — это уменьшение/увеличение значения энтропии при разделении узла.
Атрибут должен иметь самый высокий информационный прирост, чтобы быть выбранным для разделения. Основываясь на вычисленных значениях энтропии и прироста информации, мы выбираем лучший атрибут на каждом конкретном этапе.
Рассмотрим следующие данные:
Может быть n деревьев решений, которые можно сформулировать из этого набора атрибутов.
Пробная версия создания дерева-1:
Здесь мы используем атрибут «Студент» в качестве начального условия проверки.
Пробная версия создания дерева-2:
Точно так же, зачем выбирать «Студент»? Мы можем выбрать «Доход» в качестве условия теста.
Создание идеального дерева решений с помощью жадного подхода
Давайте воспользуемся «Жадным подходом» и построим оптимальное дерево решений.
Здесь задействованы два класса: Да, т. е. покупает ли человек компьютер, или «Нет», т. е. не покупает. Чтобы рассчитать энтропию и прирост информации, мы вычисляем значение вероятности для каждого из этих двух классов.
«Положительно: для ‘buys_computer=yes’ вероятность окажется:
«Отрицательно: для ‘buys_computer=no’ вероятность получается:
Энтропия в D: теперь мы вычисляем энтропию, помещая значения вероятности в формулу, указанную выше.
Мы уже классифицировали значения энтропии, а именно:
Энтропия = 0: данные полностью однородны (чисты).
Энтропия = 1: данные делятся на 50-50 % (нечистые)
Наше значение энтропии равно 0,940, что означает, что наш набор почти грязный.
Давайте углубимся, чтобы найти подходящий атрибут и рассчитать прирост информации.
Что даст информация, если мы разделим ее на "Возраст"?
Эти данные показывают, сколько людей, попадающих в определенную возрастную группу, покупают и не покупают продукт.
Например, для людей в возрасте 30 лет и младше, 2 человека покупают (Да) и 3 человека не покупают (Нет) продукт, информация (D) рассчитывается для этих 3 категорий людей, которые представлены в последнем столбце. .
Информация (D) для атрибута возраста вычисляется по сумме этих трех диапазонов значений возраста. Теперь вопрос в том, каков «прирост информации», если мы разделим атрибут «Возраст».
Разница общего значения информации (0,940) и информации, рассчитанной для атрибута возраста (0,694), дает «прирост информации».
Это решающий фактор для разделения по «возрасту» или любому другому признаку. Точно так же мы вычисляем «прирост информации» для остальных атрибутов:
Прирост информации (возраст) = 0,246
Прирост информации (доход) = 0,029
Получение информации (учащийся) = 0,151
Прирост информации (кредит_рейтинг) = 0,048
При сравнении этих значений прироста по всем признакам мы обнаруживаем, что «прирост информации» для «Возраст» является самым высоким. Таким образом, разделение по «возрасту» — хорошее решение.
Точно так же при каждом разделении мы сравниваем прирост информации, чтобы выяснить, следует ли выбирать этот атрибут для разделения или нет.
Таким образом, созданное оптимальное дерево выглядит так:
Если возраст человека меньше 30 лет и он не студент, он не будет покупать товар.
Если возраст человека меньше 30 лет и он не студент, он не будет покупать товар.
Возраст (‹ 30) ^ студент (нет) = НЕТ
Если возраст человека меньше 30 лет и он студент, то он купит товар.
Возраст(‹ 30) ^ студент(да) = ДА
Если возраст человека от 31 до 40 лет, он, скорее всего, купит.
Возраст(31…40) = ДА
Если возраст человека старше 40 лет и у него отличный кредитный рейтинг, он покупать не будет.
Возраст(>40) ^ кредит_рейтинг(отлично) = НЕТ
Если возраст человека старше 40 лет с удовлетворительным кредитным рейтингом, он, скорее всего, купит.
Возраст(›40) ^ Credit_rating(fair) = Yes
Таким образом, мы достигаем идеального Дерева Решений!!
Если вы хотите прочитать больше статей о самых популярных на рынке технологиях, таких как Python, DevOps, Ethical Hacking, вы можете обратиться к официальному сайту Edureka.
Обратите внимание на другие статьи из этой серии, в которых объясняются различные другие аспекты науки о данных.
17. R против Python
18.Искусственный интеллект, машинное обучение и глубокое обучение
21.Наука о данных и инструменты машинного обучения для непрограммистов
Первоначально опубликовано на https://www.edureka.co 28 января 2015 г.