基于网格和密度比的DBSCAN算法研究

《基于网格和密度比的DBSCAN算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：单位代码：１０１４０密级：公开学号：４０３１５３１９０６？ＬＩＡＯＮＩＮＧＵＮＩＶＥＲＳＩＴＹ硕士学位论文ＴＨＥＳＩＳＦＯＲＭＡＳＴＥＲＤＥＧＲＥＥ中文题目：基于网格和密度比的ＤＢＳＣＡＮ算法研究ＲｅｓｅａｒｃｈｏｎＤＢＳＣＡＮＡｌｏｒｉｔｈｍＢａｓｅｄｏｎＧｒｉｄａｎｄｇ－英文题目：Ｄｅｎｓｉｔｙｒａｔｉｏ论文作者：普蓉指导教师：徐红艳副教授专业：计算机应用技术完成时间一：二○八年五月＊辽宁大学学位论文原创性声明本人郑重声明：所呈交的学位论文是本人在

2、导师的指导下独立完成的。论文中取得的研究成果除加以标注的内容外，不包含其他个人或集体已经发表或撰写过的研究成果，不包含本人为获得其他学位而使用过的成果。对本文的研究做出重要贡献的个人和集体均已在文中进行了标注，并表示谢意。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：年ｒ月知日学位论文版权使用授权书本学位论文作者完全了解学校有保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交学位论文的原件、复印件和电子版，允许学位论文被查阅和借阅。本人授权辽宁大学可以将本学位论文的全

3、部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编学位论文。同时授权中国学术期刊（光盘版）电子杂志社将本学位论文收录到《中国博士学位论文全文数据库》和《中国优秀硕士学位论文全文数据库》并通过网络向社会公众提供信息服务。学校须按照授权对学位论文进行管理，不得超越授权对学位论文进行任意处理。保密（），在年后解密适用本授权书。（保密：请在括号“”内戈ｉｖ）ｊ授权人签名１：％Ｉ指导教师签名：令《日期：良年［月如曰曰期：ｙ咜年ｒ月知日申请辽宁大学硕士学位论文基于网格

4、和密度比的DBSCAN算法研究ResearchonDBSCANAlgorithmBasedonGridandDensity-ratio作者：普蓉指导教师：徐红艳副教授专业：计算机应用技术答辩日期：2018年5月22日二○一八年五月·中国辽宁摘要摘要近年来，随着科学技术的飞速发展，数据量的不断膨胀，如何有效地分析这些海量数据已经成为了目前研究的热点和难点。聚类分析方法发展至今，已被广泛应用于生物信息学、计算机视觉、文本文档分类等领域。DBSCAN算法作为一种典型的基于密度的聚类算法，因其能够识别出任意形状的簇，以及能够有效识别出噪声点的特点，

5、该算法得到了广泛应用。但算法本身也存在一些问题，由于其使用单一密度阈值MinPts划分所有的簇，当给出的数据分布不均匀时，DBSCAN算法聚类效果不佳。另一方面，已有的增量聚类方式难以满足增量处理的需求。针对这些问题，本文开展了如下研究工作：（1）本文对基于密度的聚类条件进行了深刻剖析，提出一种基于网格和密度比的DBSCAN聚类算法，首先对数据空间进行多分辨率网格划分，把数据划分到多个网格空间中，并且利用所划分的网格加快查找到网格数据空间类簇的“峰值”和“低谷”，即网格空间的极大值和极小值的集合，再利用密度估计来计算密度比替换密度聚类算法中

6、的密度，从而达到快速自适应地确定聚类密度比阈值和可用该密度比阈值进行DBSCAN聚类的目的。最后针对本文所使用的数据集测试本文的时间复杂度及聚类效果，并将本文算法分别与DBSCAN算法和DPC算法进行比较。实验表明，对于分布不均匀的数据集，该算法在时间复杂度增加不大的前提下，较传统DBSCAN方法的聚类精确度有显著提高。（2）大数据时代下所研究的数据并不是永远不变的，更多的时候人们往往要面临不断新增的数据。针对当前聚类算法在增量聚类过程中的效率问题，提出了一种基于网格划分的增量聚类处理方法。每当有新增数据集加入到原有数据集中时，该方法只对增

7、量数据进行聚类，然后将聚类结果根据匹配到的网格信息纳入到初始聚类结果当中，得到最终聚类结果。最后本文所提方法与传统DBSCAN算法在时间复杂度和聚类效果方面进行比较，测试本文提出的处理方法的可行性和高效性。通过实验可知，在损失部分聚类精度的情况下，能够快速地对新增数据对象实现批量增量处理。关键词：网格，密度比，DBSCAN，增量聚类IAbstractABSTRACTInrecentyears,withtherapiddevelopmentofscienceandtechnology,thevolumeofdataisexpanding.Ho

8、wtoeffectivelyanalyzethesemassivedatahasbecomeahotanddifficultpointinthepresentresearch.C