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

Improved Density-Based Algorithm for Robust Clustering

作　　者：侯越先[1] 石陆魁[1,2] 何丕廉[1] 张莹[3] 

机构地区：[1]天津大学电子信息工程学院 [2]河北工业大学计算机科学与软件学院,天津300130 [3]天津大学管理学院

出　　处：《天津大学学报》2005年第12期1091-1095,共5页Journal of Tianjin University(Science and Technology)

基　　金：天津市科技发展计划基金资助(04310941R)天津市应用基础研究计划基金资助(05YFJMJC11700)

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

关 键 词：聚类 顺序无关性 盒索引 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]