基于解耦概要图的大规模图数据高效分布式挖掘算法

频繁封闭子图挖掘被证明是NP-难问题.多年来,虽然已有许多算法被提出用于解决该问题,但在挖掘大规模图数据时,却面临着共同的计算效率问题.特别是,当图中节点的平均度数增加时,挖掘效率更是急剧下降.现在已有的面向图数据库的分布式频繁子图挖掘算法大多采用基于水平划分的分布式计算框架,且都聚焦在挖掘所有频繁子图的问题上.基于水平划分的分布式计算框架是对原始数据进行水平分片,完成分布式挖掘过程.在计算效率方面,该框架存在一些不足.同时,由于封闭子图模式需要对频繁子图进行封闭性检测,如果直接将现有的分布式频繁子图挖掘算法用于闭图模式挖掘可能导致各节点间频繁的通讯,或大量的子图同构检测.针对以上问题,本文提出一种面向大规模图数据的高效分布式挖掘算法Desu-FSM.与现有基于水平分解的分布式挖掘框架不同,该算法首次采用了基于垂直分解的分布式挖掘框架.其基本思想可概括为“快速抵近,双向搜索”.首先,通过τ-邻域核图合并,获得概要图集,跨越式地快速抵近较大尺寸子图的聚集区域.在此基础上,通过对概要图的缩减和扩展发现所有被概要图包含和包含概要图的闭图模式.相较于原始图数据,概要图的尺寸和平均节点度数更小.而且,基于概要图的双向搜索可在分布式环境下同时独立完成,不存在耦合.与基于水平划分的框架采用的“数据物理分治”方式不同,该框架采用“任务逻辑分治”.前者减少了各节点处理的图数据量,后者将原始图数据中的挖掘任务分解为一系列具有更小尺寸和平均节点度数的子图限定的子任务.因此,计算效率大幅提升.本文还提出一组高效的优化策略来减少概要图之间存在公共子图导致的大量重复计算.大量真实和人工数据集上的测试结果表明,在大规模图数据封闭子图挖掘中,基于垂直分解框架的挖掘效率相较于水平分解框架的效率可提升一个数量级.同时,具有更少的内存空间占用.

基于解耦概要图的图数据频繁模式挖掘算法

为了提高图数据频繁模式的分析效果,提出基于解耦概要图的图数据频繁模式挖掘算法.构建闭频繁项特征分析模型,采用解耦概要图模式分析方法进行图数据频繁模式特征检测,根据图数据频繁模式数据的混合分类属性进行相似度分析,提取图数据频繁模式数据的数值属性特征和分类特征,结合自相关特征检测方法进行图数据频繁模式挖掘的统计分析,建立图数据频繁模式挖掘的模糊相关性融合模型,采用解耦概要图检测方法进行图数据频繁模式挖掘过程中的特征提取,建立图数据频繁模式挖掘的特征提取和分类模型,采用大数据融合方法进行图数据频繁模式挖掘的模式匹配和信息融合聚类,根据信息融合结果实现对图数据频繁模式挖掘优化.仿真结果表明,采用该方法进行图数据频繁模式挖掘的自适应性较好,数据挖掘的精度较高,提高了图数据频繁模式检测和特征分析能力.