聚类(clustering)是数据挖掘中的重要手段, 其核心思想是“同类相近, 异类相远”, 将数据集划分为不同的簇, 同一簇中的数据对象之间有较高的相似度, 不同簇之间的数据对象差异较大. 通过聚类的方法可以分析数据之间的联系和价值, 目前已被广泛应用于诸如数据分析, 生物学, 模式识别^[1]等多领域的研究工作中.

目前聚类算法主要分为基于层次的方法如BIRCH算法, 基于网格的聚类方法如STING算法, 基于划分的方法如K-means算法, 基于密度的方法如DBSCAN算法以及基于模型的聚类方法等^[2-6]. 其中DBSCAN算法是密度聚类中最经典的一种聚类算法, DBSCAN算法不需要预先指定簇的个数, 且能在含有“噪声”的数据中找出任意形状的簇, 具有很好的抗干扰性, 但当数据量增大时, 由于算法自身的特性会导致时间的消耗急剧增加.

为了解决上述问题, 许多学者提出了不同的改进方案. 文献[7]提出的IF-DBSCAN通过选取核心点邻域中的代表对象来扩展类, 从而减少邻域中的查询次数, 但效率提升有限. 文献[8]通过按顺序选择邻域外未被标记的点作为种子点, 分不同情况进行聚类扩展, 有效地减少了核心点邻域重叠区域的查询次数, 同时也提升聚类的质量. 文献[9]提出选取距离最远且半径内样本个数大于MinPts的点为核心点, 以避免因核心点随机选取而导致计算量过大, 但优化效率还需提高. 文献[10]通过避免公共邻域内对象的重复查询来优化算法的执行速度, 但聚类质量还需提高. 文献[11]采用贪心策略进行聚类, 在寻找核心对象的过程中使用邻域查询的方法来提升算法的运行效率, 但需手动输入密度阈值. 文献[12]采用重心点转移的方法来改进St-DBSCAN算法, 以提升聚类的时间性能和质量, 但效率还有待提高. 本文提出的KD-DBSCAN算法能减少传统DBSCAN算法在聚类时需要计算数据样本中每个点Eps邻域所带来的开销, 从而极大的降低聚类时间, 且保证了聚类的效果与传统的DBSCAN算法基本一致.

1 DBSCAN算法分析

DBSCAN算法是一种基于密度的空间聚类算法, 该算法可以在具有“噪声”的数据中发现具有一定密度条件下的任意形状的簇. DBSCAN中的基本概念如下.

定义1. Eps邻域: 给定某对象点X, 其半径Eps范围称为该点的Eps邻域, 对于X的Eps邻域内的任意一点Y都有: dist(X, Y) ≤ Eps.

定义2. 核心点: 给定某对象点X, 其Eps邻域内数据点数量超过MinPts的点.

定义3. MinPts: 簇的最小点集, 即核心点邻域内的点数量必须不少于MinPts.

定义4. 噪声点: 既不是核心点也不是边界点的其它点.

定义5. 边界点: 不是核心点, 但在核心点的邻域内.

定义6. 直接密度可达: 对象点Y在X的Eps邻域内, 且对象点X是核心点, 则称X到Y是直接密度可达的.

定义7. 密度可达: 某一对象链 ${X_1},{X_2},\cdots,{X_n}$ , 若满足任意 $ {X_i} $ 到 $ {X_{i + 1}} $ 是直接密度可达的, 则称 $ {X_{\text{0}}} $ 到 $ {X_n} $ 密度可达.

定义8. 密度相连: 对某一对象Z,若Z到X和Y都是密度可达的, 则称X和Y是密度相连的.

DBSCAN算法聚类过程思想为: 从给定的数据集D中随机选取某个对象点X, 查询X的Eps邻域半径内的所有密度可达点是否大于MinPts, 如果大于则创建一个以X为核心点的聚类簇. 之后迭代聚集核心点密度可达的所有对象, 该过程可能会将核心点密度可达的簇进行合并, 在算法执行的过程中, 某些核心点的密度可达对象会被重复查询. 当一个簇聚类完成后会开始选取下一个点开始聚类, 直到没有任何新的点添加到任何一个簇中时, 聚类结束, 算法流程图(如图1所示)及部分伪代码如算法1.

算法1. DBSCAN算法

输入: D: 包含n个样本点的数据集; Eps: 半径大小; MinPts : 最少样本点个数;

输出: 簇的集合.

1) Initialize all points in D are unvisited

2) Select a pointp in unvisited

3) Mark pas visited

4) Set N as Eps-neighbor of p

5) if size of N ≥ MinPts

6) 　　Create a new cluster C, and put pin C

7) 　　for each point p∈N

8) 　　　If p in unvisited

9) 　　　　Mark p as visited

10)　　　　Set N as Eps-neighbor of p

11)　　　　if size of N ≥ MinPts

12) 　　　　　Put those points in N

13)　　　　endif

14) 　　　endif

15) 　　　if p is not yet a number of any cluster

16)　　　　　Put p to C

17) 　　endfor

18) else markp as noise

19) Until all points are marked as visited

2 KD-DBSCAN算法

传统的DBSCAN聚类算法在生成邻域集时会扫描整个数据样本, 导致大量且不必要的计算开销. 因此, 在聚类之前使用有效的数据结构对数据进行预处理, 可以快速地找出给定对象的邻域集, 减少近邻点的搜索时间. 文中将利用KD树这种数据结构对数据进行划分, 由于KD树是基于数据属性进行构建的, 因此相似度高的数据对象在KD树中联系更加紧密, 在查找的过程中也更加快速, 避免了在全局范围内查找邻域对象的时间开销.

2.1 相关概念

KD树是K-dimensional tree的缩写, 是一种在存储和查询方面非常高效的数据结构. 最早由Bentley^[13]提出, 用于将数据点在K维空间中进行构造, 是一种特殊的二叉搜索树结构, 树中的每一层对应一个维度. 传统二叉搜索树只对一维的数据进行构建, KD树通过数据点的属性个数循环的构造K维二叉搜索树. KD树中左子树在给定维度上的值小于父节点, 而右子树则大于父节点, 以二维数据为例, 假设有一数据集为{(2, 11), (9, 12), (2, 13), (12, 12), (11, 14), (10, 10), (15, 13)}对其进行KD树的构造, 在第一层中首先按第一个维度上的值进行排序, 将中间数据值的点作为根节点, 如(10, 10), 此时将数据集划分为两个区域, 左边的子数据集为{(2, 11), (2, 13), (9, 12)}在第一个维度上的数值均小于根节点, 右边为{(11, 14), (12, 12), (15, 13)}在第一个维度上的数值都大于根节点, 再分别在左右子树中选择第2个维度上的数据进行排序并选中间值, 左子树中以点(9, 12), 右子树为点(15, 13)分别构造左右子树, 到第3层又回到第一维进行比较构造, 图2为构造的效果图.

2.2 算法相关步骤

利用KD树对数据集进行构造, 在聚类之前生成每个数据点的邻域对象集, 遍历每个数据点, 并通过构造好的KD树进行近邻点搜索, 找出所有数据对象的邻域集, 包含核心点, 边界点以及噪声点, 将找出的核心点用于后续的聚类步骤. 虽然构造KD树需要花费一些时间且需要全局查询, 但是当数据量增大时, 可以明显减少近邻节点查找次数, 因此是非常值得的.

(1) KD树的构造

将数据点在K维空间中进行分割并构造KD树的节点, 先在一个维度上对数据点的某一属性值进行排序, 选取中间值点作为根节点, 再构造其左右子树, 其左子树节点在此维度上的数值均小于根节点在此维度上的值, 右子树则相反; 在子树的构造过程中, 在第2个维度上对数据点的第2个属性值进行排序, 选取中间值的数据点为子树的根节点, 反复执行, 直至构造完毕. 利用KD树对DBSCAN算法改进可将算法的时间复杂度由 ${\rm{O}}({n^2})$ 降至 ${\rm{O}}(n\log_2 n)$ .

