Алгоритм CURE

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^[en] полягає в тому, що коли кластери генеруються після кроку 3, він використовує центроїди кластерів і призначає кожну точку даних^[en] кластеру з найближчим центроїдом. Використання лише центроїда для перерозподілу даних має проблеми, коли кластерам бракує однакових розмірів і форм.

Алгоритм кластеризації 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++.

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

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

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.