✅ Ієрархічний аналіз кластеризації - Посібник з ієрархічного аналізу кластеризації

Огляд ієрархічного аналізу кластеризації

Огляд ієрархічного аналізу кластеризації

Перш ніж ми підемо вперед і зрозуміємо аналіз ієрархічного кластеризації, спробуємо розібратися, що таке кластер? А що таке кластерний аналіз? Кластер - це сукупність об’єктів даних; точки даних у кластері більше схожі між собою та відрізняються від точок даних в іншому кластері. Аналіз кластерів - це, в основному, групування цих точок даних у кластер. Кластеризація - це тип непідконтрольного алгоритму машинного навчання, де немає наборів даних з міткою навчання. Існують різні типи аналізу кластеризації, одним з таких типів є Ієрархічне кластеризація.

Ієрархічна кластеризація допоможе створити кластери в належному порядку / ієрархії. Приклад: найпоширеніший щоденний приклад, який ми бачимо, - це те, як ми замовляємо наші файли та папки на своєму комп’ютері за належною ієрархією.

Типи ієрархічної кластеризації

Далі ієрархічна кластеризація класифікується на два типи, тобто агломераційне кластеризація та поділ кластеризації (DIANA)

Агломераційна кластеризація

У цьому випадку кластеризації ієрархічна декомпозиція проводиться за допомогою стратегії знизу вгору, де вона починається зі створення атомних (малих) кластерів, додаючи один об'єкт даних за один раз, а потім об'єднує їх разом, утворюючи великий кластер в кінці, де цей кластер відповідає всім умовам припинення. Ця процедура є ітеративною, поки всі точки даних не підведені під один великий кластер.

AGNES (AGglomerative NESting) - це тип агломераційної кластеризації, який об'єднує об'єкти даних у кластер на основі подібності. Результатом цього алгоритму є структура на основі дерева, що називається Dendrogram. Тут використовується метрика відстані для визначення того, які точки даних слід поєднувати з кластером. В основному, вона будує матрицю відстані і перевіряє наявність пар кластерів з найменшою відстані і поєднує їх.

На наведеному малюнку зображено агломераційне та розділене кластеризація

Виходячи з того, як вимірюється відстань між кожним кластером, ми можемо мати 3 різні методи

Одиничний зв'язок : де найменша відстань між двома точками в кожному кластері визначається як відстань між кластерами.
Повне з'єднання : У цьому випадку ми розглянемо найдовшу відстань між точками в кожному кластері як відстань між кластерами.
Середня зв'язок: тут ми візьмемо середнє значення між кожною точкою в одному кластері до кожної точки в іншому кластері.

Тепер поговоримо про сильні та слабкі сторони у AGNES; цей алгоритм має часову складність щонайменше O (n ² ), отже, він не справляється з масштабуванням, і ще одним головним недоліком є те, що все, що було зроблено, ніколи не можна скасувати, тобто якщо ми неправильно групуємо будь-який кластер на більш ранній стадії алгоритм тоді ми не зможемо змінити результат / змінити його. Але цей алгоритм має і яскраву сторону, оскільки існує багато менших кластерів, які можуть бути корисними в процесі виявлення, і він створює впорядкування об'єктів, що дуже допомагає у візуалізації.

Роздільна кластеризація (DIANA)

Діана в основному означає розбіжний аналіз; це ще один тип ієрархічної кластеризації, в основному він працює за принципом підходу зверху вниз (зворотний AGNES), коли алгоритм починається з формування великого кластеру, і він рекурсивно ділить найбільш несхожий кластер на два, і він продовжується, поки ми не ' всі подібні точки даних належать до їх відповідних кластерів. Ці алгоритми, що поділяються, призводять до більш точних ієрархій, ніж агломераційний підхід, але вони обчислювально дорогі.

На наведеному малюнку показано поділ кластеризації покроковий процес

Багатофазна ієрархічна кластеризація

Для покращення якості кластерів, породжених вищезазначеними ієрархічними методами кластеризації, ми інтегруємо наші ієрархічні методи кластеризації з іншими методами кластеризації; це називається багатофазною кластеризацією. Різні типи багатофазної кластеризації є наступними:

BIRCH (збалансоване ітеративне скорочення та кластеризація за допомогою ієрархій)
ROCK (кластеризація RObust за допомогою посилань)
ХАМЕЛЕОН

1. Збалансоване ітеративне скорочення та кластеризація за допомогою ієрархій

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

а. Функція кластеризації (допомагає узагальнити кластер)

CF визначається як (n- кількість точок даних у кластері, лінійна сума n точок, квадратна сума n балів). Збереження функції кластеру таким чином допомагає уникнути зберігання детальної інформації про нього, а CF має характер додатків для різних кластерів.

CF ₁ + CF ₂ = 1+ n ₂, LS ₁ + LS ₂, SS ₁ + SS ₂ >

б. Дерево функцій кластеризації (допомагає представляти кластер як ієрархію)

CF-дерево - збалансоване дерево з коефіцієнтом розгалуження B (максимальна кількість дітей) та порогом T (макс. Кількість підкластерів, які можуть зберігатися у листкових вузлах).

Алгоритм в основному працює в 2 фази; у фазі 1 він сканує базу даних і будує дерево CF CF в пам'яті, а у фазі 2 він використовує алгоритм кластеризації, який допомагає кластеризувати вузли листків, видаляючи потоки (розріджені кластери) та групує кластер з максимальною щільністю. Єдиним недоліком цього алгоритму є те, що він обробляє лише числовий тип даних.

2. Надійна кластеризація за допомогою посилань

Посилання визначається як кількість загальних сусідів між двома об’єктами. Алгоритм ROCK - це тип алгоритму кластеризації, який використовує цю концепцію зв'язку з категоричним набором даних. Як ми знаємо, що алгоритми кластеризації, виміряні на відстані, не забезпечують високоякісні кластери для категоричного набору даних, але у випадку ROCK він розглядає також квартали точок даних, тобто, якщо дві точки даних мають однакове сусідство, то вони є швидше за все, належать до одного кластеру. Алгоритм побудує розрізнений графік на першому кроці з урахуванням матриці подібності з поняттям сусідства та порогу подібності. На другому кроці він використовує техніку агломеративної ієрархічної кластеризації на розрізненому графіку.

3. Хамелеон

Цей тип ієрархічного алгоритму кластеризації використовує концепцію динамічного моделювання. Цікаво, чому його називають динамічним? Це називається динамічним, оскільки він має можливість автоматично пристосовуватися до внутрішніх характеристик кластера, оцінюючи схожість кластера, тобто наскільки добре з'єднані точки даних у кластері та в близькості кластерів. Одним з недоліків хамелеона є те, що вартість обробки зависока (O (n ² ) для n об’єктів - найгірша часова складність).

Джерело зображення - Google

Висновок

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

Ієрархічний аналіз кластеризації - Посібник з ієрархічного аналізу кластеризації