Проблема классификации
Во входящем наборе данных каждый экземпляр описывается как набор атрибутов и одна специальная метка класса. Проблема классификации — это задача найти модель, которая может правильно предсказать метку класса на основе значений различных атрибутов.
Дерево решений
Дерево решений можно определить с точки зрения его четырех компонентов:
1. Корневой узел: это точка доступа к дереву решений.
2. Ветвь: соединение между двумя узлами
3. Лист: конечный узел или конечный узел в дереве.
4. Внутренний узел: узлы, находящиеся между корневым и конечным узлами.
Может быть несколько правильно классифицирующих деревьев решений, которые можно создать для любого данного набора данных.
Как работает дерево решений
Пусть Tn будет набором доступных экземпляров в n-м узле, а c = {c1, c2, c3…cm} будет m метками классов.
1 · Если все экземпляры в Tn имеют одинаковые метки класса, то n является самим узлом Leaf и ему должна быть присвоена одна и та же метка класса.
2. Если Tn имеет более одной метки класса, присвоенной экземплярам, то идентифицируется условие проверки атрибута, которое разбивает данные на меньшие подмножества более похожих меток класса.
3. Дочерний узел создается для каждого результата тестового условия, и экземпляры Tn распределяются между этими двумя новыми узлами на основе результата.
4. Затем этот алгоритм рекурсивно применяется к каждому созданному таким образом дочернему узлу.
Однако есть некоторые оговорки —
Базовый алгоритм будет работать наиболее эффективно, если в обучающих данных присутствуют всевозможные комбинации значений всех атрибутов и каждая комбинация имеет уникальную метку класса.
Если в узле все экземпляры имеют одинаковые значения атрибутов, но разные метки класса, то класс узла определяется на основе наиболее часто встречающегося класса.
Разделение экземпляров
Это ключевой вопрос при построении дерева решений. В основном он состоит из двух частей —
1. Как задать условие проверки атрибута?
2. Как определить лучший сплит?
Для бинарных атрибутов, таких как пол, условие проверки может дать только два возможных результата. Для номинальных атрибутов, таких как семейное положение, алгоритм может произвести столько разбиений, сколько в нем категорий, или будет (2^(k-1)–1) способов возможных бинарных разбиений.
Для порядковых атрибутов, таких как size, убедитесь, что порядок сохраняется при разделении.
Числовые атрибуты, такие как доход, также могут использоваться для создания двоичных или множественных разделений.
Как решить, является ли разделение оптимальным
Качество разделения можно определить путем сравнения разделения классов, созданного условием, с исходным распределением в узле.
Показатели примесей. Пусть m будет общим количеством классов, присутствующих в узле, а pi будет долей экземпляров одного класса i, присутствующих в этом узле. узел.
Чтобы определить выигрыш при выполнении разделения, значение примеси вычисляется до разделения (в родительском узле) и после разделения (дочерние узлы). Чем выше выигрыш, тем лучше сплит.
Где M — используемая мера примеси (одна из них), n — количество экземпляров в родительском узле, а ni — количество экземпляров в дочернем узле i.
Таким образом, чтобы максимизировать выигрыш, нам нужно минимизировать средневзвешенное значение меры примеси в дочернем узле.
Интуиция, стоящая за мерой примесей для двух классов, заключается в том, что они ниже на краях или в более чистом распределении узлов.
Поговорим о примесной мере энтропии — сумме pi(log2(pi)). Недостатком является то, что эта мера благоприятствует разбиению, которое создает множество дочерних узлов, каждый из которых содержит чистые экземпляры, поскольку это максимизирует выигрыш. Однако это можно исправить, введя фактор, наказывающий такое поведение. Здесь k — количество дочерних узлов.
и усиление затем масштабируется как –
Рассмотрим пример, чтобы лучше понять этот момент. Допустим, Split создает 10 классов, каждый из которых содержит один или чистый экземпляр. Таким образом, значение pi равно 0 или 1. Таким образом, энтропия дочернего узла рассчитывается как - p1 = 0 и p2 = 1 в каждом узле, поэтому -
Таким образом, усиление — это дельта-энтропия или —
Однако, если мы рассмотрим только что описанный выше фактор разделить информацию и масштабируем усиление, мы получим:
Критерий остановки
Когда мы остановимся при росте нашего дерева решений или когда перестанем продолжать создавать дочерние узлы? Есть несколько простых правил, которым можно следовать, чтобы определить точку остановки:
1. Все экземпляры имеют одинаковую метку класса
2. Все экземпляры имеют одинаковые значения атрибутов
3. Количество экземпляров падает ниже заданного минимального порога.
Несколько пунктов о многоходовке против бинарных сплитов –
1. Если номинальный атрибут разделен на все его значения, то его нельзя использовать снова для создания разделения по этой ветви дерева.
2. Бинарные разбиения делают атрибут доступным для дальнейшего разбиения по ветке.
3. Но несколько двоичных разбиений на один числовой атрибут приводят к менее интерпретируемому дереву.
4. Одним из критических недостатков многостороннего разделения является то, что оно приводит к недостаточному объему данных на следующем уровне.
Как обрабатывать отсутствующие значения в деревьях решений
Значения некоторых атрибутов могут отсутствовать. Существует механизм обработки этих пропущенных значений при изучении дерева решений. Есть два способа сделать это -
1. Игнорировать пропущенные значения и построить дерево
2. Создайте частичные или взвешенные экземпляры.
Давайте рассмотрим два способа создания деревьев, когда в экземпляре класса setosa (из набора данных iris) отсутствуют значения ширины лепестка и длины лепестка.
На первом рисунке мы распределили частичные экземпляры по всем узлам в зависимости от количества строк экземпляра класса в узле и листе. Например, в самой правой зеленой ветви здесь лежит (46/100)*(100/149)=0,31, или 0,31 доля экземпляра с пропущенным значением.
Если у нас есть входящий тестовый экземпляр с отсутствующим значением ширины лепестка, то, используя второе дерево, мы можем рассчитать вероятности экземпляра, принадлежащего любому из листьев, как показано. Таким образом, экземпляр будет принадлежать наиболее вероятному значению, в данном случае это Versicolor.
Сокращение
Если дерево решений становится слишком длинным, оно слишком хорошо подходит для обучающих данных и, таким образом, может не давать обобщенных прогнозов для будущего тестового примера. Для обработки таких сценариев существуют методы, позволяющие уменьшить или обрезать размер дерева. Обрезка бывает двух видов — предварительная и постобрезная.
Предварительная обрезка останавливаеталгоритм до того, как будет создано полностью выросшее дерево. Критерии остановки:
1. Расширение текущего узла существенно не увеличивает прирост
2. Нет статистически значимой связи между каким-либо атрибутом и классами в узле.
Пост-обрезка — наиболее часто используемый метод из двух. Он обрезает взрослое дерево снизу вверх. Ключевые моменты:
- Поднятие поддерева: поднять более низкое поддерево, чтобы заменить более высокое.
2. Замена поддерева: можно заменить целое поддерево листом. Метки классов определяются в соответствии с большинством классов.
Регрессия с использованием деревьев решений
В случае проблемы регрессии мы пытаемся предсказать значение вместо метки класса. В этом случае прогнозируемое значение дерева представляет собой среднее значение y hat для обучающих экземпляров, присутствующих в листовом узле. Здесь вместо использования меры примесей мы выбираем атрибут, который минимизирует сумму квадратов ошибок.
Если Tn — это набор обучающих экземпляров, связанных с узлом n, а yi — значение экземпляра i, то —
Преимущества использования деревьев решений –
1. Недорогой в строительстве
2. Чрезвычайно быстро классифицирует неизвестные записи
3. Легко интерпретировать, в отличие от современных нейронных сетей.
4. Для категориальных атрибутов преобразование не требуется.
5. Они общего назначения, могут решить многие проблемы
6. Полезно для выбора атрибута
Недостатки деревьев решений –
1. Чувствителен к изменениям данных обучения
2. Больше не считается современным в области машинного обучения.
