机器学习——DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的经典聚类算法，由 Martin Ester 等人于 1996 年提出。该算法通过定义两个关键参数（邻域半径 eps 和最小样本数 minPts）来识别高密度区域，能够有效发现任意形状的簇，并自动将稀疏区域的点标记为噪声点（离群点）。

与基于距离的 K-Means 算法相比，DBSCAN 具有以下显著优势：

1. 无需预先指定簇的数量，算法可自动确定合适的簇数
2. 能够识别非凸形状的簇（如环形、月牙形等）
3. 对噪声数据具有鲁棒性，能有效过滤离群点
4. 对初始值不敏感，结果具有稳定性

例如在电商用户分析中，DBSCAN 可以基于用户的购买频率和消费金额，自动识别出高价值用户群、普通用户群，并将异常消费行为的用户标记为需要特别关注的离群点。

DBSCAN 算法详解

核心概念

（1）关键参数

eps（ε）：邻域半径，决定两个样本是否属于同一簇。这个参数直接影响聚类结果的范围和粒度。例如，在二维空间中，如果设置 eps=0.5，意味着两个点距离小于0.5单位时会被视为相邻。

• 较小值可能导致过度分割
• 较大值可能合并本应分开的簇

min_samples：核心点（Core Point）的邻域内最少样本数。这个参数决定了一个区域被识别为密集区域所需的最小数据点数量。

• 常见取值范围：3-10（取决于数据集大小）
• 较大值更适合噪声较多的数据集

（2）点类型

核心点（Core Point）：

• 在 eps 邻域内至少有 min_samples 个样本的点
• 是簇形成的基础
• 示例：在一个二维数据集中，某点周围有至少5个点（min_samples=5）都在半径0.3（eps=0.3）范围内

边界点（Border Point）：

• 属于某个核心点的邻域，但自身邻域内样本数不足 min_samples
• 处在簇的边缘区域
• 示例：某点周围只有3个邻居（min_samples=5），但位于一个核心点的邻域内

噪声点（Noise Point）：

• 既非核心点也非边界点
• 被算法识别为离群值
• 示例：某点周围没有足够邻居，也不在任何核心点的邻域内

算法流程

1. 随机选择一个未访问的点

• 从数据集中随机选取一个未被处理的数据点
• 在实际应用中，为提高可重复性，通常会设置随机种子

2. 检查其 eps 邻域内的样本数

• 计算该点半径eps范围内的所有点
• 条件判断：
  • 若邻域内点数 ≥ min_samples：
    • 标记该点为核心点
    • 创建新簇
    • 将该点加入当前簇
  • 否则：
    • 暂时标记为噪声点（可能在后续处理中被重新分类）

3. 扩展簇

• 对于新发现的核心点，递归处理其邻域内的所有点：
  • 将邻域内未分类的点加入当前簇
  • 如果邻域内有新发现的核心点，继续扩展
• 使用深度优先搜索(DFS)或广度优先搜索(BFS)策略进行扩展

4. 重复

• 返回步骤1，选择下一个未访问的点
• 直到所有点都被访问和分类

优缺点

优点

1. 无需指定簇数量（对比 K-Means）：

   • 自动确定数据中存在的簇数量
   • 适合事先不知道数据分布的情况

2. 能发现任意形状的簇（如环形、线性）：

   • 基于密度连接而非距离质心
   • 示例：能正确识别环形分布的数据（K-Means会将其分成多个扇形）

3. 对噪声鲁棒（自动识别离群点）：

   • 明确的噪声识别机制
   • 示例：在含有10%随机噪声的数据集中仍能保持良好聚类效果

缺点

1. 对参数 eps 和 min_samples 敏感：

   • 需要仔细调整参数
   • 可能需要通过k-距离图等方法确定合适参数

2. 不适合密度差异大的数据集（全局参数难以适应局部变化）：

   • 单一eps值无法同时适应稀疏和密集区域
   • 示例：数据集中同时存在非常密集和非常稀疏的区域

3. 高维数据性能下降（"维度灾难"）：

   • 在高维空间中距离度量变得不可靠
   • 通常需要降维预处理
   • 示例：在100维以上的数据集中效果显著下降

4. 计算复杂度：

   • 需要计算所有点对之间的距离
   • 时间复杂度约为O(n²)，对于大数据集可能较慢
   • 可通过空间索引技术（如KD-tree）优化

