不确定图数据挖掘

出版时间：2013-1  出版社：哈尔滨工业大学出版社  
Tag标签：无  

内容概要

《不确定图数据挖掘》的内容建立在图论、概率论、计算复杂性理论、数据挖掘和算法等理论和技术的基础上，因此需要读者具备上述理论和技术的基础知识。书中的论述基于严格的数学证明，除一些特殊情况外，所有定理给出了完整的数学证明。同时，为了读者更容易理解《不确定图数据挖掘》中的概念、定理和算法书。

书籍目录

第1章 不确定图数据挖掘概述 1.1 不确定图数据的产生 1.2 不确定图数据挖掘的概念 1.3 不确定图数据挖掘面临的挑战 1.4 不确定图数据挖掘的研究内容 1.4.1 不确定图数据模型 1.4.2 不确定图数据挖掘问题的语义 1.4.3 不确定图数据挖掘问题的计算复杂性 1.4.4 不确定图数据挖掘算法 1.4.5 不确定图数据挖掘的应用 第2章 不确定图数据模型 2.1 确定图 2.2 不确定图 2.2.1 不确定图的形式化表示 2.2.2 不确定图的语义 2.3 不确定图数据库 2.3.1 不确定图数据库的形式化表示 2.3.2 不确定图数据库的语义 2.4 不确定图数据模型的扩展 第3章 不确定图数据挖掘问题的语义 3.1 确定图数据挖掘问题的语义 3.2 不确定图数据挖掘问题的语义 第4章 期望频繁子图模式挖掘 4.1 确定图数据上的频繁子图模式挖掘 4.2 问题定义 4.3 计算复杂性 4.3.1 #P复杂性类 4.3.2 期望频繁子图模式挖掘问题的计算复杂性 4.3.3 期望支持度计算的复杂性 4.4 子图模式的表示方法 4.5 近似挖掘算法 4.5.1 问题松驰 4.5.2 算法概述 4.5.3 期望支持度的计算算法 4.5.4 DFS编码树的优化裁剪方法 4.5.5 完整算法 第5章 概率频繁子图模式挖掘 5.1 问题定义 5.2 计算复杂性 5.2.1 概率频繁子图模式挖掘问题的计算复杂性 5.2.2 φ－频繁概率计算的复杂性 5.3 近似挖掘算法 5.3.1 算法概述 5.3.2 计算φ－频繁概率近似区间的算法 5.3.3 完整算法 5.3.4 参数设置方法 5.3.5 算法优化 5.4 频繁子图模式挖掘语义的区别 5.4.1 数学分析 5.4.2 实验分析 第6章 TOP－K极大团挖掘 6.1问题定义 6.2 计算复杂性 6.3 计算极大团概率的算法 6.4 分支限界挖掘算法 6.4.1 基本分支限界算法 6.4.2 优化裁剪规则 6.4.3 两阶段分支限界搜索 6.5预处理方法 6.5.1 基于顶点度的过滤 6.5.2 初始化临时topk结果 6.6 极大团挖掘算法在蛋白质复合体预测中的应用 6.6.1 基于topk极大团挖掘的蛋白质复合体预测算法 6.6.2 实验对比 第7章 紧密顶点子集挖掘 7.1 问题定义 7.2 最紧密顶点子集挖掘算法 7.3 topk紧密顶点子集挖掘算法 7.3.1 Lawler方法 7.3.2 挖掘算法

章节摘录

版权页：   插图：   由于真实物理世界中的网络普遍具有不确定性，因此网络可以表示为不确定图。Jin等使用数据挖掘方法研究了如何从不确定图中挖掘连通可靠性高于某阈值的全部导出子图。该问题在蛋白质复合体发现、通信网络路由和社会网络分析中具有重要应用。由于该问题是对两节点间连通可靠性计算问题和全网连通可靠性计算问题的推广，因此其计算复杂性至少属于#P完全复杂性类。为解决该问题，文献中提出了一种新的采样方法，并将核心挖掘问题转化为确定图上的频繁可达顶点集（frequent cohesive sets）发现问题。作者将挖掘极大集合的切削（peeling）技术与导出子图枚举的深度优先搜索技术相结合，提出了一种高效的两阶段挖掘算法。 4.聚类算法 图聚类（graph clustering）问题在生物信息学、物理学和社会网络等领域中具有广泛应用，现已被广泛研究。图聚类问题与稠密子图挖掘问题不同：在稠密子图挖掘中，人们只关心顶点子集的导出子图是否稠密；而在图聚类问题中，人们关心的是如何将图的顶点集划分成若干子集，使得每个顶点子集内部的连接密度比这组顶点与其他顶点之间的连接密度要大。 针对大规模图数据中普遍存在的不确定性，Kollios等研究了不确定图聚类问题，即给定一个不确定图和一个确定图聚类目标函数，如何将不确定图的顶点集合快速划分成若干互不相交的子集（即聚类），使该聚类在不确定图的所有可能世界上的聚类目标函数的期望值最大。文献提出了基于编辑距离（edit distance）的图聚类函数，并将该聚类问题与相关聚类（correlation clustering）问题联系起来，并最终提出了具有性能保证的近似算法。

编辑推荐

《不确定图数据挖掘》对作者在不确定图数据挖掘领域取得的研究成果进行了全面的梳理和总结，从数据模型、问题语义、计算复杂性和算法几方面系统介绍了不确定图数据挖掘，力图为研究人员提供一个了解不确定图数据挖掘的严谨、易懂的学术读物。