Как вы все уже знаете, поскольку вы попали на эту страницу, кластеризация — это фундаментальный метод машинного обучения и анализа данных. Это полезно для нескольких целей, таких как классификация, сегментация, уменьшение размерности, обнаружение выбросов и извлечение дополнительных сведений из данных. Алгоритмы неконтролируемой кластеризации, такие как K-means и DBSCAN, не требуют предварительных знаний или обучения и могут идентифицировать кластеры для группировки точек данных, которые находятся ближе друг к другу. В Интернете есть несколько хороших руководств по K-means и DBSCAN. В этой статье представлен краткий обзор двух алгоритмов, K-средних и DBSCAN, и показаны простые реализации для одномерного случая.
Начнем с импорта обычных пакетов.
import matplotlib.pyplot as plt from scipy import signal import numpy as np
Кластеры данных могут быть созданы путем создания различных эллипсов и добавления шума. Мы определяем следующий метод для генерации всех данных для каждого кластера.
def generate_ellipse(npts,majaxis,minaxis,rotation,center,nvar):
# Generate angles between 0 and 2*pi
angles = np.linspace(0, 2 * np.pi, npts)
# Calculate x and y points on ellipse
x1 = center[0] + majaxis*np.cos(angles)*np.cos(rotation) - minaxis*np.sin(angles)*np.sin(rotation)
y1 = center[1] + majaxis*np.cos(angles)*np.sin(rotation) + minaxis*np.sin(angles)*np.cos(rotation)
noise = np.random.normal(0, nvar, size=x2.shape)
x1 += noise
noise = np.random.normal(0, nvar, size=y2.shape)
y1 += noise
ellipsoid = np.column_stack((x1, y1))
return ellipsoid
Затем с помощью следующего кода мы генерируем данные, имеющие два кластера.
ellipse1 = generate_ellipse(1000,1,0.5,np.pi/4,(5,2),0.5)
ellipse2 = generate_ellipse(1000,1,0.5,np.pi/4,(1,1),0.5)
data = np.concatenate((ellipse1, ellipse2))
plt.figure()
plt.scatter(data[:, 0], data[:, 1])
plt.title('Data')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()
Кластеризация K-средних находит центроиды, которые представляют каждый из кластеров, найденных в данных. Однако нам нужно указать количество кластеров, которые есть в наборе данных. Алгоритм начинается со случайных центроидов для определенного количества кластеров. Для каждого центроида мы находим все точки данных, которые ближе к этому центроиду по сравнению с другими центроидами. Этот шаг также можно заменить вычислением вероятности того, что точки данных, принадлежащие кластеру, определяются этим центроидом. Как только подмножество точек данных связано с этим кластером, центроид затем повторно вычисляется на основе всех точек данных, связанных с этим кластером. Это составляет одну итерацию алгоритма. Итерации продолжаются до тех пор, пока центроиды не перестанут меняться.
from sklearn.cluster import KMeans
# Fit a k-means model to the data
kmeans = KMeans(n_clusters=2)
kmeans.fit(data)
# Get the cluster labels and centroids
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
# Plot the data points and centroids
plt.figure()
plt.scatter(data[:, 0], data[:, 1], c=labels)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', s=200, linewidths=3, color='r')
plt.title('K-means Clustering')
plt.show()
Если мы изменим количество кластеров на другое число, то увидим, что кластеризация K-средних группирует точки данных в эти многочисленные кластеры. На практике мы не знаем, сколько кластеров содержится в данных, и нам нужно применять дополнительные стратегии для оценки количества кластеров.
kmeans = KMeans(n_clusters=5)
kmeans.fit(data)
# Get the cluster labels and centroids
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
# Plot the data points and centroids
plt.figure()
plt.scatter(data[:, 0], data[:, 1], c=labels)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='x', s=200, linewidths=3, color='r')
plt.title('K-means Clustering')
plt.show()
DBSCAN, с другой стороны, использует шар эпсилон для группировки точек данных вместе. Мы рисуем эпсилон-шар вокруг точки данных, и если в радиусе эпсилон есть хотя бы определенное количество соседей, мы связываем их с точкой данных. Затем это повторяется для каждого из соседей. Все точки данных, до которых можно добраться друг от друга (то есть все они находятся в пределах эпсилон-расстояния друг от друга), группируются вместе в один кластер. Те точки данных, которые не имеют достаточного количества соседей в пределах своего эпсилон-шара, рассматриваются как выбросы.
На следующем графике показано, как DBSCAN группирует точки данных. Здесь мы видим, что мы по-прежнему идентифицируем 4 кластера вместо 2, и все точки на границах не включены в кластеры.
from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.2, min_samples=5)
labels = dbscan.fit_predict(data)
# Count the number of clusters (excluding outliers)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print("Number of clusters from DBSCAN:", n_clusters)
# Plot the results
plt.figure()
plt.scatter(data[:, 0], data[:, 1], c=labels)
plt.title('DBSCAN Clustering')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()
Если мы правильно найдем количество кластеров, то большой разницы между K-средними и DBSCAN из приведенного выше набора данных не будет. Но есть определенные наборы данных, где K-средние просто не могут найти нужные кластеры, в то время как DBSCAN работает хорошо. См., например, набор данных, представленный ниже.
ellipse1 = generate_ellipse(1000,2,1,np.pi/4,(3,2),0.1)
ellipse2 = generate_ellipse(1000,4,2,np.pi/4,(3,2),0.1)
data = np.concatenate((ellipse1, ellipse2))
plt.figure()
plt.scatter(data[:, 0], data[:, 1])
plt.title('Data')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()
Теперь мы видим резкую разницу в производительности K-средних по сравнению с DBSCAN.
Но даже DBSCAN потерпит неудачу, если мы увеличим дисперсию шума, как мы видим на графиках ниже.
ellipse1 = generate_ellipse(1000,2,1,np.pi/4,(3,2),0.25)
ellipse2 = generate_ellipse(1000,4,2,np.pi/4,(3,2),0.25)
data = np.concatenate((ellipse1, ellipse2))
plt.figure()
plt.scatter(data[:, 0], data[:, 1])
plt.title('Data')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()
Давайте теперь сосредоточимся на одномерном случае, когда точки данных просто лежат вдоль линии. Мы сделаем данные целыми, потому что нас интересуют точки данных, лежащие в сетке, а целые числа всегда можно масштабировать до разрешения сетки. Одно ключевое преимущество, которое мы имеем для одномерного случая, заключается в том, что данные можно легко упорядочить, просто отсортировав.
data = np.sort(np.random.choice(np.arange(1, 100), size=10, replace=False)) print(data)
Неортодоксальный способ кластеризации здесь состоит в том, чтобы смотреть на точки данных как на места, где есть ненулевое значение. Затем мы можем сгруппировать точки данных вместе с помощью «сглаживания». См., например, следующий код. Мы создаем импульсный вектор, присваивая 1 всем местоположениям точек данных. Сглаживание выполняется путем свертки этого вектора импульса с гауссовским импульсом. Затем центроиды оцениваются путем определения пиков в результирующем сигнале.
t = np.linspace(-1, 1, 11)
i, q, e = signal.gausspulse(t, fc=1.5, retquad=True, retenv=True)
impvec = np.zeros(100)
impvec[data] = 1
clustered_signal = np.convolve(impvec,e)
clustered_signal = clustered_signal[5:104]
peak_locs, _ = signal.find_peaks(clustered_signal);
print("Estimated centroid locations: ", peak_locs)
fig, (ax1, ax2, ax3) = plt.subplots(nrows=1, ncols=3, figsize=(15, 3))
ax1.plot(e, '--*', color='red')
ax1.set_title('Gaussian Pulse')
ax2.stem(impvec)
ax2.set_title('Impulse vector')
ax3.plot(clustered_signal,'-*')
ax3.stem(peak_locs,clustered_signal[peaks_locs],linefmt='r-', markerfmt='ro', basefmt='r-')
ax3.stem(data,impvec[data],linefmt='g-', markerfmt='g+', basefmt='g-')
ax3.set_title('Clustered Signal and Centroids')
plt.show()
Давайте теперь применим DBSCAN к тому же набору данных и посмотрим, что мы получим для центроидов.
# Perform DBSCAN on the data
dbscan = DBSCAN(eps=3, min_samples=2)
dbscan.fit_predict(data.reshape(-1, 1))
# Plot the results
labels = dbscan.labels_
unique_labels = set(labels)
#print(unique_labels)
# Count the number of clusters (excluding outliers)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print("Number of DBSCAN clusters: ", n_clusters)
centroids_dbscan = []
for k in unique_labels:
if k == -1:
# For noise points, use the original point as the centroid
#centroids_dbscan.append(data[labels == k])
centroids_dbscan = np.concatenate((centroids_dbscan, data[labels == k]))
else:
class_members = (labels == k)
this_centroid = np.mean(data[class_members])
centroids_dbscan.append(this_centroid)
print("DBSCAN Centroids:", np.sort(centroids_dbscan))
Вспомните, что алгоритм максимизации ожидания (EM) начинается со случайных центроидов заранее определенного числа и находит все точки данных, которые близки к каждому из этих центроидов, перед повторным вычислением центроидов на основе ассоциаций. Теперь мы объединяем алгоритм EM с эпсилон-шаром DBSCAN, чтобы получить алгоритм, который начинается с первой точки данных в качестве центроида, и для каждой дополнительной точки данных, которая находится внутри эпсилон-шара центроида, новый центроид вычисляется путем усреднения центроид с новой точкой данных. Если следующая точка данных находится за пределами эпсилон-шара центроида, она инициирует новый кластер и становится первым центроидом для этого кластера. Нам просто нужно выполнить один проход по данным, чтобы найти количество кластеров и их центроиды. Обратите внимание, что это работает для одномерного случая, поскольку данные могут быть упорядочены!
epsilon = 5
centroids_em = np.zeros(data.shape);
centroids_em[0] = data[0];
cluster_idx = 0;
for k in range(1, len(data)):
if abs(data[k] - centroids_em[cluster_idx]) < epsilon:
centroids_em[cluster_idx] = 0.5 * (centroids_em[cluster_idx] + data[k])
else:
cluster_idx += 1
centroids_em[cluster_idx] = data[k]
centroids_em = centroids_em[0:cluster_idx+1]
print("EM Centroids:", centroids_em)
И теперь мы, наконец, сравним различные способы кластеризации одномерных данных. На следующем графике мы видим, что результаты различных алгоритмов кластеризации почти совпадают.
plt.figure() plt.stem(data,4*impvec[data],linefmt='g-', markerfmt='g+', basefmt='g-',label='data') plt.stem(peaks_locs,clustered_signal[peaks_locs],linefmt='r-', markerfmt='ro', basefmt='r-', label='smoothing') plt.stem(centroids_dbscan,2*np.ones(len(centroids_dbscan)),linefmt='b-', markerfmt='bs', basefmt='b-', label='dbscan') plt.stem(centroids_em,3*np.ones(len(centroids_em)),linefmt='k-', markerfmt='kx', basefmt='k-', label='EM') plt.legend(loc='center left', bbox_to_anchor=(1, 0.5)) plt.show()
