学习日记_20241115_聚类方法（DBSCAN）

🕗 发布于 2024-11-18 22:44 学习聚类 机器学习

前言

提醒：
文章内容为方便作者自己后日复习与查阅而进行的书写与发布，其中引用内容都会使用链接表明出处（如有侵权问题，请及时联系）。
其中内容多为一次书写，缺少检查与订正，如有问题或其他拓展及意见建议，欢迎评论区讨论交流。

聚类算法

聚类算法在各种领域中有广泛的应用，主要用于发现数据中的自然分组和模式。以下是一些常见的应用场景以及每种算法的优缺点：

经典应用场景

市场细分：根据消费者的行为和特征，将他们分成不同的群体，以便进行有针对性的营销。
图像分割：将图像划分为多个区域或对象，以便进行进一步的分析或处理。
社交网络分析：识别社交网络中的社区结构。
文档分类：自动将文档分组到不同的主题或类别中。
异常检测识别数据中的异常点或异常行为。
基因表达分析：在生物信息学中，根据基因表达模式对基因进行聚类。

层次聚类

DBSCAN
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，广泛应用于数据挖掘和模式识别。它具有一些显著的优点和缺点，下面我将分别介绍。

优点

无需指定簇的数量：与 K-means 等方法不同，DBSCAN 不需要用户事先指定聚类的数量。它能够根据数据的分布自动识别簇的数量。

处理任意形状的簇：DBSCAN 可以发现任意形状的簇，而不仅限于球形。这使得它在处理复杂数据集时表现优良。

对噪声的鲁棒性：DBSCAN 可以有效识别并处理噪声点，将其标记为离群点，而不是将其归入某个簇中。

适用于大规模数据集：在某些实现中，DBSCAN 可以利用索引结构（如 KD 树或球树）来加速邻域查询，从而在处理大规模数据集时提高效率。

可扩展性：DBSCAN 可以通过调整参数（如 ε 和 MinPts）来适应不同的数据特征，使其具有一定的灵活性。

缺点

参数敏感性：DBSCAN 的性能高度依赖于 ε（邻域半径）和 MinPts（核心点的最小邻居数）的选择。选择不当可能导致聚类效果不佳。

处理不同密度簇的能力：对于具有不同密度的簇，DBSCAN 可能难以找到合适的参数，导致高密度簇合并或低密度簇被错误地分类为噪声。

计算复杂度：虽然 DBSCAN 的平均时间复杂度为 O(n log n)，但在最坏情况下，使用暴力搜索时可能达到 O(n^2)，尤其是在数据量很大时会影响效率。

高维数据问题：在高维空间中，距离度量的有效性下降，DBSCAN 的性能可能受到影响，可能导致无法找到足够的邻域来形成核心点。

噪声点分类问题：边界点可能会被错误分类为噪声或归入不恰当的簇，从而影响聚类的结果。

不支持在线学习：DBSCAN 主要用于静态数据集，对于动态数据或实时更新的数据，无法有效进行增量更新，必须重新计算整个数据集的聚类。

总结

DBSCAN 是一种强大的聚类算法，适用于发现复杂形状的簇和处理噪声。然而，在使用时需要谨慎选择参数，并注意其对不同密度簇和高维数据的处理能力。根据具体应用场景，可能需要结合其他聚类方法以获得更好的结果。

简单实例（函数库实现）

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN

# 生成示例数据集（两个半月形状）
X, y = make_moons(n_samples=300, noise=0.1, random_state=42)

# 创建 DBSCAN 聚类模型
# 创建 DBSCAN 模型，并指定 eps（邻域的半径）和 min_samples（核心点的最小邻居数）。
dbscan = DBSCAN(eps=0.2, min_samples=5)

# 拟合模型并预测聚类标签
labels = dbscan.fit_predict(X)

# 绘制聚类结果
# 使用 matplotlib 绘制聚类结果，不同的颜色表示不同的簇，黑色表示噪声点。
plt.figure(figsize=(10, 6))
unique_labels = set(labels)
colors = plt.cm.get_cmap('Spectral', len(unique_labels))

for k in unique_labels:
    class_member_mask = (labels == k)
    xy = X[class_member_mask]
    plt.scatter(xy[:, 0], xy[:, 1], s=30, color=colors(k), label=f'Cluster {k}' if k != -1 else 'Noise')

