不确定图上的结构聚类算法研究与实现

发布时间：2020-11-13 02:08

　　 随着科学技术的迅猛发展,图结构越来越广泛地被应用于各行各业的数据挖掘和分析中。图结构抽象了事物之间的关系与联系,为人们的研究分析提供了便利。结构聚类作为一种重要的图结构数据的分析挖掘工具,不仅可以找出网络中稠密连接的簇,还可以识别其中的离群点与中介点,从而更好地理解图中各点的角色与它们之间的关系。现有的结构聚类研究主要是针对确定图的,即图上的点与边都确定存在。然而在科学研究与现实生活中,由于种种原因,许多的关系存在不确定性。例如社交网络中受个人隐私保护影响的不确定关系、生物网络中受实验因素影响的不确定关联、移动点对点网络中受环境影响的不确定连接等。这些不确定性通常需要使用不确定图(概率图)来表征。为此,需要考虑不确定图上的结构聚类问题。然而,现有的确定图上的结构聚类算法往往不能准确地表征不确定图上的连通关系。因此,在本文中,我们提出了一个不确定图上的结构聚类算法问题,目的是找出一个给定的概率图上的可靠结构聚类,并给出了它的形式化定义。在此基础上,设计并实现了一个不确定图上的结构聚类求解算法。具体地,本文首先对不确定图上的结构聚类算法问题的定义进行了研究。分析总结了现有的确定图上结构聚类问题模型,从而推广出不确定图上的结构聚类算法的问题定义。不同于确定图上的结构聚类,本文的结构聚类问题依赖于一种全新定义的概念——可靠结构相似度。可靠结构相似度度量了概率图上两个节点之间的结构相似的概率。从而可以用一个概率来衡量节点之间的相似性。随后,由于可靠结构相似度的求解是一个比较困难的问题,直接求解具有很高的时间复杂度,是不可取的。为此,本文详细分析了可靠结构相似度的求解过程,并在此基础上设计了一种基于动态规划思想的求解算法。该算法能够快速地求解可靠结构相似度问题,在该算法的基础上,本文根据目前最好的确定图上结构聚类算法,设计出不确定图上结构聚类算法框架。为了进一步加快我们算法的速度,我们设计了多种强有力的剪枝和优化措施。最后,我们使用了五个真实的数据集对我们所提出的算法进行了较为全面的研究与分析。通过与现有聚类算法的比较,我们的算法可以得到更好的不确定图上的聚类。同时,通过性能分析,我们验证了优化措施的有效性。综合实验的结果,得出我们的算法能够有效且高效地完成不确定图上的结构聚类问题。
【学位单位】：深圳大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP311.13;O157.5
【部分图文】：

于是节点9v 与节点6 7v ,v 和8v 就可能不再属于同一个聚类。从例子 1 中，我们可以看出来，简单地将不确定图转化为确定图，然后再求解确定图上的结构聚类的方法是有很大问题的，并不能用来很好地解决不确定图上的聚类问题。为此，我们必须针对不确定图的性质和特点，给出一个适用于不确定图条件下的结构聚类解决方案。在本文中，我们首先给出了不确定图上的结构聚类的形式化定义，这个定义基本沿袭了确定图上的结构聚类的思路，但是根据不确定图的性质，进行了调整和改进。随后，在不确定图上的结构聚类的形式化定义基础上，我们提出了一个高效的解决方案。本文主要的贡献包括以下三个方面：1.全新的概念和问题。为了度量不确定图上节点之间的相似程度，我们首先提出了“可靠结构相似度”的概念。值得注意的是，不确定图上两个节点之间的可靠结构相似度综合考虑了该图上所有可能世界的情况。基于可靠结构相似度，我们给出了不确定图上的结构聚类问题的定义。

