Кластеризация с помощью метода k-средних на Python

В области анализа данных широко распространена задача разделения множества объектов на подмножества таким образом, чтобы все объекты каждого подмножества имели больше сходства друг с другом, чем с объектами других подмножеств.

Данная задача находит широкое практическое применение. Например, в области медицины алгоритм кластеризации может помочь идентифицировать центры клеток на изображении группы клеток. Используя GPS-данные мобильного устройства, можно определить наиболее посещаемые пользователем места в пределах определенной территории.

Для любого набора данных, которым не присвоены метки, кластеризация помогает обнаружить наличие некоторой структуры, указывающей на то, что данные поддаются группировке.

Математическая база

Алгоритм k-средних принимает в качестве входных данных набор данных X, содержащий N точек, а также параметр K, задающий требуемое количество кластеров. На выходе получаем набор из K центроидов кластеров, кроме того, всем точкам множества X присваиваются метки, относящие их к определенному кластеру. Все точки в пределах данного кластера расположены ближе к своему центроиду, чем к любому другому центроиду.

Математическое выражение для K кластеров Ck и K центроидов μk имеет вид:

Безымянный

Алгоритм Ллойда

К сожалению, задача является NP-сложной. Тем не менее, существует итерационный метод, известный как алгоритм Ллойда, который сходится (хотя и к локальному минимуму) в пределах небольшого количества итераций. В рамках данного алгоритма поочередно выполняются две операции. (1) Как только набор центроидов μk становится доступен, каждый кластер обновляется таким образом, чтобы содержать точки ближайшие к данному центроиду. (2) Как только набор кластеров становится доступен, каждый центроид пересчитывается, как среднее значение всех точек, принадлежащих данному кластеру.

1

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. Каждый кластер обозначен собственным цветом.

p_N100_K7

Начальная конфигурация точек для алгоритма получена следующим образом:

import random
def init_board(N):
    X = np.array([(random.uniform(-1, 1), random.uniform(-1, 1)) for i in range(N)])
    return X

В случае конфигурации с вдвое большим количеством точек и тремя кластерами алгоритму обычно требуется больше итераций, чтобы сойтись.

p_N200_K3

Очевидно, что набор сгенерированных случайным образом точек не обладает естественной кластерной структурой. С целью немного усложнить задачу, модифицируем функцию, генерирующую исходные точки, чтобы получить более интересную структуру. Следующая функция создает заданное количество кластеров с гауссовским распределением и случайной дисперсией:

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 итераций.

p_N200_K3_G

Если целевое распределение имеет разрозненную структуру, и используется только один экземпляр алгоритма Ллойда, возникает опасность того, что полученный локальный минимум не является оптимальным решением. Это показано в примере ниже, где начальные данные имеют островершинное гауссовское распределение:

p_N100_K9_G

Желтый и черный центроиды представляют по два различных кластера каждый, в то время как оранжевый, красный и синий центроиды теснятся в пределах одного кластера вследствие неудачной случайной инициализации. В подобных случаях помогает более рациональный выбор начальных кластеров.

Чтобы завершить наш настольный эксперимент по кластеризации с помощью метода k-средних, давайте рассмотрим ситуацию, когда пространство данных плотно заполнено:

p_N2000_K15_

Алгоритм k-средних разделяет данные подобно диаграмме Вороного, полученной на основе K центроидов. И это, безусловно, очень красиво!

Заключение

Двухэтапная Ллойдовская реализация алгоритма k-средних позволяет сгруппировать данные в кластеры, представленные центроидами. Эта технология применяется во многих областях машинного обучения – от задач обучения без учителя до задач понижения размерности.

Общая задача кластеризации является NP-сложной, но итерационный алгоритм всегда сходится, хотя и к локальному минимуму. Правильная инициализация центроидов имеет существенное значение. Кроме того, данный алгоритм не предоставляет информацию о том, какое значение K является оптимальным. Это необходимо выяснить с помощью других методов.

По материалам: Data Science Lab

1 комментарий

  1. johngrape:

    Крутые анимашки 😉

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =