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

Алгоритм машинного обучения

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

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

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

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

Общий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особым случаем дерева решений является список решений ^[12] , который представляет собой одностороннее дерево решений, так что каждый внутренний узел имеет ровно 1 листовой узел и ровно 1 внутренний узел в качестве дочернего узла (за исключением самого нижнего узла, чей единственный дочерний узел — это единственный листовой узел). Хотя списки решений менее выразительны, их, возможно, легче понять, чем общие деревья решений, из-за их дополнительной разреженности ^{[ нужна цитация ]} , они позволяют налагать нежадные методы обучения ^{[13] и монотонные ограничения. [14]}

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

• ID3 (Итеративный дихотомизатор 3)
• C4.5 (преемник ID3)
• CART (дерево классификации и регрессии) ^[7]
• Автоматическое обнаружение взаимодействия по хи-квадрату (CHAID). Выполняет многоуровневое разбиение при вычислении деревьев классификации. ^{[15] [16] [17]}
• MARS : расширяет деревья решений для лучшей обработки числовых данных.
• Деревья условного вывода. Подход, основанный на статистике, который использует непараметрические тесты в качестве критериев разделения, с поправкой на множественное тестирование, чтобы избежать переобучения. Этот подход приводит к беспристрастному выбору предикторов и не требует обрезки. ^{[18] [19]}

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

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

Метрики

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

Оценка положительной корректности

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

${\displaystyle E_{P}=TP-FP}$

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

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

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

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

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

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

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

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

${\displaystyle \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}.}$

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

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

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

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

${\displaystyle \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}}$

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

$${\displaystyle \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)}}}$$

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

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

$${\displaystyle \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)}}}$$

${\displaystyle =-\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)}$

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

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

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

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

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

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

${\displaystyle 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» рассчитывается с использованием приведенного выше уравнения энтропии. Поскольку в этом узле одинаковое количество «да» и «нет», мы имеем

${\displaystyle 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, было восемь точек данных: шесть «да» и два «нет». Таким образом, мы имеем

${\displaystyle 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}$

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

${\displaystyle 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}$

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

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

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

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

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

Представленное в CART ^[7] сокращение дисперсии часто используется в тех случаях, когда целевая переменная является непрерывной (дерево регрессии), а это означает, что использование многих других показателей сначала потребует дискретизации перед их применением. Уменьшение дисперсии узла N определяется как общее уменьшение дисперсии целевой переменной Y вследствие разделения в этом узле:

${\displaystyle 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)}$

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

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

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

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

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

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

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

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

${\displaystyle \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}$

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

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

Использование

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

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

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

Ограничения

• Деревья могут быть очень ненадежными. Небольшое изменение в обучающих данных может привести к большим изменениям в дереве и, следовательно, к окончательным прогнозам. ^[26]
• Известно, что задача обучения оптимального дерева решений является NP-полной при некоторых аспектах оптимальности и даже для простых концепций. ^{[31] [32]} Следовательно, практические алгоритмы обучения дерева решений основаны на эвристиках, таких как жадный алгоритм , где локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать получение глобально оптимального дерева решений. Чтобы уменьшить жадный эффект локальной оптимальности, были предложены некоторые методы, такие как дерево двойного информационного расстояния (DID). ^[33]
• Обучающиеся, использующие дерево решений, могут создавать слишком сложные деревья, которые плохо обобщают данные обучения. (Это известно как переобучение . ^[34] ). Чтобы избежать этой проблемы, необходимы такие механизмы, как сокращение (за исключением некоторых алгоритмов, таких как подход условного вывода, который не требует сокращения). ^{[18] [19]}
• Средняя глубина дерева, которая определяется количеством узлов или тестов до классификации, не обязательно будет минимальной или маленькой при различных критериях разделения. ^[35]
• Для данных, включающих категориальные переменные с разным количеством уровней, прирост информации в деревьях решений смещен в пользу атрибутов с большим количеством уровней. ^[36] Чтобы решить эту проблему, вместо выбора атрибута с наибольшим приростом информации можно выбрать атрибут с самым высоким коэффициентом прироста информации среди атрибутов, чей прирост информации превышает средний прирост информации. ^[37] Это смещает дерево решений в сторону рассмотрения атрибутов с большим количеством различных значений, но при этом не дает несправедливого преимущества атрибутам с очень низким информационным потенциалом. Альтернативно, проблемы предвзятого выбора предикторов можно избежать с помощью подхода условного вывода ^[18] , двухэтапного подхода ^[38] или адаптивного выбора исключаемых признаков. ^[39]

Реализации

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

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

• 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). ^[40] Графики решений были дополнительно расширены, чтобы обеспечить возможность динамического изучения ранее не указанных новых атрибутов и их использования в разных местах графика. ^[41] Более общая схема кодирования приводит к повышению точности прогнозирования и вероятностной оценки логарифмических потерь. ^{[ нужна ссылка ]} В общем, графы решений подразумевают модели с меньшим количеством листьев, чем деревья решений.

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

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

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

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

