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

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

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

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

Мову програмування студент обирає самостійно. Об'єкти у файлі описано числовими
ознаками; відстань між об'єктами — **евклідова**. «Знизу догори» означає
**агломеративний** алгоритм: кожен об'єкт спершу окремий кластер, далі
послідовне злиття найближчих пар (див. [2method.md](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](3classroom.md)), і прокоментувати різницю.

## Що здавати

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