Алгоритм кластеризации K-средних

Основы кластеризации k-средних и принцип работы кластеризации k-средних. Как реализовать на python.

Кластеризация

K-means - один из простейших алгоритмов машинного обучения без учителя, который решает хорошо известную проблему кластеризации данных. Кластеризация - одна из наиболее распространенных задач анализа данных, используемых для получения интуитивного представления о структуре данных. Он определяется как поиск таких подгрупп в данных, при которых все точки данных в разных кластерах сильно различаются. Мы пытаемся найти однородные подгруппы в данных. Точки данных каждой группы аналогичным образом основаны на показателях сходства, таких как расстояние на основе Евклида или расстояние на основе корреляции.
Алгоритм может выполнять кластерный анализ на основе функций или образцов. Мы пытаемся найти подкатегорию выборки на основе атрибутов или пытаемся найти подкатегорию деталей на основе образцов. У такой процедуры много практических применений: наилучшее использование кластеризации в системе, рекомендованной Amazon и Netflix, учитывая медицинское изображение группы ячеек, алгоритм кластеризации может помочь в идентификации центров ячеек; глядя на данные GPS мобильного устройства пользователя, можно определить их наиболее часто посещаемые местоположения в определенном радиусе; для любого набора немаркированных наблюдений кластеризация помогает установить наличие некоторой структуры данных, которая может указывать на то, что данные можно разделить.

Что такое кластеризация K-средних?

K означает алгоритм кластеризации, основная цель которого - сгруппировать похожие элементы или точки данных в кластер.

K в k-средних представляет количество кластеров.

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

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

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

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

Наконец, этот алгоритм направлен на минимизацию целевой функции, известной как функция квадрата ошибок, определяемая следующим образом:

куда,

‘|| xi - vj ||’ - евклидово расстояние между xi и VJ.

‘ci’ - количество точек данных в ith кластере.

‘c’ - количество кластерных центров.

куда,

‘|| xi - vj ||’ - евклидово расстояние между xi и VJ.

‘ci’ - количество точек данных в ith кластере.

‘c’ - количество кластерных центров.

Алгоритмические шаги для кластеризации k-средних:

Пусть X = {x1, x2, x3, …… .., xn} будет набором точек данных, а V = {v1, v2, ……., Vc} будет набором центров.

Произвольно выберите центры кластеров ‘c’.

2. Рассчитайте расстояние между каждой точкой данных и центрами кластеров.

3. Назначьте точку данных центру кластера, расстояние от которого до центра кластера является минимальным из всех центров кластера.

4. Пересчитайте новый центр кластера, используя:

где ‘ci’ представляет количество точек данных в ith кластере.

5. Пересчитайте расстояние между каждой точкой данных и новыми полученными центрами кластеров.

6. Если ни одна точка данных не была переназначена, остановитесь, в противном случае повторите действия, начиная с шага 3).

Пример задачи алгоритма K-средних

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

Мы воспользуемся библиотекой Scikit-learn и некоторыми случайными данными, чтобы проиллюстрировать простое объяснение кластеризации k-средних.

Шаг 1. Импортируйте библиотеки

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn.cluster import KMean

Как видно из приведенного выше кода, мы импортируем в наш проект следующие библиотеки:

Панды для чтения и написания электронных таблиц
Numpy для проведения эффективных вычислений
Matplotlib для визуализации данных

Шаг 2. Создайте случайные данные

Вот код для генерации случайных данных в двумерном пространстве:

X= -2 * np.random.rand(100,2)
X1 = 1 + 2 * np.random.rand(50,2)
X[50:100, :] = X1
plt.scatter(X[ : , 0], X[ :, 1], s = 50, c = ‘b’)
plt.show()

Всего было сгенерировано 100 точек данных, которые были разделены на две группы по 50 точек в каждой.

Вот как данные отображаются в двухмерном пространстве:

Шаг 3. Используйте Scikit-Learn

Мы будем использовать некоторые из доступных функций в Scikit-learn library для обработки случайно сгенерированных данных.

Вот код:

from sklearn.cluster import KMeans
Kmean = KMeans(n_clusters=2)
Kmean.fit(X)

В этом случае мы произвольно дали k (n_clusters) произвольное значение два.

Вот вывод параметров k-средних, которые мы получаем, если запустим код:

KMeans (алгоритм = 'auto', copy_x = True, init = 'k-means ++', max_iter = 300
n_clusters = 2, n_init = 10, n_jobs = 1, precompute_distances = 'auto',
random_state = Нет, доп. = 0,0001, подробный = 0)

Шаг 4. Определение центроида

Вот код для поиска центра кластеров:

Вот результат значения центроидов:

Давайте отобразим центроиды кластера (зеленым и красным цветом).

plt.scatter(X[ : , 0], X[ : , 1], s =50, c=’b’)
plt.scatter(-0.94665068, -0.97138368, s=200, c=’g’, marker=’s’)
plt.scatter(2.01559419, 2.02597093, s=200, c=’r’, marker=’s’)
plt.show()

Вот результат:

Шаг 5. Тестирование алгоритма

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

Вот результат выполнения вышеуказанного кода алгоритма k-средних:

Как видно выше, 50 точек данных принадлежат кластеру 0, а остальные - кластеру 1.

Например, давайте воспользуемся приведенным ниже кодом для прогнозирования кластера точки данных:

Вот результат:

Это показывает, что точка тестовых данных принадлежит кластеру 0 (зеленый центроид).

Алгоритм кластеризации K-средних