Цель этой статьи - подробно объяснить алгоритм ID3 (один из многих алгоритмов, используемых для построения деревьев решений). Мы объясним алгоритм, используя поддельный образец набора данных Covid-19.
Что такое деревья решений?
Проще говоря, дерево решений - это структура, которая содержит узлы (прямоугольные блоки) и ребра (стрелки) и построена на основе набора данных (таблица столбцов, представляющих функции / атрибуты, а строки соответствуют записям). Каждый узел используется либо для принятия решения (, известного как узел решения) , либо представления результата (известный как листовой узел).
Пример дерева решений
На рисунке выше изображено дерево решений, которое используется для определения того, является ли человек пригодным или неподходящим.
Узлами принятия решения здесь являются такие вопросы, как "" Моложе 30 лет?, "Ест ли человек мусор?" и т. д. и листья являются одним из двух возможных результатов, а именно. Подходит и Не подходит.
Глядя на Дерево решений, мы можем сказать, что принимаем следующие решения:
если человек моложе 30 лет и не ест нездоровую пищу, значит он Подходит, если человек моложе 30 лет и ест нездоровую пищу, то он Подходящий и так далее.
Начальный узел называется корневым узлом (окрашен синим), последние узлы называются листовыми узлами (окрашены зеленым ), а остальные узлы называются промежуточными или внутренними узлами.
Корневые и промежуточные узлы представляют решения, а конечные узлы представляют результаты.
Кратко об ID3
ID3 расшифровывается как Iterative Dichotomiser 3 и назван так потому, что алгоритм итеративно (многократно) дихотомирует (делит) признаки на две или более группы на каждом шаге.
Изобретенная Россом Куинланом, ID3 использует жадный нисходящий подход для построения дерева решений. Проще говоря, нисходящий подход означает, что мы начинаем строить дерево сверху, а жадный подход означает, что на каждой итерации мы выбираем лучшую функцию на данный момент. момент для создания узла.
Чаще всего ID3 используется только для задач классификации с номинальными характеристиками.
Описание набора данных
В этой статье мы будем использовать образец данных об инфекции COVID-19. Предварительный просмотр всего набора данных показан ниже.
+----+-------+-------+------------------+----------+ | ID | Fever | Cough | Breathing issues | Infected | +----+-------+-------+------------------+----------+ | 1 | NO | NO | NO | NO | +----+-------+-------+------------------+----------+ | 2 | YES | YES | YES | YES | +----+-------+-------+------------------+----------+ | 3 | YES | YES | NO | NO | +----+-------+-------+------------------+----------+ | 4 | YES | NO | YES | YES | +----+-------+-------+------------------+----------+ | 5 | YES | YES | YES | YES | +----+-------+-------+------------------+----------+ | 6 | NO | YES | NO | NO | +----+-------+-------+------------------+----------+ | 7 | YES | NO | YES | YES | +----+-------+-------+------------------+----------+ | 8 | YES | NO | YES | YES | +----+-------+-------+------------------+----------+ | 9 | NO | YES | YES | YES | +----+-------+-------+------------------+----------+ | 10 | YES | YES | NO | YES | +----+-------+-------+------------------+----------+ | 11 | NO | YES | NO | NO | +----+-------+-------+------------------+----------+ | 12 | NO | YES | YES | YES | +----+-------+-------+------------------+----------+ | 13 | NO | YES | YES | NO | +----+-------+-------+------------------+----------+ | 14 | YES | YES | NO | NO | +----+-------+-------+------------------+----------+
Столбцы говорят сами за себя. Y и N означают Да и Нет соответственно. Значения или классы в столбце «Заражено» Y и N представляют зараженный и незараженный соответственно.
Столбцы, используемые для создания узлов решений, а именно. «Проблемы с дыханием», «Кашель» и «Лихорадка» называются столбцами характеристик или просто характеристиками, а столбец, используемый для листовых узлов, то есть «Зараженный», называется целевым столбцом.
Метрики в ID3
Как упоминалось ранее, алгоритм ID3 выбирает лучшую функцию на каждом этапе при построении дерева решений.
Прежде чем вы спросите, ответ на вопрос: «Как ID3 выбирает лучшую функцию?» заключается в том, что ID3 использует усиление информации или просто усиление для поиска Лучшая особенность.
Information Gain вычисляет уменьшение энтропии и измеряет, насколько хорошо данная функция разделяет или классифицирует целевые классы. Функция с наибольшим объемом информации выбирается как наилучшая.
Проще говоря, Энтропия - это мера беспорядка , а Энтропия набора данных - это мера беспорядка в целевой функции набора данных.
В случае двоичной классификации (когда целевой столбец имеет только два типа классов) энтропия равна 0, если все значения в целевом столбце однородны (аналогично ) и будет 1, если целевой столбец имеет равные числовые значения для обоих классов.
Мы обозначаем наш набор данных как S, энтропия рассчитывается как:
Entropy(S) = - ∑ pᵢ * log₂(pᵢ) ; i = 1 to n
где
n - общее количество классов в целевом столбце (в нашем случае n = 2, т.е. ДА и НЕТ)
pᵢ - это вероятность класса i или отношение «количества строк с классом i в целевом столбце» к «общему количеству строк» в наборе данных.
Информационная выгода для столбца характеристик A рассчитывается по следующей формуле:
IG(S, A) = Entropy(S) - ∑((|Sᵥ| / |S|) * Entropy(Sᵥ))
где Sᵥ - это набор строк в S, для которых столбец функций A имеет значение v, | Sᵥ | - это количество строк в Sᵥ, а также | S | - количество строк в S.
ID3 шаги
- Рассчитайте информационное усиление каждой функции.
- Учитывая, что все строки не принадлежат к одному классу, разделите набор данных S на подмножества, используя функцию, для которой получение информации является максимальным.
- Создайте узел дерева решений, используя функцию с максимальным приростом информации.
- Если все строки принадлежат одному классу, сделайте текущий узел листовым узлом с классом в качестве его метки.
- Повторите эти действия для оставшихся функций, пока у нас не закончатся все функции, или пока в дереве решений не будут все листовые узлы.
Реализация в нашем наборе данных
Как указывалось в предыдущем разделе, первым делом необходимо найти лучшую функцию, то есть ту, которая имеет максимальное получение информации (IG). Сейчас мы рассчитаем IG для каждой из функций, но для этого нам сначала нужно вычислить энтропию S
Из 14 строк в нашем наборе данных S есть 8 строк с целевым значением ДА и 6. строки с целевым значением NO. Энтропия S рассчитывается как:
Entropy(S) = — (8/14) * log₂(8/14) — (6/14) * log₂(6/14) = 0.99
Примечание. Если все значения в нашем целевом столбце одинаковы, энтропия будет равна нулю (это означает, что случайность отсутствует или равна нулю).
Теперь мы рассчитываем информационный выигрыш для каждой функции:
Расчет IG для лихорадки:
В этой функции (лихорадка) есть 8 строк со значениями ДА и 6 строк со значением NO.
Как показано ниже, в строках 8 со значением YES для Fever есть 6 строк с целевым значением ДА и 2 строк с целевым значением НЕТ.
+-------+-------+------------------+----------+ | Fever | Cough | Breathing issues | Infected | +-------+-------+------------------+----------+ | YES | YES | YES | YES | +-------+-------+------------------+----------+ | YES | YES | NO | NO | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | YES | YES | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | YES | YES | NO | YES | +-------+-------+------------------+----------+ | YES | YES | NO | NO | +-------+-------+------------------+----------+
Как показано ниже, в 6 строках с NO есть 2 строки с целевым значением YES и 4 строк с целевым значением NO.
+-------+-------+------------------+----------+ | Fever | Cough | Breathing issues | Infected | +-------+-------+------------------+----------+ | NO | NO | NO | NO | +-------+-------+------------------+----------+ | NO | YES | NO | NO | +-------+-------+------------------+----------+ | NO | YES | YES | YES | +-------+-------+------------------+----------+ | NO | YES | NO | NO | +-------+-------+------------------+----------+ | NO | YES | YES | YES | +-------+-------+------------------+----------+ | NO | YES | YES | NO | +-------+-------+------------------+----------+
В блоке ниже показан расчет получения информации для лихорадки.
# total rows |S| = 14 For v = YES, |Sᵥ| = 8 Entropy(Sᵥ) = - (6/8) * log₂(6/8) - (2/8) * log₂(2/8) = 0.81 For v = NO, |Sᵥ| = 6 Entropy(Sᵥ) = - (2/6) * log₂(2/6) - (4/6) * log₂(4/6) = 0.91 # Expanding the summation in the IG formula: IG(S, Fever) = Entropy(S) - (|Sʏᴇꜱ| / |S|) * Entropy(Sʏᴇꜱ) - (|Sɴᴏ| / |S|) * Entropy(Sɴᴏ) ∴ IG(S, Fever) = 0.99 - (8/14) * 0.81 - (6/14) * 0.91 = 0.13
Затем мы вычисляем IG для функций Кашель и Проблемы с дыханием.
Вы можете использовать это бесплатное онлайн инструмент для расчета прироста информации.
IG(S, Cough) = 0.04 IG(S, BreathingIssues) = 0.40
Поскольку функция Проблемы с дыханием имеет наибольшее получение информации, она используется для создания корневого узла.
Следовательно, после этого начального шага наше дерево выглядит следующим образом:
Затем из двух оставшихся неиспользуемых функций, а именно Лихорадка и Кашель, мы решаем, какая из них лучше всего подходит для левой ветви Проблемы с дыханием. .
Поскольку левая ветвь Проблемы с дыханием означает ДА, мы будем работать с подмножеством исходных данных, то есть с набором строк, имеющих ДА в качестве значения в столбце Проблемы с дыханием. Эти 8 строк показаны ниже:
+-------+-------+------------------+----------+ | Fever | Cough | Breathing issues | Infected | +-------+-------+------------------+----------+ | YES | YES | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | YES | YES | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | NO | YES | YES | YES | +-------+-------+------------------+----------+ | NO | YES | YES | YES | +-------+-------+------------------+----------+ | NO | YES | YES | NO | +-------+-------+------------------+----------+
Затем мы вычисляем IG для признаков Лихорадка и Кашель, используя подмножество S ʙʏ (S и Проблемы с дыханием Y es), который показан выше:
Примечание. Для расчета IG энтропия будет рассчитываться из подмножества S ʙʏ, а не из исходного набора данных S.
IG(Sʙʏ, Fever) = 0.20 IG(Sʙʏ, Cough) = 0.09
IG у лихорадки выше, чем у кашля, поэтому мы выбираем лихорадку в качестве левой ветви «Проблемы с дыханием»:
Теперь наше дерево выглядит следующим образом:
Затем мы находим функцию с максимальным IG для правой ветви Проблемы с дыханием. Но поскольку осталась только одна неиспользуемая функция, у нас нет другого выбора, кроме как сделать ее правой ветвью корневого узла.
Итак, наше дерево теперь выглядит так:
Больше нет неиспользуемых функций, поэтому мы останавливаемся на этом и переходим к последнему этапу создания листовых узлов.
Для левого листового узла Fever мы видим подмножество строк из исходного набора данных, у которого есть Проблемы с дыханием и Лихорадка оба значения - ДА.
+-------+-------+------------------+----------+ | Fever | Cough | Breathing issues | Infected | +-------+-------+------------------+----------+ | YES | YES | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | YES | YES | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+ | YES | NO | YES | YES | +-------+-------+------------------+----------+
Поскольку все значения в целевом столбце - ДА, мы помечаем левый листовой узел как ДА, но для большей логики мы помечаем его как Зараженный.
Точно так же для правого узла Fever мы видим подмножество строк из исходного набора данных, которые имеют значение Проблемы с дыханием как YES и Fever как НЕТ.
+-------+-------+------------------+----------+ | Fever | Cough | Breathing issues | Infected | +-------+-------+------------------+----------+ | NO | YES | YES | YES | +-------+-------+------------------+----------+ | NO | YES | YES | NO | +-------+-------+------------------+----------+ | NO | YES | YES | NO | +-------+-------+------------------+----------+
Здесь не все, кроме большинства, значений - НЕТ, следовательно, НЕТ или Не заражен становится нашим правым листовым узлом.
Теперь наше дерево выглядит так:
Мы повторяем тот же процесс для узла Кашель, однако здесь и левый, и правый листы оказываются одинаковыми, т.е. НЕТ или Не заражен как показано ниже:
Странно выглядит, не правда ли?
Я знаю! Правый узел проблем с дыханием ничем не хуже листового узла с классом «Не заражен». Это один из недостатков ID3, он не выполняет обрезку.
Сокращение - это механизм, который уменьшает размер и сложность дерева решений за счет удаления ненужных узлов. Подробнее об обрезке можно узнать здесь.
Еще один недостаток ID3 - это переоснащение или высокая дисперсия, то есть он настолько хорошо изучает набор данных, который он использовал, что не может обобщить новые данные.
Резюме
Мы подробно рассмотрели процесс алгоритма ID3 и увидели, насколько легко было создать дерево решений с использованием этого алгоритма, используя только две метрики, а именно. Энтропия и получение информации.
Надеюсь, вам понравилось, ребята !!!
Спасибо, что прочитали
Использованная литература:
Https://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm
