Алгоритмы кластеризации в машинном обучении презентация

О кластеризации
Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами.
Главное отличие кластеризации от классификации состоит в том, что перечень групп четко не задан и определяется в процессе работы алгоритма.

K-means
K-means - самый популярный алгоритм кластеризации.
Выделяется благодаря простоте реализации и скорости выполнения.
Принцип работы - минимизация отклонения точек кластеров от центров этих кластеров.
Алгоритм:
Выбрать точки, соответствующие центроидам первичных кластеров
Обходим каждую точку и относим ее к ближайшему (относительно центроида) кластеру
Новые центроиды выбираются как среднее значение (координат) всех точек кластера
Повторяем шаги 2-3 до тех пор, пока центроиды на i-той итерации не будут равны центроидам на i-1 итерации

Affinity Propagation
Вводится матрица схожести S = NxN, S(k,k)<0 (за схожесть 2-х точек можно взять расстояние между ними)
Вводятся матрицы ответственности R = NxN и доступности A = NxN, на первом шаге итерации принятые нулевыми.
Далее по алгоритму:

Обязательные оптимизации и параметры Affinity Propagation
В начале к матрице сходства добавляется немного шума, т.к. когда есть несколько хороших разбиений на кластеры, алгоритм подвержен осцилляциям.
При обновлении R и A используется присваивание с экспоненциальным сглаживаением, с коэффициентом 0.5<α<1
R[i] = α*R[i] + (1-α)*R[i-1] (аналогично для А)
Если алгоритм не сходится/сходится частично - увеличивают α до 0.9-0.95
Affinity Propagation работет хорошо только с НЕБОЛЬШИМИ объемам данных

DBSCAN
На вход подается матрица близости (S=NxN) и два загаочных параметра:
Радиус ε-окресности - радиус, в котором ищутся ближайшие от точки соседи
Ближайшие k-соседи - точки, попадающие в радиус ε-окрестности от заданной
Алгоритм:
Берем случайную точку
Если для нее k<3 - идем дальше
Иначе:
Точка "зеленая"(k>3) - создает группу. Обходим ее соседей, присоединяем их к группе и исключаем из списка обхода. Если сосед "зеленый", его соседей также добавляем в список обхода. Желтым помечаются точки с k<3, но вошедшие в эту группу. Повторяем пока список обхода не окажется пуст.
Повторяем пункты 1-3, пока не обойдем все точки. Точки, не вошедшие ни в какую группу помечаем красным цветом.
В пункте 4 можно включить дополнительную классификацию для "красных" точек, но здесь это опускается.

Spectral clustering
Данные представляются в виде графа. Связи проходят в заданной окресности от точки к другим данным. Строится матрица А.
Строится диагональная матрица D, диагональнымы элементами являются суммы весов связей, исходящих из соответствующей точки.
Строится матрица Кирхгофа по формуле L=D-A
- матрица Кирхгофа L в простейшем случае
(все связи равны 1)

Spectral clustering
После построения матрицы L, находим ее собственные вектора u и собственные значения λ.
Оптимальное количество кластеров равняется кратности собственного значения λ=0
Последний шаг: берем собственный вектор, соответствующий первому ненулевому значению λ и применяем к его элементам алгоритм k-means (первый элемент этого вектора соответствует первой точке и так далее).

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

Еще больше алгоритмов