蒋 华，季 丰，王 鑫，王慧娇

(桂林电子科技大学 计算机与信息安全学院，广西 桂林 541000)

0 引 言

聚类分析作为数据挖掘中处理数据的重要环节之一，研究者们对聚类算法持续性、大批量的研究从未间断，取得了丰硕的研究成果。

Marek Gagolewski等提出了一种连接标准层次聚类算法Genie[1]。Xianchao Zhang等[2]的研究中先提出了一种基于密度的算法PDBSCAN，又提出了一种基于层次密度的算法POPTICS。Singh G等提出了一种结合K均值聚类算法和分层聚类算法BIRCH特征的算法[3]。Nazari Z等提出了一种使用欧氏距离的层次聚类方法[4]。Proietti A等提出2D层次模糊聚类方法[5]。以上所提3种算法均未能有效解决层次聚类对噪音敏感问题。Kumar D等提出了一种clusiVAT算法[6]。针对自动分簇这一想法Abe R等提出了一种方法来自动估计AHC中的簇数[7]。高长元等提出了一种基于CURE聚类算法[8,9]。针对Argo浮标观测数据数据量庞大的特点，蒋华等设计了基于MapReduce技术的Argo浮标剖面信息融合算法[10]，为利用大数据技术解决海洋数据监测问题提供了新思路。

基于上述分析，本文提出了DCNDA算法，即一种基于MeanShift核函数平移模型DBSCAN算法改进的CURE算法。MeanShift核函数平移模型自适应获取DBSCAN参数Eps、MinPts，提高初步聚类准确率。对所有正常值数据簇进行CURE层次聚类过程中不引入收缩因子，避免收缩因子选取不当造成聚类结果偏差。不必计算代表点，进一步降低了算法时间复杂度，在筛选出的正常值簇中层次聚类，解决了CURE对异常值敏感问题，提高聚类精确度。

1 相关理论

1.1 MeanShift

MeanShift(均值位移)这一概念最早由Fukunage在1975年提出，图1可见。MeanShift算法是一个迭代过程，首先计算出当前点的偏移均值，将该点移动到此偏移均值点处，其次以此为新的起始点，继续移动，直至满足最终条件。

图1 MeanShift

图2 MeanShift偏移过程

在给定的d维空间Rd中的n个样本点xi,i=1,…,n，则对于x点，其MeanShift向量基本形式为

(1)

其中，指半径为h的高维球形区域，其定义为

Sh(x)=(y|(y-x)(y-x)T≤h2)

(2)

但是，在Sh区域内，每个点对x的贡献是一样的。而实际上，这种贡献与x到每个点的距离相关。对于每个样本，其重要程度也不相同。基于这些考虑对基本MeanShift向量形式增加了核函数和样本权重，得到改进型MeanShift向量形式

(3)

其中，G(x)是一个单位的核函数。H是一个正定的对称矩阵，称为带宽矩阵。ω(xi)≥0是每个样本的权重。Meanshift向量Mh(x)是归一化的概率密度梯度。

1.2 核密度估计

核密度估计(kernel density estimation)是一种用于估计概率密度函数的非参数方法，在d维空间Rd中，有一组数据点x1,…,xn为独立同分布F的n个样本点，令其概率密度函数为f，核密度估计如下

(4)

其中，K(·)为核函数，h>0为一个平滑参数，称为带宽，也称之为窗口。

核密度估计中核函数分为多种，最常用的如高斯核函数

(5)

1.3 DBSCAN算法

DBSCAN算法是一种基于密度聚类的经典算法，核心思想是一个数据点x在邻域范围ε内的邻居点数量衡量该点所在空间的密度。该算法可以找出不规则形状的cluster，事先不需要知道簇的数量。

DBSCAN算法有两个关键参数Eps和MinPts，前者为定义密度时的邻域半径，定义核心点时的阀值，分别简称为ε和ϖ。

定义1 (ε邻域)设x∈X，X={x1,…,xn}，称Nε(x)={y∈X:d(y,x)≤ε}为x的ε邻域，显然x∈Nε(x)。

