Анализ данных Кластеризация

План лекции Модельные алгоритмы (пример: EM) Концептуальные алгоритмы (пример: COBWEB) Цель: Знакомство с основными алгоритмами кластеризации

Модельные алгоритмы Находят распределение данных по кластерам согласно некоторой модели Максимизируют сходство модели с реальным распределением данных

Модельные алгоритмы Преимущества: Хорошая масштабируемость Можно работать с небольшим количеством данных Недостатки: Нужны модели (но есть популярные решения)

Expectation-Maximization (EM) Основная идея: набор данных может быть смоделирован с помощью линейной комбинации нормальных распределений Нужно найти параметры максимизирующие функцию правдоподобия

Алгоритм работы EM Инициализация: Начальные k распределений (похоже на k- means) Шаг кластеризации: 1.Ожидание (шаг Е) 2.Максимизация (шаг М)

Инициализация EM Инициализация: Начальные k распределений: мат.ожидания μ, ковариации Σ, веса w – все вместе Θ Вектор скрытых переменных G Допустимое отклонение от функции правдоподобия ε Прочие условия выхода из цикла

E-шаг (ожидание) Задача: вычислить G по текущему приближению Θ

E-шаг (ожидание) Задача: вычислить G по текущему приближению Θ

М-шаг (максимизация) Задача: максимизации правдоподобия и поиск следующего приближения G по текущим значениям G и Θ Среднее значение и дисперсия:

Правдоподобие ЕМ Значение правдоподобия: Максимальное значение - наилучшее

Пример ЕМ

Применение ЕМ Обработка результатов экспериментов Распознавание образов Поиск аномалий

Концептуальные алгоритмы Основная идея: создание концепции описания каждого кластера Обычно генерируют иерархию кластеров, но не относятся к иерархической кластеризации

Концептуальные алгоритмы Преимущества Масштабируемость Работа при неизвестном количестве объектов (легкое добавление в ходе работы) Недостатки: Относительно сложный мат.аппарат

COBWEB Основная идея: последовательно строит дерево кластеров, рассматривая полезность отнесения объекта к какому- либо кластеру

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

Свойства критерия полезности Предиктивность P(C k | A = υ ij ) Предсказуемость P(A j = υ ij | C k ) Усиленное влияние распространенных свойств P(A = υ ij ) Высокая вероятность что объекты из одной категории обладают одинаковыми свойствами Низкая вероятность наличия этих свойств у объектов из других категорий

Формула критерия полезности C k – категории A j – свойства υ ij – значения свойств

Алгоритм COBWEB Добавление нового объекта может: Слить две категории Разделить категорию на две Добавить новую категорию Отправить объект дальше по иерархии

Алгоритм COBWEB 1.Если у категории нет подкатегорий, то создать подкатегорию и отнести к ней объект 2.Если есть, то вычислить пользу: – От отнесения объекта к имеющейся подкатегории – От создания новой подкатегории 3.Если отнесли к имеющейся подкатегории, то вычислить пользу слияния наиболее подходящих объекту категорий

Применение COBWEB Веб-анализ Экспертные системы Анализ разнородных данных

Спасибо за внимание Вопросы по кластеризации присылайте на: