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

Задачи интеллектуального анализа данных
Задачи ИАД
Описательные
Ассоциативные правила
Кластеризация
Классификация
Прогнозирование
Предсказательные

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

Кластеризация отличается
от классификации тем, что этап обучения на примерах отсутствует
В задачах классификации множество классов заранее известно, в кластеризации классы определяются в процессе анализа
Поэтому кластеризация относится
к задачам обучения без учителя (unsupervised learning)

Задача кластеризации часто решается на начальных этапах исследования, когда о данных мало что известно
Ее решение помогает лучше понять данные
После определения кластеров применяются другие методы Data Mining, чтобы попытаться установить, что означает такое разбиение
Кластерный анализ позволяет рассматривать достаточно большой объем информации и сжимать большие массивы информации,
делать их компактными и наглядными

ПРИМЕР –кластеризация результатов поиска

Формальная постановка задачи
Дано множество данных, состоящее из N объектов (векторов):
S1, S2, …, SN
Каждый объект описывается набором признаков:
x1, x2, …, xm,
где m – размерность пространства признаков

Формальная постановка задачи
Таким образом, i-й объект можно записать в виде:
Si = (xi1, xi2, …, xim)
Класс для каждого объекта неизвестен

Формальная постановка задачи
Требуется:
найти способ сравнения d(Sp, Sq)
объектов между собой (меру сходства, функцию расстояния)
определить множество кластеров
С1, C2, …, Cr
причем количество кластеров r – неизвестно
разбить данные по кластерам

евклидово расстояние
Манхэттенское расстояние
расстояние Чебышева
Метрики расстояния между объектами

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

Виды кластеров
Внутрикластерные расстояния, как правило, меньше межкластерных
Но бывают ленточные кластеры, в которых внутрикластерные расстояния большие
Идеальный случай- сферические кластеры с центром (встречаются редко)

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

Алгоритмы кластеризации

Как сделать признаки
равноправными в образовании кластеров?
ИТОГ: мы получим значения признаков, 95% которых находится в интервале (-2;2)
Стандартизация данных

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

Метод k-средних
1. Выбирается k произвольных исходных центров кластеров – обычно выбираются k объектов
2. Все объекты разбиваются на k групп, наиболее близких к одному из центров
3. Вычисляются новые центры кластеров
4. Проводится новое разбиение всех объектов на основании близости к новым центрам
Шаги 3 и 4 повторяются до тех пор, пока центры кластеров не перестанут меняться или пока не достигнуто максимальное число итераций

Метод k-средних
Пример.
Примем k = 3
Начальные центры – объекты 1, 3, 4
Разобьем все объекты по кластерам

Метод k-средних
Найдем новые центры кластеров

Метод k-средних
Найдем новые центры кластеров

Метод k-средних
Разобьем все объекты по новым кластерам, относя каждый объект к кластеру с ближайшим центром

Метод k-средних
Пересчитаем центры кластеров.
Дальнейшая разбивка объектов
по новым кластерам
не меняет расположение центров

Метод k-средних: определение k с помощью метода каменистой осыпи
J (Ck) - сумма квадратов расстояний от точек до центроидов кластеров, к которым они относятся, k- количество кластеров

До стандартизации
После
График средних значений
Признаков в кластерах

Иерархические методы
К иерархическим методам кластеризации относятся:
агломеративный алгоритмы
дивизимный алгоритмы

Агломеративный метод
В начале работы алгоритма все объекты являются отдельными кластерами
На первом шаге наиболее похожие (близкие) два кластера объединяются в дин кластер
На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер
На любом этапе объединение можно прервать, получив нужное число кластеров

Метод ближайшего соседа (одиночная связь, Single linkage). Расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами («ближайшими соседями») в различных кластерах.
Метод наиболее удаленного соседа (полная связь, Complete linkage). Расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах.
Попарное среднее (Unweighted pair-group average). Расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них.
Вычисление расстояния между
кластерами

4. Невзвешенный центроидный метод (Unweighted pair-group centroid). В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами.
Вычисление расстояния между
кластерами
5. Метод Варда (Ward's method). В качестве расстояния между кластерами берется прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения В целом метод представляется очень эффективным, однако он стремится создавать кластеры малого размера.

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

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

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

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

Дивизимный метод
На первом шаге все объекты помещаются в один кластер С1
Выбирается объект, у которого среднее значение расстояния до других объектов в этом кластере наибольшее:

Дивизимный метод
Выбранный объект удаляется из кластера С1 и формирует первый элемент второго кластера С2
На каждом последующем шаге объект
в кластере С1, для которого разность между средним расстоянием до объектов, находящихся в С2 и средним расстоянием до объектов, остающихся в С1, наибольшая, переносится в С2

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

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

ДЕНДРОГРАММА

Метрики качества кластеризации
Коэффициент силуэта:
Здесь a — среднее внутрикластерное расстояние (то есть среднее расстояние между элементами, принадлежащими одному кластеру) , b— среднее межкластерное расстояние (cреднее расстояние между элементами, принадлежащими разным кластерам).
Значение коэффициента силуэта лежит в диапазоне [−1,1]. Чем больше величина коэффициента, тем качественнее проведена кластеризация. Значения, близкие к -1, соответствуют плохим (неправильным) кластеризациям, значения, близкие к нулю, говорят о том, что кластеры пересекаются и накладываются друг на друга, значения, близкие к 1, соответствуют плотно сгруппированным кластерам.

Пример программы на Python
from sklearn import datasets
dataset = datasets.load_iris()
X = dataset.data
y = dataset.target
from sklearn.cluster import KMeans
model = KMeans(n_clusters=3).fit(X)
labels = model.labels_
from sklearn import metrics
metrics.silhouette_score(X, labels, metric='euclidean')

DBSCAN
На вход алгоритму подаётся набор точек, параметры ϵ (радиус окрестности)
и m (минимальное число точек в окрестности).

DBSCAN

DBSCAN: результаты работы