层次化聚类在分布式计算环境中的剪枝策略

• 作者: 丁晓阳 王建新 罗阳
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 层次化聚类算法 分布式计算环境 剪枝操作
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 算法
• 页码范围: 261-267
• 页数: 7页
• 分类号: TP3
• 字数: 6150字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2017.05.045

摘要

基于树结构中结点覆盖关系的一类层次化聚类算法可以对海量数据生成有意义的摘要.然而,该算法已被证明是NP-完全问题,求解其精确解需要庞大的计算量.虽然它在单机计算环境中存在有效的剪枝方法,但在分布式计算环境中这种剪枝算法并不可行.相应地提出了该层次聚类算法在分布式环境中的剪枝新策略,通过绑定结点与其覆盖的基本事件构成的有序数组,使穷举查询转换为有序数组的求交集运算,并能够在合并过程中执行大量剪枝,从而在有限的额外空间消耗的基础上显著减少计算时间.在2组公开基准数据集上进行了测试,结果表明,相比朴素的分布式计算策略,新的层次化聚类算法在时间效率上平均有30 ～ 40倍左右的提升.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	北京林业大学信息学院	35	165	8.0	11.0
2	丁晓阳	北京林业大学信息学院	2	3	1.0	1.0
3	罗阳	北京林业大学信息学院	3	4	1.0	2.0