Дерево решений выбор места отдыха

Обновлено: 19.05.2024

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

Статья подготовлена на основе перевода: How to Create a Perfect Decision Tree by Upasana Priyadarshiny.

Основные задачи, которые дерево решений решает в машинном обучении, анализе данных и статистике:

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

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

ИИС.doc

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

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

2.4. Структура данных экспертной системы.

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

Список логических выводов - это структура данных, содержащая упорядоченный список возможных логических выводов.

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

На рис. 2 приведён полностью сформированный список логических выводов для всех правил базы знаний.

Рис.2 Список логических выводов.

Список считается сформированным, когда логический вывод каждого правила помещён в запись с номером, совпадающим с номером правила.

Список переменных – это перечень имен переменных для всех условных частей правил базы знаний и признак их инициализации.

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

Список имен переменных

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

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

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

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

Список переменных условия – это перечень всех переменных для всех условных частей всех правил базы знаний.

Условная часть правила (ЕСЛИ) может содержать несколько переменных. Под каждое правило выделяется одинаковое число позиций в списке переменных условия. Минимальное число позиций равно числу переменных условия самого «длинного» правила.

Рисунок 3 - Список переменных условия

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

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

№ = 6* (номер правила/10 — 1)+1

Например, переменные правила 50 будут размещаться, начиная с 25-го элемента массива: 6* (50/10—1)+1=25. №=25.

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

2. 5 Интерфейс программы и программная реализация

Для программной реализации ЭС был выбран язык HTML.

HTML (HyperText Markup Language) - язык гипертекстовой разметки документов. Назначение HTML в том, чтобы сделать документы пригодными для чтения с экрана монитора.

Для создания HTML документов используют текстовые редакторы (например Блокнот), текстовые процессоры (Word), редакторы тегов HTML и визуальные HTML-редакторы. Вы можете создать HTML документ в простом Блокноте. Придерживаясь определённого стандарта и записав в текстовом файле HTML код, сохранив на жёстком диске и изменив расширение на .html или .htm я получила полноценную web страничку.

Теги - это инструменты разметки текста. Теги могут прописываться как строчными, так и прописными буквами, разницы никакой нет. Теги бывают парными и не парными. В качестве примера парного тега можно привести тег <html></html>, этот тег начинает и заканчивает любой HTML документ. Вторая часть парного тега отличается от первой только наличием символа "/", однако первая часть тега может содержать и дополнительные параметры. Например в теге <font size="4"></font>, параметр size="4" определяет размер текста. Примером непарного тега является <hr> - тег вставки в HTML документ горизонтальной линии, такой как в конце этого абзаца.

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

Как использовать жадный алгоритм для построения дерева решений

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

Упрощенно алгоритм можно объяснить так:

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

Главный вопрос: «Как выбрать начальные условия для проверки?». Ответ заключается в значениях энтропии и прироста информации (информационном усилении). Рассказываем, что это и как они влияют на создание нашего дерева:

Энтропия — в дереве решений это означает однородность. Если данные полностью однородны, она равна 0; в противном случае, если данные разделены (50-50%), энтропия равна 1. Проще этот термин можно объяснить так — это то, как много информации, значимой для принятия решения, мы не знаем.
Прирост информации — величина обратная энтропии, чем выше прирост информации, тем меньше энтропия, меньше неучтенных данных и лучше решение.

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

Смотрите на примере. У нас есть большое количество таких данных:

Номер	Возраст (Age)	Уровень дохода (Income)	Студент (Student)	Кредитный рейтинг (CR)	Покупка компьютера (Buys Computer)
1	<30	низкий (Low)	да	средний (Fair)	да
2	30-40	высокий (High)	нет	прекрасный (Excellent)	да
3	40	высокий (High)	нет	прекрасный (Excellent)	нет
4	<30	средний (Medium)	нет	средний (Fair)	нет

Здесь может быть n деревьев решений, которые формируются из этого набора атрибутов.

Почему сложно построить идеальное дерево решений

В структуре дерева решений выделяют следующие компоненты:

