论文部分内容阅读
随着计算机技术和网络通信技术的高速发展,各种信息化和数字化技术与社会生活的方方面面联系的越来越紧密,无论是对我们的生产、生活还是工作和思维等都引发了巨大的影响,我们已经进入了大数据时代。面对海量数据,当前一个十分重要的课题就是如何能够将这些海量数据转化为由价值的信息。机器学习、数据挖掘技术在解决这类问题中发挥了日益重要的作用。聚类分析是机器学习研究的一个重要内容,目前已经被广泛应用于图像处理、推荐系统、医疗诊断等多个领域。聚类是一个无监督的过程,聚类算法的目的是将输入的数据集基于某种相似性度量准则划分为若干个语义一致的簇。DBSCAN是最为重要的一种基于密度的聚类算法,它不需要预先指定聚类个数,可以在含有噪声的数据中识别出复杂分布的聚类。虽然DBSCAN算法有很多的优势,但是其时间复杂度为O(n~2),无法高效的处理大规模高维数据。其根本原因在于DBSCAN在判断每个点是否为核心点时,需要对每个数据点做近邻搜索,而其中存在大量冗余计算。本文对造成DBSCAN冗余计算的根源进行了深度分析,并在总结前人工作的基础上,提出了基于邻近搜索技术的快速密度聚类算法(NQ-DBSCAN),有效提高了DBSCAN算法处理大规模高维数据的性能。本文主要包括以下几个方面的内容:(1)首先,对DBSCAN的优缺点进行了深入探究,总结出DBSCAN在近邻搜索中存在大量的冗余计算,造成了该算法复杂度过高,无法处理大规模数据。(2)其次,对于DBSCAN相关改进算法的改进思路和效果也进行了深入分析,如IDBSCAN、FDBSCAN、LSH-DBSCAN、STDBSCAN、Fast-DBSCAN和ρ-Approximate DBSCAN等,发现这些算法处理相对高维的数据时性能不够理想。(3)最后,对于DBSCAN聚类速度较慢的问题,提出了改进算法NQ-DBSCAN。该算法使用邻近搜索的思想,通过将部分满足条件的数据点直接标记为离群点或者核心点,过滤了大量的冗余近邻计算,从而加快了聚类速度。从理论上确定了邻近搜索的上限和下限,确保NQ-DBSCAN和DBSCAN有一致的聚类结果。通过在人工合成数据集和真实数据集上的实验表明,NQ-DBSCAN的算法效率有很大的提升,尤其对于高维数据,随着维度增加算法性能退化缓慢,且对带噪声数据适应性更好。