当前位置： 首页 > news >正文

ML 聚类算法 dbscan|| OPTICS

news 2025/4/3 15:07:00

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，基于密度的空间聚类应用）是一种经典的密度聚类算法。它能够发现任意形状的簇，并且能够识别噪声点（离群点）。DBSCAN的核心思想是：如果一个点的邻域内包含足够多的点（达到设定的阈值），则该点属于一个簇；否则，它被视为噪声点。

DBSCAN 的核心概念

  1. 核心点（Core Point）：

    • 给定一个点 ( p ) 和参数 ( \epsilon )（邻域半径）和 ( MinPts )（最小点数），如果在以 ( p ) 为圆心、( \epsilon ) 为半径的邻域内（包括 ( p ) 自身）的点数不少于 ( MinPts )，则 ( p ) 是核心点。

  2. 边界点（Border Point）：

    • 如果一个点 ( q ) 不是核心点，但它位于某个核心点的 ( \epsilon )-邻域内，则 ( q ) 是边界点。

  3. 噪声点（Noise Point）：

    • 如果一个点既不是核心点，也不是边界点，则它被视为噪声点。

  4. 直接密度可达（Directly Density-Reachable）：

    • 如果点 ( p ) 是核心点，且点 ( q ) 位于 ( p ) 的 ( \epsilon )-邻域内，则 ( q ) 从 ( p ) 直接密度可达。

  5. 密度可达（Density-Reachable）：

    • 如果存在一系列点 ( p_1, p_2, \dots, p_n )，使得 ( p_1 = p )，( p_n = q )，且 ( p_{i+1} ) 从 ( p_i ) 直接密度可达，则 ( q ) 从 ( p ) 密度可达。

  6. 密度相连（Density-Connected）：

    • 如果存在一个点 ( o )，使得 ( p ) 和 ( q ) 都从 ( o ) 密度可达，则 ( p ) 和 ( q ) 密度相连。

DBSCAN 的算法步骤

  1. 初始化：

    • 将所有点标记为未访问（unvisited）。
    • 初始化簇编号 ( C = 0 )。

  2. 遍历所有点：

    • 对于每个未访问的点 ( p )：
      • 标记 ( p ) 为已访问。
      • 计算 ( p ) 的 ( \epsilon )-邻域内的点数。
      • 如果 ( p ) 是核心点：
        • 创建一个新簇 ( C )，并将 ( p ) 加入该簇。
        • 递归地将 ( p ) 的 ( \epsilon )-邻域内的所有点加入簇 ( C )。
        • 递增簇编号 ( C = C + 1 )。
      • 如果 ( p ) 不是核心点，则将其标记为噪声点。

  3. 输出结果：

    • 返回所有簇和噪声点。

Python 实现

以下是 DBSCAN 的 Python 实现：

import numpy as np
from collections import dequedef dbscan(data, eps, min_pts):n = len(data)# 标记点是否被访问过visited = np.zeros(n, dtype=bool)# 标记点的簇编号，未分类的点为 -1labels = np.full(n, -1)# 簇编号cluster_id = 0def euclidean_distance(a, b):return np.linalg.norm(a - b)def get_neighbors(p):neighbors = []for i in range(n):if euclidean_distance(data[p], data[i]) <= eps:neighbors.append(i)return neighborsfor i in range(n):if not visited[i]:visited[i] = Trueneighbors = get_neighbors(i)if len(neighbors) < min_pts:# 标记为噪声点labels[i] = -1else:# 创建一个新簇labels[i] = cluster_idqueue = deque(neighbors)while queue:q = queue.popleft()if not visited[q]:visited[q] = Trueq_neighbors = get_neighbors(q)if len(q_neighbors) >= min_pts:# 将 q 的邻居加入队列queue.extend(q_neighbors)if labels[q] == -1:# 将 q 加入当前簇labels[q] = cluster_id# 递增簇编号cluster_id += 1return labels

使用示例

# 生成一些示例数据
data = np.array([[1, 1], [1, 2], [2, 2], [8, 8], [8, 9], [9, 9], [15, 15]])
eps = 1.5
min_pts = 2# 运行 DBSCAN
labels = dbscan(data, eps, min_pts)# 输出结果
print("聚类结果:", labels)

输出解释

  • 每个点的标签表示它所属的簇编号，标签为 -1 的点是噪声点。
  • 例如，如果输出为 [0, 0, 0, 1, 1, 1, -1]，则表示前三个点属于簇 0，接下来的三个点属于簇 1，最后一个点是噪声点。