我们可以很容易地得到(0.5,0.2 ) 41 2 3 4 5N [ v ] = {v , v , v , v , v}。( ,η)-可靠结构邻居也可以被叫做可靠相似邻居。显然，一个顶点拥有的相似邻居越多，则这个顶点在这个网络中重要性就越强，同样，在聚类的过就扮演越重要的作用。于是，当一个顶点拥有足够多的可靠相似邻居的时候们就称该顶点为一个可靠核心顶点（Reliable Core Vertex）。定义 7（( ,η ,μ)-可靠核心节点，( ,η ,μ)- Reliable Core Vertex）：对不图 上的一个顶点 u ，给定一个相似性阈值 0 < ≤1，一个可靠性阈 < η≤ 1，和一个整数 μ ≥ 2，当( ,)| N [u ]|η≥μ 时，该顶点u 为一个( ,η ,μ可靠核心节点。定义 7 给出了可靠核心节点，在可靠核心节点的基础上，我们可以进一步可靠结构可达的定义。定义 8（可靠结构可达，Reliable Structure-reachable）：给定参数0 < ≤1 < η≤ 1，和 μ ≥ 2，节点u 可靠结构可达节点 v ，当且仅当存在一个顶点

基于表达式(3.1)，我们可以给出动态规( , ) ( , ) ) ( , ) ( , ) ( , ) ) ( , )) ( 1, 1, 1)) (1 )) ( 1,)(1 )) ( 1, , )h hh h hhw u w vu w v w u w vu w vn p p X h m np p p X h p X h m n′ ′ ′ + ′ ′，对于每一条边，我们可以把 DP 算是因为在没有顶点被处理的情况下 m ' 了我们的 DP 算法的具体实现过程。Pr ( e, ) =0（见第 1~2 行）。随后，根2,2) = 1。这里我们假定只有边e存在的后结束的地方，（第 11 行）我们会把结我们将不断地处理每一个点，根据式子的每一种可能。在第 8-10 行，算法计算
【相似文献】

相关期刊论文 前10条

1 林佳楠;;一种基于结构相似度的部分参考型图像质量评价方法[J];长春大学学报;2016年10期

2 寻琛;杜向云;张锡宝;;中美贸易结构相似度研究的因素分析——从比较优势和要素禀赋角度[J];现代商业;2015年27期

3 王宇庆;刘维亚;王勇;;一种基于局部方差和结构相似度的图像质量评价方法[J];光电子.激光;2008年11期

4 朱震锋;曹玉昆;王非;陈丽荣;;黑龙江森工林区产业结构相似度测算及动态评价[J];林业经济问题;2016年03期

5 樊福卓;;一种改进的产业结构相似度测度方法[J];数量经济技术经济研究;2013年07期

6 李波;;基于协同视角的武陵山区产业结构相似度比较研究[J];中南民族大学学报(人文社会科学版);2012年06期

7 尹永超;徐敏;傅皇麟;孙胜男;;链路预测中的一种局部结构相似度算法[J];小型微型计算机系统;2018年01期

8 桑庆兵;梁狄林;吴小俊;李朝锋;;基于膨胀的梯度结构相似度图像质量评价方法[J];计算机科学;2014年06期

9 李京娜;王国宏;孙少燕;王刚;;基于改进后的结构相似度的三维图像配准[J];光电工程;2012年12期

10 楼斌;沈海斌;赵武锋;严晓浪;;基于失真模型的结构相似度图像质量评价[J];浙江大学学报(工学版);2009年05期

相关博士学位论文 前9条

1 俞唯仁;普适的结构相似度在大规模网络中的计算优化技术研究[D];东华大学;2012年

2 钱方;激光对光电系统图像干扰的效果评估[D];中国科学院研究生院(长春光学精密机械与物理研究所);2015年

3 杜小坤;数据库模式匹配算法研究[D];华中科技大学;2010年

4 张蕾;红外与可见光图像融合技术研究[D];中国科学院研究生院(长春光学精密机械与物理研究所);2015年

5 杨俊丰;基于感知的全参图像质量评价研究[D];湖南大学;2018年

6 陈晓琳;基于视觉特征的图像质量评价技术研究[D];上海交通大学;2012年

7 黎新;面向问答系统的段落检索技术研究[D];中国科学技术大学;2010年

8 张桦;基于视觉感知的图像质量评价方法研究[D];浙江大学;2009年

9 曹立民;喹诺酮药物族特异性识别材料及其检测性能的研究[D];中国海洋大学;2008年

相关硕士学位论文 前10条

1 邱宇轩;不确定图上的结构聚类算法研究与实现[D];深圳大学;2018年

2 朱毅;基于双边滤波的连续脑图像序列随机噪声去除方法研究[D];华中科技大学;2017年

3 郭旭超;基于结构相似度的社区发现方法研究[D];山东农业大学;2018年

4 孙芬芬;基于源码结构相似度检测系统的设计与实现[D];内蒙古大学;2017年

5 李红芳;基于梯度的结构相似度图像质量评价方法研究[D];西安科技大学;2012年

6 程梅娟;中国与东盟出口结构相似度与双边贸易研究[D];湖南大学;2011年

7 周进;基于结构相似度的动态复杂网络社团增量更新算法研究[D];辽宁大学;2016年

8 卢亚广;基于分组统计及梯度结构相似度的AVS2帧内预测高效算法[D];西南交通大学;2017年

9 刘婧;基于结构相似度的图像质量评价方法研究[D];长沙理工大学;2016年

10 江程;基于结构相似度的图像客观质量评价方法研究[D];湘潭大学;2012年

本文编号：2881571