地球信息科学学报 ›› 2018, Vol. 20 ›› Issue (7): 887-894.doi: 10.12082/dqxxkx.2018.180081
颜金彪1,2(), 郑文武1,2, 段晓旗1,2,*(
), 邓运员1,2, 郭元军1,2, 胡最1,2
收稿日期:
2018-01-30
修回日期:
2018-04-15
出版日期:
2018-07-20
发布日期:
2018-07-13
通讯作者:
段晓旗
E-mail:715829216@qq.com;201997125@qq.com
作者简介:
作者简介:颜金彪(1987-),男,湖南衡阳人,硕士生,主要从事时空数据挖掘研究。E-mail:
基金资助:
YAN Jinbiao1,2(), ZHENG Wenwu1,2, DUAN Xiaoqi1,2,*(
), DENG Yunyuan1,2, GUO Yuanjun1,2, HU Zui1,2
Received:
2018-01-30
Revised:
2018-04-15
Online:
2018-07-20
Published:
2018-07-13
Contact:
DUAN Xiaoqi
E-mail:715829216@qq.com;201997125@qq.com
Supported by:
摘要:
针对传统的最小生成树聚类算法存在使用全局不变阈值确定噪声边,聚类需要用户根据经验确定初始化聚类参数,如“边权值倍数容差”,“边长变化因子”等,聚类不能发现局部噪声的问题,本文提出了一种改进的最小生成树自适应空间点聚类算法。该算法在无需用户输入参数的前提下,克服主观因素的影响,根据最小生成树边长的数理统计特征定义裁剪因子。算法首先从宏观层面对最小生成树进行首轮删枝操作,消除全局环境下的噪声边,进而根据各子树的边长统计情况,自适应设定局部裁剪因子,进行第二轮删枝操作,消除局部环境下的噪声边。最后,采用1个模拟数据和1个实际应用验证算法的有效性,结果表明本文提出的改进算法在无需人为提供经验参数的环境下能够发现任意形状、不同密度的簇,能够准确的识别出空间点中的噪声数据,从而能够实现空间点数据背后隐藏信息的自动挖掘。
颜金彪, 郑文武, 段晓旗, 邓运员, 郭元军, 胡最. 改进的最小生成树自适应空间点聚类算法[J]. 地球信息科学学报, 2018, 20(7): 887-894.DOI:10.12082/dqxxkx.2018.180081
YAN Jinbiao,ZHENG Wenwu,DUAN Xiaoqi,DENG Yunyuan,GUO Yuanjun,HU Zui. Improved Adaptive Spatial Points Clustering Algorithm Based on Minimum Spanning Tree[J]. Journal of Geo-information Science, 2018, 20(7): 887-894.DOI:10.12082/dqxxkx.2018.180081
[1] |
Eckley D C, Curtin K M.Evaluating the spatiotemporal clustering of traffic incidents[J]. Computers, Environment and Urban Systems, 2013,37:70-81.
doi: 10.1016/j.compenvurbsys.2012.06.004 |
[2] | Dale M R T. Spatial pattern analysis in plant ecology[M]. Cambridge: Cambridge university press, 2000. |
[3] | Miller H J, Han J Geographic.Data mining and knowledge discovery, second edition[M]. New York: CRC Press, 2009. |
[4] |
Grubesic T H, Mack E A.Spatio-temporal interaction of urban crime[J]. Journal of Quantitative Criminology, 2008,24(3):285-306.
doi: 10.1007/s10940-008-9047-5 |
[5] |
Wang M, Wang A, Li A.Mining spatial-temporal clusters from geo-databases[J]. Advanced Data Mining and Applications, 2006:263-270.
doi: 10.1007/11811305_29 |
[6] | 邓敏,刘启亮,李光强,等.一种基于似最小生成树的空间聚类算法[J].武汉大学学报·信息科学版,2010,35(11):1360-1364. |
[ Dend M, Liu Q L, Li G Q.A spatial clustering algorithm based on minimum spanning tree-like[J]. Geomatics and Information Science of Wuhan University, 2010,35(11):1360-1364. ] | |
[7] | Macqueen J.Some methods for classification and analysis of multivariate observations[C]. Proceeding of Berkeley Symposium on Mathematical Statistics and Probability. 1967:281-297. |
[8] |
Frey B J, Dueck D.Clustering by passing messages between data points[J]. Science, 2007,315(5814):972-976.
doi: 10.1126/science.1136800 |
[9] | 孙磊磊. AP聚类算法研究及其在电子病历挖掘中的应用[D].大连:大连理工大学,2017. |
[ Sun L L.Study on affinity propagation clustering algorithm and its application in mining electronic medical records[D]. Dalian: Dalian University of Technology, 2017. ] | |
[10] |
Guha S, Rastogi R, Shim K. Cure: An efficient clustering algorithm for large databases[J]. International System,2001,26(1)35-38.
doi: 10.1016/S0306-4379(01)00008-4 |
[11] | Ester M.A density-based algorithm for discovering clusters in large spatial databases with noise[C]. Proceeding of International Conference on Knowledg Discovery and Data Mining, Portland, 1996:226-231. |
[12] | Wang W, Yang J, Muntz R R.STING: A statistical information grid approach to spatial data mining[C]. International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc. 1997:186-195. |
[13] |
汪闽,周成虎,裴韬,等.一种带控制节点的最小生成树聚类方法[J].中国图象图形学报,2002,7(8):765-770.
doi: 10.11834/jig.200208249 |
[ Wang Min, Zhou C H, Pei T, et al.A MST based clustering method with controlling vertexes[J]. Journal of Image and Graphics, 2002,7(8):765-770. ]
doi: 10.11834/jig.200208249 |
|
[14] | Grygorash O, Zhou Y, Jorgensen Z.Minimum Spanning Tree based clustering algorithms[C]. IEEE International Conference on TOOLS with Artificial Intelligence, IEEE, 2006:73-81. |
[15] | 王小乐,刘青宝,陆昌辉,等.一种最小生成树聚类算法[J].小型微型计算机系统,2009,30(5):877-882. |
[ Wang X L, Liu Q B, Lu C H.Minimum Spanning Tree clustering algorithm[J]. Journal of Chinese Computer Systems, 2009,30(5):877-882. ] | |
[16] | 徐晨凯,高茂庭.改进的最小生成树自适应分层聚类算法[J].计算机工程与应用,2014,50(22):149-153. |
[ Xu C K, Gao M T.Improved adaptive hierarchical clustering algorithm based on minimum spanning tree[J]. Computer Engineering and Applications, 2014,50(22):149-153. ] | |
[17] |
邱雪松,蔺艳斐,邵苏杰,等.一种面向智能电网数据采集的传感器聚合布局构造算法[J].电子与信息学报,2015,37(10):2411-2417.
doi: 10.11999/JEIT150231 |
[ Qiu X S, Lin Y F, Shao S J, et al. Sensor aggregation distribution construction algorithm for smart grid data collection system[J]. Journal of Electronics & Information Technology, 2015,37(10):2411:2417. ]
doi: 10.11999/JEIT150231 |
|
[18] | 贾瑞玉,李振.基于最小生成树的层次K-means聚类算法[J].微电子学与计算机, 2016,33(3):86-88. |
[ Jia R Y, Li Z.The level of K-means clustering algorithm based on the Minimum Spanning Tree[J]. Microelectronics and Computer, 2016,33(3):86-88. ] | |
[19] | 朱利,邱媛媛,于帅,等.一种基于快速k-近邻的最小生成树离群检测方法[J].计算机学报,2017,40(12):2856-2870. |
[ Zhu L, Qiu Y Y, Yu S, et al.A fast kNN-Based MST outlier detection method[J]. Chinese Journal of Computers, 2017,40(12):2856-2870. ] | |
[20] |
Humphrey G.The psychology of the gestalt[J]. Journal of Educational Psychology, 1924,15(7):401-412.
doi: 10.1037/h0070207 |
[21] |
Deng M, Liu Q, Cheng T, et al.An adaptive spatial clustering algorithm based on delaunay triangulation[J]. Computers Environment & Urban Systems, 2011,35(4):320-332.
doi: 10.1016/j.compenvurbsys.2011.02.003 |
[22] |
余杰,吕品,郑昌文. Delaunay三角网构建方法比较研究[J].中国图象图形学报,2010,15(8):1158-1167.
doi: 10.11834/jig.20100804 |
[ Yu J, Lu P, Zheng C W.A comparative research on methods of Delaunay triangulation[J]. Journal of Image and Graphics, 2010,15(8):1158-1167. ]
doi: 10.11834/jig.20100804 |
|
[23] |
Graham R L, Hell P.On the history of the minimum Sspanning tree problem[J]. Annals of the History of Computing, 1985,7(1):43-57.
doi: 10.1109/MAHC.1985.10011 |
[24] | Asano T, Bhattacharya B, Keil M, et al.Clustering algorithms based on minimum and maximum spanning trees[C]. Symposium on Computational Geometry, DataBase systems and Logic Programming, 1988:252-257. |
[25] | Xu X, Ester M, Kriegel H P, et al.A Distribution-Based clustering algorithm for mining in large spatial databases[C]. International Conference on Data Engineering, 1998. Proceedings, IEEE, 1998:324-331. |
[26] |
Zahn C T.Graph-theoretical methods for detecting and describing gestalt clusters[J]. IEEE Transactions on Computers, 1971,20(1):68-86.
doi: 10.1109/T-C.1971.223083 |
[1] | 谢聪慧, 吴世新, 张晨, 孙文涛, 何海芳, 裴韬, 罗格平. 基于谱系聚类的全球各国新冠疫情时间序列特征分析[J]. 地球信息科学学报, 2021, 23(2): 236-245. |
[2] | 韩珂珂, 邢子瑶, 刘哲, 刘峻明, 张晓东. 重大公共卫生事件中的舆情分析方法研究——以新冠肺炎疫情为例[J]. 地球信息科学学报, 2021, 23(2): 331-340. |
[3] | 张琛, 马祥元, 周扬, 郭仁忠. 基于用户情感变化的新冠疫情舆情演变分析[J]. 地球信息科学学报, 2021, 23(2): 341-350. |
[4] | 高楹, 宋辞, 郭思慧, 裴韬. 接驳地铁站的共享单车源汇时空特征及其影响因素[J]. 地球信息科学学报, 2021, 23(1): 155-170. |
[5] | 陈文静, 李锐, 董广胜, 李江. 网络地理信息服务中用户空间访问聚集行为研究[J]. 地球信息科学学报, 2021, 23(1): 93-103. |
[6] | 张政, 华一新, 张亚军, 曾梦熊, 杨振凯. 以节点为中心的关系边聚类与可视化算法[J]. 地球信息科学学报, 2020, 22(9): 1779-1788. |
[7] | 姚可桢, 岳书平. 网络大数据下的中国现代食甜习惯空间分布特征及其影响因素研究[J]. 地球信息科学学报, 2020, 22(6): 1202-1215. |
[8] | 项秋亮, 邬群勇, 张良盼. 一种逐级合并OD流向时空联合聚类算法[J]. 地球信息科学学报, 2020, 22(6): 1394-1405. |
[9] | 周琦, 高长春. 城市创意产业空间动态集聚演化的计算与可视优化方法[J]. 地球信息科学学报, 2020, 22(5): 1033-1048. |
[10] | 赵斌, 韩晶晶, 史覃覃, 吉根林, 刘信陶, 俞肇元. 语义轨迹建模与挖掘研究进展[J]. 地球信息科学学报, 2020, 22(4): 842-856. |
[11] | 高海峰, 葛莹, 张杰, 肖胜昌, 陈科. 面向复杂地形的坡位K-means聚类划分研究[J]. 地球信息科学学报, 2020, 22(3): 474-481. |
[12] | 李培林, 刘小平, 黄应淮, 张鸿辉. 基于GEE平台的广州市主城区不透水面时间序列提取[J]. 地球信息科学学报, 2020, 22(3): 638-648. |
[13] | 何惠馨, 范俊甫, 陈文贺, 周玉科, 张鹏, 俞宵. 基于亮度补偿的遥感影像阴影遮挡道路提取方法[J]. 地球信息科学学报, 2020, 22(2): 258-267. |
[14] | 孙小芳. 夜光遥感支持下的城市人口核密度空间化及自相关分析[J]. 地球信息科学学报, 2020, 22(11): 2256-2266. |
[15] | 裴韬, 舒华, 郭思慧, 宋辞, 陈洁, 刘亚溪, 王席. 地理流的空间模式:概念与分类[J]. 地球信息科学学报, 2020, 22(1): 30-40. |
|