一种改进的mpts-HDBSCAN算法

doi:10.12052/gdutxb.170011一种改进的mpts-HDBSCAN算法王荣荣，傅秀芬（广东工业大学计算机学院，广东广州510006）摘要:聚类分析是非监督模式分类的一个重要分支.DBSCAN算法是基于密度聚类的最常见算法,且具有可发现任意形状的簇并且对噪声点不敏感等优点而得到广泛研究与应用.本文首先研究了DBSCAN所存在的一些问题,以及当前基于DBSCAN算法改进算法所存在的不足.其次,对于mpts-HDBSCAN算法处理密度分布不均匀数据聚类效果不理想的情况,提出了一种新的分区算法.分区算法根据数据分布的直方图确定分组数据,根据分区阈值这个标准来确定是否对数据进行划分处理;然后运用mpts-HDBSCAN算法对划分后的子数据进行聚类,并对聚类的结果进行合并.实验结果表明,改进后的算法对于处理密度不均匀数据具有更好的效果.关键词:聚类；数据分区；mpts-HDBSCAN算法；合并子类中图分类号:TP391文献标志码:A文章编号:1007–7162(2017)03–0049–05AnImprovedmpts-HDBSCANAlgorithmWangRong-rong,FuXiu-fen(SchoolofComputers,GuangdongUniversityofTechnology,Guangzhou510006,China)Abstract:Clusteranalysisisanimportantbranchofnon-supervisedmodelclassification,DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)isoneofthemostcommonalgorithmsindensity-basedclusteringmethods.It'swidelyresearchedandappliedinmanyfieldsasitcanfindclustersofarbitraryshapeswithnoises.SomeshortcomingsofDBSCANandalsorecentlyimprovedalgorithmsbasedonDBSCANarefocusedon.Anewdatapartitioningmethodisproposedtosolvetheproblemthatmpts-HDBSCANclusteringqualitywilldegradewhenappliedinvarieddensitydataset.Firstlytheproposedpartitioningmethodcalculatesthenumbersofthegroupbasedonthehistogramofthedatadistribution.Secondlyitisdeterminedwhethertopartitionthedatasetbasedonthethresholdvalue.Sub-datasetsgeneratedbypartitioningmethodwillbindwithmpts-HDBSCANtofindclustersandfinallymergethesub-clusterstoone.Experimentshowstheproposedbindingalgorithmismoreeffectivethanmpts-HDBSCANinfindingclusterswhendatasetdensityisnoteven.Keywords:clustering;datapartitioning;mpts-HDBSCAN;mergingsubclusters随着计算机科学技术的发展，数据量呈现爆炸式增长，这些数据中隐藏着许多有用的信息.聚类分析作为数据挖掘中一种重要的手段，在机器学习、模式识别、电信、生物信息等等领域有着广泛的应用[1]，其原理在于通过计算数据之间的相似度，将数据划分成若干个簇.常见的聚类方法包括：划分法、层次法、基于密度的方法等等.DBSCAN算法[2]属于基于密度聚类的一种算法，其原理是：对于聚类中的每个对象，在给定的半径邻域内的数据对象必须超过某个阀值.算法简洁，对噪声点不敏感，而且可以发现任意形状的簇.DBSCAN算法在现实世界中有着许多应用，对此国内外学者有着许多研究，文献[3]通过卫星云图热点数据与DBSCAN算法相结合，来提前防止森林火灾.文献[4]提出一种核DBSCAN算法，实现了对民航客户行为的分析.文献[5]通过将DBSCAN算法与无线传感技术相结合，以去除噪声点来提高定位的准确性，等等.DBSCAN算法的不足之处在于以下两点：(1)由于需要在整个数据空间构建树，算法需要第34卷第3期广东工业大学学报Vol.34No.32017年5月JournalofGuangdongUniversityofTechnologyMay2017收稿日期：2017-01-15基金项目：广东省科技计划项目(2013B010401034)作者简介：王荣荣(1990–)，男，硕士研究生，主要研究方向为数据挖掘、云计算.很大的IO开销，这也是限制算法发展的重要瓶颈之一.(2)算法输入参数没有一个很完美的科学标准来作为参考，这就使得人为干扰的因素变得很大，参数选取略有偏差对于聚类的效果有时会呈现出完全不同的效果.针对DBSCAN算法以上的两个缺点，国内外有许多学者都做了很深入的研究.在IO开销方面VIJAYALAKSMIS和PUNITHAVALLIM[6]提出了一种以k-dimensional树来代替R树使得算法时间复杂度明显降低；李双庆和慕升弟[7]在基于隐马尔科夫模型的流量背景下，改进了DBSCAN算法，并应用在网络流量的大规模数据，改进后的算法聚类的时间相比传统DBSCAN有着明显的改善.随着大数据技术的发展，越来越多的学者将DBSCAN算法与云平台相结合，采用并行计算，来降低算法的时间效率；Woong-KeeLoh等[8]提出了一种利用GPU来划分数据，对每个子区域进行聚类.针对DBSCAN算法在密度不均匀的区域聚类效果不理想的缺点，WANGSM等[9]提出了一种MDBSCAN算法，该算法根据统计学方法来产生两个密度参数以解决DBSCAN算法在密度分布不均匀的数据集聚类效果差问题；文献[10]在OPTICS算法[11]的基础上提出了一种ICA算法对可达距离方面进行改进，改进后的算法可用于处理动态数据集；Campello[12]提出了一种HDBSCAN算法，该算法是DBSCAN算法与基于层次聚类算法相结合而来的，是对OPTICS算法的一种改进，但对于边界点的处理方面效果却不是很理想；Dockhorn[13]针对HDBSCAN算法的缺点提出了mpts-HDBSCAN算法，该算法克服了HDBSCAN算法边界点聚类效果差的问题，但是由于使用的是核心点数量mpts作为全局参数，当数据密度分布相差较大时，聚类的效果不理想.本文针对mpts-HDBSCAN算法在密度分布不均匀的数据集聚类效果不理想的情况，提出了一种数据分区算法，然后对分区后的子数据集采用mpts-HDBSCAN进行聚类，最后对每一个分区聚类结果进行合并.1mpts-HDBSCAN算法介绍mpts-HDBSCAN算法是由DBSCAN算法改进的，算法通过固定参数mpts，然后通过遍历所有可能的数值来自动选择一个合适的ε值.以下为DBSCAN算法单调性证明：定义1　dis(x,y)，表示两点之间的距离.jN(p)j定义2　：以半径为ε，核心点p的领域内数据点的个数.N(p)=fq2Djdist(p;q)⩽g:(1)定义3　以半径为ε，最小阈值点为mpts范围内，核心点的数目.cores;mpts=fp2Djmpts⩽jN(p)jg:(2)p;q;812证明：对于数据点，都有jN1(p)j⩾jN2(p)j(3)成立.由式(3)可知，通过增加ε可以影响核心点数目.令mpts为一固定值，可得出fp2Djmpts⩽jN1(p)jg⩾fp2Djmpts⩽jN2(p)jg;即core1;mpts⩾core2;mpts:(4)由以上的分析可得出，在参数mpts固定的情况下，核心的数量随着聚类半径ε的增大而增多，固定其中的参数mpts，遍历找到最佳匹配参数ε，从而降低多个参数带来的影响.文献[9]最后通过在多种数据集下进行聚类来证明算法的有效性，但算法只局限在数据密度分布相对均匀的情况下才能取得较好的效果.由于算法使用一个全局参数mpts进行聚类，当数据的密度分布差异较大时，算法的聚类效果就显得差强人意.2mpts-HDBSCAN改进针对mpts-HDBSCAN算法的缺点，本文提出了一种数据分区算法，根据分区阈值这个标准来判定是否将数据进行分区，然后再将划分后的每一个子数据集运用mpts-HDBSCAN算法进行聚类.对数据进行划分有以下两个好处.(1)mpts-HDBSCAN算法是以固定一个参数，通过算法的单调性来选取另一个参数，由于使用全局参数，在数据的密度差异性较大时，如果依据密度较大的区域来选取mpts，密度较小的区域会标记为噪声点，反之，密度较大的区域会划分成许多子类；采用数据分区，对密度差异较大的一些区域进行数据划分，对每个区域进行单独聚类就可以很好地解决全局参数带来的误差问题.(2)密度相差比较多的区域，数据之间没有多少相关性，对每一个区域的数据进行聚类也可以从侧50广东工业大学学报第34卷面解决mpts-HDBSCAN算法的IO开销问题.在只考虑二维数据的情况下，算法改进分为4大步：(1)利用关系型数据库系统中的聚集函数进行数据分布特性的统计.(2)根据数据密度差异不同划分成若干个子数据区.(3)对每一部分用mpts-HDBSCAN算法进行聚类.(4)将最终的数据合并输出.2.1数据分区首先将数据库中的数据映射到二维平面上，使用直方图来表示密度分布情况，在画直方图之前首先要确定分组的数目x，一般情形下：x1:87(n1)2=3，n为数据点数量[14].如图1所示，通过平滑曲线依次连直方图中心点，便可得知数据密度的大致情况.对于数据分区，国内外学者提出过一些算法，其中大多数与Hadoop等大数据平台有关[15-16]，文献[14]没有考虑波峰与波谷之间密度相差不大的情况，对数据进行划分时就会显得意义不大；文献[17]没有考虑在数据连续时要用怎样的标准对数据进行划分.如图2所示，组号为20、24分别处于波谷，如果按照文献[14]进行划分的话，数据将划分成3个子集.这样处理显然是不合理的.为此，本文提出了另一种分区算法，当相邻的波峰与波谷之间的密度差值超过某一阈值（本文称之为分区阈值）时，便在波谷处进行分区处理.假设第i处的数据密度值用ρi来表示.为了表示方便，本文给出几个定义.peaki⩾i1peaki⩾i+1定义1　波峰值peaki，表示数据密度为ρi处恰好处于波峰位置，峰值密度为peaki.即且⩽i1thoughj⩽i+1定义2　波谷值thoughj，表示数据密度为ρi处恰好处于波谷位置，波谷密度为thoughj.即thoughj且定义3　分区阈值∆ρ，若相邻波峰与波谷之间的密度差值大于∆ρ时，进行数据划分.∆⩽peakithoughj即.其中peaki，thoughj为相邻的波峰波谷.算法1：Partitioning2.2聚类与合并;


;通过数据分区后形成数据子集D1,D2,D3Dn，其中D=D1[D2[D3;


;Dn:(5)Di\Dj=ϕ;i,j;1⩽i⩽n;1⩽j⩽n且，对其中的每Input:asetofdataobjectsDataset,∆ρOutput:asetofsub-regions{Di}1.calculatenumberofgroups2.calculateunit_distanced3.reflectDatasetin2D