浅析DBSCAN算法中参数设置问题的研究

侯雄文

摘 要 传统的DBSCAN密度聚类算法，需要人为设置邻域阈值（Eps）和点数阈值（minPts）2个参数来对数据集进行聚类，由于minPts和Eps具有全局性，使得DBSCAN算法对参数很敏感， 特别是分布不均匀的数据集。针对DBSCAN算法中这一问题，本文研究改进的算法通过对数据点的k最近点平均距离进行分析，根据其统计特性动态地确定minPts和多个Eps值，然后根据所求得的多组（minPts， Eps）值依次对数据集进行聚类，从而达到自适应设置参数的目的。

关键词 聚类算法 自适应 参数

中图分类号：TP31 文献标识码：A

聚类算法是数据挖掘、模式识别等研究中的一项重要技术。聚类的目的是把数据集分成若干类或簇，使得同一个类中的元素相似性较大，不同类中的元素相似性较小。其中，有多种方法来确定DBSCAN的两个阈值参数Eps和minPts。对于minPts的确定，在数据点不多的情况下，minPts在二维空间中的聚类中一般取4. 另外取数据集合的1/25作为minPts的值也是一种比较有效的方法。

本文针对密度分布不均匀的数据集的minPts和Eps的取值问题，提出了一种新的改进的基于k最近点平均距离的（DBSCAN based on K Nearest Average Distance， KNA-DBSCAN）聚类算法，该算法通过对数据点的k最近点平均距离的统计特性进行分析，自动的确定minPts和多个Eps参数，使其可以对密度分布不均匀的数据集进行聚类。

1 DBSCAN算法

DBSCAN算法是基于中心的密度聚类算法，相关概念如下：

定义1 数据点的Eps邻域：数据集D中任意数据点P，P的邻域Eps（P）定义为以P为中心，Eps半径的球形区域，公式表示为：

EPS（p）={q∈D|dist（p，q）≤Eps}

其中dist（p，q）表示数据点p和q之间的距离，这里采用欧式距离。

定义2 数据点的密度：数据集D中任意数据点P，所在的Eps邻域内，包含的数据点的数目，叫做数据点P的密度。

定义3 核心数据点：对于数据点P，p∈D ，如果以P为中心，以Eps为半径，在Eps（P）内的数据点的个数超过给定的minPts，则称P为核心数据点。

定义4 边界数据点：对于数据点P， p∈D，如果P不是核心数据点，但是P在某核心数据点q的邻域Eps（q）内，则称数据点p为边界数据点

定义5 噪音点：对于数据点p， p∈D，若p既不是核心数据点，也不是边界數据点，则p为噪音点或离群点。

定义6 直接密度可达：给定数据点集D，若数据点p在数据点q的邻域内，若q为核心数据点，则称从数据点p出发到数据点q是直接密度可达。

定义7 密度相连：若一个数据点o∈D，使得数据点p和数据点q都从点o在（minPts，Eps）条件下密度可达，则称数据点p和数据点q密度相连，密度相连是对称的。

2 KNA-DBSCAN算法

定义8：密度层次：按照数据集中数据点的密度不同，将数据点分为不同的密度层次，密度相近的点簇在同一个密度层次，数据点分布越稠密，密度越大，密度层次也就越大。

对于分布不均匀的数据集，各个数据点与周围数据的相似程度不同，本文采用数据点与周围的数据点的距离作为衡量该点稠密程度的判断标准。采用数据集D中数据点P的k平均最近距离作为该点稠密程度的评判标准，则p点的k最近点平均距离与k+1最近点平均距离之差则反映了p点密度的变化，变化越小，则p点当前的（k+1）最近点平均距离越能反映p点的密度层次。我们定义密度变化如下：

定义9：密度变化：数据点P的k最近点平均距离与k+1最近点平均距离之差 △distak：

对于数据集中所有点的密度变化之和则反映了所有数据点的密度变化，当密度变化之和最小时，则大部分点都达到了自己所在的密度层次。密度变化之和sum_incdistak的计算公式如下：

其中，pi表示第i个数据点，n表示数据集中数据点的个数。

2.1 KNA-DBSCAN算法的思想是

（1）确定k的取值：首先计算所有数据点的k最近点平均距离，然后计算所有数据点的（k+1） 最近点平均距离，求出所有数据点的（k+1） 最近点平均距离与k最近点平均距离的差值即，密度变化，再将这些差值求和，即计算所有点的密度变化之和，找出其中密度变化之和的最小值，此时，对应的（k+1） 最近点平均距离最能反映各点的密度层次，所以取此时的k+1的值作为k的值。

（2）确定minPts的值：k值确定后，取minPts=k。

（3）确定多个Eps的值：k值确定后，对所有点的k最近点平均距离求取对数，取对数之后不会改变数据的性质和相关关系，但压缩了变量的尺度，使数据变得更稳定。这里我们将其定义为数据点的对数距离，数据点p的对数距离计算公式如下：

定义10：密度转折点：若在某数据点Pm处，Pm+1的distak-log的值相对于Pm的distak-bg值突然增大，则称Pm为密度转折点。Pm对应的distak值即为对应的一个密度阈值Eps。

2.2 KNA-DBSCAN算法聚类步骤

步骤1：确定Mintps和Eps的值

根据KNA-DBSCAN算法思想对数据集进行计算，得到minPts和Eps的值，对于密度单一的数据集，得到的Eps只有一个，对于含有多个密度层次的数据集，得到多个Eps值。

步骤2：进行DBSCAN聚类

对数据集进行DBSCAN聚类，按照Eps从小到大依次进行聚类，先聚较高密度的簇，再聚较低密度的簇。将聚类成功的类标记为Ci（i≥1），表示数据集的第i个簇。对所有的（minPts，Eps）进行聚类后，没有被标记的点记为离群点或噪音点。

3结束语

本文在DBSCAN算法的基础上，提出了参数自适应的KNA-DBSCAN算法，该算法可以根据数据集的特点自动地确定minPts和多个Eps参数，有效地解决了DBSCAN算法对参数敏感的问题。

参考文献

[1] Chen，M.S.&J.Han.&P.S，Yu .Data mining：an overview from a database perspective [J]. Knowledge and data Engineering， IEEE Transactions on， 1996， 8（06）： 866-883.

[2] 孙凌燕.基于密度的聚类算法研究[D].太原：中北大学， 2009.

[3] Daszykowski，M.&B.Walczak&D.L.Massart.Looking for natural patterns in data： Part 1. Density-based approach[J]. Chemometrics and Intelligent Laboratory Systems，2001，56（02）： 83-92.

[4] ZHOU，H.& P.WANG.DBSCAN 算法中参数自适应确定方法的研究[J].西安理工大学学报，2012，28（03）.

[5] 夏鲁宁，荆继武. SA-DBSCAN：一种自适应基于密度聚类算法[J].中国科学院研究生院学报，2009， 26（04）：530-538.endprint