Спектральна кластеризація

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

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

Метод був розроблений у 1970-х для розділення графів і пізніше був багаторазово поліпшений і застосований для ширшого класу задач. Його ідея полягає в тому, щоб, розглядаючи множину спостережень як зважений граф (де кожному спостереженню відповідає вершина, а ребра мають вагу, що дорівнює подібності пари спостережень), знайти такий мінімальний розріз цього графа, щоб два отримані підграфи були близькими за розміром.

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

Історія

Приклад спектрального розбиття простого графа на дві частини. Вершини 1-4 відповідають додатнім компонентам вектора Фідлера, а 5-8 — від'ємним. Тоді розірваними мають бути лише два ребра

Ідея спектральної кластеризації ґрунтується на роботах Кеннета Холла — він шукав спосіб спроєктувати граф на числову пряму та, більш загально, в багатовимірний евклідів простір і запропонував використовувати для цього власні вектори матриці Лапласа, а також Доната й Хоффмана, які помітили, що власні вектори модифікованої матриці зв'язності можна застосувати для задачі розбиття графа на рівні частини. У 1973–1975 роках чеський математик Мирослав Фідлер показав, що найменше ненульове власне значення матриці Лапласа графа відповідає його зв'язності й показав зв'язок відповідного власного вектора та породжуваної ним кластеризації в загальному випадку (результати Доната й Хоффмана стосувалися деяких специфічних типів графів). Доробок Фідлера в спектральній теорії графів є значним, тому найменше ненульове власне значення матриці Лапласа називають числом Фідлера, а відповідний вектор — вектором Фідлера. Пізніше було показано, що графи з маленьким числом Фідлера мають маленьке співвідношення кількості видалених ребер до кількості вершин, які розділяються, що відповідає уявленню про «хорошу» кластеризацію.

Застосування алгоритму стримувалося важкістю задачі пошуку власних значень та векторів, допоки у 80-х роках не з'явилися ефективніші алгоритми, такі як метод Ланцоша, і багато експериментів на реальних графах показали практичну придатність методу.

