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

• • 上一篇    下一篇

的DBSCAN算法

刘淑芬, 孟冬雪, 王晓燕   

  1. 吉林大学 计算机科学与技术学院, 长春 130012
  • 收稿日期:2013-04-14 出版日期:2014-07-01 发布日期:2014-07-01
  • 通讯作者: 王晓燕(1977-), 女, 讲师, 博士.研究方向:软件建模技术, 软件编程新方法.E-mail:wangxy@jlu.edu.cn
  • 作者简介:刘淑芬(1950-), 女, 教授, 博士生导师.研究方向:计算机网络协同工作技术, 软件编程新方法. E-mail:liusf@mail.jlu.edu.cn
  • 基金资助:
    国家自然科学基金项目(60973041); “863”国家高技术研究发展计划项目(2009AA010314); 中央高校基本科研业务费专项资金资助; 吉林省科技发展计划项目(2011507)

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

摘要： 针对DBSCAN算法时间开销大的缺点, 提出了基于网格单元的DBSCAN算法, 通过对数据空间进行网格单元划分来优化DBSCAN算法中最耗时的区域查询过程, 省去了大量不必要的查询操作, 并分析了网格单元的划分方式对本文算法的影响, 通过选取最优划分方式, 提高整个算法的运行效率。通过仿真实验, 验证了基于网格单元的DBSCAN算法具有较高的准确率和较低的时间复杂度。

关键词: 计算机应用, 数据挖掘, 聚类分析, DBSCAN, 网格单元

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

中图分类号: 

  • 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] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发