Спектральна кластеризація: відмінності між версіями

Інтерактивний перегляд історії

(Переглянути усі неперевірені зміни)

[перевірена версія]

← Попереднє редагування Наступне редагування →

Вилучено вміст Додано вміст

ВізуальнийВікірозмітка

Лінійно

Версія за 22:07, 4 березня 2023

Спектральна кластеризація — метод кластеризації, заснований на концепції зв'язності графів^[en]. На відміну від інших методів, таких як к-середніх, що шукають щільні, компактні, опуклі кластери, спектральна кластеризація може знаходити кластери довільної форми. Метод був розроблений у 1970-х для розділення графів, і пізніше був багатократно покращений і застосований для ширшого класу задач. Ідея методу полягає в тому щоб, розглядаючи множину спостережень як зважений граф (де кожному спостереженню відповідає вершина, а ребра мають вагу, що дорівнює подібності пари спостережень), з одного боку, знайти мінімальний розріз такого графа, а з іншого — щоб отримані два підграфи були близькі за розміром. Назву метод отримав через те що він ґрунтується на аналізі спектру графа — множини власних значень його матриці суміжності. Спектральна кластеризація — один з найпотужніших сучасних методів кластеризації, і може бути застосований у будь-яких задачах кластерного аналізу, в тому числі таких як сегментація зображення, аналіз експресії генів, графів соціальних мереж, тощо.

Історія

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

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

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

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

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

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

Алгоритм

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

Для представлення всіх спостережень у вигляді графа, потрібно визначити функцію подібності. Ця функція має бути невід'ємною і симетричною. Подібність велика для близьких точок і прямує до нуля для далеких. У випадку якщо максимальна подібність дорівнює 1, вона може бути інтерпретована як ймовірність того, що спостереження відносяться до одного кластеру^[12]. Для потреб алгоритму, подібність точок самих собі зануляється: $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-тим найближчим сусідом^[13].

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

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

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

Тільки якщо відстань між відповідними точками є меншою за деяку величину $d_{ij}\leq \varepsilon$
Тільки якщо точка $i$ входить до k найближчих сусідів точки $j$ або ж точка $j$ входить до k найближчих сусідів точки $i$
Тільки якщо точка $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}$ ^[8]. Іншим способом нормалізації лапласіана є $L=I-DW$ ^[15].

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

В будь-якому випадку, після обчислення лапласіана (нормалізованого або ні) необхідно обчислити його власні числа і власні вектори.

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

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

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

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

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

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

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

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|

кількість вершин у отриманих кластерах^[7].

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

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}

сумарна вага усіх ребер, які виходять з вершин кластера А (включаючи ті, які з'єднують його з іншими кластерами)^[8].

MinMaxCut: мінімізується величина

Rmm(U,V)=cut(U,V)\left({\frac {1}{d_{U}-cut(U,V)}}+{\frac {1}{d_{V}-cut(U,V)}}\right)

, тобто, у знаменнику на відміну від NormalCut стоїть сума ваг лише тих ребер, які з'єднують точки всередині кластеру (ребра, що сполучають різні кластери не враховуються)^[9].

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

Уявімо, що ми маємо зважений граф 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

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

Вираз вище пов'язаний з ненормалізованим лапласіаном графу як^[19]:

\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^[19]. Отже, всі компоненти першого вектора дорівнюють $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$ може бути розписаний у базисі власних векторів^[19]

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}$ , ми можемо записати, що^[19]

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$ дорівнює другому найменшому власному вектору^[19].

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

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

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

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

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

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

Незважаючи на значні переваги, спектральна кластеризація має і кілька недоліків^[22]:

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

Відмінності від інших алгоритмів кластеризації

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

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

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

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

Спектральна кластеризація включена в пакет Scikit-learn, написаний мовою Python^[27]. Мовою R алгоритм реалізовано в пакеті kernlab^[28].

Примітки