定义2 (密度)设x∈X，称ρ(x)=|Nε(x)|为x的密度。此处，密度为一个整数值，且依赖于ε邻域。

定义3 (核心点和边界点)设x∈X，若ρ(x)≥ϖ，则称x为X的核心点，由核心点构成的数据集称之为簇Xc。非核心点但属于核心点x在邻域范围内ε的对象，称之为边界点。

定义4 (噪音点)若x不属于任何Xc称之为噪音点。

DBSCAN算法适用于任何形状的聚类，且不需要事先知道类簇数量，可以自适应的聚类出相应的类簇数量。但是该算法的两个核心参数Eps和MinPts需要人为输入，这组参数的组合值稍有不同便会引起聚类效果的巨大偏差，参数值的筛选严重影响聚类准确率。

1.4 CURE算法

CURE(clustering using representatives)算法是一种自底向上的层次聚类算法，可以对任意形状的数据集聚类，采用计算代表点在收缩因子下的最短距离来合并簇，并重复这一过程直到聚类出最终数量的类簇。其特点是聚类步骤不可逆、分区处理和随机取样。

算法步骤如下：

(1)在原始数据集中随机抽取一部分作为样本集S；

(2)将样本集S分区处理；

(3)对分区样本集进行局部的聚类；

(4)随机选取孤立点，若簇增长太慢就去掉孤立点；

(5)对局部数据簇聚类，新形成的簇的代表点根据自定义的收缩因子向中心点移动；

(6)标记类簇。

CURE算法的提出者认为，收缩因子一般取值0.2～0.7之间可以取得较好的聚类效果。但是，收缩因子的选取不当会产生聚类准确率低的问题，并且孤立点的随机选取和根据簇增长速度来剔除孤立点，增加了人为主观判断，会对聚类效果造成负面影响。

2 DCNDA算法的提出

2.1 MeanShift核函数平移模型

DBSCAN聚类算法具有对异常值不敏感，事先不需要知道聚类数量，可以对不规则形状数据样本自适应聚类等优点，常常用于大数据库样本聚类。但是该算法严重依赖于两个参数Eps和MinPts，这对参数的组合值需要人工确定，稍有差别聚类结果会出现明显偏差。针对这一问题本文提出了密度函数平移模型来自适应确定Eps和MinPts的值。

MeanShift核函数平移模型原理：将样本数据集分区，在某一分区中，选取样本点x跟随MeanShift向量向着该分区中密度最大点处不断移动。MeanShift向量加入高斯核函数，在此过程中带宽的选取根据拇指法则来指定为h，对MeanShift高斯核函数向量式求导，计算每一次偏移的极大值点，重复偏移过程直至选中样本点移动至当前分区密度最大点处。计算所有分区MeanShift偏移结束后的带宽均值，这个带宽均值即为Eps；计算某分区密度最大点以带宽h为密度半径，当前区域内的数据点数量为s；计算出所有分区的s，其均值即为MinPts。完整步骤如下：

步骤2 在某一分区Si中的样本点xi,i=1,…,l对于样本点x的MeanShift向量形式如式(1)所示，加入核函数后的MeanShift向量形式如下

(6)

步骤3 对式(6)求导，令g(x)=-k`(x)得到如下结果

(7)

(8)

(9)

步骤8 若分区Si中MeanShift结束后带宽为hi，那么Eps为所有分区带宽的均值

(10)

计算当前分区中数据点与中心点之间的欧氏距离D(x,xi),0hi的数据点数量为ci，那么MinPts为所有分区满足条件数据点数量的均值

(11)

2.2 DCNDA算法

本文所提的DCNDA算法是一种基于MeanShift核函数平移模型优化的DBSCAN算法改进的CURE算法。DCNDA算法基本思想：首先，输入数据集D和聚类簇数K，通过自适应参数密度聚类算法获得正常点数据簇和异常点簇；其次，计算所有正常点簇的质心，将质心、簇以键值对的形式存放在HashMap中；再次，计算所有质心之间的欧氏距离，找出距离最小的两个质心，合并质心所在簇，生成一个新的簇，计算新生成簇的质心；最后，将新生成簇与质心的键值对存入HashMap，并删除生成新簇的两个键值对，重复前两步过程，直到HashMap中键值对数等于K为止，将HashMap中的数据簇按序号存放在文件中。DCNDA算法执行流程如图3所示。

图3 DCNDA算法执行流程

假设在d维数据空间Rd中，有样本数据集X={x1,…,xn},n为正整数，DCNDA算法完整步骤如下：

步骤1 输入数据集以及聚类数K，MeanShift核函数平移模型处理数据集，确定参数Eps和MinPts的值(确定这两个参数的详细步骤见2.1)；

步骤2 执行DBSCAN算法自适应聚类出正常点簇(cluster[1],…,cluster[m])和异常点簇cluster(outlier)；

步骤3 比较步骤2中正常点簇数与输入的K值，若正常点簇数小于或等于K，即m≤K，算法结束，输出正常点簇和异常点簇；若m>K，继续执行下列步骤；

步骤4 计算所有正常点数据簇(cluster[1],…,cluster[m])的质心点c

(12)

若c的取值范围为(c1,…,cm)，则将键值对cl,cluster[l](1≤l≤m)存入HashMap；

步骤5 计算m个质心间的欧氏距离D(cj,ck) 1≤j,k≤m，若有两质心点满足D(ca,cb)=minD(cj,ck)则将质心ca,cb所代表的簇cluster[a],cluster[b]合并为一个新簇cluster[new]；

步骤6 计算新簇cluster[new]的质心cnew，将键值对cnew,cluster[new]存入HashMap删除合并前的键值对ca,cluster[a],cb,cluster[b]；

步骤7 判断当前HashMap中的键值对数H，若H>K，重复步骤5和步骤6直到H=K，输出当前HashMap中的数据簇(cluster[1],…,cluster[K])和异常点簇cluster(outlier)，算法结束。

3 实验及结果比较

3.1 实验环境及数据集

实验环境：window7操作系统、Eclipse、gnuplot4.6等。为了充分验证本文所提算法的有效性、鲁棒性，实验数据集采用加入一定量人工数据集的二维和多维的Argo浮标数据集，实验数据集来源于中国Argo实时资料中心，实验数据规模见表1。

表1 实验数据集规模

本文选取PDBSCAN算法[2]和改进分区CURE算法[9]为对比算法，以聚类准确率、异常值检测率、算法执行时间、时间复杂度等关键因素做为算法评判标准，算法准确度的验证采用有监督的F值方法实现。

3.2 聚类结果分析

在同等数据集的对比实验中，DCNDA算法只需要输入聚类数K1，PDBSCAN算法需要人工确定参数Eps、MinPts等。改进分区CURE算法需要人工输入聚类数K2、分区、收缩因子等参数。如图4、图5、图6所示，分别为DCNDA算法、改进分区CURE算法、PDBSCAN算法采用S2数据集的聚类效果图。令K1=10，Eps=20，MinPts=100，K2=10，分区为100，收缩因子为0.6等。

图4 DCNDA算法聚类效果

图5 改进分区CURE算法聚类效果

图6 PDBSCAN算法聚类效果

图4～图6中，由实心圆点、上三角形、下三角形、叉号形、空心方形等不同形状间隔分布的数据簇代表聚类结果，聚类结果上方不同形状的数据点表示相应数据簇的异常值点。由图4～图6可看出，本文所提算法DCNDA算法对高密度数据集的聚类效果最佳，异常值点描述准确。

改进分区CURE算法对异常值敏感，在初始聚类过程中受异常值影响导致聚类出现偏差。在层次聚类增长过程中，该算法排除增长缓慢的数据点这一过程，评判标准的制定受研究者主观因素影响，难以适当的评判某一点增长速度的快慢，会造成聚类过程中异常点和正常点区分错误。收缩因子选取不当，也会对聚类效果造成影响。

PDBSCAN算法，Eps和MinPts这对参数需要人为设置，为了获得良好的聚类效果只能通过多次实验来确定参数，即便如此，仍然难以取得良好的聚类效果。PDBSCAN不需要事先知道聚类数量，依靠Eps和MinPts这对组合参数，自适应的聚类出若干数量的聚类结果。聚类数量太少或太多都是聚类精度低的表现，如图6所示，聚类数量过多，原本属于同一类簇的数据被分开为多个类簇，聚类效率较低。

从执行时间方面考虑，由表2可见，在二维数据集的聚类中DCNDA算法执行时间与其它两种算法相差不大。MeanShift核函数平移模型的时间复杂度为O(Tn2),T为迭代次数，由于算法使用HashMap和KDTree等数据结构优化存储，DCNDA算法的时间复杂度为O(mlogn)+O(Tn2),m为初始类簇数。随着数据集中数据量的增大，数据集维度的增高，DCNDA算法的执行时间比其它两种算法更长。在最坏情况下，改进分区CURE算法时间复杂度为O(n2logn)。PDBSCAN算法时间复杂度为O(n2)。当数据量大到一定程度后DCNDA的时间复杂度相仅当于O(n2)，与两种对比算法时间复杂度相当。

从聚类准确率方面分析，由图7可见DCNDA算法无论在二维数据集还是多维数据集方面的聚类准确率均高于同等数据集下的改进分区CURE算法和PDBSCAN算法。随着数据量和数据维度的增高，DCNDA算法的聚类准确率基本保持在93.50%左右，具有较高有效性和鲁棒性。改进分区CURE算法在对二维数据集聚类时，表现出了较好的稳定性和鲁棒性，随着数据集数量的进一步增大和数据维度的增长，改进分区CURE算法聚类效率有所降低，受随机取样和收缩因子影响，该算法对大量的高维的数据集聚类效果不稳定。PDBSCAN算法对数据量较少的二维数据集聚类效果良好，随着数据量增大维度增高数据集簇之间存在交叉包含关系时聚类精度下降。对高维数据集聚类效果DCNDA算法明显优于其它两种对比算法。

表2 DCNDA、改进分区CURE、PDBSCAN聚类效率分析

图7 聚类准确率分析

从异常值检测率方面分析，由图8可见，无论是二维数据集还是多维数据集，DCNDA算法的异常值检测率维持在91%～95%之间，改进分区CURE算法主要集中在80%～85%之间，PDBSCAN算法的异常值检测率在65%～78%范围内。相较于其它两种对比算法，DCNDA算法在聚类过程中对于异常值的处理更加合理，在高维数据集和数据量大的数据集聚类过程中，有明显的优越性。

图8 异常值检测率分析

综上分析，DCNDA算法对二维和多维数据集聚类具备有效性和鲁棒性，为了保证聚类精确度而引入了MeanShift核函数平移模型导致时间复杂度增加，但是随着数据量增大，时间复杂度对算法的影响程度趋于稳定。

4 结束语

本文提出了一种基于自适应参数DBSCAN算法改进的CURE算法。DCNDA算法，在初始聚类过程中，引入了MeanShift核函数平移模型来自适应确定了DBSCAN的参数，大大提高了初步密度聚类的精确度和鲁棒性。初步密度聚类将异常值簇和若干正常值簇分别输出，保证了后面层次聚类数据集的纯净性，对正常值簇的层次聚类进一步提高了聚类精确度。引用质心公式计算各簇质心，通过质心最短距离两两合并数据簇，避免了使用收缩因子而造成的聚类偏差，而且不需要重复计算代表点，减少了计算时间。MeanShift核函数平移模型的引入，尽管使算法聚类精度提高，但是牺牲了一定的时间复杂度，尤其是对大批量的高维数据集操作时，虽然使用了HashMap和KDTree优化算法结构，时间复杂度仍然较高。因此，如何在最大化的降低时间复杂度的前提下保证算法聚类精确度和鲁棒性，将是本文下一步研究的重点。