В этом посте мы подробно разбираемся в алгоритме ID3 деревьев решений с примерным набором данных.
Содержание:
·Что такое алгоритм ID3?
· Псевдокод алгоритма ID3
· Работа с числовым примером
· Недостатки алгоритма ID3
· Преимущества алгоритма ID3
Что такое алгоритм ID3?
Давайте начнем с полной формы ID3, которая расшифровывается как «Итеративный дихотомайзер 3», где дихотомайзер означает «разделить на части». ID3 использует жадный нисходящий подход для построения дерева решений. Проще говоря, подход сверху вниз означает, что мы начинаем строить дерево сверху, а жадный подход означает, что на каждой итерации мы выбираем лучшую функцию в данный момент. момент для создания узла.
Алгоритм ID3 начинается с исходного набора S в качестве корневого узла. На каждой итерации алгоритм выполняет итерацию по каждому неиспользуемому атрибуту набора S:
· Вычисляет энтропию каждого атрибута A набора данных S.
· Разбить множество S на подмножества, используя признак, для которого результирующая энтропия после разбиения минимальна/эквивалентно, прирост информации максимален.
· Создайте узел дерева решений, содержащий этот атрибут.
· Выполните то же самое рекурсивно на подмножествах, используя оставшиеся атрибуты.
Для более глубокого понимания работы алгоритма следуйте приведенному псевдокоду:
ID3 (примеры, Target_Attribute, атрибуты)
Создать корневой узел для дерева
Если все примеры положительные, вернуть корень дерева с одним узлом с меткой = +.
Если все примеры отрицательные, вернуть корень дерева с одним узлом , с меткой = -.
Если количество предсказывающих атрибутов пусто, то Вернуть корень дерева с одним узлом,
с меткой = наиболее распространенное значение целевого атрибута в примерах.
В противном случае Начать
A ← Атрибут, который лучше всего классифицирует примеры.
Атрибут дерева решений для корня = A.
Для каждого возможного значения vi из A
Добавить новую ветвь дерева ниже корня , соответствующий тесту A = vi.
Пусть Examples(vi) будет подмножеством примеров, которые имеют значение vi для A
Если Examples(vi) пусто
Тогда под этой новой ветвью добавьте конечный узел с меткой = наиболее распространенное целевое значение в примерах
Еще ниже этой новой ветви добавьте поддерево ID3 (Примеры (vi), Target_Attribute, Attributes — {A})
Конец
Вернуть корень
Давайте разберемся с его работой на числовом примере:
В следующей таблице указаны факторы для игры в теннис на улице в предыдущие 14 дней:
Формулы, используемые в алгоритме ID3:
Примечание: используется журнал на основе 2.
Энтропия(S) = ∑ — p (I) . журнал (я)
Прирост(S, A) = Энтропия(S) — ∑ [p(S|A) . Энтропия (S|A)]
p обозначает вероятность, A обозначает атрибут, S обозначает энтропию, а I обозначает информацию.
Энтропия
Сначала нужно вычислить энтропию. Колонка решений состоит из 14 экземпляров и включает две метки: да и нет. Есть 9 решений с пометкой «да» и 5 решений с пометкой «нет».
Энтропия (Решение) = — p(Да) . лог(Да) — р(Нет) . журнал(нет)
Энтропия (Решение) = — (9/14) . лог(9/14) — (5/14) . журнал (5/14) = 0,940
Фактор ветра при принятии решения
Выигрыш(Решение, Ветер) = Энтропия(Решение) — ∑ [ p(Решение|Ветер) . Энтропия(Решение|Ветер) ]
Атрибут ветра имеет две метки: слабый и сильный.
Выигрыш(Решение, Ветер) = Энтропия(Решение) — [ p(Решение|Ветер=Слабо) . Энтропия(Решение|Ветер=Слабый) ] — [ p(Решение|Ветер=Сильный) . Энтропия(Решение|Ветер=Сильный) ]
Теперь нам нужно рассчитать (Решение|Ветер=Слабый) и (Решение|Ветер=Сильный) соответственно.
Фактор слабого ветра на решение:
Есть 8 случаев для слабого ветра. В котором Решения по 2 пунктам - нет, а по 6 пунктам - да, как показано ниже.
Энтропия(Решение|Ветер=Слабый) = -p(Нет) . logp(Нет) -p(Да) . журнал (Да)
Энтропия(Решение|Ветер=Слабый) = -(2/8) . лог(2/8) -(6/8) . журнал (6/8) = 0,811
Фактор сильного ветра:
Здесь есть 6 моментов для сильного ветра. Решение делится на две равные части.
Энтропия(Решение|Ветер=Сильный) = — p(Нет) . logp(Нет) — p(Да) . log2p (Да)
Энтропия(Решение|Ветер=Сильный) = — (3/6) . лог(3/6) — (3/6) . журнал2(3/6) = 1
Теперь мы можем вернуться к уравнению Gain(Decision, Wind).
Выигрыш(Решение, Ветер) = Энтропия(Решение) — [ p(Решение|Ветер=Слабый) . Энтропия(Решение|Ветер=Слабый) ] — [ p(Решение|Ветер=Сильный) . Энтропия(Решение|Ветер=Сильный) ] = 0,940 — [ (8/14) . 0,811] — [ (6/14). 1] = 0,048
Расчеты ветрового столба закончены. Теперь нам нужно применить те же вычисления для других столбцов, чтобы найти наиболее доминирующий фактор при принятии решения.
Точно так же мы вычисляем и другие атрибуты, и их результаты выглядят так:
Прибыль (Решение, Перспективы) = 0,246
Усиление (Решение, Температура) = 0,029
Прирост (Решение, Влажность) = 0,151
Из вышеприведенных результатов видно, что фактор перспективы при принятии решения дает наивысший балл, поэтому сделайте его корневым.
Решение всегда будет да, если прогноз был пасмурным. Здесь есть 5 экземпляров для солнечной погоды. Решение будет, вероятно, 3/5 процента нет, 2/5 процента да.
1- Прирост(Прогноз=Солнечно|Температура) = 0,570
2- Прирост(Прогноз=Солнечно|Влажность) = 0,970
3- Прирост(Прогноз=Солнечно|Ветер) = 0,019
Теперь решающим фактором является влажность, потому что она дает наивысший балл, если погода солнечная. Теперь решение всегда будет «нет», если влажность будет высокой.
С другой стороны, решение всегда будет положительным, если влажность будет нормальной. Это означает, что нам нужно проверить влажность и решить, была ли погода солнечной.
Подобно этому далее,
Прирост (прогноз = дождь | температура) = 0,01997309402197489
Прирост(Прогноз=Дождь | Влажность) = 0,01997309402197489
Прирост(Прогноз=Дождь | Ветер) = 0,9709505944546686
Здесь ветер дает наивысший балл, если прогнозом был дождь. Вот почему нам нужно проверить атрибут ветра на 2-м уровне, если прогноз был дождь. Итак, выясняется, что решение всегда будет положительным, если ветер слабый, а прогноз дождь. Решение всегда будет отрицательным, если ветер сильный, а прогноз дождь.
Итоговое дерево выглядит так:
Приведенный выше числовой пример объясняет, как это работает с его математикой.
Теперь некоторые темные стороны ID3:
· ID3 не гарантирует оптимального решения.
· ID3 может перенасыщать обучающий набор данных.
· ID3 сложнее использовать с непрерывным набором данных.
Преимущества алгоритма ID3:
· На основе обучающих данных создаются понятные правила прогнозирования.
· Строит короткое дерево за относительно небольшое время.
· Требуется только проверить достаточное количество атрибутов, пока все данные не будут классифицированы.
· Поиск листовых узлов позволяет обрезать тестовые данные, сокращая количество тестов.
В этом посте мы узнали, как работает алгоритм ID3, каковы его числовые показатели и работа, его недостатки, преимущества. В следующих постах мы следуем нашему пути обучения и изучаем другие алгоритмы машинного обучения.
Спасибо Удачного обучения!!!
Использованная литература:
https://sefiks.com/2017/11/20/a-step-by-step-id3-decision-tree-example/
