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

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

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

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

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

де d — метрика, $x_{i}$$x_{i}$ — і-ий об'єкт даних, а $m_{j}(x_{i})$$m_{j}(x_{i})$ — центр кластера, якому на j-ій ітерації приписаний елемент $x_{i}$$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}$$V=\sum _{i=1}^{k}\sum _{x_{j}\in S_{i}}(x_{j}-\mu _{i})^{2}$

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

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

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

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

Переваги

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

Недоліки

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

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

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

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

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

Див. також

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

Посилання

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

Це незавершена стаття з математики. Ви можете допомогти проекту, виправивши або дописавши її.