Презентация КЛАСТЕРНЫЙ АНАЛИЗ онлайн

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

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

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

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

Содержание слайда:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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