Изучение дерева решений - Decision tree learning - Wikipedia

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

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

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

Общее

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

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

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

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

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

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

${\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 г.^[6] Деревья, используемые для регрессии, и деревья, используемые для классификации, имеют некоторое сходство, но также и некоторые различия, такие как процедура, используемая для определения места разделения.^[6]

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

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

Частным случаем дерева решений является список решений,^[11] которое является односторонним деревом решений, так что каждый внутренний узел имеет ровно 1 листовой узел и ровно 1 внутренний узел в качестве дочернего (за исключением самого нижнего узла, единственный дочерний узел которого является единственным листовым узлом). Несмотря на то, что списки решений менее выразительны, их легче понять, чем общие деревья решений, из-за их дополнительной разреженности, но они позволяют использовать не жадные методы обучения.^[12] и накладывать монотонные ограничения.^[13]

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

• ID3 (Итерационный дихотомизатор 3)
• C4.5 (преемник ID3)
• КОРЗИНА (Дерево классификации и регрессии)^[6]
• Автоматическое обнаружение взаимодействия по хи-квадрат (ЧЭЙД). Выполняет многоуровневое разбиение при вычислении деревьев классификации.^[14]
• МАРС: расширяет деревья решений для лучшей обработки числовых данных.
• Деревья условного вывода. Подход, основанный на статистике, который использует непараметрические тесты в качестве критериев разделения, скорректированный для множественного тестирования, чтобы избежать переобучения. Этот подход приводит к беспристрастному выбору предикторов и не требует отсечения.^[15][16]

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

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

Метрики

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

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

Не путать с Коэффициент Джини.

Используемый алгоритмом CART (дерево классификации и регрессии) для деревьев классификации, примесь Джини является мерой того, как часто случайно выбранный элемент из набора будет неправильно помечен, если он был случайно помечен в соответствии с распределением ярлыков в подмножестве. Примесь Джини может быть вычислена путем суммирования вероятностей ${\displaystyle p_{i}}$ товара с этикеткой ${\displaystyle i}$ быть выбранным умноженным на вероятность ${\displaystyle \sum _{k\neq i}p_{k}=1-p_{i}}$ ошибки в классификации этого элемента. Он достигает своего минимума (нуля), когда все наблюдения в узле попадают в одну целевую категорию.

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

Чтобы вычислить примесь Джини для набора элементов с ${\displaystyle J}$ классы, предположим ${\displaystyle i\in \{1,2,...,J\}}$, и разреши ${\displaystyle p_{i}}$ быть долей элементов, помеченных классом ${\displaystyle 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}}$

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

Основная статья: Сбор информации в деревьях решений

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

Энтропия определяется следующим образом

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

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

$${\displaystyle \overbrace {IG(T,a)} ^{\text{Information Gain}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|a)} ^{\text{Sum of Entropy (Children)}}}$$

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

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

$${\displaystyle \overbrace {E_{A}\left(IG(T,a)\right)} ^{\text{Expected Information Gain}}=\overbrace {I(T;A)} ^{\text{Mutual Information between T and A}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|A)} ^{\text{Weighted Sum of Entropy (Children)}}}$$

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

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

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

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

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

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

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

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

Для узла, где ветреный= 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 IG({\text{windy}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.94-0.89=0.05}$

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

Снижение дисперсии

Представлено в CART,^[6] Уменьшение дисперсии часто используется в тех случаях, когда целевая переменная является непрерывной (дерево регрессии), что означает, что использование многих других показателей потребует сначала дискретизации перед применением. Уменьшение дисперсии узла 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 {1}{|S_{t}|^{2}}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(y_{i}-y_{j})^{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}}$ представляют собой набор индексов предварительно разделенной выборки, набор индексов выборки, для которых тест разделения является истинным, и набор индексов выборки, для которых тест разделения является ложным, соответственно. Каждое из приведенных выше слагаемых действительно отклонение оценки, однако, записываются в форме, не относящейся непосредственно к среднему значению.

Мера «добра»

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

${\displaystyle \phi (s|t)=2P_{L}P_{R}\sum _{j=1}^{ClassCount}|P(j|t_{L})-P(j|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|t_{L})}$ и ${\displaystyle P(j|t_{R})}$ пропорции класса ${\displaystyle j}$ записи в ${\displaystyle t_{L}}$ и ${\displaystyle t_{R}}$соответственно.

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

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