↑ Hall, Kenneth M. (1970). An r-Dimensional Quadratic Placement Algorithm. Management Science (англ.). 17 (3): 219—229.
↑ Essential spectral theory, Hall’s spectral graph drawing, the Fiedler value(англ.)
↑ ^а ^б ^в ^г ^д ^е ^ж 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.
↑ 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.
↑ 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.
↑ Guattery, Stephen; Miller, Gary L. (1995). On the Performance of Spectral Graph Partitioning Methods (PDF). ACM-SIAM Symposium on Discrete Algorithms (англ.): 233—242.
↑ ^а ^б 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.
↑ ^а ^б ^в 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.
↑ ^а ^б 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.
↑ ^а ^б 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. {{cite journal}}: Перевірте значення |doi= (довідка)
↑ ^а ^б ^в 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. {{cite journal}}: Перевірте значення |doi= (довідка)
↑ Affinity Matrix(англ.)
↑ 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) (англ.).
↑ ^а ^б ^в ^г ^д ^е von Luxburg, Ulrike (2007). A Tutorial on Spectral Clustering (PDF). Statistics and Computing (англ.). 17 (4): 395—416. doi:10.1007/s11222-007-9033-z.
↑ Хасті,Тібширані,Фрідман, 2020, с. 574.
↑ ^а ^б ^в Хасті,Тібширані,Фрідман, 2020, с. 575.
↑ 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).
↑ 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.
↑ ^а ^б ^в ^г ^д Graph Theory(англ.)
↑ Pentney, William; Meila, Marina (2005). Spectral Clustering of Biological Sequence Data (PDF). Proceedings of the national conference on artificial intelligence (англ.). 20: 845—850.
↑ Spectral clustering for image segmentation(англ.)
↑ When to use spectral clustering(англ.)
↑ Practical 2: Cluster Detection(англ.)
↑ Comparing different clustering algorithms on toy datasets(англ.)
↑ Using Internal Validity Measures to Compare Clustering Algorithms(англ.)
↑ K-means and Spectral Clustering (англ.)
↑ sklearn.cluster.SpectralClustering
↑ kernlab: Kernel-Based Machine Learning Lab(англ.)

Література

Хасті Т., Тібширані Р., Фрідман Дж. Основы статистического обучения. — 2. — Київ : «Діалектика», 2020. — 768 с. — ISBN 978-617-7812-91-2.

