Обучение дереву решений

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

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

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

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

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

Общие

Дерево, показывающее выживание пассажиров « Титаника» («sibsp» — количество супругов или братьев и сестер на борту). Цифры под листьями показывают вероятность выживания и процент наблюдений в листе. Подводя итог: ваши шансы на выживание были хорошими, если вы были (i) женщиной или (ii) мужчиной не старше 9,5 лет и имели строго менее трех братьев и сестер.

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

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

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

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

Данные поступают в записи вида:

$({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)$

Зависимая переменная, $Y$, — это целевая переменная, которую мы пытаемся понять, классифицировать или обобщить. Вектор ${\textbf {x}}$ состоит из особенностей, $x_{1},x_{2},x_{3}$ и т. д., которые используются для этой задачи.

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

Типы деревьев решений

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

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

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

Некоторые методы, часто называемые ансамблевыми методами, строят более одного дерева решений:

• Усиленные деревья. Постепенное построение ансамбля путем обучения каждого нового экземпляра, чтобы подчеркнуть ранее неправильно смоделированные обучающие экземпляры. Типичный пример — AdaBoost . Их можно использовать для решения задач типа регрессии и классификации.
• Комитеты деревьев решений (также называемые k-DT ), ранний метод, который использовал алгоритмы рандомизированного дерева решений для создания нескольких различных деревьев на основе обучающих данных, а затем объединял их с помощью голосования большинством для получения выходных данных.
• Агрегированные (или упакованные) деревья решений Bootstrap , ранний метод ансамбля, строит несколько деревьев решений путем многократной повторной выборки обучающих данных с заменой и голосования деревьев для консенсусного прогноза.
  • Классификатор случайного леса — это особый тип бутстрап-агрегирования.
• Ротационный лес – в котором каждое дерево решений обучается путем предварительного применения анализа главных компонентов (PCA) к случайному подмножеству входных объектов.

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

Известные алгоритмы дерева решений включают:

• ID3 (Итеративный дихотомизатор 3)
• C4.5 (преемник ID3)
• CART (дерево классификации и регрессии)
• OC1 (Наклонный классификатор 1). Первый метод, который создавал многомерные разбиения в каждом узле.
• Автоматическое обнаружение взаимодействия по хи-квадрату (CHAID). Выполняет многоуровневое разбиение при вычислении деревьев классификации.
• MARS : расширяет деревья решений для лучшей обработки числовых данных.
• Деревья условного вывода. Подход, основанный на статистике, который использует непараметрические тесты в качестве критериев разделения, с поправкой на множественное тестирование, чтобы избежать переобучения. Этот подход приводит к беспристрастному выбору предикторов и не требует обрезки.

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

Также было предложено использовать концепции теории нечетких множеств для определения специальной версии дерева решений, известной как нечеткое дерево решений (FDT). В этом типе нечеткой классификации, как правило, входной вектор ${\textbf {x}}$связан с несколькими классами, каждый из которых имеет разное значение достоверности. Недавно были исследованы усиленные ансамбли FDT, и они показали характеристики, сравнимые с характеристиками других очень эффективных нечетких классификаторов.

Метрики

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

положительной

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

$E_{P}=TP-FP$

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

Матрица путаницы

Предсказанный Сорт Фактический класс	Рак	Нерак
Рак	8	3
Нерак	2	5

Здесь мы видим, что значение TP будет равно 8, а значение FP — 2 (подчеркнутые цифры в таблице). Подставив эти числа в уравнение, мы сможем рассчитать оценку: $E_{p}=TP-FP=8-2=6$. Это означает, что при использовании оценки этой функции она получит оценку 6.

Однако следует отметить, что эта цифра является лишь приблизительной. Например, если два объекта имеют значение FP, равное 2, а один из объектов имеет более высокое значение TP, этот объект будет иметь более высокий рейтинг, чем другой, поскольку результирующая оценка при использовании уравнения даст более высокое значение. Это может привести к некоторым неточностям при использовании метрики, если некоторые функции имеют больше положительных выборок, чем другие. Чтобы бороться с этим, можно использовать более мощную метрику, известную как «Чувствительность» , которая учитывает пропорции значений из матрицы путаницы, чтобы получить фактический истинно положительный уровень (TPR). Разница между этими показателями показана на примере ниже:

Матрица путаницы Предсказанный Сорт Фактический класс Рак Нерак Рак 8 3 Нерак 2 5	Функция B Матрица путаницы Предсказанный Сорт Фактический класс Рак Нерак Рак 6 2 Нерак 2 8
$E_{p}=TP-FP=8-2=6$ $TPR=TP/(TP+FN)=8/(8+3)\approx 0.73$	$E_{p}=TP-FP=6-2=4$ $TPR=TP/(TP+FN)=6/(6+2)=0.75$

В этом примере функция A имела оценку 6 и TPR примерно 0,73, тогда как функция B имела оценку 4 и TPR 0,75. Это показывает, что, хотя положительная оценка для некоторого объекта может быть выше, более точное значение TPR для этого объекта может быть ниже по сравнению с другими объектами, которые имеют более низкую положительную оценку. В зависимости от ситуации и знания данных и деревьев решений можно использовать положительную оценку для быстрого и простого решения своей проблемы. С другой стороны, более опытный пользователь, скорее всего, предпочтет использовать значение TPR для ранжирования объектов, поскольку оно учитывает пропорции данных и всех выборок, которые должны были быть классифицированы как положительные.

Джини примесь

Примесь Джини , индекс разнообразия Джини , или Индекс Джини-Симпсона в исследованиях биоразнообразия, назван в честь итальянского математика Коррадо Джини и используется алгоритмом CART (дерево классификации и регрессии) для деревьев классификации. Примесь Джини измеряет, как часто случайно выбранный элемент набора будет помечен неправильно, если бы он был помечен случайно и независимо в соответствии с распределением меток в наборе. Он достигает своего минимума (нуля), когда все случаи в узле попадают в одну целевую категорию.

Для набора предметов с $J$ классы и относительные частоты $p_{i}$, $i\in \{1,2,...,J\}$, вероятность выбора предмета с меткой $i$ является $p_{i}$, и вероятность неправильной категоризации этого элемента равна $\sum _{k\neq i}p_{k}=1-p_{i}$. Примесь Джини вычисляется путем суммирования попарных произведений этих вероятностей для каждой метки класса:

$\operatorname {I} _{G}(p)=\sum _{i=1}^{J}\left(p_{i}\sum _{k\neq i}p_{k}\right)=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-p_{i}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}p_{i}^{2}=1-\sum _{i=1}^{J}p_{i}^{2}.$

Примесь Джини также является мерой теории информации и соответствует энтропии Цаллиса с коэффициентом деформации. $q=2$, что в физике связано с недостатком информации в неравновесных, неэкстенсивных, диссипативных и квантовых системах. Для лимита $q\to 1$восстанавливается обычная энтропия Больцмана-Гиббса или Шеннона. В этом смысле примесь Джини представляет собой не что иное, как вариацию обычной меры энтропии для деревьев решений.

Получение информации

Основная статья: Получение информации в деревьях решений

Используется ID3 , C4.5 алгоритмами генерации дерева и C5.0. Получение информации основано на концепции энтропии и информационного содержания из теории информации .

Энтропия определяется, как показано ниже.

$\mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},\ldots ,p_{J}\right)=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}$

где $p_{1},p_{2},\ldots$ представляют собой дроби, сумма которых равна 1 и представляет собой процент каждого класса, присутствующего в дочернем узле, который является результатом разделения дерева.

$$\overbrace {IG(T,a)} ^{\text{information gain}}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid a)} ^{\text{sum of entropies (children)}}$$

$=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)$

Усреднение по возможным значениям $A$,

$$\overbrace {E_{A}(\operatorname {IG} (T,a))} ^{\text{expected information gain}}=\overbrace {I(T;A)} ^{{\text{mutual information between }}T{\text{ and }}A}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid A)} ^{\text{weighted sum of entropies (children)}}$$

$=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)$

Если взвешенная сумма энтропий определяется выражением,

${\mathrm {H} (T\mid A)}=\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)$

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

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

Рассмотрим пример набора данных с четырьмя атрибутами: прогноз погоды (солнечно, пасмурно, дождливо), температура (жарко, умеренно, прохладно), влажность (высокая, нормальная) и ветрено (истина, ложь) с двоичным значением (да или нет). целевая переменная, play и 14 точек данных. Чтобы построить дерево решений на основе этих данных, нам нужно сравнить прирост информации каждого из четырех деревьев, каждое из которых разделено по одному из четырех признаков. Разделение с наибольшим приростом информации будет считаться первым разделением, и процесс будет продолжаться до тех пор, пока каждый из дочерних узлов не будет иметь согласованные данные или пока прирост информации не станет равным 0.

