一种基于网格与加权信息熵的OPTICS改进算法

doi:10.3969/j.issn.1000-3428.2017.02.034

计算机工程

一种基于网格与加权信息熵的OPTICS改进算法

安建瑞,张龙波,王雷,金超,怀浩,王晓丹

(山东理工大学计算机科学与技术学院,山东淄博 255049)

收稿日期:2016-01-18 出版日期:2017-02-15 发布日期:2017-02-15
作者简介:安建瑞(1990—),男,硕士研究生,主研方向为数据挖掘;张龙波(通信作者),教授、博士;王雷,讲师、博士;金超、怀浩、王晓丹,硕士研究生。
基金资助:
国家自然科学基金青年科学基金项目(61502282);山东省自然科学基金青年科学基金项目(ZR2015FQ005);山东理工大学博士科研启动经费资助项目(414023)。

An Improved OPTICS Algorithm Based on Grid and Weighted Information Entropy

AN Jianrui,ZHANG Longbo,WANG Lei,JIN Chao,HUAI Hao,WANG Xiaodan

(College of Computer Science and Technology,Shandong University of Technology,Zibo,Shandong 255049,China)

Received:2016-01-18 Online:2017-02-15 Published:2017-02-15

摘要/Abstract

摘要： 针对现有OPTICS算法时间复杂度高且不适用于数据密集型环境的问题,提出一种基于网格与加权信息熵的改进算法。将数据集合划分为一定数量的网格单元,引入加权信息熵,自适应计算每个网格单元的最小密度阈值。对满足最小密度阈值的网格单元定义密集格的概念,利用质心点代替网格数据点集的方法对数据点进行压缩。采用Geolife Trajectories数据集对算法性能进行测试,从理论分析和实验结果两方面证明了改进算法的有效性。

关键词: 数据密集型环境, 加权信息熵, OPTICS算法, 密度阈值, 质心点

Abstract: Since the existing OPTICS algorithm is time-consuming,highly complex and unsuitable for data-intensive environments,this paper brings about an improved algorithm based on grid and weighted information entropy.It firstly divides the data set into a number of grid cells,and then introduces the weighted information entropy concept to the divided grid units.By calculating the weighted information entropy,it self-adaptively computes the minimum density threshold for each grid cell.For the grid cells that satisfy the minimum density threshold,a dense grid concept is proposed to compress data points by replacing gridded data sets with centroid points.Finally,the GeoLife Trajectories dataset is employed to test the algorithm performance,and the validity of the improved algorithm is proved by both theoretical analysis and experimental results.

Key words: data-intensive environment, weighted information entropy, OPTICS algorithm, density threshold, centroid point

中图分类号:

TP391

安建瑞,张龙波,王雷,金超,怀浩,王晓丹. 一种基于网格与加权信息熵的OPTICS改进算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.02.034.

AN Jianrui,ZHANG Longbo,WANG Lei,JIN Chao,HUAI Hao,WANG Xiaodan. An Improved OPTICS Algorithm Based on Grid and Weighted Information Entropy[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.02.034.

http://www.ecice06.com/CN/Y2017/V43/I2/206

参考文献

参考文献［1］Chen Dongming,Yan Yun,Wang Dongqi.Density Clustering Based on Border-expanding［C］//Proceed-ings of the 10th International Conference on Natural Computation.Washington D.C.,USA:IEEE Press,2014:670-674. ［2］Ye Zonglin,Cao Hui,Jia Lixin,et al.Multi-radius Density Clustering Algorithm Based on Outlier Factor［J］.Applied Mechanics & Materials,2014,472:427-431. ［3］Chen Qi,Lu Jianfeng,Zhang Hao.A Text Mining Model Based on Improved Density Clustering Algorithm［C］//Proceedings of the 4th International Conference on Electronics Information and Emergency Communication.Washington D.C.,USA:IEEE Press,2013:337-339. ［4］Ester M,Kriegel H P,Sander J,et al.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise［C］//Proceedings of 1996 Inter-national Conference on Knowledge Discovering and Data Mining.New York,USA:ACM Press,1996:226-231. ［5］Zhou Shuigeng,Zhou Aoying,Jin Wen,et al.FDBSCAN:A Fast DBSCAN Algorithm［J］.Journal of Software,2000,11(6):735-744. ［6］Ma Yu,Gao Yuling,Song Shaoyun.The Algorithm of DBSCAN Based on Probability Distribution［C］//Pro-ceedings of the 5th International Symposium on IT in Medicine and Education.Xining,China:［s.n.］,2014:2785-2792. ［7］Jahirabadkar S,Kulkarni P.Algorithm to Determine ε-distance Parameter in Density Based Clustering［J］.Expert Systems with Applications,2014,41(6):2939-2946. ［8］Xiong Zhongyang,Chen Ruotian,Zhang Yufang,et al.Multi-density DBSCAN Algorithm Based on Density Levels Partitioning［J］.Journal of Information and Computational Science,2012,9(10):2739-2749. ［9］Ankerst M,Breuning M,Kriegel H.OPTICS:Ordering Points to Identify the Clustering Structure［C］//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,1999:49-60. ［10］陈燕俐,洪龙,金达文,等.一种简单有效的基于密度的聚类分析算法［J］.南京邮电学院学报,2005,25(4):24-29. ［11］曾依灵,许洪波,白硕.改进的OPTICS算法及其在文本聚类中的应用［J］.中文信息学报,2008,22(1):51-55,60. ［12］Qiu Baozhi,Li Xiao.Grid-based Clustering Algorithm Based on Intersecting Partition and Density Estima-tion［C］//Proceedings of PAKDD’07.Berlin,Germany:Springer,2007,21(5):368-377. ［13］黄国顺,文翰.基于边界域的条件信息熵和属性约简［J］.计算机应用,2015,35(10):2771-2776. ［14］Kohansal A,Rezakhah S.Modified Entropy Estimators for Testing Normality［J］.Journal of Statistical Com-putation and Simulation,2016,86(3):1-16. ［15］戴阳阳,李朝锋,徐华.初始点优化与参数自适应的密度空间聚类算法［J］.计算机工程,2016,42(1):203-209. ［16］Ratul D,Chakraborty S.Convex-Hull & DBSCAN Cluster-ing to Predict Future Weather［C］//Proceedings of 2015 International Conference and Workshop on Computing and Communication.Washington D.C.,USA:IEEE Press,2015:1-8. 编辑金胡考

[1]	郭雨, 陈金勇, 张新宇, 李梁, 孙未未. OPTICS与离线批处理在轨迹聚类中的应用[J]. 计算机工程, 2020, 46(7): 72-77,83.
[2]	杨慧,李振,霍纬纲. 改进小波聚类算法在QAR数据中的应用[J]. 计算机工程, 2017, 43(9): 29-33,38.
[3]	刘斌,孙斌,余方超,唐虎潇. 基于不可分小波分解的图像配准方法[J]. 计算机工程, 2014, 40(10): 252-257.
[4]	陈曦, 马一峰. 空间数据聚类中的网格粒度求解方法[J]. 计算机工程, 2011, 37(19): 65-67.
[5]	周炎涛;易兴东;吴正国. 基于网格的带有参考参数的聚类算法[J]. 计算机工程, 2008, 34(9): 98-100.

选择文件类型/文献管理软件名称

选择包含的内容

一种基于网格与加权信息熵的OPTICS改进算法

An Improved OPTICS Algorithm Based on Grid and Weighted Information Entropy

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种基于网格与加权信息熵的OPTICS改进算法

An Improved OPTICS Algorithm Based on Grid and Weighted Information Entropy

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价