结构图聚类算法的并行化研究

发布时间：2021-01-17 17:49

　　结构图聚类是针对无向图,根据顶点的相似度定义,将图顶点分类。结构图聚类算法作为数据挖掘和机器学习的基础算法之一,为海量数据的研究与分析提供一种基本方法,被广泛应用于现实生活的各个领域,如:生态环境、交通管理、模式识别、生物基因网络以及电子商务等,其运行效率决定了众多图分析算法的应用范围,是研究者最关心的热点话题之一。本文重点研究结构图的高效聚类问题,具体研究内容如下。首先,针对现有结构图聚类算法在处理大规模图数据时需大量计算边的相似度导致运行效率低的问题,提出了一种高效聚类算法CUWG。该算法通过状态转换图快速产生规模较小的聚类,合并这些小的聚类从而产生聚类结果,并且在计算边的相似度之前,先通过简单的相似边界判断,减少一些边相似度的计算,从而提高算法的运行效率。其次,针对CUWG算法处理极大规模图数据时大量计算边的相似度和频繁查询合并聚类导致运行效率较低的问题,结合并行处理的想法,提出优化方法CUWG+。相似度的计算和聚类的查询都是针对单个边或节点的操作,利用这种特性,提出将算法并行化处理,同时计算多条边的相似度,并行查询不同节点所属的聚类,从而提高算法的运行效率。最后,通过在多个真实... 

【文章来源】：燕山大学河北省

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景及意义
    1.2 研究现状
    1.3 研究内容
    1.4 本文结构
第2章 基础知识概述
    2.1 相关概念及定义
    2.2 相关算法介绍
        2.2.1 结构图聚类算法
        2.2.2 并行算法
    2.3 本章小结
第3章 结构图聚类算法CUWG
    3.1 问题分析
    3.2 CUWG算法基本思想
    3.3 算法描述
        3.3.1 CUWG算法
        3.3.2 分类查找算法
        3.3.3 基于结构相似可达的合并算法
        3.3.4 异常值点查找算法
    3.4 本章小结
第4章 CUWG算法的优化与实现
    4.1 问题分析
    4.2 算法的基本思想
    4.3 算法描述
        4.3.1 CUWG+算法
        4.3.2 基于内存管理的分类查询算法
        4.3.3 并行实现聚类扩展
        4.3.4 并行实现异常值点分类
    4.4 本章小结
第5章 实验结果与分析
    5.1 引言
    5.2 环境配置
    5.3 数据集
    5.4 性能比较与分析
        5.4.1 结构图聚类算法性能比较分析
        5.4.2 并行算法性能比较分析
    5.5 本章小结
结论
参考文献
攻读硕士学位期间承担的科研任务与主要成果
致谢


【参考文献】：
期刊论文
[1]基于微博社交平台的舆情分析[J]. 盛成成,朱勇,刘涛.  智能计算机与应用. 2019(01)
[2]基于文档对象模型结构聚类的钓鱼网页检测方法[J]. 冯健,张莹.  科学技术与工程. 2018(23)
[3]社交网络中基于成本的广告投放策略[J]. 曹玖新,崔桂旗,冯雪艳,闵绘宇.  东南大学学报(自然科学版). 2018(04)
[4]数据挖掘常用聚类算法分析与研究[J]. 陈向东.  数字技术与应用. 2017(04)
[5]改进灰色聚类法在粤港珠江三角洲区域大气环境质量评价中的应用研究[J]. 王国胜,冉治霖,黄奕崇,朱艳茹,涂桂娥.  深圳信息职业技术学院学报. 2015(01)
[6]图数据表示与压缩技术综述[J]. 张宇,刘燕兵,熊刚,贾焰,刘萍,郭莉.  软件学报. 2014(09)
[7]并行计算技术与并行算法综述[J]. 胡峰,胡保生.  电脑与信息技术. 1999(05)



本文编号：2983322