В случае связей кластеризация k-средних случайным образом назначит неоднозначную точку кластеру.(Это основано на реализации R кластеризации k-средних kmeans.)
Начнем с загрузки необходимых библиотек R
library(broom)
library(tidyverse)
. В этом примере мы будем использовать измерения Petal.Length и Petal.Width из набора данных iris, а для простоты исключимИзмерения "virginica", так что измерения "setosa" и "versicolor" образуют две наши группы.
df <- iris %>%
filter(Species != "virginica") %>%
select(starts_with("Petal"), Species)
Теперь мы используем кластеризацию k-средних с k = 2 и присваиваемметка кластера для каждого (Petal.Length, Petal.Width) измерения;поскольку присвоение какой-либо группы "1", а какой - "2" является случайным, мы используем фиксированное начальное число для воспроизводимости.
set.seed(2018)
kcl <- kmeans(df %>% select(-Species), 2)
df <- augment(kcl, df)
Мы показываем диаграмму рассеяния Petal.Length против Petal.Width;известные Species метки показаны разными цветами, а предполагаемая ассоциация кластеров - разными символами.
ggplot(df, aes(Petal.Length, Petal.Width, colour = Species)) +
geom_point(aes(shape = .cluster), size = 3)
Давайте вручную вычислим внутрикластерную сумму квадратов парных расстояний;так как это нам понадобится и позже, мы создадим функцию calculate_d.
calculate_d <- function(df) {
df %>%
select(.cluster, Petal.Length, Petal.Width) %>%
group_by(.cluster) %>%
nest() %>%
mutate(dist = map_dbl(data, ~sum(as.matrix(dist(.x)^2)) / (2 * nrow(.x)))) %>%
pull(dist)
}
calculate_d(df)
#[1] 2.0220 12.7362
Обратите внимание, что расстояния идентичны сумме квадратов в пределах кластера (WCSS)
kcl$withinss
#[1] 2.0220 12.7362
Теперь давайте добавим новое измерение, которое имеет одинаковое евклидово расстояние от обоих центров кластеров: для этого мы выберем точку, которая находится точно посередине между обоими центрами кластеров, если вы подключитесьих по прямой линии.Все, что нам нужно, это немного базовой тригонометрии для построения этой точки:
z <- kcl$centers[2, ] - kcl$center[1, ]
theta <- atan(z[2] / z[1])
dy <- sin(theta) * dist(kcl$centers) / 2
dx <- cos(theta) * dist(kcl$centers) / 2
x <- as.numeric(kcl$centers[1, 1] + dx)
y <- as.numeric(kcl$centers[1, 2] + dy)
Мы сохраняем нашу новую точку вместе с двумя центрами кластеров в новом data.frame.Первые две строки задают положение кластера «1» и «2», а третья строка содержит нашу новую точку.
df2 <- bind_rows(as.data.frame(kcl$centers), c(Petal.Length = x, Petal.Width = y))
Давайте покажем новую точку вместе с центрами кластеров поверх нашей (Petal.Length, Petal.Width) измерения.
df2 <- bind_rows(as.data.frame(kcl$centers), c(Petal.Length = x, Petal.Width = y))
ggplot(df, aes(Petal.Length, Petal.Width)) +
geom_point(aes(colour = Species, shape = .cluster), size = 3) +
geom_point(data = df2, aes(Petal.Length, Petal.Width), size = 4)
Мы подтверждаем, что квадрат евклидова расстояния между новой точкой и каждым центром кластера равендействительно то же самое;Для этого мы вычисляем попарные расстояния нашей новой точки «3» до центров кластеров «1» и «2»:
as.matrix(dist(df2))[, 3]
# 1 2 3
#1.4996 1.4996 0.0000
Теперь давайте добавим нашу новую точку к(Petal.Length, Petal.Width) измерений и вычислите внутри кластера сумму квадратов парных расстояний, сначала с назначением нашей новой точки для кластера "1", а затем с назначением нашей новой точки для кластера "2".
# Add new point and assign to cluster "1"
df.1 <- df %>%
bind_rows(cbind.data.frame(
Petal.Length = x,
Petal.Width = y,
Species = factor("setosa", levels = levels(df$Species)),
.cluster = factor(1, levels = 1:2)))
calculate_d(df.1)
#[1] 4.226707 12.736200
# Add new point and assign to cluster "2"
df.2 <- df %>%
bind_rows(cbind.data.frame(
Petal.Length = x,
Petal.Width = y,
Species = factor("versicolor", levels = levels(df$Species)),
.cluster = factor(2, levels = 1:2)))
calculate_d(df.2)
#[1] 2.02200 14.94091
Обратите внимание на то, что квадратичные попарные расстояния внутри кластера различны, даже если новая точка имеет одинаковые расстояния от любого центра кластера.Однако обратите внимание также, что сумма квадратов парных расстояний внутри кластера одинакова!
sum(calculate_d(df.1))
#[1] 16.96291
sum(calculate_d(df.2))
#[1] 16.96291
identical(sum(calculate_d(df.2)), sum(calculate_d(df.1)))
# [1] TRUE
Чтобы показать, что kmeans назначает новую точкув случайном порядке для любого кластера мы повторно кластеризируем данные.Для этого мы определяем вспомогательную функцию, которая возвращает соответствующую Species новой точки после кластеризации k-средних.
kmeans_cluster_data <- function(df) {
kcl <- kmeans(df %>% select(-Species), 2)
df <- augment(kcl, df)
map_cluster_to_Species <- df[1:(nrow(df) - 1), ] %>%
count(Species, .cluster) %>%
split(., .$.cluster)
map_cluster_to_Species[[
df[nrow(df), ] %>%
pull(.cluster) %>%
as.character()]]$Species %>% as.character()
}
Теперь мы неоднократно кластеризовываем одни и те же данные 100 раз.
bind_cols(
Iteration = 1:100,
Species = map_chr(1:100, ~kmeans_cluster_data(df.1 %>% select(-.cluster)))) %>%
ggplot(aes(Iteration, Species, group = 1)) +
geom_line() +
labs(title = "Assignment of new point to group")
Обратите внимание, как новая точка присваивается произвольной группе Species.