改进的密度聚类算法研究

随着全球信息量的爆炸式的增长，数据挖掘技术已成为新世纪计算机科学技术的研究热点。聚类分析是数据挖掘的核心任务，而聚类算法的效率和求解质量在数据挖掘中起着至关重要的作用，也是计算机科学领域的难题之一。迄今为止研究者们提出了多种聚类算法，例如划分方法、层次方法、基于网格的方法、基于密度的方法等。 其中基于密度的聚类算法是聚类分析的重要分支，其主要优点是能够发现任意形状的聚类，且对噪声数据不敏感。代表性算法包括DBSCAN、OPTICS、DENCLUE、KNNCLUST等。现实世界中的事物大多都具有密度不均匀这一特征，而上述的密度聚类算法由于缺乏处理不同密度聚类的能力，在分析含有不同密度聚类的数据集时效果往往不能令人满意，难以解决实际问题。因此，密度不均匀数据集聚类方法的研究已成为基于密度聚类算法的焦点研究课题。 为解决上述难题，本文通过对几种基于密度的聚类算法和分类算法的分析研究，提出了一种结合了分类技术的基于弥散度的聚类算法CUDL(Clustering Using Dispersive degree and cLassification)。CUDL算法主要分为发现聚类核心点和依据聚类结果分类两个步骤。CUDL算法采用“弥散度”这一新的相对密度度量标准，并使用类似OPTICS算法的数据扫描方式，依据弥散度动态的产生弥散度分布图来直观的刻画数据分布，据此确定参数识别聚类的核心点和边缘点。在分类步骤，CUDL使用改进的KNN核密度估计方法将边缘点分类，最终形成完整的聚类。 该算法根据数据的实际分布确定参数，在保持了基于密度聚类算法优点的同时，避免了其他算法在不了解数据集结构的情况下主观的给定参数造成的缺陷。理论分析和实验证明，CUDL算法能够较好的解决密度不均匀数据集聚类的问题，并且其聚类效果优于DBSCAN、OPTICS和KNNCLUST算法。