Методы кластеризации - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Методы кластеризации. Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Методы кластеризации Лекция 16

Слайд 2

Описание слайда:

План лекции Введение Формальная постановка задачи Метод k-средних Метод ISODATA Агломеративный метод Дивизимный метод

Слайд 3

Описание слайда:

Введение Задача кластеризации состоит в разделении исследуемого множества объектов на группы «похожих» объектов, называемых кластерами Решение задачи кластеризации называют кластерным анализом

Слайд 4

Описание слайда:

Введение Кластеризация отличается от классификации тем, что этап обучения на примерах отсутствует В задачах классификации множество классов заранее известно, в кластеризации классы определяются в процессе анализа Поэтому кластеризация относится к задачам обучения без учителя (unsupervised learning)

Слайд 5

Описание слайда:

Введение Эта задача решается на начальных этапах исследования, когда о данных мало что известно Ее решение помогает лучше понять данные После определения кластеров применяются другие методы Data Mining, чтобы попытаться установить, что означает такое разбиение

Слайд 6

Описание слайда:

Введение Кластерный анализ позволяет рассматривать достаточно большой объем информации и сжимать большие массивы информации, делать их компактными и наглядными

Слайд 7

Описание слайда:

Формальная постановка задачи Дано множество данных, состоящее из N объектов (векторов): S1, S2, …, SN Каждый объект описывается набором признаков: x1, x2, …, xm, где m – размерность пространства признаков

Слайд 8

Описание слайда:

Формальная постановка задачи Таким образом, i-й объект можно записать в виде: Si = (xi1, xi2, …, xim) Класс для каждого объекта неизвестен

Слайд 9

Описание слайда:

Формальная постановка задачи Требуется: найти способ сравнения d(Sp, Sq) объектов между собой (меру сходства, функцию расстояния) определить множество кластеров С1, C2, …, Cr причем количество кластеров r – неизвестно разбить данные по кластерам

Слайд 10

Описание слайда:

Формальная постановка задачи В качестве меры сходства используются: евклидово расстояние квадрат евклидова расстояния расстояние Хэмминга расстояние Чебышева

Слайд 11

Описание слайда:

Формальная постановка задачи Методы кластерного анализа можно разделить на две группы: неиерархические иерархические

Слайд 12

Описание слайда:

Метод k-средних Неиерархическим методом кластеризации является метод k-средних (k-means) Предварительно необходимо выбрать вероятное число кластеров k

Слайд 13

Описание слайда:

Метод k-средних 1. Выбирается k произвольных исходных центров кластеров – обычно выбираются k объектов 2. Все объекты разбиваются на k групп, наиболее близких к одному из центров 3. Вычисляются новые центры кластеров 4. Проводится новое разбиение всех объектов на основании близости к новым центрам Шаги 3 и 4 повторяются до тех пор, пока центры кластеров не перестанут меняться или пока не достигнуто максимальное число итераций

Слайд 14

Описание слайда:

Метод k-средних Выбор числа кластеров является сложным вопросом Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т. д., сравнивая полученные результаты

Слайд 15

Описание слайда:

Метод k-средних Начальный выбор центров кластеров осуществляется следующим образом: выбор k объектов для максимизации начального расстояния случайный выбор k объектов выбор первых k объектов

Слайд 16

Описание слайда:

Метод k-средних Центры кластеров вычисляются по формулам: … где NC – количество объектов, входящих в кластер С

Слайд 17

Описание слайда:

Метод k-средних Пример.

Слайд 18

Описание слайда:

Метод k-средних Пример.

Слайд 19

Описание слайда:

Метод k-средних

Слайд 20

Описание слайда:

Метод k-средних

Слайд 21

Описание слайда:

Метод k-средних

Слайд 22

Описание слайда:

Метод k-средних

Слайд 23

Описание слайда:

Метод ISODATA ISODATA – Iterative Self-Organizing Data Analysis Techniques – итеративный самоорганизующийся метод анализа данных Более сложный алгоритм, чем k-means, дополненный несколькими эвристиками Полное описание см. Ту Дж., Гонсалес Р. «Принципы распознавания образов», М.: Мир, 1978

