Что такое кластеризация K-Means и как работает ее алгоритм?

Что такое кластеризация K-Means и как работает ее алгоритм?

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

Автор: Клинтон Ойого, специалист по обработке данных Всемирного центра агролесомелиорации, 2 мая 2023 года в области машинного обучения

Вступление

По сути, существует четыре типа алгоритмов машинного обучения: контролируемые алгоритмы, полууправляемые алгоритмы, неконтролируемые алгоритмы и алгоритмы обучения с подкреплением. Контролируемые алгоритмы - это те, которые работают с данными, имеющими метки. Полуконтролируемый - это когда часть данных помечена, а другая часть - нет. Неконтролируемый - это когда данные не имеют меток. Обучение с подкреплением - это разновидность машинного обучения, при котором у нас есть агент, который работает над достижением определенной цели и делает это методом проб и ошибок. Агент получает вознаграждение, когда поступает правильно, и наказывается, когда ошибается.

Наше внимание сосредоточено на неконтролируемом алгоритме машинного обучения, в частности на алгоритме кластеризации K-Means.

K-Означает кластеризацию

K-Means - это неконтролируемый алгоритм машинного обучения, который присваивает точки данных одному из K кластеров. Неконтролируемый, как упоминалось ранее, означает, что данные не имеют групповых меток, которые вы получили бы в контролируемой задаче. Алгоритм отслеживает закономерности в данных и использует их для помещения каждой точки данных в группу со схожими характеристиками. Конечно, существуют и другие алгоритмы для решения задач кластеризации, такие как DBSCAN, агломеративная кластеризация, KNN и другие, но K-Means несколько более популярен по сравнению с другими подходами.

K относится к различным группам, в которые помещаются точки данных. Если K равно 3, то точки данных будут разделены на 3 кластера. Если 5, то у нас будет 5 кластеров.. Подробнее об этом позже.

Применение K-средств

Существует множество способов, с помощью которых мы можем применять кластеризацию для решения реальных проблем. Ниже приведены несколько примеров приложений:

• Кластеризация клиентов: Компании могут использовать кластеризацию для группировки своих клиентов для лучшего целевого маркетинга и понимания своей клиентской базы.
• Классификация документов: Группируйте документы на основе тем или ключевых слов в содержании.
• Сегментация изображения: кластеризация пикселей изображения перед распознаванием изображения.
• Группировка учащихся в зависимости от их успеваемости: вы могли бы разделить их на лучших и средних исполнителей и использовать это для улучшения процесса обучения.

Как работают алгоритмы K-средних

Алгоритм запускает начальную итерацию, на которой точки данных случайным образом распределяются по группам, центральная точка которых известна как центроид. Вычисляется евклидово расстояние каждой точки данных до центроидов, и если расстояние до точки больше, чем до другого центроида, точка переназначается наЂ?Другой центр тяжести. Когда это произойдет, алгоритм запустит еще одну итерацию, и процесс будет продолжаться до тех пор, пока все группировки не будут иметь минимальную дисперсию внутри группы.

Что мы подразумеваем под минимальной вариабельностью внутри группы, так это то, что характеристики наблюдений в группе должны быть настолько схожими, насколько это возможно.

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

Что такое кластеризация K-Means и как работает ее алгоритм?Что такое кластеризация K-Means и как работает ее алгоритм?

Шаг 1: Инициализация

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

На начальной итерации в приведенном ниже примере случайным образом выбираются K центроидов.

Что такое кластеризация K-Means и как работает ее алгоритм?Что такое кластеризация K-Means и как работает ее алгоритм?

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

Шаг 2: Назначьте точки одному из K центроидов

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

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

Что такое кластеризация K-Means и как работает ее алгоритм?Что такое кластеризация K-Means и как работает ее алгоритм?

Шаг 3: Повторно вычислите центроиды

После первого раунда группировок новые центральные баллы пересчитываются снова, и это потребует повторного присвоения баллов. На графике ниже приведен пример того, какими потенциально могли бы быть новые группировки, и обратите внимание, как некоторые точки были перемещены в новые кластеры.

Что такое кластеризация K-Means и как работает ее алгоритм?Что такое кластеризация K-Means и как работает ее алгоритм?

Повторять

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

Что такое кластеризация K-Means и как работает ее алгоритм?Что такое кластеризация K-Means и как работает ее алгоритм?

Выбор K

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

Что такое кластеризация K-Means и как работает ее алгоритм?Что такое кластеризация K-Means и как работает ее алгоритм?

Можете ли вы назвать количество группировок? Не совсем ясно. Итак, как мы найдем оптимальное количество кластеров, в которые можно сгруппировать вышеуказанные точки данных?

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

Локтевой метод

Этот подход использует общее количество вариаций внутри кластера, иначе известное как WCSS (сумма квадратов внутри кластера). Цель состоит в том, чтобы иметь минимальную дисперсию внутри кластеров (WCSS).

Этот метод работает следующим образом:

Он принимает диапазон из K значений, скажем, от 1 до 8, и вычисляет WSS для каждого K значения.
Результирующие данные будут иметь значение K и соответствующий WSS. Затем эти данные используются для построения графика WCSS в соответствии со значениями k.
Оптимальное число K находится в точке изгиба, где кривая начинает ускоряться. Именно с этого момента метод получил свое название. Подумайте о локте своей руки.

Силуэтный метод

Этот метод измеряет сходство и несходство. Он количественно определяет расстояние точки до других элементов назначенного ей кластера, а также расстояние до элементов в других кластерах. Это работает таким образом:

Он принимает диапазон значений K, начинающийся с 2.
Для каждого значения K он вычисляет сходство кластера, которое представляет собой среднее расстояние между точкой данных и всеми другими членами группы в том же кластере.
Затем вычисляется несходство кластеров путем вычисления среднего расстояния между точкой данных и всеми другими элементами ближайшего кластера.
Коэффициент силуэта будет представлять собой разницу между значением сходства кластера и значением непохожести кластера, деленную на наибольшее из двух значений.

Оптимальным значением K было бы значение с самым высоким коэффициентом. Значения этого коэффициента ограничены диапазоном от -1 до 1.

Вывод

Это вводная статья к алгоритму кластеризации K-Means, в которой мы рассказали, что это такое, как он работает и как выбрать K. В следующей статье мы рассмотрим процесс решения задач кластеризации в реальном мире с использованием библиотеки scikit-learn от Python.

Клинтон Ойого, автор статьи в Saturn Cloud, считает, что анализ данных для получения полезной информации является важной частью его повседневной работы. Обладая навыками в области визуализации данных, анализа данных и машинного обучения, он гордится своей работой в качестве специалиста по обработке данных.