Неконтролируемое обучение: разделение (на основе расстояния) кластеризация с использованием K-Means и K-Medoids…

Абстрактный

В этом руководстве мы обсудим концепцию разделения на кластеры, популярную технику обучения без учителя, используемую для группировки схожих точек данных в кластеры на основе их сходства и различий. Этот метод делит точки данных на фиксированное количество кластеров, где каждая точка данных принадлежит только одному кластеру. Основная цель разделяющей кластеризации — минимизировать расстояние внутри кластера и максимизировать расстояние между кластерами. Мы описываем два основных типа кластеризации разделения, K-Means и K-Medoids, и объясняем разницу между centroid и medoid. Он предоставляет математические формулы для расчета центроида и медоида кластера.

В учебнике также обсуждается важность выбора оптимального количества кластеров и вводится метод локтя для определения оптимального количества кластеров. В нем объясняются аргументы и параметры KMeans(), такие как n_clusters, init, n_init, max_iter, tol, precompute_distances, verbose, random_state, copy_x и n_jobs.

Мы также рассмотрим практический пример того, как использовать алгоритм K-средних для кластеризации набора данных радужной оболочки глаза с использованием библиотеки Python Scikit-learn. В этом примере описываются необходимые шаги, такие как импорт необходимых библиотек, загрузка набора данных, выполнение кластеризации K-средних, визуализация кластеров, интерпретация результатов, экспериментирование с различными значениями K и определение оптимального количества кластеров с использованием метода локтя. Наконец, представлены наиболее важные параметры объекта модели KMeans и их описания, такие как cluster_centers_, labels_, inertia_ и n_iter_.

🦊Я также приглашаю вас ознакомиться с моими сообщениями о контролируемом и неконтролируемом обучении, которые можно найти в следующих списках тем: Темы о контролируемом обучении, Темы о неконтролируемом обучении, и Общие темы машинного обучения.

Разделение на кластеры — это популярный метод обучения без учителя, используемый для группировки схожих точек данных в кластеры на основе их сходства и различий. В этом методе точки данных делятся на фиксированное количество кластеров, где каждая точка данных принадлежит только одному кластеру. Цель разделения кластеров состоит в том, чтобы минимизировать внутрикластерное расстояние (т. е. расстояние между точками данных в одном кластере) и максимизировать межкластерное расстояние (т. е. расстояние между точками данных в разных кластерах).

Двумя основными типами кластеризации разделения являются кластеризация K-Means и K-Medoids. В кластеризации K-средних алгоритм случайным образом выбирает K начальных центроидов (т. Е. Репрезентативные точки для каждого кластера), а затем назначает каждую точку данных ближайшему центроиду. Затем алгоритм повторно вычисляет центроиды на основе среднего значения точек данных в каждом кластере и повторяет процесс, пока не будет достигнута сходимость. При кластеризации K-Medoids алгоритм выбирает K репрезентативных точек из набора данных, а затем присваивает каждой точке данных ближайшую репрезентативную точку. Затем алгоритм выбирает новый набор репрезентативных точек на основе медоида точек данных в каждом кластере и повторяет процесс, пока не будет достигнута сходимость.

Кластеризация K-средних: инициализация, назначение и сходимость

Процесс кластеризации включает в себя три основных этапа:

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

Жесткая кластеризация

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

🦊Если вы хотите узнать больше о кластеризации в неконтролируемом обучении, вам может быть интересно прочитать другую мою статью «Методы кластеризации 101: введение в неконтролируемые методы обучения». В этой публикации представлен исчерпывающий обзор. различных методов кластеризации, включая иерархическую кластеризацию, кластеризацию на основе плотности и кластеризацию на основе моделей, и обсуждают их преимущества и недостатки. В нем также рассматриваются такие темы, как оценка и выбор кластера, и приводятся примеры приложений кластеризации в различных областях.

🤔 Центроид или Медоид?

Представьте, что у вас есть группа людей, стоящих в парке, и вы хотите найти центральную точку группы. Один из способов сделать это — рассчитать среднее положение всех людей в группе, что даст вам центр тяжести. Другой способ — найти человека, который ближе всего ко всем остальным, и этим человеком будет медоид.

Теперь предположим, что в группе есть один человек, который стоит очень далеко от всех остальных, в совершенно другом районе парка. Если вы рассчитаете центроид, этот выброс будет сильно влиять на него, и он будет смещен в сторону позиции этого человека. Однако, если вы вычислите медоид, это будет человек, который ближе всего ко всем остальным, и на него меньше повлияет выброс.

