Дерево решений — это древовидный алгоритм, используемый для определения курса действий. Каждая ветвь дерева представляет собой возможное решение, событие или реакцию.
Теория информации:
Теория информации — это основы деревьев решений. Чтобы понять алгоритм дерева решений, нам нужно понять теорию информации.
Основная идея теории информации заключается в том, что «информационная ценность» набора данных зависит от того, в какой степени содержание сообщения является неожиданным или запутанным. Если событие очень вероятно, то неудивительно (и, как правило, неинтересно), когда оно происходит так, как ожидалось; следовательно, передача такого сообщения несет очень мало новой информации. Однако, если событие маловероятно, гораздо информативнее узнать, что событие произошло или произойдет.
Например, только на обоих побережьях Индии есть не менее 3000 разновидностей рыб, если мы создаем классификатор «акул», чтобы определить, является ли это акулой или нет. Для нас важно ввести изображения неакул в наборы данных как отрицательные выборки, чтобы классификатор мог различать акулу и неакулью рыбу. Энтропия высока только тогда, когда смесь положительных выборок (акула) и отрицательных выборок (не акула) одинакова, что означает, что набор данных имеет интересные особенности для изучения.
Если все изображения в нашем наборе данных положительные (акула), то мы не узнаем ничего нового — независимо от того, сколько изображений акул он содержит.
Замечено, что энтропия максимальна, когда вероятности равны.
Древо решений:
Основная идея Дерева решений состоит в том, чтобы разбить классификацию на набор вариантов для каждой записи (т. е. столбца) в нашем векторе признаков. Мы начинаем с корня дерева, а затем продвигаемся вниз к листьям, где производится фактическая классификация.
Например, предположим, что мы в походе по озерному краю, и дождь то идет, то прекращается, нам нужно решить, оставаться ли дома или отправиться в поход.
Как видно из РИС. 1 выше, мы создали диаграмму дерева решений, в которой блоки решений (прямоугольники) указывают на выбор, который мы должны сделать. Затем у нас есть ветви, которые ведут нас к другим блокам принятия решений или завершающему блоку (овалы). Конечный блок – это конечный узел дерева, указывающий на принятие окончательного решения.
Строительство дерева:
Алгоритмы дерева решений используют теорию информации в той или иной форме для получения оптимальных, наиболее информативных разбиений (то есть «решений») для построения серии правил «если/то» в виде дерева.
Первым шагом в построении дерева решений является формирование корневого узла дерева. то есть, какая функция разделена, чтобы сформировать остальную часть дерева.
Чтобы мы могли найти корневой узел, мы вычисляем прирост информации от каждого столбца признаков. Столбец признаков с максимальным приростом информации выбирается в качестве корневого узла, и из выбранного корневого узла выполняется разделение для построения дерева решений.
Формула для расчета энтропии:
Где , p = количество уникальных значений в столбце функций / общее количество функций в столбце функций
Например, давайте найдем энтропию приведенного ниже набора данных о животных.
Набор данных выглядит довольно беспорядочно, и в этом случае энтропия высока.
Общее количество животных= 8
Количество жирафов в наборе данных = 3
Количество тигров в наборе данных = 2
Количество обезьян в наборе данных = 1
Количество слонов в наборе данных = 2
Следовательно, энтропия рассчитывается следующим образом:
import math entropy = -(3/8)*math.log2(3/8)+(2/8)*math.log2(2/8)+(1/8)*math.log2(1/8)+(2/8)*math.log2(2/8) print(entropy)
Энтропия здесь составляет приблизительно 1,9. Это считается высокой энтропией, высоким уровнем беспорядка (что означает низкий уровень чистоты).
Пример: Дерево решений
Давайте возьмем приведенный ниже пример набора данных и построим на нем дерево решений. Здесь функция «воспроизведение» является независимой переменной, а остальные столбцы функций являются зависимыми переменными.
Мы сделаем 5 шагов для построения дерева решений:
- Шаг 1: вычислить энтропию набора данных (целевая переменная) — E(s)
- Шаг 2. Вычислите прирост информации для каждой зависимой переменной — Прирост (прогноз), Прирост (температура), Прирост (влажность), Прирост (ветер), используя следующие уравнения:
I(прогноз) = ((общее количество солнечных дней/все объекты в прогнозе) * E(прогноз=солнечно)) * ((общее количество пасмурных дней/общее количество объектов в прогнозе) E(outlook=пасмурно) )) * ((общее количество дождливых/всего объектов в прогнозе) E(прогноз=дождливый))
Выигрыш(прогноз) = E(s) – I(прогноз)
I(temp) = ((общее количество горячих/всего объектов в temp) * E(temp=горячих)) * ((общее количество слабых/всего в temp) E(temp=mild )) * ((общее количество крутых/всего функций в temp) E(temp=cool))
Усиление(темп) = E(с) — I(темп)
I(влажность) = ((общее количество высоких/общее количество признаков влажности) * E(влажность=высокое)) * ((общее количество нормальных/общее количество признаков влажности) E(влажность=нормальное ))
Усиление(влажность) = E(s) — I(влажность)
I(ветрено) = ((общее количество верных/всего признаков в ветреном) * E(ветренное=истинно)) * ((общее количество ложных/всего признаков в ветреном) E(ветрено=ложно ))
Усиление(ветрено)= E(s) — I(ветрено)
- Шаг 3. Найдите объект с максимальным коэффициентом усиления и выберите его в качестве корневого узла. илиУсиление (ветер)
- Шаг 4. Найдите следующий узел, чтобы разделить дерево дальше.
- Шаг 5.Дерево решений будет повторять этот процесс по мере того, как оно становится все глубже и глубже, пока либо оно не достигнет заданной глубины, либо никакое дополнительное разделение не может привести к более высокому получению информации сверх определенного порога, что также может обычно указывается как гиперпараметр!
Шаг 1. Вычисление энтропии набора данных (целевая переменная) — E(s)
Энтропия набора данных E(s) составляет 0,94.
Шаг 2. Рассчитайте прирост информации о каждой функции
Функция 1: внешний вид
Прирост информации от функции «прогноз» составляет 0,24.
Функция 2: временная
Функция 3. Влажность
Особенность 4: ветрено
Шаг 3. Найдите объект с максимальным коэффициентом усиления и выберите его в качестве корневого узла.
Таким образом, максимальный прирост определяется как 0,24, поэтому Outlook является нашим КОРНЕВЫМ узлом.
Шаг 4. При наличии более двух объектов первое разделение выполняется на наиболее информативном объекте, а затем при каждом разделении необходимо пересчитывать прирост информации для каждого дополнительного объекта, поскольку он не будет таким же, как получение информации от каждой функции отдельно. Энтропия и прирост информации должны быть рассчитаны после того, как одно или несколько расщеплений уже были сделаны, что изменило бы результаты.
Шаг 5. Дерево решений будет повторять этот процесс по мере того, как оно становится все глубже и глубже, пока либо оно не достигнет заданной глубины, либо никакое дополнительное разделение не может привести к более высокому получению информации сверх определенного порога, что также может обычно указывается как гиперпараметр!
Надеюсь, вы получили отличное представление об алгоритме дерева решений, поняв вычисления, лежащие в основе получения информации и энтропии.
Дайте мне знать ваши отзывы в комментариях
Ссылка:
https://web.stanford.edu/~montanar/RESEARCH/BOOK/partA.pdf
https://web.mit.edu/6.933/www/Fall2001/Shannon2.pdf
https://towardsdatascience.com/entropy-how-decision-trees-make-decisions-2946b9c18c8
