Реализация кластеризации методом 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-средних.