Root Node, или корневой узел — тот, с которого начинается дерево, в нашем примере в качестве корня рассматривается фактор «температура».
Internal Node, или внутренний узел — узлы с одним входящим и двумя или более исходящими соединениями.
Leaf Node, или листовой узел — это заключительный элемент без исходящих соединений.

Когда создается дерево решений, мы начинаем от корневого узла, проверяем условия тестирования и присваиваем элемент управления одному из исходящих соединений. Затем снова тестируем условия и назначаем следующий узел. Чтобы считать дерево законченным, нужно все условия привести к листовому узлу (Leaf Node). Листовой узел будет содержать все метки класса, которые влияют на «за» и «против» в принятии решения.

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

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

Практическое использование деревьев решений

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

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

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

Преимущества и недостатки методики дерева решений

Преимущества метода:

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

Недостатки метода:

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

Разработка экспертной системы «Выбор страны отдыха»

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

Содержание работы

Введение. 3
1.1 Интеллектуальный интерфейс. 5
1.2 Принципы разработки интеллектуальных интерфейсов. 9
Список литературы. 12
Вторая часть: разработка экспертной системы «Выбор страны отдыха»
2.1 Постановка задачи. 13
2.2 Дерево решений, таблица переменных и база знаний. 13
2.3 Преобразование дерева решений в правила. 14
2.4 Структуры данных экспертной системы. 19
2.5 Интерфейс программы и программная реализация. 23
Литература. 29

Файлы: 1 файл

Что такое дерево решений и где его используют?

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

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

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

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

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

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

дерево классификации — когда целевая переменная дискретная;

дерево регрессии — когда целевая переменная непрерывная.

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

Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с Джоном Р. Куинленом (автором алгоритма ID3 и последующих модификаций С4.5 и С5.0) и Лео Брейманом, предложившим алгоритм CART и метод случайного леса.

Структура дерева решений

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

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

первое — те, которые удовлетворяют установленное правило;

второе — те, которые не удовлетворяют установленное правило.

Далее к каждому подмножеству снова применяется правило, процедура повторяется. Это продолжается, пока не будет достигнуто условие остановки алгоритма. Последний узел, когда не осуществляется проверка и разбиение, становится листом.

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

Пример попадает в лист, если соответствует всем правилам на пути к нему. К каждому листу есть только один путь. Таким образом, пример может попасть только в один лист, что обеспечивает единственность решения.

Терминология

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

Какие задачи решает дерево решений?

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

Классификация. Отнесение объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные задачи.

Регрессия (численное предсказание). Предсказание числового значения независимой переменной для заданного входного вектора.

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

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

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

Узел становится листом в двух случаях:

естественным образом — когда он содержит единственный объект или объект только одного класса;

после достижения заданного условия остановки алгоритм — например, минимально допустимое число примеров в узле или максимальная глубина дерева.

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

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

n примеров, для каждого из которых задана метка класса Ci(i = 1..k);

m атрибутов Aj(j = 1..m), которые определяют принадлежность объекта к тому или иному классу.

Тогда возможно три случая:

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

Множество S — пустое множество без примеров. Для него сформируется лист, класс которого выберется из другого множества. Например, самый распространенный из родительского множества класс.

Множество S состоит из обучающих примеров всех классов Ck. В таком случае множество разбивается на подмножества в соответствии с классами. Для этого выбирают один из атрибутов Aj множества S, состоящий из двух и более уникальных значений: a1, a2, …, ap), где p — число уникальных значений признака. Множество S разбивают на p подмножеств (S1, S2, …, Sp), состоящих из примеров с соответствующим значением атрибута. Процесс разбиения продолжается, но уже со следующим атрибутом. Он будет повторяться, пока все примеры в результирующих подмножества не окажутся одного класса.

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

Сегодня существует много алгоритмов обучения: ID3, CART, C4.5, C5.0, NewId, ITrule, CHAID, CN2 и другие. Самыми популярными считаются:

ID3 (Iterative Dichotomizer 3). Алгоритм позволяет работать только с дискретной целевой переменной. Деревья решений, построенные на основе ID3, получаются квалифицирующими. Число потомков в узле неограниченно. Алгоритм не работает с пропущенными данными.

