RDD上扩展索引层优化的分布式K-means算法

• 作者: 李力 马菁
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: K-means算法 聚类算法 Spark系统 R树 四叉树 KD树 Ball树
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 161-167,270
• 页数: 8页
• 分类号: TP393
• 字数: 6866字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1709-0161

摘要

K-means是经典的聚类算法,为了适应大规模数据,很多研究利用分布式计算提高其扩展性.但传统基于磁盘的分布式系统仍然存在大量I/O消耗,在基于内存的Spark系统上实现,在继承Spark平台低读写消耗和良好容错性等优点的基础上,扩展了Spark的机器学习MLlib库,在此之上增加一个索引层,引入包含多种策略的基于RDD的双级索引机制,采用新的数据划分方式,对空间距离相近的点的信息进行预处理,利用索引存储其对应的点集的概括信息,以便在K-means算法中对搜索空间剪枝,从而达到对K-means算法的优化.实验结果表明,索引层能够剪枝搜索空间达40%以上,相对无优化的分布式K-means,提升效率达21%,具有较好的可扩展性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李力	上海交通大学软件学院	14	111	5.0	10.0
2	马菁	上海交通大学计算机科学与工程系	1	3	1.0	1.0