一种针对单个不确定图的频繁子图挖掘与优化方法
一种针对单个不确定图的频繁子图挖掘与优化方法
【技术领域】
[0001] 本发明涉及图挖掘技术，特别地，涉及一种针对单个不确定图的频繁子图挖掘与 优化方法。
【背景技术】
[0002] 不确定性在现实应用中，无论是对内源还是外源，都是一种固有的属性。例如，在 一个合作社交网络中，利用目前掌握的信息，我们未必能明确断言比尔和马修两人具有很 好的合作关系，通常我们使用概率来衡量这种合作关系的可能性。假设这种关系存在的概 率为p，P的值由本领域专家通过可用信息人工确定，或者由信息抽取或生成规则自动产 生。在大数据时代的今天，对于管理不确定数据有更为强烈的需求，因此目前出现了各种质 量不一的数据。特别地，我们专注于不确定图，尤其是图的边上具有存在概率的不确定图。 不确定图模型具有广泛的应用领域，除了社会网络，不确定图模型还被应用于通信网络，无 线传感器网络，蛋白质交互网络以及生物学中的调控网络等。
[0003]另一方面，频繁模式挖掘作为数据挖掘领域高度关注的主题，一直持续了近十年， 相关研宄也取得了长足的进展，其中频繁子图引起了特别的研宄兴趣。所谓频繁子图是指 从多个小确定图的集合或者单个大确定图中发现的支持度不小于用户给定阈值的子图。频 繁子图再刻画确定图的数据特征、分类、聚类以及建立索引方面具有重要作用。
[0004] 虽然目前对于频繁子图及其在确定图上挖掘的方法已经具有很好的理解，但在不 确定图上，这一问题变得更加有趣但也更少被研宄。一个不确定图时特殊的边加权图，其中 每条边（U，V)上的权重是其存在的概率。最近，研宄工作致力于在多个小的不确定图的图 集上挖掘频繁子图。但是，该问题在单个大型不确定图中虽然同等重要，因为现实生活中的 大型网络越来越多地出现了不确定性一一比如，在社会网络中一个人对另一个人的影响是 具有概率的；在生物网络中的蛋白质交互情况也有一定测量误差一一但现有技术在本方面 是一片空白。
[0005] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 目前尚缺乏有效的解决方案。
【发明内容】
[0006] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 本发明的目的在于提出一种针对单个不确定图的频繁子图挖掘与优化方法，能允许针对单 个不确定图进行频繁子图挖掘并优化挖掘算法，填补了本领域的技术空白。
[0007] 基于上述目的，本发明提供的技术方案如下：
[0008] 根据本发明的一个方面，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法，包括：
[0009] 获取单个不确定图；
[0010] 根据单个不确定图枚举出单个不确定图的所有子图；
[0011] 在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0012] 使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使用计算 重用方法计算每个子图在单个不确定图的样本图上的期望支持度；
[0013] 根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的每个 样本图的存在概率，判定该子图是否为频繁子图；
[0014] 输出所有频繁子图。
[0015] 其中，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度，为根据单个不确 定图构造重用树，为单个不确定图的每个样本图中的每条嵌入边构建反向索引，并根据重 用树与反向索引分别计算单个不确定图的每个样本图的存在概率与每个子图在单个不确 定图的样本图上的期望支持度。
[0016] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0017] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0018] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0019] 分别计算每个蕴含图所包含的所有子图。
[0020] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0021] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0022] 并且，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法每个子图在单个不确定图的样本图上的期望支持度包括：
[0023] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0024] 指定单个不确定图的所有子图中的一个；
[0025] 分别计算被指定的子图在每个样本图上的支持度；
[0026] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在每个样本图的支持度；
[0027] 继续从单个不确定图中指定下一个子图并计算其在每个样本图上的支持度，直到 单个不确定图的所有子图都被指定；
[0028] 根据每个子图在每个样本图上的支持度，计算每个子图在单个不确定图上的期望 支持度。
[0029] 并且，分别计算被指定的子图在每个样本图上的支持度，为使用最大独立集法计 算被指定的子图在每个样本图上的基于最小像的支持度。
[0030] 并且，根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的 每个样本图的存在概率，判定该子图是否为频繁子图包括：
[0031] 获取期望支持度阈值；
[0032]根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0033] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0034]根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0035]根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图。 [0036] 从上面所述可以看出，本发明提供的技术方案通过将单个不确定图划分为多个蕴 含的确定图并将蕴含图视作确定图使用计算重用方法抽样计算子图的期望支持度的手段， 能在单个不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
【附图说明】
[0037]为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所 需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施 例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获 得其他的附图。
[0038] 图1为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 的流程图；
[0039] 图2为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图、确定图与子图的一个实施例；
[0040] 图3为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，根据布尔表达式获得的单个不确定图及其子图的一个实施例；
[0041]图4为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图的两个样本图及其重用树的一个实施例。
【具体实施方式】
[0042] 为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明实施例中 的附图，对本发明实施例中的技术方案进一步进行清 楚、完整、详细地描述，显然，所描述的 实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域 普通技术人员所获得的所有其他实施例，都属于本发明保护的范围。
[0043] -个确定图G是一个元组（VpE^le，2e)，其中，是节点集合，
是 边的集合，1<^屮^是为节点和边赋予标签的函数。IVJ和lEj分别表示G中节 点和边的数量。为了描述简便，我们假设图是无向的，且没有自循环和多重边。但是，本方 法可以很容易的被拓展到具有多重边的有向图。
[0044] 如果存在单射f:Vg-V洞时满足以下两个条件：
[0045]
[0047] 我们就用gGG表示一个子图g同构于确定图G。我们称g是G的子图，G是g 的超图，f(g)是g在G中的一个嵌入。如果g是g'的直接超图，那么g￡g',且|Eg| = |Eg, |+1。直接超图是指仅比子图多一条边的超图。
[0048] 对于gG G，以及支持度阈值T，假设存在一个函数来衡量g在G中的支持度，那 么最直接的想法是计算g在G中的同构次数。然而，该支持度计算方法不具有反单调性。反 单调性对于开发能够有效剪枝搜索空间的算法是十分关键的，如果没有此性质，则不得在 整个空间进行穷举搜索。因此，目前的研宄提出了很多具有反单调性的支持度计算法方法， 包括最小映射法（MI)，有害重叠法（H0)，以及最大独立集法（MIS)。这些计算方法都是基于 子图同构，但对延生的重叠兼容性有所不同，而导致计算复杂度不同。特别的，MI是唯一一 个可以高效计算的方法，而H0和MIS都涉及解决NP完全的问题；MI得到的结果是H0/MIS 得到结果的超集，因此，其结果可以从MI的结果通过进一步计算得到。因此，接下来我们使 用MI作为支持度计算的标准，然而算法只需要简单改变即可拓展到另外两种计算方法。 [0049] 考虑从g到G的一个子图同构集合F= {f}。F(v)表示|v' }，其中对于每个 ，，存在映射f?将vGVg映射到V' 。基于最小像的支持度表示为sup(g,G)=
，下文中"支持度"是"基于最小像的支持度"的缩写。
[0050] 图2示出了确定图G和子图g，该图建模了合作社交网络，其中节点表示人，边表示 合作关系。每个人的研宄领域作为标签，即Bio表示生物学家；为了图示的清晰，边的标签 被省略了。容易发现在g和G之间有三个同构，分别是（Upu2)到（v^v2)，（v3,v2)和（v3， v4)。结果是sup(g，G) =min{2,2} =2。
[0051] 虽然在确定图上子图的重要性由支持度进行衡量，但此概念在不确定图上没有意 义，因为图结构中存在概率，包含关系变得模糊或者不确定.现有的工作在多个小的不确 定图的图集上定义了期望支持度，该定义计算不确定图来自所蕴含的确定图中支持度的贡 献，只要当前子图被包含了一次.扩展此概念，我们定义单个大的不确定图上期望支持度 为在所有可能图上支持度的聚合值，即支持度在所有由不确定图蕴含的确定图上的概率分 布.子图超过一个给定阈值被认为是频繁的.由于定义的偏移，目前在多个小不确定图的 图集上的算法不再适用于单个不确定图.我们提出了一个高效的具有精度保证的解决方 案，解决了基于边的概率和基于点的支持度计算。
[0052] 根据本发明的实施例，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法。
[0053] 如图1所示，根据本发明的实施例提供的针对单个不确定图的频繁子图挖掘与优 化方法包括：
[0054] 步骤S101，获取单个不确定图；
[0055] 步骤S103,根据单个不确定图枚举出单个不确定图的所有子图；
[0056] 步骤S105,在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0057] 步骤S107,使用计算重用方法分别计算单个不确定图的每个样本图的存在概率， 并使用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度；
[0058] 步骤S109,根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定 图的每个样本图的存在概率，判定该子图是否为频繁子图；
[0059]步骤S111，输出所有频繁子图。
[0060] 其中，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度，为根据单个不确 定图构造重用树，为单个不确定图的每个样本图中的每条嵌入边构建反向索引，并根据重 用树与反向索引分别计算单个不确定图的每个样本图的存在概率与每个子图在单个不确 定图的样本图上的期望支持度。
[0061] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0062] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0063] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0064] 分别计算每个蕴含图所包含的所有子图。
[0065] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0066] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0067] 并且，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法每个子图在单个不确定图的样本图上的期望支持度包括：
[0068] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0069] 指定单个不确定图的所有子图中的一个；
[0070] 分别计算被指定的子图在每个样本图上的支持度；
[0071] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在每个样本图的支持度；
[0072] 继续从单个不确定图中指定下一个子图并计算其在每个样本图上的支持度，直到 单个不确定图的所有子图都被指定；
[0073] 根据每个子图在每个样本图上的支持度，计算每个子图在单个不确定图上的期望 支持度。
[0074] 并且，分别计算被指定的子图在每个样本图上的支持度，为使用最大独立集法计 算被指定的子图在每个样本图上的基于最小像的支持度。
[0075] 并且，根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的 每个样本图的存在概率，判定该子图是否为频繁子图包括：
[0076] 获取期望支持度阈值；
[0077] 根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0078] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0079] 根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0080] 根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图。
[0081] 下面根据具体实施例进一步阐述本发明的技术方案。
[0082] 一个不确定图是一个元组Gu= (G，P)，其中G是一个确定图，P(0，1是一个 概率函数，将每条边e映射为一个存在概率，由Pe表示，eGEG。G是主干图。
[0083] 一旦确定了每条边的存在情况，由Gu可以蕴含得到确定图GS称为蕴含图。因此 一个不确定图Gu总共蕴含21 &1可能的确定图，每个蕴含图都是Gu可能的存在方式。
[0084] 我们考虑的模型假设边之间的存在概率是相互独立的，这种模型有很多实际的应 用，那么，Gu蕴含G1的概率，或者G1的存在概率，可以通过包括或不包括边来计算：
[0086] 既然经典的关于支持度的概率在不确定图上变得很有意义，我们求助于期望支持 度，即在蕴含图上的概率分布情况。
[0087] 我们将子图g在不确定图Gu上的期望支持度定义为：
[0089] 其中，以是6"的蕴含图。给定期望支持度阈值〇,子图g如果是频繁的，那么g在 Gu中的期望支持度将不小于阈值，即eSUp(g，Gu)彡〇。
[0090] 对每个Gu的蕴含图G\
，esup(g，G1) <esup(g'，G1)。不等式在对 i进行求和后仍然成立。因此，esup(g，Gu)彡eSUp(g'，GU)，期望支持度是反单调的。 [0091] 在图2中，我们为G的每条边赋予一个存在概率并构造一个不确定图Gu，其中 存在概率建模两个人合作关系的紧密程度。此时，G是主干图，同时Gu有8个蕴含图，
。我们在上文中已经计算出sup(g，G) =2,因
。照此将所有来自蕴含图的值聚合起来，可以计算出esup(g，Gu) = 1. 12。如果给定的支持度阈值〇 = 1，则esup(g，Gu)彡1，g是频繁子图。
[0092] 给定一个不确定图Gu= (G，P)和一个期望支持度阈值〇，单个不确定 图上频繁子图挖掘问题是指发现所有期望支持度不小于给定阈值的子图g，即
[0093] 我们在期望支持度的定义中给出了频繁子图的语义。假设sup(g，Gu) = 10,4表 示一个随机独立选择的蕴含图，那么我们有理由期望g在4中至少有10次不重复的出现。 根据现有的分析，基于期望语义的频繁子图适合于在不确定图中进行主题发现。当不存在 二义性时，在后文中省略领域Gu，即表示为sup(g)。
[0094] 我们提出了一个枚举一评价的算法，取名为fanta(frequentsubgraphminingon uncertaingraphs)。fanta算法先枚举所有可能的候选子图，再对每个子图计算期望支持 度，然后决定是否将其作为结果输出。任何利用了Apriori性质的枚举策略都可以使用。 Apriori性质陈述的是，不频繁子图的超图也不可能是频繁的。特别地，不确定图中所有子 图可以被组织为一个有根的有向无环图（DAG)，其中节点代表候选子图（根表示为空KDAG 中从g'到g的一条弧表示g'是g的直接超图。我们从频繁的边开始，每次将一条新的边 加到频繁子图中，枚举所有可能子图，因此可以在DAG的第n层找到包含n条边的子图。为 了避免重复枚举同时保证完备性，我们使用方法gSpan给每个子图增加了词典顺序。
[0095] 然而，通过比较期望支持度和阈值，决定一个被枚举出的子图是否是频繁的，其最 简单的方式是产生所有蕴含图，计算并聚合子图在所有蕴含图上的支持度，得到期望支持 度，再与支持度阈值进行比较。但这种方法因为会产生大量蕴含图，加上支持度计算的高复 杂度，因此对终端用户而言是不可接受的。为了达到更好的运行性能，我们尝试所有可能， 在可接受时间内返回结果。
[0096] 我们已经发现，使用定义计算期望支持度复杂度相当高，因为Gu存在2141个蕴含 图。对每个候选子图，我们需要计算在指数级的确定图上计算其支持度，其中频繁涉及具有 高昂时间代价的子图同构检测。我们研宄这一问题并通过一个高效的算法来降低计算复杂 度。
[0097] 我们首先用另一种方式给出期望支持度的计算。假设P(sup(g) =j)表示子图g 在所有支持度等于j的蕴含图上的聚合概率，即
[0099] 其中，Aj(g) = {G'lsupCg，G1) =j}。
[0100] 因此有
[0102] 其中，Ms=sup(g，G)是g在Gu所有蕴含图中最大的支持度。
[0103] 我们进一步定义，Pj(g)为g在Gu的蕴含图中支持度不小于j的聚合概率，SP
[0105]其中，Aj(g) = {G'lsupCg，G1)彡j}。
[0106] 同时，对esup(g)公式右端展开可得
[0108] 因此又有
[0110] 我们还注意到P」(g)的两个性质：（l)P」(g)彡P」(g')，其中，gGg;⑵Pj(g) ^Pjr (g)，其中，1 <j' <j。
[0111] 我们可以证明，计算1\化)是#P难的，其中q是一个整型常数。可以将DNF计数问 题在多项式时间内归约为此问题，以此证明该问题是#P难的。
[0112] 考虑一个析取范式的一阶逻辑表达式（DNF)D=QVC2V~VCtCjiG[l，m]) 的形式为1，12八…八lk，其中，l」(je[l，k])是{Xl，x2，…，xn}中的布尔变量。DNF计 数问题是计算有多少种对变量的赋值可以满足D。设P(Xi)表示Xi被赋值为真的概率，P(D) 是随机一组对变量的赋值满足D的概率，给定一个前述实例，下面构造了在Gu中计算Pq(g) 的问题。
[0113] 我们构造一个不确定图Gu，其节点集合为ViUV2UV3，其中：
[0117] 其中，V#节点的标签为a，V2UV3中为0。边的构造方法如下：
[oils] ⑴在i
|之间增加一条边，ie[lj-1]，jg[i，k]，存在概率为 i；
[0119] (2)如果D中Xi包含在C冲，则在（ci，11」）增加一条概率为1的边；
[0120] (3)对每个xf{x^x2, . . .，xn}，在(X，vD之间增加概率为P(Xi)的一条边，所 有Gu的边标签为y。
[0121] 两个问题之间的关联性为：
[0122] 每个对{Xi，x2，…，xn}的真值赋值JT一对一对应于Gu的一个蕴含图GS即边（Up Vi)存在当且仅当\赋值为真，每个真值赋值31的概率等于
。显然，在所有蕴 含图以中
。因此，如果一个真值赋值满足D，当且仅当g在蕴含图 6"中的支持度超过。因此
[0123] 综上可知，计算Pjg)是一个#P难问题。类似地，可以证明计算esup(g)也是#P 难的。
[0124] 图3示出的是布尔表达式D按照上述构造方法，得到的不确定图Gu和子图g，其中， D= (X,X2八X3)V(X2AX3八X4)，Xpx2,x3,x4被赋值为真的概率分别是P(xD，P(x2)， P(x3)，P(x4)〇
[0125] 由于计算子图支持度问题具有#?难的时间复杂度，我们提出了一个近似评价算 法，其误差为e。作为近似算法，理想的结果是能够返回所有频繁的子图（真正）；为了满 足这一要求，则结果集中也会有不频繁的子图（假正）。根据这一目的，我们输出一个闭区 间「esup,esup]， 该区间包含esup真实值，然后对于子图g的支持度与支持度阈值〇之间 关系的以下不同情况进行处理：
[0126]Case1:如果
，不输出g，因为esup(g) <〇是确定的；
[0127]Case2:如果esup(g) ^ (1_e) 〇 且
，则输出g，因为 esup(g)彡（1-e) 〇是肯定的，而且很有可能esup(g)彡〇;
[0128]Case3:如果i
冃.esup(g)<(卜e)o，则不能决定是否输出g，因为 我们不能决定是否esup(g)彡〇或者esup(g) < (1-e) 〇。
[0129]Case3并不是我们想要的，因为Case3我们无法决定。然而，我们观察到如果区 间「esup,?^n^l的宽度在e0范围内，则Case3不会出现。因此，通过限制区间宽度最大 为e〇，则通过「esup,万1来估计esup是足够的，因为此时只有Case1和Case2会出 现。这对于算法设计很重要，我们的算法依赖此来决定是否将g作为结果输出。
[0130] 我们的近似算法基于蒙特卡洛方法。通过
，我们首先计 算P」(g)的近似值， 其中，je[1，MJ;然后聚合该值得到区间[^^(g),^Ip(g)]。为了 保证区间不会大于e〇，我们要求每个Pj(g)近似值的绝对误差不会超过eo/Ms。此要求 来自一类随机算法一一随机近似模式，可以提供精度保证。
[0131] 给定一个置信系数Se[0，1]，以及一个绝对误差范围e '，我们可以使用由随 机近似模式得到的近似值p来估计P，如果PCIP-PI< :) 2 1 -S,其中，1-S是置信程 度。为了在S和e'的条件下近似得到Pj(g)，我们依靠一个基于霍夫丁不等式的算法。
[0132] 假设Xi，X2，…，Xn是独立同分布的伯努利随机变量，其中Xi= 1的概率为P，则有 下述不等式成立：
[0134] n个样本观察值的平均可以提供一个具有精度保证关于p的近似，为提供置信度 1-S和绝对误差e' =e o/2Ms需要的样本量大小为：
[0136]算法1为评价一个子图的过程的封装。输入一个子图g，不确定图Gu误差系数e以及实数S;输出一个布尔值，表示g是否是频繁的。
[0138] 算法第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评价支持度 的近似值.
[0139] 函数EvaluateSup工作流程为：输入Pj(g)的观察概率值P[j]、整数X， 并输出Case 1或者Case 2 (Case 3不应该出现）。特别地，当前概率观察值
，输出结果在，
之间。 根据区间与支持度阈值0之间的关系作出决定。
[0140]
丨证明，只要样本量足够，所有输出 子图满足给定误差范围，算法1就是正确的。另一方面，由于在子图g增长的过程中存储 了其嵌入（embedding)，可以在0(|F(g) | |Vg|)的时间复杂度下计算Ms，其中F(g)是g嵌 入（embedding)的集合；接着，我们执行蒙特卡洛仿真，计算支持度和概率的复杂度分别为 〇(|F(g) | |Vg|)和0(|Eg|)。因为总的抽样样本数量复杂度不超过
，则 算法1的总复杂度是
。既然时间复杂度是关于
的多项 式级，算法1属于完全多项式随机近似模式（FPRAS)，该模式可以同时提供高效性和高准确 度。
[0141] 实现基于蒙特卡洛支持度评价的一种直观方式是在每个样本图中计算子图的支 持度，并聚合观察概率。这种方式会比较耗时，因此我们考虑可能的加速方法。
[0142]图4示出的是图2中不确定图Gu的两个样本图G'和G"，以及G'和G"的重用树 "DM_Bio"。首先，在计算
丨后。我们可以进一步考虑边03来计算
另外。如果一个P的嵌入（embedding)存在于G"中，我们可以确定G'也包含了此嵌入而 不需要额外的计算。最后，为了算出sup(p，G")，我们构造了一个数据结构：
[0144] 可增加一个新的列（v3_v4)，用于计算sup(p，G')。
[0145]对于图4中的两个样本图G" □G'，存在三种可以重用的计算：
[0146] (1)计算样本图的存在概率；
[0147] (2)测试一个嵌入是否存在；
[0148] (3)计算支持度。
[0149] 我们可以将此计算重用的思想泛化到多个样本图的情况，此时，样本图之间的包 含关系并不需要满足。
[0150] 对于第（1)种和第（2)种计算，我们首先要构造一个二叉重用树，其中所有样本图 都是树的叶节点。假设嵌入边有一种关于其ID的线性顺序，则可以得到传统的树的结构。 二叉树的深度为I ，在深度为i的所有分支决定于是否包含边％。换言之，根的深度为 1，其左分支h是一棵包含有e:这条边所有样本图的子树的根，而右分支i包含剩下的不 含4这条边所有样本图子树的根。这个分支过程从~到em中最后一条边，最终得到2l'l 叶节点。因此我们可以在叶节点为每个样本图找到一个对应的位置。
[0151] 我们不需要产生整棵树。我们每计算了一个样本图，就存储包含此样本图的一个 分支。我们采用如下方法产生样本图，并构造整个树：在根节点，对每个样本图h，我们随 机决定它是去左分支h还是右分支np左分支、右分支分别由left边和right边连接。接 着，如果^不为空，则将n1在树上保存下来，接着，随机决定样本图的去向；如果ni是空，则 停止此分支继续增长。对于~也是同样的处理过程，当所有的样本图都到达叶节点时，整 个迭代过程结束。在增长过程中，每个样本图的存在概率在增长过程中作为一个副产品计 算得到，同时计算重用达到最大。
[0152] 之后，我们计算每个样本图的支持度。第一步是决定每个样本图包含的嵌入 (embedding)。为此，我们对每条嵌入边维护一个反向索引，每条嵌入边作为一个条目，那些 包含这条边的嵌入（embedding)作为对应的记录。该索引便于发现那些因为不存在嵌入边 而缺少的嵌入，而该索引在主干图上计算支持度时建立，且开销较小。根据重用树的构造， 进入右分支意味着一条边e不存在，因此包含这条边的嵌入也不存在；而进入左分支并不 影响嵌入集合。
[0153] 对于一个样本图，我们从叶节点追踪到根节点，并记录下经过的right边。整个嵌 入集合减去那些一路上遇到的right边对应的嵌入即为考虑的样本图。另外，为了能计算 重用，我们在处理每个样本图时，都会记录树节点上的中间结果。接着，我们从最低父节点 开始，增量式地进行计算，即从叶节点到根节点路径上第一个已经被处理过的节点开始，而 不是从根节点开始。
[0154] 在图4示出的实施例中，右边的树是从G'和G"构造的部分重用树，其中ni是根， n4(或者n5)是叶节点，对应G'(或者G")。在处理完G'后，我们在节点n3有嵌入集合 {Vi-VyV3-V2,V3-V4}，该集合可以包含于任意在此分支后的样本图。接着，由于不存在边e3， 我们从反向索引上获取到那些不再包含的嵌入，即Iv3-v4}。然后我们将其删除，得到G"包 含的嵌入集合IvfVyV3-V2}。
[0155]接下来，我们以串行的方式进行第（3)种计算的重用。对于两个样本图G'和G"， 我们首先描述怎样计算sup(g，G')。对每个包含在G'中的嵌入，我们将其对应的点排成 一行行。注意到由于我们已经获得了同构映射，因此该操作比一般情况要简单和迅速得多。 特别地，对于一个点vg，我们利用一个映射来记录一一G'中每个嵌入点作为键，该点在所 有嵌入中出现次数作为其值。当我们遇到一个嵌入以u作为^嵌入点时，则对u对应于vg 在映射中的值增加1。在对所有嵌入中的节点进行计数后，我们可以通过获取所有映射中最 小集合的值，得到sup(g，G')。
[0156] 为了在计算G"时重用之前的中间结果，而不是从头开始建立这些映射，我们首先 去除掉不包含在G"中的嵌入，减少其在映射中对应的值，然后增加之前没有包含在G'中 的嵌入，并增加对应的值。之后，我们可以得到sup(g，G")。
[0157] 对增加或减少一个单位的开销进行建模，固定为c ;获取最小映射的集合大小的 开销为c'。给定一系列样本图匕，每个包含一个嵌入的集合Fi G F，其中i e [l，N]，从头 开始计算支持度的开销为iFil.c+c'。 我们定义：
[0159]从Gi (或Gj)到Gj (或GD，支持度计算的开销是
，并
?则对于h，从头开始计算开销更小。为了最大化计算重用，我 们将此问题进行形式化地描述如下：
[0160] 给定一系列样本图GiGD，每个包含一个嵌入的集合FiGF，其中，ie[1，N]， 从匕到h的计算开销为
，找到一个计算序列使得开销最小，满足每个 图只被处理过一次。
[0161] 该问题是NP难的。我们为每个样本图构造一个比特数组，每个比特对应一个F中 的嵌入，即数组的维度为|F|。如果样本图包含该对应的嵌入，则比特位设为1，相反则设为 0。这种情况下，两个图之间的开销可以通过计算二进制串之间的汉民距离比较容易获得。 接着我们使用一种启发式的计算序列一一从左到右对应样本图在叶节点的位置。直观的想 法是两个连续叶节点（如图4中的G'和G")，通常距离较小，因此增量计算复杂度相对 小。
[0162] 我们使用算法2将所有3中重用计算集合在一起如下：
[0164] 为了将算法2整合到基本算法中，我们可以将算法1中第4-8行替换为 "P-ShareCompTree(g，Q) "，使得算法2在基本算法中生效，修改后的算法1可以执行基 于计算重用的子图判定。
[0165] 综上所述，为获得不仅频繁，而且在现实中具有高置信度的子图，我们定义了在单 个不确定图上，基于期望支持度的频繁子图挖掘问题，基于期望语义的支持度对于在不确 定网络中主题发现很有用。为了说明此问题的高复杂度，通过将DNF计数问题归约为此问 题，我们证明了计算子图期望支持度是#?难的，我们提出了一种基于蒙特卡洛的近似算 法来获取一个区间，并以给定精确度包含真实值，将获取的支持度区间与支持度阈值之间 的关系分为三种情况，可以保证，以概率至少为1-8,任何子图支持度不小于〇的子图都 会被输出，同时任何期望支持度小于（l-e)〇的子图都不会输出。此分类确定了我们枚 举-评价的算法框架，即慎重地枚举候选子图并逐一评价；同时，我们对抽取样本中可重用 的计算进行共享，通过在线建立的二叉共享树进行计算重用，大幅度减少了子图挖掘消耗 的时间。借助于本发明的上述技术方案，通过将单个不确定图划分为多个蕴含的确定图并 将蕴含图视作确定图使用计算重用方法抽样计算子图的期望支持度的手段，我们能在单个 不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
[0166] 所属领域的普通技术人员应当理解：以上所述仅为本发明的具体实施例而已，并 不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。
【主权项】
1. 一种针对单个不确定图的频繁子图挖掘与优化方法，其特征在于，包括： 获取单个不确定图； 根据所述单个不确定图枚举出所述单个不确定图的所有子图； 在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图； 使用计算重用方法分别计算所述单个不确定图的每个样本图的存在概率，并使用计算 重用方法计算所述每个子图在所述单个不确定图的样本图上的期望支持度； 根据所述每个子图在所述单个不确定图的样本图上的期望支持度与所述单个不确定 图的每个样本图的存在概率，判定该子图是否为频繁子图； 输出所有频繁子图。2. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的每个样本图的存在概率，并使用计 算重用方法计算所述每个子图在所述单个不确定图的样本图上的期望支持度，为根据所述 单个不确定图构造重用树，为所述单个不确定图的每个样本图中的每条嵌入边构建反向索 弓丨，并根据所述重用树与所述反向索引分别计算所述单个不确定图的每个样本图的存在概 率与所述每个子图在所述单个不确定图的样本图上的期望支持度。3. 根据权利要求2所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图构造重用树，为从所述单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到所述单个不确定图上所有节点与嵌入边的二叉树形式均被重 用树包括。4. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图枚举出所述单个不确定图的所有子图包括： 从所述单个不确定图提取出多个蕴含图，所述每个蕴含图都是所述单个不确定图可能 的存在方式； 分别计算所述每个蕴含图所包含的所有子图。5. 根据权利要求4所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，所述提取出多个蕴含图的个数为2的所述单个不确定图中边的个数次幂。6. 根据权利要求5所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在所述单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，所述样本图的数量与任一子图在 所述单个不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成 反比，与误差系数的平方成反比，与支持度阈值的平方成反比。7. 根据权利要求6所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的每个样本图的存在概率，并使用计 算重用方法所述每个子图在所述单个不确定图的样本图上的期望支持度包括： 根据所述单个不确定图中每条边的概率，计算出所述每个蕴含图的存在概率； 指定所述单个不确定图的所有子图中的一个； 分别计算所述被指定的子图在每个样本图上的支持度； 根据所述每个样本图的存在概率、所述被指定的子图在每个样本图上的支持度，计算 所述被指定的子图在每个样本图的支持度； 继续从所述单个不确定图中指定下一个子图并计算其在每个样本图上的支持度，直到 所述单个不确定图的所有子图都被指定； 根据所述每个子图在每个样本图上的支持度，计算所述每个子图在所述单个不确定图 上的期望支持度。8. 根据权利要求7中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，分别计算所述被指定的子图在每个样本图上的支持度，为使用最大独立集法计算 所述被指定的子图在每个样本图上的基于最小像的支持度。9. 根据权利要求8中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，根据所述每个子图在所述单个不确定图的样本图上的期望支持度与所述单个不确 定图的每个样本图的存在概率，判定该子图是否为频繁子图包括： 获取期望支持度阈值； 根据所述单个不确定图的每个样本图的存在概率，计算所述子图在所有支持度等于一 恒定值的蕴含图上的聚合概率； 根据所述子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算所述子图在所 述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率； 根据所述子图在所述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚 合概率，计算当前概率观察值与结果区间； 根据所述结果区间与期望支持度阈值判定所述子图是否为频繁子图，将所有结果区 间上限大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的 子图判定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子 图。
【专利摘要】本发明公开了一种针对单个不确定图的频繁子图挖掘与优化方法，包括：获取单个不确定图；根据单个不确定图枚举出单个不确定图的所有子图；在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度；根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的每个样本图的存在概率，判定该子图是否为频繁子图；输出所有频繁子图。
【IPC分类】G06F17/30
【公开号】CN104899283
【申请号】CN201510296077
【发明人】唐九阳, 赵翔, 陈一帆, 李瑞琪
【申请人】中国人民解放军国防科学技术大学
【公开日】2015年9月9日
【申请日】2015年6月2日
【技术领域】
[0001] 本发明涉及图挖掘技术，特别地，涉及一种针对单个不确定图的频繁子图挖掘与 优化方法。
【背景技术】
[0002] 不确定性在现实应用中，无论是对内源还是外源，都是一种固有的属性。例如，在 一个合作社交网络中，利用目前掌握的信息，我们未必能明确断言比尔和马修两人具有很 好的合作关系，通常我们使用概率来衡量这种合作关系的可能性。假设这种关系存在的概 率为p，P的值由本领域专家通过可用信息人工确定，或者由信息抽取或生成规则自动产 生。在大数据时代的今天，对于管理不确定数据有更为强烈的需求，因此目前出现了各种质 量不一的数据。特别地，我们专注于不确定图，尤其是图的边上具有存在概率的不确定图。 不确定图模型具有广泛的应用领域，除了社会网络，不确定图模型还被应用于通信网络，无 线传感器网络，蛋白质交互网络以及生物学中的调控网络等。
[0003]另一方面，频繁模式挖掘作为数据挖掘领域高度关注的主题，一直持续了近十年， 相关研宄也取得了长足的进展，其中频繁子图引起了特别的研宄兴趣。所谓频繁子图是指 从多个小确定图的集合或者单个大确定图中发现的支持度不小于用户给定阈值的子图。频 繁子图再刻画确定图的数据特征、分类、聚类以及建立索引方面具有重要作用。
[0004] 虽然目前对于频繁子图及其在确定图上挖掘的方法已经具有很好的理解，但在不 确定图上，这一问题变得更加有趣但也更少被研宄。一个不确定图时特殊的边加权图，其中 每条边（U，V)上的权重是其存在的概率。最近，研宄工作致力于在多个小的不确定图的图 集上挖掘频繁子图。但是，该问题在单个大型不确定图中虽然同等重要，因为现实生活中的 大型网络越来越多地出现了不确定性一一比如，在社会网络中一个人对另一个人的影响是 具有概率的；在生物网络中的蛋白质交互情况也有一定测量误差一一但现有技术在本方面 是一片空白。
[0005] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 目前尚缺乏有效的解决方案。
【发明内容】
[0006] 针对现有技术中缺乏针对单个不确定图的频繁子图挖掘与优化技术方案的问题， 本发明的目的在于提出一种针对单个不确定图的频繁子图挖掘与优化方法，能允许针对单 个不确定图进行频繁子图挖掘并优化挖掘算法，填补了本领域的技术空白。
[0007] 基于上述目的，本发明提供的技术方案如下：
[0008] 根据本发明的一个方面，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法，包括：
[0009] 获取单个不确定图；
[0010] 根据单个不确定图枚举出单个不确定图的所有子图；
[0011] 在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0012] 使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使用计算 重用方法计算每个子图在单个不确定图的样本图上的期望支持度；
[0013] 根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的每个 样本图的存在概率，判定该子图是否为频繁子图；
[0014] 输出所有频繁子图。
[0015] 其中，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度，为根据单个不确 定图构造重用树，为单个不确定图的每个样本图中的每条嵌入边构建反向索引，并根据重 用树与反向索引分别计算单个不确定图的每个样本图的存在概率与每个子图在单个不确 定图的样本图上的期望支持度。
[0016] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0017] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0018] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0019] 分别计算每个蕴含图所包含的所有子图。
[0020] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0021] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0022] 并且，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法每个子图在单个不确定图的样本图上的期望支持度包括：
[0023] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0024] 指定单个不确定图的所有子图中的一个；
[0025] 分别计算被指定的子图在每个样本图上的支持度；
[0026] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在每个样本图的支持度；
[0027] 继续从单个不确定图中指定下一个子图并计算其在每个样本图上的支持度，直到 单个不确定图的所有子图都被指定；
[0028] 根据每个子图在每个样本图上的支持度，计算每个子图在单个不确定图上的期望 支持度。
[0029] 并且，分别计算被指定的子图在每个样本图上的支持度，为使用最大独立集法计 算被指定的子图在每个样本图上的基于最小像的支持度。
[0030] 并且，根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的 每个样本图的存在概率，判定该子图是否为频繁子图包括：
[0031] 获取期望支持度阈值；
[0032]根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0033] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0034]根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0035]根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图。 [0036] 从上面所述可以看出，本发明提供的技术方案通过将单个不确定图划分为多个蕴 含的确定图并将蕴含图视作确定图使用计算重用方法抽样计算子图的期望支持度的手段， 能在单个不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
【附图说明】
[0037]为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所 需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施 例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获 得其他的附图。
[0038] 图1为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 的流程图；
[0039] 图2为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图、确定图与子图的一个实施例；
[0040] 图3为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，根据布尔表达式获得的单个不确定图及其子图的一个实施例；
[0041]图4为根据本发明实施例的一种针对单个不确定图的频繁子图挖掘与优化方法 中，单个不确定图的两个样本图及其重用树的一个实施例。
【具体实施方式】
[0042] 为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明实施例中 的附图，对本发明实施例中的技术方案进一步进行清 楚、完整、详细地描述，显然，所描述的 实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域 普通技术人员所获得的所有其他实施例，都属于本发明保护的范围。
[0043] -个确定图G是一个元组（VpE^le，2e)，其中，是节点集合，
是 边的集合，1<^屮^是为节点和边赋予标签的函数。IVJ和lEj分别表示G中节 点和边的数量。为了描述简便，我们假设图是无向的，且没有自循环和多重边。但是，本方 法可以很容易的被拓展到具有多重边的有向图。
[0044] 如果存在单射f:Vg-V洞时满足以下两个条件：
[0045]
[0047] 我们就用gGG表示一个子图g同构于确定图G。我们称g是G的子图，G是g 的超图，f(g)是g在G中的一个嵌入。如果g是g'的直接超图，那么g￡g',且|Eg| = |Eg, |+1。直接超图是指仅比子图多一条边的超图。
[0048] 对于gG G，以及支持度阈值T，假设存在一个函数来衡量g在G中的支持度，那 么最直接的想法是计算g在G中的同构次数。然而，该支持度计算方法不具有反单调性。反 单调性对于开发能够有效剪枝搜索空间的算法是十分关键的，如果没有此性质，则不得在 整个空间进行穷举搜索。因此，目前的研宄提出了很多具有反单调性的支持度计算法方法， 包括最小映射法（MI)，有害重叠法（H0)，以及最大独立集法（MIS)。这些计算方法都是基于 子图同构，但对延生的重叠兼容性有所不同，而导致计算复杂度不同。特别的，MI是唯一一 个可以高效计算的方法，而H0和MIS都涉及解决NP完全的问题；MI得到的结果是H0/MIS 得到结果的超集，因此，其结果可以从MI的结果通过进一步计算得到。因此，接下来我们使 用MI作为支持度计算的标准，然而算法只需要简单改变即可拓展到另外两种计算方法。 [0049] 考虑从g到G的一个子图同构集合F= {f}。F(v)表示|v' }，其中对于每个 ，，存在映射f?将vGVg映射到V' 。基于最小像的支持度表示为sup(g,G)=
，下文中"支持度"是"基于最小像的支持度"的缩写。
[0050] 图2示出了确定图G和子图g，该图建模了合作社交网络，其中节点表示人，边表示 合作关系。每个人的研宄领域作为标签，即Bio表示生物学家；为了图示的清晰，边的标签 被省略了。容易发现在g和G之间有三个同构，分别是（Upu2)到（v^v2)，（v3,v2)和（v3， v4)。结果是sup(g，G) =min{2,2} =2。
[0051] 虽然在确定图上子图的重要性由支持度进行衡量，但此概念在不确定图上没有意 义，因为图结构中存在概率，包含关系变得模糊或者不确定.现有的工作在多个小的不确 定图的图集上定义了期望支持度，该定义计算不确定图来自所蕴含的确定图中支持度的贡 献，只要当前子图被包含了一次.扩展此概念，我们定义单个大的不确定图上期望支持度 为在所有可能图上支持度的聚合值，即支持度在所有由不确定图蕴含的确定图上的概率分 布.子图超过一个给定阈值被认为是频繁的.由于定义的偏移，目前在多个小不确定图的 图集上的算法不再适用于单个不确定图.我们提出了一个高效的具有精度保证的解决方 案，解决了基于边的概率和基于点的支持度计算。
[0052] 根据本发明的实施例，提供了一种针对单个不确定图的频繁子图挖掘与优化方 法。
[0053] 如图1所示，根据本发明的实施例提供的针对单个不确定图的频繁子图挖掘与优 化方法包括：
[0054] 步骤S101，获取单个不确定图；
[0055] 步骤S103,根据单个不确定图枚举出单个不确定图的所有子图；
[0056] 步骤S105,在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；
[0057] 步骤S107,使用计算重用方法分别计算单个不确定图的每个样本图的存在概率， 并使用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度；
[0058] 步骤S109,根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定 图的每个样本图的存在概率，判定该子图是否为频繁子图；
[0059]步骤S111，输出所有频繁子图。
[0060] 其中，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度，为根据单个不确 定图构造重用树，为单个不确定图的每个样本图中的每条嵌入边构建反向索引，并根据重 用树与反向索引分别计算单个不确定图的每个样本图的存在概率与每个子图在单个不确 定图的样本图上的期望支持度。
[0061] 并且，根据单个不确定图构造重用树，为从单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到单个不确定图上所有节点与嵌入边的二叉树形式均被重用树 包括。
[0062] 另外，根据单个不确定图枚举出单个不确定图的所有子图包括：
[0063] 从单个不确定图提取出多个蕴含图，每个蕴含图都是单个不确定图可能的存在方 式；
[0064] 分别计算每个蕴含图所包含的所有子图。
[0065] 并且，提取出多个蕴含图的个数为2的单个不确定图中边的个数次幂。
[0066] 并且，在单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，样本图的数量与任一子图在单个 不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成反比，与 误差系数的平方成反比，与支持度阈值的平方成反比。
[0067] 并且，使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使 用计算重用方法每个子图在单个不确定图的样本图上的期望支持度包括：
[0068] 根据单个不确定图中每条边的概率，计算出每个蕴含图的存在概率；
[0069] 指定单个不确定图的所有子图中的一个；
[0070] 分别计算被指定的子图在每个样本图上的支持度；
[0071] 根据每个样本图的存在概率、被指定的子图在每个样本图上的支持度，计算被指 定的子图在每个样本图的支持度；
[0072] 继续从单个不确定图中指定下一个子图并计算其在每个样本图上的支持度，直到 单个不确定图的所有子图都被指定；
[0073] 根据每个子图在每个样本图上的支持度，计算每个子图在单个不确定图上的期望 支持度。
[0074] 并且，分别计算被指定的子图在每个样本图上的支持度，为使用最大独立集法计 算被指定的子图在每个样本图上的基于最小像的支持度。
[0075] 并且，根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的 每个样本图的存在概率，判定该子图是否为频繁子图包括：
[0076] 获取期望支持度阈值；
[0077] 根据单个不确定图的每个样本图的存在概率，计算子图在所有支持度等于一恒定 值的蕴含图上的聚合概率；
[0078] 根据子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算子图在单个不 确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率；
[0079] 根据子图在单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概 率，计算当前概率观察值与结果区间；
[0080] 根据结果区间与期望支持度阈值判定子图是否为频繁子图，将所有结果区间上限 大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的子图判 定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子图。
[0081] 下面根据具体实施例进一步阐述本发明的技术方案。
[0082] 一个不确定图是一个元组Gu= (G，P)，其中G是一个确定图，P(0，1是一个 概率函数，将每条边e映射为一个存在概率，由Pe表示，eGEG。G是主干图。
[0083] 一旦确定了每条边的存在情况，由Gu可以蕴含得到确定图GS称为蕴含图。因此 一个不确定图Gu总共蕴含21 &1可能的确定图，每个蕴含图都是Gu可能的存在方式。
[0084] 我们考虑的模型假设边之间的存在概率是相互独立的，这种模型有很多实际的应 用，那么，Gu蕴含G1的概率，或者G1的存在概率，可以通过包括或不包括边来计算：
[0086] 既然经典的关于支持度的概率在不确定图上变得很有意义，我们求助于期望支持 度，即在蕴含图上的概率分布情况。
[0087] 我们将子图g在不确定图Gu上的期望支持度定义为：
[0089] 其中，以是6"的蕴含图。给定期望支持度阈值〇,子图g如果是频繁的，那么g在 Gu中的期望支持度将不小于阈值，即eSUp(g，Gu)彡〇。
[0090] 对每个Gu的蕴含图G\
，esup(g，G1) <esup(g'，G1)。不等式在对 i进行求和后仍然成立。因此，esup(g，Gu)彡eSUp(g'，GU)，期望支持度是反单调的。 [0091] 在图2中，我们为G的每条边赋予一个存在概率并构造一个不确定图Gu，其中 存在概率建模两个人合作关系的紧密程度。此时，G是主干图，同时Gu有8个蕴含图，
。我们在上文中已经计算出sup(g，G) =2,因
。照此将所有来自蕴含图的值聚合起来，可以计算出esup(g，Gu) = 1. 12。如果给定的支持度阈值〇 = 1，则esup(g，Gu)彡1，g是频繁子图。
[0092] 给定一个不确定图Gu= (G，P)和一个期望支持度阈值〇，单个不确定 图上频繁子图挖掘问题是指发现所有期望支持度不小于给定阈值的子图g，即
[0093] 我们在期望支持度的定义中给出了频繁子图的语义。假设sup(g，Gu) = 10,4表 示一个随机独立选择的蕴含图，那么我们有理由期望g在4中至少有10次不重复的出现。 根据现有的分析，基于期望语义的频繁子图适合于在不确定图中进行主题发现。当不存在 二义性时，在后文中省略领域Gu，即表示为sup(g)。
[0094] 我们提出了一个枚举一评价的算法，取名为fanta(frequentsubgraphminingon uncertaingraphs)。fanta算法先枚举所有可能的候选子图，再对每个子图计算期望支持 度，然后决定是否将其作为结果输出。任何利用了Apriori性质的枚举策略都可以使用。 Apriori性质陈述的是，不频繁子图的超图也不可能是频繁的。特别地，不确定图中所有子 图可以被组织为一个有根的有向无环图（DAG)，其中节点代表候选子图（根表示为空KDAG 中从g'到g的一条弧表示g'是g的直接超图。我们从频繁的边开始，每次将一条新的边 加到频繁子图中，枚举所有可能子图，因此可以在DAG的第n层找到包含n条边的子图。为 了避免重复枚举同时保证完备性，我们使用方法gSpan给每个子图增加了词典顺序。
[0095] 然而，通过比较期望支持度和阈值，决定一个被枚举出的子图是否是频繁的，其最 简单的方式是产生所有蕴含图，计算并聚合子图在所有蕴含图上的支持度，得到期望支持 度，再与支持度阈值进行比较。但这种方法因为会产生大量蕴含图，加上支持度计算的高复 杂度，因此对终端用户而言是不可接受的。为了达到更好的运行性能，我们尝试所有可能， 在可接受时间内返回结果。
[0096] 我们已经发现，使用定义计算期望支持度复杂度相当高，因为Gu存在2141个蕴含 图。对每个候选子图，我们需要计算在指数级的确定图上计算其支持度，其中频繁涉及具有 高昂时间代价的子图同构检测。我们研宄这一问题并通过一个高效的算法来降低计算复杂 度。
[0097] 我们首先用另一种方式给出期望支持度的计算。假设P(sup(g) =j)表示子图g 在所有支持度等于j的蕴含图上的聚合概率，即
[0099] 其中，Aj(g) = {G'lsupCg，G1) =j}。
[0100] 因此有
[0102] 其中，Ms=sup(g，G)是g在Gu所有蕴含图中最大的支持度。
[0103] 我们进一步定义，Pj(g)为g在Gu的蕴含图中支持度不小于j的聚合概率，SP
[0105]其中，Aj(g) = {G'lsupCg，G1)彡j}。
[0106] 同时，对esup(g)公式右端展开可得
[0108] 因此又有
[0110] 我们还注意到P」(g)的两个性质：（l)P」(g)彡P」(g')，其中，gGg;⑵Pj(g) ^Pjr (g)，其中，1 <j' <j。
[0111] 我们可以证明，计算1\化)是#P难的，其中q是一个整型常数。可以将DNF计数问 题在多项式时间内归约为此问题，以此证明该问题是#P难的。
[0112] 考虑一个析取范式的一阶逻辑表达式（DNF)D=QVC2V~VCtCjiG[l，m]) 的形式为1，12八…八lk，其中，l」(je[l，k])是{Xl，x2，…，xn}中的布尔变量。DNF计 数问题是计算有多少种对变量的赋值可以满足D。设P(Xi)表示Xi被赋值为真的概率，P(D) 是随机一组对变量的赋值满足D的概率，给定一个前述实例，下面构造了在Gu中计算Pq(g) 的问题。
[0113] 我们构造一个不确定图Gu，其节点集合为ViUV2UV3，其中：
[0117] 其中，V#节点的标签为a，V2UV3中为0。边的构造方法如下：
[oils] ⑴在i
|之间增加一条边，ie[lj-1]，jg[i，k]，存在概率为 i；
[0119] (2)如果D中Xi包含在C冲，则在（ci，11」）增加一条概率为1的边；
[0120] (3)对每个xf{x^x2, . . .，xn}，在(X，vD之间增加概率为P(Xi)的一条边，所 有Gu的边标签为y。
[0121] 两个问题之间的关联性为：
[0122] 每个对{Xi，x2，…，xn}的真值赋值JT一对一对应于Gu的一个蕴含图GS即边（Up Vi)存在当且仅当\赋值为真，每个真值赋值31的概率等于
。显然，在所有蕴 含图以中
。因此，如果一个真值赋值满足D，当且仅当g在蕴含图 6"中的支持度超过。因此
[0123] 综上可知，计算Pjg)是一个#P难问题。类似地，可以证明计算esup(g)也是#P 难的。
[0124] 图3示出的是布尔表达式D按照上述构造方法，得到的不确定图Gu和子图g，其中， D= (X,X2八X3)V(X2AX3八X4)，Xpx2,x3,x4被赋值为真的概率分别是P(xD，P(x2)， P(x3)，P(x4)〇
[0125] 由于计算子图支持度问题具有#?难的时间复杂度，我们提出了一个近似评价算 法，其误差为e。作为近似算法，理想的结果是能够返回所有频繁的子图（真正）；为了满 足这一要求，则结果集中也会有不频繁的子图（假正）。根据这一目的，我们输出一个闭区 间「esup,esup]， 该区间包含esup真实值，然后对于子图g的支持度与支持度阈值〇之间 关系的以下不同情况进行处理：
[0126]Case1:如果
，不输出g，因为esup(g) <〇是确定的；
[0127]Case2:如果esup(g) ^ (1_e) 〇 且
，则输出g，因为 esup(g)彡（1-e) 〇是肯定的，而且很有可能esup(g)彡〇;
[0128]Case3:如果i
冃.esup(g)<(卜e)o，则不能决定是否输出g，因为 我们不能决定是否esup(g)彡〇或者esup(g) < (1-e) 〇。
[0129]Case3并不是我们想要的，因为Case3我们无法决定。然而，我们观察到如果区 间「esup,?^n^l的宽度在e0范围内，则Case3不会出现。因此，通过限制区间宽度最大 为e〇，则通过「esup,万1来估计esup是足够的，因为此时只有Case1和Case2会出 现。这对于算法设计很重要，我们的算法依赖此来决定是否将g作为结果输出。
[0130] 我们的近似算法基于蒙特卡洛方法。通过
，我们首先计 算P」(g)的近似值， 其中，je[1，MJ;然后聚合该值得到区间[^^(g),^Ip(g)]。为了 保证区间不会大于e〇，我们要求每个Pj(g)近似值的绝对误差不会超过eo/Ms。此要求 来自一类随机算法一一随机近似模式，可以提供精度保证。
[0131] 给定一个置信系数Se[0，1]，以及一个绝对误差范围e '，我们可以使用由随 机近似模式得到的近似值p来估计P，如果PCIP-PI< :) 2 1 -S,其中，1-S是置信程 度。为了在S和e'的条件下近似得到Pj(g)，我们依靠一个基于霍夫丁不等式的算法。
[0132] 假设Xi，X2，…，Xn是独立同分布的伯努利随机变量，其中Xi= 1的概率为P，则有 下述不等式成立：
[0134] n个样本观察值的平均可以提供一个具有精度保证关于p的近似，为提供置信度 1-S和绝对误差e' =e o/2Ms需要的样本量大小为：
[0136]算法1为评价一个子图的过程的封装。输入一个子图g，不确定图Gu误差系数e以及实数S;输出一个布尔值，表示g是否是频繁的。
[0138] 算法第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评价支持度 的近似值.
[0139] 函数EvaluateSup工作流程为：输入Pj(g)的观察概率值P[j]、整数X， 并输出Case 1或者Case 2 (Case 3不应该出现）。特别地，当前概率观察值
，输出结果在，
之间。 根据区间与支持度阈值0之间的关系作出决定。
[0140]
丨证明，只要样本量足够，所有输出 子图满足给定误差范围，算法1就是正确的。另一方面，由于在子图g增长的过程中存储 了其嵌入（embedding)，可以在0(|F(g) | |Vg|)的时间复杂度下计算Ms，其中F(g)是g嵌 入（embedding)的集合；接着，我们执行蒙特卡洛仿真，计算支持度和概率的复杂度分别为 〇(|F(g) | |Vg|)和0(|Eg|)。因为总的抽样样本数量复杂度不超过
，则 算法1的总复杂度是
。既然时间复杂度是关于
的多项 式级，算法1属于完全多项式随机近似模式（FPRAS)，该模式可以同时提供高效性和高准确 度。
[0141] 实现基于蒙特卡洛支持度评价的一种直观方式是在每个样本图中计算子图的支 持度，并聚合观察概率。这种方式会比较耗时，因此我们考虑可能的加速方法。
[0142]图4示出的是图2中不确定图Gu的两个样本图G'和G"，以及G'和G"的重用树 "DM_Bio"。首先，在计算
丨后。我们可以进一步考虑边03来计算
另外。如果一个P的嵌入（embedding)存在于G"中，我们可以确定G'也包含了此嵌入而 不需要额外的计算。最后，为了算出sup(p，G")，我们构造了一个数据结构：
[0144] 可增加一个新的列（v3_v4)，用于计算sup(p，G')。
[0145]对于图4中的两个样本图G" □G'，存在三种可以重用的计算：
[0146] (1)计算样本图的存在概率；
[0147] (2)测试一个嵌入是否存在；
[0148] (3)计算支持度。
[0149] 我们可以将此计算重用的思想泛化到多个样本图的情况，此时，样本图之间的包 含关系并不需要满足。
[0150] 对于第（1)种和第（2)种计算，我们首先要构造一个二叉重用树，其中所有样本图 都是树的叶节点。假设嵌入边有一种关于其ID的线性顺序，则可以得到传统的树的结构。 二叉树的深度为I ，在深度为i的所有分支决定于是否包含边％。换言之，根的深度为 1，其左分支h是一棵包含有e:这条边所有样本图的子树的根，而右分支i包含剩下的不 含4这条边所有样本图子树的根。这个分支过程从~到em中最后一条边，最终得到2l'l 叶节点。因此我们可以在叶节点为每个样本图找到一个对应的位置。
[0151] 我们不需要产生整棵树。我们每计算了一个样本图，就存储包含此样本图的一个 分支。我们采用如下方法产生样本图，并构造整个树：在根节点，对每个样本图h，我们随 机决定它是去左分支h还是右分支np左分支、右分支分别由left边和right边连接。接 着，如果^不为空，则将n1在树上保存下来，接着，随机决定样本图的去向；如果ni是空，则 停止此分支继续增长。对于~也是同样的处理过程，当所有的样本图都到达叶节点时，整 个迭代过程结束。在增长过程中，每个样本图的存在概率在增长过程中作为一个副产品计 算得到，同时计算重用达到最大。
[0152] 之后，我们计算每个样本图的支持度。第一步是决定每个样本图包含的嵌入 (embedding)。为此，我们对每条嵌入边维护一个反向索引，每条嵌入边作为一个条目，那些 包含这条边的嵌入（embedding)作为对应的记录。该索引便于发现那些因为不存在嵌入边 而缺少的嵌入，而该索引在主干图上计算支持度时建立，且开销较小。根据重用树的构造， 进入右分支意味着一条边e不存在，因此包含这条边的嵌入也不存在；而进入左分支并不 影响嵌入集合。
[0153] 对于一个样本图，我们从叶节点追踪到根节点，并记录下经过的right边。整个嵌 入集合减去那些一路上遇到的right边对应的嵌入即为考虑的样本图。另外，为了能计算 重用，我们在处理每个样本图时，都会记录树节点上的中间结果。接着，我们从最低父节点 开始，增量式地进行计算，即从叶节点到根节点路径上第一个已经被处理过的节点开始，而 不是从根节点开始。
[0154] 在图4示出的实施例中，右边的树是从G'和G"构造的部分重用树，其中ni是根， n4(或者n5)是叶节点，对应G'(或者G")。在处理完G'后，我们在节点n3有嵌入集合 {Vi-VyV3-V2,V3-V4}，该集合可以包含于任意在此分支后的样本图。接着，由于不存在边e3， 我们从反向索引上获取到那些不再包含的嵌入，即Iv3-v4}。然后我们将其删除，得到G"包 含的嵌入集合IvfVyV3-V2}。
[0155]接下来，我们以串行的方式进行第（3)种计算的重用。对于两个样本图G'和G"， 我们首先描述怎样计算sup(g，G')。对每个包含在G'中的嵌入，我们将其对应的点排成 一行行。注意到由于我们已经获得了同构映射，因此该操作比一般情况要简单和迅速得多。 特别地，对于一个点vg，我们利用一个映射来记录一一G'中每个嵌入点作为键，该点在所 有嵌入中出现次数作为其值。当我们遇到一个嵌入以u作为^嵌入点时，则对u对应于vg 在映射中的值增加1。在对所有嵌入中的节点进行计数后，我们可以通过获取所有映射中最 小集合的值，得到sup(g，G')。
[0156] 为了在计算G"时重用之前的中间结果，而不是从头开始建立这些映射，我们首先 去除掉不包含在G"中的嵌入，减少其在映射中对应的值，然后增加之前没有包含在G'中 的嵌入，并增加对应的值。之后，我们可以得到sup(g，G")。
[0157] 对增加或减少一个单位的开销进行建模，固定为c ;获取最小映射的集合大小的 开销为c'。给定一系列样本图匕，每个包含一个嵌入的集合Fi G F，其中i e [l，N]，从头 开始计算支持度的开销为iFil.c+c'。 我们定义：
[0159]从Gi (或Gj)到Gj (或GD，支持度计算的开销是
，并
?则对于h，从头开始计算开销更小。为了最大化计算重用，我 们将此问题进行形式化地描述如下：
[0160] 给定一系列样本图GiGD，每个包含一个嵌入的集合FiGF，其中，ie[1，N]， 从匕到h的计算开销为
，找到一个计算序列使得开销最小，满足每个 图只被处理过一次。
[0161] 该问题是NP难的。我们为每个样本图构造一个比特数组，每个比特对应一个F中 的嵌入，即数组的维度为|F|。如果样本图包含该对应的嵌入，则比特位设为1，相反则设为 0。这种情况下，两个图之间的开销可以通过计算二进制串之间的汉民距离比较容易获得。 接着我们使用一种启发式的计算序列一一从左到右对应样本图在叶节点的位置。直观的想 法是两个连续叶节点（如图4中的G'和G")，通常距离较小，因此增量计算复杂度相对 小。
[0162] 我们使用算法2将所有3中重用计算集合在一起如下：
[0164] 为了将算法2整合到基本算法中，我们可以将算法1中第4-8行替换为 "P-ShareCompTree(g，Q) "，使得算法2在基本算法中生效，修改后的算法1可以执行基 于计算重用的子图判定。
[0165] 综上所述，为获得不仅频繁，而且在现实中具有高置信度的子图，我们定义了在单 个不确定图上，基于期望支持度的频繁子图挖掘问题，基于期望语义的支持度对于在不确 定网络中主题发现很有用。为了说明此问题的高复杂度，通过将DNF计数问题归约为此问 题，我们证明了计算子图期望支持度是#?难的，我们提出了一种基于蒙特卡洛的近似算 法来获取一个区间，并以给定精确度包含真实值，将获取的支持度区间与支持度阈值之间 的关系分为三种情况，可以保证，以概率至少为1-8,任何子图支持度不小于〇的子图都 会被输出，同时任何期望支持度小于（l-e)〇的子图都不会输出。此分类确定了我们枚 举-评价的算法框架，即慎重地枚举候选子图并逐一评价；同时，我们对抽取样本中可重用 的计算进行共享，通过在线建立的二叉共享树进行计算重用，大幅度减少了子图挖掘消耗 的时间。借助于本发明的上述技术方案，通过将单个不确定图划分为多个蕴含的确定图并 将蕴含图视作确定图使用计算重用方法抽样计算子图的期望支持度的手段，我们能在单个 不确定图上使用频繁子图挖掘技术，填补了本领域的技术空白。
[0166] 所属领域的普通技术人员应当理解：以上所述仅为本发明的具体实施例而已，并 不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。
【主权项】
1. 一种针对单个不确定图的频繁子图挖掘与优化方法，其特征在于，包括： 获取单个不确定图； 根据所述单个不确定图枚举出所述单个不确定图的所有子图； 在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图； 使用计算重用方法分别计算所述单个不确定图的每个样本图的存在概率，并使用计算 重用方法计算所述每个子图在所述单个不确定图的样本图上的期望支持度； 根据所述每个子图在所述单个不确定图的样本图上的期望支持度与所述单个不确定 图的每个样本图的存在概率，判定该子图是否为频繁子图； 输出所有频繁子图。2. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的每个样本图的存在概率，并使用计 算重用方法计算所述每个子图在所述单个不确定图的样本图上的期望支持度，为根据所述 单个不确定图构造重用树，为所述单个不确定图的每个样本图中的每条嵌入边构建反向索 弓丨，并根据所述重用树与所述反向索引分别计算所述单个不确定图的每个样本图的存在概 率与所述每个子图在所述单个不确定图的样本图上的期望支持度。3. 根据权利要求2所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图构造重用树，为从所述单个不确定图上选取一根节点，根据一 条嵌入边的存在与否生成第一层二叉树，再根据根节点的子节点上嵌入边的存在与否生成 第二层二叉树，如此重复直到所述单个不确定图上所有节点与嵌入边的二叉树形式均被重 用树包括。4. 根据权利要求1所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，根据所述单个不确定图枚举出所述单个不确定图的所有子图包括： 从所述单个不确定图提取出多个蕴含图，所述每个蕴含图都是所述单个不确定图可能 的存在方式； 分别计算所述每个蕴含图所包含的所有子图。5. 根据权利要求4所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，所述提取出多个蕴含图的个数为2的所述单个不确定图中边的个数次幂。6. 根据权利要求5所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，在所述单个不确定图的所有蕴含图中指定部分蕴含图为样本图，为在所述单个不确 定图的所有蕴含图随机指定数个蕴含图为样本图，其中，所述样本图的数量与任一子图在 所述单个不确定图的所有蕴含图的支持度最大值的平方成正比，与不置信度的自然对数成 反比，与误差系数的平方成反比，与支持度阈值的平方成反比。7. 根据权利要求6所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特征 在于，使用计算重用方法分别计算所述单个不确定图的每个样本图的存在概率，并使用计 算重用方法所述每个子图在所述单个不确定图的样本图上的期望支持度包括： 根据所述单个不确定图中每条边的概率，计算出所述每个蕴含图的存在概率； 指定所述单个不确定图的所有子图中的一个； 分别计算所述被指定的子图在每个样本图上的支持度； 根据所述每个样本图的存在概率、所述被指定的子图在每个样本图上的支持度，计算 所述被指定的子图在每个样本图的支持度； 继续从所述单个不确定图中指定下一个子图并计算其在每个样本图上的支持度，直到 所述单个不确定图的所有子图都被指定； 根据所述每个子图在每个样本图上的支持度，计算所述每个子图在所述单个不确定图 上的期望支持度。8. 根据权利要求7中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，分别计算所述被指定的子图在每个样本图上的支持度，为使用最大独立集法计算 所述被指定的子图在每个样本图上的基于最小像的支持度。9. 根据权利要求8中所述的一种针对单个不确定图的频繁子图挖掘与优化方法，其特 征在于，根据所述每个子图在所述单个不确定图的样本图上的期望支持度与所述单个不确 定图的每个样本图的存在概率，判定该子图是否为频繁子图包括： 获取期望支持度阈值； 根据所述单个不确定图的每个样本图的存在概率，计算所述子图在所有支持度等于一 恒定值的蕴含图上的聚合概率； 根据所述子图在所有支持度等于一恒定值的蕴含图上的聚合概率，计算所述子图在所 述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚合概率； 根据所述子图在所述单个不确定图的所有蕴含图中期望支持度不小于该恒定值的聚 合概率，计算当前概率观察值与结果区间； 根据所述结果区间与期望支持度阈值判定所述子图是否为频繁子图，将所有结果区 间上限大于期望支持度阈值、且结果区间下限大于期望支持度阈值与非误差系数的乘积的 子图判定为频繁子图，将所有结果区间上限小于期望支持度阈值的子图判定为不是频繁子 图。
【专利摘要】本发明公开了一种针对单个不确定图的频繁子图挖掘与优化方法，包括：获取单个不确定图；根据单个不确定图枚举出单个不确定图的所有子图；在单个不确定图的所有蕴含图中指定部分蕴含图为样本图；使用计算重用方法分别计算单个不确定图的每个样本图的存在概率，并使用计算重用方法计算每个子图在单个不确定图的样本图上的期望支持度；根据每个子图在单个不确定图的样本图上的期望支持度与单个不确定图的每个样本图的存在概率，判定该子图是否为频繁子图；输出所有频繁子图。
【IPC分类】G06F17/30
【公开号】CN104899283
【申请号】CN201510296077
【发明人】唐九阳, 赵翔, 陈一帆, 李瑞琪
【申请人】中国人民解放军国防科学技术大学
【公开日】2015年9月9日
【申请日】2015年6月2日
最新回复(0)