КЛАСТЕРНЫЙ АНАЛИЗ - презентация, доклад, проект скачать

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему КЛАСТЕРНЫЙ АНАЛИЗ. Доклад-сообщение содержит 27 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

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

КЛАСТЕРНЫЙ АНАЛИЗ Постановка задачи группировки данных Задача состоит в том ,чтобы на основании данных , находящихся в множестве Х разбить их на m групп таким образом , чтобы Такое разбиение должно отвечать некоторому критерию сходства, т.е. элементы из одного класса отвечают критерию сходства, а элементы из разных классов- нет. Имеется некоторая целевая функция, которая определяет правило, по которому мы относим элементы к тому или иному классу. Предполагается, что каждый элемент относится строго к одному классу- это детерминированная постановка задачи. Кластеризация может быть и нечетной. Может быть вероятностная постановка задачи кластеризации. Существует задача разделения смесей, когда по совместной выборке необходимо оценить характеристики классов. Мы будем рассматривать кластерный анализ в детерминированном смысле. Задача классификации может решаться очень успешно, если вначале провести кластеризацию.

Слайд 2

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

Задача кластеризации: Задача кластеризации: 1)Изучение данных 2)Использование кластеров для более правильного решения задачи классификации. На чем базируется задача кластеризации: Результат кластеризации зависит от критерия, по которому будет проходить кластеризация. Большинство методов основано на понятии расстояния между объектами.

Слайд 3

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

Пример Х={3,4,7,4,3,3,4,4} Сумма квадратов отклонения: Внутригрупповые квадраты отклонения (критерий- это минимум внутригруппового отклонения) w1=0 w2=0 w3=0 w=w1+w2+w3=0 Все метрические методы основаны функции расстояния между объектами.

Слайд 4

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

Функция расстояния Функция расстояния При рассмотрении задачи кластеризации применяются различные функции расстояния.

Слайд 5

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

Слайд 6

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

Свойство расстояния Махланобиса: Свойство расстояния Махланобиса: заданы это расстояние обладает свойством инвариантности по отношению к линейному преобразованию. (Нужно доказать свойство инвариантности. Выписать формулы и т.д.) Если имеется m объектов, то можно определить матрицу расстояний между этими объектами для каждой пары xi и xj Условно обозначим

Слайд 7

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

Некоторые алгоритмы работают на основе таких матриц. Некоторые алгоритмы работают на основе таких матриц. Мера сходства определяется следующим образом: и обладают следующими свойствами: rij-коэффициент корреляции.

Слайд 8

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

Если то rij определяется немного не так. Если то rij определяется немного не так. Меру сходства очень просто построить из меры расстояния: Фактически это обратная функция Может быть мера сходства для бинарных объектов , которая определяется следующим образом: -число совпадений единиц (если все совпадают, то Sij =1,если нет, то Sij =0) nij -число совпадений нулей

Слайд 9

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

Что такое расстояние между кластерами: Что такое расстояние между кластерами: 1) Расстояние на основе ближайшего соседа – это расстояние, которое определяется минимальным расстоянием между элементами рассматриваемых кластеров.

Слайд 10

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

Расстояние по принципу дальнего соседа(т.е. рассматриваются наиболее удаленные точки между объектами) Расстояние по принципу дальнего соседа(т.е. рассматриваются наиболее удаленные точки между объектами) Расстояние между центрами тяжести (или между математическими ожиданиями) средний вектор. Расстояние по принципу средней связи.

Слайд 11

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

Критерии качества разбиения на классы Критерий суммы квадратов ошибок: ni –элементов в Xi: Мы можем ввести функцию разброса: Здесь можно минимизировать только положение mi. Этот критерий хорошо работает, когда предполагается, что кластеры хорошо разнесены.

Слайд 12

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

Есть критерий, основанный на матрице рассеивания: матрица рассеивания определяется следующим образом: Есть критерий, основанный на матрице рассеивания: матрица рассеивания определяется следующим образом: Где Si -матрица рассеяния внутри группы, Sw – суммарная матрица рассеяния внутри группы. Есть понятия расстояния между группами: где -общее среднее, ST – общее рассеивание

Слайд 13

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

На данной базе рассматривают следующие критерии: На данной базе рассматривают следующие критерии: Еще один критерий основан на минимизации определителя матрицы рассеивания (данный критерий эквивалентен линейным преобразованиям):

Слайд 14

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

Основные типы кластерных процедур. Основные задачи кластерного анализа Задачи могут быть классифицированы по объему выборки . 1) Малые выборки (10-100 объектов) 2) Большие выборки (100-1000 и больше объектов) Задачи кластеризации с точки зрения априорной информации: 1) Число кластеров априорно задано 2)Число кластеров априорно не задано и их нужно определить 3)Число кластеров априорно не задано, но не требуется их точно определять в процессе обработки информации Имеются следующие виды процедур: 1)Иерархические. Они отличаются большим объемом вычислений. 2)Параллельные процедуры. На каждом шагу анализируется вся выборка. 3)Процедуры последовательного типа: на каждом шагу анализируется один элемент выборки. Цель-минимизация некоторого функционала разбиения.