DBSCAN 的优势

  1. 无需指定簇的数量：与 ( k )-means 不同，DBSCAN 不需要事先指定簇的数量。
  2. 能够处理噪声点：DBSCAN 能够识别并剔除噪声点。
  3. 能够发现任意形状的簇：DBSCAN 可以发现任意形状的簇，而不仅仅是球形簇。

DBSCAN 的局限性

  1. 对参数敏感：DBSCAN 的性能高度依赖于参数 ( \epsilon ) 和 ( MinPts ) 的选择。
  2. 不适用于高维数据：在高维数据中，距离度量可能失效，导致 DBSCAN 性能下降。

总结

DBSCAN 是一种强大的密度聚类算法，特别适用于发现任意形状的簇和处理噪声点。通过合理选择参数 ( \epsilon ) 和 ( MinPts )，可以有效地应用于各种实际场景，如异常检测、图像分割等。

##-_____________________————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

Ordering Points To Identify the Clustering Structure (OPTICS) 是一种基于密度的聚类算法，类似于 DBSCAN，但它可以处理不同密度的数据集，并且不需要预先指定聚类半径（eps）。OPTICS 通过生成一个 可达性图（Reachability Plot）来描述数据点的聚类结构。

OPTICS 的核心思想

  1. 核心距离（Core Distance）：
    • 对于一个点 p，其核心距离是使 p 成为核心点的最小半径 eps。如果 p 在半径 eps 内有至少 min_samples 个点，则 p 是核心点。
  2. 可达距离（Reachability Distance）：
    • 对于点 p 和点 q，可达距离是 max(core_distance(p), distance(p, q))。它表示从 p 到 q 的可达性。

OPTICS 算法步骤

  1. 初始化：
    • 为每个点计算核心距离和可达距离。
    • 维护一个有序列表（Order List）来存储点的处理顺序。
  2. 处理点：
    • 从未处理的点中选择一个点，计算其核心距离和可达距离。
    • 将该点加入有序列表，并将其邻居点加入待处理队列。
  3. 生成可达性图：
    • 根据处理顺序和可达距离生成可达性图。
  4. 提取聚类：
    • 通过分析可达性图，提取聚类结构。

Python 实现

可以使用 sklearn 库中的 OPTICS 类来实现该算法。

from sklearn.cluster import OPTICS
import matplotlib.pyplot as plt
import numpy as np# 示例数据
X = np.array([[1, 2], [2, 5], [3, 6], [8, 7], [8, 8], [7, 3], [9, 2]])# 创建 OPTICS 模型
optics_model = OPTICS(min_samples=2, xi=0.05, min_cluster_size=0.5)# 拟合数据
optics_model.fit(X)# 获取聚类标签
labels = optics_model.labels_# 打印聚类结果
print("聚类标签:", labels)# 可视化可达性图
plt.figure(figsize=(10, 5))
plt.subplot(121)
plt.bar(range(len(optics_model.reachability_)), optics_model.reachability_)
plt.title("Reachability Plot")
plt.xlabel("Ordered Points")
plt.ylabel("Reachability Distance")# 可视化聚类结果
plt.subplot(122)
for label in set(labels):if label == -1:plt.scatter(X[labels == label, 0], X[labels == label, 1], c='gray', label='Noise')else:plt.scatter(X[labels == label, 0], X[labels == label, 1], label=f'Cluster {label}')
plt.title("Clustering Result")
plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.legend()
plt.show()

参数说明

  1. min_samples：
    • 定义核心点所需的最小邻居数。
  2. xi：
    • 用于提取聚类的阈值参数，控制聚类的紧密程度。
  3. min_cluster_size：
    • 定义最小聚类大小，可以是绝对数量或比例。

输出结果

  1. 可达性图：
    • 显示了每个点的可达距离，用于识别聚类结构。
  2. 聚类结果：
    • 将数据点分配到不同的聚类中，噪声点标记为 -1。

优点

  • 不需要预先指定聚类半径 eps。
  • 可以处理不同密度的数据集。
  • 生成的可达性图提供了数据结构的直观表示。

缺点

  • 对于大规模数据集，计算复杂度较高。
  • 参数 xi 和 min_cluster_size 的选择可能影响聚类结果。

