快速鲁棒的密度基聚类算法

为有效改善基于密度的聚类算法的聚类效果,提出了判定顺序聚类算法的聚类合理性的形式判据,简述了其神经生物学证据,并据此给出了可有效改善DBSCAN算法的聚类精度和时间效率的新算法DBSCANJZPoll．该算法首先以随机处理次序多次执行一个顺序依赖的子进程;再根据子进程的各次执行结果,由“合理聚类”的形式判据和简单的统计原则确定最终聚类结果．在聚类精度方面,仿真实验表明,DBSCANJZPoll可有效处理密度不均匀的样本集,聚类效果显著优于DBSCAN．在时间效率方面,理论分析表明,对于中高维样本集,DBSCANJZPoll的时间复杂性渐近于O(N),优于DBSCAN算法族中其他算法至少O(N log N)的复杂性;对于低维样本集的仿真也表明, DBSCANJZPoll具有相对优化的时间效率．

Improved Density-Based Algorithm for Robust Clustering

A formal criterion to verify the validity of sequential clustering algorithms is presented. Based on the criterion, DBSCANJZPoll, an algorithmic variation of DBSCAN clustering algorithm, is proposed. DBSCANJZ-Poll performs an order-dependent clustering sub-procedure a few times with random processing order, and determines the last clustering results by means of a simple statistical principle, which is derived from the above formal criterion. Simulation results show that in the case of noisy data, the clustering precision of DBSCANJZPoll is superior to DBSCAN algorithm. Moreover, theoretical analysis indicates that, for high dimensionality data, the time complexity of DBSCANJZPoll is asymptotical to O(N) , which is superior to other algorithms in DBSCAN family. The simulation of low dimensionality data shows superior time efficiency of DBSCANJZPoll.