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

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

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

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

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

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

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

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

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

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

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

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

12 Пример ЕМ

13

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

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

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

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

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

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

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

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

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

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

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