Чтобы найти прирост информации от разделения с помощью Windy , мы должны сначала вычислить информацию в данных перед разделением. Исходные данные содержали девять «да» и пять «нет».

$I_{E}([9,5])=-{\frac {9}{14}}\log _{2}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0.94$

Разделение с использованием функции Windy приводит к образованию двух дочерних узлов: один для ветрового значения true, а другой для ветрового значения false. В этом наборе данных есть шесть точек данных с истинным значением ветра , три из которых имеют значение play (где play — целевая переменная) «да», а три — со значением « нет». Восемь оставшихся точек данных с переменным значением false содержат два «нет» и шесть «да». Информация узла «windy =true» рассчитывается с использованием приведенного выше уравнения энтропии. Поскольку в этом узле одинаковое количество «да» и «нет», мы имеем

$I_{E}([3,3])=-{\frac {3}{6}}\log _{2}{\frac {3}{6}}-{\frac {3}{6}}\log _{2}{\frac {3}{6}}=-{\frac {1}{2}}\log _{2}{\frac {1}{2}}-{\frac {1}{2}}\log _{2}{\frac {1}{2}}=1$

Для узла, где Windy = False, было восемь точек данных: шесть «да» и два «нет». Таким образом, мы имеем

$I_{E}([6,2])=-{\frac {6}{8}}\log _{2}{\frac {6}{8}}-{\frac {2}{8}}\log _{2}{\frac {2}{8}}=-{\frac {3}{4}}\log _{2}{\frac {3}{4}}-{\frac {1}{4}}\log _{2}{\frac {1}{4}}=0.81$

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

$I_{E}([3,3],[6,2])=I_{E}({\text{windy or not}})={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0.81=0.89$

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

$\operatorname {IG} ({\text{windy}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.94-0.89=0.05$

Чтобы построить дерево, необходимо рассчитать прирост информации от каждого возможного первого разделения. Лучшее первое разделение — это то, которое обеспечивает наибольший прирост информации. Этот процесс повторяется для каждого нечистого узла, пока дерево не будет завершено. Этот пример адаптирован из примера, приведенного в Witten et al.

Прирост информации также известен как индекс Шеннона в исследованиях биоразнообразия.

Уменьшение дисперсии

Представлено в КОРЗИНЕ, уменьшение дисперсии часто используется в тех случаях, когда целевая переменная является непрерывной (дерево регрессии), а это означает, что использование многих других показателей сначала потребует дискретизации перед их применением. Уменьшение дисперсии узла N определяется как общее уменьшение дисперсии целевой переменной Y вследствие разделения в этом узле:

$I_{V}(N)={\frac {1}{|S|^{2}}}\sum _{i\in S}\sum _{j\in S}{\frac {1}{2}}(y_{i}-y_{j})^{2}-\left({\frac {|S_{t}|^{2}}{|S|^{2}}}{\frac {1}{|S_{t}|^{2}}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(y_{i}-y_{j})^{2}+{\frac {|S_{f}|^{2}}{|S|^{2}}}{\frac {1}{|S_{f}|^{2}}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(y_{i}-y_{j})^{2}\right)$

где $S$, $S_{t}$, и $S_{f}$представляют собой набор индексов выборки перед разделением, набор индексов выборки, для которых сплит-тест верен, и набор индексов выборки, для которых сплит-тест является ложным, соответственно. Однако каждое из приведенных выше слагаемых действительно является оценкой дисперсии , записанной в форме без прямой ссылки на среднее значение.

Заменив $(y_{i}-y_{j})^{2}$ в формуле выше с несходством $d_{ij}$ между двумя объектами $i$ и $j$, критерий уменьшения дисперсии применяется к любому типу объектов, для которых можно вычислить попарные несходства.

Мера «доброты»

Используется CART в 1984 году, мера «хорошести» — это функция, которая стремится оптимизировать баланс способности раскола-кандидата создавать чистых детей с его способностью создавать детей одинакового размера. Этот процесс повторяется для каждого нечистого узла, пока дерево не будет завершено. Функция $\varphi (s\mid t)$, где $s$ является кандидатом, разделенным в узле $t$, определяется, как показано ниже

$\varphi (s\mid t)=2P_{L}P_{R}\sum _{j=1}^{\text{class count}}|P(j\mid t_{L})-P(j\mid t_{R})|$

где $t_{L}$ и $t_{R}$ являются левыми и правыми дочерними элементами узла $t$ использование разделения $s$, соответственно; $P_{L}$ и $P_{R}$ доли записей в $t$ в $t_{L}$ и $t_{R}$, соответственно; и $P(j\mid t_{L})$ и $P(j\mid t_{R})$ это пропорции класса $j$ записи в $t_{L}$ и $t_{R}$, соответственно.

Рассмотрим пример набора данных с тремя атрибутами: сбережения (низкий, средний, высокий), активы (низкий, средний, высокий), доход (числовое значение) и бинарная целевая переменная кредитного риска (хороший, плохой) и 8 точек данных. Полные данные представлены в таблице ниже. Чтобы запустить дерево решений, мы рассчитаем максимальное значение $\varphi (s\mid t)$используя каждую функцию, чтобы найти, какая из них разделит корневой узел. Этот процесс будет продолжаться до тех пор, пока все дети не станут чистыми или все $\varphi (s\mid t)$ значения ниже установленного порога.

Клиент	Экономия	Ресурсы	Доход (1000 долларов США)	Риск кредита
1	Середина	Высокий	75	Хороший
2	Низкий	Низкий	50	Плохой
3	Высокий	Середина	25	Плохой
4	Середина	Середина	50	Хороший
5	Низкий	Середина	100	Хороший
6	Высокий	Высокий	25	Хороший
7	Низкий	Низкий	25	Плохой
8	Середина	Середина	75	Хороший

Найти $\varphi (s\mid t)$ функций Что касается экономии , нам нужно отметить количество каждого значения. Исходные данные содержали три минимума, три средних и два максимума. Из низких показателей один имел хороший кредитный риск , а из средних и высоких - хороший кредитный риск имелся у четырех . Предположим, что кандидаты раскололись $s$ так, что записи с низкими сбережениями будут помещены в левый дочерний элемент, а все остальные записи будут помещены в правый дочерний элемент.

$\varphi (s\mid {\text{root}})=2\cdot {\frac {3}{8}}\cdot {\frac {5}{8}}\cdot \left(\left|\left({\frac {1}{3}}-{\frac {4}{5}}\right)\right|+\left|\left({\frac {2}{3}}-{\frac {1}{5}}\right)\right|\right)=0.44$

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

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

Использует

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

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

• Просто понять и интерпретировать. Люди могут понять модели дерева решений после краткого объяснения. Деревья также можно отображать графически, чтобы их было легко интерпретировать неспециалистам.
• Способен обрабатывать как числовые, так и категориальные данные. Другие методы обычно специализируются на анализе наборов данных, содержащих переменные только одного типа. (Например, правила отношений можно использовать только с номинальными переменными, а нейронные сети можно использовать только с числовыми переменными или категориальными величинами, преобразованными в значения 0–1.) Ранние деревья решений были способны обрабатывать только категориальные переменные, но более поздние версии, такие как как C4.5, не имеют этого ограничения.
• Требует небольшой подготовки данных. Другие методы часто требуют нормализации данных. Поскольку деревья могут обрабатывать качественные предикторы, нет необходимости создавать фиктивные переменные .
• Использует белый ящик или открытый ящик. модель. Если данная ситуация наблюдаема в модели, объяснение условия легко объясняется булевой логикой . Напротив, в модели черного ящика объяснение результатов обычно трудно понять, например, с помощью искусственной нейронной сети .
• Можно проверить модель с помощью статистических тестов. Это позволяет учитывать надежность модели.
• Непараметрический подход, который не делает никаких предположений относительно обучающих данных или остатков прогноза; например, никаких предположений о распределении, независимости или постоянной дисперсии
• Хорошо работает с большими наборами данных. Большие объемы данных можно анализировать с использованием стандартных вычислительных ресурсов в разумные сроки.
• Точность благодаря гибкому моделированию . Эти методы могут быть применены к медицинским исследованиям с повышенной точностью.
• Более точно отражает процесс принятия решений человеком, чем другие подходы. Это может быть полезно при моделировании человеческих решений/поведения.
• Устойчив к коллинеарности, особенно к ускорению.
• Встроенный выбор функций . Дополнительные ненужные функции будут использоваться реже, поэтому их можно будет удалить при последующих запусках. Иерархия атрибутов в дереве решений отражает важность атрибутов. Это означает, что функции сверху являются наиболее информативными.
• Деревья решений могут аппроксимировать любую логическую функцию, например XOR .

Ограничения

• Деревья могут быть очень ненадежными. Небольшое изменение в обучающих данных может привести к большим изменениям в дереве и, следовательно, к окончательным прогнозам.
• Известно, что задача обучения оптимального дерева решений является NP-полной при некоторых аспектах оптимальности и даже для простых концепций. Следовательно, практические алгоритмы обучения дерева решений основаны на эвристиках, таких как жадный алгоритм , в котором локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать получение глобально оптимального дерева решений. Чтобы уменьшить жадный эффект локальной оптимальности, были предложены некоторые методы, такие как дерево двойного информационного расстояния (DID).
• Обучающиеся, использующие дерево решений, могут создавать слишком сложные деревья, которые плохо обобщают данные обучения. (Это известно как переобучение . ) Чтобы избежать этой проблемы, необходимы такие механизмы, как сокращение (за исключением некоторых алгоритмов, таких как подход условного вывода, который не требует сокращения).
• Средняя глубина дерева, которая определяется количеством узлов или тестов до классификации, не обязательно будет минимальной или маленькой при различных критериях разделения.
• Для данных, включающих категориальные переменные с разным количеством уровней, прирост информации в деревьях решений смещен в пользу атрибутов с большим количеством уровней. Чтобы решить эту проблему, вместо выбора атрибута с наибольшим приростом информации можно выбрать атрибут с самым высоким коэффициентом прироста информации среди атрибутов, чей прирост информации превышает средний прирост информации. Это смещает дерево решений в сторону рассмотрения атрибутов с большим количеством различных значений, но при этом не дает несправедливого преимущества атрибутам с очень низким информационным потенциалом. Альтернативно, проблемы предвзятого выбора предикторов можно избежать с помощью подхода условного вывода. двухэтапный подход, или адаптивный выбор исключаемых функций.

Реализации

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

Примеры с открытым исходным кодом включают:

• ALGLIB , библиотека численного анализа C++, C# и Java с функциями анализа данных (случайный лес)
• KNIME , бесплатная платформа для анализа данных, отчетности и интеграции с открытым исходным кодом (деревья решений, случайный лес)
• Orange — набор инструментов для визуализации данных, машинного обучения и интеллектуального анализа данных с открытым исходным кодом (случайный лес).
• R (программная среда с открытым исходным кодом для статистических вычислений, которая включает в себя несколько реализаций CART, таких как пакеты rpart, party и randomForest),
• scikit-learn (бесплатная библиотека машинного обучения с открытым исходным кодом для языка программирования Python ).
• Weka (бесплатный пакет анализа данных с открытым исходным кодом, содержит множество алгоритмов дерева решений),

Известное коммерческое программное обеспечение:

• МАТЛАБ ,
• Microsoft SQL-сервер и
• РапидМайнер ,
• SAS Enterprise Майнер ,
• IBM SPSS Modeler ,

Расширения

Графики решений

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

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

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

Также возможно выборку дерева с помощью MCMC .

Дерево можно искать снизу вверх. Или можно построить несколько деревьев параллельно, чтобы сократить ожидаемое количество тестов до классификации.

См. также

• Обрезка дерева решений
• Бинарная диаграмма решений
• ЧАЙД
• КОРЗИНА
• Алгоритм ID3
• Алгоритм C4.5
• Пни решений , используемые, например, в AdaBoosting.
• Список решений
• Инкрементное дерево решений
• Альтернативное дерево решений
• Анализ структурированных данных (статистика)
• Дерево логистической модели
• Иерархическая кластеризация

Дальнейшее чтение

• Джеймс, Гарет; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2017). «Древовидные методы» (PDF) . Введение в статистическое обучение: с приложениями на R. Нью-Йорк: Спрингер. стр. 303–336. ISBN  978-1-4614-7137-0 .

Внешние ссылки

• Эволюционное обучение деревьев решений в C++
• Очень подробное объяснение получения информации как критерия разделения.