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

МЕНЮ


Главная страница
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


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

Существует множество алгоритмов кластеризации, однако ниже будет рассмотрен метод 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 = 999999999 		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 = cluster 	while 1: 		cluster = cluster_update(cluster, cluster_content, dim) 		cluster_content = data_distribution(array, cluster) 		if cluster == privious_cluster: 			break

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

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

def cluster_update(cluster, cluster_content, dim): #новый кластер вычисляется   #на основании прилежных ему точек 	k = len(cluster)  	for i in range(k): #кластер 		for q in range(dim): #параметр 			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 = cluster 	while 1: 		cluster = cluster_update(cluster, cluster_content, dim) 		cluster_content = data_distribution(array, cluster) 		if cluster == privious_cluster: 			break

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

Визуализируем результат алгоритма для 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().

Визуализация кластеризации для точек двумерного пространства. Количество точек — 1000. Количество кластеров — 5.
Визуализация кластеризации для точек двумерного пространства. Количество точек — 1000. Количество кластеров — 5.

Аналогичным образом визуализируется результат алгоритма для 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()
Визуализация кластеризации для 3-х мерного пространства. Количество точек — 1000. Количество кластеров — 5.
Визуализация кластеризации для 3-х мерного пространства. Количество точек — 1000. Количество кластеров — 5.
Визуализация кластеризации 3-х мерного пространства для сгруппированных данных. Количество точек — 390. Количество кластеров — 3
Визуализация кластеризации 3-х мерного пространства для сгруппированных данных. Количество точек — 390. Количество кластеров — 3

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


Источник: habr.com

Комментарии: