Данная статья является переводом. Ссылка на оригинал.
Перед тем как начнем изучать алгоритм, давайте разберемся – что же такое кластеризация. Под кластеризацией понимается обнаружение естественных группировок в данных. Обычно, когда нам даны данные, которые мы можем визуализировать (2- или 3-мерные данные), человеческий глаз может легко формировать различные кластеры. Но для машин это делать несколько сложнее. Но тут на помощь и приходят алгоритмы кластеризации, способные находить кластеры в пространстве с ещё большим количеством измерений, чего не может делать даже глаз человека. Теперь, когда мы знаем, что мы хотим сделать, воспользуемся K-means здесь.
Представьте, что у нас есть набор данных из 19 значений, которые выглядят примерно так:
Теперь предположим, что мы знаем, что эти данные разбиваются на 3, относительно очевидные, категории и выглядеть это будет так:
Наша задача – использовать алгоритм кластеризации K-means, чтобы произвести эту категоризацию.
Шаг 1: Выбираем число кластеров, k Число кластеров, которые мы хотим распознать, это и есть k в K-means. В нашем случае, так как мы предположили, что всего 3 кластера, k = 3.
Шаг 2: Выбираем k случайных значений Процесс обнаружения кластеров мы начинаем с выбора 3 случайно выбранных значений (не обязательно, чтобы они были нашими данными). Эти точки будут сейчас работать как центроиды или центры кластеров, которые мы собираемся сгруппировать:
Шаг 3: Создать k кластеров Чтобы создать кластеры, мы начнем измерять расстояние между каждым значением наших данных до каждого из трех центроидов, а затем добавляем его к наиболее близкому кластеру. Для значения, взятого в качестве примера, расстояния будут выглядеть примерно так:
Смотря на рисунок, мы понимаем, что расстояние от значения до зеленого центроида наименьшее, поэтому мы и добавляем значение в зеленый кластер.
В 2-мерном пространстве для нахождения расстояния между двумя точками используется формула:
d=(x2−x1)2+(y2−y1)2
Используя эту формулу, мы повторяем процесс с оставшимися значениями, после этого кластеры будут выглядеть следующим образом:
Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста» Интересно, перейти к каналу
Шаг 4: Вычисляем новый центроид каждого кластера Теперь, когда у нас есть все три кластера, мы находим новые центроиды для каждого из них. Например, ниже изображена формула для нахождения координат синего кластера:
где x1, x2 и x3 – это координаты по оси x каждого из трех значений синего кластера, а y1, y2 и y3 – координаты соответствующих точек по оси y . Мы разделили сумму координат на 3, потому что 3 значения содержится в кластере. Аналогично, координаты центроид розового и зеленого кластеров будут равны:
Так, новые центроиды будут иметь вид:
Шаг 5: Оценить качество каждого кластера Так как k-means не может видеть кластеры так, как это делаем мы, он измеряет качество, находя среднее отклонение внутри всех кластеров. Основная идея, лежащая в основе k-means, заключается в определении таких кластеров, что отклонения внутри каждого кластера минимальны. Чтобы оценить отклонение, мы вычислим такую величину, как WCSS (within-cluster sum of squares) – cумму квадратов внутрикластерных расстояний до центра кластера.
WCSS=∑CkCn(∑diinCidmdistance(di,Ck)2)
Где С – это кластерные центроиды, а d – значения данных в каждом кластере
Но в целях упрощения, давайте представим, что отклонение визуально выглядит так:
Шаг 6: повторяем шаги 3-5 Итак, мы получили кластеры и отклонение, и … Мы начинаем все сначала.
Но теперь мы используем центроиды, которые были вычислены ранее, чтобы создать 3 новых кластера, пересчитать центры новых кластеров и вычислить сумму расстояний внутри каждого кластера.
Давайте предположим, что следующие 4 итерации будут выглядеть так:
На двух последних итерациях мы видим, что кластеры не меняются. Это значит, что алгоритм сошелся и мы останавливаем процесс. Затем мы выбираем кластеры с наименьшим WCSS. Это будут кластеры на последних 2 итерациях, поэтому они и становятся нашими финальными кластерами.
Как выбирать k? В нашем примере мы знали, что нам нужно 3 кластера. Но что, если мы не знаем, какое количество кластеров мы имеем, тогда как нам выбрать k ?
В этом случае мы пытаемся использовать различные значения k и считать WCSS.
k=1:
k=2:
k=3:
k=4:
Вы можете заметить, что каждый раз, когда мы добавляем новый кластер, общее отклонение внутри каждого кластера становится все меньше и меньше. В конце настанет случай, когда на каждое значение данных будет приходиться отдельный кластер, и тогда отклонение будет равно 0 .
Нам нужно использовать подход, называемый «метод локтя», чтобы найти наилучшее значение k . Для этого мы строим график зависимости WCSS от количества кластеров, или k .
Подход называется «метод локтя», потому что мы можем найти оптимальное значение k , когда найдем «согнутый локоть» графика, что находится в точке с k=3 . Вы можете заметить, что до 3 наблюдается быстрое уменьшение отклонения, но потом отклонение перестает падать также быстро.
Что ж, а на этом все. Вот такой он, k-means – простой, но эффективный алгоритм кластеризации! Подведем краткий итог. Сегодня из этой статьи мы узнали, что же такое k-means, как он работает при решении задач кластеризации, а также как находить количество кластеров, когда это неизвестно. Надеюсь, что статья вам понравилось. До новых встреч.
Мне нужно оперативно освоить алгоритмы и структуры данных. Что делать? Если хотите подтянуть или освежить знания по алгоритмам и структурам данных, загляните на наш курс «Алгоритмы и структуры данных», на котором вы:
углубитесь в решение практических задач; научитесь применять алгоритмы и структуры данных при разработке программ; изучите сленг, на котором говорят все разработчики независимо от языка программирования: язык алгоритмов и структур данных; узнаете все про сложные алгоритмы, сортировки, сжатие данных и многое другое. Вы также будете на связи с преподавателем и другими студентами. В итоге будете браться за сложные проекты и повысите чек за свою работу. Курс подходит как junior, так и middle-разработчикам.
Интересно, хочу попробовать