OPTICS 是一种强大的聚类算法，特别适用于密度不均匀的数据集。

##-------------------------------------------------------------------------------------------------------------——————————————————————————————————————————————————————————————

Ordering Points To Identify the Clustering Structure，简称OPTICS，是一种基于密度的聚类算法。它的核心优势在于不需要预先指定簇的数量，且能够识别出具有不同密度、形状和大小的簇。以下是关于OPTICS算法的详细解释：

1. 基本概念

  • 可达性距离：对于两个点p和q，如果p是核心对象且q位于p的邻域内，则p到q的可达性距离定义为p的核心距离与p到q之间欧氏距离的最大值。如果p不是核心点，则p到q的可达性距离未定义。
  • 核心距离：一个点的核心距离是使其成为核心点的最小半径，即在给定邻域半径和最小点数参数下，该点邻域内至少有最小点数个点。

2. 算法步骤

  1. 初始化：标记所有数据点为未处理，并准备构建聚类顺序。
  2. 遍历数据点：按一定顺序（如数据集的初始顺序）遍历所有未处理点，标记当前点为已处理。
  3. 计算邻域：找出当前点的ε邻域内的所有点。
  4. 判断核心点：如果当前点邻域内的点数大于等于MinPts，则视其为核心点，并计算其邻域内所有点的可达距离。
  5. 排序与插入：将这些点按照可达距离从小到大排序，并插入一个优先队列（种子列表）中。
  6. 选择下一个处理点：从种子列表中选择具有最小可达距离的点作为下一个处理点，重复上述步骤。
  7. 记录可达距离：在遍历过程中，记录每个处理点的可达距离，从而构建最终的聚类顺序。
  8. 重复处理：持续从种子列表中提取点并处理，直到所有数据点被标记为已处理。

3. 聚类结果的提取

OPTICS算法并不直接产生聚类结果，而是生成一个增广的簇排序（例如，以可达距离为纵轴、样本点输出次序为横轴的坐标图）。这个排序代表了各样本点基于密度的聚类结构。用户可以通过观察这个排序图，并根据不同的密度阈值来提取聚类结果。

4. 参数选择

  • ε（邻域半径）：虽然OPTICS不像DBSCAN那样严格依赖于ε，但该参数仍用于限制邻域搜索的范围以提高算法效率。在实际应用中，可以根据数据的分布特性来选择合适的ε值。
  • MinPts（最小点数）：该参数决定了数据点被分类为核心点、边界点或噪声点的标准，从而影响最终的聚类结果。MinPts的选择应基于对数据集的理解和分析。

综上所述，OPTICS算法通过计算可达性距离和核心距离来识别数据中的聚类结构，无需预先指定簇的数量，且能够处理具有不同密度和形状的簇。这使得OPTICS在实际应用中具有广泛的适用性和灵活性。

##——————————————————————————————————————————————————————————————————————————————————————————————————————————————
“Ordering Points To Identify Cluster Structure”（排序点以识别聚类结构）通常简称为OPTICS算法，这是一种密度聚类算法。与传统的基于密度的空间聚类应用（DBSCAN）算法类似，OPTICS算法也是基于数据点的密度来发现数据集中的聚类结构，但它有一些独特的优势。

1. 基本概念

  • 核心点（Core Point）：与DBSCAN中类似，如果一个点的密度达到某个阈值（MinPts），则该点为核心点。给定一个点 ( p ) 和半径 ( \epsilon )，如果在以 ( p ) 为圆心，( \epsilon ) 为半径的邻域内（包括 ( p ) 自身）的点数不少于 ( MinPts )，则 ( p ) 是核心点。
  • 可达距离（Reachability Distance）：对于一个点 ( q ) 和核心点 ( p )，可达距离定义为 ( \max(\epsilon§, d(p, q)) )，其中 ( \epsilon§ ) 是 ( p ) 的最小邻域半径，使得 ( p ) 成为核心点，( d(p, q) ) 是 ( p ) 和 ( q ) 之间的距离。如果 ( p ) 不是核心点，那么 ( q ) 到 ( p ) 的可达距离是无穷大。
  • 核心距离（Core Distance）：对于一个核心点 ( p )，核心距离是使得 ( p ) 成为核心点的最小 ( \epsilon ) 值。如果 ( p ) 不是核心点，核心距离为无穷大。

