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

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

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

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

Мову програмування студент обирає самостійно. Значення ознак вважати числовими;
кожен рядок файлу — окремий об'єкт, стовпці — його ознаки (координати в просторі
ознак). Кластеризацію виконують методом $k$-середніх (евклідова відстань).

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

- **Вхід:** шлях до файлу **CSV** з даними — рядки-об'єкти, числові
  стовпці-ознаки (можлива наявність заголовка та стовпця-ідентифікатора, які до
  кластеризації не входять). Число кластерів $k$ задають параметром.
- **Вихід:** файл із **результатом категоризації** — для кожного об'єкта його
  **мітка кластера** (номер $1..k$). Додатково рекомендовано вивести координати
  фінальних **центроїдів** та досягнуту **SSE**.

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

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

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

1. Прочитати дані з файлу CSV (числові ознаки об'єктів).
2. Реалізувати метод $k$-середніх із **фіксованим** $k$ (задається параметром):
   - ініціалізація $k$ центроїдів (напр., перші $k$ об'єктів або випадкові);
   - **віднесення** кожного об'єкта до найближчого центроїда за **евклідовою**
     відстанню;
   - **перерахунок** центроїдів як середніх кластерів;
   - повторення до **збіжності** (центроїди не зміщуються) або досягнення
     максимуму ітерацій.
3. Записати у **вихідний файл мітки кластерів** для всіх об'єктів.
4. Формули відстані та перерахунку центрів реалізувати **самостійно** (не
   викликати готовий `KMeans` як основне обчислення).

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

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

5. **Нормалізувати** ознаки перед кластеризацією ($z$-нормування або min–max) і
   пояснити, навіщо це потрібно за несумірних масштабів ознак.
6. Обчислювати **SSE** отриманого розбиття й виводити її.
7. Виконувати **кілька запусків** алгоритму з **різною** (випадковою)
   ініціалізацією центроїдів і обирати **найкраще** розбиття — з **найменшою**
   SSE (боротьба з чутливістю до ініціалізації).

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

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

8. Реалізувати **автоматичний вибір $k$** одним зі способів:
   - **метод ліктя** (*elbow*) — побудувати залежність SSE$(k)$ для діапазону
     $k$ і визначити точку «зламу»; або
   - **силуетний коефіцієнт** — обчислити середній силует для кожного $k$ і
     обрати $k$ з найбільшим значенням.
9. Передбачити **перевірку коректності** вводу (порожній файл, нечислові значення,
   пропуски, $k$ більше за число об'єктів) з інформативним повідомленням.
10. Опрацьовувати **порожні кластери** (коли до центроїда не віднесено жодної
    точки) — переініціалізацією центра чи іншою розумною стратегією.

## Що здавати

- Вихідний код програми (з коротким `README`: як запустити, формат входу й виходу).
- Приклад запуску на **тестовому** файлі. Обов'язково перевірте програму на даних
  [Задачі 2](3classroom.md) ($6$ точок, $k = 2$) — очікувані кластери
  $\{A, B, C\}$ та $\{D, E, F\}$ і $\mathrm{SSE} = \tfrac{8}{3} \approx 2.667$.
- Оформлення звіту — за [5report.md](5report.md); перелік запитань до захисту — у
  [6questions.md](6questions.md).