DBSVEC:Density-Based Clustering Using Support Vector Expansion

来源：2019 IEEE 35th International Conference on Data Engineering (ICDE)  

作者：Zhen Wang，Rui Zhang，JianZhong Qi，Bo Yuan

简介

DBSCAN是著名的密度聚类算法之一，它将在ε-邻域内拥有至少MinPts个邻点的数据点定义为核心点（ε和MinPts为自定义参数），连接由低密度区域分隔的相邻核心点形成簇。在连接相邻核心点时，DBSCAN要求对每个数据点进行范围查询以测试其是否满足核心点标准，因此即便使用kd-tree、r-tree等加速索引技术，DBSCAN的时间复杂度在最坏情况下仍然是O(n²)，也即，DBSCAN在处理大规模数据集时仍然存在效率问题。

尽管有研究尝试使用近似范围查询来解决这一问题，如层次网格结构、局部敏感哈希等，来实现近似DBSCAN，然而时间复杂度的降低往往伴随着精度丢失等问题。论文提出一种基于支持向量扩张的密度聚类算法（Density-Based Clustering Using Support Vector Expansion，DBSVEC）及三种优化技术，利用支持向量域描述（Support Vector Domain Description，SVDD）来识别簇边界，只对当前簇边界上的点进行范围查询以避免不必要的范围查询，能够在生成与DBSCAN相同的划分结果的同时大大减少运行时间。

下文将用到的符号描述如下。

预备知识

1.DBSCAN

给定数据集X、半径ε和密度阈值MinPts。给出如下定义：

定义1（ε-邻域）：以某一样本为球心、半径为ε的d维超球体中的样本集合称为该样本ε-邻域。

定义2（核心点）：当某一样本的ε-邻域内包含至少MinPts个点，则该样本为核心点。

定义3（密度可达）：对于样本xi和xj，如果存在序列，其中，，并且为核心点，对于k∈[1,t-1]，时，则称可由密度可达。

定义4（聚类簇）：给定ε和MinPts，一个聚类簇是满足如下条件的非空集合：

•  （极大值）如果某个核心点属于簇Cl，则从该点密度可达的所有点都属于Cl

• （连接）如果，∈Cl，必有核心点∈Cl使得和都由密度可达

则DBSCAN的算法步骤大致描述如下：

1. 遍历所有样本，重复执行2-3步

2. 如果样本为核心点且未被访问过 ，找出其所有密度可达的样本并生成聚类簇

3. 重复访问簇中的样本并将其密度可达的邻居添加到簇中来扩展此聚类簇，直至没有新的样本可供扩展

4. 当所有的点都被访问过后，那些不在任何簇中的点都被视为噪声

图1 DBSCAN算法流程

2.SVDD

支持向量域描述（Support Vector Domain Description，SVDD）查找包含数据集中所有或大部分点的最小超球体，该超球体由半径R和球心a定义。SVDD计算如下优化问题：

其中C为惩罚因子，为松弛变量，用于表示当样本点落在超球体外时样本点与超球体表面的距离。

用拉格朗日乘子将式(1)中的约束合并到优化函数中，得式(2)：

式(2)分别对R、a、求偏导，得式(3)：

将式(3)代入式(1)，可得式(4)：

最大化式(4)以获得的值。

只有＞0对应的样本点为支持向量。

DBSVEC

论文提出了一种针对超大数据集的高效密度聚类算法DBSVEC。它显著提高了DBSCAN的效率，同时保持了较高的聚类精度。

为了识别必要的范围查询，给出子簇的定义如下，子簇是簇的子集，它满足连通性，但不满足集群的最大化要求。

定义5（子簇）：给定ε和MinPts，子簇是X的一个非空集合，该集合满足：，存在点使得和都由其密度可达。

DBSVEC有四个主要步骤：初始化（initialization）、支持向量扩展（support vector expansion）、子簇合并（sub-cluster merging）和噪声处理（noise processing）。

