大数据时代产生的数据量呈指数型上升,这些数据中潜藏着巨大价值。从海量数据中找到感兴趣的信息,成为一个难题。但是数据挖掘却可以比较精确和高效地找到其中的信息。聚类分析作为数据挖掘中常用技术,能够在无先验知识的时候,发挥很好的信息发掘作用。基于密度的聚类分析方法是聚类分析中一类重要方法,它能够检测任意形状聚类、处理异常值,并且不需要预先确定聚类数目。常用的基于密度的聚类算法是DBSCAN算法,除了拥有聚类分析的特点以外,对有噪声的数据集也能产生很好的结果。虽然DBSCAN是解决许多问题时有吸引力的方案,但是,和其他一些聚类算法一样,由于其时间复杂度高,并不能很好地适应大型数据集和高维数据集。于是,本文从减少DBSCN抽样数据集的大小和降低其时间复杂度两个方向提出了改进。第一,本文从减少抽样数据集大小的角度,提出了两种生成抽样数据的方法以减少数据集大小,后续DBSCAN算法使用减小了的数据集,执行时间随之减少。第一种方法是对Rough-DBSCAN的中的Leader算法进行了改进,来简单估计每个Leader密度,得到了较好的结果,称为Leader*算法,进而称改进后的DBSCAN算法为Rough*-DBSCAN,与Rough-DBSCAN类似。第二种方法是一种称为I-DBSCAN,是新的启发式算法,它从Leader*算法发现的簇的交叉点中提取样本和元素,能够在不需要任何附加参数的情况下适应所有数据集并且在减少计算时间的方面获得了明显效果。第二,本文从降低其时间复杂度的角度,提出了一种基于邻域图搜索的组方法DBSCAN（Groups-DBSCAN）。Groups方法在数据上构建基于图的索引结构。与R-树等传统的层次索引结构不同,该方法适用于高维数据集。此外,Groups-DBSCAN在处理大量噪声时是有效的,而且不会降低DBSCAN的性能。并且Groups-DBSCAN产生的聚类结果与DBSCAN完全相同,但其运行时间缩短。