Что такое дерево решений?

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

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

Типы деревьев решений

  • CHAID (автоматическое обнаружение взаимодействия по хи-квадрату) — метод, созданный Гордоном В. Кассом в 1980 году. CHAID используется для категориальных данных и использует статистические тесты (такие как тесты хи-квадрат или F-тест). для определения разделения функций. Его часто используют в социальных науках и исследованиях рынка.
  • CART (деревья классификации и регрессии) Бреймана, Фридмана, Олсена и Стоуна в 1984 году. Это универсальный тип дерева решений, который может решать задачи как классификации, так и регрессии. Он использует критерий примеси Джини для классификации и среднеквадратическую ошибку для регрессии для разделения данных.
  • ID3 (Итеративный дихотомизатор 3), разработанный Куинланом в 1986 году. ID3 — это классический алгоритм дерева решений, который использует энтропию и прирост информации для определения наилучшего разделения. В основном он используется для задач классификации.
  • C4.5 от Quinlan в 1993 году. Это расширение ID3. C4.5 также использует энтропию и сбор информации, но может решать как задачи классификации, так и регрессии. Кроме того, C4.5 обрабатывает пропущенные значения и категориальные функции.

Критерий разделения

  • CHAID использует статистический тест хи-квадрат в качестве критерия разделения для определения взаимодействия между категориальными переменными. Критерий хи-квадрат оценивает независимость между двумя категориальными переменными путем сравнения наблюдаемых частот в таблице непредвиденных обстоятельств с ожидаемыми частотами в предположении независимости. Анализ CHAID разбивает цель на две или более категории, которые называются исходными или родительскими узлами, а затем узлы разбиваются с помощью статистических алгоритмов на дочерние узлы.
    После первоначального разделения CHAID приступает к рекурсивному процессу. Он исследует каждую ветвь (категорию) выбранной переменной и определяет, могут ли дальнейшие разделения привести к статистически значимым взаимосвязям. CHAID продолжает этот процесс до тех пор, пока не достигнет критерия остановки, которым может быть предопределенная максимальная глубина, минимальный размер выборки в узле или отсутствие статистически значимых разбиений.
    На каждом этапе рекурсии CHAID оценивает, является ли разделение статистически значимым, используя тест хи-квадрат или F-тест. Если значение p из теста ниже определенного порога (часто определяемого уровнем значимости, например 0,05), разделение считается значимым, и алгоритм продолжает работу. Рекурсивный процесс разделения продолжается до тех пор, пока не будет выполнен критерий остановки. Это гарантирует, что дерево не станет слишком сложным и поможет предотвратить переобучение.
  • КОРЗИНА. Для классификации CART использует Примесь Джини.

где fi — это доля примеров класса i в tузле, а m — количество классов.
Обеспечено улучшение при расщеплении – это изменение примеси до и после расщепления.

где pL и pR — это доля примеров, которые после разделения попадают в левый и правый узел соответственно.

  • ID3 и C4.5 используют энтропию и прирост информации.

Где IG (Получение информации)

Коэффициент получения информации (IGR)

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

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

Критерии остановки и обрезка

Критерии остановки

  • Все примеры, присвоенные узлу, относятся к одному и тому же классу.
  • Никакого разделения для разделения данных не обнаружено.
  • Количество примеров в узле меньше заранее определенного числа (например, если примеров меньше 10, дальнейшее разделение не требуется).
  • Прирост от примесей в узле не падает ниже заранее определенного порога.
  • Дерево достигает максимальной глубины.

Обрезка

  • Сокращение затрат и сложности (CART).

-R(t) — ошибка дерева с корнем в узле t.
— C(t) — количество листьев, выходящих из узла t.< br /> — Параметр α определяет относительный вес между точностью и сложностью дерева.
— CART использует 10-кратную перекрестную проверку данных обучения для оценки альфа. Итеративно для обучения дерева используются 9 групп, а для тестирования — одна группа.
— Дерево обучается с использованием 9 групп и сокращается с использованием всех возможных альф (которые конечны).
— Каждая сокращена дерево тестируется на оставшемся наборе.
- Процесс повторяется 10 раз, и значение альфа, которое возвращает лучшую ошибку обобщения, используется для построения окончательного дерева с использованием всех данных.

  • Статистическая обрезка (C4.5)

-C4.5 оценивает ошибку в листьях, используя верхнее значение достоверности (это параметр) нормального распределения вместо прямого использования ошибки.
- Ошибка поддерева представляет собой взвешенную сумму ошибок каждого из них. его листьев.
- Эта ошибка имеет тенденцию увеличиваться, когда в листе меньше примеров.
- Следовательно, листья с небольшим количеством экземпляров имеют тенденцию быть обрезанными.

Преимущества и недостатки деревьев решений

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

  • Легко понять неспециалистам. Можно преобразовать в правила.
  • Обработка как номинальных, так и числовых атрибутов.
  • Хорошо управляйте неинформативными или избыточными атрибутами.
  • Они могут работать с пропущенными значениями.
  • Непараметрический метод. Никакого заранее определенного представления о концепции, которую предстоит изучить.
  • Простая настройка параметров. Имеют очень мало параметров.

Недостатки

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

Пример Python

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

Эти наборы данных состоят из лепестков и чашелистиков трех разных типов ирисов (Setosa, Versicolour и Virginica), хранящихся в numpy.ndarray размером 150x4.

Строки представляют собой образцы, а столбцы: длина чашелистика, ширина чашелистика, длина лепестка и ширина лепестка, но в нашем примере для простоты мы будем использовать только первые две функции.

Мы импортируем пакеты и разделяем данные на функции и целевой класс.

Мы будем использовать «plot_tree», чтобы понять, как выглядит наше дерево. Мы видим, что первая переменная разбивается в корневом узле.

Ссылки

  1. Дж. Джеймс, Д. Виттен, Т. Хасти, Р. Тибширани. Введение в статистическое обучение. Тексты Спрингера в статистике. 2013.
  2. Т. Хасти, Р. Тибширани, Дж. Фридман. Элементы статистического обучения. Серия Спрингера по статистике.