(2)查找邻近节点集合

利用KD树进行近邻节点的查询, 此步骤将遍历数据集中的每一个节点, 让每一个节点根据输入的Eps参数计算出其正方形边界范围, 再从KD树的根节点开始查找其近邻点, 比较树中的每一层对应维度上的值是否在其边界范围内, 如果不满足条件则去子树中查找, 如果在其边界范围内还要继续计算其两点之间的距离是否满足dist(X, Y)≤Eps, 因为构造的正方形边界范围会略大于Eps为半径的圆形范围, 两者对应关系如图3所示. 将满足上述条件的数据对象添加到该点的neighbors邻域集合中, 每个数据点都有一个属性Key用于唯一标识该点, 构造后的 $ neighbors(Ke{y_n}) $ 集合形式如{ $ Ke{y_1},Ke{y_2},\cdots,Ke{y_n} $ }, 其含义是 $ Ke{y_1} $ 点在Eps邻域内包含的数据点有 $ Ke{y_2},\cdots,Ke{y_n} $ . 算法中采用的是haversine距离^[14], 具体公式如下:

$ d = {\sin ^2}\left( \theta \right) + \cos \left( {lat1} \right)\times \cos \left( {lat2} \right)\times{\sin ^2}\left( \omega \right) $

(1)

$ \theta = \frac{{lat2 - lat1}}{2} $

(2)

$ \omega = \frac{{lon2 - lon1}}{2} $

(3)

两点的距离为:

$ {\rm{dist}}\left( {{P_1},{P_2}} \right) = 2\times R\times \arcsin \left( {{\rm{sqrt}}\left( d \right)} \right) $

(4)

其中, R为地球半径, lat1, lon1和lat2,lon2分别对应P₁,P₂两点的经纬度, ${\rm{dist}}({P_1},{P_2})$ 为P₁, P₂两点之间的距离.

(3) KD-DBSCAN聚类

将上一步中查找到的邻近节点集合中长度大于等于MinPts的数据点用于聚类, 即len(neighbors( $ Ke{y_n} $ )) ≥ MinPts的数据点, 通过过滤噪声点来进一步减少聚类时间.

算法的部分伪代码如算法2和算法3.

算法2. 构建KD树

CreateKDTree(points, tree_depth):

1) //根据树的深度来选择维度

2) axis = tree_depth mod K

3) //选择第axis维度的中间值为根节点进行KD树的构造

4) select median by axis from points

5) //构造节点和子树

6) node = median

7) node.left = KDTree(points in subList(0,median),axis, tree_depth + 1)

8) node.right = KDTree(points in subList(median + 1, points.size()),axis, tree_depth + 1)

9) Return node

算法3. 找出邻近节点集合find_neighbors(kdtree,node,eps)

1) //遍历节点node, 根据Eps大小计算边界范围

2) bounding = getbounding(node, Eps)

3) Set bounding_max as the max value of bounding

4) Set bounding_min as the min value of bounding

5) q = deque(kdtree)

6) while size of q > 0

7) 　　current_node = q.popleft()

8) 　　if is_inbounding(current_node, bounding)

9) 　　　if haversine(node,current_node) <= eps and current_node.key!= node.key

10) 　　　　Put current_node into neighbors

11) 　　　endif

12) 　　endif

13) 　　Set axis as current_node’s axis

14) 　　if bounding_max[axis] > current_node[axis] and bounding_min[axis] > current_node[axis]

15) 　　and current_node has rightTree:

16) 　　　q.add(current_node.rightTree)

17) 　　elif bounding_max[axis] < current_node[axis] and bounding_min[axis]<current_node[axis]

18) 　　and current_node has leftTree:

19) 　　　q.add(current_node.leftTree)

20) 　　elif bounding_max[axis] >= current_node[axis] >= bounding_min[axis]:

