В области анализа данных широко распространена задача разделения множества объектов на подмножества таким образом, чтобы все объекты каждого подмножества имели больше сходства друг с другом, чем с объектами других подмножеств.
Данная задача находит широкое практическое применение. Например, в области медицины алгоритм кластеризации может помочь идентифицировать центры клеток на изображении группы клеток. Используя GPS-данные мобильного устройства, можно определить наиболее посещаемые пользователем места в пределах определенной территории.
Для любого набора данных, которым не присвоены метки, кластеризация помогает обнаружить наличие некоторой структуры, указывающей на то, что данные поддаются группировке.
Математическая база
Алгоритм k-средних принимает в качестве входных данных набор данных X, содержащий N точек, а также параметр K, задающий требуемое количество кластеров. На выходе получаем набор из K центроидов кластеров, кроме того, всем точкам множества X присваиваются метки, относящие их к определенному кластеру. Все точки в пределах данного кластера расположены ближе к своему центроиду, чем к любому другому центроиду.
Математическое выражение для K кластеров Ck и K центроидов μk имеет вид:
Алгоритм Ллойда
К сожалению, задача является NP-сложной. Тем не менее, существует итерационный метод, известный как алгоритм Ллойда, который сходится (хотя и к локальному минимуму) в пределах небольшого количества итераций. В рамках данного алгоритма поочередно выполняются две операции. (1) Как только набор центроидов μk становится доступен, каждый кластер обновляется таким образом, чтобы содержать точки ближайшие к данному центроиду. (2) Как только набор кластеров становится доступен, каждый центроид пересчитывается, как среднее значение всех точек, принадлежащих данному кластеру.
Двухэтапная процедура повторяется, пока кластеры и центроиды не перестанут изменяться. Как уже было сказано, сходимость гарантируется, но решение может представлять собой локальный минимум. На практике, алгоритм выполняется несколько раз, и результаты усредняются. Для получения набора начальных центроидов можно использовать несколько методов, например центроиды можно задать случайным образом.
Ниже представлена простая реализация на Python алгоритма Ллойда для выполнения кластеризации с помощью метода k-средних:
import numpy as npdef 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 clustersdef reevaluate_centers(mu, clusters): newmu = [] keys = sorted(clusters.keys()) for k in keys: newmu.append(np.mean(clusters[k], axis = 0)) return newmudef 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 randomdef 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
Крутые анимашки 😉