Практическое руководство
Почему начальные центроиды кластера в k-средних влияют на сгенерированный окончательный кластер?
Различные начальные центроиды кластера повлияют на разные результаты в алгоритме кластера k-средних — как определить лучший?
Алгоритм кластеризации k-средних является таким простым алгоритмом в неконтролируемой (кластеризации) реализации. Сформулировать алгоритм в ручном расчете с помощью математики тоже достаточно просто.
Однако за своими преимуществами k-means имеет ограничение в правиле выбора центроидов кластера. Он слишком чувствителен к начальным центроидам кластера — когда мы выбираем разные начальные значения, результат будет другим. Это наводит нас на неверный вывод о кластере.
В этой короткой статье вы поймете, как начальные центроиды кластера могут повлиять на сгенерированные конечные кластеры. В последней статье я расскажу вам подход к решению этой проблемы. Итак, продолжайте читать, и я надеюсь, вам понравится эта тема!
Будь счастлив!
Базовая теория k-средних (это то, что вы должны знать!)
k-means — это метод обучения без учителя, который используется для группировки данных со схожими характеристиками. Он включает в себя расчет евклидова расстояния между каждой точкой данных. Предположим, у нас есть два вектора: x и y. Евклидово расстояние можно измерить по следующей формуле.
Алгоритм кластеризации k-средних включает следующие шаги для создания кластеров следующим образом.
- Определяем количество кластеров (k) — обычно мы используем метод локтя или субъективную оценку аналитика.
- Выберите k точек для начальных центроидов кластера — из точек данных случайным образом выберите k точек, которые будут начальными центроидами кластера.
- Рассчитать расстояние между точками и центроидами — выполняется алгоритм k-средних, в котором на каждой итерации оценивается расстояние между точками данных и центроидами.
- Пересчитать центроиды — каждая итерация создает новые элементы в кластерах. Это означает вычисление новых центроидов путем деления общего количества точек данных на количество элементов в кластерах.
- Критерии остановки — итерация останавливается, когда элементы в кластерах стабильны (есть какие-либо изменения по сравнению с предыдущей итерацией).
Почему центроиды начальных кластеров в k-средних влияют на конечные кластеры?
Чтобы ответить на поставленный выше вопрос, лучше взглянем на следующую иллюстрацию. Он показывает нам механизм работы оптимизации. Зеленая точка — это начальное решение — начальные центроиды кластера дают начальное решение. Алгоритм k-средних работает, и центроиды кластера переназначаются и пересчитываются до тех пор, пока не будут выполнены критерии остановки. В этом случае мы находимся в синей точке — оптимальное локальное решение.
Если алгоритм продолжится, он попытается найти другое решение, пока не будут выполнены все альтернативы, мы получим оптимальное глобальное решение. Это глобальные средства не только для определенной области, но и для всей области.
Моделирование того, как k-средние получают окончательные центроиды кластера
Есть несколько модулей, которые должны быть правильно установлены в нашей системе, чтобы продемонстрировать симуляцию. Они следующие.
pandas— модуль для работы с даннымиnumpy— модуль для расчета линейной алгебры и простой статистикиsklearn— модуль для создания фиктивных данных и выполнения алгоритма кластеризации K-среднихplotnine— модуль для визуализации данных с использованием грамматики графикиggplot2random— модуль рандомизации чиселwarnings— модуль для игнорирования любых предупреждений при выполнении Python-скриптов
# Data manipulation
import pandas as pd
# Linear algebra calculation
import numpy as np
# Generate data
from sklearn.datasets import make_blobs
# kmeans clustering
from sklearn.cluster import KMeans
# Data viz
import plotnine
from plotnine import *
# Random numbers
import random
# Ignore warning
import warnings
warnings.filterwarnings('ignore')
Модуль sklearn предоставляет функцию make_blobs для создания фиктивных данных. Путем определения количества кластеров в аргументе centers и количества данных в n_samples. Мы также можем определить стандартное отклонение кластеров в cluster_std.
# Generate dummy data
features, clusters = make_blobs(
n_samples = 2000,
n_features = 2,
centers = 3,
cluster_std = 0.8,
shuffle = True,
random_state = 9
)
Переменная features содержит два столбца для 2000 фиктивных данных, а clusters — для меток кластеров.
# Concate these arrays array = np.column_stack([features, clusters]) array
Из массива мы преобразуем его во фрейм данных df, чтобы можно было легко выполнять манипуляции.
# Data frame
df = pd.DataFrame(data = array,
columns = [
'Feature 1',
'Feature 2',
'Cluster'
]
)
# Show data frame
print('Dimension: {} rows and {} columns'.format(
len(df),
len(df.columns))
)
df = df.astype({'Cluster': object})
df.head()
Центроиды рассчитываются путем деления суммы feature 1 и feature 2 within-cluster на количество элементов в кластерах.
# Centroids
df_centroids = df.groupby(['Cluster']).mean().reset_index().rename(columns = {
'Feature 1': 'Centroid Feature 1',
'Feature 2': 'Centroid Feature 2'
}
).astype({'Cluster': object})
df_centroids
Используя функцию make_blobs, мы уже установили для random_state значение 9. Таким образом, мы получим аналогичный результат в фиктивных данных. Данные визуализируются с помощью plotnine и визуально мы нашли кластеры. К счастью, между кластерами нет перекрывающихся данных.
# Scatterplot
plotnine.options.figure_size = (8, 4.8)
(
ggplot()+
geom_point(aes(x = 'Feature 1',
y = 'Feature 2',
color = 'Cluster'),
data = df)+
labs(title = 'Dummy Data for kmeans Clustering')+
xlab('Feature 1')+
ylab('Feature 2')+
scale_color_manual(name = 'Clusters',
values = [
'#80797c',
'#981220',
'#D4AF37'
],
labels = [
'Cluster 1',
'Cluster 2',
'Cluster 3'
]
)+
theme_minimal()
)
Как мы знаем, начальные центроиды кластера в k-средних влияют на полученные конечные центроиды. Чтобы продемонстрировать это, мы создадим три пары начальных центроидов кластера. Они исходят из минимума и максимума feature 1 и feature 2.
# Feature 1
feature1_min = df['Feature 1'].min()
feature1_max = df['Feature 1'].max()
print('Feature 1 has minimum {} and maximum {}'.format(
feature1_min, feature1_max
)
)
# Feature 2
feature2_min = df['Feature 2'].min()
feature2_max = df['Feature 2'].max()
print('Feature 2 has minimum {} and maximum {}'.format(
feature2_min, feature2_max
)
)
Начальные центроиды для трех кластеров генерируются с использованием равномерного распределения, в котором нижний предел является его минимумом, а верхний предел — его максимумом (feature 1 и feature 2). После рандомизации у нас есть массив 3x2, который представляет собой три пары начальных центроидов кластера.
# Initial centroids
cent_feature1 = [random.uniform(feature1_min, feature1_max) for _ in range(3)]
cent_feature2 = [random.uniform(feature2_min, feature2_max) for _ in range(3)]
print('Centroid for feature 1: {}'.format(cent_feature1))
print('Centroid for feature 2: {}'.format(cent_feature2))
# Merge into array
centroid_init = np.array((cent_feature1, cent_feature2)).transpose()
print('\nInitial centroid:\n {}'.format(centroid_init))
Чтобы применить метод k-средних к фиктивным данным, sklearn предоставил функцию KMeans. Задаем количество кластеров, случайное состояние (оно влияет на рандомизацию), начальные центроиды кластера и количество инициализаций.
Примечание — на самом деле KMeans предоставил самый быстрый подход к выбору центроидов кластера. Это kmeans++, но в этом уроке мы продемонстрируем, как работает ручной расчет k-средних.
# Create a clustering model
kmeans = KMeans(
n_clusters = 3,
random_state = 0,
init = centroid_init,
n_init = 50
)
# Fit the kmeans clustering model
kmeans.fit(df[['Feature 1', 'Feature 2']])
Команда kmeans.cluster_centers_ распечатает окончательные центроиды кластера.
# Centroids kmeans.cluster_centers_
Технически алгоритм k-средних, который мы использовали, требует 5 итераций для сходимости. Для каждой итерации мы будем хранить и визуализировать сгенерированные центроиды кластера.
# Number of iterations
n_iter = kmeans.n_iter_
print('kmeans clustering algorithm needs {} iteration to converge'.format(n_iter))
# Output
kmeans clustering algorithm needs 5 iteration to converge
К сожалению, функция KMeans не предоставляет результат для каждой итерации. Итак, для их хранения нам нужен цикл, использующий одно и то же случайное состояние. Важно отметить, что в каждой итерации или цикле max_iter устанавливайте в индекс + 1. Далее индекс ходит от 0 до 5.
Примечание. помните, что предыдущему k-среднему требуется 5 итераций для сходимости.
# Get centroids each iterations - how kmeans works
centroids = {}
for i in range(n_iter):
# Apply kmeans
kmeans = KMeans(
n_clusters = 3,
random_state = 0,
init = centroid_init,
max_iter = i + 1
)
kmeans.fit(df[['Feature 1', 'Feature 2']])
centroid = kmeans.cluster_centers_
# Store the centroids
centroids.update({'Iteration {}'.format(i + 1): centroid})
# Array of centroids
centroids
centroids хранит центроиды кластера для каждой итерации (в массиве). Чтобы визуализировать кластер с помощью plotnine, его необходимо преобразовать во фрейм данных.
# Transpose the array
feature_1 = []
feature_2 = []
iterations = []
for key in list(centroids.keys()):
for i, j in centroids[key]:
feature_1.append(i)
feature_2.append(j)
iterations.append(key)
# Create a data frame
df_iteration = pd.DataFrame(
{
'Centroid Feature 1': feature_1,
'Centroid Feature 2': feature_2,
'Cluster': [
'Cluster 1',
'Cluster 2',
'Cluster 3'
] * (len(feature_1) // 3),
'Iteration': iterations
}
)
# Show data frame
df_iteration.head()
Синие кресты — это фактические центроиды кластера, а черные точки — центроиды кластера в 5 итерациях. Центроиды кластера в итерациях визуально разбросаны. Это делает вывод неверным. На 5-й итерации алгоритм k-средних удовлетворяет критерию остановки, хотя он еще не соответствует глобальным оптимумам.
Алгоритм кластеризации k-средних будет остановлен, когда он соответствует критериям остановки. Это приводит нас к оптимальному локальному решению вместо оптимального глобального решения.
# Scatterplot
plotnine.options.figure_size = (8, 4.8)
(
ggplot()+
geom_point(aes(x = 'Feature 1',
y = 'Feature 2',
color = 'Cluster'),
data = df)+
geom_point(aes(x = 'Centroid Feature 1',
y = 'Centroid Feature 2'),
color = '#000000',
size = 3,
show_legend = False,
data = df_iteration)+
geom_point(aes(x = 'Centroid Feature 1',
y = 'Centroid Feature 2'),
shape = 'X',
color = '#0000FF',
size = 5,
show_legend = False,
data = df_centroids)+
labs(title = 'Dummy Data for kmeans Clustering')+
xlab('Feature 1')+
ylab('Feature 2')+
scale_color_manual(name = 'Clusters',
values = [
'#80797c',
'#981220',
'#D4AF37'
],
labels = [
'Cluster 1',
'Cluster 2',
'Cluster 3'
]
)+
theme_minimal()
)
Моделирование того, как рандомизация влияет на сгенерированные кластеры
Предыдущее моделирование, которое пыталось визуализировать каждую итерацию при поиске конечных центроидов кластера, выполнено, в этом втором моделировании мы попытаемся визуализировать конечные центроиды кластера для 50 различных начальных центроидов кластера. Он призван показать нам, как начальные центроиды кластера могут привести нас к различным решениям.
Отмечено, что в каждом начальном кластерном центроиде мы будем хранить эту максимальную итерацию для сходимости.
# Get centroids each iterations - with randomization
array = {}
for n_random in range(50):
# Initial centroids
cent_feature1 = [random.uniform(feature1_min, feature1_max) for _ in range(3)]
cent_feature2 = [random.uniform(feature2_min, feature2_max) for _ in range(3)]
# Merge into array
centroid_init = np.array((cent_feature1, cent_feature2)).transpose()
centroids = {}
# Apply kmeans
kmeans = KMeans(
n_clusters = 3,
random_state = 0,
init = centroid_init,
max_iter = 50
)
kmeans.fit(df[['Feature 1', 'Feature 2']])
centroid = kmeans.cluster_centers_
# Store the centroids
centroids.update({'Max Iteration': kmeans.n_iter_})
centroids.update({'Centroid': centroid})
array_new = {'Random {}'.format(n_random + 1): centroids}
array.update(array_new)
# Array of centroids
array
df_random содержит 5 столбцов. Они следующие.
Centroid Feature 1— точки центроида для объекта 1Centroid Feature 2— точки центроида для объекта 2Cluster— содержит ярлыки для 3 кластеров (кластер 1, кластер 2, кластер 3)Max Iteration— максимальная итерация для сходимости k-среднихRandom— содержит метки для 50 рандомизаций.
# Transpose the array
feature_1 = []
feature_2 = []
repetition = []
randoms = []
for key_1 in list(array.keys()):
for i, j in array[key_1]['Centroid']:
feature_1.append(i)
feature_2.append(j)
randoms.append(key_1)
repetition.append(array[key_1]['Max Iteration'])
# Create a data frame
df_random = pd.DataFrame(
{
'Centroid Feature 1': feature_1,
'Centroid Feature 2': feature_2,
'Cluster': [
'Cluster 1',
'Cluster 2',
'Cluster 3'
] * (len(feature_1) // 3),
'Max Iteration': repetition,
'Random': randoms
}
)
# Show data frame
df_random.head()
Следующий график рассеяния показывает нам, что конечные центроиды кластера для разных начальных значений приведут нас к ошибочному выводу. Черная точка между кластерами 1 и 3 полностью беспокоит результат. Это заставляет точки данных кластера перекрываться. Более того, посмотрите на кластер 3, последние центроиды кластера разбросаны!
# Scatterplot
plotnine.options.figure_size = (8, 4.8)
(
ggplot()+
geom_point(aes(x = 'Feature 1',
y = 'Feature 2',
color = 'Cluster'),
data = df)+
geom_point(aes(x = 'Centroid Feature 1',
y = 'Centroid Feature 2'),
color = '#000000',
size = 3,
show_legend = False,
data = df_random)+
geom_point(aes(x = 'Centroid Feature 1',
y = 'Centroid Feature 2'),
shape = 'X',
color = '#0000FF',
size = 5,
show_legend = False,
data = df_centroids)+
labs(title = 'Dummy Data for kmeans Clustering')+
xlab('Feature 1')+
ylab('Feature 2')+
scale_color_manual(name = 'Clusters',
values = [
'#80797c',
'#981220',
'#D4AF37'
],
labels = [
'Cluster 1',
'Cluster 2',
'Cluster 3'
]
)+
theme_minimal()
)
Вывод
Вывод в этой короткой статье о том, насколько чувствительны начальные центроиды кластера. Неправильное решение о том, как их определить, повлияет на конечный результат. В нашем лучшем сценарии последний кластер центроидов получит оптимальное глобальное решение, но как насчет других?
Затем предлагается один умный вопрос — существует ли какой-либо метод, который может гарантировать, что оптимальное глобальное решение будет найдено в конце кластерного анализа с использованием k-средних? Да, конечно. Распространенным подходом, который может обрабатывать оптимальное локальное решение, является генетический алгоритм. Его механизм пытается имитировать естественный отбор живых существ.
использованная литература
[1] scikit-learn Разработчики. KMeans (2020). https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html
