В моем предыдущем блоге мы познакомились с некоторыми основами кластеризации. Теперь давайте попробуем получить более полную картину алгоритма кластеризации k-средних.
Заявление о кластеризации K-средних
K-means пытается разделить x точек данных на набор из k кластеров, где каждая точка данных назначается ближайшему кластеру. Этот метод определяется целевой функцией, которая пытается минимизировать сумму всех квадратов расстояний в кластере для всех кластеров.
Целевая функция определяется как:
Где xj - точка данных в наборе данных, Si - кластер (набор точек данных, а ui - среднее значение кластера (центр кластера Si).
Алгоритм кластеризации K-средних:
1. Выберите значение k, количество кластеров, которые нужно сформировать.
2. Произвольно выберите k точек данных из набора данных в качестве начальных центроидов / центров кластера.
3. Для каждой точки данных:
а. Вычислить расстояние между точкой данных и центроидом кластера
б. Назначьте точку данных ближайшему центроиду
4. Для каждого кластера вычислите новое среднее значение на основе точек данных в кластере.
5. Повторяйте 3 и 4 шага до тех пор, пока среднее значение кластеров не перестанет изменяться или пока не будет достигнуто максимальное количество итераций.
Разбираемся на простом примере
Мы применим k-means к следующему одномерному набору данных для K = 2.
Набор данных {2, 4, 10, 12, 3, 20, 30, 11, 25}
Итерация 1
M1, M2 - два случайно выбранных центроида / средних, где
M1= 4, M2=11
и начальные кластеры
C1= {4}, C2= {11}
Вычислите евклидово расстояние как
D=[x,a]=√(x-a)²
D1 - расстояние от M1
D2 - расстояние от M2
Как видно из приведенной выше таблицы, 2 точки данных добавляются в кластер C1, а другие точки данных добавляются в кластер C2.
Следовательно
C1= {2, 4, 3}
C2= {10, 12, 20, 30, 11, 25}
Итерация 2
Вычислить новое среднее значение точек данных в C1 и C2.
Следовательно
M1= (2+3+4)/3= 3
M2= (10+12+20+30+11+25)/6= 18
Расчет расстояния и обновление кластеров на основе таблицы ниже
Новые кластеры
C1= {2, 3, 4, 10}
C2= {12, 20, 30, 11, 25}
Итерация 3
Вычислить новое среднее значение точек данных в C1 и C2.
Следовательно
M1= (2+3+4+10)/4= 4.75
M2= (12+20+30+11+25)/5= 19.6
Расчет расстояния и обновление кластеров на основе таблицы ниже
Новые кластеры
C1= {2, 3, 4, 10, 12, 11}
C2= {20, 30, 25}
Итерация 4
Вычислить новое среднее значение точек данных в C1 и C2.
Следовательно
M1= (2+3+4+10+12+11)/6=7
M2= (20+30+25)/3= 25
Расчет расстояния и обновление кластеров на основе таблицы ниже
Новые кластеры
C1= {2, 3, 4, 10, 12, 11}
C2= {20, 30, 25}
Как мы видим, точки данных в кластере C1 и C2 на итерации 3 такие же, как точки данных кластера C1 и C2 на итерации 2.
Это означает, что ни одна из точек данных не переместилась в другой кластер. Также среднее значение / центроид этих кластеров постоянно. Таким образом, это становится условием остановки нашего алгоритма.
Сколько кластеров?
Выбрать правильное значение «K» очень сложно, пока мы не будем хорошо знакомы с нашим набором данных.
Поэтому нам нужен какой-то метод для определения и проверки погоды, мы используем правильное количество кластеров. Фундаментальная цель разделения набора данных - минимизация внутрикластерной вариации или SSE. SSE можно рассчитать следующим образом: сначала возьмите разницу между каждой точкой данных с ее центром тяжести, а затем сложите все квадраты вычисленных разностей.
Итак, чтобы найти оптимальное количество кластеров:
Выполните k-среднее для различных значений «K». Например, K изменяется от 1 до 10 и для каждого значения K вычисляют SSE.
Постройте линейную диаграмму значений K на оси x и соответствующих ей значений SSE на оси y, как показано ниже.
SSE = 0, если K = количество кластеров, что означает, что каждая точка данных имеет свой собственный кластер.
Как мы видим на графике, при переходе от K = 2 к 3 наблюдается быстрое падение SSE, и оно становится почти постоянным при дальнейшем увеличении значения K.
Из-за внезапного падения мы видим на графике изгиб. Таким образом, значение, которое следует учитывать для K, равно 3. Этот метод известен как метод локтя.
Есть также много других методов, которые используются для определения значения K.
K-means - это алгоритм кластеризации «к работе», потому что он быстрый и простой для понимания.
Перечисление некоторых недостатков K-средних
1. Результат может быть неоптимальным в глобальном масштабе: мы не можем гарантировать, что этот алгоритм приведет к лучшему глобальному решению. Выбор различных случайных семян в начале влияет на конечные результаты.
2. Значение K необходимо указать заранее: мы можем ожидать это значение только в том случае, если у нас есть хорошее представление о нашем наборе данных, и если мы работаем с новым набором данных, то для определения значения K можно использовать метод локтя.
3. Работает только для линейных границ: K-means предполагает, что границы всегда будут линейными. Следовательно, он терпит неудачу, когда дело доходит до сложных границ.
4. Медленно для большого количества выборок: поскольку этот алгоритм обращается к каждой точке набора данных, он становится медленным при увеличении размера выборки.
Так что все это касалось K-Means. Надеюсь, теперь вы лучше понимаете, как на самом деле работает k-средство. Есть много других алгоритмов, которые используются для кластеризации в отрасли.
Спасибо за прочтение!
