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

План лекции Иерархические алгоритмы (пример: алгоритм ближайшего соседа) Итеративные алгоритмы (пример: k-means) Плотностные алгоритмы (пример: DBSCAN) Цель: Знакомство с основными алгоритмами кластеризации

Иерархические алгоритмы Строят иерархию кластеров Результаты: срез дендрограммы

Алгоритм ближайшего соседа Single-linkage clustering Алгомеративный алгоритм На каждом шаге объединяем наиболее близкие друг другу кластеры в один Вычислительная сложность: O(n 2 )

Алгоритм ближайшего соседа Инициализация: Каждый объект входит в единичный кластер Шаг алгоритма: 1.Вычисление матрицы попарной близости кластеров 2.Объединение наиболее близких кластеров 3.Проверка условий окончания кластеризации

Варианты метрик Ближайший сосед - метод одиночной связи (single linkage) Дальний сосед - метод полной связи (complete linkage) Средний сосед - метод средней связи (pair- group method using arithmetic averages) прочие метрики

Применение иерархических алгоритмов Составление таксономических иерархий (например: упорядочивание документов) Поиск информативных срезов дендрограммы (поиск целевых групп)

Неиерархические алгоритмы Часто разрабатываются под конкретную задачу или сферу применения Вычислительная сложность варьируется Популярные подвиды: – Итеративные – Плотностные – Модельные – Концептуальные

Итеративные алгоритмы Основная идея: выполнение цикла кластеризации до устойчивого состояния или выполнения других условий выхода Отличия от иерархических: – Нельзя построить дендрограмму – Неизвестно максимальное количество итераций – Увеличение количества итераций дает различный эффект

Алгоритм k-means В ходе кластеризации нужно установить центроид так, чтобы все объекты кластера были на минимальной расстоянии от него, а остальные на большем.

Алгоритм k-means Разделяем объекты на k кластеров Вводим центроиды – характеризующие кластер (не обязательно реальные) объекты данных Вычислительная сложность: O(nki), где i – количество итераций

Алгоритм k-means Инициализация: Установить k центроидов (хоть случайно) Шаг алгоритма: 1.Отнести каждый объект к кластеру с ближайшим центроидом 2.Сдвинуть центроиды в «центр» кластера 3.Проверить условия выхода из цикла

Алгоритм k-means

Fuzzy c-means Fuzzy c-means – алгоритм нечеткой кластеризации, в котором каждый объект может относиться к нескольким кластерам Не теряется информация о значимой близости объекта к нескольким центроидам

Применение k-means Быстрая и простая кластеризация Поиск известного количества кластеров (распознавание образов)

Плотностные алгоритмы Идея: поиск кластеров, внутри которых сохраняется определенная плотность между объектами

Алгоритм DBSCAN Внутри каждого кластера наблюдается плотность объектов заметно выше, чем плотность снаружи кластера Плотность в областях с шумом ниже плотности любого из кластеров Вычислительная сложность: O(nlog n)

Алгоритм DBSCAN ε-соседство точки (N ε (p) ) - множество объектов находящихся на расстоянии не более ε MinPt – минимальное число точек (плотность) в множестве соседства данной точки

Алгоритм DBSCAN Инициализация: Выбрать ε, MinPt Для каждого из множества объектов: 1.Найти множество соседей точки 2.Если вокруг точки плотность меньше MinPt, то это шум 3.Если точка еще не входит в кластер, то создаем его вокруг нее 4.Если входит – расширяем кластер

Применение DBSCAN Устранения шумов (с изображений, аудиозаписей и т.д.) Поиск сложных фигур из объектов

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