Share This
Связаться со мной
Крути в низ
Categories
//Алгоритм кластеризации K-means (k-средних): формула и метод

Алгоритм кластеризации K-means (k-средних): формула и метод

В статье объясним всем новичкам в мире алгоритмов машинного обучения принципы работы алгоритма K-means (k-средних), пользующегося большой популярностью при решении задач кластеризации. Постараемся избавиться от устрашающих математических нюансов и объяснить на уровне интуитивного понимания.

algoritm klasterizacii k means k srednih formula i metod f20de58 - Алгоритм кластеризации K-means (k-средних): формула и метод

Данная статья является переводом. Ссылка на оригинал.

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

Представьте, что у нас есть набор данных из 19 значений, которые выглядят примерно так:

algoritm klasterizacii k means k srednih formula i metod 7ed5058 - Алгоритм кластеризации K-means (k-средних): формула и метод

Теперь предположим, что мы знаем, что эти данные разбиваются на 3, относительно очевидные, категории и выглядеть это будет так:

algoritm klasterizacii k means k srednih formula i metod 3d7265c - Алгоритм кластеризации K-means (k-средних): формула и метод

Наша задача – использовать алгоритм кластеризации K-means, чтобы произвести эту категоризацию.

Шаг 1: Выбираем число кластеров, k

Число кластеров, которые мы хотим распознать, это и есть k в K-means. В нашем случае, так как мы предположили, что всего 3 кластера, k = 3.

Шаг 2: Выбираем k случайных значений

Процесс обнаружения кластеров мы начинаем с выбора 3 случайно выбранных значений (не обязательно, чтобы они были нашими данными). Эти точки будут сейчас работать как центроиды или центры кластеров, которые мы собираемся сгруппировать:

algoritm klasterizacii k means k srednih formula i metod 4f0b0b3 - Алгоритм кластеризации K-means (k-средних): формула и метод

Шаг 3: Создать k кластеров

Чтобы создать кластеры, мы начнем измерять расстояние между каждым значением наших данных до каждого из трех центроидов, а затем добавляем его к наиболее близкому кластеру. Для значения, взятого в качестве примера, расстояния будут выглядеть примерно так:

algoritm klasterizacii k means k srednih formula i metod 58d6fb2 - Алгоритм кластеризации K-means (k-средних): формула и метод

Смотря на рисунок, мы понимаем, что расстояние от значения до зеленого центроида наименьшее, поэтому мы и добавляем значение в зеленый кластер.

В 2-мерном пространстве для нахождения расстояния между двумя точками используется формула:

algoritm klasterizacii k means k srednih formula i metod c3f8db5 - Алгоритм кластеризации K-means (k-средних): формула и метод

d=(x2−x1)2+(y2−y1)2

Используя эту формулу, мы повторяем процесс с оставшимися значениями, после этого кластеры будут выглядеть следующим образом:

algoritm klasterizacii k means k srednih formula i metod fed023a - Алгоритм кластеризации K-means (k-средних): формула и метод

Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста» Интересно, перейти к каналу

Шаг 4: Вычисляем новый центроид каждого кластера

Теперь, когда у нас есть все три кластера, мы находим новые центроиды для каждого из них. Например, ниже изображена формула для нахождения координат синего кластера:

algoritm klasterizacii k means k srednih formula i metod 4c5ac00 - Алгоритм кластеризации K-means (k-средних): формула и метод

где x1, x2 и x3 – это координаты по оси x каждого из трех значений синего кластера, а y1, y2 и y3 – координаты соответствующих точек по оси y. Мы разделили сумму координат на 3, потому что 3 значения содержится в кластере. Аналогично, координаты центроид розового и зеленого кластеров будут равны:

algoritm klasterizacii k means k srednih formula i metod 832861c - Алгоритм кластеризации K-means (k-средних): формула и метод

Так, новые центроиды будут иметь вид:

algoritm klasterizacii k means k srednih formula i metod 9d3eb53 - Алгоритм кластеризации K-means (k-средних): формула и метод

Шаг 5: Оценить качество каждого кластера