Метод центроида используется в кластеризации K-средних для определения центра кластера. Центроид представляет собой среднее арифметическое всех точек данных в кластере. Чтобы найти центроид, мы вычисляем среднее значение координат всех точек в кластере. Например, если у нас есть набор 2D-данных, центр тяжести кластера будет средним значением координат x и средним значением координат y.

Медоидный метод используется в кластеризации K-медоидов для определения центра кластера. Медоид — это точка данных в кластере, ближайшая ко всем остальным точкам в кластере. Чтобы найти медоид, мы вычисляем расстояние между каждой точкой в кластере и всеми остальными точками в кластере. Точка с наименьшей суммой расстояний до всех остальных точек кластера называется медоидом.

Математически центр тяжести кластера можно рассчитать следующим образом:

Пусть C будет кластером из n точек данных с координатами (x1,y1), (x2,y2), …, (xn,yn).

Центроид кластера определяется как:

Точно так же медоид кластера можно рассчитать следующим образом:

Пусть C будет кластером из n точек данных с координатами (x1,y1), (x2,y2), …, (xn,yn).

Медоид кластера — это точка данных, которая минимизирует сумму расстояний до всех других точек кластера:

где d(x_i,x_j) — расстояние между точками данных x_i и x_j, а argmin_i — индекс точки данных, которая минимизирует сумму расстояний.

При кластеризации K-medoids медоид каждого кластера используется в качестве центра кластера вместо центроида. Это связано с тем, что медоид более устойчив к выбросам и может лучше понять центральную тенденцию кластера.

💡Предположим, у нас есть набор данных из 5 одномерных точек:

{1, 2, 4, 7, 9}

Допустим, мы хотим сгруппировать этот набор данных в один кластер, используя алгоритмы k-medoids и k-means.

Если мы используем алгоритм k-medoids с евклидовым расстоянием в качестве меры несходства, мы инициализируем кластер с медоидом в точке, которая имеет наименьшее среднее различие со всеми другими точками в наборе данных. В этом случае медоид будет равен 4, поскольку это точка с наименьшим средним расстоянием до всех остальных точек:

Кластер 1: {1, 2, 4, 7, 9}, Медоид 1: 4

Если вместо этого мы используем алгоритм k-средних, мы инициализируем кластер центроидом в среднем расположении всех точек в наборе данных. В этом случае центр тяжести будет средним значением всех точек, что равно 4,6:

Кластер 1: {1, 2, 4, 7, 9}, Центроид 1: 4,6

Обратите внимание, что в этом случае медоид и центроид — разные значения. Медоид равен 4, то есть точке, которая имеет наименьшее среднее расстояние до всех других точек, а центроид равен 4,6, что является средним расположением всех точек в наборе данных.

📌 Количество кластеров

Выбор количества кластеров является важным шагом в разделении кластеров. Одним из подходов к определению оптимального количества кластеров является метод локтя, который включает построение суммы квадратов внутри кластера (WCSS) в зависимости от количества кластеров. WCSS — это мера того, насколько точки данных в каждом кластере отличаются от центроида. По мере увеличения количества кластеров WCSS уменьшается, но в какой-то момент уменьшение WCSS становится незначительным. Оптимальное количество кластеров — это точка, в которой уменьшение WCSS начинает выравниваться, образуя на графике локтевую форму.

🤔 Преимущества и ограничения кластеризации K-средних по сравнению с другими алгоритмами кластеризации

Преимущества:

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

Ограничения:

Предполагается, что кластеры имеют сферическую форму и имеют одинаковую дисперсию.
Альтернативное решение: модели гауссовских смесей (GMM) можно использовать для моделирования кластеров с различной дисперсией или формой.
Требуется заранее указать количество кластеров, что может быть проблематично для многомерных наборов данных или наборов данных с большим количеством кластеров.
Альтернативное решение: можно использовать иерархическую кластеризацию для определения количества кластеров на основе дендрограммы или анализ силуэта для оценки оптимального количества кластеров.
Чувствителен к начальному выбору центроидов и может сходиться к субоптимальным решениям, если начальные центроиды выбраны неудачно.
Альтернативное решение: K-means++ можно использовать для выбора более репрезентативных начальных центроидов или можно использовать другие методы инициализации, такие как иерархическая кластеризация или кластеризация на основе плотности.
Высокая чувствительность к выбросам, которые могут искажать кластеры и влиять на интерпретируемость результатов.
Альтернативное решение: DBSCAN, OPTICS или LOF можно использовать в качестве альтернативных алгоритмов кластеризации, более устойчивых к выбросам. В качестве альтернативы можно использовать методы предварительной обработки, такие как PCA или надежная статистика, для удаления или уменьшения влияния выбросов.

