Пошаговое руководство — с решенным примером
1. Введение
1.1 Кластеризация K-средних и проблемы
Кластеризация крупномасштабных данных является ключом к реализации алгоритмов на основе сегментации. Сегментация может включать в себя определение групп клиентов для содействия целевому маркетингу, определение групп лиц, выписывающих рецепты, чтобы позволить участникам здравоохранения обращаться к ним с правильными сообщениями, а также выявление закономерностей или аномальных значений в данных. K-Means — это самый популярный алгоритм кластеризации, применяемый в различных проблемных областях, в основном благодаря его вычислительной эффективности и простоте понимания алгоритма. K-Means использует определение центров кластеров по данным. Он чередует присвоение точек этим центрам кластеров с использованием метрики евклидова расстояния и повторно вычисляет центры кластеров до тех пор, пока не будет достигнут критерий сходимости. Однако кластеризация K-Means имеет ряд недостатков:
- Кластеризация K-Means не использует никакую другую метрику расстояния, кроме евклидова расстояния. Различные метрики расстояния, такие как косинусное расстояние, часто используются в рекомендательной системе, использующей разреженные данные.
- В кластеризации K-средних конечные центры не обязательно являются точками данных из данных и действуют как узкое место для интерпретации для различных областей приложений, таких как изображения в компьютерном зрении.
2. Разделение вокруг медоидов (PAM)
PAM расшифровывается как «Partition Around Medoids». PAM преобразует каждый шаг PAM из детерминированных вычислений в задачу статистической оценки и снижает сложность размера выборки n до O(n log n). Medoids — это точки данных, выбранные в качестве центров кластеров. Кластеризация K-средних направлена на минимизацию внутрикластерного расстояния (часто называемого общей квадратичной ошибкой). Напротив, K-Medoid сводит к минимуму различия между точками в кластере и точками, рассматриваемыми как центры этого кластера.
Любая точка в наборе данных может рассматриваться как медоид тогда и только тогда, когда ее непохожесть на все другие точки данных в кластере минимальна.
Фундаментальная концепция PAM включает в себя:
- Найдите набор kмедоидов (k означает количество кластеров, а M — набор медоидов) из точек данных размера n (n — количество записей).
- Используя любую метрику расстояния (например, d(.), может быть евклидовой, манхэттенской и т. д.), попробуйте найти медоиды, которые минимизируют общее расстояние точек данных до их ближайшего медоида.
- Наконец, поменяйте местами медоидные и немедоидные пары, которые уменьшат функцию потерь L среди всех возможных k(n-k)пар. Функция потерь определяется как:
Обновление центроидов: в случае K-средних мы вычисляли среднее значение всех точек, присутствующих в кластере. Но для алгоритма PAM обновление центроида отличается. Если в кластере есть m-точки, поменяйте местами предыдущий центроид со всеми другими (m-1) точками и завершите точку как новый центроид с минимальными потерями. Минимальные потери вычисляются с помощью функции стоимости, показанной на рисунке 1. Ниже приведен рабочий пример того же самого (GeeksforGeeks, 2019).
2.1 Алгоритм — набор данных
Давайте рассмотрим набор точек данных и признаков.
2.2 Этап инициализации
- Давайте случайным образом выберем два медоида, поэтому выберите 𝐾= 2 и пусть M1 = (4, 5) и M2 = (9, 10) будут двумя медоидами. Обратите внимание, что алгоритм кластеризации выбирает точки данных из данных как медоиды.
- Вычислите непохожесть всех точек на медоиды 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);
Справочник
- 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
- Гикс для гиков. (2019, 17 мая). ML | Кластеризация K-Medoids с решенным примером. Гикс для гиков. https://www.geeksforgeeks.org/ml-k-medoids-clustering-with-example/
Об авторе: специалист по продвинутой аналитике и консультант по управлению, помогающий компаниям находить решения различных проблем с помощью сочетания бизнеса, технологий и математики с организационными данными. Энтузиаст науки о данных, здесь, чтобы делиться, учиться и вносить свой вклад; Вы можете связаться со мной в Linked и Twitter;