论文部分内容阅读
聚类分析作为一种无监督的学习方法在模式识别、机器学习等领域得到了广泛的研究,并已成功应用于实际。随着网络的发展和信息收集技术的进步,实际应用的数据正变得越来越庞大和复杂,因此对聚类算法产生了新的需求,如何在大规模和带有噪声的数据集中有效发现任意形状的簇就是其中之-。基于划分的聚类算法,如经典的K-MEANS,倾向于发现数据集中具有超球形状的簇且无法识别噪声;基于密度的聚类算法DBSCAN等可以有效地识别具有任意形状的簇和噪声,且在使用数据索引技术后可达到O(nlogn)的时间复杂度,但对于大规模数据集创建和维护索引需要较大的时间和空间开销。层次型聚类算法CURE采用收缩后的多代表点表示一个簇,可以识别具有任意形状和密度不均匀的簇,但其时间复杂度达到O(n2logn)。基于网格的聚类算法CLiQUE等可以识别任意形状的簇,并且其时间复杂度通常较低,但这些算法的聚类质量与网格划分的尺度密切相关,而确定划分尺度并非一项容易的操作。本文结合CURE算法和网格算法的优点提出一种新的聚类算法ShrinClus。该算法利用簇内与簇间数据点的密度差异,使数据点往簇内移动,让簇内变得更紧密而簇间变得更分离,从而查找准确的簇边缘来确定簇。ShrinClus能发现任意形状并具有密度差异的簇,具有接近线性的计算复杂度。