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

Машинне навчання та добування даних
Задачі
класифікація кластеризація регресія виявлення аномалій асоціативні правила навчання з підкріпленням структурне передбачення навчання ознак інтерактивне навчання напівавтоматичне навчання виведення граматик
Навчання з учителем (класифікація • регресія)
дерева рішень ансамблі (бутстрепова агрегація, підсилювання, випадковий ліс) k-NN лінійна регресія наївне баєсове нейронні мережі логістична регресія перцептрон метод опорних векторів метод доречних векторів
Кластеризація
BIRCH ієрархічна k-середніх очікування-максимізація DBSCAN OPTICS зсув середнього
Зменшення розмірності
факторний аналіз канонічна кореляція аналіз незалежних складових лінійний дискримінаційний аналіз розклад невід'ємних матриць метод головних компонент t-розподілене вкладення стохастичної близькості
Структурне передбачення
графічні моделі (баєсова мережа, умовне випадкове поле, прихована марковська модель)
Виявлення аномалій
k-NN Фактор локального відхилення
Нейронні мережі
автоасоціатор Глибинне навчання багатошаровий перцептрон рекурентна нейронна мережа Обмежена машина Больцмана самоорганізаційна карта Кохонена згорткова нейронна мережа
Теорія
дилема зсуву та дисперсії теорія обчислювального навчання мінімізація емпіричного ризику ймовірно майже правильне навчання статистичне навчання теорія Вапника-Червоненкіса

Кластериза́ція зобра́ження ме́тодом k-сере́дніх полягає у наступному: будується деяка цільова функція Ф(°), що виражає якість поточного розбиття зображення на k кластерів із центрами у точках Сі, і=1,…,n; k — задано.

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

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

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

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

Див. також

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

Посилання

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

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