吉林大学学报(工学版) ›› 2014, Vol. 44 ›› Issue (4): 1135-1139.doi: 10.13229/j.cnki.jdxbgxb201404035

Previous Articles     Next Articles

DBSCAN algorithm based on grid cell

LIU Shu-fen, MENG Dong-xue, WANG Xiao-yan   

  1. College of Computer Science and Technology, Jilin University, Changchun 130012, China
  • Received:2013-04-14 Online:2014-07-01 Published:2014-07-01

RICH HTML

0   

PDF (PC)

601

Abstract: To overcome the time overhead shortcoming of Density Based Spatial Clustering of Applications with Noise (DBSCAN) algorithm, a modified DBSCAN algorithm based on grid cell is proposed. Using this algorithm the data space is divided into grid cells and large number of unnecessary operations is eliminated, thus the region query process, which is the most time-consuming in DBSCAN algorithm, is optimized. The effects of different grid division methods are analyzed to select the optimal division method, thus improving the total operation efficiency of the algorithm. Simulation results verify that the modified DBSCAN algorithm based on grid cell has higher accuracy and lower time complexity.

Key words: computer application, data mining, cluster analysis, density-based spatial clustering of applications with noise(DBSCAN), grid cell

CLC Number: 

  • TP301.6
[1] 王光宏, 蒋平. 数据挖掘综述[J]. 同济大学学报:自然科学版, 2004, 32(2):246-252. Wang Guang-hong, Jiang Ping. Survey of data mining[J]. Journal of Tongji University(Natural Science), 2004, 32(2):246-252.
[2] 刘明亮, 李雄飞, 孙涛, 等. 数据挖掘技术标准综述[J]. 计算机科学, 2008, 35(6):5-10. Liu Ming-liang, Li Xiong-fei, Sun Tao, et al. Survey of data mining technology standards[J]. Computer Science, 2008, 35(6):5-10.
[3] Yu X, Jian Y. A new clustering algorithm based on KNN and DENClUE[C]∥Proceedings of International Conference on Machine Learning and Cybernetics, Guangzhou, China, 2005: 2033- 2038.
[4] 于智航. 改进的密度聚类算法研究[D].大连:大连理工大学, 2007. Yu Zhi-hang. Reaearch on improved clustering algorithm based on Density[D]. Dalian: Dalian University of Technology, 2007.
[5] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J]. 软件学报, 2008, 19(1):48-61. Sun Ji-gui, Liu Jie, Zhao Lian-yu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1):48-61.
[6] 张海龙, 王仁彪, 聂俊, 等. 海量数据的网格启发信息密度聚类算法[J]. 吉林大学学报:工学版, 2011, 41(Sup.2):254-258. Zhang Hai-long, Wang Ren-biao, Nie Jun, et al. Grid heuristic information density clustering algorithm based on mass data[J]. Journal of Jilin University(Engineering and Technology Edition), 2011, 41(Sup.2):254-258.
[7] 李海峰, 吴冀川, 刘建波, 等. 有限元网格剖分与网格质量判定指标[J]. 中国机械工程, 2012, 23(3): 368-377. Li Hai-feng, Wu Ji-chuan, Liu Jian-bo, et al. Finite element mesh generation and decision criteria of mesh quality[J]. China Mechanical Engineering, 2012, 23(3): 368-377.
[8] 冯少荣, 肖文俊. 一种提高DBSCAN聚类算法质量的新方法[J]. 西安电子科技大学学报, 2008, 35(3): 523-529. Feng Shao-rong, Xiao Wen-jun. New method to improve DBSCAN clustering algorithm quality[J]. Journal of Xidian University, 2008, 35(3): 523-529.
[9] 王桂芝, 王广亮. 改进的快速DBSCAN算法[J]. 计算机应用, 2009, 29(9):2505-2508. Wang Gui-zhi, Wang Guang-liang. Improved fast DBSCAN algorithm[J]. Journal of Computer Applications, 2009, 29(9):2505-2508.
[10] 孙玉芬. 基于网格方法的聚类算法研究[D]. 武汉:华中科技大学, 2006 Sun Yu-fen. Study on grid-based clustering algorithms[D].Wuhan: Huazhong University of Science and Technology, 2006.
[1] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd