大规模数据集Spark并行优化谱聚类

doi:10.13474/j.cnki.11-2246.2019.0394

测绘通报 ›› 2019, Vol. 0 ›› Issue (12): 96-100.doi: 10.13474/j.cnki.11-2246.2019.0394

大规模数据集Spark并行优化谱聚类

吕洪林¹, 尹青山^1,2

1. 辽宁对外经贸学院, 辽宁大连 116052;
2. 吉林大学, 吉林长春 130000

收稿日期:2019-06-24 修回日期:2019-10-30 发布日期:2020-01-03
作者简介:吕洪林(1967-),男,硕士,教授,研究方向为计算机技术与应用。E-mail:lu_ljuan@163.com
基金资助:
辽宁对外经贸学院博士科研启动基金（2019XJLXBSJJ002）；辽宁省教育厅科学研究项目（ldxy2017008）

Spark parallel optimization large-scale spectral clustering

Lü Honglin¹, YIN Qingshan^1,2

1. Liaoning University of International Business and Economics, Dalian 116052, China;
2. College of Mining Engineering, Jilin University, Changchun 130000, China

Received:2019-06-24 Revised:2019-10-30 Published:2020-01-03

摘要/Abstract

摘要： 针对已有大规模数据集并行谱聚类算法的计算耗时和资源占用巨大等问题，基于当前批处理和图计算兼顾的Spark并行技术，提出了大规模数据集谱聚类的并行优化改进算法，算法通过并行单向迭代避免了相似矩阵计算时的数据重复计算，通过并行位置变换、标量乘法替换及距离缩放优化算法的资源占用，通过近似特征向量替代进一步优化算法的计算量。试验结果验证了算法近特征向量的有效性及在大规模数据集下良好聚类性能和扩展性。

关键词: 大规模集谱聚类, 近似特征向量, Spark并行框架, K-means距离计算, 优化

Abstract: To solve the problems of computational time-consuming and resource occupation, which is hard to be prevented in existing spectral clustering on large-scale datasets, based on the Spark technology, an improved parallel optimization algorithm for spectral clustering is proposed. In which, repetitive calculation of data in similar matrix calculations is avoided by parallel one-way iteration, the resource occupancy is optimized by the parallel position transformation, the scalar multiplication replacement and the distance scaling, and the calculation amount is further optimized by the use of the approximate eigenvectors. The experimental results verify the effectiveness of the approximate eigenvectors and the good clustering performance and scalability under large-scale data sets.

Key words: large-scale spectral clustering, approximate eigenvector, Spark parallel computing, K-means distance calculation, optimization

中图分类号:

P208

吕洪林, 尹青山. 大规模数据集Spark并行优化谱聚类[J]. 测绘通报, 2019, 0(12): 96-100.

Lü Honglin, YIN Qingshan. Spark parallel optimization large-scale spectral clustering[J]. Bulletin of Surveying and Mapping, 2019, 0(12): 96-100.

参考文献

