DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的空间聚类算法,由Martin Ester、Hans-Peter Kriegel、Jörg Sander和Xiaowei Xu提出。其核心思想是通过寻找被低密度区域分隔的高密度区域来定义簇,特别适合用于数据集中的噪声和发现任意形状的簇。DBSCAN算法对于具有噪声的空间数据库或者聚类个数未知的情况尤为适用。
DBSCAN算法的主要参数有两个:Eps(邻域半径)和MinPts(最小点数)。Eps定义了将邻域半径内的点视为邻近点的距离阈值,MinPts定义了形成一个密集区域所需的最小点数。在DBSCAN算法中,对于给定数据集中的一个点,如果其邻域内至少有MinPts-1个其他点,则该点为核心点,并且这些点会根据密度可达性原则被加入到同一个簇中。反之,如果一个点在任意核心点的邻域内,那么这个点被归入该核心点所在的簇。如果一个点既不是核心点也不是边界点,则被视为噪声点。
然而,DBSCAN算法的聚类效果在很大程度上依赖于参数Eps和MinPts的选择。在Eps选择过大时,算法会把原本不属于同一簇的点归并在一起,导致簇的边界模糊,甚至出现单一簇包含所有数据点的极端情况;相反,如果Eps选取过小,则算法可能会将本属于同一簇的点错误地划分为多个簇,甚至将大部分点划分为噪声。对于MinPts来说,设置得过高会导致无法找到簇,设置得过低则会降低算法对于噪声点的鲁棒性。
为了解决上述问题,杨静、高嘉伟提出了一种基于数据场的改进DBSCAN聚类算法。该算法利用数据场的概念描述数据点的分布情况和数据点之间的关系。数据场能够反映出数据点之间的相互作用,如吸引或排斥,而这对于聚类分析来说是十分重要的信息。在数据场模型中,每个数据点都会生成一个势场,而这个势场对周围的点产生吸引或排斥作用。基于数据场的改进DBSCAN算法引入了平均势差的概念,在聚类过程中动态地确定每个类的Eps和平均势差,这有助于算法更好地识别密度差异较大的数据集上的簇,从而在这些数据集上获得较好的聚类结果。
实验结果表明,该改进算法在一些性能指标上比如AC(轮廓系数)和RI(兰德指数)等都优于原始的DBSCAN算法。轮廓系数是一个衡量聚类效果好坏的内部指标,其值介于-1到1之间,接近1表示簇内相似度高且簇间差异大,兰德指数是另一种衡量聚类结果与真实分类之间相似程度的指标,其值越高表示聚类效果越接近真实情况。
整体而言,该改进算法的成功在于它能够更准确地识别密度差异较大的数据集上的簇结构,并且可以更灵活地调整参数以适应不同数据集的特性。这一改进提高了DBSCAN算法在面对复杂数据分布情况时的适用性和鲁棒性。对于未来的研究,可以继续探讨如何进一步提高聚类算法的效率,降低对参数选择的敏感性,以及如何将这一改进策略应用到其他基于密度的聚类算法中。