Алгоритм Сure (clustering using representatives) - Студопедія
Алгоритм [36], як і всі агломеративные ієрархічні методи, спочатку всі точки розглядає як кластери і кожному кроці об'єднує найближчу пару. Але замість підрахунку подібності (або відстані) для кожного кластера вибирається деяка кількість c представницьких точок, що найкраще представляють кластер, і далі тільки ці точки використовуються для визначення подібності між кластерами.
Зокрема, вибирається відстань між двома найближчими представницькими точками двох кластерів. Визначаються представницькі точки вибором з найбільш віддалених точок, що належать кластеру і далі зменшенням відстані між цими точками та центром кластера на деяку частку цієї відстані. Якщо застосовується міра, подібність, то зменшено має бути подібність.
Отже, якщо a = 0, то метод наближається до методів кластеризації за принципом найближчого сусіда, а разі a = 1, до центроїдним методам. Автори методу радять обирати a від 0.2 до 0.7, що дозволить, на їхню думку, набувати кластерів несферичної форми. А значення пропонують вибирати від 10 до 50, залежно від обсягу даних і передбачуваного розміру і форми кластерів.
Вибір таких точок відбувається в такий спосіб. Спочатку вибирається перша точка, найбільш віддалена від центру (середньої точки, середнього вектора) кластера. І далі на кожному наступному кроці, вибирається точка найбільш віддалена від усіх точок, знайдених раніше. Передбачається, що з представницьких точок найкраще відбивають форму і геометричні розміри кластерів, яких вони ставляться.
Розглянемо докладніше алгоритм кластеризації. На початку, для кожного кластера набір представницьких точок містить лише одну точку,оскільки самі кластери складаються із однієї точки.
Крок 1. Для кожного кластера знаходиться найближчий кластер.
Крок 2. Пари, що мають найбільшу подібність, об'єднуються і для новоствореного кластера знаходяться представницькі точки і найближчий кластер.
Крок 3. Виконується перерахунок найближчого кластера для деякого піднабору кластерів. Цьому піднабору належать кластери, у яких найближчими кластерами були об'єднані кластери. Причому, якщо близькість нового кластера з кластером із цього піднабору ще більше, ніж із кластером, що увійшли до об'єднання, то перерахунок не потрібний і найближчим вважається новий кластер. Якщо отримані цьому кроці кластери відповідають цільової функції, то завершити кластеризацію, якщо ні – перейти до кроку 3.
Такий підхід дозволяє дійсно отримувати кластери будь-яких як сферичних, так і несферичних форм, а також різних розмірів. Загальна часова складність цього алгоритму дорівнює O(n 2 log(n)), де n – кількість об'єктів кластеризації, причому це максимальна складність, його середня складність дорівнює O(n 2 +nm log(n)), де m – змінна кількість кластерів , що входять до набору на 4-му кроці. З іншого боку, просторова складність цього алгоритму з допомогою використання динамічних структур даних (купи, дерева) дорівнює O(n)).
Також, збільшення продуктивності у цьому алгоритмі застосовується прийом попереднього поділу. Основна ідея такого підходу полягає в тому, щоб розділити простір n об'єктів на p рівних частин і провести ієрархічну кластеризацію в кожній з них, доки кількість кластерів у кожній такій частині не стане рівною.
, (39)
де q & gt; 0. Далі здійснювати вже ієрархічна кластеризація всіх отриманих кластерів.
ДоНедолікам даного методу можна віднести те, що він, при об'єднанні кластерів, не враховує їх внутрішньої подібності, тобто він використовує цільову функцію для всього розбиття, але не на кожному кроці при виборі кластерів, що об'єднуються. І, зрозуміло, як і в багатьох подібних методів, основний недолік CURE в тому, що необхідні параметри, від яких великою мірою залежать результати аналізу.
Чи не знайшли те, що шукали? Скористайтеся пошуком:
Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно