Сегодня я объясню один из наиболее часто используемых алгоритмов классификации данных — деревья решений. В этом типе классификации мы разделяем данные на основе функций, а затем еще больше с другими функциями, пока не дойдем до конца. Я собираюсь объяснить, используя ID3 (итеративный дихотомайзер 3), который использует метрики энтропии и прироста информации для расчета узла (функции) и листа (конечный результат).
Основная идея состоит в том, чтобы разделить весь набор данных в виде перевернутого дерева и достичь единого результата в конце каждой ветви.
Итак, как мы строим?
Чтобы начать с дерева, нам нужно взять один атрибут (признак), который может дать максимальное разделение данных (или наибольший прирост информации), чтобы таким образом мы могли достичь конца ветви за наименьшее количество возможных итераций.
Позвольте мне объяснить, взяв классический пример данных «Играть в теннис»:
Здесь нам нужно решить, можем ли мы играть в теннис или нет, исходя из погодных условий, данных для любого конкретного дня.
Как мы видим здесь, у нас есть 4 атрибута (Обзор, Температура, Влажность и Ветер), на основе которых мы решаем, можем ли мы играть в теннис или нет. Итак, построим дерево по алгоритму ID3!
Чтобы начать с корневого узла, нам нужно выбрать лучший атрибут/признак, который бы их классифицировал.
Как выбрать лучший классифицирующий признак?
Здесь мы воспользуемся формулой получения информации и рассчитаем для каждого атрибута. Тот, который дает наибольший выигрыш, будет выбран в качестве нашего корневого узла.
Есть в основном 3 формулы, которые будут использоваться для алгоритма ID3:
Получение информации-
Энтропия-
Усиление-
И вот шаги, которым мы следуем:
- Сначала рассчитайте информационный прирост таблицы.
- Рассчитайте энтропию для этого атрибута.
- Теперь рассчитайте усиление для соответствующего атрибута.
- Возьмите тот, который имеет самый высокий коэффициент усиления, чтобы быть узлом.
- Повторите весь процесс, чтобы найти новый набор прироста информации, энтропии и прироста после фильтрации значений атрибутов.
Аналогичным образом я рассчитал прибыль и для других атрибутов.
Усиление (прогноз) = 0,248
Усиление (температура) = 0,029
Усиление (влажность) = 0,151
Усиление (ветер) = 0,048
Как мы видим, у нас самый высокий прирост в атрибуте «Outlook», поэтому это будет корневой узел для нашего дерева решений. Таким образом, наше дерево решений выглядит так:
Теперь мы повторим те же шаги с подмножеством таблицы, в которой мы возьмем каждый тип прогноза и посмотрим, какой атрибут будет использоваться для дальнейшего продолжения дерева решений.
Итак, вот строки, которые у нас остаются, когда мы берем «Солнечный» в качестве прогноза.
Точно так же мы вычисляем энтропию и усиление для других атрибутов (влажность, ветер). Таким образом, это прибыль для атрибутов в таблице Sunny:
Усиление (температура) = 0,57
Усиление (влажность) = 0,970
Усиление (ветер) = 0,020
Как мы видим, самый высокий прирост дает атрибут Влажность, и, следовательно, он становится нашим следующим узлом для классификации. Также, если мы видим пасмурную перспективу, мы видим, что все результаты да, и мы можем напрямую закончить это здесь (это лист).
Таким образом, деревья теперь выглядят так:
Теперь вы, возможно, поняли, как мы будем работать с таблицей Outlook-Rain. После повторного выполнения вышеописанных шагов для таблицы outlook-rain ветер имеет самый высокий коэффициент усиления, и у нас, наконец, готово полное дерево решений, и вот как оно будет выглядеть:
Я даже реализовал описанный выше алгоритм с помощью python, и если вы хотите увидеть, как это было сделано, загляните в мой репозиторий GitHub здесь.
Я надеюсь, что к настоящему моменту у вас будет довольно четкое представление о том, как работают деревья решений и как они рассчитываются.
Спасибо!
Первоначально опубликовано на http://madhureshgupta.home.blog 17 мая 2020 г.
