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

1. Простейшие методы кластеризации в машинном  обучении

Подготовил: Бикмурзин М.А.
Группа: Фт-450005
Простейшие методы кластеризации в
машинном обучении

2. О кластеризации

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

3. K-means

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

4. Affinity Propagation

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

5. Обязательные оптимизации и параметры Affinity Propagation

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

6. DBSCAN

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

7. Spectral clustering

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

8. Spectral clustering

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

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

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

11. Спасибо за внимание!