一种针对单个不确定图的频繁子图挖掘与优化方法
一种针对单个不确定图的频繁子图挖掘与优化方法
【技术领域】
[0001] 本发明涉及图挖掘技术，特别地，涉及一种针对单个不确定图的频繁子图挖掘与 优化方法。
【背景技术】
[0002] 不确定性在现实应用中，无论是对内源还是外源，都是一种固有的属性。例如，在 一个合作社交网络中，利用目前掌握的信息，我们未必能明确断言比尔和马修两人具有很 好的合作关系，通常我们使用概率来衡量这种合作关系的可能性。假设这种关系存在的概 率为p，P的值由本领域专家通过可用信息人工确定，或者由信息抽取或生成规则自动产 生。在大数据时代的今天，对于管理不确定数据有更为强烈的需求，因此目前出现了各种质 量不一的数据。特别地，我们专注于不确定图，尤其是图的边上具有存在概率的不确定图。 不确定图模型具有广泛的应用领域，除了社会网络，不确定图模型还被应用于通信网络，无 线传感器网络，蛋白质交互网络以及生物学中的调控网络等。
[0003] 另一方面，频繁模式挖掘作为数据挖掘领域高度关注的主题，一直持续了近十年， 相关研宄也取得了长足的进展，其中频繁子图引起了特别的研宄兴趣。所谓频繁子图是指 从多个小确定图的集合或者单个大确定图中发现的支持度不小于用户给定阈值的子图。频 繁子图再刻画确定图的数据特征、分类、聚类以及建立索引方面具有重要作用。
[0004] 虽然目前对于频繁子图及其在确定图上挖掘的方法已经具有很好的理解，但在不 确定图上，这一问题变得更加有趣但也更少被研宄。一个不确定图时特殊的边加权图，其中 每条边（u，v)上的权重是其存在的概率。最近，研宄工作致力于在多个小的不确定图的图 集上挖掘频繁子图。但是，该问题在单个大型不确定图中虽然同等重要，因为现实生活中的 大型网络越来越多地出现了不确定性一一比如，在社会网络中一个人对另一个人的影响是 具有概率的；在生物网络中的蛋白质交互情况也有一定测量误差一一但现有技术在本方面 是一片空白。
[0005] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 目前尚缺乏有效的解决方案。
【发明内容】
[0006] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 本发明的目的在于提出一种针对单个不确定图的频繁子图挖掘与优化方法，能允许针对单 个不确定图进行频繁子图挖掘并优化挖掘算法，填补了本领域的技术空白。
[0007] 基于上述目的，本发明提供的技术方案如下：
[0008] 根据本发明的一个方面，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法，包括：
[0009] 获取单个不确定图；
[0010] 根据单个不确定图枚举出单个不确定图的所有子图；
[0011] 在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0012] 在样本图集合中设定多个检查点，多个检查点将样本图集合分割为多个部分样本 图集合，并依次指定每个检查点；
[0013] 使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本图集 合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖的部 分样本图集合中每个样本图上的期望支持度；
[0014] 根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期望支 持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子图、或 不确定是不是频繁子图，若判定该子图是频繁子图或不是频繁子图则停止该子图的相关运 算，若判定该子图不确定是不是频繁子图则继续指定下一个检查点并根据下一个被指定检 查点覆盖的部分样本图集合重新进行判定直到每个检查点都被指定过，其中，对最末被指 定的检查点覆盖的部分样本图集合进行判定时一定不会得出不确定的判定结果；
[0015] 输出所有频繁子图。
[0016] 其中，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖 的部分样本图集合中每个样本图上的期望支持度，为根据单个不确定图构造重用树，为单 个不确定图的被指定检查点覆盖的部分样本图集合中每个样本图中的每条嵌入边构建反 向索引，并根据重用树与反向索引分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率与每个子图在被指定检查点覆盖的部分样本图集合中每 个样本图上的期望支持度。
[0017] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0018] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0019] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0020] 分别计算每个蕴含图所包含的所有子图。
[0021] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0022] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0023] 并且，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法每个子图在被指定检查点覆盖的部 分样本图集合中每个样本图上的期望支持度包括：
[0024] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0025] 指定单个不确定图的所有子图中的一个；
[0026] 分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本图上 的支持度；
[0027] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在被指定检查点覆盖的部分样本图集合中每个样本图的支持度；
[0028] 继续从单个不确定图中指定下一个子图并计算其在被指定检查点覆盖的部分样 本图集合中每个样本图上的支持度，直到单个不确定图的所有子图都被指定；
[0029] 根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的支持度， 计算每个子图在单个不确定图上的期望支持度。
[0030] 并且，分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本 图上的支持度，为使用最大独立集法计算被指定的子图在被指定检查点覆盖的部分样本图 集合中每个样本图上的基于最小像的支持度。
[0031] 并且，根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期 望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子 图、或不确定是不是频繁子图包括：
[0032] 获取期望支持度阈值；
[0033] 根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0034] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0035] 根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0036] 根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图，将 所有结果区间上限大于期望支持度阈值、且结果区间下限小于期望支持度阈值与非误差系 数的乘积的子图判定为不确定是不是频繁子图。
[0037] 从上面所述可以看出，本发明提供的技术方案通过将单个不确定图划分为多个蕴 含的确定图并将蕴含图视作确定图使用计算重用方法与计算剪枝方法抽样计算子图的期 望支持度的手段，能在单个不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
【附图说明】
[0038] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所 需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施 例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获 得其他的附图。
[0039] 图1为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 的流程图；
[0040] 图2为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图、确定图与子图的一个实施例；
[0041]图3为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，根据布尔表达式获得的单个不确定图及其子图的一个实施例；
[0042]图4为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图的两个样本图及其重用树的一个实施例；
[0043]图5为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图及其两个子图在算法剪枝中一个反直觉的实施例；
[0044]图6为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，输出频繁子图正确率随置信度阈值与非误差系数在CIT上变化的柱状图；
[0045] 图7为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，三种不同算法在CIT与C0L上的运行时间折线图；
[0046]图8为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，两种不同算法在CIT与C0L上的运行样本量柱状图；
[0047] 图9为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，fanta与baseline算法耗时随非误差系数在CIT与C0L上变化的运行时间折线图； [0048]图10为根据本发明实施例的一种针对单个不确定图的频繁子图 挖掘与优化方法 中，fanta与baseline算法耗时随置信度阈值在CIT与C0L上变化的运行时间折线图； [0049]图11为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，fanta算法耗时随不确定因素在C0L上变化的运行时间折线图；
[0050] 图12为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，fanta算法耗时随数据集大小与数据集密度在C0L上变化的运行时间折线图。
【具体实施方式】
[0051] 为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明实施例中 的附图，对本发明实施例中的技术方案进一步进行清楚、完整、详细地描述，显然，所描述的 实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域 普通技术人员所获得的所有其他实施例，都属于本发明保护的范围。
[0052] -个确定图G是一个元组（VpEe,le，2e)，其中，是节点集合，
是 边的集合，e是为节点和边赋予标签的函数。|Ve|和|Ee|分别表示G中节 点和边的数量。为了描述简便，我们假设图是无向的，且没有自循环和多重边。但是，本方 法可以很容易的被拓展到具有多重边的有向图。
[0053] 如果存在单射f:Vg- 时满足以下两个条件：
[0056] 我们就用gGG:表不一个子图g同构于确定图G。我们称g是G的子图，G是g 的超图，f(g)是g在G中的一个嵌入。如果g是g'的直接超图，那么gGg',且|Eg| = |Eg, |+1。直接超图是指仅比子图多一条边的超图。
[0057]对于gGG，以及支持度阈值t，假设存在一个函数来衡量g在G中的支持度，那 么最直接的想法是计算g在G中的同构次数。然而，该支持度计算方法不具有反单调性。反 单调性对于开发能够有效剪枝搜索空间的算法是十分关键的，如果没有此性质，则不得在 整个空间进行穷举搜索。因此，目前的研宄提出了很多具有反单调性的支持度计算法方法， 包括最小映射法（MI)，有害重叠法（H0)，以及最大独立集法（MIS)。这些计算方法都是基于 子图同构，但对延生的重叠兼容性有所不同，而导致计算复杂度不同。特别的，MI是唯一一 个可以高效计算的方法，而H0和MIS都涉及解决NP完全的问题；MI得到的结果是HO/MIS 得到结果的超集，因此，其结果可以从MI的结果通过进一步计算得到。因此，接下来我们使 用MI作为支持度计算的标准，然而算法只需要简单改变即可拓展到另外两种计算方法。
[0058] 考虑从g到G的一个子图同构集合F= {f}。F(v)表示|v' }，其中对于每个 ，，存在映射f?将vGVg映射到，。基于最小像的支持度表示为SUp(g,G) =
下文中"支持度"是"基于最小像的支持度"的缩写。
[0059] 图2示出了确定图G和子图g，该图建模了合作社交网络，其中节点表示人，边表示 合作关系。每个人的研宄领域作为标签，即Bio表示生物学家；为了图示的清晰，边的标签 被省略了。容易发现在g和G之间有三个同构，分别是（Upu2)到（Vuv2), (v3,v2)和（v3,v4)。 结果是sup(g,G) =min{2, 2} =2。
[0060] 虽然在确定图上子图的重要性由支持度进行衡量，但此概念在不确定图上没有意 义，因为图结构中存在概率，包含关系变得模糊或者不确定.现有的工作在多个小的不确 定图的图集上定义了期望支持度，该定义计算不确定图来自所蕴含的确定图中支持度的贡 献，只要当前子图被包含了一次.扩展此概念，我们定义单个大的不确定图上期望支持度 为在所有可能图上支持度的聚合值，即支持度在所有由不确定图蕴含的确定图上的概率分 布.子图超过一个给定阈值被认为是频繁的.由于定义的偏移，目前在多个小不确定图的 图集上的算法不再适用于单个不确定图.我们提出了一个高效的具有精度保证的解决方 案，解决了基于边的概率和基于点的支持度计算。
[0061] 根据本发明的实施例，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法。
[0062] 如图1所示，根据本发明的实施例提供的针对单个不确定图的频繁子图挖掘与优 化方法包括：
[0063] 步骤S101，获取单个不确定图；
[0064] 步骤S103,根据单个不确定图枚举出单个不确定图的所有子图；
[0065] 步骤S105,在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0066] 步骤S107,在样本图集合中设定多个检查点，多个检查点将样本图集合分割为多 个部分样本图集合，并依次指定每个检查点；
[0067] 步骤S109,使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分 样本图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点 覆盖的部分样本图集合中每个样本图上的期望支持度；
[0068] 步骤S111，根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上 的期望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频 繁子图、或不确定是不是频繁子图，若判定该子图是频繁子图或不是频繁子图则停止该子 图的相关运算，若判定该子图不确定是不是频繁子图则继续指定下一个检查点并根据下一 个被指定检查点覆盖的部分样本图集合重新进行判定直到每个检查点都被指定过，其中， 对最末被指定的检查点覆盖的部分样本图集合进行判定时一定不会得出不确定的判定结 果；
[0069] 步骤S113,输出所有频繁子图。
[0070] 其中，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖 的部分样本图集合中每个样本图上的期望支持度，为根据单个不确定图构造重用树，为单 个不确定图的被指定检查点覆盖的部分样本图集合中每个样本图中的每条嵌入边构建反 向索引，并根据重用树与反向索引分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率与每个子图在被指定检查点覆盖的部分样本图集合中每 个样本图上的期望支持度。
[0071] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0072] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0073] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0074] 分别计算每个蕴含图所包含的所有子图。
[0075] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0076] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0077] 并且，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法每个子图在被指定检查点覆盖的部 分样本图集合中每个样本图上的期望支持度包括：
[0078] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0079] 指定单个不确定图的所有子图中的一个；
[0080] 分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本图上 的支持度；
[0081] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在被指定检查点覆盖的部分样本图集合中每个样本图的支持度；
[0082] 继续从单个不确定图中指定下一个子图并计算其在被指定检查点覆盖的部分样 本图集合中每个样本图上的支持度，直到单个不确定图的所有子图都被指定；
[0083] 根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的支持度， 计算每个子图在单个不确定图上的期望支持度。
[0084] 并且，分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本 图上的支持度，为使用最大独立集法计算被指定的子图在被指定检查点覆盖的部分样本图 集合中每个样本图上的基于最小像的支持度。
[0085] 并且，根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期 望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子 图、或不确定是不是频繁子图包括：
[0086] 获取期望支持度阈值；
[0087] 根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0088] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0089] 根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0090] 根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图，将 所有结果区间上限大于期望支持度阈值、且结果区间下限小于期望支持度阈值与非误差系 数的乘积的子图判定为不确定是不是频繁子图。
[0091] 下面根据具体实施例进一步阐述本发明的技术方案。
[0092] -个不确定图是一个元组Gu= (G，P)，其中G是一个确定图，P:Ee-(0，1是一个 概率函数，将每条边e映射为一个存在概率，由Pe表示，eGEG。G是主干图。
[0093] -旦确定了每条边的存在情况，由Gu可以蕴含得到确定图GS称为蕴含图。因此 一个不确定图Gu总共蕴含21%1可能的确定图，每个蕴含图都是Gu可能的存在方式。
[0094] 我们考虑的模型假设边之间的存在概率是相互独立的 ，这种模型有很多实际的应 用，那么，Gu蕴含G1的概率，或者G1的存在概率，可以通过包括或不包括边来计算：
[0096] 既然经典的关于支持度的概率在不确定图上变得很有意义，我们求助于期望支持 度，即在蕴含图上的概率分布情况。
[0097]我们将子图g在不确定图Gu上的期望支持度定义为：
[0099] 其中，以是6"的蕴含图。给定期望支持度阈值〇,子图g如果是频繁的，那么g在 Gu中的期望支持度将不小于阈值，即eSUp(g，Gu)彡〇。
[0100] 对每个Gu的蕴含图G1，
，esup(g,G1) <esup(g^，G1)。不等式在对 i进行求和后仍然成立。因此，esup(g，Gu)彡eSUp(g'，GU)，期望支持度是反单调的。
[0101] 在图2中，我们为G的每条边赋予一个存在概率并构造一个不确定图Gu，其中 存在概率建模两个人合作关系的紧密程度。此时，G是主干图，同时Gu有8个蕴含图，
=我们在上文中已经计算出sup(g，G) =2,因 此
。照此将所有来自蕴含图的值聚合起来，可以计算出 esup(g，Gu) = 1. 12。如果给定的支持度阈值〇 = 1，则esup(g，Gu)彡1，g是频繁子图。
[0102] 给定一个不确定图Gu= (G，P)和一个期望支持度阈值〇,单个不确定 图上频繁子图挖掘问题是指发现所有期望支持度不小于给定阈值的子图g，即
[0103] 我们在期望支持度的定义中给出了频繁子图的语义。假设sup(g，Gu) = 10, 4表 示一个随机独立选择的蕴含图，那么我们有理由期望g在4中至少有10次不重复的出现。 根据现有的分析，基于期望语义的频繁子图适合于在不确定图中进行主题发现。当不存在 二义性时，在后文中省略领域Gu，即表示为sup(g)。
[0104] 我们提出了一个枚举一评价的算法，取名为fanta(frequentsubgraphminingon uncertaingraphs)。fanta算法先枚举所有可能的候选子图，再对每个子图计算期望支持 度，然后决定是否将其作为结果输出。任何利用了Apriori性质的枚举策略都可以使用。 Apriori性质陈述的是，不频繁子图的超图也不可能是频繁的。特别地，不确定图中所有子 图可以被组织为一个有根的有向无环图（DAG)，其中节点代表候选子图（根表示为空KDAG 中从g'到g的一条弧表示g'是g的直接超图。我们从频繁的边开始，每次将一条新的边 加到频繁子图中，枚举所有可能子图，因此可以在DAG的第n层找到包含n条边的子图。为 了避免重复枚举同时保证完备性，我们使用方法gSpan给每个子图增加了词典顺序。
[0105] 然而，通过比较期望支持度和阈值，决定一个被枚举出的子图是否是频繁的，其最 简单的方式是产生所有蕴含图，计算并聚合子图在所有蕴含图上的支持度，得到期望支持 度，再与支持度阈值进行比较。但这种方法因为会产生大量蕴含图，加上支持度计算的高复 杂度，因此对终端用户而言是不可接受的。为了达到更好的运行性能，我们尝试所有可能， 在可接受时间内返回结果。
[0106] 我们已经发现，使用定义计算期望支持度复杂度相当高，因为Gu存在2丨心丨个蕴含 图。对每个候选子图，我们需要计算在指数级的确定图上计算其支持度，其中频繁涉及具有 高昂时间代价的子图同构检测。我们研宄这一问题并通过一个高效的算法来降低计算复杂 度。
[0107] 我们首先用另一种方式给出期望支持度的计算。假设P(sup(g) =j)表示子图g 在所有支持度等于j的蕴含图上的聚合概率，即
[0109] 其中，Aj(g) = {G'lsupfeG1) =j}。
[0110] 因此有
[0112] 其中，Ms=sup(g，G)是g在Gu所有蕴含图中最大的支持度。
[0113] 我们进一步定义，Pj(g)为g在Gu的蕴含图中支持度不小于j的聚合概率，SP
[0115] 其中，Aj(g) = {G'lsupfeG1)彡j}。
[0116] 同时，对esup(g)公式右端展开可得
[0118] 因此又有
[0120] 我们还注意到Pj(g)的两个性质：（l)Pj(g)彡Pj^ )，其中，
⑵ Pj(g)SPj, (g)，其中，Kj，<j。
[0121] 我们可以证明，计算1\化)是#?难的，其中卩是一个整型常数。可以将DNF计数问 题在多项式时间内归约为此问题，以此证明该问题是#P难的。
[0122] 考虑一个析取范式的一阶逻辑表达式（DNF)D=QVC2V~VCrCjiG[l，m]) 的形式为1，12八…八lk，其中，l」(je[l，k])是{Xl，x2，…，xj中的布尔变量。DNF计 数问题是计算有多少种对变量的赋值可以满足D。设P(Xi)表示Xi被赋值为真的概率，P(D) 是随机一组对变量的赋值满足D的概率，给定一个前述实例，下面构造了在Gu中计算P?；(g) 的问题。
[0123]我们构造一个不确定图Gu，其节点集合为ViUV2UV3，其中：
[0127] 其中，Vi*节点的标签为a，V2UV3中为0。边的构造方法如下：
[0128] (1)在
jG[l，k]，存在概率 为1 ;
[0129] (2)如果D中Xi包含在C，则在（ci,Uj)增加一条概率为1的边；
[0130] (3)对每个x#{xx2，…，xn}，在（Upv)之间增加概率为P(Xi)的一条边，所有 Gu的边标签为y。
[0131] 两个问题之间的关联性为：
[0132]每个对{xp x2,…，xn}的真值赋值JT一对一对应于Gu的一个蕴含图G \即边 (Ui，Vi)存在当且仅当\赋值为真，每个真值赋值31的概率等于
。显然，在所 有蕴含图以中，
，因此，如果一个真值赋值满足D，当且仅当g在蕴 含图6"中的支持度超过卩。因此
[0133] 综上可知，计算I\(g)是一个#P难问题。类似地，可以证明计算esup (g)也是#P 难的。
[0134] 图3示出的是布尔表达式D按照上述构造方法，得到的不确定图Gu和子图g，其 中，D= (XiAx2Ax3) V匕八叉^义^~士…士被赋值为真的概率分别是卩匕)，？" 2)，P (x3)，P (x4)。
[0135] 由于计算子图支持度问题具有#?难的时间复杂度，我们提出了一个近似评价算 法，其误差为e。作为近似算法，理想的结果是能够返回所有频繁的子图（真正）；为了满 足这一要求，则结果集中也会有不频繁的子图（假正）。根据这一目的，我们输出一个闭区 间[esup, esup]，该区间包含esup真实值，然后对于子图g的支持度与支持度阈值〇之间 关系的以下不同情况进行处理：
[0136] Case 1 :如果
不输出g，因为esup (g)〈〇是确定的；
[0137] Case 2 :如果
则输出g，因为 esup(g)彡（1-e) 〇是肯定的，而且很有可能esup(g)彡〇 ;
[0138] Case 3:如果
，则不能决定是否输出g，因 为我们不能决定是否esup(g)彡〇或者esup(g)〈（l-e) 〇。
[0139] Case 3并不是我们想要的，因为Case 3我们无法决定。然而，我们观察到如果区 间|esup,^n5〗的宽度在e 0范围内，则Case 3不会出现。因此，通过限制区间宽度最大 为e 〇,则通过[亞MB 来估计esup是足够的，因为此时只有Case 1和Case 2会出 现。这对于算法设计很重要，我们的算法依赖此来决定是否将g作为结果输出。
[0140] 我们的近似算法基于蒙特卡洛方法。通过
?我们首先计 算Pj(g)的近似值，其中，je [1，MJ ;然后聚合该值得到区间[^IME(g),^P(g)]。为了保 证区间不会大于e 〇，我们要求每个Pj(g)近似值的绝对误差不会超过e o/Ms。此要求来 自一类随机算法一一随机近似模式，可以提供精度保证。
[0141] 给定一个置信系数SG[0, 1]，以及一个绝对误差范围e'，我们可以使用由随 机近似模式得到的近似值及来估计P，如果
其中，1- S是置信 程度。为了在S和e '的条件下近似得到Pj(g)，我们依靠一个基于霍夫丁不等式的算法。
[0142] 假设XpX2，…，Xn是独立同分布的伯努利随机变量，其中Xi= 1的概率为p，则有 下述不等式成立：
[0144] n个样本观察值的平均可以提供一个具有精度保证关于p的近似，为提供置信度 1-S和绝对误差e' =eo/2Ms需要的样本量大小为：
[0146]算法1为评价一个子图的过程的封装。输入一个子图g，不确定图Gu误差系数e 以及实数S;输出一个布尔值，表示g是否是频繁的。
[0148] 算法第1行为Pj(g)的观察值分配一个空的数组，并计算札，即g在所有蕴含图中 最大的支持度，也即在Gu的主干图G中的支持度，其中嵌入（embedding)被记录下来，并以 其ID进行标识。第2行初始化变量，以及抽样次数N。接着，我们应用蒙特卡洛方法。第3 行收集N个随机抽取的蕴含图，或者Gu的样本图G^注意到"样本图"与"蕴含图"是不一样 的，因为两个样本图可能对应于同一个蕴含图。一个小的优化是，不用抽样图中所有的边， 而是只考虑嵌入边，S卩％={ei|eieF(g)}，其中F是g到G同构的集合，ie[1，|e」]。 这样便缩小了概率空间，而且相对在整个不确定图上进行抽样而言，并不影响正确性。我们 仍然用Gu的样本来表示，虽然只包含嵌入边（部分边），第4-7行计算g在每个Gi上的支 持度，并聚合对应的概率值
，即增加观察概率，或者1(g)的近似值（如果j不 大于sup(g，Gi)的话）。在浏览了所有样本图后，第9行通过函数EvaluateSup评价支持 度的近似值.
[0149]函数EvaluateSup工作流程为：输入Pj(g)的观察概率值P[j]、整数X， 并输出Case1或者Case2(Case3不应该出现）。特别地，当前概率观察值
，输出结果在
之 间。根据区间与支持度阈值0之间的关系作出决定。
[0150]< br>证明，只要样本量足够，所有输出 子图满足给定误差范围，算法1就是正确的。另一方面，由于在子图g增长的过程中存储 了其嵌入（embedding)，可以在0(|F(g) | |Vg|)的时间复杂度下计算Ms，其中F(g)是g嵌 入（embedding)的集合；接着，我们执行蒙特卡洛仿真计算支持度和概率的复杂度分别为 〇(|F(g) | |Vg|)和0(|Eg|)。因为总的抽样样本数量复杂度不超过
^，则 算法1的总复杂度是
：既然时间复杂度是关于
的多项 式级，算法1属于完全多项式随机近似模式（FPRAS)，该模式可以同时提供高效性和高准确 度。
[0151] 实现基于蒙特卡洛支持度评价的一种直观方式是在每个样本图中计算子图的支 持度，并聚合观察概率。这种方式会比较耗时，因此我们考虑可能的加速方法。
[0152]图4示出的是图2中不确定图Gu的两个样本图G'和G"，以及G'和G"的重用树 "DM_Bio"。首先，在计算
1后。我们可以进一步考虑边03来计算
另外。如果一个P的嵌入（embedding)存在于G"中，我们可以确定G'也包含了此嵌入而 不需要额外的计算。最后，为了算出sup(p，G")，我们构造了一个数据结构：
[0154]可增加一个新的列（v3_v4)，用于计算sup(p,G' )〇
[0155] 对于图4中的两个样本图
存在三种可以重用的计算：
[0156] (1)计算样本图的存在概率；
[0157] (2)测试一个嵌入是否存在；
[0158] (3)计算支持度。
[0159] 我们可以将此计算重用的思想泛化到多个样本图的情况，此时，样本图之间的包 含关系并不需要满足。
[0160] 对于第（1)种和第（2)种计算，我们首先要构造一个二叉重用树，其中所有样本图 都是树的叶节点。假设嵌入边有一种关于其ID的线性顺序，则可以得到传统的树的结构。 二叉树的深度为I ，在深度为i的所有分支决定于是否包含边％。换言之，根的深度为 1，其左分支h是一棵包含有e:这条边所有样本图的子树的根，而右分支i包含剩下的不 含4这条边所有样本图子树的根。这个分支过程从~到em中最后一条边，最终得到 叶节点。因此我们可以在叶节点为每个样本图找到一个对应的位置。
[0161] 我们不需要产生整棵树。我们每计算了一个样本图，就存储包含此样本图的一个 分支。我们采用如下方法产生样本图，并构造整个树：在根节点，对每个样本图h，我们随 机决定它是去左分支h还是右分支np左分支、右分支分别由left边和right边连接。接 着，如果^不为空，则将n1在树上保存下来，接着，随机决定样本图的去向；如果ni是空，则 停止此分支继续增长。对于~也是同样的处理过程，当所有的样本图都到达叶节点时，整 个迭代过程结束。在增长过程中，每个样本图的存在概率在增长过程中作为一个副产品计 算得到，同时计算重用达到最大。
[0162] 之后，我们计算每个样本图的支持度。第一步是决定每个样本图包含的嵌入 (embedding)。为此，我们对每条嵌入边维护一个反向索引，每条嵌入边作为一个条目，那些 包含这条边的嵌入（embedding)作为对应的记录。该索引便于发现那些因为不存在嵌入边 而缺少的嵌入，而该索引在主干图上计算支持度时建立，且开销较小。根据重用树的构造， 进入右分支意味着一条边e不存在，因此包含这条边的嵌入也不存在；而进入左分支并不 影响嵌入集合。
[0163] 对于一个样本图，我们从叶节点追踪到根节点，并记录下经过的right边。整个嵌 入集合减去那些一路上遇到的right边对应的嵌入即为考虑的样本图。另外，为了能计算 重用，我们在处理每个样本图时，都会记录树节点上的中间结果。接着，我们从最低父节点 开始，增量式地进行计算，即从叶节点到根节点路径上第一个已经被处理过的节点开始，而 不是从根节点开始。
[0164] 在图4示出的实施例中，右边的树是从G'和G"构造的部分重用树，其中ni是根， n4(或者n5)是叶节点，对应G'(或者G")。在处理完G'后，我们在节点n3有嵌入集合 {Vi-VhV3-V2,V3-V4}，该集合可以包含于任意在此分支后的样本图。接着，由于不存在边e3， 我们从反向索引上获取到那些不再包含的嵌入，即Iv3-v4}。然后我们将其删除，得到G"包 含的嵌入集合IvfVaV3-V2}。
[0165]接下来，我们以串行的方式进行第（3)种计算的重用。对于两个样本图G'和G"，我们首先描述怎样计算sup(g，G')。对每个包含在G'中的嵌入，我们将其对应的点排成 一行行。注意到由于我们已经获得了同构映射，因此该操作比一般情况要简单和迅速得多。 特别地，对于一个点vg，我们利用一个映射来记录一一G'中每个嵌入点作为键，该点在所 有嵌入中出现次数作为其值。当我们遇到一个嵌入以u作为^嵌入点时，则对u对应于vg 在映射中的值增加1。在对所有嵌入中的节点进行计数后，我们可以通过获取所有映射中最 小集合的值，得到sup(g,G')。
[0166] 为了在计算G"时重用之前的中间结果，而不是从头开始建立这些映射，我们首先 去除掉不包含在G"中的嵌入，减少其在映射中对应的值，然后增加之前没有包含在G'中 的嵌入，并增加对应的值。之后，我们可以得到sup(g，G")。
[0167] 对增加或减少一个单位的开销进行建模，固定为c;获取最小映射的集合大小的 开销为c'。给定一系列样本图匕，每个包含一个嵌入的集合FjGF，其中ie[l，N]，从 头开始计算支持度的开销为|F」*c+c'。我们定义：
[0169]从Gi(或Gj)到Gj(或GJ，支持度计算的开销是
，并 且
，则对于h，从头开始计算开销更小。为了最大化计算重用，我 们将此问题进行形式化地描述如下：
[0170] 给定一系列样本图GiGD，每个包含一个嵌入的集合FieF，其中，ie[l，N]， 从匕到h的计算开销为
，找到一个计算序列使得开销最小，满足每个 图只被处理过一次。
[0171] 该问题是NP难的。我们为每个样本图构造一个比特数组，每个比特对应一个F中 的嵌入，即数组的维度为|F|。如果样本图包含该对应的嵌入，则比特位设为1，相反则设为 0。这种情况下，两个图之间的开销可以通过计算二进制串之间的汉民距离比较容易获得。 接着我们使用一种启发式的计算序列一一从左到右对应样本图在叶节点的位置。直观的想 法是两个连续叶节点（如图4中的G'和G")，通常距离较小，因此增量计算复杂度相对 小。
[0172] 我们使用算法2将所有3中重用计算集合在一起如下：
[0174] 为了将算法2整合到基本算法中，我们可以将算法1中第4-8行替换为 "P-ShareCompTree(g,Q) "，使得算法2在基本算法中生效，修改后的算法1可以执行基 于计算重用的子图判定。
[0175] 除了上述的计算重用方法之外，对支持度评价的过程设计也可以加入计算剪枝来 进行优化。
[0176] 虽然需要
〖样本来保证算法1中的Case3不会出现，但我们实际上 可以在确保区间宽度之前决定g。在一些情况下，采样量未达到N时Case1或者Case2可 能就已经被满足，此时不需要继续采样计算，直接给出判定即可。一个极端的使用该思想的 方法是，在每次计算样本图后都进行检查，这样导致增加的开销反而大于减少的开销。为了 在两方面达到最好的平衡，我们引入一个定期检查的检查点机制，这样提前结束的情况可 以在检查点发生，详见算法3。
[0178] 检查点是一个给定的样本大小，在处理过的样本数量达到检查点时进行检查。假 设我们检查r次，当所有样本大小分别为q，…，ck,…q，其中0 = 〈…<(^=N。每到 达一个检查点，我们就计算ck+1-ck个样本，特别地，第3-4行从样本空间Q中获取样本图。 接着，在第5行计算通过Q'计算Pj(g)的观察概率。最终，第6行通过函数EvaluateSup 决定是否输出子图。注意，在这里Case3在没有达到最终检查点之前都是合法的。
[0179] 为了将此机制引入算法框架，我们将算法1中的第4-12行替换为算法3。注意到 对每个子图，重用树即其他数据结构在整个检查点过程中都是缓存下来的。下面我们将介 绍此方法的细节及检查点的选择。
[0180] 在EvaluateSup最简单的实现中，根据绝对误差可以得到一个区间。然而，绝对误 差可能会特别大，特别是当样本比较少的时候。相反的，这就给了我们提示，即如果有一个 更紧的上界来辅助决策，那么评价性能可以进一步提升。事实上，我们试图考虑图结构性 质，来发现更紧的上界，而不是用绝对误差直接作为上界。
[0181] -个esup(g)的上界u(g)可以用来对子图进行剪枝。如果u(g)〈 〇，则可以确 定g是不频繁的。通过Apriori性质，Pj(g)由Pj(g')进行约束，其中gEg且|Eg| = |Eg, |+1。然而该不等式比较简单，我们是否可以增强其剪枝效果？ 一种直接的想法是为Pj(g')乘上Pj(e)，其中e是g新增的边。然而，这种想法是不正确的。
[0182] 考虑如图5所示的不确定图Gu、子图g和g'。注意对于g和g'，在所有蕴含图 中，只有主干图G可以提供支持度为4,因此
.其中 e=g\g',P4(g)>P4(g, )*P4(e)〇
[0183] 虽然该结果违反直觉，我们认为这是因为在单个不确定图上基于节点的支持 度计算的特殊约束。然而在很多情况下我们还是可以利用剪枝规则。对于如图5所示 的两个子图g和g'，其中g是g'的直接超图，且满足
。 我们已知
，其中，A」(g)=彡j}，以 是Gu的蕴含图；假设
，其中Aj(g'Ae) = {G^supfeG1)彡j八supe，Gi彡j，根据Apriori性质，
因此 Pjg彡Pjg'八e。另外因为eJZg，则sup(g、G1)彡j与sup(e,G1)彡j是相互独立的， 则P」(g'Ae)=Pj(g' )P」(e)，因此有不等式 ).Pj(e)成立。
[0184] 为了应用剪枝规则，我们定义一个指示变量：
[0186] 特别地，当e不同于g'中所有边时，I= 1意味着我们可以 利用更加紧的上界 Pj(g) <Pj(g'）?Pj(e)，否贝丨J使用基于Apriori性质的界。
[0187] esup(g)受以下等式所约束：
[0189] 其中，g是g'的直接超图，e是独特的边。这里"独特"是指不存在另一条边 ^eEg,具有相同的标签。这样，我们可以推到出一系列上界
，满足
。因此，对于x有很多种选择来应用 此剪枝规则。虽然很多剪枝规则都可以用，但剪枝效果却因为界紧的程度不同而差别很大。[0190]注意到该上界需要Pj(g')以及Pj(e)，但其真实值都是未知的。幸运的 是，它们的观察值是可得到的。特别地，前者在这之前计算得到，后者则可以提前计 算并全局存储。接着，我们可以用观察概率值P^g')和1(e)并加上其绝对误差，
3值得注意的是如果因为样本量不够大导致误 差e'足够大，
都会很大，限制了剪枝效果。因此，我们需要保证B(g')异口 B (e)的精度来提供好的剪枝效果。
[0191] 由于Pj(g)彡Pj-Jg)，Pj(g)本质上是被min{Pj(g' ) ?Pj(e)，Pj^ (g)}所约束，因 此剪枝效果还可以进一步提升。
[0192] 依赖于何时执行剪枝，我们提供一个评价过程，称为敏锐评价，如算法4所示。"敏 锐"是指该评价方法总是尽早过滤掉不频繁的子图，为了利用这个技术，我们将算法3第6 行替换为"switchPruneEval(P,k)do"。
[0194] 算法4对于所有频繁子图，为了保证绝对误差不超过
可能抽样到最大 次数。换言之，结果是：
[0195] (1)如果g是频繁的，那么它和算法1加上检查点机制是一样的；
[0196] (2)如果是不频繁的，那么样本量大小将被极大减少。
[0197] 在实际数据中，不频繁的子图比频繁子图更多。
[0198] 值得注意的是这一系列上界碰巧为检查点提供很好的选择。更准确的是，我们可 以保证ux(g)的
I在e 〇范围内当应用Pj(g) SP^g') "。.⑷提供的上界。 接着，每个上界的样本大小刚好提供了检查点，即
，即我 们总共抽样凡次，而其相对应的绝对误差分别为
[0199] 我们设计了实验来验证算法的可行性。
[0200] 所有评价的算法都使用C++，并提供STL支持。特别的，首先实现了不包含算法重 用与算法剪枝的算法框架，命名为基本算法；在基础算法之上，实现提出的优化技术。我们 选择亚马逊EC2作为标准实验平台，其中我们选择c3. 2xlarge进行实验。每个示例有28 个计算单元，8个虚拟CPU及15G内存。
[0201] 默认情况下，我们的实验在两个现实世界，两种不同应用背景的网络数据集上进 行。一个是引文网络，另一个是社交网络。
[0202] CIT是一个典型出版文章的引用网络，包括约3千个出版文献（点）及约4000个 引用关系（边）。每个点有单个标签，表示其在计算机科学的领域，总共6个不同的标签。 每条边都有一个标签（从0到100)，衡量文献之间的差异性。因此，小的标签意味着大的相 似性。两份文献之间的相似性由边在不确定图中的概率进行表示。
[0203] C0L是一个DBLP上的学者合作网络，包括100k不同的作者及450k合作边。节点 标签表示一个人主要研宄方向，边的概率表达两个不同作者合作关系的强度。特别地，概率 由均值U的CDF指数进行推导；如果两个作者合作t次，则对应的概率为l-et/w [17,19， 31]。按照惯例，我们在实验中考虑y=5。
[0204] 总结表1中数据集的特点。为了对比，两个不确定图有不同的结构特征。图的密 度由|E|/|V|进行衡量。因此，CIT的密度为1.43,而C0L的密度大约为3. 50。虽然C0L数 量和密度都大于CIT，但C0L不同节点标签数量比CIT更大。另外，平均存在概率值分别是 0? 12 和 0? 23。
[0205] Table1:DatasetStatistics
[0207] 我们记录并报告以下衡量结果：
[0208] (1)算法发现并返回的子图数量；
[0209] (2)总的样本大小，即算法产生并处理的样本图数量；
[0210] (3)运行时间，运行完一个算法所需的总时间。
[0211] 在此，我们评价所提算法框架，即基本算法的近似质量。回忆精确算法需要枚举所 有可能的蕴含图。既然不可能在一个稍微大一些的图上，精确发现所有真实的频繁模式，我 们在CIT的一个部分图上进行实验（30个点），并认为在e= 〇. 〇1且S= 〇. 〇1时，发现 的子图都是真的频繁子图，实验中将支持度阈值设为2。注意到在这样的参数设定下，基本 算法需要很长时间才能完成。
[0212] 我们研宄关于参数e与S的近似质量。特别地，近似质量由精确率和召回率进 行衡量一一精确率是在返回结果中真频繁的子图所占百分比，而召回率是返回子图所占所 有真频繁子图的百分比。CIT和C0L的结果在图6中进行比较。
[0213] 图6描述输出子图，其中白条表示发现的错误频繁子图，而黑条表示真频繁子图。 我们将e从〇. 01到〇. 3变化，S保持〇. 1，在条之上的数字分别表示准确率（加粗）和召 回率。图6揭示了随着e的变化，基本算法的准确率下降，但召回率基本保持不变。这是因 为：⑴当e变大时，更多的错误频繁子图会被返回，因此降低精度⑵当S是固定的，一 个频繁子图被返回的概率是一定的，因此返回的真实频繁子图数量并不会收太大影响。图 6还显示随S从〇.〇1到0.3变化，e=0.1时结果的变化。我们观察到虽然准确度基本 维持在95%，召回率则随着S的增加而降低。原因是：（1)固定e决定了错误频繁子图的 期望数量；（2)在S增加的同时，频繁子图被输出的概率降低，因此，返回的真频繁子图数 量减少，导致召回率降低。
[0214] 简而言之，实验证明我们提出了近似框架具有很高近似质量。
[0215] 我们还评价在近似框架下所提优化技术的效果。特别地，我们比较了三个算法，为 了表达清晰，分别表示为[基本]，[+重用]，[+剪枝]。
[0216] [基本]:基本的基于蒙特卡洛仿真，挖掘单个不确定图的近似算法，即算法1 ;
[0217] [+重用]:在[基本]上应用计算重用技术，即算法2;
[0218] [+剪枝]:在[+重用]的基础上，包含所有提出的优化策略，即算法3+4。
[0219] 图7绘制了在CIT上运行算法的时间。我们固定e与S为〇. 1，将支持度〇的 值从35到55变化。图显示运行时间降低十分明显。另外，[+重用]很大程度上提高了 [基本]的效率，而[+剪枝]进一步增加了算法运行速度，虽然提高相对于[+重用]效果 适中。在最好的情况下，当支持度阈值〇 =35时，节约时间的效果最明显，降低了 73. 1% 的运行时间。我们进一步在COL上进行实验。虽然反映了相似的趋势，但也有两点区别。 首先，执行时间的降低在C0L上相对CIT更加明显，特别当支持度阈值很小时。第二点，[+ 重用]的效果相对[+剪枝]更加明显，证明在C0L上剪枝效果更好。进一步，当〇 = 100 时，所提技术节省了最多的计算时间，大约1000s。
[0220] 进一步鉴别剪枝技术，我们研宄总的样本量。图8描绘了在CIT和COL上需要的 总的样本数量。重点需要观察的是剪枝策略使得提前结束成为可能，使得需要更少的样本。 既然[+重用]并不考虑剪枝，那么气需要的样本数量和[基本]是一样的，因此我们忽略 对其进行比较。两个图都反映了剪枝规则很有效，减少了约1
?的样本量，最终使得运行 速度加快。
[0221] 总的来讲，[+重用]相比[基本]体现了优越性，而[+剪枝]比[+重用]更好。 因此[+剪枝]作为最终的算法fanta。接下来，我们评价参数值变化对于fanta不确定性， 及可扩展性的影响。
[0222] 除了 〇，用户定义的参数e与S也会影响算法性能。在本组实验中，我们衡量 e与6的变化对算法效率的影响程度，其中fanta与Baseline进行了比较与分析。
[0223] 我们固定〇 = 40,S= 〇. 1，在数据集CIT上，每次对e增加〇.〇5。结果在图9 中进行展示，作为一般的趋势，执行时间随着e的增加而降低，e越大降低的趋势越小。值 得注意的是fanta受e变化的影响相对较小，而且相对于Baseline来讲性能更佳，进一步 证明了fanta的优越性和鲁棒性。在数据集C0L上进行了相似的实验，其中〇 = 200,S =0. 1。可以在图9上看到相似的趋势；然而反映了受e变化影响更大。
[0224] 接着，我们评价S的影响，其值来自{〇. 05, 0. 10, 0. 15, 0. 20}。图10总结了分别 在CIT和C0L上的实验结果，两个图显示执行时间随着S的增加而逐渐降低。和e的变 化带来的影响相比，S变化对执行时间带来的影响并不显著。
[0225] 总而言之，fanta对e和S的变化相对不那么敏感；同时，两个算法受e的影响 都比S大。这是合理的，因为算法时间复杂度是关于'
，成比例的。
[0226] 另一方面，探宄不确定性，即图边存在概率的概率分布，对算法的影响很有意义。 为此，定义一个数学转换模型，将存在概率P(e)转换为f(P(e)):
[0228] 该转换在CIT数据集上进行实验。由于CIT上边的平均概率较小，我们对fanta 在平均概率更高情况的图上表现，以及对于固定平均概率，增大概率分布方差的情况更感 兴趣。对此，我们首先固定(^并增大C(l，从0.1到0.5,其中〇 =50,e与S都是0.1。
[0229] 从图11可以看出，随着C(l的增加，执行时间也在增大，概括来讲，基本保持了线性 增加的趋势。这是合理的，因为概率值的增加可以提高期望支持度的值。当〇固定，更多 的子图将需要进行评价，因此导致更多频繁子图。
[0230] 之后，我们将c# 0. 5到1变化，并设cf(1-cDy，其中y是边上存在概率的 均值。显然在转变后，概率均值维持不变，但分布方差将变大。图11显示执行时间随(^而 增加，虽然最终逐渐趋于平缓。这是因为增大的概率方差导致更多的边具有高概率。结果 是，一些子图具有了更高的 支持度，增加了整体的运行时间。
[0231] 简而言之，概率分布对算法效率具有显著。更高的均值和更大的方差都将导致更 多频繁子图，并最终增加执行时间。
[0232]fanta算法的可扩展性在两方面进行评价一一数据集大小和密度。数据集大小通 过节点数量进行衡量，但与此同时保持密度不变；而密度则固定|V|变化
I图中数据从 C0L合成得到。
[0233] 首先，fanta在分别0.2,0.4,0.6,0.8部分C0L上进行评价，其中〇 = 100。图12 显示一个快速增长的趋势，特别是当比例从〇. 6升高到0. 8时，增长速率在0. 8之后有所下 降。注意到，随着数据大小的增加，被发现子图数量并不是线性增加而是指数级增加。实际 上，我们进行了另一个实验（由于空间有限，没有在此展示），支持度阈值随着比例增加，这 样可以得到一个线性增长的趋势。
[0234] 关于密度的实验是在C0L的一个样本上进行的，该样本具有20, 000个点，边的数 量不断变化。在图12中，x轴代表密度，S卩|E| = |V|，2|V|，3|V|，4|V|，5|V|，〇 = 100。 从图中可以看出，运行时间不断增加，增长率也不断提升。我们认为这是因为和支持度阈值 结果相同的原因.
[0235] 可扩展性实验显示fanta可以处理较大的现实图数据，正如那些现有的为单确定 图挖掘设计的算法.
[0236] 综上所述，为获得不仅频繁，而且在现实中具有高置信度的子图，我们定义了在单 个不确定图上，基于期望支持度的频繁子图挖掘问题，基于期望语义的支持度对于在不确 定网络中主题发现很有用。为了说明此问题的高复杂度，通过将DNF计数问题归约为此问 题，我们证明了计算子图期望支持度是#P难的，我们提出了一种基于蒙特卡洛的近似算法 来获取一个区间，并以给定精确度包含真实值，将获取的支持度区间与支持度阈值之间的 关系分为三种情况，可以保证，以概率至少为1-8,任何子图支持度不小于〇的子图都会 被输出，同时任何期望支持度小于（1-e) 〇的子图都不会输出。此分类确定了我们枚举一 评价的算法框架，即慎重地枚举候选子图并逐一评价。
[0237] 同时，我们对抽取样本中可重用的计算进行共享，还提前对不频繁的候选子图进 行剪枝，通过在线建立的二叉共享树进行计算重用，并在基于检查点的机制上，设计了基于 结构的剪枝规则，以在特定检查点过滤掉不太可能频繁的候选子图，大幅度减少了子图挖 掘消耗的时间。
[0238] 最后我们使用真实数据，对所提算法fanta进行了广泛的实验研宄。通过实验发 现，所提算法框架能在单个不确定大图上正常工作，能获得基于期望存在概率的频繁子图。 而且，增加了优化技术的近似算法优化效果明显，最大减少了 71. 3%的运行时间，因此提高 了挖掘性能及用户体验。借助于本发明的上述技术方案，通过将单个不确定图划分为多个 蕴含的确定图并将蕴含图视作确定图使用计算重用方法抽样计算子图的期望支持度的手 段，我们能在单个不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
[0239] 所属领域的普通技术人员应当理解：以上所述仅为本发明的具体实施例而已，并 不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。
【主权项】
1. 一种针对单个不确定图的频繁子图挖掘与优化方法，其特征在于，包括： 获取单个不确定图； 根据所述单个不确定图枚举出所述单个不确定图的所有子图； 在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图； 在所述样本图集合中设定多个检查点，所述多个检查点将所述样本图集合分割为多个 部分样本图集合，并依次指定所述每个检查点； 使用计算重用方法分别计算所述单个不确定图的所述被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算所述每个子图在所述被指定检 查点覆盖的部分样本图集合中每个样本图上的期望支持度； 根据所述每个子图在所述被指定检查点覆盖的部分样本图集合中每个样本图上的期 望支持度与所述单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频 繁子图、或不确定是不是频繁子图，若判定该子图是频繁子图或不是频繁子图则停止该子 图的相关运算，若判定该子图不确定是不是频繁子图则继续指定下一个检查点并根据下一 个被指定检查点覆盖的部分样本图集合重新进行判定直到所述每个检查点都被指定过，其 中，对所述最末被指定的检查点覆盖的部分样本图集合进行判定时一定不会得出不确定的 判定结果； 输出所有频繁子图。2. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的所述被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算所述每个子图在所述被指定检 查点覆盖的部分样本图集合中每个样本图上的期望支持度，为根据所述单个不确定图构造 重用树，为所述单个不确定图的所述被指定检查点覆盖的部分样本图集合中每个样本图中 的每条嵌入边构建反向索引，并根据所述重用树与所述反向索引分别计算所述单个不确定 图的所述被指定检查点覆盖的部分样本图集合中每个样本图的存在概率与所述每个子图 在所述被指定检查点覆盖的部分样本图集合中每个样本图上的期望支持度。3. 根据权利要求2所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图构造重用树，为从所述单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到所述单个不确定图上所有节点与嵌入边的二叉树形式均被重 用树包括。4. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图枚举出所述单个不确定图的所有子图包括： 从所述单个不确定图提取出多个蕴含图，所述每个蕴含图都是所述单个不确定图可能 的存在方式； 分别计算所述每个蕴含图所包含的所有子图。5. 根据权利要求4所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，所述提取出多个蕴含图的个数为2的所述单个不确定图中边的个数次幂。6. 根据权利要求5所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在所述单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，所述样本图的数量与任一子图在 所述单个不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成 反比，与误差系数的平方成反比，与支持度阈值的平方成反比。7. 根据权利要求6所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的所述被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法所述每个子图在所述被指定检查点 覆盖的部分样本图集合中每个样本图上的期望支持度包括： 根据所述单个不确定图中每条边的概率，计算出所述每个蕴含图的存在概率； 指定所述单个不确定图的所有子图中的一个； 分别计算所述被指定的子图在所述被指定检查点覆盖的部分样本图集合中每个样本 图上的支持度； 根据所述每个样本图的存在概率、所述被指定的子图在每个样本图上的支持度，计算 所述被指定的子图在所述被指定检查点覆盖的部分样本图集合中每个样本图的支持度； 继续从所述单个不确定图中指定下一个子图并计算其在所述被指定检查点覆盖的部 分样本图集合中每个样本图上的支持度，直到所述单个不确定图的所有子图都被指定； 根据所述每个子图在所述被指定检查点覆盖的部分样本图集合中每个样本图上的支 持度，计算所述每个子图在所述单个不确定图上的期望支持度。8. 根据权利要求7中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，分别计算所述被指定的子图在所述被指定检查点覆盖的部分样本图集合中每个样 本图上的支持度，为使用最大独立集法计算所述被指定的子图在所述被指定检查点覆盖的 部分样本图集合中每个样本图上的基于最小像的支持度。9. 根据权利要求8中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，根据所述每个子图在所述被指定检查点覆盖的部分样本图集合中每个样本图上的 期望支持度与所述单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是 频繁子图、或不确定是不是频繁子图包括： 获取期望支持度阈值； 根据所述单个不确定图的每个样本图的存在概率，计算所述子图在所有支持度等于一 恒定值的蕴含图上的聚合概率； 根据所述子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算所述子图在所 述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率； 根据所述子图在所述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚 合概率，计算当前概率观察值与结果区间； 根据所述结果区间与期望支持度阈值判定所述子图是否为频繁子图，将所有结果区 间上限大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的 子图判定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子 图，将所有结果区间上限大于期望支持度阈值、且结果区间下限小于期望支持度阈值与非 误差系数的乘积的子图判定为不确定是不是频繁子图。
【专利摘要】本发明公开了一种针对单个不确定图的频繁子图挖掘与优化方法，包括：获取单个不确定图；枚举出单个不确定图的所有子图；指定部分蕴含图为样本图；多个检查点将样本图集合分割为多个部分样本图集合，并依次指定每个检查点；使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期望支持度；根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子图、或不确定是不是频繁子图；输出所有频繁子图。
【IPC分类】G06T7/00
【公开号】CN104899885
【申请号】CN201510299659
【发明人】赵翔, 陈一帆, 胡艳丽, 汤大权
【申请人】中国人民解放军国防科学技术大学
【公开日】2015年9月9日
【申请日】2015年6月3日
【技术领域】
[0001] 本发明涉及图挖掘技术，特别地，涉及一种针对单个不确定图的频繁子图挖掘与 优化方法。
【背景技术】
[0002] 不确定性在现实应用中，无论是对内源还是外源，都是一种固有的属性。例如，在 一个合作社交网络中，利用目前掌握的信息，我们未必能明确断言比尔和马修两人具有很 好的合作关系，通常我们使用概率来衡量这种合作关系的可能性。假设这种关系存在的概 率为p，P的值由本领域专家通过可用信息人工确定，或者由信息抽取或生成规则自动产 生。在大数据时代的今天，对于管理不确定数据有更为强烈的需求，因此目前出现了各种质 量不一的数据。特别地，我们专注于不确定图，尤其是图的边上具有存在概率的不确定图。 不确定图模型具有广泛的应用领域，除了社会网络，不确定图模型还被应用于通信网络，无 线传感器网络，蛋白质交互网络以及生物学中的调控网络等。
[0003] 另一方面，频繁模式挖掘作为数据挖掘领域高度关注的主题，一直持续了近十年， 相关研宄也取得了长足的进展，其中频繁子图引起了特别的研宄兴趣。所谓频繁子图是指 从多个小确定图的集合或者单个大确定图中发现的支持度不小于用户给定阈值的子图。频 繁子图再刻画确定图的数据特征、分类、聚类以及建立索引方面具有重要作用。
[0004] 虽然目前对于频繁子图及其在确定图上挖掘的方法已经具有很好的理解，但在不 确定图上，这一问题变得更加有趣但也更少被研宄。一个不确定图时特殊的边加权图，其中 每条边（u，v)上的权重是其存在的概率。最近，研宄工作致力于在多个小的不确定图的图 集上挖掘频繁子图。但是，该问题在单个大型不确定图中虽然同等重要，因为现实生活中的 大型网络越来越多地出现了不确定性一一比如，在社会网络中一个人对另一个人的影响是 具有概率的；在生物网络中的蛋白质交互情况也有一定测量误差一一但现有技术在本方面 是一片空白。
[0005] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 目前尚缺乏有效的解决方案。
【发明内容】
[0006] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 本发明的目的在于提出一种针对单个不确定图的频繁子图挖掘与优化方法，能允许针对单 个不确定图进行频繁子图挖掘并优化挖掘算法，填补了本领域的技术空白。
[0007] 基于上述目的，本发明提供的技术方案如下：
[0008] 根据本发明的一个方面，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法，包括：
[0009] 获取单个不确定图；
[0010] 根据单个不确定图枚举出单个不确定图的所有子图；
[0011] 在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0012] 在样本图集合中设定多个检查点，多个检查点将样本图集合分割为多个部分样本 图集合，并依次指定每个检查点；
[0013] 使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本图集 合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖的部 分样本图集合中每个样本图上的期望支持度；
[0014] 根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期望支 持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子图、或 不确定是不是频繁子图，若判定该子图是频繁子图或不是频繁子图则停止该子图的相关运 算，若判定该子图不确定是不是频繁子图则继续指定下一个检查点并根据下一个被指定检 查点覆盖的部分样本图集合重新进行判定直到每个检查点都被指定过，其中，对最末被指 定的检查点覆盖的部分样本图集合进行判定时一定不会得出不确定的判定结果；
[0015] 输出所有频繁子图。
[0016] 其中，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖 的部分样本图集合中每个样本图上的期望支持度，为根据单个不确定图构造重用树，为单 个不确定图的被指定检查点覆盖的部分样本图集合中每个样本图中的每条嵌入边构建反 向索引，并根据重用树与反向索引分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率与每个子图在被指定检查点覆盖的部分样本图集合中每 个样本图上的期望支持度。
[0017] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0018] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0019] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0020] 分别计算每个蕴含图所包含的所有子图。
[0021] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0022] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0023] 并且，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法每个子图在被指定检查点覆盖的部 分样本图集合中每个样本图上的期望支持度包括：
[0024] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0025] 指定单个不确定图的所有子图中的一个；
[0026] 分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本图上 的支持度；
[0027] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在被指定检查点覆盖的部分样本图集合中每个样本图的支持度；
[0028] 继续从单个不确定图中指定下一个子图并计算其在被指定检查点覆盖的部分样 本图集合中每个样本图上的支持度，直到单个不确定图的所有子图都被指定；
[0029] 根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的支持度， 计算每个子图在单个不确定图上的期望支持度。
[0030] 并且，分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本 图上的支持度，为使用最大独立集法计算被指定的子图在被指定检查点覆盖的部分样本图 集合中每个样本图上的基于最小像的支持度。
[0031] 并且，根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期 望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子 图、或不确定是不是频繁子图包括：
[0032] 获取期望支持度阈值；
[0033] 根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0034] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0035] 根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0036] 根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图，将 所有结果区间上限大于期望支持度阈值、且结果区间下限小于期望支持度阈值与非误差系 数的乘积的子图判定为不确定是不是频繁子图。
[0037] 从上面所述可以看出，本发明提供的技术方案通过将单个不确定图划分为多个蕴 含的确定图并将蕴含图视作确定图使用计算重用方法与计算剪枝方法抽样计算子图的期 望支持度的手段，能在单个不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
【附图说明】
[0038] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所 需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施 例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获 得其他的附图。
[0039] 图1为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 的流程图；
[0040] 图2为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图、确定图与子图的一个实施例；
[0041]图3为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，根据布尔表达式获得的单个不确定图及其子图的一个实施例；
[0042]图4为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图的两个样本图及其重用树的一个实施例；
[0043]图5为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图及其两个子图在算法剪枝中一个反直觉的实施例；
[0044]图6为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，输出频繁子图正确率随置信度阈值与非误差系数在CIT上变化的柱状图；
[0045] 图7为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，三种不同算法在CIT与C0L上的运行时间折线图；
[0046]图8为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，两种不同算法在CIT与C0L上的运行样本量柱状图；
[0047] 图9为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，fanta与baseline算法耗时随非误差系数在CIT与C0L上变化的运行时间折线图； [0048]图10为根据本发明实施例的一种针对单个不确定图的频繁子图 挖掘与优化方法 中，fanta与baseline算法耗时随置信度阈值在CIT与C0L上变化的运行时间折线图； [0049]图11为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，fanta算法耗时随不确定因素在C0L上变化的运行时间折线图；
[0050] 图12为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，fanta算法耗时随数据集大小与数据集密度在C0L上变化的运行时间折线图。
【具体实施方式】
[0051] 为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明实施例中 的附图，对本发明实施例中的技术方案进一步进行清楚、完整、详细地描述，显然，所描述的 实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域 普通技术人员所获得的所有其他实施例，都属于本发明保护的范围。
[0052] -个确定图G是一个元组（VpEe,le，2e)，其中，是节点集合，
是 边的集合，e是为节点和边赋予标签的函数。|Ve|和|Ee|分别表示G中节 点和边的数量。为了描述简便，我们假设图是无向的，且没有自循环和多重边。但是，本方 法可以很容易的被拓展到具有多重边的有向图。
[0053] 如果存在单射f:Vg- 时满足以下两个条件：
[0056] 我们就用gGG:表不一个子图g同构于确定图G。我们称g是G的子图，G是g 的超图，f(g)是g在G中的一个嵌入。如果g是g'的直接超图，那么gGg',且|Eg| = |Eg, |+1。直接超图是指仅比子图多一条边的超图。
[0057]对于gGG，以及支持度阈值t，假设存在一个函数来衡量g在G中的支持度，那 么最直接的想法是计算g在G中的同构次数。然而，该支持度计算方法不具有反单调性。反 单调性对于开发能够有效剪枝搜索空间的算法是十分关键的，如果没有此性质，则不得在 整个空间进行穷举搜索。因此，目前的研宄提出了很多具有反单调性的支持度计算法方法， 包括最小映射法（MI)，有害重叠法（H0)，以及最大独立集法（MIS)。这些计算方法都是基于 子图同构，但对延生的重叠兼容性有所不同，而导致计算复杂度不同。特别的，MI是唯一一 个可以高效计算的方法，而H0和MIS都涉及解决NP完全的问题；MI得到的结果是HO/MIS 得到结果的超集，因此，其结果可以从MI的结果通过进一步计算得到。因此，接下来我们使 用MI作为支持度计算的标准，然而算法只需要简单改变即可拓展到另外两种计算方法。
[0058] 考虑从g到G的一个子图同构集合F= {f}。F(v)表示|v' }，其中对于每个 ，，存在映射f?将vGVg映射到，。基于最小像的支持度表示为SUp(g,G) =
下文中"支持度"是"基于最小像的支持度"的缩写。
[0059] 图2示出了确定图G和子图g，该图建模了合作社交网络，其中节点表示人，边表示 合作关系。每个人的研宄领域作为标签，即Bio表示生物学家；为了图示的清晰，边的标签 被省略了。容易发现在g和G之间有三个同构，分别是（Upu2)到（Vuv2), (v3,v2)和（v3,v4)。 结果是sup(g,G) =min{2, 2} =2。
[0060] 虽然在确定图上子图的重要性由支持度进行衡量，但此概念在不确定图上没有意 义，因为图结构中存在概率，包含关系变得模糊或者不确定.现有的工作在多个小的不确 定图的图集上定义了期望支持度，该定义计算不确定图来自所蕴含的确定图中支持度的贡 献，只要当前子图被包含了一次.扩展此概念，我们定义单个大的不确定图上期望支持度 为在所有可能图上支持度的聚合值，即支持度在所有由不确定图蕴含的确定图上的概率分 布.子图超过一个给定阈值被认为是频繁的.由于定义的偏移，目前在多个小不确定图的 图集上的算法不再适用于单个不确定图.我们提出了一个高效的具有精度保证的解决方 案，解决了基于边的概率和基于点的支持度计算。
[0061] 根据本发明的实施例，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法。
[0062] 如图1所示，根据本发明的实施例提供的针对单个不确定图的频繁子图挖掘与优 化方法包括：
[0063] 步骤S101，获取单个不确定图；
[0064] 步骤S103,根据单个不确定图枚举出单个不确定图的所有子图；
[0065] 步骤S105,在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0066] 步骤S107,在样本图集合中设定多个检查点，多个检查点将样本图集合分割为多 个部分样本图集合，并依次指定每个检查点；
[0067] 步骤S109,使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分 样本图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点 覆盖的部分样本图集合中每个样本图上的期望支持度；
[0068] 步骤S111，根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上 的期望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频 繁子图、或不确定是不是频繁子图，若判定该子图是频繁子图或不是频繁子图则停止该子 图的相关运算，若判定该子图不确定是不是频繁子图则继续指定下一个检查点并根据下一 个被指定检查点覆盖的部分样本图集合重新进行判定直到每个检查点都被指定过，其中， 对最末被指定的检查点覆盖的部分样本图集合进行判定时一定不会得出不确定的判定结 果；
[0069] 步骤S113,输出所有频繁子图。
[0070] 其中，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖 的部分样本图集合中每个样本图上的期望支持度，为根据单个不确定图构造重用树，为单 个不确定图的被指定检查点覆盖的部分样本图集合中每个样本图中的每条嵌入边构建反 向索引，并根据重用树与反向索引分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率与每个子图在被指定检查点覆盖的部分样本图集合中每 个样本图上的期望支持度。
[0071] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0072] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0073] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0074] 分别计算每个蕴含图所包含的所有子图。
[0075] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0076] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0077] 并且，使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法每个子图在被指定检查点覆盖的部 分样本图集合中每个样本图上的期望支持度包括：
[0078] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0079] 指定单个不确定图的所有子图中的一个；
[0080] 分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本图上 的支持度；
[0081] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在被指定检查点覆盖的部分样本图集合中每个样本图的支持度；
[0082] 继续从单个不确定图中指定下一个子图并计算其在被指定检查点覆盖的部分样 本图集合中每个样本图上的支持度，直到单个不确定图的所有子图都被指定；
[0083] 根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的支持度， 计算每个子图在单个不确定图上的期望支持度。
[0084] 并且，分别计算被指定的子图在被指定检查点覆盖的部分样本图集合中每个样本 图上的支持度，为使用最大独立集法计算被指定的子图在被指定检查点覆盖的部分样本图 集合中每个样本图上的基于最小像的支持度。
[0085] 并且，根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期 望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子 图、或不确定是不是频繁子图包括：
[0086] 获取期望支持度阈值；
[0087] 根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0088] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0089] 根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0090] 根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图，将 所有结果区间上限大于期望支持度阈值、且结果区间下限小于期望支持度阈值与非误差系 数的乘积的子图判定为不确定是不是频繁子图。
[0091] 下面根据具体实施例进一步阐述本发明的技术方案。
[0092] -个不确定图是一个元组Gu= (G，P)，其中G是一个确定图，P:Ee-(0，1是一个 概率函数，将每条边e映射为一个存在概率，由Pe表示，eGEG。G是主干图。
[0093] -旦确定了每条边的存在情况，由Gu可以蕴含得到确定图GS称为蕴含图。因此 一个不确定图Gu总共蕴含21%1可能的确定图，每个蕴含图都是Gu可能的存在方式。
[0094] 我们考虑的模型假设边之间的存在概率是相互独立的 ，这种模型有很多实际的应 用，那么，Gu蕴含G1的概率，或者G1的存在概率，可以通过包括或不包括边来计算：
[0096] 既然经典的关于支持度的概率在不确定图上变得很有意义，我们求助于期望支持 度，即在蕴含图上的概率分布情况。
[0097]我们将子图g在不确定图Gu上的期望支持度定义为：
[0099] 其中，以是6"的蕴含图。给定期望支持度阈值〇,子图g如果是频繁的，那么g在 Gu中的期望支持度将不小于阈值，即eSUp(g，Gu)彡〇。
[0100] 对每个Gu的蕴含图G1，
，esup(g,G1) <esup(g^，G1)。不等式在对 i进行求和后仍然成立。因此，esup(g，Gu)彡eSUp(g'，GU)，期望支持度是反单调的。
[0101] 在图2中，我们为G的每条边赋予一个存在概率并构造一个不确定图Gu，其中 存在概率建模两个人合作关系的紧密程度。此时，G是主干图，同时Gu有8个蕴含图，
=我们在上文中已经计算出sup(g，G) =2,因 此
。照此将所有来自蕴含图的值聚合起来，可以计算出 esup(g，Gu) = 1. 12。如果给定的支持度阈值〇 = 1，则esup(g，Gu)彡1，g是频繁子图。
[0102] 给定一个不确定图Gu= (G，P)和一个期望支持度阈值〇,单个不确定 图上频繁子图挖掘问题是指发现所有期望支持度不小于给定阈值的子图g，即
[0103] 我们在期望支持度的定义中给出了频繁子图的语义。假设sup(g，Gu) = 10, 4表 示一个随机独立选择的蕴含图，那么我们有理由期望g在4中至少有10次不重复的出现。 根据现有的分析，基于期望语义的频繁子图适合于在不确定图中进行主题发现。当不存在 二义性时，在后文中省略领域Gu，即表示为sup(g)。
[0104] 我们提出了一个枚举一评价的算法，取名为fanta(frequentsubgraphminingon uncertaingraphs)。fanta算法先枚举所有可能的候选子图，再对每个子图计算期望支持 度，然后决定是否将其作为结果输出。任何利用了Apriori性质的枚举策略都可以使用。 Apriori性质陈述的是，不频繁子图的超图也不可能是频繁的。特别地，不确定图中所有子 图可以被组织为一个有根的有向无环图（DAG)，其中节点代表候选子图（根表示为空KDAG 中从g'到g的一条弧表示g'是g的直接超图。我们从频繁的边开始，每次将一条新的边 加到频繁子图中，枚举所有可能子图，因此可以在DAG的第n层找到包含n条边的子图。为 了避免重复枚举同时保证完备性，我们使用方法gSpan给每个子图增加了词典顺序。
[0105] 然而，通过比较期望支持度和阈值，决定一个被枚举出的子图是否是频繁的，其最 简单的方式是产生所有蕴含图，计算并聚合子图在所有蕴含图上的支持度，得到期望支持 度，再与支持度阈值进行比较。但这种方法因为会产生大量蕴含图，加上支持度计算的高复 杂度，因此对终端用户而言是不可接受的。为了达到更好的运行性能，我们尝试所有可能， 在可接受时间内返回结果。
[0106] 我们已经发现，使用定义计算期望支持度复杂度相当高，因为Gu存在2丨心丨个蕴含 图。对每个候选子图，我们需要计算在指数级的确定图上计算其支持度，其中频繁涉及具有 高昂时间代价的子图同构检测。我们研宄这一问题并通过一个高效的算法来降低计算复杂 度。
[0107] 我们首先用另一种方式给出期望支持度的计算。假设P(sup(g) =j)表示子图g 在所有支持度等于j的蕴含图上的聚合概率，即
[0109] 其中，Aj(g) = {G'lsupfeG1) =j}。
[0110] 因此有
[0112] 其中，Ms=sup(g，G)是g在Gu所有蕴含图中最大的支持度。
[0113] 我们进一步定义，Pj(g)为g在Gu的蕴含图中支持度不小于j的聚合概率，SP
[0115] 其中，Aj(g) = {G'lsupfeG1)彡j}。
[0116] 同时，对esup(g)公式右端展开可得
[0118] 因此又有
[0120] 我们还注意到Pj(g)的两个性质：（l)Pj(g)彡Pj^ )，其中，
⑵ Pj(g)SPj, (g)，其中，Kj，<j。
[0121] 我们可以证明，计算1\化)是#?难的，其中卩是一个整型常数。可以将DNF计数问 题在多项式时间内归约为此问题，以此证明该问题是#P难的。
[0122] 考虑一个析取范式的一阶逻辑表达式（DNF)D=QVC2V~VCrCjiG[l，m]) 的形式为1，12八…八lk，其中，l」(je[l，k])是{Xl，x2，…，xj中的布尔变量。DNF计 数问题是计算有多少种对变量的赋值可以满足D。设P(Xi)表示Xi被赋值为真的概率，P(D) 是随机一组对变量的赋值满足D的概率，给定一个前述实例，下面构造了在Gu中计算P?；(g) 的问题。
[0123]我们构造一个不确定图Gu，其节点集合为ViUV2UV3，其中：
[0127] 其中，Vi*节点的标签为a，V2UV3中为0。边的构造方法如下：
[0128] (1)在
jG[l，k]，存在概率 为1 ;
[0129] (2)如果D中Xi包含在C，则在（ci,Uj)增加一条概率为1的边；
[0130] (3)对每个x#{xx2，…，xn}，在（Upv)之间增加概率为P(Xi)的一条边，所有 Gu的边标签为y。
[0131] 两个问题之间的关联性为：
[0132]每个对{xp x2,…，xn}的真值赋值JT一对一对应于Gu的一个蕴含图G \即边 (Ui，Vi)存在当且仅当\赋值为真，每个真值赋值31的概率等于
。显然，在所 有蕴含图以中，
，因此，如果一个真值赋值满足D，当且仅当g在蕴 含图6"中的支持度超过卩。因此
[0133] 综上可知，计算I\(g)是一个#P难问题。类似地，可以证明计算esup (g)也是#P 难的。
[0134] 图3示出的是布尔表达式D按照上述构造方法，得到的不确定图Gu和子图g，其 中，D= (XiAx2Ax3) V匕八叉^义^~士…士被赋值为真的概率分别是卩匕)，？" 2)，P (x3)，P (x4)。
[0135] 由于计算子图支持度问题具有#?难的时间复杂度，我们提出了一个近似评价算 法，其误差为e。作为近似算法，理想的结果是能够返回所有频繁的子图（真正）；为了满 足这一要求，则结果集中也会有不频繁的子图（假正）。根据这一目的，我们输出一个闭区 间[esup, esup]，该区间包含esup真实值，然后对于子图g的支持度与支持度阈值〇之间 关系的以下不同情况进行处理：
[0136] Case 1 :如果
不输出g，因为esup (g)〈〇是确定的；
[0137] Case 2 :如果
则输出g，因为 esup(g)彡（1-e) 〇是肯定的，而且很有可能esup(g)彡〇 ;
[0138] Case 3:如果
，则不能决定是否输出g，因 为我们不能决定是否esup(g)彡〇或者esup(g)〈（l-e) 〇。
[0139] Case 3并不是我们想要的，因为Case 3我们无法决定。然而，我们观察到如果区 间|esup,^n5〗的宽度在e 0范围内，则Case 3不会出现。因此，通过限制区间宽度最大 为e 〇,则通过[亞MB 来估计esup是足够的，因为此时只有Case 1和Case 2会出 现。这对于算法设计很重要，我们的算法依赖此来决定是否将g作为结果输出。
[0140] 我们的近似算法基于蒙特卡洛方法。通过
?我们首先计 算Pj(g)的近似值，其中，je [1，MJ ;然后聚合该值得到区间[^IME(g),^P(g)]。为了保 证区间不会大于e 〇，我们要求每个Pj(g)近似值的绝对误差不会超过e o/Ms。此要求来 自一类随机算法一一随机近似模式，可以提供精度保证。
[0141] 给定一个置信系数SG[0, 1]，以及一个绝对误差范围e'，我们可以使用由随 机近似模式得到的近似值及来估计P，如果
其中，1- S是置信 程度。为了在S和e '的条件下近似得到Pj(g)，我们依靠一个基于霍夫丁不等式的算法。
[0142] 假设XpX2，…，Xn是独立同分布的伯努利随机变量，其中Xi= 1的概率为p，则有 下述不等式成立：
[0144] n个样本观察值的平均可以提供一个具有精度保证关于p的近似，为提供置信度 1-S和绝对误差e' =eo/2Ms需要的样本量大小为：
[0146]算法1为评价一个子图的过程的封装。输入一个子图g，不确定图Gu误差系数e 以及实数S;输出一个布尔值，表示g是否是频繁的。
[0148] 算法第1行为Pj(g)的观察值分配一个空的数组，并计算札，即g在所有蕴含图中 最大的支持度，也即在Gu的主干图G中的支持度，其中嵌入（embedding)被记录下来，并以 其ID进行标识。第2行初始化变量，以及抽样次数N。接着，我们应用蒙特卡洛方法。第3 行收集N个随机抽取的蕴含图，或者Gu的样本图G^注意到"样本图"与"蕴含图"是不一样 的，因为两个样本图可能对应于同一个蕴含图。一个小的优化是，不用抽样图中所有的边， 而是只考虑嵌入边，S卩％={ei|eieF(g)}，其中F是g到G同构的集合，ie[1，|e」]。 这样便缩小了概率空间，而且相对在整个不确定图上进行抽样而言，并不影响正确性。我们 仍然用Gu的样本来表示，虽然只包含嵌入边（部分边），第4-7行计算g在每个Gi上的支 持度，并聚合对应的概率值
，即增加观察概率，或者1(g)的近似值（如果j不 大于sup(g，Gi)的话）。在浏览了所有样本图后，第9行通过函数EvaluateSup评价支持 度的近似值.
[0149]函数EvaluateSup工作流程为：输入Pj(g)的观察概率值P[j]、整数X， 并输出Case1或者Case2(Case3不应该出现）。特别地，当前概率观察值
，输出结果在
之 间。根据区间与支持度阈值0之间的关系作出决定。
[0150]< br>证明，只要样本量足够，所有输出 子图满足给定误差范围，算法1就是正确的。另一方面，由于在子图g增长的过程中存储 了其嵌入（embedding)，可以在0(|F(g) | |Vg|)的时间复杂度下计算Ms，其中F(g)是g嵌 入（embedding)的集合；接着，我们执行蒙特卡洛仿真计算支持度和概率的复杂度分别为 〇(|F(g) | |Vg|)和0(|Eg|)。因为总的抽样样本数量复杂度不超过
^，则 算法1的总复杂度是
：既然时间复杂度是关于
的多项 式级，算法1属于完全多项式随机近似模式（FPRAS)，该模式可以同时提供高效性和高准确 度。
[0151] 实现基于蒙特卡洛支持度评价的一种直观方式是在每个样本图中计算子图的支 持度，并聚合观察概率。这种方式会比较耗时，因此我们考虑可能的加速方法。
[0152]图4示出的是图2中不确定图Gu的两个样本图G'和G"，以及G'和G"的重用树 "DM_Bio"。首先，在计算
1后。我们可以进一步考虑边03来计算
另外。如果一个P的嵌入（embedding)存在于G"中，我们可以确定G'也包含了此嵌入而 不需要额外的计算。最后，为了算出sup(p，G")，我们构造了一个数据结构：
[0154]可增加一个新的列（v3_v4)，用于计算sup(p,G' )〇
[0155] 对于图4中的两个样本图
存在三种可以重用的计算：
[0156] (1)计算样本图的存在概率；
[0157] (2)测试一个嵌入是否存在；
[0158] (3)计算支持度。
[0159] 我们可以将此计算重用的思想泛化到多个样本图的情况，此时，样本图之间的包 含关系并不需要满足。
[0160] 对于第（1)种和第（2)种计算，我们首先要构造一个二叉重用树，其中所有样本图 都是树的叶节点。假设嵌入边有一种关于其ID的线性顺序，则可以得到传统的树的结构。 二叉树的深度为I ，在深度为i的所有分支决定于是否包含边％。换言之，根的深度为 1，其左分支h是一棵包含有e:这条边所有样本图的子树的根，而右分支i包含剩下的不 含4这条边所有样本图子树的根。这个分支过程从~到em中最后一条边，最终得到 叶节点。因此我们可以在叶节点为每个样本图找到一个对应的位置。
[0161] 我们不需要产生整棵树。我们每计算了一个样本图，就存储包含此样本图的一个 分支。我们采用如下方法产生样本图，并构造整个树：在根节点，对每个样本图h，我们随 机决定它是去左分支h还是右分支np左分支、右分支分别由left边和right边连接。接 着，如果^不为空，则将n1在树上保存下来，接着，随机决定样本图的去向；如果ni是空，则 停止此分支继续增长。对于~也是同样的处理过程，当所有的样本图都到达叶节点时，整 个迭代过程结束。在增长过程中，每个样本图的存在概率在增长过程中作为一个副产品计 算得到，同时计算重用达到最大。
[0162] 之后，我们计算每个样本图的支持度。第一步是决定每个样本图包含的嵌入 (embedding)。为此，我们对每条嵌入边维护一个反向索引，每条嵌入边作为一个条目，那些 包含这条边的嵌入（embedding)作为对应的记录。该索引便于发现那些因为不存在嵌入边 而缺少的嵌入，而该索引在主干图上计算支持度时建立，且开销较小。根据重用树的构造， 进入右分支意味着一条边e不存在，因此包含这条边的嵌入也不存在；而进入左分支并不 影响嵌入集合。
[0163] 对于一个样本图，我们从叶节点追踪到根节点，并记录下经过的right边。整个嵌 入集合减去那些一路上遇到的right边对应的嵌入即为考虑的样本图。另外，为了能计算 重用，我们在处理每个样本图时，都会记录树节点上的中间结果。接着，我们从最低父节点 开始，增量式地进行计算，即从叶节点到根节点路径上第一个已经被处理过的节点开始，而 不是从根节点开始。
[0164] 在图4示出的实施例中，右边的树是从G'和G"构造的部分重用树，其中ni是根， n4(或者n5)是叶节点，对应G'(或者G")。在处理完G'后，我们在节点n3有嵌入集合 {Vi-VhV3-V2,V3-V4}，该集合可以包含于任意在此分支后的样本图。接着，由于不存在边e3， 我们从反向索引上获取到那些不再包含的嵌入，即Iv3-v4}。然后我们将其删除，得到G"包 含的嵌入集合IvfVaV3-V2}。
[0165]接下来，我们以串行的方式进行第（3)种计算的重用。对于两个样本图G'和G"，我们首先描述怎样计算sup(g，G')。对每个包含在G'中的嵌入，我们将其对应的点排成 一行行。注意到由于我们已经获得了同构映射，因此该操作比一般情况要简单和迅速得多。 特别地，对于一个点vg，我们利用一个映射来记录一一G'中每个嵌入点作为键，该点在所 有嵌入中出现次数作为其值。当我们遇到一个嵌入以u作为^嵌入点时，则对u对应于vg 在映射中的值增加1。在对所有嵌入中的节点进行计数后，我们可以通过获取所有映射中最 小集合的值，得到sup(g,G')。
[0166] 为了在计算G"时重用之前的中间结果，而不是从头开始建立这些映射，我们首先 去除掉不包含在G"中的嵌入，减少其在映射中对应的值，然后增加之前没有包含在G'中 的嵌入，并增加对应的值。之后，我们可以得到sup(g，G")。
[0167] 对增加或减少一个单位的开销进行建模，固定为c;获取最小映射的集合大小的 开销为c'。给定一系列样本图匕，每个包含一个嵌入的集合FjGF，其中ie[l，N]，从 头开始计算支持度的开销为|F」*c+c'。我们定义：
[0169]从Gi(或Gj)到Gj(或GJ，支持度计算的开销是
，并 且
，则对于h，从头开始计算开销更小。为了最大化计算重用，我 们将此问题进行形式化地描述如下：
[0170] 给定一系列样本图GiGD，每个包含一个嵌入的集合FieF，其中，ie[l，N]， 从匕到h的计算开销为
，找到一个计算序列使得开销最小，满足每个 图只被处理过一次。
[0171] 该问题是NP难的。我们为每个样本图构造一个比特数组，每个比特对应一个F中 的嵌入，即数组的维度为|F|。如果样本图包含该对应的嵌入，则比特位设为1，相反则设为 0。这种情况下，两个图之间的开销可以通过计算二进制串之间的汉民距离比较容易获得。 接着我们使用一种启发式的计算序列一一从左到右对应样本图在叶节点的位置。直观的想 法是两个连续叶节点（如图4中的G'和G")，通常距离较小，因此增量计算复杂度相对 小。
[0172] 我们使用算法2将所有3中重用计算集合在一起如下：
[0174] 为了将算法2整合到基本算法中，我们可以将算法1中第4-8行替换为 "P-ShareCompTree(g,Q) "，使得算法2在基本算法中生效，修改后的算法1可以执行基 于计算重用的子图判定。
[0175] 除了上述的计算重用方法之外，对支持度评价的过程设计也可以加入计算剪枝来 进行优化。
[0176] 虽然需要
〖样本来保证算法1中的Case3不会出现，但我们实际上 可以在确保区间宽度之前决定g。在一些情况下，采样量未达到N时Case1或者Case2可 能就已经被满足，此时不需要继续采样计算，直接给出判定即可。一个极端的使用该思想的 方法是，在每次计算样本图后都进行检查，这样导致增加的开销反而大于减少的开销。为了 在两方面达到最好的平衡，我们引入一个定期检查的检查点机制，这样提前结束的情况可 以在检查点发生，详见算法3。
[0178] 检查点是一个给定的样本大小，在处理过的样本数量达到检查点时进行检查。假 设我们检查r次，当所有样本大小分别为q，…，ck,…q，其中0 = 〈…<(^=N。每到 达一个检查点，我们就计算ck+1-ck个样本，特别地，第3-4行从样本空间Q中获取样本图。 接着，在第5行计算通过Q'计算Pj(g)的观察概率。最终，第6行通过函数EvaluateSup 决定是否输出子图。注意，在这里Case3在没有达到最终检查点之前都是合法的。
[0179] 为了将此机制引入算法框架，我们将算法1中的第4-12行替换为算法3。注意到 对每个子图，重用树即其他数据结构在整个检查点过程中都是缓存下来的。下面我们将介 绍此方法的细节及检查点的选择。
[0180] 在EvaluateSup最简单的实现中，根据绝对误差可以得到一个区间。然而，绝对误 差可能会特别大，特别是当样本比较少的时候。相反的，这就给了我们提示，即如果有一个 更紧的上界来辅助决策，那么评价性能可以进一步提升。事实上，我们试图考虑图结构性 质，来发现更紧的上界，而不是用绝对误差直接作为上界。
[0181] -个esup(g)的上界u(g)可以用来对子图进行剪枝。如果u(g)〈 〇，则可以确 定g是不频繁的。通过Apriori性质，Pj(g)由Pj(g')进行约束，其中gEg且|Eg| = |Eg, |+1。然而该不等式比较简单，我们是否可以增强其剪枝效果？ 一种直接的想法是为Pj(g')乘上Pj(e)，其中e是g新增的边。然而，这种想法是不正确的。
[0182] 考虑如图5所示的不确定图Gu、子图g和g'。注意对于g和g'，在所有蕴含图 中，只有主干图G可以提供支持度为4,因此
.其中 e=g\g',P4(g)>P4(g, )*P4(e)〇
[0183] 虽然该结果违反直觉，我们认为这是因为在单个不确定图上基于节点的支持 度计算的特殊约束。然而在很多情况下我们还是可以利用剪枝规则。对于如图5所示 的两个子图g和g'，其中g是g'的直接超图，且满足
。 我们已知
，其中，A」(g)=彡j}，以 是Gu的蕴含图；假设
，其中Aj(g'Ae) = {G^supfeG1)彡j八supe，Gi彡j，根据Apriori性质，
因此 Pjg彡Pjg'八e。另外因为eJZg，则sup(g、G1)彡j与sup(e,G1)彡j是相互独立的， 则P」(g'Ae)=Pj(g' )P」(e)，因此有不等式 ).Pj(e)成立。
[0184] 为了应用剪枝规则，我们定义一个指示变量：
[0186] 特别地，当e不同于g'中所有边时，I= 1意味着我们可以 利用更加紧的上界 Pj(g) <Pj(g'）?Pj(e)，否贝丨J使用基于Apriori性质的界。
[0187] esup(g)受以下等式所约束：
[0189] 其中，g是g'的直接超图，e是独特的边。这里"独特"是指不存在另一条边 ^eEg,具有相同的标签。这样，我们可以推到出一系列上界
，满足
。因此，对于x有很多种选择来应用 此剪枝规则。虽然很多剪枝规则都可以用，但剪枝效果却因为界紧的程度不同而差别很大。[0190]注意到该上界需要Pj(g')以及Pj(e)，但其真实值都是未知的。幸运的 是，它们的观察值是可得到的。特别地，前者在这之前计算得到，后者则可以提前计 算并全局存储。接着，我们可以用观察概率值P^g')和1(e)并加上其绝对误差，
3值得注意的是如果因为样本量不够大导致误 差e'足够大，
都会很大，限制了剪枝效果。因此，我们需要保证B(g')异口 B (e)的精度来提供好的剪枝效果。
[0191] 由于Pj(g)彡Pj-Jg)，Pj(g)本质上是被min{Pj(g' ) ?Pj(e)，Pj^ (g)}所约束，因 此剪枝效果还可以进一步提升。
[0192] 依赖于何时执行剪枝，我们提供一个评价过程，称为敏锐评价，如算法4所示。"敏 锐"是指该评价方法总是尽早过滤掉不频繁的子图，为了利用这个技术，我们将算法3第6 行替换为"switchPruneEval(P,k)do"。
[0194] 算法4对于所有频繁子图，为了保证绝对误差不超过
可能抽样到最大 次数。换言之，结果是：
[0195] (1)如果g是频繁的，那么它和算法1加上检查点机制是一样的；
[0196] (2)如果是不频繁的，那么样本量大小将被极大减少。
[0197] 在实际数据中，不频繁的子图比频繁子图更多。
[0198] 值得注意的是这一系列上界碰巧为检查点提供很好的选择。更准确的是，我们可 以保证ux(g)的
I在e 〇范围内当应用Pj(g) SP^g') "。.⑷提供的上界。 接着，每个上界的样本大小刚好提供了检查点，即
，即我 们总共抽样凡次，而其相对应的绝对误差分别为
[0199] 我们设计了实验来验证算法的可行性。
[0200] 所有评价的算法都使用C++，并提供STL支持。特别的，首先实现了不包含算法重 用与算法剪枝的算法框架，命名为基本算法；在基础算法之上，实现提出的优化技术。我们 选择亚马逊EC2作为标准实验平台，其中我们选择c3. 2xlarge进行实验。每个示例有28 个计算单元，8个虚拟CPU及15G内存。
[0201] 默认情况下，我们的实验在两个现实世界，两种不同应用背景的网络数据集上进 行。一个是引文网络，另一个是社交网络。
[0202] CIT是一个典型出版文章的引用网络，包括约3千个出版文献（点）及约4000个 引用关系（边）。每个点有单个标签，表示其在计算机科学的领域，总共6个不同的标签。 每条边都有一个标签（从0到100)，衡量文献之间的差异性。因此，小的标签意味着大的相 似性。两份文献之间的相似性由边在不确定图中的概率进行表示。
[0203] C0L是一个DBLP上的学者合作网络，包括100k不同的作者及450k合作边。节点 标签表示一个人主要研宄方向，边的概率表达两个不同作者合作关系的强度。特别地，概率 由均值U的CDF指数进行推导；如果两个作者合作t次，则对应的概率为l-et/w [17,19， 31]。按照惯例，我们在实验中考虑y=5。
[0204] 总结表1中数据集的特点。为了对比，两个不确定图有不同的结构特征。图的密 度由|E|/|V|进行衡量。因此，CIT的密度为1.43,而C0L的密度大约为3. 50。虽然C0L数 量和密度都大于CIT，但C0L不同节点标签数量比CIT更大。另外，平均存在概率值分别是 0? 12 和 0? 23。
[0205] Table1:DatasetStatistics
[0207] 我们记录并报告以下衡量结果：
[0208] (1)算法发现并返回的子图数量；
[0209] (2)总的样本大小，即算法产生并处理的样本图数量；
[0210] (3)运行时间，运行完一个算法所需的总时间。
[0211] 在此，我们评价所提算法框架，即基本算法的近似质量。回忆精确算法需要枚举所 有可能的蕴含图。既然不可能在一个稍微大一些的图上，精确发现所有真实的频繁模式，我 们在CIT的一个部分图上进行实验（30个点），并认为在e= 〇. 〇1且S= 〇. 〇1时，发现 的子图都是真的频繁子图，实验中将支持度阈值设为2。注意到在这样的参数设定下，基本 算法需要很长时间才能完成。
[0212] 我们研宄关于参数e与S的近似质量。特别地，近似质量由精确率和召回率进 行衡量一一精确率是在返回结果中真频繁的子图所占百分比，而召回率是返回子图所占所 有真频繁子图的百分比。CIT和C0L的结果在图6中进行比较。
[0213] 图6描述输出子图，其中白条表示发现的错误频繁子图，而黑条表示真频繁子图。 我们将e从〇. 01到〇. 3变化，S保持〇. 1，在条之上的数字分别表示准确率（加粗）和召 回率。图6揭示了随着e的变化，基本算法的准确率下降，但召回率基本保持不变。这是因 为：⑴当e变大时，更多的错误频繁子图会被返回，因此降低精度⑵当S是固定的，一 个频繁子图被返回的概率是一定的，因此返回的真实频繁子图数量并不会收太大影响。图 6还显示随S从〇.〇1到0.3变化，e=0.1时结果的变化。我们观察到虽然准确度基本 维持在95%，召回率则随着S的增加而降低。原因是：（1)固定e决定了错误频繁子图的 期望数量；（2)在S增加的同时，频繁子图被输出的概率降低，因此，返回的真频繁子图数 量减少，导致召回率降低。
[0214] 简而言之，实验证明我们提出了近似框架具有很高近似质量。
[0215] 我们还评价在近似框架下所提优化技术的效果。特别地，我们比较了三个算法，为 了表达清晰，分别表示为[基本]，[+重用]，[+剪枝]。
[0216] [基本]:基本的基于蒙特卡洛仿真，挖掘单个不确定图的近似算法，即算法1 ;
[0217] [+重用]:在[基本]上应用计算重用技术，即算法2;
[0218] [+剪枝]:在[+重用]的基础上，包含所有提出的优化策略，即算法3+4。
[0219] 图7绘制了在CIT上运行算法的时间。我们固定e与S为〇. 1，将支持度〇的 值从35到55变化。图显示运行时间降低十分明显。另外，[+重用]很大程度上提高了 [基本]的效率，而[+剪枝]进一步增加了算法运行速度，虽然提高相对于[+重用]效果 适中。在最好的情况下，当支持度阈值〇 =35时，节约时间的效果最明显，降低了 73. 1% 的运行时间。我们进一步在COL上进行实验。虽然反映了相似的趋势，但也有两点区别。 首先，执行时间的降低在C0L上相对CIT更加明显，特别当支持度阈值很小时。第二点，[+ 重用]的效果相对[+剪枝]更加明显，证明在C0L上剪枝效果更好。进一步，当〇 = 100 时，所提技术节省了最多的计算时间，大约1000s。
[0220] 进一步鉴别剪枝技术，我们研宄总的样本量。图8描绘了在CIT和COL上需要的 总的样本数量。重点需要观察的是剪枝策略使得提前结束成为可能，使得需要更少的样本。 既然[+重用]并不考虑剪枝，那么气需要的样本数量和[基本]是一样的，因此我们忽略 对其进行比较。两个图都反映了剪枝规则很有效，减少了约1
?的样本量，最终使得运行 速度加快。
[0221] 总的来讲，[+重用]相比[基本]体现了优越性，而[+剪枝]比[+重用]更好。 因此[+剪枝]作为最终的算法fanta。接下来，我们评价参数值变化对于fanta不确定性， 及可扩展性的影响。
[0222] 除了 〇，用户定义的参数e与S也会影响算法性能。在本组实验中，我们衡量 e与6的变化对算法效率的影响程度，其中fanta与Baseline进行了比较与分析。
[0223] 我们固定〇 = 40,S= 〇. 1，在数据集CIT上，每次对e增加〇.〇5。结果在图9 中进行展示，作为一般的趋势，执行时间随着e的增加而降低，e越大降低的趋势越小。值 得注意的是fanta受e变化的影响相对较小，而且相对于Baseline来讲性能更佳，进一步 证明了fanta的优越性和鲁棒性。在数据集C0L上进行了相似的实验，其中〇 = 200,S =0. 1。可以在图9上看到相似的趋势；然而反映了受e变化影响更大。
[0224] 接着，我们评价S的影响，其值来自{〇. 05, 0. 10, 0. 15, 0. 20}。图10总结了分别 在CIT和C0L上的实验结果，两个图显示执行时间随着S的增加而逐渐降低。和e的变 化带来的影响相比，S变化对执行时间带来的影响并不显著。
[0225] 总而言之，fanta对e和S的变化相对不那么敏感；同时，两个算法受e的影响 都比S大。这是合理的，因为算法时间复杂度是关于'
，成比例的。
[0226] 另一方面，探宄不确定性，即图边存在概率的概率分布，对算法的影响很有意义。 为此，定义一个数学转换模型，将存在概率P(e)转换为f(P(e)):
[0228] 该转换在CIT数据集上进行实验。由于CIT上边的平均概率较小，我们对fanta 在平均概率更高情况的图上表现，以及对于固定平均概率，增大概率分布方差的情况更感 兴趣。对此，我们首先固定(^并增大C(l，从0.1到0.5,其中〇 =50,e与S都是0.1。
[0229] 从图11可以看出，随着C(l的增加，执行时间也在增大，概括来讲，基本保持了线性 增加的趋势。这是合理的，因为概率值的增加可以提高期望支持度的值。当〇固定，更多 的子图将需要进行评价，因此导致更多频繁子图。
[0230] 之后，我们将c# 0. 5到1变化，并设cf(1-cDy，其中y是边上存在概率的 均值。显然在转变后，概率均值维持不变，但分布方差将变大。图11显示执行时间随(^而 增加，虽然最终逐渐趋于平缓。这是因为增大的概率方差导致更多的边具有高概率。结果 是，一些子图具有了更高的 支持度，增加了整体的运行时间。
[0231] 简而言之，概率分布对算法效率具有显著。更高的均值和更大的方差都将导致更 多频繁子图，并最终增加执行时间。
[0232]fanta算法的可扩展性在两方面进行评价一一数据集大小和密度。数据集大小通 过节点数量进行衡量，但与此同时保持密度不变；而密度则固定|V|变化
I图中数据从 C0L合成得到。
[0233] 首先，fanta在分别0.2,0.4,0.6,0.8部分C0L上进行评价，其中〇 = 100。图12 显示一个快速增长的趋势，特别是当比例从〇. 6升高到0. 8时，增长速率在0. 8之后有所下 降。注意到，随着数据大小的增加，被发现子图数量并不是线性增加而是指数级增加。实际 上，我们进行了另一个实验（由于空间有限，没有在此展示），支持度阈值随着比例增加，这 样可以得到一个线性增长的趋势。
[0234] 关于密度的实验是在C0L的一个样本上进行的，该样本具有20, 000个点，边的数 量不断变化。在图12中，x轴代表密度，S卩|E| = |V|，2|V|，3|V|，4|V|，5|V|，〇 = 100。 从图中可以看出，运行时间不断增加，增长率也不断提升。我们认为这是因为和支持度阈值 结果相同的原因.
[0235] 可扩展性实验显示fanta可以处理较大的现实图数据，正如那些现有的为单确定 图挖掘设计的算法.
[0236] 综上所述，为获得不仅频繁，而且在现实中具有高置信度的子图，我们定义了在单 个不确定图上，基于期望支持度的频繁子图挖掘问题，基于期望语义的支持度对于在不确 定网络中主题发现很有用。为了说明此问题的高复杂度，通过将DNF计数问题归约为此问 题，我们证明了计算子图期望支持度是#P难的，我们提出了一种基于蒙特卡洛的近似算法 来获取一个区间，并以给定精确度包含真实值，将获取的支持度区间与支持度阈值之间的 关系分为三种情况，可以保证，以概率至少为1-8,任何子图支持度不小于〇的子图都会 被输出，同时任何期望支持度小于（1-e) 〇的子图都不会输出。此分类确定了我们枚举一 评价的算法框架，即慎重地枚举候选子图并逐一评价。
[0237] 同时，我们对抽取样本中可重用的计算进行共享，还提前对不频繁的候选子图进 行剪枝，通过在线建立的二叉共享树进行计算重用，并在基于检查点的机制上，设计了基于 结构的剪枝规则，以在特定检查点过滤掉不太可能频繁的候选子图，大幅度减少了子图挖 掘消耗的时间。
[0238] 最后我们使用真实数据，对所提算法fanta进行了广泛的实验研宄。通过实验发 现，所提算法框架能在单个不确定大图上正常工作，能获得基于期望存在概率的频繁子图。 而且，增加了优化技术的近似算法优化效果明显，最大减少了 71. 3%的运行时间，因此提高 了挖掘性能及用户体验。借助于本发明的上述技术方案，通过将单个不确定图划分为多个 蕴含的确定图并将蕴含图视作确定图使用计算重用方法抽样计算子图的期望支持度的手 段，我们能在单个不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
[0239] 所属领域的普通技术人员应当理解：以上所述仅为本发明的具体实施例而已，并 不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。
【主权项】
1. 一种针对单个不确定图的频繁子图挖掘与优化方法，其特征在于，包括： 获取单个不确定图； 根据所述单个不确定图枚举出所述单个不确定图的所有子图； 在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图； 在所述样本图集合中设定多个检查点，所述多个检查点将所述样本图集合分割为多个 部分样本图集合，并依次指定所述每个检查点； 使用计算重用方法分别计算所述单个不确定图的所述被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算所述每个子图在所述被指定检 查点覆盖的部分样本图集合中每个样本图上的期望支持度； 根据所述每个子图在所述被指定检查点覆盖的部分样本图集合中每个样本图上的期 望支持度与所述单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频 繁子图、或不确定是不是频繁子图，若判定该子图是频繁子图或不是频繁子图则停止该子 图的相关运算，若判定该子图不确定是不是频繁子图则继续指定下一个检查点并根据下一 个被指定检查点覆盖的部分样本图集合重新进行判定直到所述每个检查点都被指定过，其 中，对所述最末被指定的检查点覆盖的部分样本图集合进行判定时一定不会得出不确定的 判定结果； 输出所有频繁子图。2. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的所述被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法计算所述每个子图在所述被指定检 查点覆盖的部分样本图集合中每个样本图上的期望支持度，为根据所述单个不确定图构造 重用树，为所述单个不确定图的所述被指定检查点覆盖的部分样本图集合中每个样本图中 的每条嵌入边构建反向索引，并根据所述重用树与所述反向索引分别计算所述单个不确定 图的所述被指定检查点覆盖的部分样本图集合中每个样本图的存在概率与所述每个子图 在所述被指定检查点覆盖的部分样本图集合中每个样本图上的期望支持度。3. 根据权利要求2所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图构造重用树，为从所述单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到所述单个不确定图上所有节点与嵌入边的二叉树形式均被重 用树包括。4. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图枚举出所述单个不确定图的所有子图包括： 从所述单个不确定图提取出多个蕴含图，所述每个蕴含图都是所述单个不确定图可能 的存在方式； 分别计算所述每个蕴含图所包含的所有子图。5. 根据权利要求4所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，所述提取出多个蕴含图的个数为2的所述单个不确定图中边的个数次幂。6. 根据权利要求5所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在所述单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，所述样本图的数量与任一子图在 所述单个不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成 反比，与误差系数的平方成反比，与支持度阈值的平方成反比。7. 根据权利要求6所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的所述被指定检查点覆盖的部分样本 图集合中每个样本图的存在概率，并使用计算重用方法所述每个子图在所述被指定检查点 覆盖的部分样本图集合中每个样本图上的期望支持度包括： 根据所述单个不确定图中每条边的概率，计算出所述每个蕴含图的存在概率； 指定所述单个不确定图的所有子图中的一个； 分别计算所述被指定的子图在所述被指定检查点覆盖的部分样本图集合中每个样本 图上的支持度； 根据所述每个样本图的存在概率、所述被指定的子图在每个样本图上的支持度，计算 所述被指定的子图在所述被指定检查点覆盖的部分样本图集合中每个样本图的支持度； 继续从所述单个不确定图中指定下一个子图并计算其在所述被指定检查点覆盖的部 分样本图集合中每个样本图上的支持度，直到所述单个不确定图的所有子图都被指定； 根据所述每个子图在所述被指定检查点覆盖的部分样本图集合中每个样本图上的支 持度，计算所述每个子图在所述单个不确定图上的期望支持度。8. 根据权利要求7中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，分别计算所述被指定的子图在所述被指定检查点覆盖的部分样本图集合中每个样 本图上的支持度，为使用最大独立集法计算所述被指定的子图在所述被指定检查点覆盖的 部分样本图集合中每个样本图上的基于最小像的支持度。9. 根据权利要求8中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，根据所述每个子图在所述被指定检查点覆盖的部分样本图集合中每个样本图上的 期望支持度与所述单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是 频繁子图、或不确定是不是频繁子图包括： 获取期望支持度阈值； 根据所述单个不确定图的每个样本图的存在概率，计算所述子图在所有支持度等于一 恒定值的蕴含图上的聚合概率； 根据所述子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算所述子图在所 述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率； 根据所述子图在所述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚 合概率，计算当前概率观察值与结果区间； 根据所述结果区间与期望支持度阈值判定所述子图是否为频繁子图，将所有结果区 间上限大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的 子图判定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子 图，将所有结果区间上限大于期望支持度阈值、且结果区间下限小于期望支持度阈值与非 误差系数的乘积的子图判定为不确定是不是频繁子图。
【专利摘要】本发明公开了一种针对单个不确定图的频繁子图挖掘与优化方法，包括：获取单个不确定图；枚举出单个不确定图的所有子图；指定部分蕴含图为样本图；多个检查点将样本图集合分割为多个部分样本图集合，并依次指定每个检查点；使用计算重用方法分别计算单个不确定图的被指定检查点覆盖的部分样本图集合中每个样本图的存在概率，并使用计算重用方法计算每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期望支持度；根据每个子图在被指定检查点覆盖的部分样本图集合中每个样本图上的期望支持度与单个不确定图的每个样本图的存在概率，判定该子图是频繁子图、不是频繁子图、或不确定是不是频繁子图；输出所有频繁子图。
【IPC分类】G06T7/00
【公开号】CN104899885
【申请号】CN201510299659
【发明人】赵翔, 陈一帆, 胡艳丽, 汤大权
【申请人】中国人民解放军国防科学技术大学
【公开日】2015年9月9日
【申请日】2015年6月3日
最新回复(0)