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

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

Постановка #

Реалізувати ієрархічний алгоритм категорізації знизу-догори. На вхід додатку передається CSV файл з даними. Результати категорізації записуються у файл. Порівняти якість категоризації з алгоритмом $k$-means.

Мову програмування студент обирає самостійно. Об’єкти у файлі описано числовими ознаками; відстань між об’єктами — евклідова. «Знизу догори» означає агломеративний алгоритм: кожен об’єкт спершу окремий кластер, далі послідовне злиття найближчих пар (див. 2method.md).

Вхід і вихід #

• Вхід: шлях до файлу CSV з даними — рядок = об’єкт, стовпці = числові ознаки (можливі заголовок і нечисловий стовпець-ідентифікатор, який до відстаней не включають). Число кластерів $k$ (або висоту розрізу) задають параметром чи запитом.
• Вихід: файл із результатом категоризації — щонайменше приналежність кожного об’єкта до кластера (мітка/номер кластера). Формат — на розсуд студента (окремий стовпець у CSV, окремий файл тощо).

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

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

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

1. Прочитати об’єкти з файлу CSV і побудувати матрицю попарних відстаней (евклідових).
2. Реалізувати агломеративний алгоритм з одиночним зв’язком (найближчого сусіда): кожен об’єкт — кластер; злиття найближчої пари; повтор до одного кластера.
3. Для заданого числа кластерів $k$ вивести кластери (приналежність об’єктів) у вихідний файл.
4. Алгоритм злиттів реалізувати самостійно (готову linkage/AgglomerativeClustering дозволено лише для перевірки).

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

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

5. Додати вибір метрики зв’язку: одиночний (single), повний (complete), середній (average). Метрику задають параметром.
6. Вивести дендрограму або порядок злиттів — послідовність пар, що зливаються, із висотами (відстанями злиття). Достатньо текстового подання (таблиця злиттів або схематичне дерево).
7. Коректно опрацьовувати файл із заголовком і стовпцем-ідентифікатором; передбачити нормалізацію ознак (за потреби), пояснивши її вплив на відстані.

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

Додатково до середнього:

8. Реалізувати $k$-means (або скористатися ним) на тих самих даних із тим самим $k$.
9. Обчислити якість обох розбиттів — ієрархічного та $k$-means — за силуетом або індексом Данна й порівняти їх (яке розбиття якісніше та чому).
10. Дослідити вплив метрики зв’язку на результат: показати набір даних, на якому одиночний і повний зв’язок дають різні розбиття (як у Задачах 1–2), і прокоментувати різницю.

Що здавати #

• Вихідний код програми (з коротким README: як запустити, формат входу й виходу).
• Приклад запуску на тестовому файлі. Обов’язково перевірте програму на даних Задач 1–2: для точок $\{0,1,7,12,15\}$ одиночний зв’язок при $k=2$ має дати $\{0,1\}\mid\{7,12,15\}$, а повний — $\{0,1,7\}\mid\{12,15\}$.
• Оформлення звіту — за 5report.md; перелік запитань до захисту — у 6questions.md.

Laboratory/Laboratory10/4task.md · 5.6 KB · updated 2026-08-04 23:25