Реализация кластеризации методом k-средних на Python (с визуализацией)

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

Существует множество алгоритмов кластеризации, однако ниже будет рассмотрен метод k-средних, так как он является наиболее лаконичным и простым для понимания.

Кластеризация методом k-средних:

Исходной задачей будет распределение произвольного количества n-мерных точек по k кластерам.

1. Случайным образом создаются k точек, в дальнейшем будем называть их центрами кластеров;

2. Для каждой точки ставится в соответствии ближайший к ней центр кластера;

3. Вычисляются средние арифметические точек, принадлежащих к определённому кластеру. Именно эти значения становятся новыми центрами кластеров;

4. Шаги 2 и 3 повторяются до тех пор, пока пересчёт центров кластеров будет приносить плоды. Как только высчитанные центры кластеров совпадут с предыдущими, алгоритм будет окончен.

Приступим к реализации алгоритма:

Исходные данные алгоритма:

• n — количество строк;

• k — количество кластеров;

• dim — размерность точек (пространства).

Выходные данные алгоритма:

• cluster — двумерный массив размерностью dim * k, содержащий k точек — центры кластеров;

• cluster_content — массив, содержащий в себе k массивов — массивов точек принадлежащих соответствующему кластеру.

def clusterization(array, k): n = len(array)  dim = len(array[0])    cluster = [[0 for i in range(dim)] for q in range(k)]  cluster_content = [[] for i in range(k)]  for i in range(dim): for q in range(k): cluster[q][i] = random.randint(0, max_cluster_value)  cluster_content = data_distribution(array, cluster)

Переменные заданы. Первичные центры кластеров созданы с помощью библиотеки random(стр. 9 — 11) max_claster_value — константа задающая примерные границы исходного множества;

При помощи функции data_ditribution() произведено первичное распределения точек по кластерам (стр. 13). Рассмотрим эту функцию подробнее:

def data_distribution(array, cluster):  cluster_content = [[] for i in range(k)]  for i in range(n): min_distance = float('inf') situable_cluster = -1 for j in range(k): distance = 0 for q in range(dim): distance += (array[i][q]-cluster[j][q])**2  distance = distance**(1/2) if distance < min_distance: min_distance = distance situable_cluster = j  cluster_content[situable_cluster].append(array[i])  return cluster_content

Для каждой строчки (стр. 5) высчитывается расстояние до каждого центра кластеров. Здесь применяется стандартный алгоритм:

1. За начальное кратчайшее расстояние (min_distance) берётся несоизмеримо большое со значениями точек число;

2. Затем происходит вычисление расстояния до центра каждого кластера;

   

3. Если вычисленное расстояние меньше минимального, то минимальное расстояние приравнивается к вычисленному и точка привязывается к этому кластеру (situable_cluster);

4. После обработки точки, в массив cluster_content в выбранный кластер (situable_cluster) кластер вкладывается значение точки.

Функция возвращает массив cluster_content.

В дальнейшем, как и полагается, данная последовательность действий обращается в цикл:

privious_cluster = copy.deepcopy(cluster) while 1: cluster = cluster_update(cluster, cluster_content, dim) cluster_content = data_distribution(array, cluster) if cluster == privious_cluster: break  privious_cluster = copy.deepcopy(cluster)

Данный цикл целостным образом описывает шаг 4 из описании алгоритм k-средних (см. выше).

После распределения точек по центрам кластеров происходит перераспределение уже центров кластеров по привязанным к ним точкам (стр. 2). Рассмотрим функцию cluster_content() подробнее:

def cluster_update(cluster, cluster_content, dim): k = len(cluster) for i in range(k): #по i кластерам for q in range(dim): #по q параметрам updated_parameter = 0 for j in range(len(cluster_content[i])):  updated_parameter += cluster_content[i][j][q] if len(cluster_content[i]) != 0: updated_parameter = updated_parameter / len(cluster_content[i]) cluster[i][q] = updated_parameter return cluster

Для каждого кластера, для каждого из n измерений вычисляется новое значения с помощью незамысловатого среднего арифметического: стр. 8-9 — складываются все значения; стр. 11-12 — сумма делится на количество точек в кластере; стр. 13 — кластер принимает обновлённое значение.

На данном месте алгоритм заканчивает свою работу. Полный алгоритм выглядит следующим образом:

def clusterization(array, k): n = len(array)   dim = len(array[0])    cluster = [[0 for i in range(dim)] for q in range(k)]  cluster_content = [[] for i in range(k)]   for i in range(dim): for q in range(k): cluster[q][i] = random.randint(0, max_cluster_value)   cluster_content = data_distribution(array, cluster)  privious_cluster = copy.deepcopy(cluster) while 1: cluster = cluster_update(cluster, cluster_content, dim) cluster_content = data_distribution(array, cluster) if cluster == privious_cluster: break privious_cluster = copy.deepcopy(cluster)

Перейдём к визуализации:

Визуализируем результат алгоритма для 3-х и 2-х мерного исходных пространств. Воспользуемся библиотекой mathplotlib:

import matplotlib.pyplot as plt from mpl_toolkits import mplot3d import numpy as np

Визуализация для 2-х мерного пространства происходит следующим образом:

def visualisation_2d(cluster_content):  k = len(cluster_content) plt.grid()  plt.xlabel("x")     plt.ylabel("y")  for i in range(k):  x_coordinates = [] y_coordinates = [] for q in range(len(cluster_content[i])): x_coordinates.append(cluster_content[i][q][0]) y_coordinates.append(cluster_content[i][q][1]) plt.scatter(x_coordinates, y_coordinates) plt.show()

Grid() — создание сетки. xlabel(), ylabel() — названия осей. Затем в массивы, соответствующие осям вкладываются значения точек. После такой операции для каждого кластера вызывается функция scatter() — разброс точек по плоскости. В конце вызывается функция отображения — show().

Аналогичным образом визуализируется результат алгоритма для 3-х мерного пространства:

def visualisation_3d(cluster_content):  ax = plt.axes(projection="3d") plt.xlabel("x")     plt.ylabel("y")  k = len(cluster_content)  for i in range(k): x_coordinates = [] y_coordinates = [] z_coordinates = [] for q in range(len(cluster_content[i])): x_coordinates.append(cluster_content[i][q][0]) y_coordinates.append(cluster_content[i][q][1]) z_coordinates.append(cluster_content[i][q][2]) ax.scatter(x_coordinates, y_coordinates, z_coordinates) plt.show()

Визуализация пошагово, с отображением центров: https://drive.google.com/drive/folders/10WLlqfw__Bqr3ERjzZyMjk3ZNOIPPad2?usp=sharing

Таким образом, мы выполнили необходимые и достаточные условия для анализа и реализации кластеризации методом k-средних.