Кластериза́ція ме́тодом k-сере́дніх () — популярний метод кластеризації, — впорядкування множини об'єктів у порівняно однорідні групи. Винайдений в 1950-х роках математиком Гуґо Штайнгаузом і майже одночасно Стюартом Ллойдом. Особливу популярність отримав після виходу роботи МакКвіна (1967).
Мета методу — розділити спостережень на кластерів, так щоб кожне спостереження належало до кластера з найближчим до нього середнім значенням. Метод базується на мінімізації суми квадратів відстаней між кожним спостереженням та центром його кластера, тобто функції , де d — метрика, — і-ий об'єкт даних, а — центр кластера, якому на j-ій ітерації приписаний елемент .
Історія
Термін «k-середні» уперше вжив Джеймс МакКвін () у 1967 році, хоча ідею методу вперше озвучив Гуґо Штайнгауз () у 1957 році. Стандартний алгоритм вперше запропонував Стюарт Лойд () у 1957 р.
Алгоритм
Опис алгоритму Маємо масив спостережень (об'єктів), кожен з яких має певні значення за рядом ознак. Відповідно до цих значень об'єкт розташовується у багатовимірному просторі. Дослідник визначає кількість кластерів , що необхідно утворити Випадковим чином обирається спостережень, які на цьому кроці вважаються центрами кластерів Кожне спостереження «приписується» до одного з кластерів — того, відстань до якого найкоротша Розраховується новий центр кожного кластера як елемент, ознаки якого розраховуються як середнє арифметичне ознак об'єктів, що входять у цей кластер Відбувається така кількість ітерацій (повторюються кроки 3-4), поки кластерні центри стануть стійкими (тобто при кожній ітерації в кожен кластер потрапляють одні й ті самі об'єкти), дисперсія всередині кластера буде мінімізована, а між кластерами — максимізована Вибір кількості кластерів робиться на основі дослідницької гіпотези. Якщо її немає, то рекомендують спочатку створити 2 кластери, далі 3, 4, 5, порівнюючи отримані результати.
Принцип дії Принцип алгоритму полягає в пошуку таких центрів кластерів та наборів елементів кожного кластера при наявності деякої функції Ф(°), що виражає якість поточного розбиття множини на k кластерів, коли сумарне квадратичне відхилення елементів кластерів від центрів цих кластерів буде найменшим:
де — число кластерів, — отримані кластери, , — центри мас векторів .
У початковий момент роботи алгоритму довільним чином обираються центри кластерів, далі для кожного елемента множини ітеративно обраховується відстань від центрів з приєднанням кожного елемента до кластера з найближчим центром. Для кожного з отриманих кластерів обчислюються нові значення центрів, намагаючись при цьому мінімізувати функцію Ф(°), після чого повторюється процедура перерозподілу елементів між кластерами.
Алгоритм методу «Кластеризація за схемою к-середніх»: вибрати k інформаційних точок як центри кластерів поки не завершиться процес зміни центрів кластерів; зіставити кожну інформаційну точку з кластером, відстань до центра якого мінімальна; переконатися, що в кожному кластері міститься хоча б одна точка. Для цього кожний порожній кластер потрібно доповнити довільною точкою, що розташована «далеко» від центра кластера; центр кожного кластера замінити середнім від елементів кластера; кінець.
Переваги Головні переваги методу k-середніх — його простота та швидкість виконання. Метод k-середніх більш зручний для кластеризації великої кількості спостережень, ніж метод ієрархічного кластерного аналізу (у якому дендограми стають перевантаженими та втрачають наочність).
Недоліки
Одним із недоліків простого методу є порушення умови зв'язності елементів одного кластера, тому розвиваються різні модифікації методу, а також його нечіткі аналоги (), у яких на першій стадії алгоритму допускається приналежність одного елемента множини до декількох кластерів (із різним ступенем приналежності).
Попри очевидні переваги методу, він має суттєві недоліки: Результат класифікації сильно залежить від початкових позицій кластерних центрів Алгоритм чутливий до викидів, які можуть викривлювати середнє Кількість кластерів має бути заздалегідь визначена дослідником
Застосування Метод k-середніх є доволі простим і прозорим, тому успішно застосовується в різноманітних галузях — маркетингових сегментаціях, геостатистиці, астрономії, сільському господарстві тощо.
Див. також
Моделювання Сегментація зображення Алгоритм Ллойда Спектральна кластеризація
Примітки
Посилання Clustering Чисельний приклад кластеризаці методом к-середніх Image Segmentation (k-clusters method)