Дерево решений — это контролируемый метод обучения, который строит дерево решений с помощью функций и меток и изучает правила между функциями для решения задач классификации и регрессии.
Процесс использования дерева решений для принятия решения состоит в том, чтобы начать с корневого узла, протестировать соответствующие атрибуты признаков в элементах, подлежащих классификации, и выбрать выходную ветвь в соответствии с ее значением, пока она не достигнет конечного узла, а категория хранящийся в листовом узле, используется как результат решения.
Дерево решений состоит из следующих 3 элементов:
- Корневой узел: содержит полный набор образцов
- Внутренний узел: проверка атрибута соответствующей функции
- Конечный узел: результат решения (метка)
Как дерево решений отличает хорошие дыни от плохих?
(Эта картинка взята из книги Чжоу Чжихуа об арбузах, нарисованная вручную на моей доске)
Взяв в качестве примера вышеупомянутый арбуз, как мы можем определить, является ли дыня хорошей дыней? Характеристики такие: прозрачная текстура, слегка закрученные корни, зеленая на ощупь, в самый раз, вы построили дерево решений, чтобы сразу судить, хорошая это дыня или плохая?
Этапы судебного разбирательства следующие:
- По текстуре понятно, заведомо понятно, тогда идем налево и видим первый шаг
- Затем от текстуры ко второму слою, по диаграмме дерева решений мы видим, что корень слегка закручен
- Переходя к 3 слою, цветовая характеристика бирюзовая, из этого можно сделать вывод, что это хорошая дыня.
В соответствии с приведенным выше примером мы можем интуитивно получить оценку категории экземпляра.Пока указано конкретное значение каждой функции, процесс оценки дерева решений эквивалентен переходу от корневого узла к определенному конечному узлу в дерево. То, как проходит каждый шаг, определяется конкретными атрибутами каждой функции данных.
Итак, исходя из приведенного выше дерева, у нас возникает следующий вопрос, почему корневой узел является текстурой, а не корнем или другими функциями?
На каких критериях основывается дерево решений для выбора признаков? Как построить дерево решений?
3 шага к обучению дереву решений
Исходя из вышеперечисленных проблем, для построения качественного дерева решений дерево решений в основном имеет 3 шага.
Выбор признаков, генерация дерева решений, обрезка дерева решений
Выбор функции
Выбор функции заключается в выборе оптимального атрибута разделения и выборе функции из функций текущих данных в качестве стандарта разделения текущего узла. Надеемся, что в процессе непрерывного деления выборки, содержащиеся в узлах ветвления дерева решений, максимально принадлежат одному классу, то есть «чистота» узлов становится все выше и выше. Различные критерии выбора оптимальных функций разбиения также приводят к различным алгоритмам дерева решений.
- Информационная энтропия (information entropy)
- Прирост информации (information gain)
- Скорость получения информации (information gain ratio)
- Индекс Джини (Gini index)
Дерево решений принимает решения на основе древовидной структуры, которую можно использовать для классификации или регрессии Существуют деревья регрессии ID3, C4.5 и Cart. Обычно оптимальная функция выбирается рекурсивно, и обучающие данные делятся в соответствии с этой функцией, так что каждый набор подданных имеет наилучший процесс принятия решений, а дерево решений надеется развиваться в сторону самой быстрой и более чистой подсистемы. -набор.
Генерация дерева решений
| генеративный алгоритм | Критерии классификации |
|---|---|
| ID3 | получение информации |
| C4.5 | Скорость получения информации |
| CART | Индекс Джини |
ID3
ID3 вполучение информацииСамые большие признаки делятся как узлы, и дерево решений строится рекурсивно до тех пор, пока не будут разделены все признаки.
Прирост информации означает, что информация о признаке X, как известно, делает информацию класса Yстепень снижения неопределенности. Указывает разницу между энтропией до и после деления, чем больше разница, тем больше выигрыш. Определена энтропия до деления, и чем меньше скорректированная энтропия после деления, тем больше конечный прирост информации.
Принимая решения, мы всегда надеемся развиваться в направлении самого быстрого подмножества с более высокой чистотой, а чем объясняется более высокая чистота? Чем выше чистота, чем больше разница между признаками, тем лучше выбор признаков.
конкретный метод
- Начиная с корневого узла, вычислить информационный прирост всех возможных признаков для узла и выбрать признак с наибольшим значением информационного прироста в качестве признака раздела узла;
- Создавать дочерние узлы из разных значений признака;
- Затем рекурсивно вызовите описанный выше метод на дочерних узлах, чтобы построить дерево решений;
- До тех пор, пока прирост информации по всем функциям не будет очень мал или нельзя будет выбрать ни одну функцию, будет получено окончательное дерево решений.
Прирост информации смещается в сторону функций с большим количеством значений
Получение информации хорошо работает при наличии дискретных данных с меньшим количеством категорий, но эффект очень неудовлетворителен при наличии признаков с большим количеством значений.
Что касается смещения прироста информации к признакам с большим количеством значений, я думаю, что причина в том, что когда признаки имеют больше значений, чистота подмножества, полученного путем деления этого признака, с большей вероятностью будет выше (сравнение и значение, скорее всего, будут выше). выше). Следовательно, энтропия после деления ниже. Поскольку энтропия до деления постоянна, прирост информации больше, поэтому прирост информации более смещен в сторону признаков с большим количеством значений.
Может быть лучше понятен более экстремальный пример: если значение признака А может разделить каждую выборку на узел (например, такие признаки, как нумерация), часть условной энтропии будет равна 0, что означает, что ситуация Прирост информации при условии достигло максимального значения, поэтому алгоритм ID3 обязательно выберет признак A. Но, очевидно, мы знаем, что эта фича А явно не лучший выбор.
Так почему же скорость получения информации улучшает ситуацию? Давайте сначала посмотрим на формулу для расчета коэффициента прироста информации:
Также известная как внутренняя информация функции A,
На самом деле это мера неопределенности классификации набора данных D с разными значениями признака A. Если значений признака А больше, то неопределенность обычно будет больше, тогда
будет крупнее и
будет меньше, что эквивалентно умножению информационного прироста на штрафной коэффициент, а именно:
Особенности ID3
- Выберите функции с большим приростом информации для построения дерева решений, и прирост информации будет смещен в сторону тех функций с большим количеством значений (это также причина, по которой C4.5 принимает скорость прироста информации)
- Только процесс генерации дерева легко переобучить
- Может обрабатывать только дискретные данные
- Не могу обработать пропущенные значения
C4.5
ID3 улучшен, скорость получения информации используется для выбора признаков, а дерево решений строится рекурсивно.
C4.5 Особенности
- Улучшите ID3 и используйте скорость получения информации для выбора функций
- Может обрабатывать непрерывные и дискретные типы
- Может обрабатывать пропущенные значения
- Дерево выбора текстуры
Cart
CART (дерево классификации и регрессии)Алгоритм дерева классификации и регрессии может использоваться как для классификации, так и для регрессии.В этой части мы в основном сосредоточимся на создании его дерева классификации.
Дерево классификации ТЕЛЕГИ
В отличие от ID3 и C4.5, CART предполагает, что дерево решений является бинарным деревом, значениями внутренних признаков узла являются «Да» и «Нет», левая ветвь — это ветвь со значением «Да», а правая ветвь - это значение "Нет" "ветви.
Такое дерево решений эквивалентно рекурсивному делению пополам каждого признака, разделяющему входное пространство (то есть пространство признаков) на конечное число единиц.
Дерево классификации CART использует индекс Джини для выбора оптимальной точки разделения оптимальной функции Конкретный процесс выглядит следующим образом.
- Начиная с корневого узла, вычислите индекс Джини существующих признаков для узла, для каждого признака, такого как A, а затем для каждого возможного значения, такого как a, в соответствии с результатом пары точек выборки A=a: и «Нет» делится на две части, используя
-
Среди всех возможных признаков А и всех возможных значений а этого признака выбрать в качестве оптимального признака и оптимальной точки сегментации признак с наименьшим индексом Джини и соответствующее ему значение, а затем по оптимальному признаку и оптимальной точке сегментации разделить набор данных на два, создайте два дочерних узла.
-
Вышеупомянутые шаги вызываются рекурсивно для двух дочерних узлов до тех пор, пока количество выборок в узле не станет меньше порогового значения, или индекс Джини набора выборок не станет меньше порогового значения, или остановятся после того, как признаков больше не будет.
-
Создайте дерево классификации CART.
Дерево регрессии CART
Дерево регрессии — это модель дерева решений, которую можно использовать для регрессии.Дерево регрессии соответствует разделению входного пространства (т. е. пространства признаков) и выходного значения на единицу деления.
В отличие от дерева классификации, дерево регрессии использует эвристический метод для разделения входного пространства, оно будет проходить по всем входным переменным и находитьОптимальная переменная сегментации j и оптимальная точка сегментации s, то есть выберите j-й признак xj и его значение s, чтобы разделить входное пространство на две части, а затем повторите эту операцию.
А как найти оптимальные j и s получается путем сравнения ошибок разных делений. Ошибка разделения входного пространства измеряется методом наименьших квадратов истинного значения и предсказанного значения разделенной области, а именно
где f(xi) — прогнозируемое значение каждой единицы деления, а это прогнозируемое значение — среднее значение значений каждой точки выборки в единице.
Тогда решение j и s может быть выполнено с помощью
R1(j,s) и R2(j,s) — две разделенные области.
Метод генерации
- Выберите оптимальную переменную сегментации j и оптимальную точку сегментации s, решите и пройдите все функции, просмотрите все значения фиксированных функций и найдите (j, s), благодаря которому приведенная выше формула достигает минимального значения.
- Разделите область с выбранным (j, s) и определите прогнозируемое значение для этой области
- Продолжайте вышеуказанные шаги для обоих субрегионов, пока не будет выполнено условие остановки.
- Создание деревьев регрессии
обрезка дерева решений
Обрезка предназначена для того, чтобы избежать переобучения модели дерева решений, потому что алгоритм дерева решений продолжает делить узлы, чтобы максимально правильно классифицировать обучающие выборки в процессе обучения, поэтому это приведет к слишком большому количеству ветвей во всем дереве, что средства приводит к переоснащению.
Существует два типа обрезки дерева решений: предварительная обрезка и постобрезка.
предварительная обрезка
Предварительная обрезка означает, что в процессе построения дерева решений каждый узел оценивается перед разделением.Если разделение текущего узла не может привести к улучшению производительности обобщения модели дерева решений, текущий узел не будет разделен , И пометить текущий узел как конечный узел.
после обрезки
Постобрезка заключается в том, чтобы сначала построить все дерево решений, а затем изучить нелистовые узлы снизу вверх.Если поддерево, соответствующее узлу, заменить листовым узлом, производительность обобщения может быть улучшена, затем заменить поддерево с листовыми узлами.