# 4. Домашнє завдання (написання програми)

> **Джерело завдання.** Формулювання взято **з методичних матеріалів курсу**.
> Готового коду тут **немає** — це індивідуальне завдання; техніку обчислень
> показано на інших даних у [2method.md](2method.md) та на вибірці «Спортивний
> канал» у [3classroom.md](3classroom.md).

## Постановка

**Реалізувати алгоритм побудови дерева рішень за допомогою алгоритму ID3. На вхід
додатку передається CSV файл з навчальною вибіркою. Побудоване дерево виводиться на
екран.**

Мову програмування студент обирає самостійно. Готові реалізації дерев рішень
(наприклад, `sklearn.tree.DecisionTreeClassifier`) дозволено використовувати
**лише для перевірки** власного коду.

## Вхід і вихід

- **Вхід:** шлях до файлу **CSV** із навчальною вибіркою. Рядки — об'єкти, стовпці —
  атрибути; один зі стовпців (за домовленістю останній або заданий параметром) —
  **цільовий клас**. Атрибути **категоріальні** (рядкові значення). Перший рядок
  файлу — заголовок з іменами атрибутів.
- **Вихід:** **побудоване дерево**, виведене на екран у читабельному вигляді —
  напр., відступами за рівнями (де кожен внутрішній вузол показує атрибут, ребра —
  його значення, а листи — клас):

```text
Дохід?
  = Високий -> Так
  = Низький -> Ні
  = Середній:
      Стать?
        = Ч -> Так
        = Ж:
            Студент?
              = Так -> Так
              = Ні  -> Ні
```

Точний формат виводу — на розсуд студента, аби структуру дерева було однозначно
видно.

## Рівні складності

Оцінка відповідає найвищому **повністю й правильно** виконаному рівню.

### Базовий рівень — 60–74 балів

1. Прочитати навчальну вибірку з файлу CSV (заголовок + категоріальні атрибути +
   стовпець класу).
2. Реалізувати обчислення **ентропії** множини та **середньозваженої ентропії**
   розбиття за атрибутом (формули — **самостійно**, не готовою функцією).
3. Реалізувати рекурсивну побудову дерева алгоритмом **ID3**: на кожному вузлі
   обирати атрибут із найбільшим приростом інформації; зупинятися на **чистому**
   вузлі (один клас) або коли атрибути вичерпані.
4. **Вивести** побудоване дерево на екран.

### Середній рівень — 75–89 балів

Додатково до базового:

5. Коректно опрацьовувати **довільну** кількість атрибутів і **більше двох**
   значень класу (не лише бінарний випадок).
6. Реалізувати **класифікацію нового об'єкта**: за введеними значеннями атрибутів
   програма проходить деревом від кореня до листа й повертає передбачений клас.
7. Опрацьовувати випадок **порожньої гілки** та вузла з вичерпаними атрибутами —
   приписувати листу **найпоширеніший клас** відповідної підмножини.

### Високий рівень — 90–100 балів

Додатково до середнього (виконати **щонайменше один** із пунктів 8–9, бажано
обидва):

8. Явно вивести для кожного вузла **приріст інформації** обраного атрибута та
   реалізувати додатковий **критерій зупинки** (напр., мінімальна кількість
   об'єктів у вузлі або поріг приросту), щоб уникнути перенавчання.
9. Реалізувати **альтернативний критерій** розбиття — **коефіцієнт приросту**
   (C4.5) або **індекс Джині** з бінарними розбиттями (CART) — і порівняти
   отримані дерева з деревом ID3.
10. **Обов'язково** перевірити програму на вибірці зі слайдів/лекції **«Спортивний
    канал»** ([3classroom.md](3classroom.md)): дерево має мати корінь **Дохід** і
    бути чистим (гілка «Середній» розгалужується далі за «Стать», потім «Студент?»).

## Що здавати

- Вихідний код програми (з коротким `README`: як запустити, який формат входу).
- Приклад запуску на **тестовому** файлі. Обов'язково перевірте програму на вибірці
  «Спортивний канал» ([3classroom.md](3classroom.md)) — очікуване дерево з коренем
  **Дохід**.
- Оформлення звіту — за [5report.md](5report.md); перелік запитань до захисту — у
  [6questions.md](6questions.md).