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

Машинне навчання та добування даних
Задачі класифікація кластерування регресія виявлення аномалій асоціативні правила навчання з підкріпленням структурове передбачування проектування ознак навчання ознак інтерактивне навчання напівавтоматичне навчання спонтанне навчання навчання ранжуванню виведення граматик
Кероване навчання (класифікація • регресія) ансамблі (бутстрепова агрегація, випадковий ліс, підсилювання) дерева рішень доречно-векторна машина k-НС лінійна регресія логістична регресія наївне баєсове опорно-векторна машина нейронні мережі перцептрон
Кластерування BIRCH ієрархічна k-середніх очікування-максимізація DBSCAN OPTICS зсув середнього
Зниження розмірності факторний аналіз метод незалежних компонент канонічна кореляція лінійний розділювальний аналіз метод головних компонент розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості
Структурове передбачування графові моделі (баєсова мережа, прихована марковська модель, умовне випадкове поле)
Виявлення аномалій k-НС коефіцієнт локального відхилення
Нейронні мережі автокодувальник багатошаровий перцептрон глибинне навчання згорткова нейронна мережа обмежена машина Больцмана рекурентна нейронна мережа самоорганізаційне відображення
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць
Теорія дилема зсуву та дисперсії ймовірно майже правильне навчання мінімізація емпіричного ризику оккамове навчання статистичне навчання теорія Вапника — Червоненкіса теорія обчислювального навчання
Місця машинного навчання NIPS ICML ML JMLR ArXiv:cs.LG

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

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

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

де d — метрика, $x_{i}$ — і-ий об'єкт даних, а $m_{j}(x_{i})$ — центр кластера, якому на j-ій ітерації приписаний елемент $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 кластерів, коли сумарне квадратичне відхилення елементів кластерів від центрів цих кластерів буде найменшим:

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

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

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

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

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

Переваги

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

Недоліки

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

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

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

Застосування

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

Див. також

• Моделювання
• Сегментація зображення
• Алгоритм Ллойда

Посилання

• Clustering
• Чисельний приклад кластеризаці методом к-середніх
• Image Segmentation (k-clusters method)
• Журнал «Комп'ютерна графіка та мультимедіа»