Мы действительно знаем все о K-средних?
Кластеризация не новость для машинного обучения, но она определенно никогда не устареет. Группировка точек данных со схожими характеристиками в кластеры без знания их соответствующих меток или какой-либо другой предварительной информации, если на то пошло, звучит для меня довольно круто. Давайте углубимся в один из самых фундаментальных и наиболее часто используемых алгоритмов, который находится под капотом кластеризации; К-средства.
Оглавление
K-означает
Алгоритм направлен на разделение точек данных на k наборов (т. Е. кластеры) путем минимизации отклонений набора. Последнее просто означает минимизацию расстояния от центроида (центра кластера).
Часто бывает так, что у нас есть дополнительная информация о наших точках данных. Возможно, каждая выборка принадлежит определенной группе, то есть мужчине / женщине, давнему / новому пользователю, странам и т. Д. Таким образом, мы могли бы присвоить вес каждой выборке с учетом группы, к которой они принадлежат. Для этого мы используем взвешенное К-среднее.
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
# Generate data
centers = [[1, 1], [-1, -1], [1, -1]]
n_clusters = len(centers)
X, y_true = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7)
# K-means
kmeans = KMeans(n_clusters=n_clusters)
kmeans.fit(X)
y_kmeans = kmeans.predict(X)
centers = kmeans.cluster_centers_
# Weighted K-means
weights = list(map(lambda x: x*10, y_true))
kmeans = KMeans(n_clusters=n_clusters)
kmeans.fit(X, sample_weight=weights)
y_kmeans_w = kmeans.predict(X, sample_weight=weights)
centers_w = kmeans.cluster_centers_
# Plotting
fig, ax = plt.subplots(1, 3, figsize=(20,7))
colors = ['#d35400', '#34495e', '#2980b9']
versions = ['Original Data', 'K-means', 'Weighted K-means']
y = [y_true, y_kmeans, y_kmeans_w]
centers_ = [centers, centers_w]
for i in range(3):
ax[i].scatter(X[:, 0], X[:, 1], s=50, c=list(map(lambda x: colors[x], y[i])), alpha=0.5)
elif i>0:
ax[i].scatter(centers_[i-1][:, 0], centers_[i-1][:, 1], marker='+', c='black', s=200)
ax[i].set_title(versions[i])
ax[i].set_xticks([])
ax[i].set_yticks([])
plt.show()
Для целей этого раздела мы случайным образом сгенерировали набор данных из 3 кластеров, в общей сложности 3000 точек данных. Веса присваиваются следующим образом w_i = true_cluster_index * 10. Очевидно, кластеры и соответствующие им центроиды очень сильно зависят от результирующего вектора весов. Следует очень осторожно подходить к тому, когда и как использовать взвешенные K-средние, поскольку это может иметь большое влияние на конечные центры кластеров.
MiniBatch K-средства
K-средство очень мощное средство, но иногда его невозможно уместить в ваш набор данных из-за его большого размера. В таких случаях вы можете использовать MiniBatch K-means, который использует мини-пакеты, слегка перемещая центроиды на каждой итерации. Это также приводит к более быстрой сходимости, но, что наиболее важно, позволяет кластеризовать огромные наборы данных, которые не помещаются в памяти.
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import time
# Generate data
centers = [[1, 1], [-1, -1], [1, -1]]
n_clusters = len(centers)
X, y_true = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7)
# K-means
kmeans = KMeans(n_clusters=n_clusters)
t0 = time.time()
k_means.fit(X)
t_batch = time.time() - t0
y_kmeans = kmeans.predict(X)
centers = kmeans.cluster_centers_
mbk = MiniBatchKMeans(n_clusters=n_clusters, batch_size=45,
max_no_improvement=10, verbose=0)
t0 = time.time()
mbk.fit(X)
t_mini_batch = time.time() - t0
y_kmeans_batch = mbk.predict(X)
centers_b = mbk.cluster_centers_
# Plotting
fig, ax = plt.subplots(1, 2, figsize=(15,7))
colors = ['#d35400', '#34495e', '#2980b9']
versions = ['K-means', 'MiniBatch K-means']
y = [y_kmeans, y_kmeans_batch]
t = [t_batch, t_mini_batch]
centers_ = [centers, centers_b]
for i in range(2):
ax[i].scatter(X[:, 0], X[:, 1], s=50, c=list(map(lambda x: colors[x], y[i])), alpha=0.5)
ax[i].scatter(centers_[i][:, 0], centers_[i][:, 1], marker='+', c='black', s=200)
ax[i].set_title(versions[i] + f' | train time: {np.round(t[i], 2)}fs')
ax[i].set_xticks([])
ax[i].set_yticks([])
plt.show()
Нечеткие c-средства
Изначально K-means - это жесткая кластеризация (т.е. кластеры не перекрываются). Что, если образцы принадлежат нескольким кластерам? Затем нам нужны алгоритмы, которые выполняют мягкую кластеризацию (т.е. каждый образец имеет вероятность принадлежности к кластеру).
Процесс аналогичен K-средним, но центроид кластера вычисляется как среднее всех точек, взвешенных по их вероятности принадлежности к кластеру i.
import skfuzzy as fuzz
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
# Generate data
centers = [[1, 1], [-1, -1], [1, -1]]
n_clusters = len(centers)
X, y_true = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7)
# Fuzzy c-means
cntr, u, u0, d, jm, p, fpc = fuzz.cluster.cmeans(X.T, n_clusters, 2, error=0.005, maxiter=1000)
# Plotting
colors = ['#d35400', '#34495e', '#2980b9']
fig, ax = plt.subplots(1, 2, figsize=(15,7))
ax[0].scatter(X[:, 0], X[:, 1], s=50, c=list(map(lambda x: colors[x], y_true)), alpha=0.5)
ax[0].set_title('Original Data')
ax[0].set_xticks([])
ax[0].set_yticks([])
cluster_membership = np.argmax(u, axis=0)
for j in range(n_clusters):
cX = X[cluster_membership == j]
ax[1].scatter(cX[:, 0], cX[:, 1], s=50, c=colors[j], alpha=0.5)
for pt in cntr:
ax[1].scatter(pt[0], pt[1], marker='+', c='black', s=200)
ax[1].set_title(f'Fuzzy c-means | FPC {np.round(fpc, 2)}')
ax[1].set_xticks([])
ax[1].set_yticks([])
FPC (коэффициент нечеткого разделения) - это показатель производительности, который находится в диапазоне от 0 до 1, где 1 является лучшим. В нашем случае мы достигли FPC 0,68. В нашей задаче каждая точка принадлежит одному кластеру, поэтому np.argmax(u, axis=0), однако, можно дополнительно исследовать вероятности членства для каждого кластера. Например, мы могли бы определить порог и найти, какие образцы принадлежат нескольким кластерам или одному кластеру после определения порога.
K-medoids
Передайте привет кузену K-means, K-medoids. Возможно, вы уже догадались, что между двумя алгоритмами не так уж много различий, и вы правы. Основные отличия заключаются в следующем:
- Центры (medoids) теперь являются фактическими точками данных из нашего набора данных - что не является обязательным для K-средних.
› большая интерпретируемость центры кластеров, чем в K-средних - Вместо евклидова расстояния K-medoids сводит к минимуму сумму мер попарного несходства.
›более устойчив к выбросам и шуму
В следующем сценарии мы исследуем результаты K-medoids с использованием 3 мер попарного несходства - Manhattan, Cosine и Euclidean - и K-средних.
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
from sklearn_extra.cluster import KMedoids
import matplotlib.pyplot as plt
# Generate data
centers=[[1,1], [-1,-1], [1,-1]]
n_clusters = len(centers)
X, y_true = make_blobs(n_samples=3000, centers=centers, cluster_std=0.7)
# K-medoids models
selected_models = [(KMedoids(metric="manhattan", n_clusters=n_clusters), "KMedoids (manhattan)"),
(KMedoids(metric="euclidean", n_clusters=n_clusters), "KMedoids (euclidean)"),
(KMedoids(metric="cosine", n_clusters=n_clusters), "KMedoids (cosine)"),
(KMeans(n_clusters=n_clusters), 'KMeans')]
colors=['#d35400', '#34495e', '#2980b9']
fig, ax = plt.subplots(2, 2, figsize=(15, 15))
perm = list(set(itertools.permutations([0,1,1,0], 2)))
for s in range(4):
i, j = perm[s]
model, name = selected_models[s]
model.fit(X)
y_hat = model.predict(X)
centers_hat = model.cluster_centers_
inertia = model.inertia_
ax[i, j].scatter(X[:,0], X[:, 1], s=50, c=list(map(lambda x: colors[x], y_hat)), alpha=0.5)
ax[i, j].scatter(centers_hat[:, 0], centers_hat[:, 1], marker='+', c='black', s=200)
ax[i, j].scatter(np.array(centers)[:, 0], np.array(centers)[:, 1], marker='o', c='black', s=200, alpha=0.6)
ax[i, j].set_title(name)
ax[i, j].set_xticks([])
ax[i, j].set_yticks([])
plt.show()
На каждом графике центры кластеров изображены крестиком, а истинные центры представлены кружком. Учитывая эту информацию, сравнивая все 4, мы видим, что косинус работает хуже всех остальных. K-medoids с использованием евклидова расстояния дает очень похожие результаты с K-средними, что и ожидалось. Наконец, манхэттенское расстояние дает очень похожие результаты с евклидовым расстоянием.
K-means - это относительно простой алгоритм, но при этом очень мощный. Благодаря простой и быстрой реализации он по праву стал одним из самых популярных алгоритмов для задач кластеризации.
С другой стороны, следует отметить, что K-средних гарантированно найдет только локальный минимум, но гарантировано, что он всегда будет сходиться. Одно из наиболее раздражающих предположений состоит в том, что все кластеры имеют сферическую форму одинакового размера. Это связано с тем, что значение кластера - это просто среднее значение всех точек в кластере.
