论文部分内容阅读
随着信息技术的发展,数据挖掘技术得到了广泛的关注。在数据挖掘技术中有很多研究领域,聚类分析就是其中一个重要的研究方向。与分类不同,聚类的目标是在没有任何先验知识的前提下,根据数据的相似性将数据聚合成不同的簇,使得相同簇中的元素尽可能相似,不同簇中的元素差别尽可能大,因此又被称为非监督分类。聚类分析作为数据挖掘系统中的一个模块,既可以作为一个单独的工具以发现数据库中数据分布的深层信息,也可以作为其他数据挖掘分析算法的一个预处理步骤,因此研究如何提高聚类算法的性能具有重要的意义。迄今为止研究者们提出了多种聚类算法,例如划分方法、层次方法、基于网格的方法、基于密度的方法、基于模型的方法等。基于密度的聚类算法由于能够发现任意形状的聚类,识别数据集中的噪声点,可伸缩性好等特点,在许多领域有着重要的应用。DBSCAN算法是典型的密度聚类算法,但由于该算法采用全局密度,部分密度小的聚类可能被作为噪声数据进行处理,而处于两聚类边缘的点,若存在该点的密度比较大的情况则容易造成单连通的情形,出现错误结果。同时算法需要判断数据库中每个点是否为核心点,为每个点建立查询区域,这样就需要频繁的I/O操作。FDBSCAN算法是对算法DBSCAN的一个改进算法。该算法通过选用核心点邻域中的部分点作为种子点来扩展簇,从而大大减少区域查询的次数,降低I/O开销,在一定程度上加快了聚类速度。但其在聚类过程中容易丢失一部分对象,成为噪声,影响了聚类结果。本文第三章在对FDBSCAN算法存在的问题进行深入研究的基础上,具体提出了一种选最远距离核心对象的方法,并且针对其核心对象是非核心点就不作查询,以至于丢失对象的情况作了详细讨论,最后提出从核心领域中的核心点中选择代表对象的方法,在一定程度上解决了丢失对象的问题。FDBSCAN算法是对DBSCAN算法在速度上的一个改进,基于相对密度的聚类算法RDBClustering (Relative Density Based Clustering)则是针对其算法采用全局密度这一缺点做的改进。虽然两种算法从不同角度对DBSCAN算法做了改进,但仍都存在不足。前者在一定程度上加快了聚类速度,但无法解决对象密度不均匀时聚类出现错误结果的问题;后者解决了全局密度的问题,但其运行速度很慢,需要的内存也比较大。因此,本文第四章在两者的基础上提出一种新的算法——基于相对密度的快速聚类算法FRDBClustering (Fast Relative Density-Based Clustering),新算法结合了FDBSCAN算法和RDBClustering两种算法的优点,不仅解决了DBSCAN算法全局参数的问题,在一定程度上也加快了聚类速度,实验证明了该方法的有效性。