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

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

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

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

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

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

Общий

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

Обучение на основе дерева решений — это метод, который обычно используется при интеллектуальном анализе данных. ^[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]}
• Комитеты деревьев решений (также называемые k-DT ^[10] ), ранний метод, который использовал алгоритмы рандомизированных деревьев решений для генерации нескольких различных деревьев из обучающих данных, а затем объединял их с помощью голосования большинства для генерации выходных данных. ^[11]
• Агрегированные (или упакованные) деревья решений, ранний ансамблевый метод, строит несколько деревьев решений путем многократной повторной выборки обучающих данных с заменой и голосования по деревьям для консенсусного прогноза. ^[12]
  • Случайный лесной классификатор — это особый тип бутстреп-агрегации.
• Ротационный лес – в котором каждое дерево решений обучается путем предварительного применения анализа главных компонент (PCA) к случайному подмножеству входных признаков. ^[13]

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

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

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

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

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

Метрики

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

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

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

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

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

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

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

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

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

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

Примесь Джини , индекс разнообразия Джини , ^[26] или индекс Джини-Симпсона в исследованиях биоразнообразия, назван в честь итальянского математика Коррадо Джини и используется алгоритмом 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 и представляют собой процент каждого класса, присутствующего в дочернем узле, который является результатом разделения дерева. ^[27] ${\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 — это взаимная информация.

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

Рассмотрим пример набора данных с четырьмя атрибутами: прогноз (солнечно, пасмурно, дождливо), температура (жарко, умеренно, прохладно), влажность (высокая, нормальная) и ветрено (истина, ложь) с двоичной (да или нет) целевой переменной, 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 приводит к двум дочерним узлам, один для значения windy true и один для значения windy false. В этом наборе данных есть шесть точек данных с истинным значением windy , три из которых имеют значение play (где play — целевая переменная) yes и три со значением play no. Восемь оставшихся точек данных со значением windy false содержат два no и шесть yes. Информация узла windy = true вычисляется с использованием уравнения энтропии выше. Поскольку в этом узле равное количество yes и no, мы имеем

${\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. ^[27]

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

Сокращение дисперсии

Представленное в 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 году ^[28] , мера "доброты" - это функция, которая стремится оптимизировать баланс между способностью кандидата на разделение создавать чистые потомки и его способностью создавать равновеликие потомки. Этот процесс повторяется для каждого нечистого узла, пока дерево не будет завершено. Функция , где - кандидат на разделение в узле , определяется следующим образом ${\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})|}$

где и являются левыми и правыми потомками узла, использующего split , соответственно; и являются пропорциями записей в и , соответственно; и и являются пропорциями записей класса в и , соответственно. ${\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 точек данных. ^[28] Полные данные представлены в таблице ниже. Чтобы начать дерево решений, мы вычислим максимальное значение использования каждой функции, чтобы найти, какая из них разделит корневой узел. Этот процесс будет продолжаться до тех пор, пока все дочерние элементы не станут чистыми или все значения не будут ниже установленного порогового значения. ${\displaystyle \varphi (s\mid t)}$ ${\displaystyle \varphi (s\mid t)}$

Чтобы найти экономию признака , нам нужно отметить количество каждого значения. Исходные данные содержали три низких, три средних и два высоких. Из низких один имел хороший кредитный риск , в то время как из средних и высоких 4 имели хороший кредитный риск . Предположим, что кандидат разделен таким образом, что записи с низкой экономией будут помещены в левого потомка, а все остальные записи будут помещены в правого потомка. ${\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}$

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

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

Использует

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

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

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

Ограничения

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

Реализации

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

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

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

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

• МАТЛАБ ,
• Microsoft SQL Server и
• RapidMiner ,
• SAS Enterprise Miner ,
• IBM SPSS Modeler ,

Расширения

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

В дереве решений все пути от корневого узла до листового узла проходят посредством конъюнкции или И. В графе решений можно использовать дизъюнкции (ИЛИ) для объединения двух дополнительных путей с использованием минимальной длины сообщения (МДС). ^[43] Графы решений были дополнительно расширены, чтобы позволить ранее неуказанным новым атрибутам изучаться динамически и использоваться в разных местах в графе. ^[44] Более общая схема кодирования приводит к лучшей точности прогнозирования и вероятностной оценке логарифмических потерь. ^{[ необходима цитата ]} В целом, графы решений выводят модели с меньшим количеством листьев, чем деревья решений.

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

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

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

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

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

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

Ссылки

1. Штудер, Маттиас; Ритчард, Гилберт; Габадиньо, Алексис; Мюллер, Николас С. (2011). «Анализ расхождений последовательностей состояний». Социологические методы и исследования . 40 (3): 471–510. doi :10.1177/0049124111415372. ISSN  0049-1241. S2CID  13307797.
2. Wu, Xindong; Kumar, Vipin; Ross Quinlan, J.; Ghosh, Joydeep; Yang, Qiang; Motoda, Hiroshi; McLachlan, Geoffrey J.; Ng, Angus; Liu, Bing; Yu, Philip S.; Zhou, Zhi-Hua (2008-01-01). "10 лучших алгоритмов в добыче данных". Knowledge and Information Systems . 14 (1): 1–37. doi :10.1007/s10115-007-0114-2. hdl : 10983/15329 . ISSN  0219-3116. S2CID  2367747.
3. Рокач, Лиор; Маймон, О. (2014). Интеллектуальный анализ данных с помощью деревьев решений: теория и приложения, 2-е издание . World Scientific Pub Co Inc. doi : 10.1142/9097. ISBN 978-9814590075. S2CID  44697571.
4. Шалев-Шварц, Шай; Бен-Дэвид, Шай (2014). "18. Деревья решений". Понимание машинного обучения. Издательство Кембриджского университета.
5. Куинлан, Дж. Р. (1986). «Индукция деревьев решений» (PDF) . Машинное обучение . 1 : 81–106. doi : 10.1007/BF00116251 . S2CID  189902138.
6. Rokach, L.; Maimon, O. (2005). "Нисходящая индукция классификаторов деревьев решений - обзор". IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews . 35 (4): 476–487. CiteSeerX 10.1.1.458.7031 . doi :10.1109/TSMCC.2004.843247. S2CID  14808716. 
7. Брейман, Лео; Фридман, Дж. Х.; Олшен, Р. А.; Стоун, К. Дж. (1984). Деревья классификации и регрессии . Монтерей, Калифорния: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8.
8. Фридман, Дж. Х. (1999). Стохастический градиентный бустинг. Архивировано 28 ноября 2018 г. на Wayback Machine . Стэнфордский университет.
9. Хасти, Т., Тибширани, Р., Фридман, Дж. Х. (2001). Элементы статистического обучения: добыча данных, вывод и прогнозирование. Нью-Йорк: Springer Verlag.
10. Хит, Д., Касиф, С. и Зальцберг, С. (1993). k-DT: Метод обучения с использованием множества деревьев. В трудах Второго международного семинара по обучению с использованием множества стратегий , стр. 138-149.
11. Хит, Д., Касиф, С. и Зальцберг, С. Л. (1996). Комитеты деревьев решений. В B. Gorayska и J. Mey (ред.), Cognitive Technology: In Search of a Humane Interface (стр. 305–317). Амстердам: Elsevier Science BV
12. Брейман, Л. (1996). «Бэггинг-предикторы». Машинное обучение . 24 (2): 123–140. doi : 10.1007/BF00058655 .
13. Родригес, Дж. Дж.; Кунчева, ЛИ ; Алонсо, К. Дж. (2006). «Ротационный лес: новый метод ансамбля классификаторов». Труды IEEE по анализу шаблонов и машинному интеллекту . 28 (10): 1619–1630. CiteSeerX 10.1.1.156.8277 . doi :10.1109/TPAMI.2006.211. PMID  16986543. S2CID  6847493. 
14. Ривест, Рон (ноябрь 1987 г.). «Списки решений для обучения» (PDF) . Машинное обучение . 3 (2): 229–246. doi : 10.1023/A:1022607331053 . S2CID  30625841.
15. Летам, Бен; Рудин, Синтия ; Маккормик, Тайлер; Мэдиган, Дэвид (2015). «Интерпретируемые классификаторы с использованием правил и байесовского анализа: построение лучшей модели прогнозирования инсульта». Annals of Applied Statistics . 9 (3): 1350–1371. arXiv : 1511.01644 . doi : 10.1214/15-AOAS848. S2CID  17699665.
16. Ван, Фултон; Рудин, Синтия (2015). "Falling Rule Lists" (PDF) . Журнал исследований машинного обучения . 38 . Архивировано из оригинала (PDF) 28-01-2016 . Получено 22-01-2016 .
17. Murthy, SK (1994). «Система индукции косых деревьев решений». Журнал исследований искусственного интеллекта . 2 (1): 1–32. doi : 10.1613/jair.63 .
18. Касс, Г. В. (1980). «Исследовательский метод исследования больших объемов категориальных данных». Прикладная статистика . 29 (2): 119–127. doi :10.2307/2986296. JSTOR  2986296.
19. Биггс, Дэвид; Де Виль, Барри; Суен, Эд (1991). «Метод выбора многоканальных разделов для классификации и деревьев решений». Журнал прикладной статистики . 18 (1): 49–62. Bibcode : 1991JApSt..18...49B. doi : 10.1080/02664769100000005. ISSN  0266-4763.
20. Ритчард, Г. (2013), « CHAID и более ранние методы контролируемых деревьев», в JJ McArdle и G. Ritschard (редакторы), Contemporary Issues in Exploratory Data Mining in the Behavioral Sciences , Quantitative Methodology Series, Нью-Йорк: Routledge, страницы 48-74. Препринт
21. Hothorn, T.; Hornik, K.; Zeileis, A. (2006). «Непредвзятое рекурсивное разбиение: структура условного вывода». Журнал вычислительной и графической статистики . 15 (3): 651–674. CiteSeerX 10.1.1.527.2935 . doi :10.1198/106186006X133933. JSTOR  27594202. S2CID  6074128. 
22. Strobl, C.; Malley, J.; Tutz, G. (2009). «Введение в рекурсивное разбиение: обоснование, применение и характеристики деревьев классификации и регрессии, бэггинга и случайных лесов». Психологические методы . 14 (4): 323–348. doi :10.1037/a0016973. PMC 2927982. PMID  19968396 . 
23. Janikow, CZ (1998). «Нечеткие деревья решений: проблемы и методы». IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics . 28 (1): 1–14. doi :10.1109/3477.658573. PMID  18255917.
24. Barsacchi, M.; Bechini, A.; Marcelloni, F. (2020). «Анализ усиленных ансамблей бинарных нечетких деревьев решений». Expert Systems with Applications . 154 : 113436. doi : 10.1016/j.eswa.2020.113436. S2CID  216369273.
25. Наджманн, Оливер (1992). Методы и эвристики для получения символических знаний из примеров (диссертация). Докторская диссертация.
26. "Выращивание деревьев решений". MathWorks .
27. Witten, Ian; Frank, Eibe; Hall, Mark (2011). Data Mining . Burlington, MA: Morgan Kaufmann. стр. 102–103. ISBN 978-0-12-374856-0.
28. Larose, Daniel T.; Larose, Chantal D. (2014). Обнаружение знаний в данных: введение в интеллектуальный анализ данных . Хобокен, Нью-Джерси: John Wiley & Sons, Inc. ISBN 9781118874059.
29. Гарет, Джеймс; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2015). Введение в статистическое обучение . Нью-Йорк: Спрингер. стр. 315. ISBN 978-1-4614-7137-0.
30. Ху, Лянъюань; Ли, Лихуа (2022-12-01). «Использование машинного обучения на основе деревьев для исследований в области здравоохранения: обзор литературы и серии случаев». Международный журнал исследований окружающей среды и общественного здравоохранения . 19 (23): 16080. doi : 10.3390/ijerph192316080 . ISSN  1660-4601. PMC 9736500. PMID 36498153  . 
31. Провост, Фостер, 1964- (2013). Наука о данных для бизнеса: [что вам нужно знать о добыче данных и аналитическом мышлении] . Фосетт, Том. (1-е изд.). Севастополь, Калифорния: O'Reilly. ISBN 978-1-4493-6132-7. OCLC  844460899.{{cite book}}: CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
32. Пирионеси С. Мадех; Эль-Дираби Тамер Э. (2020-06-01). «Роль аналитики данных в управлении инфраструктурными активами: преодоление проблем с размером и качеством данных». Журнал транспортной инженерии, часть B: Дорожные покрытия . 146 (2): 04020022. doi :10.1061/JPEODX.0000175. S2CID  216485629.
33. Мехтаа, Динеш; Рагхаван, Виджай (2002). «Приближения деревьев решений булевых функций». Теоретическая информатика . 270 (1–2): 609–623. doi : 10.1016/S0304-3975(01)00011-1 .
34. Хиафил, Лоран; Ривест, Р. Л. (1976). «Построение оптимальных бинарных деревьев решений является NP-полным». Information Processing Letters . 5 (1): 15–17. doi :10.1016/0020-0190(76)90095-8.
35. Murthy S. (1998). "Автоматическое построение деревьев решений из данных: многопрофильное исследование". Data Mining and Knowledge Discovery
36. Ben-Gal I. Dana A., Shkolnik N. и Singer (2014). "Эффективное построение деревьев решений методом двойного информационного расстояния" (PDF) . Quality Technology & Quantitative Management . 11 (1): 133–147. doi :10.1080/16843703.2014.11673330. S2CID  7025979. Архивировано из оригинала (PDF) 2016-06-04 . Получено 2014-02-13 .
37. Принципы интеллектуального анализа данных . 2007. doi :10.1007/978-1-84628-766-4. ISBN 978-1-84628-765-7. S2CID  45746.
38. Ben-Gal I. и Trister C. (2015). "Параллельное построение деревьев решений с постоянно невозрастающим ожидаемым числом тестов" (PDF) . Applied Stochastic Models in Business and Industry, Vol. 31(1) 64-78. Архивировано из оригинала (PDF) 2021-02-05 . Получено 2021-01-30 .{{cite web}}: CS1 maint: numeric names: authors list (link)
39. Дэн, Х.; Рунгер, Г.; Тув, Э. (2011). Меры смещения важности для многозначных атрибутов и решений. Труды 21-й Международной конференции по искусственным нейронным сетям (ICANN). стр. 293–300.
40. Куинлан, Дж. Росс (1986). «Индукция деревьев решений». Машинное обучение . 1 (1): 81–106. doi : 10.1007/BF00116251 .
41. Брандмайер, Андреас М.; Эрцен, Тимо фон; МакАрдл, Джон Дж.; Линденбергер, Ульман (2012). «Деревья моделей структурных уравнений». Психологические методы . 18 (1): 71–86. doi :10.1037/a0030001. hdl :11858/ 00-001M -0000-0024-EA33-9. PMC 4386908. PMID  22984789. 
42. Painsky, Amichai; Rosset, Saharon (2017). «Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance». Труды IEEE по анализу шаблонов и машинному интеллекту . 39 (11): 2142–2153. arXiv : 1512.03444 . doi : 10.1109/TPAMI.2016.2636831. PMID  28114007. S2CID  5381516.
43. "CiteSeerX".
44. Тан и Доу (2003)
45. Папагелис, А.; Каллес, Д. (2001). «Выведение деревьев решений с использованием эволюционных методов» (PDF) . Труды Восемнадцатой международной конференции по машинному обучению, 28 июня – 1 июля 2001 г. . стр. 393–400.
46. Баррос, Родриго К.; Басгалупп, МП; Карвальо, АЦПЛФ; Фрейтас, Алекс А. (2012). «Обзор эволюционных алгоритмов индукции дерева решений». Труды IEEE по системам, человеку и кибернетике . Часть C: Приложения и обзоры. 42 (3): 291–312. CiteSeerX 10.1.1.308.9068 . doi :10.1109/TSMCC.2011.2157494. S2CID  365692. 
47. Чипман, Хью А.; Джордж, Эдвард И.; Маккалок, Роберт Э. (1998). «Поиск модели Байесовского CART». Журнал Американской статистической ассоциации . 93 (443): 935–948. CiteSeerX 10.1.1.211.5573 . doi :10.1080/01621459.1998.10473750. 
48. Barros, RC; Cerri, R.; Jaskowiak, PA; Carvalho, ACPLF (2011). "Алгоритм индукции дерева решений снизу вверх с косым наклоном". Труды 11-й Международной конференции по проектированию и применению интеллектуальных систем (ISDA 2011) . стр. 450–456. doi :10.1109/ISDA.2011.6121697. ISBN 978-1-4577-1676-8. S2CID  15574923.

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

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

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

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