挖掘问题
约 2263 字大约 8 分钟
2023-11-08
固定参数的易解性(FIXED PARAMETER TRACTABILITY)
我们重新回顾 GFDs 的三个关键问题:
满足性问题(Satisfiable)。
是否存在一个图数据,能满足所有 GFDs。
- GFDs 不存在冲突。
- 至少一个 GFD 是可以用在非空图数据上的。
蕴含问题(Implication)。
判断一个 GFD 是否能被一个 GFDs 的集合推导出来。对于判断多余的 GFDs 来说很有必要。
比如:Q[x,y,z](x.A=y.B∧x.C=z.D→L) 和 Q[x,y,z](x.A=y.B→L),明显第二个可以推出前一个,所以第一个是多余的。
验证问题(Validation)。
判断一个 GFDs 集合能否满足一个特定的图数据 G。
和满足性问题的区别在于此处的 G 是给定的,而满足性问题里面的 G 是任意的,存在即可。
提示
satisfiablilty,implication 和 validation 三个问题分别是 coNP-complete,NP-complete 以及 coNP-complete 问题。
对于一个可以参数化的问题 P 是一对 (x,k),其中 x 在传统的复杂性理论中表示输入,k 是表征 x 结构的参数。固定参数的易解性是指:当存在一个函数 f 和一个算法可以在 O(f(k)⋅∣x∣c) 的时间内计算出任意一个 (x,k) 实例,其中 c 是一个常量。显然,当 k 的值比较小的时候,我们是可以有效地计算出问题的答案的,虽然 f(k) 本身可能是指数增长的。
工程实践经验
事实上工程中 k 都较大,所以计算复杂度非常高,需要额外的剪枝策略来提高计算效率。
对于一个集合的 GFDs Σ,我们使用 k 来表示 Q 中 xˉ 的向量长度,即 max(∣xˉ∣),我们可以将蕴含问题用 k 表示为:
- 输入:一个 GFDs 的集合 Σ 和一个 GFD φ。
- 参数:k=max{∣xˉ∣ ∣ Q[xˉ](X→Y)∈Σ∪{φ}}。
- 问题:Σ⊨φ 是否成立?
k-bounded GFDs
模式 Q[xˉ] 是 k-bounded
当其满足 ∣xˉ∣≤k,k 是一个常量。
当其中所有的 Q[xˉ](X→Y) 中的 Q[xˉ] 都是 k-bounded
时,一个 GFDs 的集合 Σ 是 k-bounded
。
挖掘问题(THE DISCOVERY PROBLEM)
给定一个图 G,挖掘目标为找到一个 GFDs 的集合 Σ,使得 G⊨Σ。
当然,我们并不希望计算出所有的 GFDs,因为中间有很多平凡的和重复的 GFD。我们希望计算出的 GFDs 是:
- 没有平凡的和多余的 GFD。
- 是频繁的规律和约束。
Reduced GFDs and GFD Cover
我们先来定义一下不平凡和简化的 GFDs。
不平凡的 GFDs(Nontrivial GFDs)
一个 GFD φ=Q[xˉ](X→l) 是平凡的有两种情况:
- X 恒等于 false,即永远不可能被满足。
- l 可以被 X 使用恒等变换推导出来。
简化的GFD(Reduced GFD)
reduced pattern
给定一个模式 Q[xˉ](VQ,EQ,LQ,μ) 和 Q′[xˉ′](VQ′,EQ′,LQ′,μ′),如果 Q 是通过 Q′ 减少点(或者边)亦或者是将 Q′ 中的一些 label 变为通配符得到的,那么我们称 Q 简化了 Q′,记作 Q[xˉ]≪Q′[xˉ′]。这意味着 Q 是 Q′ 拓扑结构相同,但是约束更少的版本。
pivot
在一个图模式 Q[xˉ] 中,指定一个变量 z∈xˉ 并将其指定为 Q 的 pivot。我们使用 pivot 来探讨子图同构问题的数据局部性。 对于 G 中任意的 v,如果存在 h 使得 h(z)=v,则 h(xˉ) 只包含 dQ 跳以内的点。其中 dQ 我们称之为 Q 的半径,即 z 到 Q 中任意点的最长的最短路径(the longest shortest path)。
在工程实践中,pivot 一般配置为用户最感兴趣的点。
如果不清楚最长的最短路径的定义,可以查看:longest-shortest-path-in-an-undirected-unweighted-graph。
结论:如果 φ1=Q1[x1ˉ](X1→l1),φ2=Q2[x2ˉ](X2→l2)。显然,当 Q1≪Q2 并且 X1≪X2 时,φ1≪φ2。
GFDs 的覆盖(Cover of GFDs)
当所有的 φ∈Σ,Σ≡Σ\{φ},即 Σ 不包含任何多余的 GFDs 的时候,我们称 Σ 是 minimal(最小的)。
图 G 上 Σ 的一个覆盖集合 Σc 是一个 Σ 的一个子集,满足:
- G⊨Σc。
- Σc≡Σ。
- Σc 中的所有 GFD 都是最小的。
- Σc 本身是最小的。
这说明 Σc 不包含任何无趣的多余的 GFDs。
频繁的 GFDs(Frequent GFDs)
support 的传统定义
对于 GFD φ=Q[xˉ](X→)Y,φ 的 surport 为 Q 在 G 中匹配并满足 X→Y 的数量。
但是这个定义并不是反单调性的。例如 Q[xˉ] 表示一个点 person,Q′[x,y] 表示一个边从 personx 到 persony,label 是 hasChild。在现实生活中,我们会发现即便 Q 是 Q′ 的一个子集,Q′ 的数量是远远大于 Q 的数量的,因为一个人可能有多个孩子。
我们会发现,当我们的限制增多了之后,匹配的数量不仅没有减少,反而增多了。
为此,我们给出新的定义:
Pattern support(模式支持度)
对于一个图 G,和一个正向 GFD φ 拥有模式 Q[xˉ],其中 Q 有 pivotz。用 Q(G,z) 表示由 h(z) 推导出来的匹配 z 的节点的集合,其中 h(z) 是 Q 在 G 中所有的匹配。
模式 Q 的 support:
supp(Q,G)=∣Q(G,z)∣
这个公式量化了实体在 G 中满足拓扑结构 Q 且以 z 为 pivot 的频繁程度。
pivot 的作用
为了 GFDs support 的反单调性,我们在上述的定义中引入了 pivot 的概念。反单调性允许我们沿着与传统数据挖掘相同的路线加速挖掘过程。
为了量化在 Q[xˉ] 中属性的依赖程度,我们定义 correlationρ(φ,G) 如下:
Correlation measure(相关度)
ρ(φ,G)=∣Q(G,z)∣∣Q(G,Xl,z)∣
这里的 Q(G,Xl,z) 表示 Q(G,z) 的子集以至于 h(xˉ)⊨X 并且 h(xˉ)⊨l(前文曾提到过:φ=Q[xˉ](X→l))。
正向 GFDs 的支持度
φ 的支持度定义为:supp(φ,G)=supp(Q,G)∗ρ(φ,G)=∣Q(G,Xl,z)∣。
定理 3
对于任何图 G 和非平凡的正向 GFDs φ1 和 φ2,如果 φ1≪φ2 则 supp(φ1,G)≥supp(φ2,G)。
负向 GFDs 的支持度
由于负的 GFDs 无法被满足,所以无论如何都有 Q(G,Xl,z)=∅,则不再使用 Q(G,Xl,z)=∅ 来定义负的 GFDs 的支持度。
现实生活中只关心有正向 GFDs 通过增加一步垂直扩展或水平扩展所变成的负 GFDs,则负的 GFDs 的支持度定义为:
supp(φ,G)=maxφ′∈Φ′(supp(φ′,G))
- 若 X=∅,∅′ 由模式 Q′ 组成,这些模式 Q′ 有相同的轴 z 使得 supp(Q′,G)>0,且 Q′ 是通过去除 Q 的边(也有可能是节点)得到的。
- 若 X=∅,∅′ 由正的 GFDs Φ′ 组成,这些 GFDs 有相同的 pivot z 使得 G⊨φ′,X 中存在字段 l′ 使得 X=X′∪{l′}。
如果 supp(φ,G)≥σ,其中 σ 是一个支持度阈值,则说 GFD φ 是频繁的。
OWA
OWA 指出,不存在的数据不能作为知识库中的反例。
- 对于正的 GFD φ,其支持度量化了存在并符合 φ 的实体。
- 对于负 GFD φ,其支持度由正 GFD φ′ 的支持度所决定。 也就是说,负 GFDs 描述了观察世界中不存在的案例。未知数据对负 GFDs 的发现没有影响。
挖掘问题
我们将 GFDs 的挖掘问题表述为:
- 输入:一个图 G,一个自然数 k≥2 和一个支持度阈值 σ>0。
- 输出:一个 supp(φ,G)≥σ,k-bounded 最小 GFDs φ 的覆盖集 Σc。
验证问题和蕴含问题被包含在 GFD 的挖掘过程中,对应步骤:检查 G⊨φ 和计算一个 k-bounded GFDs φ 的覆盖集 Σc。
我们使用 k 这个参数来平衡挖掘过程和对 GFDs 解释的复杂性。因为显然地:
- 如果 GFDs 拥有太多属性则不太可能频繁,并且也很难跟终端用户进行解释。
- k 过大的时候计算复杂度过高,验证问题和蕴含问题是当 k 是固定的时候是 PTIME 的。
工程实践经验
真实的数据分析中我们会精心挑选参与计算的属性,我们通常会选择属性集合 Γ。Γ 通常是我们最感兴趣的属性或者是我们认为最"干净"的,可信任度最高的数据。