Введение в дерево решений с примером

Опубликовано: 2 Марта, 2022
  • Алгоритм дерева решений относится к категории контролируемого обучения. Их можно использовать для решения задач как регрессии, так и классификации.
  • Дерево решений использует представление дерева для решения проблемы, в которой каждый листовой узел соответствует метке класса, а атрибуты представлены на внутреннем узле дерева.
  • Мы можем представить любую логическую функцию на дискретных атрибутах с помощью дерева решений.

Ниже приведены некоторые предположения, которые мы сделали при использовании дерева решений:

  • Вначале мы рассматриваем весь обучающий набор как корень.
  • Желательно, чтобы значения характеристик были категориальными. Если значения непрерывны, то они дискретизируются перед построением модели.
  • На основе значений атрибутов записи распределяются рекурсивно.
  • Мы используем статистические методы для упорядочивания атрибутов как корневого или внутреннего узла.

Как видно из приведенного выше изображения, дерево решений работает с формой суммы продукта, которая также известна как дизъюнктивная нормальная форма . На изображении выше мы прогнозируем использование компьютера в повседневной жизни людей.

В «Дереве решений» основной проблемой является идентификация атрибута для корневого узла на каждом уровне. Этот процесс известен как выбор атрибута. У нас есть две популярные меры выбора атрибутов:

  1. Получение информации
  2. Индекс Джини

1. Получение информации
Когда мы используем узел в дереве решений для разделения обучающих экземпляров на более мелкие подмножества, энтропия изменяется. Прирост информации является мерой этого изменения энтропии.
Определение : Предположим, что S - это набор экземпляров, A - атрибут, S v - подмножество S с A = v, а Values (A) - это множество всех возможных значений A, тогда

Энтропия
Энтропия - это мера неопределенности случайной величины, она характеризует нечистоту произвольного набора примеров. Чем выше энтропия, тем больше информативность.
Определение : Предположим, что S - это набор экземпляров, A - атрибут, S v - подмножество S с A = v, а Values (A) - это множество всех возможных значений A, тогда

Пример:

Для множества X = {a, a, a, b, b, b, b, b}
Всего интансов: 8
Экземпляры b: 5
Экземпляры a: 3


              = - [0,375 * (-1,415) + 0,625 * (-0,678)] 
              = - (- 0,53-0,424) 
              = 0,954

Построение дерева решений с использованием сбора информации
Основы:

  • Начните со всех обучающих экземпляров, связанных с корневым узлом
  • Используйте информационное усиление, чтобы выбрать, каким атрибутом пометить каждый узел.
  • Примечание. Путь от корня к листу не должен содержать один и тот же дискретный атрибут дважды.
  • Рекурсивно создайте каждое поддерево на подмножестве обучающих экземпляров, которые будут классифицироваться по этому пути в дереве.

    Пограничные случаи:

  • Если все положительные или все отрицательные обучающие экземпляры остаются, пометьте этот узел «да» или «нет» соответственно.
  • Если атрибутов не осталось, пометьте большинством голосов обучающих экземпляров, оставшихся на этом узле.
  • Если экземпляров не осталось, отметьте большинством голосов родительские экземпляры обучения.

Пример:
Теперь давайте нарисуем дерево решений для следующих данных, используя получение информации.

Учебный набор: 3 функции и 2 класса

Икс Y Z C
1 1 1 я
1 1 0 я
0 0 1 II
1 0 0 II

Здесь у нас есть 3 функции и 2 выходных класса.
Построить дерево решений с использованием получения информации. Мы возьмем каждую функцию и вычислим информацию для каждой функции.

Разделить на функцию X

Разделить по признаку Y

Разделить на элемент Z

Из приведенных выше изображений мы видим, что получение информации является максимальным, когда мы разделяем объект Y. Итак, для корневого узла лучше всего подходит функция Y. Теперь мы можем видеть, что при разделении набора данных по объекту Y дочерний элемент содержит чистое подмножество целевой переменной. Таким образом, нам не нужно дополнительно разбивать набор данных.

Окончательное дерево для указанного выше набора данных будет выглядеть так:

2. Индекс Джини

  • Индекс Джини - это показатель для измерения того, как часто случайно выбранный элемент может быть неправильно идентифицирован.
  • Это означает, что предпочтение следует отдавать атрибуту с более низким индексом Джини.
  • Sklearn поддерживает критерий «Джини» для индекса Джини и по умолчанию принимает значение «Джини».
  • Формула для расчета индекса Джини приведена ниже.

    Пример:
    Давайте рассмотрим набор данных на изображении ниже и нарисуем дерево решений с использованием индекса gini.

    Показатель А B C D E
    1 4.8 3,4 1.9 0,2 положительный
    2 5 3 1.6 1.2 положительный
    3 5 3,4 1.6 0,2 положительный
    4 5.2 3.5 1.5 0,2 положительный
    5 5.2 3,4 1.4 0,2 положительный
    6 4,7 3.2 1.6 0,2 положительный
    7 4.8 3.1 1.6 0,2 положительный
    8 5,4 3,4 1.5 0,4 положительный
    9 7 3.2 4,7 1.4 отрицательный
    10 6.4 3.2 4,7 1.5 отрицательный
    11 6.9 3.1 4.9 1.5 отрицательный
    12 5.5 2.3 4 1.3 отрицательный
    13 6.5 2,8 4.6 1.5 отрицательный
    14 5,7 2,8 4.5 1.3 отрицательный
    15 6.3 3.3 4,7 1.6 отрицательный
    16 4.9 2,4 3.3 1 отрицательный

    В приведенном выше наборе данных есть 5 атрибутов, из которых атрибут E является прогнозирующим признаком, который содержит 2 класса (положительный и отрицательный). У нас одинаковая пропорция для обоих классов.
    В индексе Джини мы должны выбрать несколько случайных значений для классификации каждого атрибута. Эти значения для этого набора данных:

        ABCD
      > = 5> = 3,0> = 4,2> = 1,4
       <5 <3,0 <4,2 <1,4
    

    Расчет индекса Джини для переменной A:
    Значение> = 5: 12
    Атрибут A> = 5 & class = положительный:
    Атрибут A> = 5 & class = negative:
    Джини (5, 7) = 1 -
    Значение <5: 4
    Атрибут A <5 & class = положительный:
    Атрибут A <5 & class = negative:
    Джини (3, 1) = 1 -
    Добавляя вес и суммируя каждый из индексов Джини:

    Расчет индекса Джини для переменной B:
    Значение> = 3: 12
    Атрибут B> = 3 & class = положительный:
    Атрибут B> = 5 & class = negative:
    Джини (5, 7) = 1 -
    Значение <3: 4
    Атрибут A <3 & class = положительный:
    Атрибут A <3 & class = negative:
    Джини (3, 1) = 1 -
    Добавляя вес и суммируя каждый из индексов Джини:

    Используя тот же подход, мы можем рассчитать индекс Джини для атрибутов C и D.

                 Позитивный негативный
    Для A |> = 5,0 5 7
         | <5 3 1
    Индекс Гинина А = 0,45825    
    
                 Позитивный негативный
    Для B |> = 3,0 8 4
         | <3,0 0 4
    Индекс Джини B = 0,3345
    
                 Позитивный негативный
    Для C |> = 4,2 0 6
         | <4,2 8 2
    Индекс Джини C = 0,2    
    
                 Позитивный негативный
    Для D |> = 1,4 0 5
         | <1,4 8 3
    Индекс Джини D = 0,273
     

    Наиболее заметными типами алгоритмов дерева решений являются:

    1. Итеративный дихотомизатор 3 (ID3): этот алгоритм использует информационное усиление, чтобы решить, какой атрибут следует использовать для классификации текущего подмножества данных. Для каждого уровня дерева информационный прирост рассчитывается для остальных данных рекурсивно.

    2. C4.5: Этот алгоритм является преемником алгоритма ID3. Этот алгоритм использует либо информационное усиление, либо коэффициент усиления для определения атрибута классификации. Это прямое усовершенствование алгоритма ID3, поскольку он может обрабатывать как непрерывные, так и отсутствующие значения атрибутов.

    3. Дерево классификации и регрессии (CART): это алгоритм динамического обучения, который может создавать дерево регрессии, а также дерево классификации в зависимости от зависимой переменной.

    Ссылка: dataaspirant

    Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

    Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.