складність 2/5
K-means
Оберіть k центрів, віднесіть кожну точку до найближчого, перемістіть кожен центр у середнє того, що він захопив, повторіть. Завжди збігається — і може збігтися до як завгодно поганого результату.
Інтуїція
У вас є точки без міток і підозра, що вони складаються в групи. K-means перетворює цю підозру на цільову функцію: обрати k центрів так, щоб сумарна квадратична відстань від кожної точки до найближчого центру була якомога меншою [2, §2.3.2].
Потім він розв’язує цю задачу погано, навмисно, бо розв’язати її як слід обчислювально неможливо. Алгоритм чергує два кроки, кожен з яких очевидно покращує оцінку, — віднести кожну точку до найближчого центру, потім пересунути кожен центр у середину його точок — і зупиняється, коли жоден із них нічого не змінює.
Це гарантує, що він зупиниться. Але нічого не гарантує щодо того, де. Увесь характер k-means випливає з цього розриву: він швидкий, простий, завжди дає відповідь — і ця відповідь може бути вдесятеро гіршою за найкращу, а на виході ніщо про це не скаже.
Формальне визначення
Як це працює
Де застосовується
Чому і коли
Практичний приклад
Типові помилки
Перевірте себе
3 запитання
Запитання до цієї сторінки входять у доступ. Їх перевіряє сервер, тож відповіді лишаються там, доки ви не дасте свою.
Джерела
- Theoretical Analysis of the k-Means Algorithm — A Survey (2016)paperhttps://ar5iv.labs.arxiv.org/html/1602.08254
- scikit-learn User Guide — Clusteringdocs · звірено 2026-09-06https://scikit-learn.org/stable/modules/clustering.html
- scikit-learn — KMeansdocs · звірено 2026-10-07https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html