🐍 K-средства в Python

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

Шаг 1. Импорт необходимых библиотек Начнем с импорта необходимых библиотек, включая scikit-learn для алгоритма K-средних, Matplotlib для визуализации данных и NumPy для числовых операций.

from sklearn.cluster import KMeans
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
import numpy as np

Шаг 2: Загрузите набор данных Затем мы загружаем набор данных радужной оболочки, используя функцию load_iris из scikit-learn. Этот набор данных содержит информацию о длине и ширине лепестков и чашелистиков трех разных видов ирисов.

X = iris.data[:, :2]

Шаг 4: Выполнение кластеризации K-средних Теперь мы выполняем алгоритм кластеризации K-средних на извлеченных функциях набора данных радужной оболочки, используя функцию KMeans из scikit-learn. Мы установили количество кластеров равным 3, так как в наборе данных есть три разных вида ирисов.

kmeans = KMeans(n_clusters=3, random_state=42).fit(X)

Шаг 5. Визуализация кластеров Чтобы визуализировать кластеры, мы наносим каждую точку данных на точечную диаграмму, окрашенную в соответствии с кластером, к которому она принадлежит. Мы также наносим центроиды скопления красными звездами.

# Define the colors and markers for the clusters
colors = ['red', 'green', 'blue']
markers = ['o', 's', 'D']

# Plot the data points and the centroids
fig, ax = plt.subplots(figsize=(8, 6))
for i, label in enumerate(kmeans.labels_):
    ax.scatter(X[i, 0], X[i, 1], c=colors[label], marker=markers[label], alpha=0.5)
ax.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=200, c='red', marker='*', label='Centroids')

# Set x and y limits
ax.set_xlim(4, 8)
ax.set_ylim(1.5, 5)

# Add axis labels and a legend
ax.set_xlabel(iris.feature_names[0])
ax.set_ylabel(iris.feature_names[1])
ax.set_title('K-Means Clustering on Iris Dataset (n_clusters = 3)')
ax.legend(loc='best')
plt.show()

Шаг 6. Интерпретация результатов Из визуализации видно, что алгоритм K-средних успешно разделил набор данных радужной оболочки глаза на три отдельных кластера. Мы также можем заметить, что красный кластер соответствует видам setosa, синий кластер соответствует видам versicolor, а зеленый кластер соответствует видам virginica.

Шаг 7: Экспериментируйте с различными значениями K Производительность алгоритма K-средних сильно зависит от количества выбранных кластеров K. Таким образом, важно поэкспериментировать с разными значениями K, чтобы увидеть, как изменится кластеризация. Например, мы можем попробовать сгруппировать набор данных в четыре кластера, установив K=4 в функции KMeans и перерисовав результаты.

# Perform k-means clustering with n_clusters = 4
kmeans = KMeans(n_clusters=4, random_state=42).fit(X)

# Define the colors and markers for the clusters
colors = ['red', 'green', 'blue', 'purple']
markers = ['o', 's', 'D', 'P']

# Plot the data points and the centroids
fig, ax = plt.subplots(figsize=(8, 6))
for i, label in enumerate(kmeans.labels_):
    ax.scatter(X[i, 0], X[i, 1], c=colors[label], marker=markers[label], alpha=0.5)
ax.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=200, c='red', marker='*', label='Centroids')

# Set x and y limits to zoom in on the data
ax.set_xlim(4, 8)
ax.set_ylim(1.5, 5)

# Add axis labels and a legend
ax.set_xlabel(iris.feature_names[0])
ax.set_ylabel(iris.feature_names[1])
ax.set_title('K-Means Clustering on Iris Dataset (n_clusters = 4)')
ax.legend(loc='best')
plt.show()

Мы видим, что с четырьмя кластерами алгоритм разделяет виды versicolor и virginica на два отдельных кластера.

Шаг 8: Определение оптимального количества кластеров Чтобы определить оптимальное количество кластеров для набора данных радужной оболочки, мы можем построить график суммы квадратов внутри кластера (WCSS) в зависимости от количества кластеров. WCSS представляет собой сумму квадратов расстояний между каждой точкой данных и назначенным ей центром кластера. График зависимости WCSS от количества кластеров имеет форму локтя, а оптимальное количество кластеров — это точка, в которой снижение WCSS начинает выравниваться. Мы можем использовать атрибут inertia_ функции KMeans для вычисления WCSS для каждого значения K.

