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

Джерело завдання. Формулювання взято з методичних матеріалів курсу. Готового коду тут немає — це індивідуальне завдання; техніку обчислень показано на інших даних у 2method.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 ($6$ точок, $k = 2$) — очікувані кластери $\{A, B, C\}$ та $\{D, E, F\}$ і $\mathrm{SSE} = \tfrac{8}{3} \approx 2.667$.
• Оформлення звіту — за 5report.md; перелік запитань до захисту — у 6questions.md.

Laboratory/Laboratory9/4task.md · 5.8 KB · updated 2026-08-04 23:32