Изучение дерева решений

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Разработка функций Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k- означает Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор локального выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Схема машинного обучения
v т е

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

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

Общие [ править ]

Изучение дерева решений - это метод, обычно используемый в интеллектуальном анализе данных. ^[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)» является обобщающим термином, используемым для обозначения обеих вышеупомянутых процедур, впервые введенных Breiman et al. в 1984 году. ^[6] Деревья, используемые для регрессии, и деревья, используемые для классификации, имеют некоторое сходство, но также и некоторые различия, такие как процедура, используемая для определения места разделения. ^[6]

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

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

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

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

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

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

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

Показатели [ править ]

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

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

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

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

Для узла, где 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 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})|}$

где и - левый и правый дочерние элементы узла, использующего split , соответственно; и - пропорции записей в in и , соответственно; и и - пропорции записей класса в и , соответственно.${\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)}$

Чтобы найти экономию функции , нам нужно отметить количество каждого значения. Исходные данные содержали три минимума, три средних значения и два максимума. Из минимальных значений у одного был хороший кредитный риск, а из средних и высоких - у 4 был хороший кредитный риск . Предположим, что разделение-кандидат такое, что записи с низкой экономией будут помещены в левый дочерний элемент, а все остальные записи будут помещены в правый дочерний элемент.${\displaystyle \phi (s|t)}$${\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]
• Известно, что проблема обучения оптимальному дереву решений является NP-полной с точки зрения нескольких аспектов оптимальности и даже для простых концепций. ^{[26] [27]} Следовательно, практические алгоритмы обучения дереву решений основаны на эвристиках, таких как жадный алгоритм, в котором локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать возврат глобального оптимального дерева решений. Чтобы уменьшить жадный эффект локальной оптимальности, были предложены такие методы, как дерево двойных информационных расстояний (DID). ^[28]
• Обучающиеся дерева решений могут создавать слишком сложные деревья, которые плохо обобщаются на основе данных обучения. (Это известно как переобучение . ^[29] ) Чтобы избежать этой проблемы, необходимы такие механизмы, как отсечение (за исключением некоторых алгоритмов, таких как подход условного вывода, который не требует отсечения). ^{[15] [16]}
• Не гарантируется, что средняя глубина дерева, определяемая количеством узлов или тестов до классификации, будет минимальной или маленькой при различных критериях разделения. ^[30]
• Для данных, включающих категориальные переменные с разным количеством уровней, получение информации в деревьях решений смещено в пользу атрибутов с большим количеством уровней. ^[31] Тем не менее, проблема смещения выбора предиктора устраняется с помощью подхода условного вывода ^[15] , двухэтапного подхода ^[32] или адаптивного выбора функции с исключением по одному. ^[33]

Реализации [ править ]

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

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

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

Расширения [ править ]

Графики решений [ править ]

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

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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