Машинное обучение 2, лекция 6 — иерархическая и спектральная кластеризация

Курс «Машинное обучение 2», ПМИ ФКН ВШЭ

Лектор — Евгений Соколов

[aynurmukhambetova]

III
ИЕРАРХИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ
3:12 – агломеративная кластеризация
Функции расстояния на кластерах:
6:12 – single linkage (и дендрограмма)
12:24 – complete linkage
15:05 – group average

IV
ГРАФОВАЯ КЛАСТЕРИЗАЦИЯ 17:33
Способы задания графов (полный граф 18:24,  kNN-граф 19:11,  эпсилон-граф 20:10)

1. Связные компоненты 20:50

2. Минимальное остовное дерево (алгоритм Краскала) 23:41

3. Спектральная кластеризация 32:50
Идея
34:58 – ratio cut (связь со спектральной кластеризацией 1:15:34)
Математика
41:55 – Лапласиан графа и его свойства (44:58, 45:13)
48:03 – Теорема
51:05 – Доказательство (51:05 K = 1, 1:00:14 K > 1)
Кластеризация
1:04:28 – гипотеза
1:07:09 – алгоритм спектральной кластеризации

[ai-username]

Иерархическая кластеризация 0:41
Функции расстояния на кластерах 7:00
1)7:27 - single linkage
10:20 - дендрограммы
2)12:10 - complete linkage
3)15:10 - group average

Графовые методы 17:40
18:30 - подходы задания ребер
1)21:00 - метод связных компонент
2)23:32 - минимальное остовное дерево
3)Спектральная кластеризация 33:00
--35:10 - ratio cut функционал (1:14:35 связь с лапласианом)
--Лапласиан графа 42:00
--Свойства лапласиана:
--1)44:00 - как можно расписать двустороннее произведение произвольного вещественного вектора и лапласиана
--2)45:30 - симметричность и неотрицательная определенность
--3)Теорема о нулевом собственном значении лапласиана
----48:18 - формулировка
----51:00 - доказательство
--1:04:25 - гипотеза, у собственных векторов, соответствующих маленьким собственным значениям, для похожих объектов соответствующие компоненты равны
--1:07:01 - алгоритм спектральной кластеризации
--1:10:50 - какой самый трудозатратный шаг алгоритма спектральной кластеризации
--1:12:00 - PCA, UMAP, t-SNE в сравнении со спектральной кластеризацией
--1:14:00 - можно ли на последнем шаге вместо k-means брать другие алгоритмы