Введение:
Кластеризация — это фундаментальный метод анализа данных, который включает группировку точек данных в аналогичные кластеры или группы на основе определенных характеристик или признаков. Кластеризация помогает выявить шаблоны, взаимосвязи и структуры в данных, которые могут быть не очевидны сразу.
Кластеризация K-средних является одним из наиболее широко используемых алгоритмов кластеризации. Итеративный алгоритм разбивает набор данных на K кластеров, где K — определяемый пользователем параметр. Алгоритм присваивает каждую точку данных ближайшему центроиду кластера, а затем обновляет центроид на основе среднего значения точек в кластере. Алгоритм продолжает повторяться до тех пор, пока не сойдутся центроиды или не будет достигнуто максимальное количество итераций.
Цель этой статьи — предоставить обзор кластеризации методом K-средних, ее приложений и рекомендаций по использованию алгоритма. В статье будут обсуждаться основы кластеризации K-средних, как выбрать правильное количество кластеров, примеры реальных приложений, советы по оптимизации производительности и точности, а также распространенные проблемы и ловушки. К концу статьи читатели должны иметь хорошее представление о кластеризации K-средних и уметь применять ее к своим собственным задачам анализа данных.
Основы кластеризации K-средних:
Кластеризация K-средних — это простой, эффективный алгоритм машинного обучения без присмотра, который разбивает заданный набор данных на K кластеров на основе сходства. Основные принципы кластеризации K-средних следующие:
- Кластер.Кластер – это группа точек данных, похожих друг на друга по определенным характеристикам или функциям.
- Центроид. Центроид — это точка в пространстве данных, представляющая центр кластера. Он рассчитывается как среднее значение всех точек в кластере.
- Метрика расстояния. Метрика расстояния — это функция, которая измеряет сходство или различие между двумя точками данных. Наиболее часто используемой метрикой расстояния в кластеризации K-средних является евклидово расстояние.
- Итерация. Кластеризация K-средних – это итеративный алгоритм, который разбивает данные на K кластеров путем многократного обновления центроидов кластера и переназначения точек данных ближайшему центроиду.
Теперь давайте проиллюстрируем алгоритм на простом примере:
Предположим, у нас есть набор данных из 10 точек данных с двумя функциями (x и y), как показано ниже:
(2,3), (3,4), (3,5), (4,5), (5,5), (5,6), (6,5), (7,7), (8,8), (9,9)
Мы хотим разделить данные на три кластера, используя кластеризацию K-средних. Вот как работает алгоритм:
- Выберите K=3 случайных точек в пространстве данных в качестве начальных центроидов. Допустим, мы выбираем (2,3), (5,5) и (9,9) в качестве начальных центроидов.
- Назначьте каждую точку данных ближайшему центроиду на основе евклидова расстояния. Например, (2,3) и (3,4) присваиваются первому центроиду, (3,5), (4,5), (5,5), (5,6) и (6,5). ) назначаются второму центроиду, а (7,7), (8,8) и (9,9) назначаются третьему центроиду.
- Вычислите новые центроиды как среднее значение точек в каждом кластере. Например, новый центроид для первого кластера — (2,5, 3,5), новый центроид для второго кластера — (4,6, 5,4), а новый центроид для третьего кластера — (8, 8).
- Повторяйте шаги 2 и 3, пока не сойдутся центроиды или не будет достигнуто максимальное количество итераций.
В этом примере после нескольких итераций центроиды сходятся, и окончательные кластеры:
Кластер 1: (2,3), (3,4)
Кластер 2: (3,5), (4,5), (5,5), (5,6), (6,5)
Кластер 3: (7,7), (8,8), (9,9)
Таким образом, кластеризация K-средних успешно разделила набор данных на три кластера на основе сходства точек данных.
import numpy as np import matplotlib.pyplot as plt from sklearn.cluster import KMeans from sklearn.datasets import make_blobs # Generate sample dataset with 4 clusters X, y = make_blobs(n_samples=300, centers=4, n_features=2, random_state=42) # Fit K-Means algorithm with 4 clusters kmeans = KMeans(n_clusters=4, init='k-means++', max_iter=300, n_init=10, random_state=42) y_kmeans = kmeans.fit_predict(X) # Plot clusters and centroids plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s=30, color='red', label='Cluster 1' , alpha = 0.6) plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s=30, color='blue', label='Cluster 2' , alpha = 0.6) plt.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], s=30, color='green', label='Cluster 3' , alpha = 0.6) plt.scatter(X[y_kmeans == 3, 0], X[y_kmeans == 3, 1], s=40, color='orange', label='Cluster 4' , alpha = 0.6) plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=100, color='black', label='Centroids' , alpha = 0.6) plt.title('K-Means Clustering') plt.xlabel('Feature 1') plt.ylabel('Feature 2') plt.legend() plt.show()
import numpy as np import matplotlib.pyplot as plt from sklearn.cluster import KMeans from sklearn.datasets import make_circles # Generate sample dataset with 2 circles X, y = make_circles(n_samples=1000, factor=0.5, noise=0.05) # Fit K-Means algorithm with 2 clusters kmeans = KMeans(n_clusters=2, init='k-means++', max_iter=300, n_init=10, random_state=42) y_kmeans = kmeans.fit_predict(X) # Plot clusters and centroids plt.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], s=30, color='red', label='Cluster 1' , alpha = 0.6) plt.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], s=30, color='green', label='Cluster 2' , alpha = 0.6) plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=100, color='black', label='Centroids') plt.title('K-Means Clustering on Circles') plt.xlabel('Feature 1') plt.ylabel('Feature 2') plt.legend() plt.show()
import numpy as np import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D from sklearn.cluster import KMeans from sklearn.datasets import make_blobs # Generate sample dataset with 3 blobs in 3D space X, y = make_blobs(n_samples=1000, n_features=3, centers=3, random_state=42) # Fit K-Means algorithm with 3 clusters kmeans = KMeans(n_clusters=3, init='k-means++', max_iter=300, n_init=10, random_state=42) y_kmeans = kmeans.fit_predict(X) # Plot clusters and centroids in 3D space fig = plt.figure(figsize=(8, 8)) ax = fig.add_subplot(111, projection='3d') ax.scatter(X[y_kmeans == 0, 0], X[y_kmeans == 0, 1], X[y_kmeans == 0, 2], s=30, color='red', label='Cluster 1' , alpha = 0.6) ax.scatter(X[y_kmeans == 1, 0], X[y_kmeans == 1, 1], X[y_kmeans == 1, 2], s=30, color='blue', label='Cluster 2' , alpha = 0.6) ax.scatter(X[y_kmeans == 2, 0], X[y_kmeans == 2, 1], X[y_kmeans == 2, 2], s=30, color='green', label='Cluster 3' , alpha = 0.6) ax.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], kmeans.cluster_centers_[:, 2], s=100, color='black', label='Centroids') ax.set_title('K-Means Clustering in 3D Space') ax.set_xlabel('Feature 1') ax.set_ylabel('Feature 2') ax.set_zlabel('Feature 3') ax.legend() plt.show()
Выбор правильного количества кластеров:
Проверка кластера — это процесс оценки качества и надежности кластеров, полученных с помощью алгоритма кластеризации. Это важно, потому что помогает гарантировать, что результаты кластеризации значимы и полезны для предполагаемого анализа или приложения. Методы проверки кластеров можно использовать для сравнения различных алгоритмов кластеризации, определения оптимального количества кластеров и оценки стабильности и согласованности результатов кластеризации.
Существует несколько методов определения оптимального количества кластеров, в том числе метод локтя и оценка силуэта.
- Метод локтя.Метод локтя включает построение суммы квадратов внутри кластера (WCSS) в зависимости от количества кластеров. WCSS представляет собой сумму квадратов расстояний между каждой точкой и ее центром тяжести в кластере. По мере увеличения количества кластеров WCSS будет уменьшаться, но в какой-то момент скорость уменьшения начнет замедляться, образуя на графике форму «локтя». Оптимальное количество кластеров — это точка, в которой скорость убывания значительно замедляется.
Например, предположим, что у нас есть набор данных со 100 точками данных, и мы применяем кластеризацию K-средних с K в диапазоне от 1 до 10. Мы вычисляем WCSS для каждого значения K и наносим результаты на график. График показывает, что WCSS быстро уменьшается при увеличении K от 1 до 3, но затем скорость снижения замедляется. Точка изгиба находится при K = 3, что указывает на то, что 3 кластера являются оптимальным числом для этого набора данных.
2. Оценка силуэта: оценка силуэта – это показатель того, насколько хорошо каждая точка данных вписывается в назначенный кластер по сравнению с другими кластерами. Он варьируется от -1 до 1, где оценка 1 указывает, что точка данных хорошо соответствует своему собственному кластеру и плохо соответствует другим кластерам, а оценка -1 указывает на обратное. Средняя оценка силуэта по всем точкам данных используется как мера общего качества кластеризации.
Например, предположим, что у нас есть тот же набор данных, что и выше, и мы применяем кластеризацию K-средних с K в диапазоне от 2 до 5. Мы вычисляем оценку силуэта для каждого значения K и наносим результаты на график. График показывает, что оценка силуэта является самой высокой для K = 3, что указывает на то, что 3 кластера являются оптимальным числом для этого набора данных.
import numpy as np import matplotlib.pyplot as plt from sklearn.cluster import KMeans from sklearn.datasets import make_blobs from sklearn.metrics import silhouette_score # Generate sample dataset with 2 features and 4 clusters X, y = make_blobs(n_samples=300, centers=4, n_features=2, random_state=42) # Elbow method wcss = [] for i in range(1, 11): kmeans = KMeans(n_clusters=i, init='k-means++', max_iter=300, n_init=10, random_state=42) kmeans.fit(X) wcss.append(kmeans.inertia_) plt.plot(range(1, 11), wcss , c = 'black') plt.title('Elbow Method') plt.xlabel('Number of Clusters') plt.ylabel('WCSS') plt.show() # Silhouette score sil_scores = [] for i in range(2, 11): kmeans = KMeans(n_clusters=i, init='k-means++', max_iter=300, n_init=10, random_state=42) kmeans.fit(X) sil_scores.append(silhouette_score(X, kmeans.labels_)) plt.plot(range(2, 11), sil_scores , c = 'black') plt.title('Silhouette Score') plt.xlabel('Number of Clusters') plt.ylabel('Silhouette Score') plt.show()
Код генерирует образец набора данных с 2 функциями и 4 кластерами, используя функцию make_blobs
из scikit-learn. Затем он применяет алгоритм K-Means с различным количеством кластеров (от 1 до 10) для вычисления суммы квадратов внутри кластера (WCSS) для каждого количества кластеров. Затем строится метод локтя, чтобы визуализировать точку убывающей отдачи с точки зрения снижения WCSS.
Затем код применяет алгоритм K-Means с различным количеством кластеров (от 2 до 10) для вычисления оценки силуэта для каждого количества кластеров. Затем создается график оценки силуэта, чтобы визуализировать оптимальное количество кластеров на основе наивысшей оценки.
Диаграмма Вороного:
Диаграмма Вороного — это геометрическая диаграмма, которая делит плоскость на области в зависимости от расстояния до набора точек, называемых образующими. Каждая область содержит все точки, которые ближе к определенному генератору, чем к любому другому генератору.
import numpy as np from scipy.spatial import Voronoi, voronoi_plot_2d import matplotlib.pyplot as plt # Generate some random points points = np.random.rand(30, 2) # Compute the Voronoi diagram vor = Voronoi(points) # Plot the Voronoi diagram fig = voronoi_plot_2d(vor, show_vertices=False, line_colors='green', line_width=2, line_alpha=0.8, point_size=2) # Add the original points to the plot plt.scatter(points[:,0], points[:,1], color='black', s=20 , alpha = 0.6) # Add labels and title to the plot plt.xlabel('X-axis') plt.ylabel('Y-axis') plt.title('Voronoi Diagram of Random Points') # Set the aspect ratio to 'equal' and remove the frame plt.gca().set_aspect('equal', adjustable='box') plt.gca().spines['top'].set_visible(False) plt.gca().spines['right'].set_visible(False) plt.gca().spines['bottom'].set_linewidth(0.5) plt.gca().spines['left'].set_linewidth(0.5) plt.show()
import numpy as np import matplotlib.pyplot as plt from scipy.spatial import Voronoi, voronoi_plot_2d # generate random points points = np.random.rand(100, 2) # compute Voronoi diagram vor = Voronoi(points) # plot Voronoi diagram fig, ax = plt.subplots() voronoi_plot_2d(vor, ax=ax) plt.show()
Применения кластеризации K-средних:
Кластеризация K-средних — это широко используемый алгоритм обучения без учителя с несколькими реальными приложениями в различных областях. Вот несколько примеров:
- Сегментация клиентов. Кластеризация K-средних может использоваться для разделения клиентов на разные группы на основе их покупательского поведения, демографических данных и других характеристик. Эта информация может использоваться предприятиями для адаптации своих маркетинговых стратегий и продуктов в соответствии с потребностями каждой группы.
- Сжатие изображений. Кластеризация K-средних может использоваться для сжатия изображений путем группировки похожих пикселей вместе и замены их центроидами. Это уменьшает количество цветов, необходимых для представления изображения, без потери деталей.
- Обнаружение аномалий. Кластеризация K-средних может выявлять аномалии в наборах данных, выявляя кластеры со значительно отличающимися характеристиками от остальных данных. Это может быть полезно при обнаружении мошенничества, сетевых вторжений или других аномальных событий.
Преимущества кластеризации K-средних:
- Это быстрый и эффективный алгоритм, который может обрабатывать большие наборы данных.
- Его легко реализовать, и он широко используется благодаря множеству библиотек и инструментов для его поддержки.
- Он может быть эффективным при выявлении относительно простых и четко определенных кластеров в данных.
Ограничения кластеризации K-средних:
- Предполагается, что кластеры имеют сферическую форму и одинаковый размер, что лишь иногда может иметь место в реальных данных.
- Он чувствителен к начальным центроидам кластера и может сходиться к локальным минимумам вместо глобального минимума.
- Он хорошо работает только с наборами данных различной плотности или неправильной формы, поскольку может создавать кластеры, которые не точно представляют данные.
По сравнению с другими алгоритмами кластеризации K-Means имеет некоторые преимущества и ограничения:
- По сравнению с иерархической кластеризацией K-Means быстрее и масштабируемее, но требует заранее указать количество кластеров.
- По сравнению с кластеризацией на основе плотности, такой как DBSCAN, K-средние проще в реализации и хорошо работают с большими наборами данных, но могут возникнуть проблемы с наборами данных с различной плотностью.
- По сравнению со спектральной кластеризацией K-средние быстрее и масштабируемее, но могут плохо работать с нелинейно разделимыми данными.
Будущая работа:
Возможные направления дальнейших исследований и разработок кластеризации K-средних включают повышение ее эффективности и масштабируемости для больших наборов данных, разработку новых показателей расстояния для обработки неевклидовых данных и интеграцию ее с другими алгоритмами машинного обучения для повышения ее производительности в различных приложениях.