[1] LIERDE H, CHEN G, CHOW T. Scalable spectral clustering for overlapping community detection in large-scale networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 52(8):1058-1071.
[2] 成宝芝, 赵春晖, 张丽丽, 等. 联合空间预处理与谱聚类的协同稀疏高光谱异常检测[J]. 光学学报, 2017, 37(4):296-306.
[3] CHONG L, XIONG T, PENG G, et al. Improving large-scale moso bamboo mapping based on dense Landsat time series and auxiliary data[J]. Remote Sensing Letters, 2018, 9(1):1-10.
[4] BIAN Z, ISHIBUCHI H, WANG S. Joint learning of spectral clustering structure and fuzzy similarity matrix of data[J]. IEEE Transactions on Fuzzy Systems, 2019, 27(1):31-44.
[5] 金海, 张劲松, 吴睿. 一种基于抽样改进加权核K-means的大数据谱聚类算法[J]. 测绘通报, 2018(11):78-82.
[6] MORIN J, DONATI J F, PETIT P, et al. Large-scale magnetic topologies of mid M dwarfs[J]. Monthly Notices of the Royal Astronomical Society, 2018, 407(4):2269-2286.
[7] 王建明, 史文中, 邵攀. 自适应距离和模糊拓扑优化的模糊聚类SAR影像变化检测[J]. 测绘学报, 2018, 47(5):611-619.
[8] 王小玉, 丁世飞. 基于共享近邻的成对约束谱聚类算法[J]. 计算机工程与应用, 2019, 55(2):142-147.
[9] 李滔, 王士同. 适合大规模数据集的增量式模糊聚类算法[J]. 智能系统学报, 2016, 11(2):188-199.
[10] CAI D, CHEN X. Large scale spectral clustering via landmark-based sparse representation[J]. IEEE Transactions on Cybernetics, 2015, 45(8):1669-1680.
[11] CHEN W, SONG Y, BAI H, et al. Parallel spectral clustering in distributed systems[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3):568-586.
[12] 李晓瑜, 俞丽颖, 雷航,等. 一种K-means改进算法的并行化实现与应用[J]. 电子科技大学学报, 2017, 46(1):61-68.
[13] HE Li,RAY Nilanjan,GUAN Yisheng, et al. Fast large-scale spectral clustering via explicit feature mapping[J]. IEEE Transactions on Cybernetics, 2019, 49(3):1058-1071
[14] 朱书伟, 周治平, 张道文. 融合并行混沌萤火虫算法的K-调和均值聚类[J]. 智能系统学报, 2015, 10(6):872-880.
[15] GHORBANI A, HONARMAND M, SHAHRIARI H, et al. Regional scale prospecting for non-sulphide zinc deposits using ASTER data and different spectral processing methods[J]. International Journal of Remote Sensing, 2019(1):1-21.
[16] 刘鹏, 滕家雨, 丁恩杰,等. 基于Spark的大规模文本k-means并行聚类算法[J]. 中文信息学报, 2017, 31(4):145-153.

大规模数据集Spark并行优化谱聚类

Spark parallel optimization large-scale spectral clustering

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王广帅. 无人机倾斜摄影铁路轨道线高精度自动重建[J]. 测绘通报, 2022, 0(5): 133-139,156.
[2]	范军林, 肖斌, 涂梨平, 胡全一, 师现杰, 危双丰. RGB-D SLAM在室内高精度三维测图中的应用[J]. 测绘通报, 2021, 0(8): 119-122.
[3]	陶莉, 胡召玲. 利用Sentinel-2A数据提取长江中下游丘陵地带农作物种植信息[J]. 测绘通报, 2021, 0(7): 39-43.
[4]	汪志刚, 郭杭, 敖龙辉. 利用Vicon系统进行IMU标定[J]. 测绘通报, 2021, 0(7): 121-125.
[5]	陈明辉, 黄燕, 李淦波. 城市“拓空间”拟收储土地资源的评价研究——以东莞市石马河流域为例[J]. 测绘通报, 2021, 0(11): 87-91.
[6]	王文凯, 黄昆学, 李梦, 王业明. 倾斜摄影测量数据轻量化处理技术研究[J]. 测绘通报, 2020, 0(9): 123-126.
[7]	常京新, 高贤君, 杨元维, 王双喜. 融合多时相高分影像的建筑物轮廓优化方法[J]. 测绘通报, 2020, 0(7): 112-115.
[8]	乔莲花, 刘民士. 融合城市行道树特征选取模型的自适应深度学习分类[J]. 测绘通报, 2020, 0(6): 77-80.
[9]	郭迎钢, 李宗春, 李广云, 刘忠贺. 粒子加速器工程控制网研究进展与展望[J]. 测绘通报, 2020, 0(1): 136-141.
[10]	苏琳, 巫兆聪, 闫钊, 王鹏. 基于投影变换的线阵旋转扫描相机标定方法[J]. 测绘通报, 2019, 0(4): 96-98,102.
[11]	敖龙辉, 郭杭. 室内环境下立体视觉惯导融合定位[J]. 测绘通报, 2019, 0(12): 12-17.
[12]	蔡林, 李英冰, 邹子昕. 路径优化算法在外卖配送中的应用[J]. 测绘通报, 2019, 0(11): 22-25.
[13]	唐俊. 顾及复杂环境约束的无人机三维航迹快速规划[J]. 测绘通报, 2019, 0(11): 26-30.
[14]	胡柳茹, 唐新明, 李国元, 付冬暇, 窦显辉, 赵世湖. 利用GLAS激光测高数据评估DSM产品质量及精度优化[J]. 测绘通报, 2019, 0(11): 39-43.
[15]	程效猛, 郑浩, 眭海刚, 冯文卿. 结合矢量引导的高分辨率遥感影像道路自动提取[J]. 测绘通报, 2018, 0(9): 19-23.