1.初始化

DBSVEC扫描数据集并找到未访问点以激活新的子集群。当一个点被访问时，如果它不是一个核心点，它作为潜在噪音被添加到一个名为NoiseList的列表中；反之，它将被用作一个新的子簇的种子，种子的ε-邻域内的所有点将构成初始化的子簇。

2.支持向量扩展

用SVDD计算初始化的子簇的支持向量，最后只保留核心支持向量。核心支持向量指既为核心点，也为核心向量的样本点。

在这一步骤中，反复计算核心支持向量，(持续)使用SVDD扩展子簇，将核心支持向量的ε-邻域点添加到子簇中，直到找不到新的核心支持向量为止。当所有的支持向量都是非核心点，或者子簇无法进一步扩展时，返回初始化步骤以寻找新的子簇。

3.子簇合并

在支持向量扩展过程中，要添加到子簇中的点可能已被分配给另一个现有的子簇，这样的点被称为重叠点。如果重叠点也是核心点，则现有的子簇与扩展的子簇合并。

4.噪音处理

当所有点都被访问过后，扫描NoiseList中每个点的ε-邻域中是否还有核心点。如果有，则该点被分配到最近的核心点所属聚类簇；否则确认为噪音点。

图2 DBSVEC算法流程

图3 DBSVEC扩展类簇步骤流程

以图4为例，(a)中对种子点进行ε-邻域扫描后，(b)通过SVDD获得支持向量sv1、sv2、sv3、sv4，并基于支持向量继续扩展聚类簇，(c)中星号点为重叠点的同时也为核心点，据此将蓝色簇与绿色簇合并，形成最终的聚类结果(d)，包括一个聚类簇和两个噪音点。

图4 DBSVEC实例图示

此外，论文还证明了只有在非常严格的条件下，DBSVEC的聚类结果才可能会和DBSCAN有偏差，因篇幅原因，在此不作叙述。

改进SVDD的DBSVEC

在DBSVEC中，支持向量扩展是一个重复且开销大的步骤，因此论文提出了三种技术来改进SVDD，进一步优化该过程，以实现有效和高效的聚类。

1.自适应SVDD模型

在原始的SVDD模型中，对每个数据点使用相同的惩罚因子C，然而，这并不适用于DBSVEC。在聚类过程中，新扩展的数据点和远离子簇中心的数据点更有可能位于子簇超球体边界或球体外，因此应该拥有更小的惩罚因子，以获得更高成为支持向量的概率。

基于上述观察，论文提出自适应SVDD模型，根据每个数据点的位置和参与支持向量计算的次数为每个数据点分配一个单独的惩罚因子，表明其成为支持向量的可能性，从而提高聚类精度。以下给出相关公式定义和改进后的优化函数公式。

核距离函数（其中是目标数据点的数量，K是核函数（高斯核），Φ是非线性映射）：

惩罚权重（其中记忆因子λ是大于1的系数，是数据点参与SVDD计算的次数）：

使用自适应惩罚权重改进后的优化函数：

对式（9）利用拉格朗日乘子进行约束合并和求偏导回代后的优化函数：

一个样本点是否在超球体内可以通过以下判别函数来确定，当点和球心a的距离小于半径时，样本点在超球体内：

2.增量学习

在支持向量扩展过程中，随着SVDD训练中涉及数据点越来越多，反复用于计算支持向量的数据点对SVDD模型的贡献很小，但却占了很大一部分计算。因此论文提出了一种增量学习方法，重点训练目标数据集中新增的数据点，以进一步提高算法的效率。

文中使用一个学习阈值T来控制一个点在目标数据集中用于SVDD计算的次数，参加SVDD计算次数大于阈值T的数据点将从训练数据集中移除。通过这种增量学习方法，该算法可以从新扩展的数据中学习支持向量，而不是重新发现以前使用的相同的支持向量。

3.核参数选择策略

为了寻找子簇的最优边界描述，SVDD使用高斯核通过非线性变换将数据投影到高维空间中，内核参数σ决定了非线性变换的程度。较小的σ利于获得更高程度的非线性变换，非线性程度越高，通过SVDD所形成的目标数据集的边界越窄，越能更好反映数据形状。

然而，在较高的非线性程度下，SVDD可能会产生不在目标数据集边界处的支持向量，这可能会降低DBSVEC的效率。因此,论文提出一种核参数值选择策略，旨在找到σ的一个下界，有助于形成子簇的最优边界描述的同时，避免因σ过高导致过拟合。

为便于计算，论文以二维数据空间为例，考虑数据分布的一个极端场景：数据的内部为空。此时由于内部没有数据点，SVDD倾向于将内部的稀疏空间视为核空间超球面的外层空间，从而导致过拟合。以下给出求解过程。

数据描述：

选择，用f(x)表示样本点和球心的核空间距离的倒数：

对偏导求极限：

最后获得σ的下界。

论文还分析了惩罚因子C的选择，此处略过。

实验分析

论文将DBSVEC与R-DBSVEC、kd-DBSVEC、DBSCAN-LSH、ρ-Approximate、NQ-DBSCAN和K-Means做了聚类准确率和计算效率的对比试验。

1.聚类准确率

数据集：Seeds、Dim32、Dim64、Map-Joensuu、Map-Finland、D31、Breast-Cancer、Miss-America、House、t4.8k、t7.10k

参数设置：ε=8.5，MinPts=20

使用R-DBSCAN的聚类结果作为聚类准确率的评判标准，如图5所示，DBSVEC和DBSCAN在t4.8k数据集上产生了同样好的聚类结果。

图5 DBSVEC和DBSCAN的聚类结果比较

对于其他数据集，聚类结果精度的比较结果如图6。DBSVEC在除t7.10k以外的数据集上的准确率均大于等于ρ-Approximate和DBSCAN-LSH。

图6 DBSVEC和其他算法的聚类结果比较

用类内紧密度和类间区分度作为指标，将DBSVEC和K-Means做对比试验，比较结果如图7。DBSVEC始终比k-MEANS产生更高质量的聚类结果。

图7 DBSVEC与K-Means聚类结果比较

4.2 计算效率

数据集：a.维度从2~24、规模从10万~1000万的仿真数据集；b.PAMAP2、Sensors、Corel-Image

参数设置：ε=5000，MinPts=100

论文分别就维度、数据量、邻域半径、惩罚因子以及改进SVDD对算法精度和计算效率的影响进行了比较实验。图8-图11展示了实验结果。

图8 (a)为数据量的对比实验结果，(b)为数据维度的对比实验结果

图9 关于邻域半径ε的对比实验结果

图10 惩罚因子对运算时间影响的实验结果

图11 改进SVDD技术对DBSVEC的提升

实验结果表明DBSVEC在各项性能上的表现均优于对比算法，且三种改进SVDD的技术有助于提高DBSVEC的精确度和效率。

总结

论文提出了一种基于密度的大规模高维聚类算法DBSVEC。DBSVEC使用支持向量来减少不必要的范围查询，它只在子簇的支持向量上执行范围查询，其效果几乎与在所有点上执行范围查询相同。此外，文章通过设置自适应惩罚权、增量学习和核参数值选择策略来改进SVDD，这些改进使得DBSVEC更加高效和准确。最后文章通过一系列的对比试验证明DBSVEC在效率和精确度上均优于目前最先进的近似密度聚类算法。

关于 天 方 夜 “谈”

天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。

方班人有自己的浪漫，

我们探讨知识，谈论理想，

采摘科研的繁星，

脚下是星辰大海。

天：代表我们的理想犹如天空般浩荡

方：代表方班

夜：代表代码人的冷静与静谧

谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”