در این پست شما می توانید یک مثال از خوشه بند الگوریتم DBSCAN در زبان پایتون را مشاهده کنید:

شبه کد الگوریتم

# pseudocode available on ecliptic 2019
#copy right Ester et al ,1996 
#from www.aaai.org/Press/Proceedings/kdd96.php

DBSCAN(D, epsilon, min_points):
C = 0
for each unvisited point P in dataset
mark P as visited
sphere_points = regionQuery(P, epsilon)
if sizeof(sphere_points) < min_points
ignore P	
 else
C = next cluster
 expandCluster(P, sphere_points, C, epsilon, min_points)
expandCluster(P, sphere_points, C, epsilon, min_points):
add P to cluster C
for each point P’ in sphere_points
if P’ is not visited
  mark P’ as visited
 sphere_points’ = regionQuery(P’, epsilon)
 if sizeof(sphere_points’) >= min_points
sphere_points = sphere_points joined with sphere_points’
if P’ is not yet member of any cluster
 add P’ to cluster C
regionQuery(P, epsilon):
 return all points within the n-dimensional sphere centered at        P with radius epsilon (including P)

کد پایتون DBSCAN

کد زیر برگرفته از وبسایت scikit-learn یکی از نمونه های اجرای  الگوریتم خوشه بندی DBSCAN توسط کتابخانه ی sklearn به زبان پایتون در یادگیری ماشین است. که پس از اجرای کد  پارامتر های تعداد خوشه ها و نویز ها، ضریب همگونی و ضریب یک دستی داده ها را نمایش می دهد. سمپل های این برنامه 750 عدد بوده که کاملا به صورت اتفاقی ساخته شده اند.

import numpy as np

from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler


# #############################################################################
# Generate sample data
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,
                            random_state=0)

X = StandardScaler().fit_transform(X)

# #############################################################################
# Compute DBSCAN
db = DBSCAN(eps=0.3, min_samples=10).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_

# Number of clusters in labels, ignoring noise if present.
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
n_noise_ = list(labels).count(-1)

print('Estimated number of clusters: %d' % n_clusters_)
print('Estimated number of noise points: %d' % n_noise_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f"
      % metrics.adjusted_rand_score(labels_true, labels))
print("Adjusted Mutual Information: %0.3f"
      % metrics.adjusted_mutual_info_score(labels_true, labels,
                                           average_method='arithmetic'))
print("Silhouette Coefficient: %0.3f"
      % metrics.silhouette_score(X, labels))

# #############################################################################
# Plot result
import matplotlib.pyplot as plt

# Black removed and is used for noise instead.
unique_labels = set(labels)
colors = [plt.cm.Spectral(each)
          for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
    if k == -1:
        # Black used for noise.
        col = [0, 0, 0, 1]

    class_member_mask = (labels == k)

    xy = X[class_member_mask & core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=14)

    xy = X[class_member_mask & ~core_samples_mask]
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=6)

plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()

نتیجه ی اجرای برنامه ی فوق به شرح زیر است:

Estimated number of clusters: 3

Estimated number of noise points: 18

Homogeneity: 0.953

Completeness: 0.883

V-measure: 0.917

Adjusted Rand Index: 0.952

Adjusted Mutual Information: 0.883

Silhouette Coefficient: 0.626

نتیجه خوشه بندی DBSCAN در سه خوشه توسط کد پایتون بر روی داده های اتفاقی