Введение в алгоритмы деревьев решений машинного обучения
Очевидные вопросы, которые следует задать при столкновении с широким спектром алгоритмов машинного обучения: «Какой алгоритм лучше подходит для конкретной задачи и какой из них мне следует использовать?»
Ответы на эти вопросы зависят от нескольких факторов, включая: (1) размер, качество и характер данных; (2) доступное вычислительное время; (3) Актуальность задачи; и (4) Что вы хотите делать с данными.
Это один из многих алгоритмов, о которых я писал в предыдущей статье.
В этой части я попытался максимально просто отобразить и кратко объяснить основные алгоритмы (хотя и не все), которые доступны для задач деревьев решений.
Алгоритмы дерева решений:
Деревья решений дают нам отличную модель машинного обучения, которую можно применять как к задачам классификации (значение «Да» или «Нет»), так и к задачам регрессии (непрерывная функция). Деревья решений представляют собой древовидную модель решений. Это один из способов отобразить алгоритм, который содержит только условные операторы управления.
· Итерационный дихотомизатор 3 (ID3)
Начнем с того, что дихотомизация означает разделение на две совершенно противоположные вещи. Алгоритм делит атрибуты на две группы, которые являются наиболее доминирующими атрибутами и другими для построения дерева. Затем он вычисляет прирост энтропии и информации для каждого атрибута. Таким образом можно определить наиболее доминирующий атрибут. Этот алгоритм строит дерево сверху вниз, начиная с корня, выбирая, какой атрибут будет проверяться на каждом заданном узле. По сути, каждый атрибут оценивается с помощью статистических средств, чтобы увидеть, какой атрибут лучше всего разделяет набор данных. Наилучший атрибут становится корневым, значения его атрибутов разветвляются. Процесс продолжается с остальными атрибутами. После выбора атрибута вернуться к нему невозможно.
Некоторые моменты, которые следует учитывать:
ID3 является предшественником алгоритмов C4.5 и C5.0
ID3 не гарантирует оптимального решения; он может застрять в локальных оптимумах
ID3 может переобучаться обучающим данным (чтобы избежать переобучения, меньшие деревья решений должны быть предпочтительнее более крупных)
ID3 использует жадный подход, выбирая лучший атрибут для разделения набора данных на каждой итерации (одно улучшение, которое можно сделать в алгоритме, может заключаться в использовании отслеживания с возвратом во время поиска оптимального дерева решений)
ID3 сложнее использовать для непрерывных данных
ID3 не работает с отсутствующими данными
· C4.5 и C5.0 (разные версии мощного подхода)
C4.5, следующая итерация Куинлана - это более новая версия ID3. Новые функции (по сравнению с ID3): (i) допускают как непрерывные, так и дискретные функции; (ii) обрабатывает неполные точки данных; (iii) решает проблему чрезмерной подгонки с помощью восходящей техники, обычно известной как «обрезка» (под обрезкой понимается удаление тех ветвей в нашем дереве решений, которые не вносят существенного вклада в процесс принятия решения); и (iv) различные веса могут применяться к функциям, которые составляют обучающие данные.
C5.0, последняя итерация Quinlan. Эта реализация защищена патентом и, вероятно, в результате редко реализуется (за пределами коммерческих пакетов программного обеспечения).
Некоторые моменты, которые следует учитывать:
Если вы обнаружите, что ID3 вам подходит, попробуйте C4.5 или C5.
Улучшения C4.5 по сравнению с ID3:
· Может работать как с дискретными, так и с непрерывными атрибутами
· Неважно, если у вас отсутствуют значения атрибутов.
· Обрезка деревьев (замена нерелевантных ветвей листовыми узлами)
Улучшения C5.0 по сравнению с C4.5:
· На несколько порядков быстрее
· Эффективность памяти
· Меньшие деревья решений
· Повышение (больше точности)
· Возможность взвешивания различных атрибутов
· Провеивание (снижение шума)
· Дерево классификации и регрессии (CART)
Термин «дерево классификации и регрессии» (CART) - это просто более крупный термин, который относится как к деревьям регрессии, так и к деревьям решений по классификации. Реализация CART очень похожа на C4.5; одно главное отличие состоит в том, что CART строит дерево на основе критерия численного разделения, рекурсивно применяемого к данным, тогда как C4.5 включает промежуточный этап построения наборов правил.
Некоторые моменты, которые следует учитывать:
CART разделяет переменные на основе числовых значений
· Автоматическое обнаружение взаимодействия методом хи-квадрат (CHAID)
CHAID строит небинарные деревья (т. Е. Деревья, в которых более двух ветвей могут присоединяться к одному корню или узлу). И CHAID, и CART будут строить деревья, где каждый (нетерминальный) узел определяет условие разделения. Следовательно, оба типа алгоритмов могут применяться для анализа проблем регрессии или классификации. CHAID создает все возможные перекрестные таблицы для каждого категориального предиктора до тех пор, пока не будет достигнут наилучший результат и дальнейшее разделение не будет выполнено. CHAID строит прогнозную модель (дерево), чтобы помочь определить, как переменные лучше всего объединяются, чтобы объяснить результат в данной зависимой переменной. Основное различие между CHAID и CART заключается в том, что CHAID использует многостороннее разбиение (более двух узлов). Принимая во внимание, что CART выполняет двоичное разбиение (каждый узел разбивается на два дочерних узла). Кроме того, CHAID предотвращает проблему переобучения - узел разделяется только в том случае, если выполняется критерий значимости.
Некоторые моменты, которые следует учитывать:
В анализе CHAID могут использоваться номинальные, порядковые и непрерывные данные, где непрерывные предикторы разбиты на категории с примерно равным количеством наблюдений.
CHAID особенно полезен, когда вы ищете закономерности в наборах данных с большим количеством категориальных переменных.
· Камень принятия решения
Модель машинного обучения, состоящая из одноуровневого дерева решений; дерево решений с одним внутренним узлом (корнем), которое непосредственно связано с конечными узлами (его листьями). Пень принятия решения делает прогноз, основанный на значении только одной входной функции. Из-за своей простоты пень часто демонстрирует низкую прогностическую эффективность, однако эта модель может быть очень эффективной при использовании таких операторов, как оператор AdaBoost. Пень решения может использоваться в качестве базовой модели во многих методах ансамбля машинного обучения, таких как упаковка и ускорение.
Некоторые моменты, которые следует учитывать:
Легко дрессировать
Уменьшает переобучение
Очень хорошо работает в ансамблевом режиме
· M5
M5 сочетает в себе обычное дерево решений с возможностью функций линейной регрессии в узлах. Помимо точности, он может выполнять задачи очень большой размерности - до сотен атрибутов. Дерево модели M5 является средством обучения дерева решений для задачи регрессии, что означает, что оно используется для прогнозирования значений переменной числового отклика Y. Хотя дерево M5 использует тот же подход с деревом CART при выборе среднеквадратичной ошибки в качестве функции примеси, оно не назначает константа для конечного узла, но вместо этого соответствует многомерной модели линейной регрессии. Хотя деревья M могут работать хорошо, они также могут иметь большое перекрытие.
Некоторые моменты, которые следует учитывать:
M5 можно использовать с функциями линейной регрессии в узлах
До скорого,
Bobcat.