C4.5. «Продвинутая» версия ID3, дополненная возможностью работы с пропущенными значениями атрибутов. В 2008 году издание Spring Science провело исследование и выявило, что C4.5 — самый популярный алгоритм Data Mining.

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

Основные этапы построения дерева решений

Построение осуществляется в 4 этапа:

Выбрать атрибут для осуществления разбиения в данном узле.

Определить критерий остановки обучения.

Выбрать метод отсечения ветвей.

Оценить точность построенного дерева.

Далее рассмотрим каждый подробнее.

Выбор атрибута разбиения

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

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

Теоретико-информационный критерий

В основе критерия лежит информационная энтропия:

где n — число классов в исходном подмножестве, Ni — число примеров i-го класса, N — общее число примеров в подмножестве.

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

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

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

где Info(S) — информация, связанная с подмножеством S до разбиения, Info(Sa) — информация, связанная с подмножеством, полученным при разбиении атрибута A.

Задача выбора атрибута в такой ситуации заключается в максимизации величины Gain(A), которую называют приростом информации. Поэтому теоретико-информационный подход также известен под название «критерий прироста информации.

Статистический подход

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

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

Индекс Джини рассчитывается по формуле:

где Q — результирующее множество, n — число классов в нем, pi — вероятность i-го класса (выраженная как относительная частота примеров соответствующего класса).

Значение показателя меняется от 0 до 1. Если индекс равен 0, значит, все примеры результирующего множества относятся к одному классу. Если равен 1, значит, классы представлены в равных пропорциях и равновероятны. Оптимальным считают то разбиение, для которого значение индекса Джини минимально.

Критерий остановки алгоритма

Алгоритм обучения может работать до получения «чистых» подмножеств с примерами одного класса. В таком случае высока вероятность получить дерево, в котором для каждого примера будет создан отдельный лист. Такое дерево не получится применять на практике из-за переобученности. Каждому примеру будет соответствовать свой уникальный путь в дереве. Получится набор правил, актуальный только для данного примера.

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

Специалисты решили принудительно останавливать строительство дерева, чтобы оно не становилось «переобученным».

Для этого используют несколько подходов:

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

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

Задание минимально допустимого числа примеров в узле. Устанавливается ограничение на создание узлов с числом примером меньше заданного (например, 7). В таком случае не будут создаваться тривиальные разбиения и малозначимые правила.

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

Отсечение ветвей

Без ограничения «роста» дерево решений станет слишком большим и сложным, что сделает невозможной дальнейшую интерпретацию. А если делать решающие правила для создания узлов, в которые будут попадать по 2-3 примера, они не лишатся практической ценности.

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

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

Строительство полного дерева, в котором листья содержат примеры одного класса.

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

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

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

Главное отличие метода «отсечение ветвей» от преждевременной остановки — получается найти оптимальное соотношение между точностью и понятностью. При этом уходит больше времени на обучение, потому что в рамках этого подхода изначально строится полное дерево.

Извлечение правил

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

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

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

Преимущества и недостатки дерева решений

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

Формируют четкие и понятные правила классификации. Например, «если возраст < 40 и нет имущества для залога, то отказать в кредите». То есть деревья решений хорошо и быстро интерпретируются.

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

Легко визуализируются, то есть могут «интерпретироваться» не только как модель в целом, но и как прогноз для отдельного тестового субъекта (путь в дереве).

Быстро обучаются и прогнозируют.

Не требуется много параметров модели.

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

Недостатки:

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

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

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

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

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

Где применяют деревья решения?

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

Успешнее всего деревья применяют в следующих областях:

Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.

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

Медицина. Диагностика заболеваний разной сложности.

Молекулярная биология. Анализ строения аминокислот.

Торговля. Классификация клиентов и товар.

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

Надеемся, наша статья оказалась для вас полезной. Больше интересного контента от ProductStar вы найдёте в нашем блоге на vc и в аналитическом тг-канале.

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

Правила классификации

Сначала определимся с терминами и их значениями.

Правила классификации — это случаи, в которых учитываются все сценарии, и каждому присваивается переменная класса.

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