Слайд 15

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

Все задачи сводятся к минимизации следующего функционала: Все задачи сводятся к минимизации следующего функционала: Пусть мы делаем все переборы N-количество элементов Пример: N=500 c=5, тогда полных переборов: М

Слайд 16

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

Построение последовательной процедуры итеративной оптимизации Пусть есть 2 кластера хi и хj передвигаем эту выборку в xj (физически она остается на месте в пространстве, но относится уже к хj) Критерий качества:

Слайд 17

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

Теперь передвигаем из I->J. Что поменяется в этом случае? Теперь передвигаем из I->J. Что поменяется в этом случае? (1) Когда передвинули i->j , то (2) (старые х)

Слайд 18

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

После преобразования результат получился следующим: Нам надо , а это будет тогда, когда

Слайд 19

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

Базовая процедура кластеризации (базовая минимальная квадратичная ошибка) 1) выбирается некоторое первоначальное разделение по группам . x1,x2,…xc Пусть с известно. Вычисляем I и средние m1,m2,…mc . Цикл: 2) выбрать следующую выборку кандидата на передвижение 3) если Ni =1 , то перейти к следующему, иначе вычислить: 4) Передвинуть x в ХК ,если для всех I 5) Вновь вычислить I =

Слайд 20

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

Следующий: Следующий: 6) если I не изменилось после N попыток – остановка; иначе перейти к Цикл N- число выборок Это типичная последовательная процедура.

Слайд 21

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

Параллельная процедура. Базовые изоданные Основан на классификации данных по принципу min d , можно задать любое расстояние, Евклидово, Махланобиуса и т.д. Каждый группа описывается средним: Отличия к группе определяются как:

Слайд 22

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

Описание процедуры: Базовые изоданные 1. Выбираем некоторые начальные значения для средних 2. Классифицируем n-выборок, разбивая их на классы по ближайшим соседям 3. Вновь вычисляем среднее как среднее значение выборок в своем классе. 4. Если какое-либо среднее изменило значение, переходим в Цикл, иначе остановка 5. остановка.

Слайд 23

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

Алгоритм К - внутригрупповых средних (это базовые и заданные) Этот алгоритм минимизирует сумму квадратов расстояний всех точек, входящих в кластерную область, до центра кластера структура алгоритма состоит из к-шагов. Шаг 1. Выбираем К исходных центров кластеров Этот выбор производится произвольно и обычно в качестве исходных центров кластеров используем первые к- результатов выборки из заданного множества образов. Шаг 2. На к-том шаге итерации заданное множество образов {x} распределяется по к- кластерам по правилу мин расстояния: для всех i=1,2… к: , Sj(k) - множество образов, входящих в кластер с центром zj(k) В случае равенства решения принимается произвольным образом

Слайд 24

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

Шаг 3. На основе результатов шага 2 принимаются новые центры кластеров Шаг 3. На основе результатов шага 2 принимаются новые центры кластеров zj(k+1), j=1,2,…k. Исходя из условия, что сумма квадратов расстояний между всеми образами принадлежит множеству Sj(k) и новым центрам кластера д.б. минимально, таким образом, новый центр кластера выбирается так, чтобы минимизировать показатель качества центр zj(k+1), обеспечивающий минимизацию показателя качества, является, в сущности, выборочным средним, определенным по множеству Sj(k). Как Nj- число выборочных образов, входящих в множество Sj(k)

Слайд 25

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

Иерархические процедуры группировки Здесь количество групп С не определено четко, оно меняется от N (число выборок) до 1. Основаны на построении деревьев, описывающих взаимосвязи между кластерами.

Слайд 26

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

Агломеративная процедура Имеется N выборок. В начале полагается, что С=N x1, x2, x3, … xN * * * … * Используем матрицу взаимных расстояний, т.к. каждый кластер состоит из 1-го элемента Ищутся классы, ближайшие по данной ветке. Получаем следующее разбиение S(2), которой соответствует расстояние и так далее: Но на каком-то этапе можем получить довольно устойчивую кластеризацию.

Слайд 27

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

Базовую процедуру кластеризации можно сформулировать следующим образом: Базовую процедуру кластеризации можно сформулировать следующим образом: С- количество кластеров 1) Пусть , N - количество элементов выборок цикл: 2) Если , то остановка - заданное количество кластеров, текущее количество кластеров 3) Найти ближайшую пару кластеров xi , xj 4) Объединяем xi и xj и уничтожаем хi . Положить -1 5) Переход к циклу. Аналогично можно осуществлять эту процедуру и снизу.

Теги КЛАСТЕРНЫЙ АНАЛИЗ

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