Машинное обучение:Кластеризация. Н. Поваров, И. Куралёнок. СПб, 2018.


Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:

Машинное обучение:КластеризацияН. Поваров, И. КуралёнокСПб, 2018 Что будет сегодня про кластеризациюСанкт-Петербург, 2018Н. Поваров, И. Куралёнок2 Что это и зачем Описание нескольких алгоритмов
Что такое кластеризацияСанкт-Петербург, 2018Н. Поваров, И. Куралёнок3Кластерный анализ (англ. cluster analysis): задача разбиения заданной выборки объектов (ситуаций) на подмножества, называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.
КартинкаСанкт-Петербург, 2018Н. Поваров, И. Куралёнок4 Виды кластеризацииСанкт-Петербург, 2018Н. Поваров, И. Куралёнок5Centroid-basedСonnectivity-based Distribution-basedConstraint-based

Виды кластеризацииСанкт-Петербург, 2018Н. Поваров, И. Куралёнок6Centroid-basedСonnectivity-based Distribution-basedConstraint-based Другие классификацииСанкт-Петербург, 2018Н. Поваров, И. Куралёнок7Чёткие/нечёткиеПлоские/иерархические
Другие классификацииСанкт-Петербург, 2018Н. Поваров, И. Куралёнок8Чёткие/нечёткиеПлоские/иерархические Другие классификацииСанкт-Петербург, 2018Н. Поваров, И. Куралёнок9Чёткие/нечёткиеПлоские/иерархические Centroid-basedН. Поваров, И. КуралёнокСанкт-Петербург, 201810 FOREL (сentroid-based)Санкт-Петербург, 2018Н. Поваров, И. Куралёнок11Случайно выбираем точку 𝑥 и объявляем центром массИщем соседей этого центра масс ближе, чем 𝑅 Вычисляем их центр массПовторяем шаги 2-3, пока новый центр масс не совпадет с прежнимПомечаем все точки внутри сферы радиуса 𝑅 вокруг текущего центра масс как очередной кластер и выкидываем их из выборкиПовторяем шаги 1-5, пока не будет кластеризована вся выборка 


Факты о FORELСанкт-Петербург, 2018Н. Поваров, И. Куралёнок12Один параметр!Результат зависит от рандомаДетище советских учёных

k-means (сentroid-based)Санкт-Петербург, 2018Н. Поваров, И. Куралёнок13Выбираем 𝑘 точек и объявляем их центрами массДля каждой точки из выборки ищем ближайший центр масс и относим её к кластеру этого центра массВычисляем новые центры массПовторяем шаги 2-3, пока не сойдётся 

k-means (сentroid-based)Санкт-Петербург, 2018Н. Поваров, И. Куралёнок14 Факты о k-meansСанкт-Петербург, 2018Н. Поваров, И. Куралёнок15Один параметр!Нет гарантий сходимостиМожно использовать mediansА можно использовать medoids

Правило локтя для k-meansСанкт-Петербург, 2018Н. Поваров, И. Куралёнок16Вычисляем сумму квадратов расстояний от точек до центровРисуем графикВыбираем k

Правило локтя для k-meansСанкт-Петербург, 2018Н. Поваров, И. Куралёнок17 Connectivity-basedН. Поваров, И. КуралёнокСанкт-Петербург, 201818 Односвязный (сonnectivity-based)Санкт-Петербург, 2018Н. Поваров, И. Куралёнок19Выбираем случайную точку 𝑥 и кладём её в кластер 𝐶𝑖Ищем соседей 𝑥 ближе, чем 𝜀 и добавляем их в 𝐶𝑖Если соседи кончились, то берём следующую точку из 𝐶𝑖 и проделываем п. 2Если в 𝐶𝑖 больше не добавить точек, то переходим к п. 1 

Факты про односвязный алгоритмСанкт-Петербург, 2018Н. Поваров, И. Куралёнок20 Один параметр! Сложность O(𝑛3) Результат сильно зависит от рандома Можно сделать хитрее, чем односвязный 

DBSCAN (сonnectivity-based)Санкт-Петербург, 2018Н. Поваров, И. Куралёнок21 DBSCAN (сonnectivity-based)Санкт-Петербург, 2018Н. Поваров, И. Куралёнок22Выбираем случайную непосещённую точку Если у неё больше, чем m соседей в радиусе 𝜀, то кладём её в S и создаём новый кластер, иначе помечаем как шумДля каждой точки из S:Если эту точку не посещали, то ищем всех соседей в радиусе 𝜀Если таких соседей больше m, то добавляем их всех в SЕсли точка не в каком либо кластере, то добавляем в текущий кластер 


Факты о DBSCANСанкт-Петербург, 2018Н. Поваров, И. Куралёнок23Два параметра Сложность наивной реализации O(𝑛2)Пограничные точки не детерминировано разбиваютсяМожно ускорить с помощью kd-treeТут есть проклятье размерностиВ 2014 на KDD алгоритм получил «test of time award» 


«Правило локтя» для DBSCANСанкт-Петербург, 2018Н. Поваров, И. Куралёнок24Выбираем mДля каждой точки считаем среднее расстояние до m ближайших соседейСортируем и рисуем графикНа графике выбираем 𝜀 

«Правило локтя» для DBSCANСанкт-Петербург, 2018Н. Поваров, И. Куралёнок25 Интересные примеры DBSCANСанкт-Петербург, 2018Н. Поваров, И. Куралёнок26 Convex-hull & DBSCAN clustering to predict future weather, 2015 Modelling website user behaviors by combining the EM and DBSCAN algorithms, 2016 Real-Time Superpixel Segmentation by DBSCAN Clustering Algorithm, 2016

Метрики качества кластеризацииСанкт-Петербург, 2018Н. Поваров, И. Куралёнок27 Внешние Внутренние
Внешние метрикиСанкт-Петербург, 2018Н. Поваров, И. Куралёнок28 Rand measure = Accuracy F-мера ...

Внутренние метрикиСанкт-Петербург, 2018Н. Поваров, И. Куралёнок29 Вводят внутрикластерное расстояние Вводят межкластерное расстояние Первое хотят минимизировать, второе максимизировать

Внутренние метрикиСанкт-Петербург, 2018Н. Поваров, И. Куралёнок30 Dunn Index Силуэт Davies-Bouldin index ...

ИтогоСанкт-Петербург, 2018Н. Поваров, И. Куралёнок31 Есть разные методы кластеризации Возможно, что от них есть польза Их качество пытаются измерять Интересные ссылкиhttps://distill.pub/2016/misread-tsne/ — построение любых фигур из шума с помощью t-snehttps://www.naftaliharris.com/blog/visualizing-dbscan-clustering/ — можно поиграться с dbscan на разных выборкахhttps://www.naftaliharris.com/blog/visualizing-k-means-clustering/ — там же можно посмотреть на работу k-meansН. Поваров, И. КуралёнокСанкт-Петербург, 201832

Приложенные файлы

  • pptx 26548078
    Размер файла: 5 MB Загрузок: 0

Добавить комментарий