Так как k-means не может видеть кластеры так, как это делаем мы, он измеряет качество, находя среднее отклонение внутри всех кластеров. Основная идея, лежащая в основе k-means, заключается в определении таких кластеров, что отклонения внутри каждого кластера минимальны. Чтобы оценить отклонение, мы вычислим такую величину, как WCSS (within-cluster sum of squares) – cумму квадратов внутрикластерных расстояний до центра кластера.

WCSS=∑CkCn(∑diinCidmdistance⁡(di,Ck)2)

Где С – это кластерные центроиды, а d – значения данных в каждом кластере

Но в целях упрощения, давайте представим, что отклонение визуально выглядит так:

algoritm klasterizacii k means k srednih formula i metod 629b4eb - Алгоритм кластеризации K-means (k-средних): формула и метод

Шаг 6: повторяем шаги 3-5

Итак, мы получили кластеры и отклонение, и … Мы начинаем все сначала.

Но теперь мы используем центроиды, которые были вычислены ранее, чтобы создать 3 новых кластера, пересчитать центры новых кластеров и вычислить сумму расстояний внутри каждого кластера.

Давайте предположим, что следующие 4 итерации будут выглядеть так:

algoritm klasterizacii k means k srednih formula i metod a553573 - Алгоритм кластеризации K-means (k-средних): формула и метод

На двух последних итерациях мы видим, что кластеры не меняются. Это значит, что алгоритм сошелся и мы останавливаем процесс. Затем мы выбираем кластеры с наименьшим WCSS. Это будут кластеры на последних 2 итерациях, поэтому они и становятся нашими финальными кластерами.

Как выбирать k?

В нашем примере мы знали, что нам нужно 3 кластера. Но что, если мы не знаем, какое количество кластеров мы имеем, тогда как нам выбрать k?

В этом случае мы пытаемся использовать различные значения k и считать WCSS.

k=1:

algoritm klasterizacii k means k srednih formula i metod b1ff047 - Алгоритм кластеризации K-means (k-средних): формула и метод

k=2:

algoritm klasterizacii k means k srednih formula i metod b210ca1 - Алгоритм кластеризации K-means (k-средних): формула и метод

k=3:

algoritm klasterizacii k means k srednih formula i metod 7b13253 - Алгоритм кластеризации K-means (k-средних): формула и метод

k=4:

algoritm klasterizacii k means k srednih formula i metod b153c31 - Алгоритм кластеризации K-means (k-средних): формула и метод

Вы можете заметить, что каждый раз, когда мы добавляем новый кластер, общее отклонение внутри каждого кластера становится все меньше и меньше. В конце настанет случай, когда на каждое значение данных будет приходиться отдельный кластер, и тогда отклонение будет равно 0.

Нам нужно использовать подход, называемый «метод локтя», чтобы найти наилучшее значение k. Для этого мы строим график зависимости WCSS от количества кластеров, или k.

algoritm klasterizacii k means k srednih formula i metod 8464cbd - Алгоритм кластеризации K-means (k-средних): формула и метод

Подход называется «метод локтя», потому что мы можем найти оптимальное значение k, когда найдем «согнутый локоть» графика, что находится в точке с k=3. Вы можете заметить, что до 3 наблюдается быстрое уменьшение отклонения, но потом отклонение перестает падать также быстро.

Что ж, а на этом все. Вот такой он, k-means – простой, но эффективный алгоритм кластеризации! Подведем краткий итог. Сегодня из этой статьи мы узнали, что же такое k-means, как он работает при решении задач кластеризации, а также как находить количество кластеров, когда это неизвестно. Надеюсь, что статья вам понравилось. До новых встреч.

Мне нужно оперативно освоить алгоритмы и структуры данных. Что делать?

Если хотите подтянуть или освежить знания по алгоритмам и структурам данных, загляните на наш курс «Алгоритмы и структуры данных», на котором вы:

  • углубитесь в решение практических задач;
  • научитесь применять алгоритмы и структуры данных при разработке программ;
  • изучите сленг, на котором говорят все разработчики независимо от языка программирования: язык алгоритмов и структур данных;
  • узнаете все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

Вы также будете на связи с преподавателем и другими студентами. В итоге будете браться за сложные проекты и повысите чек за свою работу. Курс подходит как junior, так и middle-разработчикам.

Интересно, хочу попробовать

  • 0 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Связаться со мной
Close