В области анализа данных широко распространена задача разделения множества объектов на подмножества таким образом, чтобы все объекты каждого подмножества имели больше сходства друг с другом, чем с объектами других подмножеств.
Данная задача находит широкое практическое применение. Например, в области медицины алгоритм кластеризации может помочь идентифицировать центры клеток на изображении группы клеток. Используя GPS-данные мобильного устройства, можно определить наиболее посещаемые пользователем места в пределах определенной территории.
Для любого набора данных, которым не присвоены метки, кластеризация помогает обнаружить наличие некоторой структуры, указывающей на то, что данные поддаются группировке.
Математическая база
Алгоритм k-средних принимает в качестве входных данных набор данных X, содержащий N точек, а также параметр K, задающий требуемое количество кластеров. На выходе получаем набор из K центроидов кластеров, кроме того, всем точкам множества X присваиваются метки, относящие их к определенному кластеру. Все точки в пределах данного кластера расположены ближе к своему центроиду, чем к любому другому центроиду.
Математическое выражение для K кластеров Ck и K центроидов μk имеет вид:
Алгоритм Ллойда
К сожалению, задача является NP-сложной. Тем не менее, существует итерационный метод, известный как алгоритм Ллойда, который сходится (хотя и к локальному минимуму) в пределах небольшого количества итераций. В рамках данного алгоритма поочередно выполняются две операции. (1) Как только набор центроидов μk становится доступен, каждый кластер обновляется таким образом, чтобы содержать точки ближайшие к данному центроиду. (2) Как только набор кластеров становится доступен, каждый центроид пересчитывается, как среднее значение всех точек, принадлежащих данному кластеру.
Двухэтапная процедура повторяется, пока кластеры и центроиды не перестанут изменяться. Как уже было сказано, сходимость гарантируется, но решение может представлять собой локальный минимум. На практике, алгоритм выполняется несколько раз, и результаты усредняются. Для получения набора начальных центроидов можно использовать несколько методов, например центроиды можно задать случайным образом.
Ниже представлена простая реализация на Python алгоритма Ллойда для выполнения кластеризации с помощью метода k-средних:
import
numpy as np
def
cluster_points(X, mu):
clusters
=
{}
for
x
in
X:
bestmukey
=
min
([(i[
0
], np.linalg.norm(x
-
mu[i[
0
]])) \
for
i
in
enumerate
(mu)], key
=
lambda
t:t[
1
])[
0
]
try
:
clusters[bestmukey].append(x)
except
KeyError:
clusters[bestmukey]
=
[x]
return
clusters
def
reevaluate_centers(mu, clusters):
newmu
=
[]
keys
=
sorted
(clusters.keys())
for
k
in
keys:
newmu.append(np.mean(clusters[k], axis
=
0
))
return
newmu
def
has_converged(mu, oldmu):
return
(
set
([
tuple
(a)
for
a
in
mu])
=
=
set
([
tuple
(a)
for
a
in
oldmu])
def
find_centers(X, K):
# Initialize to K random centers
oldmu
=
random.sample(X, K)
mu
=
random.sample(X, K)
while
not
has_converged(mu, oldmu):
oldmu
=
mu
# Assign all points in X to clusters
clusters
=
cluster_points(X, mu)
# Reevaluate centers
mu
=
reevaluate_centers(oldmu, clusters)
return
(mu, clusters)
Кластеризация в действии
Давайте рассмотрим алгоритм в действии! В наборе, состоящем из 100 случайных точек на плоскости, с помощью функции k-средних выделим 7 кластеров. Алгоритм сходится за 7 итераций при задании начальных центроидов случайным образом. На расположенных ниже диаграммах точки представляют собой целевые точки из множества X, а звезды – центроиды кластеров μk. Каждый кластер обозначен собственным цветом.
Начальная конфигурация точек для алгоритма получена следующим образом:
import
random
def
init_board(N):
X
=
np.array([(random.uniform(
-
1
,
1
), random.uniform(
-
1
,
1
))
for
i
in
range
(N)])
return
X
В случае конфигурации с вдвое большим количеством точек и тремя кластерами алгоритму обычно требуется больше итераций, чтобы сойтись.
Очевидно, что набор сгенерированных случайным образом точек не обладает естественной кластерной структурой. С целью немного усложнить задачу, модифицируем функцию, генерирующую исходные точки, чтобы получить более интересную структуру. Следующая функция создает заданное количество кластеров с гауссовским распределением и случайной дисперсией:
def
init_board_gauss(N, k):
n
=
float
(N)
/
k
X
=
[]
for
i
in
range
(k):
c
=
(random.uniform(
-
1
,
1
), random.uniform(
-
1
,
1
))
s
=
random.uniform(
0.05
,
0.5
)
x
=
[]
while
len
(x) < n:
a, b
=
np.array([np.random.normal(c[
0
], s), np.random.normal(c[
1
], s)])
# Continue drawing points from the distribution in the range [-1,1]
if
abs
(a) <
1
and
abs
(b) <
1
:
x.append([a,b])
X.extend(x)
X
=
np.array(X)[:N]
return
X
Давайте рассмотрим набор данных, созданный следующим образом: X = init_board_gauss(200, 3). Чтобы найти 3 центроида требуется 7 итераций.
Если целевое распределение имеет разрозненную структуру, и используется только один экземпляр алгоритма Ллойда, возникает опасность того, что полученный локальный минимум не является оптимальным решением. Это показано в примере ниже, где начальные данные имеют островершинное гауссовское распределение:
Желтый и черный центроиды представляют по два различных кластера каждый, в то время как оранжевый, красный и синий центроиды теснятся в пределах одного кластера вследствие неудачной случайной инициализации. В подобных случаях помогает более рациональный выбор начальных кластеров.
Чтобы завершить наш настольный эксперимент по кластеризации с помощью метода k-средних, давайте рассмотрим ситуацию, когда пространство данных плотно заполнено:
Алгоритм k-средних разделяет данные подобно диаграмме Вороного, полученной на основе K центроидов. И это, безусловно, очень красиво!
Заключение
Двухэтапная Ллойдовская реализация алгоритма k-средних позволяет сгруппировать данные в кластеры, представленные центроидами. Эта технология применяется во многих областях машинного обучения – от задач обучения без учителя до задач понижения размерности.
Общая задача кластеризации является NP-сложной, но итерационный алгоритм всегда сходится, хотя и к локальному минимуму. Правильная инициализация центроидов имеет существенное значение. Кроме того, данный алгоритм не предоставляет информацию о том, какое значение K является оптимальным. Это необходимо выяснить с помощью других методов.
По материалам: Data Science Lab
Свежие комментарии