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

План лекции

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

Введение

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

Введение

Кластеризация отличается от классификации тем, что этап обучения на примерах отсутствует
В задачах

Введение

Эта задача решается на начальных этапах исследования, когда о данных мало

Введение

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

Формальная постановка задачи

Дано множество данных, состоящее из N объектов (векторов):
S1, S2,

Формальная постановка задачи

Таким образом, i-й объект можно записать в виде:
Si =

Формальная постановка задачи

Требуется:
найти способ сравнения d(Sp, Sq) объектов между собой (меру сходства,

Формальная постановка задачи

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

Формальная постановка задачи

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

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

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

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

1. Выбирается k произвольных исходных центров кластеров – обычно выбираются

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

Выбор числа кластеров является сложным вопросом
Если нет предположений относительно этого

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

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

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

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

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

Пример.

Примем k = 3

Начальные центры – объекты 1, 3,

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

Пример.

Примем k = 3

Начальные центры – объекты 1, 3,

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

Найдем новые центры кластеров

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

Найдем новые центры кластеров

Разобьем все объекты по новым кластерам

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

Пересчитаем центры кластеров

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

Разбивка объектов по новым кластерам не меняет расположение центров

Метод ISODATA

ISODATA – Iterative Self-Organizing Data Analysis Techniques – итеративный самоорганизующийся

Метод ISODATA

Если в кластер входит менее заданного минимального числа объектов, кластер

Метод ISODATA

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

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

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

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

В начале работы алгоритма все объекты являются отдельными кластерами
На первом

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

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

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

Пример.

Каждый объект формирует свой кластер

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

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

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

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

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

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

Дивизимный метод

На первом шаге все объекты помещаются в один кластер С1
Выбирается

Дивизимный метод

Выбранный объект удаляется из кластера С1 и формирует первый элемент

Дивизимный метод

Переносы элементов из С1 в С2 продолжаются до тех пор,

Дивизимный метод

В результате один кластер делится на два дочерних, один из

Дивизимный метод

Кластер для расщепления выбирается, например, по наибольшему диаметру
Диаметр кластера –

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

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

Проблема определения оптимального числа кластеров:
иногда можно априорно определить число кластеров
однако

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

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