Ієрархічна кластеризація

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних АвтоМН Асоціативні правила Семантичний аналіз Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик Навчання онтологій Мультимодальне навчання
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання 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
Пов'язані статті Глосарій штучного інтелекту Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання

Ієрархічна кластеризація (англ. hierarchical cluster analysis, HCA) в добуванні даних та статистиці — метод кластерного аналізу, який намагається побудувати ієрархію кластерів. Стратегії побудови ієрархічної кластеризації діляться на два типи:

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

Зазвичай розбиття та об'єднання визначаються у жадібний спосіб. Отриману ієрархію типово зображають як дендрограму.

Стандартний алгоритм ієрархічної кластеризації має часову складність ${\mathcal {O}}(n^{3})$ та потребує ${\mathcal {O}}(n^{2})$ пам'яті, що занадто повільно навіть для наборів даних середнього розміру. Однак, для деяких випадків, є агломератові методи, які виконуються за час ${\mathcal {O}}(n^{2})$. Це методи SLINK при однозв'язній та CLINK при повнозв'язній кластеризації. Використання купи дозволяє у загальному випадку скоротити час виконання до ${\mathcal {O}}(n^{2}\log n)$ ціною збільшення вимог до об'єму пам'яті. Такі накладні витрати на пам'ять, для багатьох мов програмування, роблять цей підхід неможливим для реалізації.

Окрім спеціального однозв'язного випадку немає алгоритмів (окрім повного перебору за час ${\mathcal {O}}(2^{n})$), який би гарантував оптимальний розв'язок.

Розділювальна кластеризація з повним перебором виконується за час ${\mathcal {O}}(2^{n})$, проте звичайною практикою є використання більш швидких евристик для розбиття, такі як k-середні.

Дендрограма

Дендрограма

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

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

У роботах по кластерному аналізу описаний досить значний ряд способів побудови (англ. sorting strategies) дендрограмм:

1. Метод одиночного зв'язку (англ. single linkage). Також відомий як «метод найближчого сусіда».
2. Метод повного зв'язку (англ. complete linkage). Також відомий як «метод далекого сусіда».
3. Метод середнього зв'язку (англ. pair-group method using arithmetic averages).

• Незважений (англ. unweighted).
• Зважений (англ. weighted).

1. Центроїдний метод (англ. pair-group method using the centroid average).

• Незважений.
• Зважений (медіанний).

1. Метод Уорда (англ. Ward's method).

Для перших трьох методів існує загальна формула, запропонована А. Н. Колмогоровим для заходів подібності:

$K_{\eta }([i,j],k)=\left[{\frac {(n_{i}K(i,k)^{\eta }+(n_{j}K(j,k)^{\eta })}{n_{i}+n_{j}}}\right]^{\frac {1}{\eta }},-{\mathcal {1}}\leqslant \eta \leqslant +{\mathcal {1}}$

де $[i,j]$ — група з двох об'єктів (кластерів) і $j$; $k$ — об'єкт (кластер), з яким шукається схожість зазначеної групи; $n_{i}$ — кількість елементів у кластері ${\displaystyle }$; $n_{j}$ — кількість елементів у кластері $j$. Для відстаней є аналогічна формула Ланса — Вільямса.

Центроїдний метод використовує для перерахунку матриці відстаней. Як відстані між двома кластерами у цьому методі береться відстань між центрами тяжіння.

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

Кореляційні плеяди

Дендрит

Широко застосовуються в геоботаніці та флористиці. Їх часто називають «кореляційними плеядами».

Окремим випадком є метод, відомий як метод побудови «оптимальних дерев (дендритів)», який був запропонований математиком львівської школи Гуго Штейнгаузом, згодом метод був розвинений математиками вроцлавської таксономічної школи. Дендрити також не повинні утворювати циклів. Можна частково використовувати спрямовані дуги графів при використанні додатково заходів включення (несиметричних заходів подібності).

Діаграма Чекановського

Метод «діагоналізації» матриці відмінності і графічне зображення кластерів уздовж головної діагоналі матриці відмінності (діаграма Чекановського) вперше запропонований Яном Чекановським у 1909 році. Наведемо опис методики:

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

Наведемо гіпотетичний приклад отримання такої діаграми. Основою методу є побудова матриці транзитивного замикання.

Приклад розрахунку діаграми Чекановского

Для побудови матриці транзитивного замикання візьмемо просту матрицю подібності і помножимо її на саму себе:

$K^{(2)}(i,j)=max(min(K(i,1),K(1,j)),...,min(K(i,q),K(q,j)))$,

де $K(i,j)$ — елемент, що стоїть на перетині $i$-го рядка $j$-го стовпця в новій (другій) матриці, отриманій після першої ітерації; $q$ — загальна кількість рядків (стовпчиків) матриці подібності. Дану процедуру необхідно продовжувати поки матриця не стане ідемпотентною (тобто самоподібною): $K^{(n)}(i,j)=K^{(n-1)}(i,j)$, де $n$ — кількість ітерацій.

Далі перетворюємо матрицю таким чином, щоб близькі числові значення знаходилися поряд. Якщо кожному числовому значенню поставити у відповідність будь-який колір або відтінок кольору (як у нашому випадку), то отримаємо класичну діаграму Чекановського. Традиційно темніший колір відповідає більшій подібності, а світліший — меншій. В цьому вона схожа з теплокартою матриці відстаней.

Див. також

• Граф (математика)
• Кластерний аналіз
• Метричний простір
• Завдання класифікації
• Гілкова декомпозиція