Смотрите также

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

Рекомендации

1. Штудер, Матиас; Ритчард, Гилберт; Габадиньо, Алексис; Мюллер, Николас С. (2011). «Анализ несоответствий последовательностей состояний». Социологические методы и исследования . 40 (3): 471–510. дои : 10.1177/0049124111415372. ISSN  0049-1241. S2CID  13307797.
2. У, Синьдун; Кумар, Випин; Росс Куинлан, Дж.; Гош, Джойдип; Ян, Цян; Мотода, Хироши; Маклахлан, Джеффри Дж.; Нг, Ангус; Лю, Бинг; Ю, Филип С.; Чжоу, Чжи-Хуа (01 января 2008 г.). «10 лучших алгоритмов интеллектуального анализа данных». Знания и информационные системы . 14 (1): 1–37. дои : 10.1007/s10115-007-0114-2. hdl : 10983/15329 . ISSN  0219-3116. S2CID  2367747.
3. Рокач, Лиор; Маймон, О. (2014). Интеллектуальный анализ данных с помощью деревьев решений: теория и приложения, 2-е издание . World Scientific Pub Co Inc., номер документа : 10.1142/9097. ISBN 978-9814590075. S2CID  44697571.
4. Шалев-Шварц, Шай; Бен-Давид, Шай (2014). «18. Деревья решений». Понимание машинного обучения. Издательство Кембриджского университета.
5. Куинлан, младший (1986). «Индукция деревьев решений» (PDF) . Машинное обучение . 1 : 81–106. дои : 10.1007/BF00116251 . S2CID  189902138.
6. Рокач, Л.; Маймон, О. (2005). «Нисходящая индукция классификаторов деревьев решений - опрос». Транзакции IEEE в системах, человеке и кибернетике. Часть C: Приложения и обзоры . 35 (4): 476–487. CiteSeerX 10.1.1.458.7031 . дои : 10.1109/TSMCC.2004.843247. S2CID  14808716. 
7. Брейман, Лео; Фридман, Дж. Х.; Ольшен, РА; Стоун, CJ (1984). Деревья классификации и регрессии . Монтерей, Калифорния: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8.
8. Фридман, Дж. Х. (1999). Повышение стохастического градиента. Архивировано 28 ноября 2018 г. на Wayback Machine . Стэндфордский Университет.
9. Хасти Т., Тибширани Р., Фридман Дж. Х. (2001). Элементы статистического обучения: интеллектуальный анализ данных, логические выводы и прогнозирование. Нью-Йорк: Springer Verlag.
10. Брейман, Л. (1996). «Предсказатели мешков». Машинное обучение . 24 (2): 123–140. дои : 10.1007/BF00058655 .
11. Родригес, Джей-Джей; Кунчева Л.И. ; Алонсо, CJ (2006). «Вращающийся лес: новый метод ансамбля классификаторов». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 28 (10): 1619–1630. CiteSeerX 10.1.1.156.8277 . дои : 10.1109/TPAMI.2006.211. PMID  16986543. S2CID  6847493. 
12. Ривест, Рон (ноябрь 1987 г.). «Списки учебных решений» (PDF) . Машинное обучение . 3 (2): 229–246. дои : 10.1023/А:1022607331053 . S2CID  30625841.
13. Летэм, Бен; Рудин, Синтия ; Маккормик, Тайлер; Мэдиган, Дэвид (2015). «Интерпретируемые классификаторы с использованием правил и байесовского анализа: построение лучшей модели прогнозирования инсульта». Анналы прикладной статистики . 9 (3): 1350–1371. arXiv : 1511.01644 . дои : 10.1214/15-AOAS848. S2CID  17699665.
14. Ван, Фултон; Рудин, Синтия (2015). «Падающие списки правил» (PDF) . Журнал исследований машинного обучения . 38 . Архивировано из оригинала (PDF) 28 января 2016 г. Проверено 22 января 2016 г.
15. Касс, Г.В. (1980). «Исследовательский метод исследования больших объемов категориальных данных». Прикладная статистика . 29 (2): 119–127. дои : 10.2307/2986296. JSTOR  2986296.
16. Биггс, Дэвид; Де Виль, Барри; Суен, Эд (1991). «Метод выбора многопутевых разбиений для деревьев классификации и решений». Журнал прикладной статистики . 18 (1): 49–62. Бибкод : 1991JApSt..18...49B. дои : 10.1080/02664769100000005. ISSN  0266-4763.
17. Ритчард, Г. (2013), « CHAID и ранее контролируемые древовидные методы», в Дж. Дж. МакАрдле и Г. Ритчарде (редакторы), Современные проблемы исследовательского интеллектуального анализа данных в поведенческих науках , Серия количественных методологий, Нью-Йорк: Routledge, страницы 48-74. Препринт
18. Хоторн, Т.; Хорник, К.; Зейлейс, А. (2006). «Беспристрастное рекурсивное разбиение: структура условного вывода». Журнал вычислительной и графической статистики . 15 (3): 651–674. CiteSeerX 10.1.1.527.2935 . дои : 10.1198/106186006X133933. JSTOR  27594202. S2CID  6074128. 
19. Штробль, К.; Мэлли, Дж.; Тутц, Г. (2009). «Введение в рекурсивное секционирование: обоснование, применение и характеристики деревьев классификации и регрессии, мешков и случайных лесов». Психологические методы . 14 (4): 323–348. дои : 10.1037/a0016973. ПМЦ 2927982 . ПМИД  19968396. 
20. Яников, Чехия (1998). «Нечеткие деревья решений: проблемы и методы». Транзакции IEEE о системах, человеке и кибернетике. Часть B: Кибернетика . 28 (1): 1–14. дои : 10.1109/3477.658573. ПМИД  18255917.
21. Барсакки, М.; Бечини, А.; Марчеллони, Ф. (2020). «Анализ усиленных ансамблей бинарных нечетких деревьев решений». Экспертные системы с приложениями . 154 : 113436. doi : 10.1016/j.eswa.2020.113436. S2CID  216369273.
22. Найманн, Оливер (1992). Приемы и эвристика приобретения символических знаний на примерах (Диссертация). Докторская диссертация.
23. «Выращивание деревьев решений». Матворкс .
24. Виттен, Ян; Фрэнк, Эйбе; Холл, Марк (2011). Сбор данных . Берлингтон, Массачусетс: Морган Кауфманн. стр. 102–103. ISBN 978-0-12-374856-0.
25. Лароз, Дэниел Т.; Лароз, Шанталь Д. (2014). Обнаружение знаний в данных: введение в интеллектуальный анализ данных . Хобокен, Нью-Джерси: ISBN John Wiley & Sons, Inc. 9781118874059.
26. Гарет, Джеймс; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2015). Введение в статистическое обучение . Нью-Йорк: Спрингер. стр. 315. ISBN 978-1-4614-7137-0.
27. Ху, Лянъюань; Ли, Лихуа (01 декабря 2022 г.). «Использование древовидного машинного обучения для исследований в области здравоохранения: обзор литературы и серия примеров». Международный журнал экологических исследований и общественного здравоохранения . 19 (23): 16080. doi : 10.3390/ijerph192316080 . ISSN  1660-4601. ПМЦ 9736500 . ПМИД  36498153. 
28. Провост, Фостер, 1964- (2013). Наука о данных для бизнеса: [что нужно знать об интеллектуальном анализе данных и аналитическом мышлении] . Фосетт, Том. (1-е изд.). Севастополь, Калифорния: О'Рейли. ISBN 978-1-4493-6132-7. ОСЛК  844460899.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
29. Пирионеси С. Маде; Эль-Дираби Тамер Э. (01.06.2020). «Роль анализа данных в управлении инфраструктурными активами: преодоление проблем с размером и качеством данных». Журнал транспортной техники, Часть B: Тротуары . 146 (2): 04020022. doi :10.1061/JPEODX.0000175. S2CID  216485629.
30. Мехтаа, Динеш; Рагхаван, Виджай (2002). «Аппроксимация дерева решений булевых функций». Теоретическая информатика . 270 (1–2): 609–623. дои : 10.1016/S0304-3975(01)00011-1 .
31. Хиафил, Лоран; Ривест, Р.Л. (1976). «Построение оптимальных двоичных деревьев решений является NP-полным». Письма об обработке информации . 5 (1): 15–17. дои : 10.1016/0020-0190(76)90095-8.
32. Мерти С. (1998). «Автоматическое построение деревьев решений на основе данных: междисциплинарный опрос». Интеллектуальный анализ данных и обнаружение знаний
33. Бен-Гал И. Дана А., Школьник Н. и Сингер (2014). «Эффективное построение деревьев решений методом двойного информационного расстояния» (PDF) . Технология качества и количественный менеджмент . 11 (1): 133–147. дои : 10.1080/16843703.2014.11673330. S2CID  7025979. Архивировано из оригинала (PDF) 4 июня 2016 г. Проверено 13 февраля 2014 г.
34. Принципы интеллектуального анализа данных . 2007. doi : 10.1007/978-1-84628-766-4. ISBN 978-1-84628-765-7. S2CID  45746.
35. Бен-Гал И. и Тристер К. (2015). «Параллельное построение деревьев решений с постоянно не растущим ожидаемым количеством тестов» (PDF) . Прикладные стохастические модели в бизнесе и промышленности, Vol. 31(1) 64-78. Архивировано из оригинала (PDF) 5 февраля 2021 г. Проверено 30 января 2021 г.{{cite web}}: CS1 maint: numeric names: authors list (link)
36. Дэн, Х.; Рангер, Г.; Тув, Э. (2011). Смещение показателей важности для многозначных атрибутов и решений. Материалы 21-й Международной конференции по искусственным нейронным сетям (ICANN). стр. 293–300.
37. Куинлан, Дж. Росс (1986). «Индукция деревьев решений». Машинное обучение . 1 (1): 81–106. дои : 10.1007/BF00116251 .
38. Брандмайер, Андреас М.; Эрцен, Тимо фон; Макардл, Джон Дж.; Линденбергер, Ульман (2012). «Деревья моделей структурных уравнений». Психологические методы . 18 (1): 71–86. дои : 10.1037/a0030001. hdl : 11858/00-001M-0000-0024-EA33-9. ПМК 4386908 . ПМИД  22984789. 
39. Паинский, Амихай; Россе, Сахарон (2017). «Выбор переменных с перекрестной проверкой в ​​древовидных методах повышает эффективность прогнозирования». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 39 (11): 2142–2153. arXiv : 1512.03444 . дои : 10.1109/TPAMI.2016.2636831. PMID  28114007. S2CID  5381516.
40. "CiteSeerX".
41. Тан и Доу (2003)
42. Папагелис, А.; Каллес, Д. (2001). «Построение деревьев решений с использованием эволюционных методов» (PDF) . Материалы восемнадцатой международной конференции по машинному обучению, 28 июня – 1 июля 2001 г. стр. 393–400.
43. Баррос, Родриго К.; Басгалупп, депутат парламента; Карвальо, ACPLF; Фрейтас, Алекс А. (2012). «Обзор эволюционных алгоритмов индукции дерева решений». Транзакции IEEE по системам, человеку и кибернетике . Часть C: Приложения и обзоры. 42 (3): 291–312. CiteSeerX 10.1.1.308.9068 . дои : 10.1109/TSMCC.2011.2157494. S2CID  365692. 
44. Чипман, Хью А.; Джордж, Эдвард И.; Маккалок, Роберт Э. (1998). «Поиск байесовской модели CART». Журнал Американской статистической ассоциации . 93 (443): 935–948. CiteSeerX 10.1.1.211.5573 . дои : 10.1080/01621459.1998.10473750. 
45. Баррос, RC; Серри, Р.; Ясковяк, Пенсильвания; Карвальо, ACPLF (2011). «Алгоритм индукции наклонного дерева решений снизу вверх». Материалы 11-й Международной конференции по проектированию и применению интеллектуальных систем (ISDA 2011) . стр. 450–456. дои : 10.1109/ISDA.2011.6121697. ISBN 978-1-4577-1676-8. S2CID  15574923.

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

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

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

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