一种基于密度的高效聚类算法

在聚类算法DBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)的基础上,提出了一种基于密度的高效聚类算法。该算法首先对样本集按某一维排序,然后通过在核心点的邻域外按顺序选择一个未标记的样本点来扩展种子点,以便减少查询次数,降低聚类的时间花费。对样本进行非线性核变换后再进行聚类可以有效地改善聚类的质量。理论分析表明,该算法的时间复杂性接近于线性复杂度。同时测试结果也表明新算法的时间复杂度和聚类质量都显著优于DBSCAN算法。

Efficient density-based clustering algorithm

An efficient density-based clustering algorithm was presented based on DBSCAN(Density Based Spatial Clustering of Applications with Noise). In this method, objects were sorted by a certain dimensional coordinate at first. Then the new algorithm selected in order unlabelled points outside a core objects neighborhood as seeds to expand clusters so that the execution frequency of region queries could be decreased, and consequently the time cost was diminished. Transforming objects with a non-linear kernel function could effectively improve the clustering accuracy. The theoretic analysis demonstrates that the time complexity of this algorithm is approximately linear. Experimental results also show that the time efficiency and the clustering quality of the new algorithm are greatly superior to those of the original DBSCAN.