[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(англ.)

[spel-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.

[vlsicad-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.

[malik-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.

[minmax-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.

[randomwalk-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. {{cite journal}}: Перевірте значення |doi= (довідка)

[nips01-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. {{cite journal}}: Перевірте значення |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) (англ.).

[luxburg-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.

[FOOTNOTEХасті,Тібширані,Фрідман2020574-15] Хасті,Тібширані,Фрідман, 2020, с. 574.

[FOOTNOTEХасті,Тібширані,Фрідман2020575-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.

[wyss-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] When to use spectral clustering(англ.)

[23] Practical 2: Cluster Detection(англ.)

[24] Comparing different clustering algorithms on toy datasets(англ.)

[25] Using Internal Validity Measures to Compare Clustering Algorithms(англ.)

[26] K-means and Spectral Clustering (англ.)

[27] sklearn.cluster.SpectralClustering

[28] rnlab: Kernel-Based Machine Learning Lab(англ.)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

@@ Рядок 2: / Рядок 2: @@
 == Історія ==
-Ідея спектральної кластеризації ґрунтується на роботах Кеннета Холла, у якій він шукав спосіб спроєктувати граф на числову пряму і загалом, у багатовимірний [[евклідів простір]], і запропонував використовувати для цього власні вектори матриці Лапласа<ref>[https://www.jstor.org/stable/2629091 An r-Dimensional Quadratic Placement Algorithm ]{{ref-en}}</ref><ref>[https://www.cs.yale.edu/homes/spielman/561/lect02-18.pdf Essential spectral theory, Hall’s spectral graph drawing, the Fiedler value]{{ref-en}}</ref><ref name="spel">[https://www.sciencedirect.com/science/article/pii/S0024379506003454 Spectral partitioning works: Planar graphs and finite element meshes]{{ref-en}}</ref> а також Доната і Хоффмана, які помітили, що власні вектори модифікованої матриці зв'язності можна застосувати для задачі [[розбиття графа]] на рівні частини<ref>[https://www.kde.cs.uni-kassel.de/mediawiki/images/7/70/Ibm_tdb_15-3_1972_donath-hoffman.pdf Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices]{{ref-en}}</ref><ref name="spel"/>. У 1973-1975 роках чеський математик {{не перекладено|Мирослав Фідлер|||Miroslav Fiedler }} показав, що найменше ненульове власне значення графа Лапласа відповідає його зв'язності і показав зв'язок відповідного власного вектора і породжуваної ним кластеризації у загальному випадку (результати Доната і Хоффмана стосувалися деяких специфічних типів графів)<ref name="spel"/><ref>[https://dml.cz/bitstream/handle/10338.dmlcz/101357/CzechMathJ_25-1975-4_12.pdf A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory]{{ref-en}}</ref>. Вклад Фідлера в спектральну теорію графів є значним, тому найменше ненульове власне значення вектора Лапласа називається ''числом Фідлера'', а відповідний вектор — ''вектором Фідлера''. Пізніше було показано, що графи з маленьким числом Фідлера мають маленьке співвідношення кількості видалених ребер до кількості розділяємих вершин, що відповідає уявленню про "хорошу" кластеризацію<ref name="spel"/>.
+Ідея спектральної кластеризації ґрунтується на роботах Кеннета Холла, у якій він шукав спосіб спроєктувати граф на числову пряму і загалом, у багатовимірний [[евклідів простір]], і запропонував використовувати для цього власні вектори матриці Лапласа<ref>{{cite journal|last1=Hall|first1=Kenneth M.|date=1970|title=An r-Dimensional Quadratic Placement Algorithm|url=https://www.jstor.org/stable/2629091|language=en|journal=Management Science|volume=17|issue=3|pages=219-229}}</ref><ref>[https://www.cs.yale.edu/homes/spielman/561/lect02-18.pdf Essential spectral theory, Hall’s spectral graph drawing, the Fiedler value]{{ref-en}}</ref><ref name="spel">{{cite journal|last1=Spielman|first1=Daniel A.|last2=Teng|first2=Shang-Hua|date=2007|title=Spectral partitioning works: Planar graphs and finite element meshes|url=https://www.sciencedirect.com/science/article/pii/S0024379506003454|language=en|journal=Linear Algebra and its Applications|volume=421|issue=2-3|pages=284-305|doi=10.1016/j.laa.2006.07.020}}</ref> а також Доната і Хоффмана, які помітили, що власні вектори модифікованої матриці зв'язності можна застосувати для задачі [[розбиття графа]] на рівні частини<ref>{{cite journal|last1=Donath|first1=W.|last2=Hoffman|first2=A.|date=1972|title=Algorithms for partitioning of graphs and computer logic based on eigenvectors of connection matrices|url=https://www.kde.cs.uni-kassel.de/mediawiki/images/7/70/Ibm_tdb_15-3_1972_donath-hoffman.pdf|language=en|journal=IBM Technical Disclosure Bulletin|volume=15|issue=3|pages=938-944}}</ref><ref name="spel"/>. У 1973-1975 роках чеський математик {{не перекладено|Мирослав Фідлер|||Miroslav Fiedler }} показав, що найменше ненульове власне значення графа Лапласа відповідає його зв'язності і показав зв'язок відповідного власного вектора і породжуваної ним кластеризації у загальному випадку (результати Доната і Хоффмана стосувалися деяких специфічних типів графів)<ref name="spel"/><ref>{{cite journal|last1=Fiedler|first1=Miroslav|date=1975|title=A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory|url=https://dml.cz/bitstream/handle/10338.dmlcz/101357/CzechMathJ_25-1975-4_12.pdf|language=en|journal=Czechoslovak Mathematical Journal|volume=25|issue=4|pages=619–633}}</ref>. Вклад Фідлера в спектральну теорію графів є значним, тому найменше ненульове власне значення вектора Лапласа називається ''числом Фідлера'', а відповідний вектор — ''вектором Фідлера''. Пізніше було показано, що графи з маленьким числом Фідлера мають маленьке співвідношення кількості видалених ребер до кількості розділяємих вершин, що відповідає уявленню про "хорошу" кластеризацію<ref name="spel"/>.
 Використання алгоритму стримувалося важкістю задачі знаходження власних векторів і значень, допоки у 80-х роках не з'явилися більш ефективні рішення, такі як {{не перекладено|алгоритм Ланчоса|||Lanczos algorithm }}, і багато експериментів на реальних графах показали практичну придатність методу<ref name="spel"/>.
 [[Файл:Roach graph.png|міні|"Тарганячій граф" з роботи Міллера і Гваттарі. Наївна спектральна кластеризація пропонує розділити граф навпіл за вертикальною лінією (розриваючи к зв'язків) замість того щоб розділити його за горизонтальною, розриваючи лише два зв'язки.]]
-Спектральна кластеризація швидко стала популярною і стандартом у багатьох галузях, проте у 1995 році Міллер і Гваттарі привернули увагу до дивної поведінки алгоритму на деяких типах графів<ref name="spel"/>. Використаний Фідлером підхід, згідно з яким два кластери графа визначалися за тим, більше чи менше нуля відповідні компоненти вектора Фідлера (наївна бісекція) давав очевидно неправильну кластеризацію на графах, що могли зустрітися в реальному житті<ref name="spel"/>. Також у роботі було запропоновано використовувати не лише вектор Фідлера для розділення, але і ще кілька найменших ненульових власних векторів<ref>[https://www.cs.cmu.edu/~glmiller/Publications/Papers/GuMi95.pdf On the Performance of Spectral Graph Partitioning Methods]{{ref-en}}</ref>.
+Спектральна кластеризація швидко стала популярною і стандартом у багатьох галузях, проте у 1995 році Міллер і Гваттарі привернули увагу до дивної поведінки алгоритму на деяких типах графів<ref name="spel"/>. Використаний Фідлером підхід, згідно з яким два кластери графа визначалися за тим, більше чи менше нуля відповідні компоненти вектора Фідлера (наївна бісекція) давав очевидно неправильну кластеризацію на графах, що могли зустрітися в реальному житті<ref name="spel"/>. Також у роботі було запропоновано використовувати не лише вектор Фідлера для розділення, але і ще кілька найменших ненульових власних векторів<ref>{{cite journal|last1=Guattery|first1=Stephen|last2=Miller|first2=Gary L.|date=1995|title=On the Performance of Spectral Graph Partitioning Methods|url=http://web.mit.edu/6.454/www/www_fall_2004/lldai/Guattery.pdf|language=en|journal=ACM-SIAM Symposium on Discrete Algorithms|volume= |pages=233-242}}</ref>.
-Також, велися пошуки оптимального значення для розділення вектора Фідлера (замість нуля). У 1992 році у роботі Ларса Хагена і Ендрю Канга був запропонований новий підхід для оцінки, Ratio-Cut, який дозволив краще знаходити кластери неоднакового розміру<ref name="vlsicad">[https://vlsicad.ucsd.edu/Publications/Journals/j5.pdf New spectral methods for ratio cut partitioning and clustering]{{ref-en}}</ref>, а в 2000 році Цзяньбо Ши і {{не перекладено|Джитендра Малик|Джитендра Малик||Jitendra Malik }} запропонували ще одну метрику якості кластеризації, і показали що для пошуку найкращого розрізу за нею необхідно модифікувати матрицю Лапласа. Така модифікована матриця отримала назву ''нормалізований лапласіан'', а сам метод отримав назву Normal-Cut(або NCut)<ref name="malik">[https://people.eecs.berkeley.edu/~malik/papers/SM-ncut.pdf Normalized Cuts and Image Segmentation]{{ref-en}}</ref>. В 2001 році був запропонований MinMaxCut<ref name="minmax">[https://escholarship.org/content/qt0g18c027/qt0g18c027_noSplash_8499f8f1cae35b5dca6a05cc04184b77.pdf?t=p0lm2h A min-max cut algorithm for graph partitioning and data clustering]{{ref-en}}</ref>.
+Також, велися пошуки оптимального значення для розділення вектора Фідлера (замість нуля). У 1992 році у роботі Ларса Хагена і Ендрю Канга був запропонований новий підхід для оцінки, Ratio-Cut, який дозволив краще знаходити кластери неоднакового розміру<ref name="vlsicad">{{cite journal|last1=Hagen|first1=Lars|last2=Kahng|first2=Andrew B. |date=1992|title=New spectral methods for ratio cut partitioning and clustering|url=https://vlsicad.ucsd.edu/Publications/Journals/j5.pdf|language=en|journal=IEEE Transactions on Computer-Aided Design|volume=11|issue=9|pages=1074-1085}}</ref>, а в 2000 році Цзяньбо Ши і {{не перекладено|Джитендра Малик|Джитендра Малик||Jitendra Malik }} запропонували ще одну метрику якості кластеризації, і показали що для пошуку найкращого розрізу за нею необхідно модифікувати матрицю Лапласа. Така модифікована матриця отримала назву ''нормалізований лапласіан'', а сам метод отримав назву Normal-Cut(або NCut)<ref name="malik">{{cite journal|last1=Shi|first1=Jianbo|last2=Malik|first2=Jitendra|date=2000|title=Normalized Cuts and Image Segmentation|url=https://people.eecs.berkeley.edu/~malik/papers/SM-ncut.pdf|language=en|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=22|issue=8|pages=888 – 905|doi=10.1109/34.868688}}</ref>. В 2001 році був запропонований MinMaxCut<ref name="minmax">{{cite journal|last1=Ding|first1=Chris|last2=Xiaofeng|first2=He|last3=Hongyuan|first3=Zha|date=2001|title=A min-max cut algorithm for graph partitioning and data clustering|url=https://escholarship.org/content/qt0g18c027/qt0g18c027_noSplash_8499f8f1cae35b5dca6a05cc04184b77.pdf?t=p0lm2h|language=en|journal=Proceedings 2001 IEEE International Conference on Data Mining|volume= |pages=107–114|doi=10.1109/ICDM.2001.989507}}</ref>.
-В 2001 році Цзяньбо Ши і Марина Мейла запропонували нову інтерпретацію спектральної кластеризації за методом NCut: при марківському [[Випадкове блукання|випадковому блуканні]] по графу, кластеризація виділяє такі компоненти, переходи між якими відбуваються якнайрідше<ref name="randomwalk">[https://www.ri.cmu.edu/pub_files/pub3/maila_marina_2001_1/maila_marina_2001_1.pdf Learning Segmentation by Random Walks]{{ref-en}}</ref>.
+В 2001 році Цзяньбо Ши і Марина Мейла запропонували нову інтерпретацію спектральної кластеризації за методом NCut: при марківському [[Випадкове блукання|випадковому блуканні]] по графу, кластеризація виділяє такі компоненти, переходи між якими відбуваються якнайрідше<ref name="randomwalk">{{cite journal|last1=Meila|first1=Marina|last2=Shi|first2=Jianb|date=2000|title=Learning Segmentation by Random Walks|url=https://www.ri.cmu.edu/pub_files/pub3/maila_marina_2001_1/maila_marina_2001_1.pdf|language=en|journal=Advances in Neural Information Processing Systems 13 (NIPS 2000)|volume= |pages=837–843|doi=10.5555/3008751.3008873}}</ref>.
-Того ж року [[Ендрю Ин]], Майкл Джордан і Яїр Вайс запропонували використовувати [[Кластеризація методом к–середніх|кластеризацію к-середніх]] на просторі, утвореному власними векторами. Важливою зміною в їх підході є те, що використовуються власні вектори, що відповідають найбільшим, а не найменшим власним значенням, а також використовується спеціальна форма лапласіана <ref name="nips01">[https://ai.stanford.edu/~ang/papers/nips01-spectral.pdf On Spectral Clustering: Analysis and an algorithm]{{ref-en}}</ref>. Метод Ина-Джордана-Вайса завоював популярність, і часто згадується як ''NJW-алгоритм''.
+Того ж року [[Ендрю Ин]], Майкл Джордан і Яїр Вайс запропонували використовувати [[Кластеризація методом к–середніх|кластеризацію к-середніх]] на просторі, утвореному власними векторами. Важливою зміною в їх підході є те, що використовуються власні вектори, що відповідають найбільшим, а не найменшим власним значенням, а також використовується спеціальна форма лапласіана <ref name="nips01">{{cite journal|last1=Ng|first1=Andrew Y.|last2=Jordan|first2=Michael I. |last3=Weiss|first3=Yair|date=2001|title=On Spectral Clustering: Analysis and an algorithm|url=https://ai.stanford.edu/~ang/papers/nips01-spectral.pdf|language=en|journal=Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic|volume= |pages=849–856|doi=10.5555/2980539.2980649}}</ref>. Метод Ина-Джордана-Вайса завоював популярність, і часто згадується як ''NJW-алгоритм''.
 == Алгоритм ==
@@ Рядок 28: / Рядок 28: @@
 або його нормалізований варіант:
 :<math>w_{ij}=e^{-d_{ij}^2 / \sigma_i \sigma_j} </math>,
-де <math>\sigma_i</math> — відстань між точкою <math>x_i</math> та її n-тим найближчим сусідом<ref>[https://www.diegopeluffo.com/publicaciones/STSIVA2010.pdf Affinity matrix selection for spectral clustering]{{ref-en}}</ref>.
+де <math>\sigma_i</math> — відстань між точкою <math>x_i</math> та її n-тим найближчим сусідом<ref>{{cite journal|last1=Peluffo|first1=D.|last2=López|first2=D. F.|last3=Rodríguez|first3=J. L.|date=2010|title=Affinity matrix selection for spectral clustering|url=https://www.diegopeluffo.com/publicaciones/STSIVA2010.pdf|language=en|journal=XV Symposium of Image, Signal Processing, and Artificial Vision (STSIVA)}}</ref>.
-У окремих випадках можуть використовуватися більш специфічні міри близькості, такі як [[коефіцієнт Жаккара]] або [[косинус подібності]].
+У окремих випадках можуть використовуватися більш специфічні міри близькості, такі як [[коефіцієнт Жаккара]] або [[косинус подібності|косинусна подібність]].
 Попарні подібності між точками формують ''матрицю подібності'' ({{lang-en|Affinity matrix}}) яка позначається як <math>W</math>.
-Таку матрицю можна вважати [[Матриця суміжності|матрицею суміжності]] зваженого [[Повний граф|повного графа]] (тобто, такого де ребра існують між будь-якими двома вершинами), а можна занулити деякі з елементів, зменшуючи кількість ребер. Існує кілька підходів до того, які ребра залишати<ref name="luxburg">[https://people.csail.mit.edu/dsontag/courses/ml14/notes/Luxburg07_tutorial_spectral_clustering.pdf A Tutorial on Spectral Clustering]{{ref-en}}</ref>:
+Таку матрицю можна вважати [[Матриця суміжності|матрицею суміжності]] зваженого [[Повний граф|повного графа]] (тобто, такого де ребра існують між будь-якими двома вершинами), а можна занулити деякі з елементів, зменшуючи кількість ребер. Існує кілька підходів до того, які ребра залишати<ref name="luxburg">{{cite journal|last1=von Luxburg|first1=Ulrike|date=2007|title=A Tutorial on Spectral Clustering|url=https://people.csail.mit.edu/dsontag/courses/ml14/notes/Luxburg07_tutorial_spectral_clustering.pdf|language=en|journal=Statistics and Computing|volume=17|issue=4|pages=395-416|doi=10.1007/s11222-007-9033-z}}</ref>:
 # Тільки якщо відстань між відповідними точками є меншою за деяку величину <math>d_{ij} \le\varepsilon</math>
 # Тільки якщо точка <math>i</math> входить до k найближчих сусідів точки <math>j</math> ''або ж'' точка <math>j</math> входить до k найближчих сусідів точки <math>i</math>
@@ Рядок 61: / Рядок 61: @@
 === Цільові функції кластеризації ===
-Існує кілька підходів оцінювання кластеризації<ref>[https://people.bu.edu/bkulis/pubs/spectral_techreport.pdf A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts]{{ref-en}}</ref>:
+Існує кілька підходів оцінювання кластеризації<ref>{{cite journal|last1=Dhillon|first1=I.|last2=Guan|first2=Y.|last3=Kulis|first3=B.|date=2004|title=A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts|url=https://people.bu.edu/bkulis/pubs/spectral_techreport.pdf|language=en|journal=University of Texas Dept. of Computer Science|issue=TR-04-25}}</ref>:
 * RatioCut: шукається таке розділення на два підграфи <math>U</math> і <math>V</math>, що мінімізується величина
 :<math>Rratio(U,V) = cut(U, V)(1 / |U| + 1 / |V|)</math> або <math>\frac{cut(U, V)}{|U|\cdot|V|}</math>, де <math>cut(U, V)</math> — сумарна вага зв'язків що розриваються, а <math>|U|, |V|</math> кількість вершин у отриманих кластерах<ref name="vlsicad"/>.
-Цей принцип може бути розширений і на випадок більше ніж кластерів<ref>[https://link.springer.com/content/pdf/10.1007/3-540-63938-1_71.pdf Graph Clustering Using Multiway Ratio Cut]{{ref-en}}</ref>:
+Цей принцип може бути розширений і на випадок більше ніж двох кластерів<ref>{{cite journal|last1=Roxborough|first1=Tom|last2=Sen|first2=Arunabha|date=1997|title=Graph Clustering Using Multiway Ratio Cut|url=[https://link.springer.com/content/pdf/10.1007/3-540-63938-1_71.pdf|language=en|journal=Graph Drawing, 5th International Symposium|pages=291-296|doi=10.1007/3-540-63938-1_71}}</ref>:
 :<math>Rratio(V_1, V_2, ..., V_n) = \frac{cut(V_1, V_2, ..., V_n)}{|V_1|\cdot|V_2|\cdot...\cdot|V_n|}</math>
@@ Рядок 120: / Рядок 120: @@
 == Застосування ==
-Спектральну кластеризацію вважається одним найбільш прогресивних і популярних методів кластеризації, завдяки універсальності (здатності працювати з багатовимірними даними і обробляти категоріальні ознаки) і можливості знаходити кластери довільної форми. Вона знаходить застосування в біології (аналіз експресії [[ген]]ів), соціології, психології, обробці зображень (виділення об'єктів на зображенні)<ref name="luxburg"/><ref>[https://www.aaai.org/Papers/AAAI/2005/AAAI05-133.pdf Spectral Clustering of Biological Sequence Data]</ref><ref>[https://scikit-learn.org/stable/auto_examples/cluster/plot_segmentation_toy.html Spectral clustering for image segmentation]{{ref-en}}</ref>.
+Спектральну кластеризацію вважається одним найбільш прогресивних і популярних методів кластеризації, завдяки універсальності (здатності працювати з багатовимірними даними і обробляти категоріальні ознаки) і можливості знаходити кластери довільної форми. Вона знаходить застосування в біології (аналіз експресії [[ген]]ів), соціології, психології, обробці зображень (виділення об'єктів на зображенні)<ref name="luxburg"/><ref>{{cite journal|last1=Pentney|first1=William|last2=Meila|first2=Marina|date=2005|title=Spectral Clustering of Biological Sequence Data|url=https://www.aaai.org/Papers/AAAI/2005/AAAI05-133.pdf|language=en|journal=Proceedings of the national conference on artificial intelligence|volume=20|pages=845-850}}</ref><ref>[https://scikit-learn.org/stable/auto_examples/cluster/plot_segmentation_toy.html Spectral clustering for image segmentation]{{ref-en}}</ref>.
 При використанні алгоритму, користувач має визначити наступні параметри:

Спектральна кластеризація: відмінності між версіями

Версія за 22:07, 4 березня 2023

Зміст

Історія

Алгоритм

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

Обчислення власних векторів лапласіана

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

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

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

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

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

Відмінності від інших алгоритмів кластеризації

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

Примітки

Література

Навігаційне меню

Спектральна кластеризація: відмінності між версіями

Версія за 22:07, 4 березня 2023

Історія

Алгоритм

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

Обчислення власних векторів лапласіана

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

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

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

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

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

Відмінності від інших алгоритмів кластеризації

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

Примітки

Література

Навігаційне меню

Пошук