2. 算法步骤

  1. 初始化：标记所有点为未处理，创建一个空的输出列表（用于存储排序后的点及其可达距离）。
  2. 选择一个未处理的核心点 ( p )：从数据集中选择一个尚未处理的核心点。如果没有未处理的核心点，则算法结束。
  3. 扩展聚类：
    • 将 ( p ) 加入输出列表。
    • 计算 ( p ) 的核心距离。
    • 对于 ( p ) 的直接密度可达点 ( q )（在 ( \epsilon ) 邻域内且点数不少于 ( MinPts ) 的点），计算 ( q ) 到 ( p ) 的可达距离，并将 ( q ) 加入输出列表。
    • 将 ( p ) 标记为已处理。
    • 对 ( p ) 的每个直接密度可达点 ( q )，如果 ( q ) 是核心点且未处理，则递归地进行扩展聚类。
  4. 重复步骤2和3：直到所有核心点都被处理。

3. Python代码示例

import numpy as npdef optics(data, min_pts, eps):n = len(data)# 标记点是否被处理过processed = np.zeros(n, dtype=bool)# 存储每个点的核心距离core_distances = np.full(n, np.inf)# 存储每个点的可达距离reachability_distances = np.full(n, np.inf)# 存储排序后的结果ordering = []def euclidean_distance(a, b):return np.linalg.norm(a - b)def get_neighbors(p):neighbors = []for i in range(n):if euclidean_distance(data[p], data[i]) <= eps:neighbors.append(i)return neighborsdef expand_cluster(p):core_distance_p = 0neighbors = get_neighbors(p)if len(neighbors) >= min_pts:core_distance_p = sorted([euclidean_distance(data[p], data[i]) for i in neighbors])[min_pts - 1]core_distances[p] = core_distance_pordering.append(p)for q in neighbors:if q != p:reachability_distance_q = max(core_distance_p, euclidean_distance(data[p], data[q]))if reachability_distance_q < reachability_distances[q]:reachability_distances[q] = reachability_distance_qif not processed[q]:processed[q] = Trueexpand_cluster(q)for i in range(n):if not processed[i]:processed[i] = Trueexpand_cluster(i)return ordering, core_distances, reachability_distances

4. 使用示例

# 生成一些示例数据
data = np.array([[1, 1], [2, 2], [3, 3], [4, 4], [10, 10], [11, 11], [12, 12]])
min_pts = 2
eps = 2ordering, core_distances, reachability_distances = optics(data, min_pts, eps)print("排序后的点索引:", ordering)
print("每个点的核心距离:", core_distances[ordering])
print("每个点的可达距离:", reachability_distances[ordering])

5. 算法优势

  • 不需要事先指定聚类的数量：不像 ( k )-means 算法需要事先指定 ( k ) 的值，OPTICS算法可以根据数据的密度自动发现聚类结构。
  • 能够处理不同密度的聚类：传统的基于密度的算法在处理不同密度的聚类时可能会遇到困难，而OPTICS算法可以更好地处理这种情况。

OPTICS算法在数据挖掘、机器学习等领域中常用于数据分析、模式识别和异常检测等任务，以发现数据集中隐藏的聚类结构。


http://www.mrgr.cn/news/96766.html

相关文章：

  • 【C++】vector常用方法总结
  • Springboot学习笔记3.28
  • JVM——模型分析、回收机制
  • 七. JAVA类和对象（二）
  • 消息中间件对比与选型指南：Kafka、ActiveMQ、RabbitMQ与RocketMQ
  • 前端界面在线excel编辑器 。node编写post接口获取文件流，使用传参替换表格内容展示、前后端一把梭。
  • LLM应用层推荐 -- 基于文档的问答tools Web UI 框架 开源向量库 -- 推荐、对比
  • 003-JMeter发起请求详解
  • Vue中将pdf文件转为图片
  • GitPython库快速应用入门
  • 【超详细】一文解决更新小米澎湃2.0后LSPose失效问题
  • 使用 Less 实现 PC 和移动端样式适配
  • pytorch模型的进阶训练和性能优化
  • uniapp -- 列表垂直方向拖拽drag组件
  • 【橘子大模型】关于PromptTemplate
  • 从 BBRv2 到 BBRv3
  • Windows搭建AI大模型应用开发环境以及踩过的坑
  • sourceinsight 4.0 任意配置主题颜色风格的方法
  • RCU机制以及内存优化屏障
  • 【408--考研复习笔记】计算机网络----知识点速览