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

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

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

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

Історія

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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: мінімізує величину

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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}$

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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}}$

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

${\displaystyle 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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

1. Hall, Kenneth M. (1970). An r-Dimensional Quadratic Placement Algorithm. Management Science (англ.). 17 (3): 219—229.
2. Essential spectral theory, Hall’s spectral graph drawing, the Fiedler value(англ.)
3. Spielman, Daniel A.; Teng, Shang-Hua (2007). Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra and its Applications (англ.). 421 (2-3): 284—305. doi:10.1016/j.laa.2006.07.020.
4. Donath, W.; Hoffman, A. (1972). Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices (PDF). IBM Technical Disclosure Bulletin (англ.). 15 (3): 938—944.
5. Fiedler, Miroslav (1975). A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory (PDF). Czechoslovak Mathematical Journal (англ.). 25 (4): 619—633.
6. Guattery, Stephen; Miller, Gary L. (1995). On the Performance of Spectral Graph Partitioning Methods (PDF). ACM-SIAM Symposium on Discrete Algorithms (англ.): 233—242.
7. Hagen, Lars; Kahng, Andrew B. (1992). New spectral methods for ratio cut partitioning and clustering (PDF). IEEE Transactions on Computer-Aided Design (англ.). 11 (9): 1074—1085.
8. Shi, Jianbo; Malik, Jitendra (2000). Normalized Cuts and Image Segmentation (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence (англ.). 22 (8): 888—905. doi:10.1109/34.868688.
9. Ding, Chris; Xiaofeng, He; Hongyuan, Zha (2001). A min-max cut algorithm for graph partitioning and data clustering (PDF). Proceedings 2001 IEEE International Conference on Data Mining (англ.): 107—114. doi:10.1109/ICDM.2001.989507.
10. Meila, Marina; Shi, Jianb (2000). Learning Segmentation by Random Walks (PDF). Advances in Neural Information Processing Systems 13 (NIPS 2000) (англ.): 837—843. doi:10.5555/3008751.3008873. {{}}: Перевірте значення |doi= ()
11. Ng, Andrew Y.; Jordan, Michael I.; Weiss, Yair (2001). On Spectral Clustering: Analysis and an algorithm (PDF). Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic (англ.): 849—856. doi:10.5555/2980539.2980649. {{}}: Перевірте значення |doi= ()
12. Affinity Matrix(англ.)
13. Peluffo, D.; López, D. F.; Rodríguez, J. L. (2010). Affinity matrix selection for spectral clustering (PDF). XV Symposium of Image, Signal Processing, and Artificial Vision (STSIVA) (англ.).
14. von Luxburg, Ulrike (2007). A Tutorial on Spectral Clustering (PDF). Statistics and Computing (англ.). 17 (4): 395—416. doi:10.1007/s11222-007-9033-z.
15. Хасті,Тібширані,Фрідман, 2020, с. 574.
16. Хасті,Тібширані,Фрідман, 2020, с. 575.
17. Dhillon, I.; Guan, Y.; Kulis, B. (2004). A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts (PDF). University of Texas Dept. of Computer Science (англ.) (TR-04-25).
18. Roxborough, Tom; Sen, Arunabha (1997). [Graph Clustering Using Multiway Ratio Cut (PDF). Graph Drawing, 5th International Symposium (англ.): 291—296. doi:10.1007/3-540-63938-1_71.
19. Graph Theory(англ.)
20. Pentney, William; Meila, Marina (2005). Spectral Clustering of Biological Sequence Data (PDF). Proceedings of the national conference on artificial intelligence (англ.). 20: 845—850.
21. Spectral clustering for image segmentation(англ.)
22. Алгоритми сегментації напівтонових зображень для систем комп'ютерного зору
23. Huang, Grace; Benos, Panayotis (2013). Spectral clustering strategies for heterogeneous disease expression data. Pac Symp Biocomput (англ.): 212—223.
24. When to use spectral clustering(англ.)
25. Practical 2: Cluster Detection(англ.)
26. Comparing different clustering algorithms on toy datasets(англ.)
27. Using Internal Validity Measures to Compare Clustering Algorithms(англ.)
28. K-means and Spectral Clustering (англ.)
29. sklearn.cluster.SpectralClustering
30. dask_ml.cluster.SpectralClustering
31. kernlab: Kernel-Based Machine Learning Lab(англ.)
32. SpectralClustering.jl(англ.)
33. spectral_cluster.h
34. spectralcluster(англ.)
35. Tip: Spectral Clustering in SAS Enterprise Miner Using Open Source Integration Node(англ.)

Література

• ^[en], ^[en], ^[en]. Основы статистического обучения: интеллектуальный анализ данных, логический вывод и прогнозирование. — 2-е изд. — Київ : «Діалектика-Вільямс», 2020. — 768 с. — .
• Bolla M. Spectral Clustering and Biclustering: Learning Large Graphs and Contingency Tables. — 1. — Wiley, 2013. — 292 с. — .
• Liu J., Han J. Spectral Clustering // Data clustering: Algorithms and Applications. — 1. — New York : Chapman and Hall, 2014. — 652 с. — .

Ця стаття належить до української Вікіпедії.