Деревья решений - это широко используемые модели для задач классификации и регрессии. По сути, они изучают иерархию вопросов «если-еще», ведущих к решению. Дерево решений - это блок-схема, подобная древовидной структуре, где каждый внутренний узел обозначает тест для атрибута, каждая ветвь представляет результат теста, а каждый листовой узел (конечный узел) содержит метку класса.
Представьте, что вы хотите различать следующих четырех животных: медведей, ястребов, пингвинов и дельфинов.
Ваша цель - найти правильный ответ, задавая как можно меньше вопросов, если это возможно.
Вы можете начать с вопроса, есть ли у животного перья - вопрос, который сужает список возможных животных до двух животных.
Если ответ положительный, вы можете задать другой вопрос, который поможет вам отличить
ястребов от пингвинов. Например, вы можете спросить, умеет ли животное летать. Если у животного нет перьев, возможно, вы выберете дельфинов и медведей, и вам нужно будет задать вопрос, чтобы различать этих двух животных, например, спросите, есть ли у животного плавники. в виде дерева решений, как показано на рисунке ниже.
Выбор атрибута
Допустим, у нас есть набор данных, как показано ниже. Таблица 1 касается клиентов, покупающих компьютер.
В дереве решений будут отображаться эти данные, как показано ниже.
Вопрос: Как алгоритм дерева решений решил, что корневым узлом должен быть возраст, и разделил два узла Студент и Кредитный рейтинг и скоро.
Для дерева решений есть несколько измерений выбора атрибутов.
1) Сбор информации
2) Коэффициент усиления
3) Индекс Джини
Получение информации для выбора атрибута
Этот показатель основан на новаторской работе Клода Шеннона по теории информации, в которой изучалась ценность или информационное содержание сообщения. Давайте посчитаем прирост информации для всех характеристик (возраст, доход, учащийся, кредит_рейтинг). Чтобы рассчитать объем информации, нам необходимо выполнить следующие действия.
- Энтропия, необходимая для классификации кортежа в D
Всего у нас есть 14 строк в целевом столбце («да» = 9, «нет» = 5). Таким образом, получение информации для всего набора данных будет:
2. Необходимая информация (после использования A для разделения D на v разделов) для классификации D:
3. Информация, полученная путем ветвления по атрибуту A
Приступим к вычислению информационного прироста возраста. В Таблице 2 столбца "Возраст":
для случая (≤30) мы имеем «да» (p = 2), «no» (n = 2) и энтропия I (p, n) составляет 0,971,
для случая (31… 40) мы имеем «да» (p = 4), «no» (n = 0) и энтропия I (p, n) равна 0,
для случая (›40) мы имеем« да »(p = 3),« no »(n = 2) и энтропия I (p, n) составляет 0,971
Рассчитать информацию для возраста
Следовательно
Аналогично для (доход, учащийся, кредит_рейтинг):
Получение информации о возрасте больше, чем о других функциях, поэтому мы знаем, почему алгоритм дерева решений выбрал возраст в первую очередь
Коэффициент усиления для выбора атрибута
Мера прироста информации используется для выбора атрибута теста в каждом узле дерева решений. Мера прироста информации предпочитает выбирать атрибуты, имеющие большое количество значений. Базовый алгоритм индукции дерева решений ID3 был расширен в C4.5. C4.5, преемник ID3, использует расширение получения информации, известное как коэффициент усиления, которое пытается преодолеть это смещение.
Пусть множество S состоит из s выборок данных с m различными классами. Ожидаемая информация, необходимая для классификации данной выборки, дается следующим образом:
Информация о кодировании, которая будет получена при ветвлении на A, равна
C4.5 использует коэффициент усиления, который применяет нормализацию к приросту информации с использованием значения, определенного как
Вышеупомянутое значение представляет информацию, сгенерированную путем разделения набора обучающих данных S на v разделов, соответствующих v результатам теста по атрибуту A.
Коэффициент усиления определяется как
В нашем случае:
Атрибут с максимальным коэффициентом усиления выбран как атрибут разделения.
Индекс Джини для выбора атрибутов
Индекс Джини учитывает двоичное разбиение для каждого атрибута. Индекс Джини измеряет чистоту D, раздела данных или набора обучающих кортежей как,
При рассмотрении двоичного разбиения мы вычисляем взвешенную сумму примесей каждого результирующего разбиения. Например, если двоичное разбиение на A разбивает D на D1 и D2, индекс Джини для D с учетом этого разбиения равен
Для каждого атрибута рассматривается каждое возможное двоичное разбиение. Для атрибута с дискретным значением подмножество, которое дает минимальный индекс gini для этого атрибута, является его атрибутом разделения.
