Есть много замечательных блогов и руководств по дереву решений, но я не нашел ни одного, где был бы показан полный пример построения дерева. Итак, я хотел бы объяснить это, используя простую математику, на очень известном примере (набор данных игрушек, обычно используемый для объяснения дерева решений).
Что такое дерево решений?
Проще говоря, это один из алгоритмов контролируемого обучения, который используется как для задач классификации, так и для задач регрессии, но имеет нелинейную структуру, в отличие от SVM, линейной регрессии и т. Д. Деревья решений хорошо известны своей интерпретируемостью.
«Деревья решений» - разбивка наших данных путем принятия решения на основе серии вопросов.
«Корневой узел» также называется родительским узлом. Это узел, с которого начинается разбиение дерева.
«Узел решения» также называется Дочерним узлом, в котором принимаются решения (или) правила.
«Конечный узел» также называется конечным узлом, который является конечным узлом и не может разделяться дальше.
В этом блоге я бы использовал приведенные выше термины как синонимы, и «функция, атрибут, переменная-предиктор» означает одно и то же. Эти термины также будут использоваться как синонимы.
Как строятся деревья решений?
В алгоритме дерева решений мы начинаем с корня дерева (корневого узла) и разделяем данные по признакам / предикторам, что приводит к максимальному приросту информации.
Не понял !! не волнуйся. А теперь давайте упростим.
Этапы построения дерева решений.
- Сначала выберите корневой узел. (Как мы это делаем?) - Рассчитайте информационный прирост для каждой функции в наборе данных / данных. Объект с «наибольшей предоставленной информацией» выбирается как «корневой узел».
- Разделите набор данных на основе корневого узла. (Как разделить?). Это снова зависит от «корневого узла» (функции). Если он состоит из трех разных категорий, вы разделите свой набор данных на три или если функции числовые, вы разделите их на основе операторов сравнения (›,‹, =).
- После разделения наборов данных на более мелкие подмножества, вычислите информационный прирост для оставшихся объектов, кроме объекта корневого узла. Объект с наибольшим приростом информации становится «узлом решения» или «дочерним узлом». . »
- Повторяйте 'step-2' и 'step-3', пока не получите листовые (или) чистые узлы. , это означает, что все обучающие примеры на каждом узле принадлежат к одному классу.
Непонятно !! Все в порядке. Вы поймете это ясно, когда мы построим дерево решений на примере.
Из приведенных выше 4 шагов мы используем термин «получение информации», но
Что такое получение информации?
Проще говоря, получение информации говорит нам, насколько важен данный атрибут векторов признаков.
Чтобы разделить наиболее информативные признаки, нам нужна целевая функция. Наша задача - максимизировать получение информации на каждом сплите.
Чтобы упростить уравнение на рисунке, мы можем сказать, что «Прирост информации - это просто разница между примесью родительского узла и суммой примесей дочернего узла».
Есть три меры нечистоты. Это «Энтропия», «Примесь Джини» и «ошибка классификации». В этом блоге мы ограничимся обсуждением «Энтропии».
Что такое энтропия?
Проще говоря, энтропия - это не что иное, как мера беспорядка.
Энтропия - это мера беспорядка или неопределенности, а цель моделей машинного обучения - уменьшить неопределенность.
Где «Пи» - это просто вероятность наличия элемента / класса «i» в наших данных. Предположим, у нас есть только два класса: положительный класс и отрицательный класс. Следовательно, «i» здесь может быть либо +, либо (-).
Энтропия максимальна, если все точки данных равномерно распределены по обоим классам, тогда значение энтропия = 1.
Энтропия минимальна, если все точки данных принадлежат тому же классу, тогда значение энтропия = 0.
Например: если у нас есть набор данных из 100 точек данных / наблюдений, принадлежащих к двум классам, положительным (+ ve) или отрицательным (-ve), то энтропия максимальна (энтропия = 1) , когда 50 равны (+ ve) и 50 равны (-ve).
энтропия минимальна (энтропия = 0), когда все точки данных принадлежат либо положительному (+ ve) классу , либо отрицательный класс (-ve).
Прирост информации - это уменьшение энтропии. Прирост информации рассчитывается для разделения путем вычитания взвешенных энтропий каждой ветви из исходной энтропии.
Таким образом, мы также можем рассчитать прирост информации, используя приведенную выше формулу.
Пример построения дерева решений
я использую
Это самый известный набор данных, который используется для объяснения деревьев решений.
В этом наборе данных есть 4 объекта / атрибута и целевая переменная и 14 наблюдений / строк.
Шаг - 1: выбор корневого узла
Как мы уже говорили ранее, чтобы выбрать корневой узел, нам нужно вычислить получение информации для всех наблюдений в наборе данных, и функция с наибольшим приростом информации будет корневой узел.
Мы можем использовать приведенное выше уравнение для расчета прироста информации. Чтобы вычислить его, нам нужно
а) сначала вычислить энтропию целевой переменной, т. е.
- это полный расчет энтропии целевой переменной исходного набора данных. Итак, энтропия целевой переменной равна 0,94.
б) вычислить энтропию целевой переменной вместе с каждой переменной / функцией-предиктором
Нам нужно вычислить энтропию целевой переменной вместе с каждой функцией, а затем вычислить информационный выигрыш для каждого признака и решить, какой признак имеет наибольший информационный прирост.
Функция: Outlook (энтропия и получение информации)
- Информационный прирост (Рис-10) рассчитывается с помощью
«Энтропия между целевой переменной« играть в гольф »и функцией« Перспективы »(рис. 9) и энтропия целевой переменной« играть в гольф »(рис. 8).
Функция: температура (энтропия и получение информации)
- Информационный прирост (Рис. 12) рассчитывается с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Темп »(Рис. 11) и Энтропии целевой переменной« Играть в гольф »(Рис. 8).
Особенность: ветреный (энтропия и получение информации)
- Информационный прирост (рис. 14) рассчитывается с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Ветреный »(рис. 13) и энтропии целевой переменной« играть в гольф »(рис. 8).
Характеристика: влажность (энтропия и получение информации)
- Информационный прирост (Рис. 16) рассчитывается с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Влажность »(Рис. 15) и энтропии целевой переменной« Играть в гольф »(Рис. 8).
Мы подсчитали информационный прирост всех объектов, объект с наибольшим информационным наполнением станет корневым узлом.
Из (Рис. 17) мы можем сказать, что «Outlook» - это функция, которая имеет наибольшее количество информации. Итак, мы можем выбрать «Outlook» в качестве корневого узла.
Шаг - 2: Разделите набор данных на основе корневого узла.
Как было сказано ранее, разделение набора данных основано на характеристиках.
На предыдущем шаге мы выбрали «Outlook» в качестве корневого узла. В функции «Outlook» есть три типа категорий («Солнечно», «Пасмурно», «Дождь»). Итак, мы разделяем набор данных на три поднабора данных.
Аналогичным образом мы разделяем наборы данных для других задач, также в зависимости от корневого узла в начале, а когда дело доходит до середины, разделение набора данных зависит от дочернего узла.
Шаг - 3: Рассчитайте информационный прирост для оставшихся функций.
Прежде чем идти дальше. На (Рис. 18) мы видим, что «OVERCAST» категория в «OUTLOOK» функции принадлежит в тот же класс в целевой переменной.
Как было сказано ранее, энтропия равна 0, когда все точки данных принадлежат одному классу. Здесь все 4 точки данных 'облачности' категории в 'Outlook' функции принадлежат к одному классу «ДА». Итак, энтропия составляет минимум, и мы не можем далее разделить, поскольку он становится «узлом листа» или «Конечный узел».
Теперь рассчитайте получение информации для оставшихся функций
Давайте выберем первый набор данных - из категории «Солнечно» функции «Outlook».
Шаг - 4: Повторение предыдущих шагов снова (вычисление IG).
IG относится к получению информации
а) Рассчитайте энтропию целевой переменной в указанном выше дополнительном наборе данных.
- это полный расчет энтропии целевой переменной поднабора данных (Рис-21). Итак, энтропия целевой переменной равна 0,972.
б) вычислить энтропию целевой переменной вместе с каждой переменной / функцией-предиктором
Нам нужно вычислить энтропию целевой переменной вместе с каждой функцией, а затем вычислить информационный выигрыш для каждой особенности и решить, какая функция имеет наибольший информационный выигрыш в этом поднаборе данных.
Функция: Temp (энтропия и получение информации) - При солнечном свете
- Информационный прирост (Рис. 24) вычисляется с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Темп »(Рис. 23) и Энтропии целевой переменной« Играть в гольф »(Рис. 22).
Характеристика: влажность (увеличение энтропии и информации) - При солнечном свете
- Информационный прирост (рис. 26) рассчитывается с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Влажность »(рис. 25) и энтропии целевой переменной« играть в гольф »(рис. 22).
Особенность: ветрено (энтропия и получение информации) - при солнечном свете
- Информационный прирост (Рис. 28) рассчитывается с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Влажность »(Рис. 27) и Энтропии целевой переменной« Играть в гольф »(Рис. 22).
Мы рассчитали информационный приток всех характеристик поднабора данных. Объект с наибольшим информационным объемом станет дочерним узлом в «Outlook» в категории Солнечный.
Из (Рис. 29) очевидно, что функция «Ветреный» имеет наибольшее информационное усиление и, следовательно, становится дочерним узлом в категории «Солнечный» в функции «Outlook».
Здесь, из (рис-30) и (рис-21), мы можем понять, что Энтропия в подкатегориях функции «Ветреный» составляет 0, что означает, что мы не может дальше разделиться. Таким образом, мы можем рассматривать категории 'False' и 'True' в разделе «Windy» узел как листовые узлы.
Давайте выберем другой набор данных - из категории «Дождь» функции «Outlook».
Названия столбцов слева направо: «Outlook», «Temp», «Humidity», «Windy», «PlayGolf».
а) Рассчитайте энтропию целевой переменной в указанном выше дополнительном наборе данных.
- это полный расчет энтропии целевой переменной поднабора данных (Рис-31). Итак, энтропия целевой переменной равна 0,972.
б) вычислить энтропию целевой переменной вместе с каждой переменной / функцией-предиктором
Нам нужно вычислить энтропию целевой переменной вместе с каждой функцией, а затем вычислить информационный выигрыш для каждой особенности и решить, какая функция имеет наибольший информационный выигрыш в этом поднаборе данных.
Функция: Temp (увеличение энтропии и информации) - At Rainy
- Информационный прирост (Рис. 34) вычисляется с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Темп »(Рис. 33) и Энтропии целевой переменной« Играть в гольф »(Рис. 32).
Функция: влажность (увеличение энтропии и информации) - При дождливой погоде
- Прирост информации (Рис. 36) рассчитывается с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Влажность »(Рис. 35) и энтропии целевой переменной« Играть в гольф »(Рис. 32).
Особенность: ветрено (энтропия и получение информации) - дождливо
- Информационный прирост (Рис. 38) рассчитывается с помощью «Энтропии между целевой переменной« играть в гольф »и характеристикой« Влажность »(Рис. 37) и Энтропии целевой переменной« Играть в гольф »(Рис. 32).
Мы рассчитали информационный приток для всех функций поднабора данных. Объект с наибольшим информационным объемом станет дочерним узлом в «Outlook» в категории Rainy.
Из (Рис. 39) очевидно, что функция «Влажность» имеет самый высокий информационный поток и, следовательно, становится дочерним узлом в категории «Дождь» в функции «Outlook».
Здесь, из (рис-31) и (рис-40), мы можем понять, что Энтропия в подкатегориях функции «Влажность» равна 0, что означает, что мы не может дальше разделиться. Таким образом, мы можем рассматривать категории 'False' и 'True' в разделе «Влажность» узел как листовые узлы.
Итак, (Рис-40) наше последнее дерево решений.
Возможное сомнение: в нашем построенном «Дереве решений» мы не можем увидеть функцию «Темп». Что с ней случилось?
Ответ: Это довольно просто. Функция «Темп» недостаточно для принятия решения, играть нам в гольф или нет. Вы также можете считать это наименее важной особенностью.
Мы также можем думать о деревьях решений как об «обучении на основе правил». Мы можем преобразовать эти деревья решений в простые правила «если-иначе».
Вывод
Как видно, построение дерева решений прямолинейно и понятно, но его можно легко изменить. Мы должны быть осторожны с глубиной дерева, при работе с большими наборами данных, которые состоят из огромного количества измерений, тогда его можно легко переобучить, если мы тренируемся, пока не дойдем до всех чистых узлов. Есть также приемы, позволяющие избежать переобучения с помощью обрезки.
