АД/Laboratory/Laboratory7/4task
Raw

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

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

Постановка

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

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

Вхід і вихід

  • Вхід: шлях до файлу CSV із навчальною вибіркою. Рядки — об’єкти, стовпці — атрибути; один зі стовпців (за домовленістю останній або заданий параметром) — цільовий клас. Атрибути категоріальні (рядкові значення). Перший рядок файлу — заголовок з іменами атрибутів.
  • Вихід: побудоване дерево, виведене на екран у читабельному вигляді — напр., відступами за рівнями (де кожен внутрішній вузол показує атрибут, ребра — його значення, а листи — клас):
Дохід?
  = Високий -> Так
  = Низький -> Ні
  = Середній:
      Стать?
        = Ч -> Так
        = Ж:
            Студент?
              = Так -> Так
              = Ні  -> Ні

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

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

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

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

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

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

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

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

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

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

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

Що здавати

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

Laboratory/Laboratory7/4task.md · 6.3 KB · updated 2026-08-04 23:04