«Тарганячий граф» з роботи Міллера і Гваттарі. Наївна спектральна кластеризація пропонує розділити граф навпіл за вертикальною лінією (розриваючи k зв'язків) замість того щоб розділити його за горизонтальною, розриваючи лише два зв'язки.

Спектральна кластеризація швидко стала популярною й стандартною в багатьох галузях, проте в 1995 році Міллер і Гваттарі привернули увагу до дивної поведінки алгоритму на деяких типах графів. Застосований Фідлером підхід, згідно з яким два кластери графа визначалися за тим, більші чи менші за нуль відповідні компоненти вектора Фідлера (наївна бісекція), давав вочевидь неправильну кластеризацію на графах, що могли траплятися в реальному житті. Також у роботі було запропоновано застосовувати для поділу не лише вектор Фідлера, а й ще кілька найменших ненульових власних векторів.

Також велися пошуки оптимального значення для поділу вектора Фідлера (замість нульового). 1992 року Ларс Хаген і Ендрю Канг запропонували новий підхід для оцінки, Ratio-Cut, який дозволив краще знаходити кластери неоднакового розміру, а в 2000 році Цзяньбо Ши і Джитендра Малик запропонували ще одну метрику якості кластеризації і показали, що для пошуку найкращого розрізу за нею необхідно модифікувати матрицю Лапласа. Така модифікована матриця отримала назву нормалізована матриця Лапласа, а сам метод отримав назву Normal-Cut (або NCut). 2001 року був запропонований MinMaxCut.

В 2001 році Цзяньбо Ши і Марина Мейла запропонували нову інтерпретацію спектральної кластеризації за методом NCut: при марківському випадковому блуканні по графу кластеризація виділяє такі компоненти, переходи між якими відбуваються якнайрідше.

Того ж року Ендрю Ин, Майкл Джордан і Яїр Вайс запропонували використовувати кластеризацію к-середніх на просторі, утвореному власними векторами. Важливою зміною в їх підході є те, що застосовуються власні вектори, що відповідають найбільшим, а не найменшим власним значенням, а також використовується спеціальна форма матриці Лапласа. Метод Ина-Джордана-Вайса набув популярності та часто згадується як NJW-алгоритм.

Алгоритм

Побудова матриці суміжності

Для представлення всіх спостережень у вигляді графа потрібно визначити функцію подібності. Ця функція двох аргументів має бути невід'ємною й симетричною. Подібність велика для близьких точок і прямує до нуля для далеких. Якщо максимальна подібність дорівнює 1, вона може бути інтерпретована як імовірність того, що спостереження належать до одного кластеру. Для потреб алгоритму подібність точок самих собі зануляється: $w_{ii}=0$, тобто отриманий граф не має петель.

Якщо близькість точок визначається відстанню між ними, простим вибором здається подібність як величина, обернена до відстані між точками:

$w_{ij}=1/d_{ij}$

Проте ця величина дуже сильно реагує на малі зміни для близьких точок, тому в знаменник додають деяку константу:

$w_{ij}=1/(d_{ij}+\varepsilon )$

Більш популярним вибором є гаусове ядро:

$w_{ij}=e^{-d_{ij}^{2}/t}$,

де t — деякий масштабний коефіцієнт, що задається вручну,

або його нормалізований варіант:

$w_{ij}=e^{-d_{ij}^{2}/\sigma _{i}\sigma _{j}}$,

де $\sigma _{i}$ — відстань між точкою $x_{i}$ та її n-тим найближчим сусідом.

В окремих випадках можуть застосовуватися специфічні міри близькості, такі як коефіцієнт Жаккара або косинусна подібність.

Попарні подібності між точками формують матрицю подібності (англ. Affinity matrix), яка позначається як $W$.

Таку матрицю можна вважати матрицею суміжності зваженого повного графа (тобто такого, де ребра існують між будь-якими двома вершинами), а можна обнулити деякі з елементів, зменшуючи кількість ребер. Існує кілька підходів до того, які ребра залишати:

1. Тільки якщо відстань між відповідними точками є меншою за деяку величину $d_{ij}\leq \varepsilon$
2. Тільки якщо точка $i$ входить до $k$ найближчих сусідів точки $j$ або ж точка $j$ входить до $k$ найближчих сусідів точки $i$
3. Тільки якщо точка $i$ входить до $k$ найближчих сусідів точки $j$ і одночасно точка $j$ входить до $k$ найближчих сусідів точки $i$ (mutual K-nearest-neighbors graph)

Побудова матриці Лапласа й обчислення її власних векторів

Задамо діагональну матрицю $D$, чиї елементи дорівнюють сумі ваг всіх ребер, що виходять із відповідної вершини:

$d_{ii}=\sum _{j=1}^{i}w_{ij}$

Тоді матриця Лапласа визначається як $L=D-W$. У деяких джерелах її називають матрицею Кірхгофа.

Також застосовується нормалізована матриця Лапласа: $L=D^{-1/2}(D-W)D^{-1/2}$. Іншим способом нормалізації матриці Лапласа є $L=I-DW$.

Для NSW-алгоритму матриця Лапласа обчислюється як $L=D^{-1/2}WD^{-1/2}$.

У будь-якому випадку після обчислення матриці Лапласа (нормалізованої чи ні) необхідно обчислити її власні значення та власні вектори.

Кластеризація за власними векторами

Граф, що складається з двох компонент, і вектор Фідлера цього графу. Позитивні й негативні компоненти вектора добре розділяються

Якщо граф, що задається матрицею суміжності $W$, має $P$ компонент, то $P$ власних чисел матриці Лапласа будуть нульовими. Решта з них завжди будуть додатними. Для кластеризації необхідно взяти один або більше векторів, що відповідають найменшим ненульовим власним значенням. У найпростішому варіанті береться один вектор. Кількість компонент вектора дорівнює кількості точок у графі. У випадку хорошої кластеризації компоненти вектора утворюють яскраво виражені кластери, які можуть бути зіставлені з оригінальними точками. Часто значення, що розділяє два кластери, лежить поблизу нуля (або дорівнює нулю).

Вектор Фідлера для «тарганячого графу». Позитивні й негативні компоненти вектора розділяються погано, проте можливий поділ на три кластери замість двох

Для поділу на більш ніж два кластери алгоритм можна застосовувати рекурсивно, але для деяких графів кращим є поділ одразу на кілька компонент. Якщо в спектрі графа є розрив (англ. eigengap), тобто проміжок між $k$ і $k+1$ ненульовими власними значеннями значно більший за проміжки між сусідніми з ними власними значеннями, то кількість кластерів дорівнює $k$.

Якщо ж використовуються більше одного власного вектора, з них формується нова матриця, у якій кожен рядок відповідає точці графа, а кожен стовпчик — одному з обраних власних векторів. Така матриця може бути інтерпретована як точки в деякому $p$-вимірному просторі (де $p$ — кількість векторів). У цьому просторі можна провести кластеризацію за якоюсь простою процедурою, зазвичай k-середніх або DBSCAN. Кластери, виявлені в цьому просторі власних векторів, відповідають кластерам в оригінальному просторі.

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

Цільові функції кластеризації

Існує кілька підходів оцінювання кластеризації:

• RatioCut: шукає такий поділ на два підграфи $U$ і $V$, що мінімізується величина

$Rratio(U,V)=cut(U,V)(1/|U|+1/|V|)$ або ${\frac {cut(U,V)}{|U|\cdot |V|}}$, де $cut(U,V)$ — сумарна вага зв'язків, що розриваються, а $|U|,|V|$ кількість вершин в отриманих кластерах.

Цей принцип може бути розширений і на випадок більше ніж двох кластерів:

$Rratio(V_{1},V_{2},...,V_{n})={\frac {cut(V_{1},V_{2},...,V_{n})}{|V_{1}|\cdot |V_{2}|\cdot ...\cdot |V_{n}|}}$

• NormalCut: мінімізує величину

$Rnormal(U,V)=cut(U,V)(1/d_{U}+1/d_{V})$, де $d_{A}$ сумарна вага всіх ребер, які виходять з вершин кластера А (включно з тими, які з'єднують його з іншими кластерами).

• MinMaxCut: мінімізує величину

$Rmm(U,V)=cut(U,V)\left({\frac {1}{d_{U}-cut(U,V)}}+{\frac {1}{d_{V}-cut(U,V)}}\right)$, тобто в знаменнику на відміну від NormalCut стоїть сума ваги лише тих ребер, які з'єднують точки всередині кластеру (ребра, що сполучають різні кластери, не враховуються).

Принцип роботи алгоритму

Уявімо, що ми маємо зважений граф $G$ з вершинами $V$, ребрами $E$ та матрицею суміжності $W$, який деяким чином розділяємо на два кластери. Позначивши належність кожної точки до одного з кластерів числом 1 або -1, ми отримаємо вектор виду x=[1, 1, -1, 1, ....., -1, 1], який описуватиме конкретну кластеризацію. Якщо ми хочемо, щоб кластери мали однаковий розмір, ми можемо записати умову

$\sum _{i}x_{i}\approx 0$ (рівність є наближеною, оскільки, наприклад, при непарній кількості вершин така сума не може дорівнювати нулю).

Тепер спробуємо з врахуванням цієї умови оцінити величину

$\sum _{(x_{i},x_{j})\in E}w_{ij}(x_{i}-x_{j})^{2}$, де сумування проходить по всіх ребрах графа.

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

Проте наближена умова, представлена вище, непрактична, тому необхідно дещо видозмінити цю задачу. Нехай $x_{i}$ можуть набувати довільних дійсних значень. Тоді можна переписати умову у строгому вигляді:

$\sum _{i}x_{i}=0$

Також, щоб уникнути тривіального розв'язку $x_{i}=0$, який виникатиме в цьому випадку, додамо другу умову

$\sum _{i}x_{i}^{2}=1$

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

Вираз вище пов'язаний із ненормалізованою матрицею Лапласа графу:

$\sum _{(x_{i},x_{j})\in E}w_{ij}(x_{i}-x_{j})^{2}=\sum _{(x_{i},x_{j})\in E}w_{ij}(x_{i}^{2}+x_{j}^{2})-\sum _{(x_{i},x_{j})\in E}w_{ij}2x_{i}x_{j}=\sum _{x_{i}\in V}d_{i}x_{i}^{2}-x^{T}Wx=x^{T}Dx-x^{T}Wx=x^{T}Lx$

Тобто, нам необхідно знайти такий вектор $x$, при якому вираз $x^{T}Lx$ набуває мінімального значення, враховуючи умови

$\sum _{i}x_{i}=0$ і $\sum _{i}x_{i}^{2}=1$

Доведемо, що розв'язок цієї задачі у випадку однозв'язного графа дається власним вектором, що відповідає другому найменшому власному значенню матриці Лапласа цього графа.

Сума будь-якого рядка або стовпчика матриці $L$ дорівнює нулю, тому можна записати

$L{\bar {1}}=0=0{\bar {1}}$

отже, одне з власних чисел $L$ дорівнює нулю, а відповідний власний вектор має всі $n$ компонент рівними. Зі спектральної теореми випливає, що всі власні вектори $L$ утворюють ортонормований базис, тобто їх довжина дорівнює 1. Отже, всі компоненти першого вектора дорівнюють $1/{\sqrt {n}}$. Решта власних чисел матриці Лапласа більші за нуль (в подальшому будемо вважати, що всі власні числа пронумеровані в порядку зростання і в тому ж порядку пронумеровані відповідні їм вектори). Довжина будь-якого з пов'язаних із ними власних векторів ${\bar {v}}$ також дорівнює одиниці, а отже

$\sum _{i}v_{i}^{2}=1$

Також, скалярний добуток будь-якої пари векторів дорівнює нулю, а отже для будь-якого власного вектора, крім першого,

$\sum _{i}v_{i}/{\sqrt {n}}=0\Rightarrow \sum _{i}v_{i}=0$

Вектор $x$ може бути розкладений у базисі власних векторів

$x=\sum _{i}{\bar {v}}_{i}a_{i}$

Проте якщо сума компонентів вектора $x$, який ми шукаємо, дорівнює нулю, то множник при першому власному векторі (єдиному, сума компонентів якого ненульова) дорівнює нулю. Крім того, сума квадратів компонентів $x$ дорівнює сумі квадратів коефіцієнтів розкладу $a_{i}$

$\sum _{i}x_{i}^{2}=x^{T}x=\left[\sum _{i=2}^{n}{\bar {v}}_{i}a_{i}\right]^{T}\left[\sum _{j=2}^{n}{\bar {v}}_{j}a_{j}\right]=\sum _{i=2}^{n}\sum _{j=2}^{n}{\bar {v}}_{i}^{T}{\bar {v}}_{j}a_{i}a_{j}=\sum _{i}a_{i}^{2}$

Тоді, скориставшись тим, що за визначенням власних векторів $L{\bar {v}}_{j}=\lambda _{j}{\bar {v}}_{j}$, ми можемо записати, що

$x^{T}Lx=\left[\sum _{i=2}^{n}{\bar {v}}_{i}a_{i}\right]^{T}L\left[\sum _{j=2}^{n}{\bar {v}}_{j}a_{j}\right]=\sum _{i=2}^{n}\sum _{j=2}^{n}a_{i}a_{j}{\bar {v}}_{i}^{T}L{\bar {v}}_{j}=\sum _{i=2}^{n}\sum _{j=2}^{n}a_{i}a_{j}{\bar {v}}_{i}^{T}\lambda _{j}{\bar {v}}_{j}=\sum _{i=2}^{n}\sum _{j=2}^{n}a_{i}a_{j}\lambda _{j}{\bar {v}}_{i}^{T}{\bar {v}}_{j}=\sum _{i=2}^{n}a_{i}^{2}\lambda _{i}$

Оскільки $\lambda _{2}\leq \lambda _{3}\leq \lambda _{4}...\leq \lambda _{n}$, а сума квадратів $a_{i}$ дорівнює одиниці, то зрозуміло, що мінімального значення функція набуває, коли $a_{2}=1,a_{3}=a_{4}=...=a_{n}=0$. Тобто вектор $x$ дорівнює другому власному вектору.

Інтерпретація випадкового блукання

Якщо ми розглянемо марківське випадкове блукання по графу таке, що матриця $P=D^{-1}W$ містить у собі ймовірності переходу від вершини до вершини, то спектральна кластеризація описуватиме розбиття на такі групи вершин, що переходи між ними є дуже малоймовірними.

Застосування

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

При використанні алгоритму користувач має визначити наступні параметри:

• Матриця суміжності графа. Є одним з найважливіших параметрів, бо визначає власне зовнішній вид графа. Можна розділити цю задачу на дві підзадачі:
  1. Визначення функції подібності. Деякі функції подібності (в тому числі найпопулярніша, гауссове ядро) мають у собі додаткові гіперпараметри, такі як масштабний фактор.
  2. Вибір, чи буде граф повним або ж кожна точка буде з'єднуватися лише з найближчими сусідами. У другому випадку з'являється додатковий параметр — кількість сусідів або максимальна відстань між ними.
• Вибір матриці Лапласа (нормалізована або ненормалізована). Якщо задача краще відповідає RatioCut, то краще використовувати ненормалізовану матрицю, а якщо NCut, то нормалізовану. Якщо є сумніви, загалом кращим вибором вважається нормалізована матриця Лапласа.
• Кількість кластерів, на які потрібно розділити граф, і метод поділу (рекурсивний або кластеризація через k-середніх). Якщо у спектрі графа є яскраво виражений розрив, то його положення може вказувати на оптимальну кількість кластерів.

Попри значні переваги, спектральна кластеризація має й кілька недоліків:

• Вона порівняно повільна (через необхідність обчислення власних векторів великих матриць)
• Не зрозуміла інтуїтивно, і часом результати можуть бути складними для інтерпретації
• Чутлива до випадкових початкових значень. Для кращого результату бажано запустити алгоритм кілька разів. Також це призводить до нестабільної роботи на зашумлених даних.

Порівняння з іншими алгоритмами кластеризації

Порівняння спектральної кластеризації (ліворуч) і кластеризації методом к-середніх на неглобулярних кластерах

Багато алгоритмів кластеризації, такі як метод k–середніх або модель гаусової суміші, шукають глобулярні кластери — тобто опуклі кластери, які мають «центр» із великою щільністю, навколо якого й розподілені спостереження. Вони мають труднощі з пошуком кластерів складних форм (неопуклі фігури, протяжні лінії). На відміну від таких методів, спектральна кластеризація знаходить кластери довільної форми, зокрема такі складні, як спіралі, що переплітаються.

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

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

Реалізація в програмних бібліотеках

Спектральна кластеризація включена в спеціалізовані математичні пакети на багатьох мовах: Scikit-learn і Dask, написані мовою Python, пакет kernlab на R, пакет SpectralClustering мовою Julia, бібліотека Dlib на C++. Також алгоритм реалізовано в математичних пакетах MATLAB, SAS.

Література

• Тревор Хасти, Роберт Тибширани, Джером Г. Фридман. Основы статистического обучения: интеллектуальный анализ данных, логический вывод и прогнозирование. — 2-е изд. — Київ : «Діалектика-Вільямс», 2020. — 768 с. — ISBN 978-617-7812-91-2.
• Bolla M. Spectral Clustering and Biclustering: Learning Large Graphs and Contingency Tables. — 1. — Wiley, 2013. — 292 с. — ISBN 978-111-8344-92-7.
• Liu J., Han J. Spectral Clustering // Data clustering: Algorithms and Applications. — 1. — New York : Chapman and Hall, 2014. — 652 с. — ISBN 9781315373515.