Найти ${\displaystyle \phi (s|t)}$ особенности сбережения, нам нужно отметить количество каждого значения. Исходные данные содержали три минимума, три средних значения и два максимума. Из низких у одного был хороший риск кредита в то время как из средних и высоких, у 4 были хорошие риск кредита. Предположим, что кандидат раскололся ${\displaystyle s}$ такие, что записи с низким сбережения будет помещен в левый дочерний элемент, а все остальные записи будут помещены в правый дочерний элемент.

${\displaystyle \phi (s|root)=2{\frac {3}{8}}*{\frac {5}{8}}*(|({\frac {1}{3}}-{\frac {4}{5}})|+|({\frac {2}{3}}-{\frac {1}{5}})|)=0.44}$

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

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

Использует

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

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

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

Ограничения

• Деревья могут быть очень ненадежными. Небольшое изменение в данные обучения может привести к большим изменениям в дереве и, как следствие, в окончательных прогнозах.^[22]
• Как известно, проблема изучения дерева оптимальных решений НП-полный при нескольких аспектах оптимальности и даже для простых концепций.^[26][27] Следовательно, практические алгоритмы обучения дереву решений основаны на эвристиках, таких как жадный алгоритм где на каждом узле принимаются локально оптимальные решения. Такие алгоритмы не могут гарантировать получение глобально оптимального дерева решений. Чтобы уменьшить жадный эффект локальной оптимальности, были предложены такие методы, как дерево двойных информационных расстояний (DID).^[28]
• Обучающиеся дерева решений могут создавать слишком сложные деревья, которые плохо обобщаются на основе данных обучения. (Это известно как переоснащение.^[29]) Такие механизмы, как обрезка необходимы, чтобы избежать этой проблемы (за исключением некоторых алгоритмов, таких как подход условного вывода, который не требует отсечения).^[15][16]
• Для данных, включающих категориальные переменные с разным количеством уровней, получение информации в деревьях решений смещен в пользу атрибутов с большим количеством уровней.^[30] Однако проблема предвзятого выбора предиктора устраняется подходом условного вывода,^[15] двухэтапный подход,^[31] или адаптивный выбор функции исключения по одному.^[32]

Реализации

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

Примеры включают

• Salford Systems CART (который лицензировал проприетарный код оригинальных авторов CART),^[6]
• IBM SPSS Modeler,
• RapidMiner,
• SAS Enterprise Майнер,
• Matlab,
• р (программная среда с открытым исходным кодом для статистических вычислений, которая включает несколько реализаций CART, таких как пакеты rpart, party и randomForest),
• Weka (бесплатный пакет для интеллектуального анализа данных с открытым исходным кодом, содержащий множество алгоритмов дерева решений),
• оранжевый,
• KNIME,
• Microsoft SQL Server [1], и
• scikit-learn (бесплатная библиотека машинного обучения с открытым исходным кодом для Python язык программирования).

Расширения

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

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

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

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

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

Дерево можно искать снизу вверх.^[38]

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

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

использованная литература

