Алгоритм CURE

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

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

Недоліки традиційних алгоритмів

Популярний алгоритм кластеризації k-середніх мінімізує критерій суми квадратів помилок:

$E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^{2}$,

де $k$ — число кластерів, $C_{i}$ — отримані кластери, $i=1,2,\dots ,k$, $m_{i}$ — центроїди векторів $p\in C_{i}$.

Враховуючи великі відмінності в розмірах або геометрії різних кластерів, метод квадратичної помилки може розділити великі кластери, щоб мінімізувати квадратичну помилку, що не завжди правильно. Крім того, ці проблеми існують з ієрархічними алгоритмами кластеризації, оскільки жоден із показників відстані між кластерами ($d_{min},d_{mean}$) зазвичай не працює у випадку коли кластери мають різні форми. Крім того, при великому n час роботи алгоритму є високим.

Проблема з алгоритмом BIRCH полягає в тому, що коли кластери генеруються після кроку 3, він використовує центроїди кластерів і призначає кожну точку даних кластеру з найближчим центроїдом. Використання лише центроїда для перерозподілу даних має проблеми, коли кластерам бракує однакових розмірів і форм.

Алгоритм кластеризації CURE

Щоб уникнути проблем із кластерами неоднорідного розміру чи форми, CURE використовує ієрархічний алгоритм кластеризації, який приймає середину між центроїдом і всіма крайніми точками. У CURE вибирається постійне число С, яке відповідає за розсіяні точки кластера, і вони звужуються до центроїда кластера на частку α. Розсіяні точки після стиснення використовуються як представники кластера. Кластери з найближчою парою представників є кластерами, які об'єднуються на кожному кроці ієрархічного алгоритму кластеризації CURE. Це дозволяє CURE правильно ідентифікувати кластери та робить його менш чутливим до викидів.

Обчислювальна складність алгоритму дорівнює O(n ² log n), що робить його обчислювально витратним, а просторова складність дорівнює O(n).

Алгоритм не можна безпосередньо застосувати до великих баз даних через високу обчислювальну складність. Наступні вдосконалення покликані розв'язати цю проблему:

• Випадкова вибірка: випадкова вибірка підтримує великі набори даних. Як правило, випадкова вибірка поміщається в основну пам'ять. Випадкова вибірка передбачає компроміс між точністю та ефективністю.
• Перегородка: Основна ідея полягає в тому, щоб розділити простір зразка на p розділів. Кожен розділ містить n/p елементів. Перший прохід частково кластеризує кожну секцію, поки кінцева кількість кластерів не зменшиться до n/pq для деякої константи q ≥ 1. Другий прохід кластеризації на n/q частково кластеризує розділи. Для другого проходу зберігаються лише репрезентативні точки, оскільки процедура злиття вимагає лише репрезентативних точок попередніх кластерів перед обчисленням репрезентативних точок для об'єднаного кластера. Розбиття вхідних даних зменшує час виконання.
• Позначення даних на диску: враховуючи лише репрезентативні точки для k кластерів, решта точок даних також призначаються кластерам. Для цього вибирається частка випадково вибраних репрезентативних точок для кожного з k кластерів, а точка даних призначається кластеру, що містить найближчу до нього репрезентативну точку.

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

CURE (кількість точок, k)

Вхід: Множина точок S

Вихід: k кластерів

• Для кожного кластера u (кожної вхідної точки) в u.mean і u.rep зберігається середнє значення точок у кластері та набір c репрезентативних точок кластера (спочатку c = 1, оскільки кожен кластер має одну точку даних). Також u.closest зберігає кластер, найближчий до u.
• Усі вхідні точки вставляються в kd-дерево T
• Розглядайте кожну вхідну точку як окремий кластер, обчислюйте u.closest для кожного u, а потім вставляйте кожен кластер у купу Q. (кластери розташовані в порядку збільшення відстані між u та u.closest).
• Доки розмір (Q) > k
  • Видаліть верхній елемент Q (скажімо u) і об'єднайте його з найближчим кластером u.closest (скажімо v) і обчисліть нові репрезентативні точки для об'єднаного кластера w.
  • Вилучіть u і v з T і Q.
  • Для всіх кластерів x у Q оновіть x.closest і перемістіть x
  • вставте w у Q
  • повторяйте, доки виконується нерівність

Доступність

• Бібліотека з відкритим кодом pyclustering включає реалізацію алгоритму CURE на Python і C++.

Дивитися також

• Кластеризація методом k-середніх
• BFR алгоритм

Список літератури

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). CURE: An Efficient Clustering Algorithm for Large Databases (PDF). Information Systems. 26 (1): 35—58. doi:10.1016/S0306-4379(01)00008-4.
• Kogan, Jacob; Nicholas, Charles K.; Teboulle, M. (2006). Grouping multidimensional data: recent advances in clustering. Springer. ISBN 978-3-540-28348-5.
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). Pattern recognition. Academic Press. с. 572—574. ISBN 978-0-12-369531-4.