Что такое дерево решений?
Дерево решений – это иерархическая модель обучения, которая делит пространство с помощью правил принятия решений. Это контролируемый алгоритм машинного обучения, используемый как для задач классификации, так и для регрессии.
Дерево решений можно представить в виде структуры, похожей на блок-схему, где каждый внутренний узел представляет функцию (или атрибут), каждая ветвь представляет правило принятия решения, а каждый листовой узел представляет результат или метку класса.
Типы деревьев решений
- 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», чтобы понять, как выглядит наше дерево. Мы видим, что первая переменная разбивается в корневом узле.
Ссылки
- Дж. Джеймс, Д. Виттен, Т. Хасти, Р. Тибширани. Введение в статистическое обучение. Тексты Спрингера в статистике. 2013.
- Т. Хасти, Р. Тибширани, Дж. Фридман. Элементы статистического обучения. Серия Спрингера по статистике.