🎯 Кластеризація K-середніх — алгоритм Ллойда

Ініціалізуйте k центроїдів (випадково або методом k-means++). Припишіть кожну точку даних до найближчого центроїда за евклідовою відстанню. Переобчисліть кожен центроїд як середню позицію всіх приписаних точок. Повторюйте приписування та оновлення, доки жодна точка не змінює кластер між ітераціями (збіжність). Запустіть алгоритм кілька разів з різними ініціалізаціями та залишіть результат з найменшим значенням WCSS.

Метод «ліктя» будує графік WCSS залежно від значень k; оптимальне k знаходиться у точці згину («лікті»), де додавання нових кластерів дає дедалі менший приріст якості. Коефіцієнт силуету вимірює, наскільки добре кожна точка відповідає своєму кластеру порівняно з сусідніми кластерами (діапазон від -1 до +1; чим вище, тим краще). Знання предметної області часто є найкращим орієнтиром — наприклад, роздрібний продавець, що сегментує клієнтів, може заздалегідь знати, що хоче отримати 5 типів клієнтських персон.

K-середні припускають сферичні кластери подібного розміру та густини, і погано працюють з витягнутими, неправильної форми або вкладеними кластерами. Алгоритм чутливий до викидів (які можуть відтягувати центроїди від основної маси даних) та до вибору k. Він використовує евклідову відстань, тому непридатний для категоріальних даних без попередньої обробки. Алгоритми на кшталт DBSCAN, гаусових сумішей або ієрархічної кластеризації усувають деякі з цих обмежень.

K-means++ покращує вибір початкових центроїдів, щоб уникнути невдалих стартових конфігурацій. Перший центроїд обирається випадково. Кожен наступний центроїд обирається з імовірністю, пропорційною квадрату відстані до найближчого вже обраного центроїда, що забезпечує добре розділені та розподілені по даних початкові центроїди. Це зазвичай дає кращу кінцеву якість кластерів і швидшу збіжність, ніж суто випадкова ініціалізація.

У стисненні зображень k-середні розглядають колір RGB кожного пікселя як тривимірну точку даних і розбивають усі пікселі на k колірних груп. Потім кожен піксель замінюється кольором центроїда свого кластера, зводячи зображення до палітри з k кольорів. При k=16 24-бітне кольорове зображення апроксимується лише 4 бітами на піксель плюс таблиця пошуку з 16 кольорів — значне стиснення за помірної втрати якості.