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

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

  • автор:

Деревья решений: общие принципы

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

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

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

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

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

Основополагающие идеи, послужившие толчком к появлению и развитию деревьев решений, были заложены в 1950-х годах в области исследований моделирования человеческого поведения с помощью компьютерных систем. Среди них следует выделить работы К. Ховеленда «Компьютерное моделирование мышления»[1] и Е. Ханта и др. «Эксперименты по индукции»[2].

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

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

Введем в рассмотрение основные понятия, используемые в теории деревьев решений.

Название Описание
Объект Пример, шаблон, наблюдение
Атрибут Признак, независимая переменная, свойство
Целевая переменная Зависимая переменная, метка класса
Узел Внутренний узел дерева, узел проверки
Корневой узел Начальный узел дерева решений
Лист Конечный узел дерева, узел решения, терминальный узел
Решающее правило Условие в узле, проверка

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

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

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

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

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

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

Задачи

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

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

Процесс построения

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

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

В основе большинства популярных алгоритмов обучения деревьев решений лежит принцип «разделяй и властвуй». Алгоритмически этот принцип реализуется следующим образом. Пусть задано обучающее множество S , содержащее n примеров, для каждого из которых задана метка класса C_i(i=1..k) , и m атрибутов A_j(j=1..m) , которые, как предполагается, определяют принадлежность объекта к тому или иному классу. Тогда возможны три случая:

  1. Все примеры множества S имеют одинаковую метку класса C_i (т.е. все обучающие примеры относятся только к одному классу). Очевидно, что обучение в этом случае не имеет смысла, поскольку все примеры, предъявляемые модели, будут одного класса, который и «научится» распознавать модель. Само дерево решений в этом случае будет представлять собой лист, ассоциированный с классом C_i . Практическое использование такого дерева бессмысленно, поскольку любой новый объект оно будет относить только к этому классу.
  2. Множество S вообще не содержит примеров, т.е. является пустым множеством. В этом случае для него тоже будет создан лист (применять правило, чтобы создать узел, к пустому множеству бессмысленно), класс которого будет выбран из другого множества (например, класс, который наиболее часто встречается в родительском множестве).
  3. Множество S содержит обучающие примеры всех классов C_k . В этом случае требуется разбить множество S на подмножества, ассоциированные с классами. Для этого выбирается один из атрибутов A_j множества S который содержит два и более уникальных значения (a_1,a_2. a_p) , где p — число уникальных значений признака. Затем множество S разбивается на p подмножеств (S_1,S_2. S_p) , каждое из которых включает примеры, содержащие соответствующее значение атрибута. Затем выбирается следующий атрибут и разбиение повторяется. Это процедура будет рекурсивно повторяться до тех пор, пока все примеры в результирующих подмножествах не окажутся одного класса.

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

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

  • ID3 (Iterative Dichotomizer 3) — алгоритм позволяет работать только с дискретной целевой переменной, поэтому деревья решений, построенные с помощью данного алгоритма, являются классифицирующими. Число потомков в узле дерева не ограничено. Не может работать с пропущенными данными.
  • C4.5 — усовершенствованная версия алгоритма ID3, в которую добавлена возможность работы с пропущенными значениями атрибутов (по версии издания Springer Science в 2008 году алгоритм занял 1-е место в топ-10 наиболее популярных алгоритмов Data Mining).
  • CART (Classification and Regression Tree) — алгоритм обучения деревьев решений, позволяющий использовать как дискретную, так и непрерывную целевую переменную, то есть решать как задачи классификации, так и регрессии. Алгоритм строит деревья, которые в каждом узле имеют только два потомка.

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

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

  1. Выбор атрибута, по которому будет производиться разбиение в данном узле (атрибута разбиения).
  2. Выбор критерия остановки обучения.
  3. Выбор метода отсечения ветвей (упрощения).
  4. Оценка точности построенного дерева.

Рассмотрим эти этапы ниже.

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

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

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

Как следует из названия, критерий основан на понятиях теории информации, а именно — информационной энтропии.

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

Таким образом, энтропия может рассматриваться как мера неоднородности подмножества по представленным в нём классам. Когда классы представлены в равных долях и неопределённость классификации наибольшая, энтропия также максимальна. Если все примеры в узле относятся к одному классу, т.е. N=N_i , логарифм от единицы обращает энтропию в ноль.

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

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

Таким образом, задача выбора атрибута разбиения в узле заключается в максимизации величины \text(A) , называемой приростом информации (от англ. gain — прирост, увеличение). Поэтому сам теоретико-информационный подход известен как критерий прироста информации. Он впервые был применён в алгоритме ID3, а затем в C4.5 и других алгоритмах.

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

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

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

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