Вот правила классификации из примера дерева решений про исследование новой планеты:

Если температура не находится в диапазоне от -0,15 °C до 99,85 °C, то выживание затруднительно.
Если температура находится в диапазоне от -0,15 °C до 99,85 °C, но нет воды, то выживание затруднительно.
Если температура находится в диапазоне от -0,15 °C до 99,85 °C, есть вода, но нет флоры и фауны, то выживание затруднительно.
Если температура находится в диапазоне от -0,15 °C до 99,85 °C, есть вода, есть флора и фауна, поверхность не подвержена штормам, то выживание возможно.
Если температура находится в диапазоне от -0,15 °C до 99,85 °C, есть вода, есть флора и фауна, но поверхность подвержена штормам, то выживание затруднительно.

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

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

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

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

В дереве решений могут быть три разных типа узлов:

Decision nodes — узлы решения, они показывают решение, которое нужно принять.
Chance nodes — вероятностные узлы, демонстрируют вероятность определенных результатов.
End nodes — замыкающие узлы, показывают конечный результат пути решения.

Описание алгоритма обучения

Пусть задано обучающее множество S , содержащее m атрибутов и n примеров. Для множества S определено k классов C_1,C_2,…C_k . Задача заключается в построении иерархической классификационной модели в виде дерева решений на основе обучающего множества S .

Построение дерева решений производится сверху вниз — от корневого узла к листьям.

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

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

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

Пусть к обучающему множеству применяется правило разбиения, в котором используется атрибут A , принимающий p значений a_1,a_2,…,a_p . В результате будет создано p подмножеств S_1,S_2,…,S_p , куда будут распределены примеры, в которых атрибут A принимает соответствующее значение.

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

Обозначим N(C_jS) число примеров класса C_j в множестве S . Тогда вероятность класса C_j в этом множестве будет:

где N(S) — общее число примеров в множестве S .

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

Эту же оценку, полученную после разбиения множества S по атрибуту A , можно записать в виде:

где S_i — i -й узел, полученный при разбиении по атрибуту A . Тогда для выбора лучшего атрибута ветвления можно использовать следующий критерий:

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

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

Если в процессе построения дерева будет сформирован «пустой» узел, куда не попало ни одного примера, то он преобразуется в лист, который ассоциируется с классом, наиболее часто встречающимся у непосредственного предка узла.

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

Описанная процедура применима к дискретным атрибутам. В случае непрерывных атрибутов алгоритм работает несколько иначе. Выбирается порог, с которым будут сравниваться все значения. Пусть числовой атрибут X принимает конечное множество значений . Упорядочив примеры по возрастанию значений атрибута, получим, что любое значение, лежащее между x_i и x_ делит все примеры на два подмножества. Первое подмножество будет содержать значения атрибута x_1,x_2,…,x_i , а второе — .

Тогда в качестве порога можно выбрать среднее:

Таким образом, задача нахождения порога сводится к рассмотрению n-1 потенциальных пороговых значений > . Последовательно применяя формулы (2), (3) и (4) ко всем потенциальным порогам, выбираем то, которое даёт максимальное значение по критерию (4). Затем, это значение сравнивается со значением критерия (4), рассчитанным для других атрибутов. Если это значение окажется наибольшим из всех атрибутов, то оно выбирается в качестве порога для проверки.

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

Деревья решений — C4.5 математический аппарат | Часть 1

Разбираем алгоритм обучения деревьев решений C4.5: требования для обучающего набора данных и классификация новых объектов.

В данной статье будет рассмотрен математический аппарат алгоритма обучения деревьев решений С4.5. Алгоритм был предложен Р. Куинленом как усовершенствованная версия алгоритма ID3, в которую добавлена возможность работы с пропущенными данными. Базовые идеи построения были описаны в статье «Деревья решений: общие принципы».

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

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

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

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

Задачу будем исследовать через дерево решений.

Пригодная для обитания температура находится в диапазоне от 0 до 100 градусов Цельсия?

Есть ли там вода?

Флора и фауна процветает?

Подвержена ли поверхность планеты штормам?

Таким образом, у нас получилось завершенное дерево решений.

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