Построение дерева принятия решений

В подпараграфе 5.4.1 мы ввели понятие энтропии и описали обучение классификатора на основе деревьев решений {decision tree). Приведем псевдокод алгоритма рекурсивного построения дерева.^[1][2]

• 3.3. Для каждого значения из столбца сформировать поднабор 1 и поднабор 2.
• 3.4. Посчитать IGain по формуле (5.12) для обоих наборов.
• 3.5. Если IGain > IGain_hest и наборы 1 и 2 не пусты, запомнить Юат_Ьы = IGain, be = значение признака и признак, bs = поднабор 1 и гтоднабор 2.
• 4. Создать подветви:
• 4.1. Если нашелся IGain_hest, сформировать ветви «Да» с поднабором 1 и «Нет» с поднабором 2. Рекурсивно вызвать алгоритм для поднабора 1 и поднабора 2.
• 4.2. Иначе запомнить в этом листе, сколько элементов каждого класса в нем содержится.

Следует отметить, что в практических задачах не следует стремиться к достижению энтропии, равной нулю, поскольку эго приводит к уже известной проблеме переобучения.

• [1] Вход: • table. rows — строки таблицы с данными. Выход:
• [2] descisionnode — корень дерева принятия решений. Алгоритм: 1. Вычислить текущую энтропию Scur таблицы с данными по формуле (5.11). 2. Инициализировать переменные. 2.1. Лучший информационный выигрыш — IGainhest 2.2. Лучший критерий — Ьс. 2.3. Лучший набор данных — bs. 3. Для каждого столбца (признака) из таблицы table с данными: 3.1. Создать список различных значений в этом столбце. 3.2. Разбить table. rows по каждому значению этого столбца.