Слайд 24

Описание слайда:

Метод ISODATA Если в кластер входит менее заданного минимального числа объектов, кластер удаляется Если среднее расстояние между объектами кластера больше заданного максимального порога, кластер расщепляется на два новых кластера

Слайд 25

Описание слайда:

Метод ISODATA Если расстояние между центрами двух кластеров меньше заданного минимального порога, кластеры сливаются В алгоритме ISODATA множество параметров, настройка которых представляет определенные трудности

Слайд 26

Описание слайда:

Иерархические методы К иерархическим методам кластеризации относятся: агломеративный алгоритм (Agglomerative Nesting, AGNES) дивизимный алгоритм (Divisive ANAlysis, DIANA)

Слайд 27

Описание слайда:

Агломеративный метод В начале работы алгоритма все объекты являются отдельными кластерами На первом шаге наиболее похожие (близкие) два кластера объединяются в дин кластер На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер На любом этапе объединение можно прервать, получив нужное число кластеров

Слайд 28

Описание слайда:

Агломеративный метод Расстояние между кластерами можно определить различными способами: расстояние между центрами кластеров расстояние между двумя наиболее близкими объектами в кластерах расстояние между двумя наиболее дальними объектами в кластерах среднее расстояние между всеми парами объектов в них

Слайд 29

Описание слайда:

Агломеративный метод Пример.

Слайд 30

Описание слайда:

Агломеративный метод Выбираем и объединяем два наиболее близких кластера

Слайд 31

Описание слайда:

Агломеративный метод Выбираем и объединяем два наиболее близких кластера

Слайд 32

Описание слайда:

Агломеративный метод Выбираем и объединяем два наиболее близких кластера

Слайд 33

Описание слайда:

Дивизимный метод На первом шаге все объекты помещаются в один кластер С1 Выбирается объект, у которого среднее значение расстояния до других объектов в этом кластере наибольшее:

Слайд 34

Описание слайда:

Дивизимный метод Выбранный объект удаляется из кластера С1 и формирует первый элемент второго кластера С2 На каждом последующем шаге объект в кластере С1, для которого разность между средним расстоянием до объектов, находящихся в С2 и средним расстоянием до объектов, остающихся в С1, наибольшая, переносится в С2

Слайд 35

Описание слайда:

Дивизимный метод Переносы элементов из С1 в С2 продолжаются до тех пор, пока соответствующие разности средних не станут отрицательными, то есть пока существуют элементы, расположенные к элементам кластера С2 ближе, чем к элементам кластера С1

Слайд 36

Описание слайда:

Дивизимный метод В результате один кластер делится на два дочерних, один из которых расщепляется на следующем уровне иерархии Каждый последующий уровень применяет процедуру разделения к одному из кластеров, полученных на предыдущем уровне

Слайд 37

Описание слайда:

Дивизимный метод Кластер для расщепления выбирается, например, по наибольшему диаметру Диаметр кластера – расстояние между двумя наиболее дальними объектами кластера Рекурсивное разделение кластеров продолжается, пока хотя бы один кластер содержит более одного объекта

Слайд 38

Описание слайда:

Иерархические методы

Слайд 39

Описание слайда:

Иерархические методы Проблема определения оптимального числа кластеров: иногда можно априорно определить число кластеров однако в большинстве случаев число кластеров определяется в процессе кластеризации

Слайд 40

Описание слайда:

Иерархические методы В иерархических методах существует способ, позволяющий определить оптимальное число кластеров Процессу группировки объектов в иерархическом кластерном анализе соответствует постепенное возрастание коэффициента, называемого критерием Е Критерий Е на каждом шаге определяется как расстояние между ближайшими кластерами

Слайд 41

Описание слайда:

Иерархические методы Скачкообразное увеличение критерия Е говорит о переходе от сильно связанного к слабо связанному состоянию объектов Таким образом, нужно останавливать процесс разбиения, когда значение критерия Е резко изменится

Теги Методы кластеризации

Похожие презентации