- В чём заключается задача кластеризации
- Алгоритм K-mean
- Как оценить качество разбиения
- Как определить оптимальное количество классов
Кластеризация (англ. cluster analysis) — задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.
Задача кластеризации относится к классу задач обучения без учителя.
Алгоритм k-mean (к-средних)
Метод k-средних – это специальный алгоритм кластеризации, подразумевающий, что у нас есть массив данных, которые мы хотим сгруппировать в кластеры, а точнее – в k кластеры.
В алгоритме метода k-средних есть два основных этапа. Сначала мы выбираем k разных центров кластеров, как правило, это просто
случайные точки в наборе данных. Например, возьмем 3. Затем мы переходим к нашему основному циклу, который также состоит из двух
этапов. Первый – это выбор, к какому из кластеров принадлежит каждая точка из X. Для этого мы берём каждый пример и выбираем
кластер, чей центр ближе всего. Не забывайте, что вначале мы выбираем центры случайным образом.
Второй этап – заново вычислить каждый центр кластера, основываясь на множестве точек, которые к нему приписаны. Для этого берутся все соответствующие примеры и вычисляется их среднее значение, отсюда и название метода – метод k-средних.
Всё это делается до тех пор, пока алгоритм не сойдется, то есть пока не прекратится изменение в распределении точек по кластерам или в координатах центров кластеров. Как правило, это происходит очень быстро: в районе от 5 до 15 проходов цикла. Это сильно отличается
от градиентного спуска в глубоком обучении, где могут пройти тысячи итераций, пока не произойдёт схождение.
Проблема оценки качества в задаче кластеризации трудноразрешима, как минимум, по двум причинам:
- Теорема невозможности Клейнберга — не существует оптимального алгоритма кластеризации.
- Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.
Оптимальное количество классов можно определить если визуализировать инерцию (среднее расстояние от точек до центров кластеров). Построим график.
Т. е. там, где есть явное преломление графика, имеет место определение нового кластера. Судя по этому графику, можно разделить все данные примерно на 23 кластера. Эти графики строятся не быстро (иногда несколько часов), и это нормально. Таким образом можно делать кластеризацию разных данных (числовых, текстовых, картинок) с подробным описанием каждого кластера.