Пошаговое руководство — с решенным примером

1. Введение

1.1 Кластеризация K-средних и проблемы

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

  1. Кластеризация K-Means не использует никакую другую метрику расстояния, кроме евклидова расстояния. Различные метрики расстояния, такие как косинусное расстояние, часто используются в рекомендательной системе, использующей разреженные данные.
  2. В кластеризации K-средних конечные центры не обязательно являются точками данных из данных и действуют как узкое место для интерпретации для различных областей приложений, таких как изображения в компьютерном зрении.

2. Разделение вокруг медоидов (PAM)

PAM расшифровывается как «Partition Around Medoids». PAM преобразует каждый шаг PAM из детерминированных вычислений в задачу статистической оценки и снижает сложность размера выборки n до O(n log n). Medoids — это точки данных, выбранные в качестве центров кластеров. Кластеризация K-средних направлена ​​​​на минимизацию внутрикластерного расстояния (часто называемого общей квадратичной ошибкой). Напротив, K-Medoid сводит к минимуму различия между точками в кластере и точками, рассматриваемыми как центры этого кластера.

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

Фундаментальная концепция PAM включает в себя:

  1. Найдите набор kмедоидов (k означает количество кластеров, а M — набор медоидов) из точек данных размера n (n — количество записей).
  2. Используя любую метрику расстояния (например, d(.), может быть евклидовой, манхэттенской и т. д.), попробуйте найти медоиды, которые минимизируют общее расстояние точек данных до их ближайшего медоида.
  3. Наконец, поменяйте местами медоидные и немедоидные пары, которые уменьшат функцию потерь L среди всех возможных k(n-k)пар. Функция потерь определяется как:

Обновление центроидов: в случае K-средних мы вычисляли среднее значение всех точек, присутствующих в кластере. Но для алгоритма PAM обновление центроида отличается. Если в кластере есть m-точки, поменяйте местами предыдущий центроид со всеми другими (m-1) точками и завершите точку как новый центроид с минимальными потерями. Минимальные потери вычисляются с помощью функции стоимости, показанной на рисунке 1. Ниже приведен рабочий пример того же самого (GeeksforGeeks, 2019).

2.1 Алгоритм — набор данных

Давайте рассмотрим набор точек данных и признаков.

2.2 Этап инициализации

  1. Давайте случайным образом выберем два медоида, поэтому выберите 𝐾= 2 и пусть M1 = (4, 5) и M2 = (9, 10) будут двумя медоидами. Обратите внимание, что алгоритм кластеризации выбирает точки данных из данных как медоиды.
  2. Вычислите непохожесть всех точек на медоиды M1 и M2. Обратите внимание, несходство рассчитывается как сумма абсолютной разницы между медоидами и точками данных. Например, D=|Mx — Функция X| + |Моя – функция Y|

2.3 Шаг назначения

Назначьте точки данных Медоидам с более низкой Непохожестью (Стоимостью). Точки данных 0 и 2 идут на M2, а точки данных 3, 4 и 5 идут на M1. Общая стоимость = стоимость/несходство баллов, присвоенных M1 + стоимость/несходство баллов, присвоенных M2.

Общая стоимость=(4+3+4)+(4+7)=22; Стоимость для M1 = Непохожесть точки 3 с M1 (4) + Непохожесть точки 4 с M1 (3) + Непохожесть точки 5 с M1 (4). Повторите тот же расчет для M2.

2.4 Этап перекомпиляции центроида

Случайным образом выберите одну немедоидную точку и пересчитайте стоимость. Давайте теперь выберем точку данных 5 M1 как (2,3) в качестве медоида и пересчитаем стоимость.

Теперь на M1 идут только точки 4 и 6, а остальные точки идут на M2. Общая стоимость = (7 + 4) + (4 + 7 + 6) = 28 и стоимость обмена = новая стоимость — предыдущая стоимость = 28–22 = 6.

Мы отменим обмен, поскольку стоимость обмена больше 0. Этот процесс продолжается до тех пор, пока не будет выполнен критерий сходимости.

3. Реализация с использованием Python

Мы смоделируем приведенный выше пример, используя алгоритм K-Medoid от scikit-learn-extra. Несколько кодов и концепций, вдохновленных документацией пакета (scikit-learn-extra, 2019)

# — — — — — — -Importing Packages — — — — — — — — — — — -
import matplotlib.pyplot as plt
import numpy as np
from sklearn_extra.cluster import KMedoids
# — — — — — — -Assigning Initial Centers — — — — — — — — — — — -
centers = [[4, 5], [9, 10]]
# — — — — — — -Assigning Data: Dummy Data used in example above — — — — — — — — — — — — — — — — — — 
df=np.array([[7,8], [9,10], [11,5], [4,9], [7,5], [2,3], [4,5]])
# — — — — — — -Fit KMedoids clustering — — — — — — — — — — — -
KMobj = KMedoids(n_clusters=2).fit(df)
# — — — — — — -Assigning Cluster Labels — — — — — — — — — — — -
labels = KMobj.labels_

Визуализация кластера.

# — — — — — — -Extracting Unique Labels — — — — — — — — — — — -
unq_lab = set(labels)
# — — — — — — -Setting Up Color Codes — — — — — — — — — — — -
colors_plot = [
 plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unq_lab))
]
for k, col in zip(unq_lab, colors_plot):
class_member_mask = labels == k
 
 # — — — — — — -Setting datapoint Feature X and Feature Y — — — — — — — — — — — -
xy = df[class_member_mask]
 
 # — — — — — — -Plotting Feature X and Feature Y for each cluster labels — — — — — — — — — — — -
 
 plt.plot(
 xy[:, 0],
 xy[:, 1],
 “o”,
 markerfacecolor=tuple(col),
 markeredgecolor=”white”,
 markersize=10,
 );
# — — — — — — -Annotate Centroids — — — — — — — — — — — -
plt.plot(
 KMobj.cluster_centers_[:, 0],
 KMobj.cluster_centers_[:, 1],
 “o”,
 markerfacecolor=”orange”,
 markeredgecolor=”k”,
 markersize=10,
);
# — — — — — — -Add title to the plot — — — — — — — — — — — -
plt.title(“KMedoids clustering on Dummy Data- Medoids are represented in Orange.”, fontsize=14);

Справочник

  1. scikit-узнать-дополнительно. (2019). Демонстрация KMedoids — документация scikit-learn-extra 0.2.0. Scikit-Learn-Extra.readthedocs.io. https://scikit-learn-extra.readthedocs.io/en/stable/auto_examples/plot_kmedoids.html#sphx-glr-auto-examples-plot-kmedoids-py
  2. Гикс для гиков. (2019, 17 мая). ML | Кластеризация K-Medoids с решенным примером. Гикс для гиков. https://www.geeksforgeeks.org/ml-k-medoids-clustering-with-example/

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