Понимание алгоритма кластеризации K-means в машинном обучении
Кластеризация K-средних, или алгоритм K-средних, или алгоритм кластеризации K-средних — что ж, прежде чем мы углубимся в то, что представляют собой алгоритмы кластеризации, нам нужно понять, насколько они важны для современных предприятий, чтобы осмысливать данные — данные о продуктах, данные о клиентах, данные о транзакциях и так далее.
В мире, где технологии переопределяют бизнес-ландшафт, предприятия тратят миллионы долларов на анализ данных, чтобы выявлять закономерности, которые помогают им становиться более эффективными и увеличивать прибыль. Группировка объектов на основе атрибутов — одна из первых задач, участвующих в этом процессе поиска таких закономерностей.
Группировка объектов помогает предприятиям разрабатывать различные стратегии для различных ситуаций. Клиенты, продукты и транзакции являются объектами ключевого интереса в таких процессах. Группировка клиентов на основе их поведения помогает компаниям разрабатывать персонализированные предложения. Группировка продуктов помогает им предлагать клиентам альтернативные варианты. А группировка транзакций помогает им выявлять необычные закономерности, требующие более пристального внимания.
Именно здесь на помощь приходит кластеризация. Кластеризация — это алгоритм машинного обучения (ML) без учителя, который группирует объекты на основе атрибутов.
Эта подробная статья от Zilliz, ведущей компании в области vector database для готового к production AI, подробно расскажет о том, что представляет собой алгоритм кластеризации K-средних в машинном обучении и как его можно реализовать с помощью Python. В ней также будет рассмотрено, когда использовать алгоритм кластеризации K-средних, и приведен реальный пример кластеризации K-средних.
Что такое кластеризация?
Кластеризация — это процесс группировки точек данных таким образом, чтобы каждый элемент в конкретной группе был более похож на элементы этой группы, чем на элементы в других группах. Кластеризация не относится к конкретному алгоритму. Это общая задача, которую можно решить с помощью множества алгоритмов. Алгоритмы кластеризации обычно определяют метрику для систематического количественного измерения сходства. Кластеризация используется во многих областях, таких как обработка изображений, retrieval информации, рекомендательные системы и сжатие данных.
Кластеризация устанавливает сходство на основе атрибутов объектов, которые она кластеризует. Атрибуты различаются в зависимости от предметной области. Например, в случае изображения атрибутами являются значения пикселей. В случае профиля пользователя атрибутами являются такие данные, как возраст, пол и история покупок. В случае продукта атрибутами являются категория, цвет, цена и т. д. Кластеризация называется задачей без учителя, потому что в ней нет контролируемого пользователем процесса обучения, включающего подготовку размеченных данных.
Как работают алгоритмы кластеризации?
Большинство алгоритмов кластеризации работают путем вычисления сходства между всеми парами выборок. Каждая точка данных назначается ближайшему центроиду на основе расчетов расстояния, что является фундаментальным этапом в процессе кластеризации.
Способность масштабироваться под объем набора данных — важный фактор, который следует учитывать при выборе алгоритма кластеризации для задачи. Время выполнения увеличивается с числом пар элементов. В крайних случаях оно может изменяться пропорционально квадрату объема данных.
Четыре подхода к кластеризации
Существует четыре распространенных подхода к кластеризации: на основе центроидов, на основе плотности, иерархический и на основе распределения. Давайте рассмотрим их по очереди.
1. Кластеризация на основе центроидов
Этот метод организует точки данных в отдельные кластеры без какой-либо иерархии на основе центроида всех точек данных в кластере. Центроид — это геометрический центр объекта. Простыми словами, это среднее арифметическое всех точек, составляющих этот объект в n-мерном пространстве. Здесь кластер — это набор точек, расположенных вокруг центроида. Кластеризация на основе центроидов страдает от проблем, связанных с начальными назначениями и выбросами.
2. Кластеризация на основе плотности
Как следует из названия, она вычисляет плотность точек в области, а затем назначает точки данных кластерам там, где обнаружена высокая плотность. В этом случае кластеры могут принимать любую форму. Кластеризация на основе плотности сталкивается с проблемами, когда данные по своей природе имеют высокую вариативность плотности. Она плохо работает, когда размерность данных высока, поскольку ей может быть трудно различать кластеры и соседние кластеры.
3. Иерархическая кластеризация
Этот метод предоставляет дерево кластеров с возможностью наличия кластеров, расположенных внутри более крупных кластеров. Этот метод хорошо подходит, когда данные демонстрируют присущую им иерархию. Иерархическая кластеризация позволяет выбирать любое количество различных кластеров после выполнения, поскольку аналитик может разорвать дерево в нужной точке и рассматривать только кластеры после этой точки.
4. Кластеризация на основе распределения
Этот метод использует концепцию вероятностных распределений для поиска кластеров. Он предполагает, что вероятность нахождения точки в кластере уменьшается, когда расстояние от центра кластера увеличивается. Разработчики должны знать распределение своих данных, чтобы эффективно использовать этот метод.
Что такое кластеризация K-means?
Алгоритм кластеризации K-means — это алгоритм кластеризации на основе центроидов. Это алгоритм обучения без учителя, поскольку он не опирается на размеченные данные. «K» в алгоритме кластеризации K-means представляет количество кластеров.
K-means — это итеративный алгоритм, который вычисляет среднее значение или центроид много раз, прежде чем сойтись. Время сходимости зависит от начального назначения и оптимального количества используемых кластеров. В целом временная сложность K-means составляет
где d — это количество измерений, k — это количество кластеров, а n — это количество k кластеров элементов данных.
Алгоритм кластеризации K-means работает, вычисляя расстояние каждого элемента данных от геометрического центра кластера. Затем он перенастраивает кластер, если находит точку, принадлежащую конкретному кластеру, ближе к центроиду другого кластера. После этого он повторно вычисляет центроид кластера и повторяет процесс до тех пор, пока дальнейшее переназначение кластеров не прекратится.
Давайте посмотрим, как работает алгоритм.
Как работает алгоритм кластеризации K-means?
Алгоритм кластеризации K-means — это итеративный процесс, включающий четыре основных шага. Чтобы понять эти шаги, рассмотрим двумерную задачу кластеризации. Предположим, что точки имеют вид (x1,y1),(x2,y2) и так далее. Начнем с размера кластера, равного 2.
Начальное назначение
Этот шаг назначает каждую точку произвольному кластеру. Один из вариантов — назначить случайные точки центроидами кластеров и вычислить расстояния между каждой точкой данных и центроидами.
Точки назначаются кластеру, чей центроид находится к ним ближе всего. Расстояние между двумя кластерами вычисляется с использованием формулы евклидова расстояния. Например, если x3,y3 является одним из случайно назначенных центроидов, можно вычислить расстояние между x1,y1 и x3,y3 с помощью этой формулы:
Y vs. X
Y vs. X
Красная и зеленая точки обозначают начальные случайные назначения центроидов. Основываясь только на этих начальных центроидах кластеров, начальное назначение кластеров будет выглядеть так, как показано ниже:
Y vs. X
Y и X
Вычисление центроидов
Этот шаг включает пересчет центроидов для каждого кластера. Центроид кластера вычисляется с использованием арифметического среднего всех элементов в этом кластере. Например, допустим, x1,y1, x2,y2 и x3,y3 принадлежат кластеру. Центроид этого кластера вычисляется как:
Точки в форме ромба, как показано ниже, становятся новыми центроидами.
Y vs. X
Y и X
Переназначение кластеров
После того как новые центроиды для всех трех кластеров найдены, расстояние между каждой точкой и новыми центроидами пересчитывается. Если какая-либо из точек расположена ближе к центроиду кластера, к которому она в настоящее время назначена, точки переназначаются.
Y vs. X
Y и X
Сходимость
После переназначения кластеров центроиды вычисляются снова, и процесс повторяется. Вычисление центроидов и переназначение кластеров выполняются до тех пор, пока больше не будет новых переназначений. Сошедшаяся задача кластеризации в этом случае будет выглядеть, как показано ниже:
Y vs. X
Y и X
Выбор количества кластеров
Два часто используемых метода выбора идеального количества кластеров — это метод локтя и метод силуэта.
Метод локтя
Метод локтя вычисляет метрику под названием WCSS (Within Cluster Sum of Squares). WCSS — это сумма квадратов расстояний каждой точки от центроида ее ближайшего кластера выше. График WCSS в зависимости от количества кластеров используется как индикатор для выбора оптимального количества кластеров.
Разработчики выполняют кластеризацию K-means для количества кластеров от 1 до n, а затем вычисляют WCSS для каждого из этих запусков. WCSS будет наибольшим при выполнении с одним кластером и уменьшается, когда количество кластеров увеличивается. Точка, в которой WCSS демонстрирует резкий изгиб, похожий на локоть руки, считается идеальным оптимальным количеством кластеров.
Elbow Method
Метод локтя
Метод силуэта
Этот метод пытается понять степень сходства объекта с другими членами того же кластера и степень отделения объектов от других кластеров. Коэффициент силуэта для точки вычисляется путем объединения среднего расстояния этой точки от других точек в кластере (a) и среднего расстояния этой точки до всех точек, принадлежащих другим кластерам (b), включая соседние кластеры. После того как a и b найдены, коэффициент силуэта для точки вычисляется как
Затем оценка для каждой точки усредняется, чтобы найти коэффициент силуэта. Оценка рассчитывается для всех кандидатов на оптимальное количество, а затем вариант с k точками и наивысшей оценкой выбирается как оптимальное количество.
Silhouette Method
Метод силуэта
Реальный пример алгоритма кластеризации K-means (реализация кластеризации K-means с помощью Python)
В этом руководстве показано, как реализовать кластеризацию K-means с использованием Python и найти оптимальный размер кластера. Для этого предположим постановку задачи, распространенную в сфере электронной коммерции. Кластеризация клиентов на основе их демографических атрибутов и покупательских привычек — распространенная задача в сфере электронной коммерции. Для упрощения примера кластеризации K-means здесь мы будем использовать два атрибута: возраст клиента и среднюю сумму, потраченную в месяц.
- Для этого воспользуемся библиотекой машинного обучения Python под названием scikit-learn и библиотекой для построения графиков под названием matplotlib. Сначала инициализируйте библиотеки с помощью операторов import, приведенных ниже:
import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette\_score
from sklearn.preprocessing import StandardScaler
- Следующий шаг — определить входной фрейм данных. Здесь первый атрибут — возраст, а второй атрибут — средние ежемесячные расходы в индийских рупиях (INR). Для простоты инициализируем массив непосредственно в коде. Здесь у нас 16 точек данных:
raw\_features = np.array([[22,200],[24,200],[24,200],[20,800],[24,800],[24,800],[25,200],[54,200],[24,200],[54,200],[50,800],[53,800],[24,800],[55,800],[53,800],[50,800]])
- Затем вы нормализуете точки данных, чтобы вариация в одном атрибуте не затмевала вариации в других атрибутах.
scaler = StandardScaler()
features = scaler.fit\_transform(raw\_features)
- Реализуйте цикл for, чтобы попробовать кластеризацию K-means для количества кластеров, варьирующегося от 2 до 6. Затем мы вычислим сумму квадратов и построим ее график относительно количества кластеров, чтобы определить оптимальное количество кластеров.
sse = []
s\_scores=[]
for i in range(2,6):
kmeans = KMeans(init = **"random"** ,n\_clusters = i,n\_init = 10,max\_iter = 300,random\_state = 42)
kmeans.fit(features)
sse.append(kmeans.inertia\_)
s\_scores.append(silhouette\_score(features, kmeans.labels\_))
- Используйте библиотеку matplotlib, чтобы построить график суммы квадратов относительно количества кластеров.
plt.style.use( **"fivethirtyeight"** )
plt.plot(range(1, 6), sse)
plt.xticks(range(1, 6))
plt.xlabel( **"Number of Clusters"** )
plt.ylabel( **"SSE"** )
plt.show()
- Запуск приведенного выше кода даст график, который мы можем использовать для определения оптимального количества кластеров.
Кластеризация K-means
Алгоритм кластеризации K-means
Приведенный выше точечный график показывает отчетливый «локоть» при 4. Поэтому оптимальное количество кластеров здесь — 4. Имея некоторые предметные знания, специалист по данным может объяснить это число как четыре комбинации — клиенты с низким возрастом и высокими расходами, низким возрастом и низкими расходами, высоким возрастом и высокими расходами, а также высоким возрастом и низкими расходами. Но такие объяснения не всегда возможны, и оптимальное количество кластеров варьируется в зависимости от спецификаций задачи.
Вот и все, что нужно для запуска кластеризации K-means в Python. Фреймворки scikit-learn и matplotlib делают использование кластеризации в Python очень простым.
Когда использовать алгоритм кластеризации K-Means
Итак, как мы узнали, кластеризация — это алгоритм машинного обучения без учителя, который помогает группировать объекты на основе сходства. Он широко используется во многих отраслевых областях для исследовательского анализа данных.
Он полезен в таких областях, как сегментация клиентов, рекомендательные системы и поиск по сходству. Тем не менее, алгоритм кластеризации K-means — не единственная техника, которую можно использовать для решения этих задач. Другой способ решить такую задачу — сгенерировать векторные вложения для каждого объекта на основе их атрибутов.
Обучающие сети на основе глубокого обучения могут генерировать многомерные вложения для объектов с большим количеством атрибутов. Эти вложения в сочетании с хорошей векторной базой данных могут решать задачи на основе сходства с гораздо лучшим контролем.
Если вы работаете над такими задачами, ознакомьтесь с Zilliz. Он предлагает универсальное решение для задач обработки неструктурированных данных, особенно для предприятий, которые создают приложения AI/ML, использующие поиск по векторному сходству.
Zilliz создала Milvus — популярную векторную базу данных с открытым исходным кодом, которая широко признана более чем тысячей корпоративных пользователей по всему миру. Компания также предлагает полностью управляемый сервис векторной базы данных, Zilliz Cloud, который позволяет предприятиям использовать всю мощь Milvus без сложностей, связанных с созданием инфраструктуры и управлением ею.
Если вы хотите узнать: что такое векторная база данных? — вы можете ознакомиться с подробным руководством. Ищете дополнительную информацию по связанным темам? Ознакомьтесь с этим объяснением приблизительного поиска ближайших соседей (ANNS). Хотите узнать больше о том, как Zilliz может вам помочь? Всё, что вам нужно сделать, — это нажать здесь и спросить!
Читать далее
Introducing Zilliz Cloud Global Cluster: Region-Level Resilience for Mission-Critical AI
Zilliz Cloud Global Cluster delivers multi-region resilience, automatic failover, and fast global AI search with built-in security and compliance.
8 Latest RAG Advancements Every Developer Should Know
Explore eight advanced RAG variants that can solve real problems you might be facing: slow retrieval, poor context understanding, multimodal data handling, and resource optimization.
How to Build RAG with Milvus, QwQ-32B and Ollama
Hands-on tutorial on how to create a streamlined, powerful RAG pipeline that balances efficiency, accuracy, and scalability using the QwQ-32B and Milvus.