近年来,数据量日益增多,数据分布呈现多样化、复杂化。在众多应用领域中,包含任意形状、任意密度以及任意大小的簇的数据集广泛出现。传统的聚类算法无法有效地识别出分布复杂的数据点中的簇结构。同时,很多新的聚类算法在各种数据集中检测任意簇时,通常会遇到精确性不高或者执行效率较低等问题。因此,在分布复杂的数据集中,精确地检测出任意形状、任意密度以及任意大小的簇,是当前亟待解决的重点问题之一,也是聚类的研究热点。k近邻是一种分类算法,综合考虑了数据点所具有的特性和所处的空间位置。在基于密度的方法中,密度可以通过数据分布的紧密程度来决定,并且基于密度的聚类方法也适合检测数据集中任意形状的簇结构。本文在深入研究k近邻与基于密度的聚类算法的基础上,提出了两个有效检测任意簇的基于k近邻的密度聚类算法CUDG和CLDB。(1)CUDG算法通过把每个数据点看作为自然界中的质点,定义了数据点间密度引力的概念。首先根据每个数据点的周围邻居分布密集程度获得其局部密度,然后迭代地将每个数据点分配给密度比它大且距其最近的互近邻点形成初始簇,最后将具有共同数据点的初始簇进行合并得到最终簇。本文实验将CUDG分别与六个对比算法在十二个不同维度、不同类型的数据集上进行了测试,结果表明,该算法的聚类性能良好,且可以在不同类型的数据集中发现任意簇。(2)CLDB算法新定义了一个计算局部密度的函数,通过将密度比其所有互近邻都大的数据点与其互近邻合并形成簇的密度主干来有效保持簇的基本形状,然后将剩余未标记点分配给密度比它大的最近邻所在的簇主干,从而实现数据集的最终划分。为了验证算法的性能,本文选用了与CUDG相同的十二个带标签的数据集和两个无标签的数据集作为基准,同时使用了与CUDG相同的对比算法。结果显示,该算法相比其他几个对比算法在不同类型的数据集上均表现最优,能够有效检测出复杂数据中的任意簇及其异常点。两个算法均可在不同类型的数据集上较准确地识别出真实的簇结构,其中,CUDG是通过两点之间的作用力实现簇的划分,CLDB是通过高密度点吸引其互近邻形成簇密度主干的方式进行聚类。二者时间复杂度都接近于O(n?logn)。