21) 　　　　if current_node has rightTree

22) 　　　　　q.add(current_node.rightTree)

23) 　　　　endif

24) 　　　　if current_node has leftTree

25) 　　　　q.add(current_node.leftTree)

26) 　　　　endif

27) 　　endif

28) Return neighbors

3 实验结果与分析 3.1 实验环境和数据集

本实验以成都市网约车GPS数据为实验数据, 在Intel Core i7-9750H CPU 2.60 GHz, 16 GB内存的笔记本电脑上运行传统DBSCAN算法与改进的KD-DBSCAN算法, 统计两种算法的运行时间以及聚类的数目并用聚类评价指标对两种算法进行评估.

3.2 实验结果与分析

设置参数Eps = 100 m, MinPts = 60, 数据集从9 300行依次增加到58 000行, 运行结果如表1所示.

图4和图5分别为耗时以及聚类簇个数的对比情况.

为比较两种算法的聚类质量, 文中引入聚类效果评价指标Calinski-Harabasz (CH)^[15,16], 其定义为:

$ CH(k) = \frac{{BGSS}}{{k - 1}}\Bigg/\frac{{WGSS}}{{n - k}} $

(5)

其中, n为数据集样本数,k为类别数.

$ {\textit{WGSS}} = \frac{1}{2}\left[ {\left( {{n_1} - 1} \right){{\overline {{d_1}} }^2} + \cdots + \left( {{n_k} - 1} \right){{\overline {{d_k}} }^2}} \right] $

(6)

$ {\textit{BGSS}} = \frac{1}{2}\left[ {\left( {k - 1} \right){{\overline d }^2} + \cdots + \left( {n - k} \right){A_k}} \right] $

(7)

其中, $ {\overline {{d_i}} ^2} $ 表示第i类中样本间的平均距离, i=1, 2…, k; $ {\overline d ^2} $ 是所有样本间的平均距离, 其中 $ {A_k} $ 为:

$ {A_k} = \frac{1}{{n - k}}\sum\limits_{i = 1}^k {\left( {{n_i} - 1} \right)} \left( {{{\overline d }^2} - {{\overline {{d_i}} }^2}} \right) $

(8)

CH指标可以用于评估DBSCAN这类事先无法得知聚类个数的算法, 即在真实的分类标签label不知道的情况下用于评估聚类结果的性能, 其指标值越大说明簇内数据对象之间的间距越小而簇间距离越大, 聚类结果的CH指标如图6所示.

实验结果分析:

(1)聚类时间

从图4中可以看出, 随着数据量的增加, 传统DBSCAN算法耗时是急剧增加的, 而改进的KD-DBSCAN算法耗时依旧平稳, 且二者耗时的差距越来越大. KD-DBSCAN算法体现出了KD树对于减少邻近节点查询时间的优势.

(2)聚类数量

两种算法在相同数据量的情况下, 聚类产生的簇个数基本一致, 在数据量较少和较大时, KD-DBSCAN算法产生的簇个数略微少于传统DBSCAN算法, 这可能是由于KD-DBSCAN算法对于数据的划分更严格导致的.

(3)聚类质量

从图6中可以看出两种算法在相应的数据量下的聚类质量基本相同, 且随着数据量的增大, KD-DBSCAN算法的CH值总是略大于传统DBSCAN算法的.

综上所述, 改进后的KD-DBSCAN算法在保证了聚类的数量和质量与传统DBSCAN算法保持基本一致的前提下, 对聚类的效率有了大幅度的提升, 因此利用KD树改进的KD-DBSCAN算法是切实可行的.

4 结束语

本文通过KD树对传统DBSCAN算法进行改进, 在保证了两种算法的聚类个数以及质量基本一致的前提下, 极大地提高了算法的运行效率. 但是, 当数据量进一步增大时两种算法都会出现内存不足的情况, 因此下一步的研究工作会聚集于如何利用分布式计算框架来解决这类问题, 以提升算法的性能.