【人工智能学习之聚类分析算法DBSCAN】
什么是DBSCAN
DBSCAN(Density-Based Spatial Clustering of Applications with Noise),即基于密度的空间聚类算法,是一种十分经典的聚类算法,它不需要事先知道要形成的簇类的数量,能够发现任意形状的簇,并且能够识别出数据集中的噪声点。
详细介绍
以下从多个方面对其进行详细介绍:
- 核心概念
- 邻域:对于样本集中的某一个点 (p),定义其邻域为距离点 (p) 小于等于某一给定距离 (\epsilon) 的所有点的集合,这个距离 (\epsilon) 称为邻域半径。
- 核心点:如果点 (p) 的 (\epsilon) 邻域内包含的点的数量(包括点 (p) 本身)不小于给定的阈值 (MinPts),则称点 (p) 为核心点。也就是说,在核心点的周围有足够多的点聚集,使得该点具有较高的密度。
- 边界点:点 (p) 的 (\epsilon) 邻域内点的数量小于 (MinPts),但点 (p) 落在某个核心点的 (\epsilon) 邻域内,这样的点被称为边界点。边界点本身密度不够高,但它与核心点是相关联的。
- 噪声点:既不是核心点也不是边界点的点就是噪声点,噪声点在空间中比较孤立,周围没有足够多的点聚集。
- 密度直达:如果点 (q) 在点 (p) 的 (\epsilon) 邻域内,且点 (p) 是核心点,则称点 (q) 从点 (p) 密度直达。
- 密度可达:对于点 (p) 和点 (q),如果存在一个点序列 (p_1, p_2, \cdots, p_n),其中 (p_1 = p),(p_n = q),并且对于 (i = 1, 2, \cdots, n - 1),点 (p_{i + 1}) 从点 (p_i) 密度直达,那么称点 (q) 从点 (p) 密度可达。
- 密度相连:如果存在一个核心点 (o),使得点 (p) 和点 (q) 都从点 (o) 密度可达,则称点 (p) 和点 (q) 密度相连。
- 算法流程
- 从数据集中随机选择一个未被访问过的点 (p)。
- 判断点 (p) 是否为核心点。如果点 (p) 不是核心点,则将其标记为噪声点;如果点 (p) 是核心点,则创建一个新的簇,并将点 (p) 及其 (\epsilon) 邻域内的所有点加入该簇。
- 对于点 (p) 的 (\epsilon) 邻域内的每个未访问过的点 (q),递归地处理点 (q)。如果点 (q) 是核心点,则将其 (\epsilon) 邻域内的所有未访问过的点加入当前簇。
- 重复步骤 1 - 3,直到数据集中的所有点都被访问过。
- 算法优点
- 不需要预先指定簇的数量:DBSCAN 能够根据数据的分布情况自动确定簇的数量,这在很多实际应用中非常方便,因为事先很难准确知道数据应该分成多少个簇。
- 能够发现任意形状的簇:与一些基于划分或层次的聚类算法(如 (K) - 均值算法只能发现球形的簇)不同,DBSCAN 基于密度的概念,可以发现各种不规则形状的簇。
- 能够识别噪声点:在聚类过程中,DBSCAN 可以将那些不属于任何簇的孤立点标记为噪声点,从而在数据处理中能够有效地去除噪声干扰。
- 算法缺点
- 对参数 (\epsilon) 和 (MinPts) 敏感:这两个参数的选择对聚类结果有很大影响。不同的参数设置可能导致完全不同的聚类结果,而且在实际应用中,很难事先确定合适的参数值。
- 计算复杂度较高:在数据量较大时,DBSCAN 的计算量会显著增加,因为它需要计算每个点的邻域,这涉及到大量的距离计算。
- 对于密度变化较大的数据聚类效果不佳:当数据集中不同簇的密度差异较大时,DBSCAN 可能无法很好地识别簇的边界,导致聚类结果不理想。因为它使用全局统一的密度阈值来定义簇,难以适应不同密度区域的情况。
对比DBSCAN和K-Means聚类算法的优缺点
DBSCAN和K-Means都是常见的聚类算法,它们在原理、应用场景等方面存在差异,优缺点也各有不同,在实际应用中,需要根据数据的特点(如数据的分布形状、是否存在噪声、数据规模等)以及具体的应用需求来选择合适的聚类算法。
以下从多个方面对它们进行对比:
- 聚类原理及对簇形状的适应性
- DBSCAN:基于密度的概念来发现簇,只要区域的点密度大于某个阈值,就将这些点划分为一个簇,能识别出任意形状的簇,尤其适用于发现不规则形状的数据集结构。比如在地理信息数据中,城市分布可能呈现不规则形状,DBSCAN能较好地聚类出不同的城市聚集区域。
- K-Means:基于距离划分的聚类算法,通过计算数据点到 (K) 个初始质心的距离,将每个数据点分配到距离最近的质心所在的簇,然后不断更新质心位置,直到收敛。它倾向于发现球形的簇,对于非球形的簇,聚类效果可能不佳。例如,对于呈细长条形分布的数据,K-Means可能无法准确地划分出符合数据分布的簇。
- 对簇数量的要求
- DBSCAN:不需要事先知道要形成的簇类的数量。它根据数据的密度分布情况自动确定簇的数量,在数据簇数量未知的情况下具有很大优势。例如在对未知分布的用户行为数据进行聚类时,无需预先估计簇的数量。
- K-Means:需要预先指定聚类的簇数 (K)。然而在实际应用中,很难准确地知道数据应该划分成多少个簇, (K) 值选择不当会导致聚类结果不理想。比如在对图像中的物体进行聚类时,如果 (K) 值设置错误,可能会将同一类物体分成多个簇,或者将不同类物体归为一个簇。
- 对噪声点和离群点的处理
- DBSCAN:能够识别出数据集中的噪声点和离群点。它将那些不在任何核心点密度可达范围内的点标记为噪声点,在聚类过程中可以有效地过滤掉这些干扰点,对噪声具有较好的鲁棒性。例如在异常交易数据检测中,DBSCAN可以将孤立的异常交易记录识别为噪声点。
- K-Means:对噪声点和离群点比较敏感。由于K-Means算法的目标是最小化每个数据点到其所属簇质心的距离之和,噪声点和离群点会对质心的计算产生较大影响,从而导致聚类结果的偏差。例如,数据集中存在少量极大值或极小值的离群点时,会使质心的位置发生偏移,进而影响整个聚类的准确性。
- 计算复杂度
- DBSCAN:在数据量较大时,计算复杂度较高。它需要计算每个点的邻域,涉及大量的距离计算,其时间复杂度通常为 (O(n^2)),其中 (n) 是数据点的数量。虽然可以通过一些优化方法(如使用空间索引)来降低计算复杂度,但在高维数据或大规模数据集上,计算仍然较为耗时。
- K-Means:一般情况下,K-Means算法的时间复杂度为 (O(nkt)),其中 (n) 是数据点的数量,(k) 是簇的数量,(t) 是迭代次数。通常 (k) 和 (t) 相对较小,因此在处理大规模数据集时,K-Means的计算效率相对较高,比DBSCAN更适合处理大规模数据。
- 聚类结果的稳定性
- DBSCAN:聚类结果相对稳定,只要数据的密度分布不发生变化,即使数据点的输入顺序不同,得到的聚类结果基本相同。因为它是基于数据点之间的密度关系进行聚类,而不是依赖于初始点的选择。
- K-Means:聚类结果受初始质心选择的影响较大。不同的初始质心可能导致不同的聚类结果,甚至可能收敛到局部最优解,而不是全局最优解。为了得到较好的聚类结果,通常需要多次运行K-Means算法并选择最优的结果。
DBSCAN的实际应用
DBSCAN(基于密度的空间聚类算法)因其能够发现任意形状的簇以及识别噪声点的特性,在数据分析、模式识别、机器学习等多个领域都有广泛且具体的实际应用,如地理信息系统中的空间数据分析、图像识别中的目标检测等,以下我将详细介绍一些实际应用场景:
- 地理信息系统(GIS)与空间数据分析
- 城市规划与土地利用分析:在城市规划中,通过DBSCAN对城市中不同区域的建筑物、人口分布等数据进行聚类分析,能够发现城市中的商业中心、住宅区、工业区等不同功能区域。由于这些区域的分布往往不规则,DBSCAN能根据建筑物或人口的密度,准确划分出各个功能区,为城市规划提供有力支持。
- 交通流量监测与分析:在交通领域,DBSCAN可用于分析交通流量数据。通过对道路上不同位置的交通流量密度进行聚类,能够识别出交通拥堵区域和正常行驶区域。此外,还能根据交通流量的变化模式,发现不同的交通流特征,如高峰时段的拥堵路段分布等,有助于交通管理部门制定合理的交通疏导策略。
- 野生动物栖息地分析:在生态研究中,利用DBSCAN对野生动物的活动轨迹数据进行聚类,可确定野生动物的栖息地和活动热点区域。根据动物活动点的密度,能够发现它们经常出没的区域,这些区域通常具有适宜的生存环境。这对于野生动物保护和生态环境评估具有重要意义。
- 图像识别与计算机视觉
- 目标检测与分割:在图像中,DBSCAN可以用于检测和分割不同的物体。例如,在遥感图像中,通过对图像像素点的特征(如颜色、纹理等)进行聚类,能够将图像中的不同地物(如建筑物、道路、植被等)区分开来。由于地物的形状往往不规则,DBSCAN能够根据像素点的密度分布,准确地分割出各个地物区域,为图像理解和分析提供基础。
- 图像降噪:DBSCAN能够识别图像中的噪声点。在图像采集和处理过程中,常常会引入噪声,影响图像的质量。通过将图像像素点视为数据点,利用DBSCAN的密度概念,可以将那些孤立的噪声点(即不属于任何高密度区域的点)识别出来并进行去除,从而提高图像的清晰度和质量。
- 客户细分与市场分析
- 客户行为分析:在商业领域,企业可以收集客户的各种行为数据,如购买频率、购买金额、浏览记录等。使用DBSCAN对这些数据进行聚类分析,能够发现不同类型的客户群体。例如,根据客户的购买行为密度,可将客户分为高频高消费客户、低频高消费客户、高频低消费客户等不同群体,企业可以针对不同群体制定个性化的营销策略,提高客户满意度和忠诚度。
- 市场趋势分析:通过对市场数据(如产品销售数据、市场份额数据等)进行DBSCAN聚类,可以发现市场中的不同趋势和模式。例如,根据不同产品在不同地区的销售密度,能够识别出哪些地区是产品的主要销售区域,哪些地区具有市场潜力,从而帮助企业合理分配资源,优化市场布局。
- 异常检测与故障诊断
- 网络安全检测:在网络安全领域,DBSCAN可用于检测网络流量中的异常行为。正常的网络流量通常具有一定的模式和密度分布,而异常流量(如黑客攻击、恶意软件传播等)往往表现为孤立的、与正常流量模式不同的流量。通过对网络流量数据点进行密度聚类,能够识别出这些异常流量,及时发现网络安全威胁。
- 设备故障诊断:在工业生产中,设备的运行数据(如温度、压力、振动等参数)可以看作是数据点。利用DBSCAN对这些数据进行聚类分析,能够发现设备正常运行时的数据模式。当设备出现故障时,其运行数据会发生变化,可能会形成与正常模式不同的低密度区域或孤立点,从而帮助工程师及时发现设备故障并进行维修。
- 医疗数据分析
- 疾病诊断与分类:在医疗领域,医生可以收集患者的各种生理指标数据(如血压、血糖、心率等)和症状信息。通过DBSCAN对这些数据进行聚类分析,能够发现不同类型的疾病模式或患者群体。例如,根据患者的症状和生理指标密度,可将患有相似疾病的患者归为一类,有助于医生进行疾病诊断和制定个性化的治疗方案。
- 药物疗效评估:在药物临床试验中,DBSCAN可用于分析患者对药物的反应数据。根据患者在服用药物后的各项指标变化情况,通过密度聚类可以将患者分为药物有效组和药物无效组,从而评估药物的疗效,为药物研发和临床应用提供参考。
DBSCAN调用方法
DBSCAN(eps=0.5, *, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=None)
以下是对 DBSCAN 算法的调用方法 DBSCAN(eps=0.5, *, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=None)
中各个参数的详细解释:
- eps(epsilon):
- 类型:浮点数。
- 含义:邻域的半径,即一个点的邻域范围大小。如果在该半径范围内的数据点数量超过
min_samples
,则该点被认为是核心点。 - 示例:
eps=0.5
表示邻域半径为 0.5。该参数的大小对聚类结果有很大影响,较小的eps
可能导致较多的噪声点和较小的簇,而较大的eps
可能会将多个簇合并为一个。
- min_samples:
- 类型:整数。
- 含义:核心点所需的邻域内最小数据点数量。一个点的
eps
邻域内的数据点数量达到或超过min_samples
时,该点被认为是核心点。 - 示例:
min_samples=5
表示一个点的邻域内至少要有 5 个点(包括该点自身)才会被视为核心点。此参数也会影响聚类结果,较大的min_samples
会使得形成簇的条件更严格,可能导致更多的点被标记为噪声。
- metric:
- 类型:字符串或可调用对象。
- 含义:用于计算两点之间距离的度量标准。默认是
'euclidean'
,即欧几里得距离,也可以使用其他度量,如'manhattan'
(曼哈顿距离)、'chebyshev'
(切比雪夫距离)等。如果提供了可调用对象,则该对象应接收两个一维数组作为输入,并返回它们之间的距离。 - 示例:
metric='manhattan'
将使用曼哈顿距离作为距离度量,这对于某些数据集可能会产生不同的聚类结果,特别是在高维空间中,不同的距离度量可以反映不同的数据相似性特征。
- metric_params:
- 类型:字典或 None。
- 含义:用于传递给
metric
函数的额外参数。如果metric
函数需要额外参数,可以使用此参数传递。通常情况下为None
,表示不传递额外参数。 - 示例:如果使用自定义的距离度量函数,可能需要传递额外的参数,如
metric_params={'p': 2}
。
- algorithm:
- 类型:字符串。
- 含义:用于计算最近邻的算法。可选项有
'auto'
(自动选择)、'ball_tree'
、'kd_tree'
或'brute_force'
。'auto'
会根据数据集的特点自动选择合适的算法,'ball_tree'
和'kd_tree'
使用特定的数据结构加速计算,'brute_force'
则使用暴力搜索。 - 示例:
algorithm='kd_tree'
表示使用 KD 树算法计算最近邻。对于小型数据集,'brute_force'
可能足够,但对于大型数据集,使用'ball_tree'
或'kd_tree'
可能会更高效。
- leaf_size:
- 类型:整数。
- 含义:当使用
'ball_tree'
或'kd_tree'
算法时,该参数影响构建树的叶子节点大小。调整该参数可以在一定程度上优化性能,但通常使用默认值即可。 - 示例:
leaf_size=30
是一个典型的设置。较大的leaf_size
可以减少树的深度,但可能会降低搜索的精度;较小的leaf_size
会增加树的深度,但可能提高搜索精度。
- p:
- 类型:整数或 None。
- 含义:当
metric='minkowski'
时,p
是 Minkowski 距离的参数。对于p=1
是曼哈顿距离,p=2
是欧几里得距离。如果metric
不是minkowski
距离,则该参数无效。 - 示例:
p=1
表示使用曼哈顿距离,这在metric='minkowski'
时会被使用。
- n_jobs:
- 类型:整数或 None。
- 含义:并行计算时使用的 CPU 数量。
None
表示使用单线程,-1
表示使用所有可用的 CPU 核心,其他正整数表示使用相应数量的核心。 - 示例:
n_jobs=-1
会使用所有可用的 CPU 核心进行并行计算,可加速计算过程,尤其是对于大型数据集。
以下是使用 DBSCAN 算法的一般步骤:
from sklearn.cluster import DBSCAN
import numpy as np
# 假设我们有一个数据集 X,它是一个二维数组
X = np.array([[1, 2], [1.5, 1.8], [5, 8], [8, 8], [1, 0.6], [9, 11]])
# 创建 DBSCAN 对象并进行聚类
dbscan = DBSCAN(eps=0.5, min_samples=2)
labels = dbscan.fit_predict(X)
# 打印每个点的聚类标签
print(labels)
代码解释:
- 首先,我们从
sklearn.cluster
中导入DBSCAN
类。 - 然后,我们创建一个示例的数据集
X
,它包含了一些二维数据点。 - 接着,我们创建一个
DBSCAN
对象,设置eps=0.5
和min_samples=2
。 - 使用
fit_predict
方法将DBSCAN
对象应用于数据集X
,并得到每个点的聚类标签存储在labels
中。 - 最后,打印出
labels
,-1
表示噪声点,其他数字表示不同的簇。
在实际应用中,你需要根据数据的特征调整 eps
和 min_samples
参数,以获得满意的聚类效果。同时,你可以根据数据的规模和计算资源选择不同的 algorithm
和 n_jobs
来优化计算性能。不同的 metric
也可以用来探索数据之间不同的相似性度量方式,可能会得到不同的聚类结果。
具体代码示例:人群密度测算
核心代码部分:
def dbscan(xy,img):
X = xy[:, :2]
# 使用DBSCAN聚类算法
dbscan = DBSCAN(eps=220, min_samples=2)
labels = dbscan.fit_predict(X)
# 输出聚类结果
for i in range(max(labels) + 1):
print(f"Cluster {i + 1}: {list(X[labels == i])}")
cluster_points = X[labels == i]
# 在 img 上划红线连接每个聚类点
for j in range(len(cluster_points) - 1):
cv2.line(img, tuple(cluster_points[j].astype(int)), tuple(cluster_points[j + 1].astype(int)), (0, 0, 255),
2)
print(f"Noise: {list(X[labels == -1])}")
# 在 img 上用蓝色显示每个噪声点
noise_points = X[labels == -1]
for point in noise_points:
cv2.circle(img, tuple(point.astype(int)), 5, (255, 0, 0), -1)
cv2.imshow("Clustered Image", img)
测试图片:
demo代码(需要自备一个人头检测模型):
from distutils.command.config import config
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import LinearRegression
import cv2
import time
from ultralytics import YOLO
import os
import numpy as np
def dbscan(xy,img):
X = xy[:, :2]
# 使用DBSCAN聚类算法
dbscan = DBSCAN(eps=220, min_samples=2)
labels = dbscan.fit_predict(X)
# 输出聚类结果
for i in range(max(labels) + 1):
print(f"Cluster {i + 1}: {list(X[labels == i])}")
cluster_points = X[labels == i]
# 在 img 上划红线连接每个聚类点
for j in range(len(cluster_points) - 1):
cv2.line(img, tuple(cluster_points[j].astype(int)), tuple(cluster_points[j + 1].astype(int)), (0, 0, 255),
2)
print(f"Noise: {list(X[labels == -1])}")
# 在 img 上用蓝色显示每个噪声点
noise_points = X[labels == -1]
for point in noise_points:
cv2.circle(img, tuple(point.astype(int)), 5, (255, 0, 0), -1)
cv2.imshow("Clustered Image", img)
YOLO_LOAD = './best.pt'
img = cv2.imread(r'./R.jpg')
model = YOLO(YOLO_LOAD)
results = model(img)
processed_frame = results[0].plot(labels=False,conf=False)
cv2.imshow('processed_frame', processed_frame)
xy = results[0].boxes.xywh.cpu().numpy()
# 记录程序开始时间
start_time = time.time()
dbscan(xy,img)
# 记录程序结束时间
end_time = time.time()
# 计算时间差并转换为毫秒,打印输出整体用时
elapsed_time = (end_time - start_time) * 1000
print(f"聚类算法用时: {elapsed_time:.2f} ms")
cv2.waitKey(0)
cv2.destroyAllWindows()
输出结果:
0: 640x416 8 heads, 75.9ms
Speed: 2.0ms preprocess, 75.9ms inference, 65.1ms postprocess per image at shape (1, 3, 640, 416)
Cluster 1: [array([ 251, 64.936], dtype=float32), array([ 446.12, 81.674], dtype=float32), array([ 335.35, 338.98], dtype=float32), array([ 137.84, 248.46], dtype=float32), array([ 457.16, 254.19], dtype=float32)]
Cluster 2: [array([ 329.67, 775.98], dtype=float32), array([ 382.25, 617.78], dtype=float32), array([ 192.87, 700.01], dtype=float32)]
Noise: []
聚类算法用时: 154.30 ms
效果图片:
修改参数
这里我们对 dbscan = DBSCAN(eps=220, min_samples=2)
中的eps稍作修改,改为200,让我们看看结果有什么不同:
输出结果:
0: 640x416 8 heads, 83.9ms
Speed: 3.0ms preprocess, 83.9ms inference, 74.1ms postprocess per image at shape (1, 3, 640, 416)
Cluster 1: [array([ 251, 64.936], dtype=float32), array([ 446.12, 81.674], dtype=float32), array([ 335.35, 338.98], dtype=float32), array([ 457.16, 254.19], dtype=float32)]
Cluster 2: [array([ 329.67, 775.98], dtype=float32), array([ 382.25, 617.78], dtype=float32), array([ 192.87, 700.01], dtype=float32)]
Noise: [array([ 137.84, 248.46], dtype=float32)]
聚类算法用时: 164.80 ms
效果图片:
显然,有一个点被孤立了,算法视其为噪声点。