Кластерування методом k–середніх

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

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

${\displaystyle \,\sum _{i=1}^{N}d(x_{i},m_{j}\,(x_{i}))^{2}\ }$,

де d — метрика, ${\displaystyle x_{i}}$ — і-ий об'єкт даних, а ${\displaystyle m_{j}(x_{i})}$ — центр кластера, якому на j-ій ітерації приписаний елемент ${\displaystyle x_{i}}$.

Історія

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

Алгоритм

Опис алгоритму

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

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

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

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

Принцип дії

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

${\displaystyle V=\sum _{i=1}^{k}\sum _{x_{j}\in S_{i}}(x_{j}-\mu _{i})^{2}}$

де ${\displaystyle k}$ — число кластерів, ${\displaystyle S_{i}}$ — отримані кластери, ${\displaystyle i=1,2,\dots ,k}$, ${\displaystyle \mu _{i}}$ — центри мас векторів ${\displaystyle x_{j}\in S_{i}}$.

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

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

• вибрати 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. J. MacQueen (1967). Some methods for classification and analysis of multivariate observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press: 281—297. Процитовано 16 квітня 2019.

Посилання

• Clustering [ 15 Травня 2015 у Wayback Machine.]
• Чисельний приклад кластеризаці методом к-середніх [ 9 Серпня 2018 у Wayback Machine.]
• Image Segmentation (k-clusters method) [ 14 Вересня 2008 у Wayback Machine.]
• Александр Вежневец, Ольга Баринова (2006). . Компьютерная графика и мультимедиа (№4(14)).