Теперь соединим всё вместе! Алгоритм ID3 (Iterative Dichotomiser 3) — это рекурсивный алгоритм построения дерева решений, который мы изучали по частям:
- ✅ Энтропия — узнали, как измерять "беспорядок"
- ✅ Информационная выгода — поняли, как выбирать лучший вопрос
- ✅ Теперь — собираем всё в единый алгоритм!
Это пошаговый алгоритм построения дерева решений. Придумал его Росс Куинлан в 1986 году.
Алгоритм ID3 (очень просто):
1. Возьми все данные → это корень дерева
2. Проверь условия остановки:
- Все примеры одного класса? → Готово, создай лист!
- Нет признаков? → Создай лист с самым частым классом
3. Если не остановились:
- Посчитай IG для КАЖДОГО признака
- Выбери признак с МАКСИМАЛЬНОЙ IG
- Раздели данные по этому признаку
4. Повтори шаги 2-3 для каждой ветки (рекурсия!)
Живой пример: Строим дерево для "Идти на прогулку?"
Данные за 8 дней:
| День |
Погода |
Температура |
Пошли? |
| 1 |
Солнце |
Тепло |
✅ Да |
| 2 |
Солнце |
Жарко |
❌ Нет |
| 3 |
Дождь |
Тепло |
❌ Нет |
| 4 |
Дождь |
Холодно |
❌ Нет |
| 5 |
Солнце |
Тепло |
✅ Да |
| 6 |
Облачно |
Тепло |
✅ Да |
| 7 |
Облачно |
Холодно |
✅ Да |
| 8 |
Дождь |
Тепло |
❌ Нет |
Итого: 4 раза "Да", 4 раза "Нет"
Шаг 1: Считаем начальную энтропию
- H = -(4/8 × log₂(4/8) + 4/8 × log₂(4/8)) = 1.0
- Максимальный хаос!
Шаг 2: Какой признак выбрать? Считаем IG для "Погода"
- Солнце: 2 дня (1 Да, 1 Нет) → H = 1.0
- Дождь: 3 дня (0 Да, 3 Нет) → H = 0 ✨ Чисто!
- Облачно: 2 дня (2 Да, 0 Нет) → H = 0 ✨ Чисто!
- IG = 1.0 - (3/8 × 1.0 + 3/8 × 0 + 2/8 × 0) = 0.62
Шаг 3: Считаем IG для "Температура"
- Тепло: 4 дня (3 Да, 1 Нет) → H ≈ 0.81
- Жарко: 1 день (0 Да, 1 Нет) → H = 0
- Холодно: 2 дня (1 Да, 1 Нет) → H = 1.0
- IG = 1.0 - (4/8 × 0.81 + 1/8 × 0 + 2/8 × 1.0) ≈ 0.40
Вывод: Погода дает больше информации (0.62 > 0.40)!
Шаг 4: Строим дерево
[Погода?]
/ | \
Солнце Дождь Облачно
| | |
[Темп.?] ❌ Нет ✅ Да
/ \
Тепло Жарко
| |
✅ Да ❌ Нет