Что такое дерево решений?
Деревья решений — это широко используемые алгоритмы машинного обучения с учителем. Они популярны из-за простоты интерпретации и широкого спектра применений. Они работают как для задач регрессии, так и для задач классификации.
Дерево решений состоит из серии последовательных решений или узлов решений по некоторым функциям набора данных. Получающаяся в результате структура, похожая на поток, перемещается с помощью операторов условного управления или правил «если-то», которые разбивают каждый узел принятия решений на два или более подузлов. Листовые узлы, также известные как конечные узлы, представляют выходные данные прогноза для модели.
Обучить дерево решений на основе данных означает выяснить порядок, в котором решения должны быть собраны от корня к листьям. Затем новые данные могут передаваться сверху вниз до достижения конечного узла, представляющего прогноз для этой точки данных.
Основные элементы дерева решений
Прежде чем мы углубимся в то, как работает дерево решений, давайте определим некоторые ключевые термины дерева решений.
- Корневой узел: основа дерева решений.
- Узел принятия решения: когда подузел далее разбивается на дополнительные подузлы.
- Конечный узел: когда подузел не разделяется на дополнительные подузлы; представляет возможные результаты.
Алгоритм обучения дерева классификации
В дереве решений для прогнозирования класса данного набора данных алгоритм начинается с корневого узла дерева. Этот алгоритм сравнивает значения корневого признака с записью (реальным набором данных) и, основываясь на сравнении, следует по ветви и переходит к следующему узлу.
Для следующего узла алгоритм снова сравнивает значение признака с другими подузлами и движется дальше. Он продолжает процесс, пока не достигнет конечного узла дерева. Полный процесс можно лучше понять, используя следующий алгоритм:
Шаг 1: начните дерево с корневого узла, говорит С, который содержит полный набор данных.
Шаг 2. Найдите лучший признак в наборе данных, измерив примесь.
Шаг 3. Разделите S на подмножества, которые содержат возможные значения для лучших функций.
Шаг 4. Создайте узел дерева решений, который содержит лучший признак.
Шаг 5. Рекурсивно создайте новые деревья решений, используя подмножества набора данных, созданного на шаге 3. Продолжайте этот процесс до тех пор, пока не будет достигнут этап, на котором вы не сможете дополнительно классифицировать узлы и назвать последний узел конечным узлом.
Как мы можем измерить примеси в наборе данных?
Существует два популярных метода измерения примесей:
- Энтропия
- Примесь Джини
Энтропия
Энтропия — это количество информации, необходимое для точного описания данных. Таким образом, если данные однородны, то есть все элементы похожи, то энтропия равна 0 (то есть чистая), в противном случае, если элементы разделены поровну, энтропия приближается к 1 (то есть нечистая).
Математически это определяется как
Примесь Джини
Примесь Джини также является мерой примеси или чистоты, используемой при создании дерева решений в алгоритме CART (Дерево классификации и регрессии). Точнее, примесь Джини набора данных — это число от 0 до 0,5. Поскольку примесь Джини не содержит какой-либо логарифмической функции, для ее вычисления требуется меньше вычислительного времени по сравнению с энтропией. Примесь Джини можно рассчитать по следующей формуле:
Взвешенная сумма примесей Джини на основе соответствующей доли категории в объекте. Формула:
Пример дерева классификации
У нас есть набор данных о погоде с категориальными и числовыми значениями, и мы хотим определить, играть в баскетбол или нет в зависимости от погодных условий. мы можем видеть из прогноза данных, температура, влажность и ветер являются особенностями.
Первое, что мы делаем, это решаем, что функция должна быть вопросом, который мы задаем на самом верху дерева (корневой узел).
Чтобы определить признаки для разделения данных, мы должны вычислить примесь Джини для каждого признака.
Перспективы
Функция Outlook имеет 3 значения: солнечно, пасмурно и дождь. Давайте классифицировать его.
Теперь мы рассчитаем взвешенную сумму примеси Джини для функций прогноза.
Температура
Теперь нам нужно рассчитать примесь Джини для функции температуры, в отличие от других функций, это числовая функция. так что разница небольшая, мы должны найти правильное значение для разделения данных. Обычно первое, что мы делаем, это сортируем строки по температуре от самой низкой до самой высокой.
мы разделим данные на две группы на основе порогов (T). мы попробуем все возможные пороги (T) и найдем лучший для разделения данных на основе самой низкой примеси Джини. в этом случае мы используем все уникальные значения температуры, кроме 30 для порогов. например, первое пороговое значение равно 11, поэтому мы используем 11 в качестве порогового значения для разделения данных.
затем вычисляем взвешенную сумму примеси Джини температуры.
Для каждого T измерьте его примесь и выберите T с наименьшим содержанием примеси.
из таблицы видно, что порог = 26 дает самую низкую примесь Джини. поэтому мы можем определить температуру условия › 26 дает наилучшее разделение.
Влажность
Функция влажности имеет 2 значения, высокое и нормальное. Давайте классифицировать его.
Теперь мы рассчитаем взвешенную сумму примеси Джини для характеристик влажности.
Ветер
ветер также является функцией бинарного класса, он может принимать два значения, слабое и сильное.
Теперь мы рассчитаем взвешенную сумму примеси Джини для характеристик ветра.
Итак, примесь Джини для всех признаков:
Итак, мы можем сделать вывод, что низшей примесью Джини является температура › 26. Тогда нашим корневым узлом является условие температуры › 26.
Теперь, потому что каждый случай, когда температура › 26 принимает решение «нет», становится Листом, потому что нет смысла делить людей на более мелкие группы.
Теперь давайте сосредоточимся на данных с температурой ‹= 26. И найдем примесь Джини для прогноза, влажности и ветра.
Примесь Джини для просмотра подданных (где температура ‹= 26)
Теперь мы рассчитаем взвешенную сумму примеси Джини для функций прогноза.
Примесь Джини для влажности в подданных (где температура ‹= 26)
Теперь мы рассчитаем взвешенную сумму примеси Джини для характеристик влажности.
Примесь Джини для ветра в дополнительных данных (где температура ‹= 26)
Теперь мы рассчитаем взвешенную сумму примеси Джини для характеристик ветра.
По словам Джини Примесь:
Как мы видим для подданных, где температура ‹ = 26, функция прогноза имеет самую низкую примесь Джини. Так что можно сделать вывод, что следующим узлом будет кухня. Outlook = пасмурно становится листом, потому что он имеет 0 примесей Джини. поэтому дерево будет таким:
Теперь давайте сосредоточимся на прогнозе дополнительных данных = солнечно
на столе мы можем видеть ясно, влажность может разделить данные. при высокой влажности решение «нет», а при нормальной влажности решение всегда «да». Итак, мы получили листовые узлы.
Наконец, давайте сосредоточимся на вспомогательных данных для функции прогноза количества осадков.
мы также можем ясно видеть, что функция ветра может разделить данные. при сильном ветре всегда принимается решение «нет», а при слабом — всегда «да».
Это последнее дерево