1. У, Синьдун; Кумар, Випин; Росс Куинлан, Дж .; Гош, Джойдип; Ян, Цян; Мотода, Хироши; Маклахлан, Джеффри Дж .; Нг, Ангус; Лю, Бинг; Yu, Philip S .; Чжоу, Чжи-Хуа (01.01.2008). «10 лучших алгоритмов интеллектуального анализа данных». Знания и информационные системы. 14 (1): 1–37. Дои:10.1007 / s10115-007-0114-2. ISSN  0219-3116. S2CID  2367747.
2. Пирьонеси С. Мадех; Эль-Дираби Тамер Э. (01.03.2020). «Аналитика данных в управлении активами: рентабельное прогнозирование индекса состояния дорожного покрытия». Журнал инфраструктурных систем. 26 (1): 04019036. Дои:10.1061 / (ASCE) IS.1943-555X.0000512.
3. Рокач, Лиор; Маймон, О. (2008). Интеллектуальный анализ данных с деревьями решений: теория и приложения. World Scientific Pub Co Inc. ISBN  978-9812771711.
4. Шалев-Шварц, Шай; Бен-Давид, Шай (2014). «18. Деревья решений». Понимание машинного обучения. Издательство Кембриджского университета.
5. Куинлан, Дж. Р. (1986). «Индукция деревьев решений» (PDF). Машинное обучение. 1: 81–106. Дои:10.1007 / BF00116251. S2CID  189902138.
6. Брейман, Лео; Friedman, J. H .; Ольшен, Р. А .; Стоун, К. Дж. (1984). Деревья классификации и регрессии. Монтерей, Калифорния: Уодсворт и Брукс / Коул Продвинутые книги и программное обеспечение. ISBN  978-0-412-04841-8.
7. Фридман, Дж. Х. (1999). Стохастическое повышение градиента. Стэндфордский Университет.
8. Хасти, Т., Тибширани, Р., Фридман, Дж. Х. (2001). Элементы статистического обучения: интеллектуальный анализ данных, вывод и прогнозирование. Нью-Йорк: Springer Verlag.
9. Брейман, Л. (1996). "Предикторы упаковки". Машинное обучение. 24 (2): 123–140. Дои:10.1007 / BF00058655.
10. Rodriguez, J. J .; Кунчева, Л. И .; Алонсо, К. Дж. (2006). «Вращающийся лес: новый метод ансамбля классификаторов». IEEE Transactions по анализу шаблонов и машинному анализу. 28 (10): 1619–1630. CiteSeerX  10.1.1.156.8277. Дои:10.1109 / TPAMI.2006.211. PMID  16986543. S2CID  6847493.
11. Ривест, Рон (ноябрь 1987 г.). «Списки решений обучения» (PDF). Машинное обучение. 3 (2): 229–246. Дои:10.1023 / А: 1022607331053. S2CID  30625841.
12. Летэм, Бен; Рудин, Синтия; Маккормик, Тайлер; Мэдиган, Дэвид (2015). «Интерпретируемые классификаторы с использованием правил и байесовского анализа: построение более совершенной модели прогнозирования инсульта». Анналы прикладной статистики. 9 (3): 1350–1371. arXiv:1511.01644. Дои:10.1214 / 15-AOAS848. S2CID  17699665.
13. Ван, Фултон; Рудин, Синтия (2015). «Падающие списки правил» (PDF). Журнал исследований в области машинного обучения. 38.
14. Касс, Г. В. (1980). «Исследовательский метод исследования больших объемов категориальных данных». Прикладная статистика. 29 (2): 119–127. Дои:10.2307/2986296. JSTOR  2986296.
15. Hothorn, T .; Хорник, К .; Зейлис, А. (2006). «Беспристрастное рекурсивное разбиение: структура условного вывода». Журнал вычислительной и графической статистики. 15 (3): 651–674. CiteSeerX  10.1.1.527.2935. Дои:10.1198 / 106186006X133933. JSTOR  27594202. S2CID  6074128.
16. Strobl, C .; Malley, J .; Тутц, Г. (2009). «Введение в рекурсивное разбиение: обоснование, применение и характеристики деревьев классификации и регрессии, мешков и случайных лесов». Психологические методы. 14 (4): 323–348. Дои:10.1037 / a0016973. ЧВК  2927982. PMID  19968396.
17. Яников, К. З. (1998). «Нечеткие деревья решений: проблемы и методы». IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics). 28 (1): 1–14. Дои:10.1109/3477.658573. PMID  18255917.
18. Barsacchi, M .; Бечини, А .; Марчеллони, Ф. (2020). «Анализ усиленных ансамблей двоичных нечетких деревьев решений». Экспертные системы с приложениями. 154: 113436. Дои:10.1016 / j.eswa.2020.113436.
19. Рокач, Л .; Маймон, О. (2005). «Нисходящая индукция классификаторов деревьев решений - обзор». Транзакции IEEE по системам, человеку и кибернетике - Часть C: Приложения и обзоры. 35 (4): 476–487. CiteSeerX  10.1.1.458.7031. Дои:10.1109 / TSMCC.2004.843247. S2CID  14808716.
20. Виттен, Ян; Франк, Эйбе; Холл, Марк (2011). Сбор данных. Берлингтон, Массачусетс: Морган Кауфманн. стр.102 –103. ISBN  978-0-12-374856-0.
21. Ларос, Дэниел Т .; Лароз, Шанталь Д. (2014). Обретение знаний в данных: введение в интеллектуальный анализ данных. Хобокен, Нью-Джерси: John Wiley & Sons, Inc. ISBN  9781118874059.
22. Гарет, Джеймс; Виттен, Даниэла; Хасти, Тревор; Тибширани, Роберт (2015). Введение в статистическое обучение. Нью-Йорк: Спрингер. стр.315. ISBN  978-1-4614-7137-0.
23. Провост, Фостер, 1964- (2013). Наука о данных для бизнеса: [что вам нужно знать о интеллектуальном анализе данных и аналитическом мышлении]. Фосетт, Том. (1-е изд.). Севастополь, Калифорния: О'Рейли. ISBN  978-1-4493-6132-7. OCLC  844460899.
24. Пирьонеси С. Мадех; Эль-Дираби Тамер Э. (01.06.2020). «Роль аналитики данных в управлении инфраструктурными активами: преодоление проблем, связанных с размером и качеством данных». Журнал транспортного машиностроения, часть B: Тротуары. 146 (2): 04020022. Дои:10.1061 / JPEODX.0000175.
25. Мехтаа, Динеш; Рагхаван, Виджай (2002). «Аппроксимации дерева решений булевых функций». Теоретическая информатика. 270 (1–2): 609–623. Дои:10.1016 / S0304-3975 (01) 00011-1.
26. Hyafil, Laurent; Ривест, Р.Л. (1976). «Построение оптимальных двоичных деревьев решений является NP-полным». Письма об обработке информации. 5 (1): 15–17. Дои:10.1016/0020-0190(76)90095-8.
27. Мурти С. (1998). «Автоматическое построение деревьев решений на основе данных: междисциплинарное исследование». Интеллектуальный анализ данных и обнаружение знаний
28. Бен-Гал И. Дана А., Школьник Н. и Зингер (2014). «Эффективное построение деревьев решений методом двойного информационного расстояния» (PDF). Качественные технологии и количественный менеджмент. 11 (1): 133–147. Дои:10.1080/16843703.2014.11673330. S2CID  7025979.
29. Принципы интеллектуального анализа данных. 2007. Дои:10.1007/978-1-84628-766-4. ISBN  978-1-84628-765-7.
30. Deng, H .; Runger, G .; Тув, Э. (2011). Меры смещения важности для многозначных атрибутов и решений. Материалы 21-й Международной конференции по искусственным нейронным сетям (ICANN). С. 293–300.
31. Brandmaier, Andreas M .; Эрцен, Тимо фон; МакАрдл, Джон Дж .; Линденбергер, Ульман (2012). «Деревья модели структурных уравнений». Психологические методы. 18 (1): 71–86. Дои:10.1037 / a0030001. HDL:11858 / 00-001M-0000-0024-EA33-9. ЧВК  4386908. PMID  22984789.
32. Паински, Амичай; Россет, Сахарон (2017). «Выбор переменных с перекрестной проверкой в ​​древовидных методах повышает эффективность прогнозирования». IEEE Transactions по анализу шаблонов и машинному анализу. 39 (11): 2142–2153. arXiv:1512.03444. Дои:10.1109 / TPAMI.2016.2636831. PMID  28114007. S2CID  5381516.
33. "CiteSeerX".
34. Тан и Доу (2003)
35. Папагелис, А .; Каллес, Д. (2001). «Разведение деревьев решений с использованием эволюционных методов» (PDF). Материалы восемнадцатой Международной конференции по машинному обучению, 28 июня - 1 июля 2001 г.. С. 393–400.
36. Баррос, Родриго С.; Basgalupp, M. P .; Карвалью, А. С. П. Л. Ф .; Фрейтас, Алекс А. (2012). "Обзор эволюционных алгоритмов индукции дерева решений". IEEE Transactions по системам, человеку и кибернетике. Часть C: Приложения и обзоры. 42 (3): 291–312. CiteSeerX  10.1.1.308.9068. Дои:10.1109 / TSMCC.2011.2157494. S2CID  365692.
37. Чипман, Хью А .; Джордж, Эдвард I; Маккалок, Роберт Э. (1998). «Поиск байесовской модели CART». Журнал Американской статистической ассоциации. 93 (443): 935–948. CiteSeerX  10.1.1.211.5573. Дои:10.1080/01621459.1998.10473750.
38. Barros, R.C .; Cerri, R .; Jaskowiak, P.A .; Карвалью, А.С.П.Л.Ф. (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 ++
• Очень подробное объяснение получения информации как критерия разделения