# Determine the optimal number of clusters
wcss = []
for i in range(1, 11):
    kmeans = KMeans(n_clusters=i, init='k-means++', max_iter=300, n_init=10, random_state=42)
    kmeans.fit(X)
    wcss.append(kmeans.inertia_)

# Plot the WCSS against the number of clusters
fig, ax = plt.subplots(figsize=(8, 6))
ax.plot(range(1, 11), wcss)
ax.set_title('The Elbow Method')
ax.set_xlabel('Number of Clusters')
ax.set_ylabel('Within-Cluster Sum of Squares')
ax.annotate('Elbow-like', xy=(3, wcss[2]), xytext=(4, 100), arrowprops=dict(facecolor='black', shrink=0.05))
plt.show()

В приведенном выше коде мы вычисляем WCSS для значений K в диапазоне от 1 до 10 и сохраняем их в списке. Затем мы строим график зависимости WCSS от количества кластеров, используя функцию plt.plot. Мы аннотируем график меткой «Похожий на локоть» в точке, где снижение WCSS начинает выравниваться. Из графика видно, что оптимальное количество кластеров для набора данных радужной оболочки равно 3, поскольку именно здесь формируется локтевая форма.

🔍 Аргументы и параметры KMeans()

Вы также можете поближе познакомиться с аргументами KMeans():

n_clusters: целое, по умолчанию=8

Количество кластеров, которые нужно сформировать, а также количество центроидов, которые нужно сгенерировать.

init: {'k-means++', 'random'} или ndarray формы (n_clusters, n_features), по умолчанию = 'k-means++'

Способ инициализации:

«k-means++»: разумно выбирает начальные центры кластеров для ускорения сходимости.
«случайный»: выберите n_clusters наблюдений (строк) случайным образом из данных для начальных центроидов.
ndarray: напрямую укажите начальные центроиды.
n_init: целое число, по умолчанию = 10

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

max_iter: целое число, по умолчанию = 300

Максимальное количество итераций алгоритма k-средних за один прогон.

tol: число с плавающей запятой, по умолчанию = 1e-4

Относительная терпимость в отношении инерции декларировать конвергенцию.

precompute_distances: {'авто', Истина, Ложь}, по умолчанию = 'авто'

Предварительное вычисление расстояний (быстрее, но занимает больше памяти).

«auto»: не выполнять предварительный расчет расстояний, если n_samples * n_clusters > 12 миллионов. Это соответствует примерно 100 МБ накладных расходов на задание с использованием двойной точности.
True : всегда предварительно вычислять расстояния.
False : никогда не вычислять расстояния заранее.
verbose: целое число, по умолчанию = 0

Многословный режим.

random_state: int, экземпляр RandomState, по умолчанию = нет

Определяет генерацию случайных чисел для инициализации центроида. Используйте int, чтобы сделать случайность детерминированной.

copy_x: логическое значение, по умолчанию = Истина

При предварительном вычислении расстояний более точно в числовом отношении сначала центрировать данные. Если copy_x имеет значение True (по умолчанию), исходные данные не изменяются, гарантируя, что X является C-непрерывным. Если False, исходные данные изменяются и возвращаются обратно до того, как функция вернется, но небольшие числовые различия могут быть введены путем вычитания, а затем добавления среднего значения данных.

n_jobs: целое число, по умолчанию = нет

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

Вот наиболее важные параметры объекта модели KMeans и их описания:

cluster_centers_: ndarray формы (n_clusters, n_features)

Координаты центров кластеров.

labels_: ndarray формы (n_samples,)

Метки каждой точки (т. е. к какому кластеру принадлежит каждая точка).

inertia_: плавающий

Сумма квадратов расстояний от образцов до их ближайшего центра кластера.

n_iter_: интервал

Количество выполненных итераций.

В заключение, разделение кластеров — это эффективный метод обучения без учителя, используемый для группировки схожих точек данных в кластеры на основе их сходств и различий. K-Means и K-Medoids — это два основных типа разделения кластеров, где K-Means использует метод центроидов для определения центра кластера, а K-Medoids использует метод медоидов. Выбор оптимального количества кластеров имеет решающее значение при разделении кластеров, и метод локтя является широко используемым подходом для его определения. Алгоритм K-Means может быть реализован в библиотеке Python Scikit-learn, а его аргументы и параметры могут быть скорректированы для достижения оптимальных результатов.