Кластеризація методом к–середніх

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Кластериза́ція ме́тодом k-сере́дніх (англ. k-means clustering) — популярний метод кластеризації, — впорядкування множини об'єктів в порівняно однорідні групи. Винайдений в 1950-х роках математиком Гуґо Штайнгаузом[1] і майже одночасно Стюартом Ллойдом[2]. Особливу популярність отримав після виходу роботи МакКвіна[3].

Мета методу — розділити n спостережень на k кластерів, так щоб кожне спостереження належало до кластера з найближчим до нього середнім значенням. Метод базується на мінімізації суми квадратів відстаней між кожним спостереженням та центром його кластера, тобто функції

,

де d — метрика,  — і-ий об'єкт даних, а  — центр кластера, якому на j-ій ітерації приписаний елемент .

Історія[ред. | ред. код]

Термін «k-середніх» був уперше вжитий Джеймсом МакКвіном (англ. James MacQueen) у 1967 році[3], хоча ідею методу вперше озвучив Гуґо Штайнгауз (англ. Hugo Steinhaus) у 1957 році[1]. Стандартний алгоритм був вперше запропонований Стюартом Лойдом (англ. Stuart Lloyd) у 1957 р[2].

Алгоритм[ред. | ред. код]

Опис алгоритму[ред. | ред. код]

Маємо масив спостережень (об'єктів), кожен з яких має певні значення по ряду ознак. Відповідно до цих значень об'єкт розташовується у багатовимірному просторі.

  1. Дослідник визначає кількість кластерів, що необхідно утворити
  2. Випадковим чином обирається k спостережень, які на цьому кроці вважаються центрами кластерів
  3. Кожне спостереження «приписується» до одного з n кластерів — того, відстань до якого найкоротша
  4. Розраховується новий центр кожного кластера як елемент, ознаки якого розраховуються як середнє арифметичне ознак об'єктів, що входять у цей кластер
  5. Відбувається така кількість ітерацій (повторюються кроки 3-4), поки кластерні центри стануть стійкими (тобто при кожній ітерації в кожному кластері опинятимуться одні й ті самі об'єкти), дисперсія всередині кластера буде мінімізована, а між кластерами — максимізована

Вибір кількості кластерів відбувається на основі дослідницької гіпотези. Якщо її немає, то рекомендують створити 2 кластери, далі 3,4,5, порівнюючи отримані результати.

Принцип дії[ред. | ред. код]

Принцип алгоритму полягає в пошуку таких центрів кластерів та наборів елементів кожного кластера при наявності деякої функції Ф(°), що виражає якість поточного розбиття множини на k кластерів, коли сумарне квадратичне відхилення елементів кластерів від центрів цих кластерів буде найменшим:

де  — число кластерів,  — отримані кластери, ,  — центри мас векторів .

В початковий момент роботи алгоритму довільним чином обираються центри кластерів, далі для кожного елемента множини ітеративно обраховується відстань від центрів з приєднанням кожного елемента до кластера з найближчим центром. Для кожного з отриманих кластерів обчислюються нові значення центрів, намагаючись при цьому мінімізувати функцію Ф(°), після чого повторюється процедура перерозподілу елементів між кластерами.

Алгоритм методу «Кластеризація за схемою к-середніх»:

  • вибрати k інформаційних точок як центри кластерів поки не завершиться процес зміни центрів кластерів;
  • зіставити кожну інформаційну точку з кластером, відстань до центра якого мінімальна;
  • переконатися, що в кожному кластері міститься хоча б одна точка. Для цього кожний порожній кластер потрібно доповнити довільною точкою, що розташована «далеко» від центра кластера;
  • центр кожного кластера замінити середнім від елементів кластера;
  • кінець.

Переваги[ред. | ред. код]

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

Недоліки[ред. | ред. код]

Одним із недоліків простого методу є порушення умови зв'язності елементів одного кластера, тому розвиваються різні модифікації методу, а також його нечіткі аналоги (англ. fuzzy k-means methods), у яких на першій стадії алгоритму допускається приналежність одного елемента множини до декількох кластерів (із різним ступенем приналежності).

Незважаючи на очевидні переваги методу, він має суттєві недоліки:

  1. Результат класифікації сильно залежить від випадкових початкових позицій кластерних центрів
  2. Алгоритм чутливий до викидів, які можуть викривлювати середнє
  3. Кількість кластерів повинна бути заздалегідь визначена дослідником

Застосування[ред. | ред. код]

Метод k-середніх є доволі простим і прозорим, тому успішно використовується у різноманітних сферах — маркетингових сегментаціях, геостатистиці, астрономії, сільському господарстві тощо.

Примітки[ред. | ред. код]

  1. а б Steinhaus, Hugo. (1957). Sur la division des corps matériels en parties (in French). Bull. Acad. Polon. Sci. 4 (12): 801–804. 
  2. а б Lloyd., S. P. (1957). Least square quantization in PCM". Bell Telephone Laboratories Paper. 
  3. а б Some Methods for classification and Analysis of Multivariate Observations". Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press. pp. 281–297. Архів оригіналу за 23 жовтня 2015. Процитовано 16 квітня 2019. 

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]