DBSCAN聚类算法简介

Question

如题所述

Answer 1

DBSCAN（Density—Based Spatial Clustering of Application with Noise）算法是一种典型的基于密度的聚类方法，能将具有足够密度的区域划分为簇，并能在包含噪音的空间数据集中发现任意形状的簇。
DBSCAN算法有两个关键参数：Eps和MinPts。Eps定义密度时的邻域半径，MinPts为定义核心点时的阈值。数据点被分为三类：核心点、边界点和噪音点。核心点是指在其半径Eps内含有超过MinPts数量的点；边界点是在其半径Eps内含有点的数量少于MinPts，但位于核心点邻域内的点；噪音点是既不是核心点也不是边界点的点。
核心点对应稠密区域内部的点，边界点对应稠密区域边缘的点，噪音点对应稀疏区域中的点。例如，在图1中，假设MinPts=5，Eps如图中箭头线所示，点A为核心点，点B为边界点，点C为噪音点。点A因为在其Eps邻域内含有7个点，超过了Eps=5，所以是核心点。点E和点C因为在其Eps邻域内含有点的个数均少于5，所以不是核心点；点B因为落在了点A的Eps邻域内，所以点B是边界点；点C因为没有落在任何核心点的邻域内，所以是噪音点。
在DBSCAN算法中，数据点的邻域、直接密度可达、密度可达、密度相连等概念很重要。在图2中，点a为核心点，点b为边界点，并且因为a直接密度可达b。但是b不直接密度可达a（因为b不是一个核心点）。因为c直接密度可达a，a直接密度可达b，所以c密度可达b。但是因为b不直接密度可达a，所以b不密度可达c。但是b和c密度相连。
DBSCAN算法对簇的定义很简单，由密度可达关系导出的最大密度相连的样本集合，即为最终聚类的一个簇。算法描述为：从数据集中任意选取一个数据对象点p，如果对于参数Eps和MinPts，所选取的数据对象点p为核心点，则找出所有从p密度可达的数据对象点，形成一个簇；如果选取的数据对象点p是边缘点，选取另一个数据对象点；重复上述步骤，直到所有点被处理。算法的复杂度为O(n²)，n为数据对象的数目。算法对输入参数Eps和MinPts敏感。
DBSCAN算法实例：使用样本数据集，如表1所示，实施DBSCAN算法进行聚类，取Eps=3，MinPts=3。数据集中的样本数据在二维空间内的表示如图3所示。第一步，顺序扫描数据集的样本点，首先取到p1(1,2)。计算p1的邻域，p1为核心点，建立簇C1，包含点{p1,p2,p3,p13,p4}。第二步，取到p5(5,8)，计算出p5为核心点，建立簇C2，包含点{p5,p6,p7,p8}。第三步，取到p9(9,5)，不是核心点，处理结束。第四步，取到p10(1,12)，不是核心点，处理结束。第五步，取到p11(3,12)，是核心点，建立簇C3，包含点{p11,p10,p12}。第六步，扫描数据的样本点，p12、p13都被处理过，算法结束。
DBSCAN算法的优点包括：能够对任意形状的稠密数据集进行聚类，不需输入簇数k，可以在聚类时发现异常点。缺点包括：在样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差；样本集较大时，聚类收敛时间较长；调试参数复杂，不同的参数组合对最后的聚类效果有较大影响；不适用于数据集中存在不同密度的簇或嵌套簇的情况；过滤噪声点的同时造成了其不适用于某些领域，如网络安全领域中恶意攻击的判断。