plt.title('DBSCAN Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()
plt.show()

#数据可视化
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
# 生成数据
X, y = make_moons(n_samples=300, noise=0.1, random_state=42)
# 绘制数据
plt.scatter(X[:, 0], X[:, 1], c=y, cmap='viridis', edgecolor='k', s=50)
plt.title("Moon Dataset")
plt.show()

数据分布：

运行结果：

代码分析

class_member_mask = (labels == k)

class_member_mask = (labels == k) 这一行代码的作用是创建一个布尔数组（mask），用于标识属于特定聚类的样本。让我们逐步解释这行代码的含义和作用。

label=f’Cluster {k}’ if k != -1 else ‘Noise’

label=f'Cluster {k}' if k != -1 else 'Noise'

label 参数用于设置当前散点图的图例标签。
f'Cluster {k}' 是一个格式化字符串，用于指示当前绘制的是聚类 k。
if k != -1 的条件是为了处理噪声点，噪声点的标签为 -1，因此如果当前聚类是噪声，标签将设置为 'Noise'。

数学解释

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法。它的主要思想是通过密度来识别聚类，能够有效处理具有任意形状的聚类，并能够识别噪声点。以下是 DBSCAN 的主要概念和数学公式的详细解释。。

主要概念

ε（epsilon）：ε 是定义邻域的半径，表示一个点周围的邻域范围。
MinPts：MinPts 是一个参数，表示在 ε 半径内需要至少有多少个点才能被认为是一个核心点。
核心点、边界点、噪声点：
核心点：如果一个点的 ε 邻域内的点的数量（包括自身）大于或等于 MinPts，那么这个点就是核心点。
边界点：如果一个点的 ε 邻域内的点的数量小于 MinPts，但该点在某个核心点的 ε 邻域内，那么该点就是边界点。
噪声点：如果一个点既不是核心点，也不是边界点，那么该点就是噪声点。

数学公式

邻域定义：

对于一个点 $P$ ，其 ε 邻域是指所有与 $P$ 距离小于或等于 ε 的点集合，表示为：
$N_\epsilon(P) = \{Q \in D | \text{dist}(P, Q) \leq \epsilon\}$
其中 $D$ 是数据集， $\text{dist}(P, Q)$ 是点 $P$ 和点 $Q$ 之间的距离（通常使用欧几里得距离）。

核心点的定义：

点 $P$ 是核心点，当且仅当：
$|N_\epsilon(P)| \geq \text{MinPts}$
这里 $|N_\epsilon(P)|$ 表示点 $P$ 的 ε 邻域内的点的数量。

聚类的形成：
- 从任意一个核心点出发，通过递归地访问其邻域内的核心点，构建一个聚类。这个过程可以用以下方式描述：
- 对于每个核心点 $P$ ，访问其 ε 邻域内所有的点 $Q$ ：
- 如果 $Q$ 也是核心点，则继续访问 $Q$ 的 ε 邻域。

实际步骤

选择一个未被访问的点 $P$ 。
检查 $P$ 的 ε 邻域，如果是核心点，则开始一个新聚类。
将所有在 $P$ ε 邻域内的点加入聚类，如果这些点是核心点，则继续扩展聚类。
重复步骤 1 到 3，直到没有未被访问的核心点。

总结

DBSCAN 是一种基于密度的聚类算法，它通过定义邻域和核心点来识别聚类和噪声，对于具有复杂形状和不同密度的聚类有良好的表现。通过合理选择 ε 和 MinPts 参数，可以使得 DBSCAN 在不同的数据集上获得良好的聚类效果。

手动实现

import numpy as np
from collections import deque

# 计算欧几里得距离
def euclidean_distance(p1, p2):
    return np.linalg.norm(p1 - p2)

# 查找邻域点
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
    
# DBSCAN 算法
def dbscan(X, eps, min_pts):
    n_points = X.shape[0]
    labels = np.zeros(n_points)  # 0: 未访问，-1: 噪声，其他: 聚类编号
    cluster_id = 0
    
    for point_idx in range(n_points):
        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[point_idx] = cluster_id
            queue = deque(neighbors)
            while queue:
                current_point_idx = queue.popleft()
                if labels[current_point_idx] == 0:
                    labels[current_point_idx] = cluster_id
                    current_neighbors = region_query(X, current_point_idx, eps)
                    if len(current_neighbors) >= min_pts:
                        queue.extend(current_neighbors)
                elif labels[current_point_idx] == -1:
                    labels[current_point_idx] = cluster_id
    
    return labels

# 示例数据生成
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

# 生成示例数据
X, _ = make_blobs(n_samples=300, centers=3, cluster_std=0.60, random_state=0)

# 使用 DBSCAN 进行聚类
eps = 0.5  # 邻域半径
min_pts = 5  # 最小邻居点数
labels = dbscan(X, eps, min_pts)
plt.figure(figsize=(10, 5))
plt.subplot(1, 2, 1)
plt.scatter(X[:, 0], X[:, 1])
plt.title('X data')
# 可视化聚类结果
plt.subplot(1, 2, 2)
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.title('DBSCAN Result')
plt.show()

结果为：

代码分析

np.linalg.norm(p1 - p2)

np.linalg.norm函数可以用来计算向量或矩阵的范数即两个点之间的欧几里得距离。

范数介绍

范数是数学中用于衡量向量“大小”的一个概念，它是向量空间中的一个函数，将每个向量映射到一个非负实数。在向量空间中，范数具有以下基本性质：

非负性：对于所有的向量 $\mathbf{v}$ ，范数 $\|\mathbf{v}\|$ 都是非负的，且 $\|\mathbf{v}\| = 0$ 当且仅当 $\mathbf{v}$ 是零向量。
齐次性：对于所有的标量 $\alpha$ 和向量 $\mathbf{v}$ ，有 $\|\alpha \mathbf{v}\| = |\alpha| \|\mathbf{v}\|$ 。
三角不等式：对于所有的向量 $\mathbf{u}$ 和 $\mathbf{v}$ ，有 $\|\mathbf{u} + \mathbf{v}\| \leq \|\mathbf{u}\| + \|\mathbf{v}\|$ 。
以下是一些常见的范数类型：
欧几里得范数（L2范数）
对于 $n$ 维向量 $\mathbf{v} = (v_1, v_2, ..., v_n)$ ，其欧几里得范数定义为：
$\|\mathbf{v}\|_2 = \sqrt{\sum_{i=1}^{n} v_i^2}$
这是最常用的范数，对应于空间中两点之间的直线距离。
曼哈顿范数（L1范数）
曼哈顿范数定义为向量各分量绝对值之和：
$\|\mathbf{v}\|_1 = \sum_{i=1}^{n} |v_i|$
这个范数对应于在城市街道上从一个点到另一个点的距离（只能沿着街道走）。
无穷范数（L∞范数）
无穷范数定义为向量各分量绝对值中的最大值：
$\|\mathbf{v}\|_\infty = \max_{1 \leq i \leq n} |v_i|$
这个范数表示向量在各个方向上可能达到的最大“延伸”。
p-范数（Lp范数）
更一般地，对于 $p\geq 1$ ，向量 $\mathbf{v}$ 的 $p$ -范数定义为：
$\|\mathbf{v}\|_p = \left( \sum_{i=1}^{n} |v_i|^p \right)^{1/p}$
当 $p = 2$ 时， $p$ -范数就是欧几里得范数；当 $p = 1$ 时， $p$ -范数就是曼哈顿范数；当 $p$ 趋向于无穷大时， $p$ -范数就是无穷范数。
范数在数学、物理学、工程学、计算机科学等领域中都有广泛的应用。在机器学习中，范数常用于正则化，以防止模型过拟合。例如，L2正则化（岭回归）和L1正则化（Lasso）就是使用L2范数和L1范数来惩罚模型的复杂度。

队列

collections 模块中的 deque（双端队列）对象提供了一系列方法，用于在队列的两端进行高效的添加、移除和访问元素的操作。以下是一些基本的 deque 操作方法：

初始化： from collections import deque中d = deque([iterable])建立队列对象。
添加元素：
append(x)：在队列的右侧（尾部）添加一个元素。
appendleft(x)：在队列的左侧（头部）添加一个元素。

移除元素：
pop()：移除并返回队列右侧（尾部）的元素，如果队列为空，抛出 IndexError。
popleft()：移除并返回队列左侧（头部）的元素，如果队列为空，抛出 IndexError。

访问元素：
index(x)：返回元素 x 在队列中的位置（从0开始计数）
count(x)：返回元素 x 在队列中出现的次数。

旋转队列：
rotate(n=1)：将队列中的元素向右旋转 n 步，如果 n 是负数，则向左旋转。

扩展队列：
extend(iterable)：在队列的右侧（尾部）添加多个元素，这些元素来自一个可迭代对象。
extendleft(iterable)：在队列的左侧（头部）添加多个元素，这些元素来自一个可迭代对象，注意元素会以相反的顺序添加。

其他操作：
remove(value)：移除队列中第一个出现的 value，如果不存在，抛出 ValueError。
reverse()：将队列中的元素顺序反转。
clear()：移除队列中的所有元素，使其变为空队列。

队列长度：
len(d)：返回队列中的元素数量。

队列是否为空：
not d：如果队列为空，返回 True，否则返回 False。

迭代队列：
可以使用 for 循环直接迭代队列中的元素。

原文地址：https://blog.csdn.net/2301_81791289/article/details/143808163

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：chatgpt训练需要什么样的gpu硬件
下一篇：常见长选项和短选项对应表

PCL 三维重建 RBF移动立方体三维重建算法
RBF（径向基函数）Marching Cubes算法是一种基于RBF插值的方法，用于从点云数据中提取三维表面。这种算法结合了传统的Marching Cubes算法和径向基函数的优势，能够处理复杂的点云
阅读更多2024-11-19
Argo workflow 拉取git 并使用pvc共享文件
第一个任务（拉取 Git 仓库）：这个任务将使用 git 命令克隆指定的 Git 仓库。第二个任务（读取 Git 文件）：这个任务会读取第一个任务拉取的 Git 仓库中的文件。我们将使用 Argo W
阅读更多2024-11-19
java计算机毕业设计选题参考3000篇
【294】springboot+jpa+layui学生住宿管理系统mysql学生寝室分配系统含文档。基于微信小程序的社区车位租赁系统的设计与实现+springboot后台weixin200。【483】
阅读更多2024-11-19
《Python网络安全项目实战》项目6 编写密码工具程序_练习题(2)答案
《Python网络安全项目实战》项目6 编写密码工具程序_练习题(2)答案
阅读更多2024-11-19
三种方式js的引入
1.js的组成部分：BOM(browser object model)浏览器对象模型、DOM(document object model)文档对象模型、ECMAScript。2.js的引入方式:行内式
阅读更多2024-11-19
使用MQTTX连接新版ONENet
使用mqtt连接新版的onenet 教程包含产品创建设备创建，关键参数获取，token软件获取，token生成，mqttx软件的下载与使用数据流的上传等手把手操作帮助你上云
阅读更多2024-11-19
深度学习之其他常见的生成式模型
自回归模型通过对图像数据的概率分布pdataxpdatax进行显式建模，并利用极大似然估计优化模型。pdatax∏i1npxi∣x1x2xi−1pdataxi1∏npxi∣x1x2..
阅读更多2024-11-19
MySQL表的新增与查询
这里的值要和列的个数和类型相匹配使用'或者"来表示字符串。
阅读更多2024-11-19
Vue-组件三大组成&组件通信
style的默认样式是作用到哪里的？scoped的作用是什么？style中推不推荐加scoped？data写成函数的目的是什么？组件通信，就是指组件与组件之间的数据传递组件的数据是独立的，无法直接访问
阅读更多2024-11-19
Python爬虫学习路线精简大纲！！！
Python爬虫学习路线精简大纲！！！
阅读更多2024-11-19

学习日记_20241115_聚类方法（DBSCAN）

前言

文章目录

聚类算法

经典应用场景

层次聚类

优点

缺点

总结

简单实例（函数库实现）

代码分析

class_member_mask = (labels == k)

label=f’Cluster {k}’ if k != -1 else ‘Noise’

数学解释

主要概念

数学公式

实际步骤

总结

手动实现

代码分析

np.linalg.norm(p1 - p2)

范数介绍

队列

相关文章