Python实战

class sklearn.cluster.DBSCAN( eps=0.5, # 邻域半径 min_samples=5, # 核心点的最小邻域样本数 metric='euclidean', # 距离度量 metric_params=None, algorithm='auto', # 邻域计算算法 ('auto', 'ball_tree', 'kd_tree', 'brute') leaf_size=30, # 树类算法的叶子大小 p=None, # 闵可夫斯基距离的p值（p=2为欧氏距离） n_jobs=None # 并行计算数 )

2. 核心参数​​

​​3. 属性​​

​​4. 方法​​

​​（1）fit(X)​​

• ​​功能​​：拟合模型并返回簇标签。

• ​​参数​​：

  • X：输入数据，形状 [n_samples, n_features]。

• ​​返回​​：

  • self：拟合后的模型实例。

​​（2）fit_predict(X)​​

• ​​功能​​：拟合模型并直接返回簇标签。

• ​​返回​​：

  • labels：形状 [n_samples]，簇标签（噪声点为 -1）。

实例

import pandas as pd
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score  # 无监督聚类评估指标# 数据加载与预处理
data = pd.read_csv('datingTestSet2.txt',sep='\t')
x_scaled = StandardScaler().fit_transform(data)  # 标准化数据
epsd =[0.3,0.5,0.6,0.7,0.8,0.9]
min_samples =[2,3,4,5,6,7]
best = []
scores= 0# DBSCAN聚类（调整参数）
for i in epsd:for j in min_samples:db = DBSCAN(eps=i, min_samples=j)  # 更合理的默认参数labels = db.fit_predict(x_scaled)score = silhouette_score(x_scaled, labels)if score > scores:scores = scorebest = [i,j]print(best)
db = DBSCAN(eps=best[0], min_samples=best[1])
labels = db.fit_predict(x_scaled)
# 评估聚类效果（无监督指标）
print("轮廓系数:", silhouette_score(x_scaled, labels))  # 值越接近1越好
print("噪声点比例:", sum(labels == -1) / len(labels))  # 噪声占比
print("簇数量:", len(set(labels)) - (1 if -1 in labels else 0))

import pandas as pd
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt
from sklearn.neighbors import NearestNeighbors# 数据加载与标准化
data = pd.read_csv('datingTestSet2.txt', sep='\t')
x_scaled = StandardScaler().fit_transform(data)# 1. 通过k-距离图确定eps范围（k=min_samples的候选值）
def plot_k_distance(X, k=4):neighbors = NearestNeighbors(n_neighbors=k).fit(X)distances, _ = neighbors.kneighbors(X)k_distances = np.sort(distances[:, -1])plt.plot(k_distances)plt.xlabel('Points sorted by distance')plt.ylabel(f'{k}-th nearest neighbor distance')plt.title('k-Distance Graph for Eps Selection')plt.show()plot_k_distance(x_scaled, k=4)  # 观察拐点位置作为eps参考值# 2. 参数调优（基于k-距离图结果调整范围）
eps_candidates = np.linspace(0.3, 1.0, 8)  # 根据拐点调整范围
min_samples_candidates = [3, 5, 7, 10]    # 至少为维度+1best_score = -1
best_params = {}for eps in eps_candidates:for min_samples in min_samples_candidates:db = DBSCAN(eps=eps, min_samples=min_samples)labels = db.fit_predict(x_scaled)if len(set(labels)) > 1:  # 至少两个簇才能计算轮廓系数score = silhouette_score(x_scaled, labels)if score > best_score:best_score = scorebest_params = {'eps': eps, 'min_samples': min_samples}# 3. 使用最佳参数聚类
db = DBSCAN(**best_params)
labels = db.fit_predict(x_scaled)# 4. 评估与可视化
print("最佳参数:", best_params)
print("轮廓系数:", silhouette_score(x_scaled, labels))
print("噪声点比例:", sum(labels == -1) / len(labels))
print("簇数量:", len(set(labels)) - (1 if -1 in labels else 0))# 可视化聚类结果（假设数据为二维）
plt.scatter(x_scaled[:, 0], x_scaled[:, 1], c=labels, cmap='viridis', alpha=0.6)
plt.title('DBSCAN Clustering Results')
plt.show()