大家好，今儿分享的是DBSCAN~
DBSCAN在我们学习过程中，是非常重要的一个聚类算法算法模型。
DBSCAN 适合用于发现形状不规则的簇，并且能自动处理噪声点（即离群点）。这个算法比较有趣，因为它不需要像 K-means 那样事先指定簇的个数，而是通过数据点的密度来判断。
核心概念
密度：在 DBSCAN 中，密度是指某个点周围的点的数量。 核心点（Core Point）：如果某个点的邻居数量（在一定距离范围内的点的数量）超过了指定的阈值（MinPts），那么它就叫做核心点。 边界点（Border Point）：这个点虽然不是核心点，但它在某个核心点的邻域范围内，所以属于该核心点所在的簇。 噪声点（Noise Point）：这个点既不是核心点，也不在任何核心点的邻域范围内，它被认为是离群点或异常点。
DBSCAN 的参数：
Epsilon (ε)：定义一个点周围的邻域范围，简单理解就是“半径”。 MinPts：定义在某个点的邻域范围内，至少需要多少个点才能把这个点当作一个核心点。
工作流程
选一个点，看看它周围有多少个点（这个“周围”就是指 epsilon 这么大的半径范围内）。 如果这个点的周围点数 >= MinPts，那么这个点就是核心点，它和邻域内的点会被归为同一个簇。 如果这个点的周围点数 < MinPts，它就要么是边界点，要么是噪声点，后续可能会归类或者被标记为离群点。 继续扫描数据集的其它点，重复上述步骤，最终形成若干个簇，并自动标记噪声点。
一个简单例子
假设我们在一个广场上有一堆人（数据点），我们想要通过这些人的站位来找出不同的团体（簇）。我们给每个人画一个小圈（这个圈的半径就是 Epsilon）。我们还设定一个规则：如果某个人圈内至少有 4 个人（MinPts），那我们认为这个人属于一个团体的核心。
核心点：某个人的圈里有足够多的人（比如 ≥ 4 个），那么这个人是核心成员，自己属于一个团体。 边界点：某个人的圈里人数不够，但他刚好站在某个团体的外围，被其他人的圈“捞”进了团体中。 噪声点：某个人周围没人或者人数远远不够，既不属于任何团体，也没有人愿意接纳他，这就是“噪声点”。
假如你站在广场上，周围 2 米范围内有 5 个人（Epsilon = 2，MinPts = 5）。你周围的人数够了（5 >= 4），所以你就是核心成员，并且你跟周围的人被认为是一个团体。同样，如果你是团体中的核心成员，那么你周围其他人也会被划分到你的团体里。
但是有个朋友，他周围 2 米范围内只有 3 个人，那他自己不是核心成员。但如果他站在你旁边，而你是核心成员，他就可以归到你的团体里，成为“边界点”。
还有些人孤零零地站在角落，周围 2 米范围内一个人都没有，既不属于任何团体，也没有别人能把他拉进团体，这些人就是“噪声点”。
DBSCAN 就像在一群人中自动识别团体的过程。它通过定义邻域范围（Epsilon）和最小人数（MinPts），来判断某个人是核心成员、团体边界成员还是被孤立的噪声点。
原理介绍
1. 基本概念
如前所述，DBSCAN 通过密度来进行聚类，主要依赖以下几个概念：
Epsilon (ε)：定义一个点周围的邻域半径。 MinPts：在 ε 邻域内，一个点被认为是核心点所需的最小点数。 核心点（Core Point）：在 ε 邻域内至少有 MinPts 个点（包括自身）。 边界点（Border Point）：在 ε 邻域内点数少于 MinPts，但位于至少一个核心点的邻域内。 噪声点（Noise Point）：既不是核心点，也不属于任何核心点的邻域。
2. DBSCAN 算法步骤
DBSCAN 的核心在于利用密度连接来构建簇。以下是算法的详细步骤：
1. 初始化：
标记所有点为未访问。 初始化簇编号为 0。
2. 遍历每个点：
如果该点已被访问，则跳过。 标记该点为已访问。 找出该点的 ε 邻域内的所有邻居（包括自身）。 如果邻居数量 ≥ MinPts： 增加簇编号。 将该点标记为核心点，并将其分配到新簇。 扩展簇： 对该点的每个邻居： 如果未被访问，标记为已访问。 找出该邻居的 ε 邻域。 如果邻域数量 ≥ MinPts，则将这些邻居添加到当前邻居列表（以便进一步扩展）。 如果该邻居尚未分配到任何簇，则将其分配到当前簇。 否则： 标记该点为噪声点（可能后续被其他簇吸收为边界点）。
3. 距离度量
在 DBSCAN 中，常用的距离度量是 欧氏距离。对于二维空间中的两个点 和 ，欧氏距离计算公式为：
4. 密度连接
两个点 和被称为密度可达（density reachable）的，如果存在一个点序列，其中,，并且对于每个和，在 的 ε 邻域内。
通过这种密度连接，DBSCAN 能够发现任意形状的簇，并有效地识别出噪声点。
完整案例
我们将通过以下步骤来实现 DBSCAN：
生成一个虚拟数据集。 实现 DBSCAN 算法。 可视化数据和聚类结果，绘制至少四个图形。
我们使用 NumPy 生成几个不同形状的簇，并添加一些噪声点。
import numpy as np
import matplotlib.pyplot as plt
# 设置随机种子以确保结果可重复
np.random.seed(42)
# 生成三个不同形状的簇
# 簇1：圆形
n_points1 = 1000
radius1 = 5
theta1 = np.random.uniform(0, 2*np.pi, n_points1)
r1 = radius1 * np.sqrt(np.random.uniform(0, 1, n_points1))
x1 = r1 * np.cos(theta1) + 10
y1 = r1 * np.sin(theta1) + 10
# 簇2：椭圆形
n_points2 = 1000
theta2 = np.random.uniform(0, 2*np.pi, n_points2)
r2 = 3 * np.sqrt(np.random.uniform(0, 1, n_points2))
x2 = r2 * np.cos(theta2) + 30
y2 = r2 * np.sin(theta2) * 2 + 30
# 簇3：线性分布（噪声较多）
n_points3 = 1000
x3 = np.linspace(50, 60, n_points3) + np.random.normal(0, 0.5, n_points3)
y3 = x3 + np.random.normal(0, 0.5, n_points3)
# 噪声点
n_noise = 200
x_noise = np.random.uniform(0, 70, n_noise)
y_noise = np.random.uniform(0, 70, n_noise)
# 合并所有点
X = np.concatenate([np.vstack((x1, y1)).T,
np.vstack((x2, y2)).T,
np.vstack((x3, y3)).T,
np.vstack((x_noise, y_noise)).T])
# 绘制初始数据分布
plt.figure(figsize=(8, 6))
plt.scatter(X[:,0], X[:,1], s=10, color='gray')
plt.title('Initial data distribution')
plt.xlabel('X')
plt.ylabel('Y')
plt.grid(True)
plt.show()
图1：初始数据分布
图中显示了三个不同形状的簇（圆形、椭圆形、线性分布)以及一些随机分布的噪声点。灰色点表示所有数据点。
实现 DBSCAN 算法
我们将按照前面详细的算法步骤，手动实现 DBSCAN。
from collections import deque
def euclidean_distance(p, q):
return np.sqrt(np.sum((p - q)**2))
def region_query(X, point_idx, eps):
neighbors = []
for idx, point in enumerate(X):
if euclidean_distance(X[point_idx], point) <= eps:
neighbors.append(idx)
return neighbors
def expand_cluster(X, labels, point_idx, neighbors, cluster_id, eps, min_pts):
labels[point_idx] = cluster_id
queue = deque(neighbors)
while queue:
current_point = queue.popleft()
if labels[current_point] == -1:
labels[current_point] = cluster_id # 将噪声点加入簇
if labels[current_point] != 0:
continue # 已经被分配到某个簇
labels[current_point] = cluster_id
current_neighbors = region_query(X, current_point, eps)
if len(current_neighbors) >= min_pts:
queue.extend(current_neighbors)
return labels
def dbscan(X, eps, min_pts):
labels = np.zeros(len(X)) # 0 表示未分类
cluster_id = 0
for point_idx in range(len(X)):
if labels[point_idx] != 0:
continue # 已经被分类
neighbors = region_query(X, point_idx, eps)
if len(neighbors) < min_pts:
labels[point_idx] = -1 # 标记为噪声
else:
cluster_id += 1
labels = expand_cluster(X, labels, point_idx, neighbors, cluster_id, eps, min_pts)
return labels
euclidean_distance：计算两个点之间的欧氏距离。 region_query：查找 ε 邻域内的所有邻居。 expand_cluster：将密度可达的点扩展到当前簇中。 dbscan：主函数，遍历所有点，分配簇标签。
选择合适的参数 Epsilon 和 MinPts
选择合适的参数对 DBSCAN 的效果至关重要。常用的方法是绘制 k-距离图（k-distance graph），其中 k = MinPts - 1。通过观察图中的“膝点”（elbow），可以选择合适的 ε 值。
# 绘制 k-距离图
def k_distance_graph(X, k):
distances = []
for point in X:
dists = np.linalg.norm(X - point, axis=1)
sorted_dists = np.sort(dists)
distances.append(sorted_dists[k])
distances = np.sort(distances)
plt.figure(figsize=(8, 6))
plt.plot(distances)
plt.title(f'k-distance (k={k})')
plt.xlabel('Sorting of Points')
plt.ylabel(f'{k} distance')
plt.grid(True)
plt.show()
k = 4 # 常用设置，MinPts = k + 1 = 5
k_distance_graph(X, k)
图2：k-距离图
通过观察图中距离的急剧上升点，可以选择 ε 的值。假设我们选择 ε = 3.5。
应用 DBSCAN 并可视化结果
根据 k-距离图，我们选择 ε = 3.5 和 MinPts = 5。
# 设置参数
eps = 3.5
min_pts = 5
# 应用 DBSCAN
labels = dbscan(X, eps, min_pts)
# 获取簇的数量
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print(f'找到的簇数量: {n_clusters}')
# 绘制聚类结果
unique_labels = set(labels)
colors = plt.cm.get_cmap('tab20', len(unique_labels))
plt.figure(figsize=(8, 6))
for k_label in unique_labels:
if k_label == -1:
# 噪声点
col = 'k'
label = 'Noise point'
else:
col = colors(k_label)
label = f'crowd {k_label}'
class_member_mask = (labels == k_label)
plt.scatter(X[class_member_mask, 0], X[class_member_mask, 1],
s=10, color=col, label=label)
plt.title('DBSCAN Cluster results')
plt.xlabel('X')
plt.ylabel('Y')
plt.legend()
plt.grid(True)
plt.show()
图3：DBSCAN 聚类结果
不同颜色代表不同的簇，黑色点表示噪声点。可以看到圆形、椭圆形和线性分布的簇被成功识别，且噪声点被有效地隔离。
5. 可视化核心点和边界点
为了更好地理解 DBSCAN 的分类，我们可以绘制出核心点、边界点和噪声点的分布。
# 确定核心点
def get_core_points(X, labels, eps, min_pts):
core_points = []
for idx, point in enumerate(X):
neighbors = region_query(X, idx, eps)
if len(neighbors) >= min_pts:
core_points.append(idx)
return core_points
core_points = get_core_points(X, labels, eps, min_pts)
# 绘制核心点、边界点和噪声点
plt.figure(figsize=(8, 6))
for k_label in unique_labels:
if k_label == -1:
# 噪声点
col = 'k'
label = 'Noise point'
plt.scatter(X[labels == k_label, 0], X[labels == k_label, 1],
s=10, color=col, label=label)
else:
# 簇内点
col = colors(k_label)
cluster_points = X[labels == k_label]
core = cluster_points[np.isin(np.where(labels == k_label)[0], core_points)]
border = cluster_points[~np.isin(np.where(labels == k_label)[0], core_points)]
plt.scatter(border[:,0], border[:,1], s=10, color=col, label=f'crowd {k_label} Boundary point')
plt.scatter(core[:,0], core[:,1], s=30, facecolors='none', edgecolors=col, marker='o', label=f'crowd {k_label} Core points')
plt.title('DBSCAN Core and boundary points')
plt.xlabel('X')
plt.ylabel('Y')
plt.legend(markerscale=2)
plt.grid(True)
plt.show()
图4：DBSCAN 核心点与边界点
说明：每个簇的核心点用较大的空心圆表示，边界点用实心圆表示，噪声点仍然用黑色表示。这样可以清晰地区分不同类型的点。
6. 可视化不同参数对聚类结果的影响
为了展示参数选择的重要性，我们可以尝试不同的 ε 和 MinPts，并观察聚类结果的变化。
def plot_dbscan(X, eps, min_pts):
labels = dbscan(X, eps, min_pts)
unique_labels = set(labels)
colors = plt.cm.get_cmap('tab20', len(unique_labels))
plt.figure(figsize=(8, 6))
for k_label in unique_labels:
if k_label == -1:
# 噪声点
col = 'k'
label = 'Noise point'
else:
col = colors(k_label)
label = f'crowd {k_label}'
class_member_mask = (labels == k_label)
plt.scatter(X[class_member_mask, 0], X[class_member_mask, 1],
s=10, color=col, label=label)
plt.title(f'DBSCAN Cluster results (ε={eps}, MinPts={min_pts})')
plt.xlabel('X')
plt.ylabel('Y')
plt.legend()
plt.grid(True)
plt.show()
# 示例：不同参数设置
plot_dbscan(X, eps=2.0, min_pts=5)
plot_dbscan(X, eps=3.5, min_pts=5)
plot_dbscan(X, eps=4.5, min_pts=5)
图5：不同 ε 值下的 DBSCAN 聚类结果
说明：通过调整 ε 参数，可以看到簇的数量和形状发生变化。较小的 ε 可能导致更多的噪声点和较多的簇，而较大的 ε 则可能将多个簇合并为一个。
DBSCAN 是一个强大且灵活的聚类算法，特别适用于发现任意形状的簇和处理噪声数据。希望通过这个详细的解释和实践案例，大家能够更好地掌握 DBSCAN 的使用和原理。
