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

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних^[en] АвтоМН Асоціативні правила Семантичний аналіз^[en] Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик^[en] Навчання онтологій^[en] Мультимодальне навчання^[en]
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання^[en] AdaBoost^[en] Дерева рішень MARS^[en] CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH^[en] CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього^[en]
Знижування розмірності Факторний аналіз Метод незалежних компонент^[en] Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад^[en] Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників^[en]
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс^[en]
Штучна нейронна мережа Автокодувальник Когнітивні обчислення^[en] Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа^[en] Мемтранзистор Електрохімічна ПДД^[en] (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе^[en]
Навчання з людьми Активне навчання (машинне навчання)^[en] Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися^[en]
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання^[en] Регуляризація LASSO^[en] Тихонова Еластично-сіткова^[en] Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання^[en]
Місця машинного навчання ECML PKDD^[en] NeurIPS^[en] ICML^[en] ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту^[en] Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання^[en]
п о р

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

Мета методу — розділити 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 році^[3], хоча ідею методу вперше озвучив Гуґо Штайнгауз (англ. Hugo Steinhaus) у 1957 році^[1]. Стандартний алгоритм вперше запропонував Стюарт Лойд (англ. Stuart Lloyd) у 1957 р^[2].

Алгоритм

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

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

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

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

• Демонстрація алгоритму
• 
  1. ${\displaystyle k}$ початкових «середніх» (тут ${\displaystyle k=3}$) випадково згенеровані у межах домени даних (кольорові).
• 
  2. створено ${\displaystyle k}$ кластерів, асоціюючи кожне спостереження з найближчим середнім. Розбиття відбувається згідно з діаграмою Вороного утвореною середніми.
• 
  3. Центроїд кожного з ${\displaystyle 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)).