где Q — результирующее множество, n — число классов в нём, p_i — вероятность i-го класса (выраженная как относительная частота примеров соответствующего класса). Очевидно, что данный показатель меняется от 0 до 1. При этом он равен 0, если все примеры Q относятся к одному классу, и равен 1, когда классы представлены в равных пропорциях и равновероятны. Тогда лучшим будет то разбиение, для которого значение индекса Джини будут минимальным.

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

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

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

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

  1. Ранняя остановка — алгоритм будет остановлен, как только будет достигнуто заданное значение некоторого критерия, например процентной доли правильно распознанных примеров. Единственным преимуществом подхода является снижение времени обучения. Главным недостатком является то, что ранняя остановка всегда делается в ущерб точности дерева, поэтому многие авторы рекомендуют отдавать предпочтение отсечению ветвей.
  2. Ограничение глубины дерева — задание максимального числа разбиений в ветвях, по достижении которого обучение останавливается. Данный метод также ведёт к снижению точности дерева.
  3. Задание минимально допустимого числа примеров в узле — запретить алгоритму создавать узлы с числом примеров меньше заданного (например, 5). Это позволит избежать создания тривиальных разбиений и, соответственно, малозначимых правил.

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

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

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

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

К сожалению, это задача относится к классу NP-полных задач, что было показано Л. Хайфилем (L. Hyafill) и Р. Ривестом (R. Rivest), и, как известно, этот класс задач не имеет эффективных методов решения.

Альтернативным подходом является так называемое отсечение ветвей (pruning). Он содержит следующие шаги:

  1. Построить полное дерево (чтобы все листья содержали примеры одного класса).
  2. Определить два показателя: относительную точность модели — отношение числа правильно распознанных примеров к общему числу примеров, и абсолютную ошибку — число неправильно классифицированных примеров.
  3. Удалить из дерева листья и узлы, отсечение которых не приведёт к значимому уменьшению точности модели или увеличению ошибки.

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

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

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

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

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

Преимущества алгоритма

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

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

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

Области применения

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

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

  • Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
  • Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например, проверка качества сварки) и т.д.
  • Медицина. Диагностика заболеваний.
  • Молекулярная биология. Анализ строения аминокислот.
  • Торговля. Классификация клиентов и товаров.

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

  1. Hovland, C. I. (1960). Computer simulation of thinking. American Psychologist, 15(11), 687-693.
  2. Hunt, Earl B.; Janet Marin; Philip J. Stone (1966). Experiments in Induction. New York: Academic Press. ISBN 978-0-12-362350-8.
  3. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1):81-106.
  4. Quinlan, J. Ross. C4.5: Programs for Machine learning. Morgan Kaufmann Publishers 1993.
  5. Breiman, Leo, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
  6. Murthy, S. Automatic construction of decision trees from data: A Multi-disciplinary survey.1997.
  7. Buntine, W. A theory of classification rules. 1992.
  8. Machine Learning, Neural and Statistical Classification. Editors D. Mitchie et.al. 1994.
  9. Шеннон, К. Работы по теории информации и кибернетике. М. Иностранная литература, 1963.
  10. Айвазян С. А., Мхитарян В. С Прикладная статистика и основы эконометрики, М. Юнити, 1998.

Другие материалы по теме:

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

Ребята, привет! Сегодня команда ProductStar подготовила для вас статью, в которой мы рассмотрели общие принципы работы и области применения дерева решений. Материал подготовлен на основе работы Акобира Шахиди «Деревья решений: общие принципы»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • n примеров, для каждого из которых задана метка класса Ci(i = 1..k);
  • m атрибутов Aj(j = 1..m), которые определяют принадлежность объекта к тому или иному классу.

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

  1. Примеры множества S имеют одинаковую метку Ci, следовательно, все обучающие примеры относятся к одному классу. В таком случае обучение не имеет смысла, потому что все примеры в модели будут одного класса, который и «научится» распознавать модель. Само дерево будет похоже на один большой лист, ассоциированный с классом Ci. Тогда его использование не будет иметь смысла, потому что все новые объекты будут относиться к одному классу.
  2. Множество S — пустое множество без примеров. Для него сформируется лист, класс которого выберется из другого множества. Например, самый распространенный из родительского множества класс.
  3. Множество 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 этапа:

  1. Выбрать атрибут для осуществления разбиения в данном узле.
  2. Определить критерий остановки обучения.
  3. Выбрать метод отсечения ветвей.
  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 шага:

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

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

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

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

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

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

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

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

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

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

Недостатки:

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

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

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

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

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

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

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

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

  • дерево решений
  • веб-аналитика

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

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

Читается за 8 мин.

Хотите создать собственную диаграмму? Попробуйте Lucidchart. Это быстро, легко и совершенно бесплатно.

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

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

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

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

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

Символы дерева решений

Фигура Название Значение
Узел решения Решение, которое необходимо принять
Узел вероятности Указывает несколько возможных результатов
Ветви альтернативы Каждая ветвь символизирует возможный результат или действие
Отклоненная альтернатива Вариант, который не был выбран
Конечный узел Символизирует конечный результат

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

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

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

2. Добавьте узлы принятия решений и узлы вероятности, соблюдая следующие правила:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *