聚类分析的目标是在没有先验知识的情况下把数据集分成若干个簇,使得簇内的数据之间的相似度较高而不同簇之间的数据相似度较低,比如用户可能并不知道数据集分类的数目或数据的分布情况。作为数据挖掘的一个重要研究分支,聚类分析被广泛应用于很多研究领域,如多媒体分类、图像分割、生物信息学等。按照不同的思想聚类算法可以大致分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法、基于图论的方法等。基于密度的方法因其较好的可解释性和具备发现任意形状簇的能力,一直是热门的研究方向。DBSCAN是一种经典的基于密度的聚类算法,受到了许多学者关注。但时间复杂度问题,特别是搜索近邻的时间花销较大导致在数据集规模较大或维度较高时算法效率低下一直是DBSCAN的主要问题之一。局部敏感哈希算法是解决近邻检索问题的一种有效手段,它能快速地从大量的高维数据集合中找到某个数据的近邻点。针对DBSCAN的算法效率问题,本文结合局部敏感哈希,提出了LSH-DBSCAN和LSHSNN-DBSCAN两个改进算法,分别从“数量”和“维度”两个方向去改进DBSCAN的算法效率问题。具体研究成果如下:1.本文详细阐述了局部敏感哈希(LSH)的思想,数学原理,局部敏感哈希构造索引的过程,并结合实验结果分析得到局部敏感哈希索引能够快速找出数据的近邻点候选集的结论。2.从数量约减的角度提出了基于局部敏感哈希的LSH-DBSCAN算法改善DBSCAN算法效率问题。针对传统DBSCAN算法在搜索epsilon邻域时因为要对所有数据都建立距离矩阵从而导致时间开销较大的问题,从LSH索引的结构中受到启发,LSH-DBSCAN将那些多次被映射到不同哈希表的同一下标下的数据对象划分为同一个子簇。然后在不同子簇中选出代表点,接着仅在代表点上运行传统的DBSCAN算法,最后将与代表点所在子簇的其余点标记为与代表点相同的簇。因此最后用于聚类的DBSCAN算法只需要在代表点集合上运行而不用整个数据集,避免了搜索epsilon邻域时花费大量时间在遍历整个数据集上,减少了不必要的比较从而提升了效率。从实验结果来分析,提出的LSH-DBSCAN算法能在保证聚类结果的正确率的同时在效率上取得一定的提升,与其它对比算法相比LSH-DBSCAN算法在数据量规模较大的时候具有较明显的优势。3.从维度的角度提出了LSHSNN-DBSCAN聚类算法改善DBSCAN算法效率问题。针对高维数据在计算数据对象相似度的时候时间花销较大,且传统的欧氏距离在高维空间中缺乏意义的问题,本文提出的LSHSNN-DBSCAN算法主要的改进有以下两点:第一,相关研究已经证明利用共享邻居能在高维数据中有效地减弱“维度灾难”的影响,本文用数据对象的近邻候选集的交集来表示它们之间的相似度,减弱了欧氏距离在高维空间下缺乏意义的影响,更好地反映出对象之间的相似度。第二,改进了搜索epsilon邻域时的算法,传统的DBSCAN算法在查找邻域的时候是把整个数据集都比较一遍,在本文的算法中查询某个数据点的epsilon邻域只需要在这个点的近邻候选集(即用LSH索引搜索出来的近邻集)中比较就行了,而不是对整个数据集,从而提升了epsilon邻域的搜索速度。实验结果表明LSHSNN-DBSCAN算法相比于其它对比算法在更多的数据集上都提升了聚类正确率和效率,具有一定的优越性。