代码之家 › 专栏 › 技术社区 › inf3rno

为什么BIDE使用半最大周期进行serach空间修剪?

pattern-mining data-mining algorithm

1

inf3rno · 技术社区 · 8 年前

根据这篇定义拜德的文章:

BIDE: Efficient Mining of Frequent Closed Sequences

定理2(后向扫描搜索空间修剪):

让前缀序列为 n序列, Sp=e1e2...en . 如果 âi(1â¤iâ¤n) 存在一个项目 eâ² 它出现在前缀的第i个半最大周期中 Sp 在里面 SDB ,我们可以安全地停止增长 服务提供商 .

证明:

因为项目 电子 出现在前缀的第i个半最大周期中 服务提供商 在里面 SDB公司 ,我们可以得到一个新的前缀 Sâ²p=e1e2...eiâ1eâ²ei...en (1<iâ¤n) 或 Sâ²p=eâ²e1e2...en(i=1) ,以及两者 (Sp ââ Sâ²p) 和 (supSDB(Sp)=supSDB(Sâ²p)) 等等。任何本地常见项目 eâ²â² w、 r.t。前缀 服务提供商 也是当地常见的东西。 Sâ²p ,同时 (ãSp,eâ²â²ãâãSâ²p,eâ²â²ã) 和 (supSDB(ãSp,eâ²â²ã)=supSDB(ãSâ²p,eâ²â²ã)) 等等。这就意味着挖掘具有复杂结构的频繁闭序列是没有希望的前缀 服务提供商 .

我明白,例如,如果我有 AB 我找到了一个 e' ,例如 C ,正处于模式的第二个最大周期,所以 A 和 B 对于包含 AB型 ,那么我就可以停止生长了 AB型 ,因为我可以使用向后扩展 ACB ,将有相同的支持,但它更长。所以我通过扩展 AB型 向前,肯定不会是封闭的格局,因为 C级 它不见了。所以我必须停止成长 AB型 等着它长大 A -> AC -> ACB 向前延伸。我不明白为什么在这种情况下,最大周期必须被限制在半最大周期内,为什么测试半最大周期是可以的。这篇文章没有作真正的解释。你知道吗?你能写一个例子吗,我们用最大周期而不是半最大周期来丢失闭合的频繁模式?

1 回复 | 直到 8 年前

1

0

inf3rno 8 年前

我想我找到答案了。下面是一个示例,它在最大时段中有新事件,但在半最大时段中没有:

[AxByB,AqBtyB], AB
2nd max period: [xBy,qBty] -> By
2nd semi-max period: [x,q] -> 0

所以根据它我不能停止成长 AB ,因为没有 e' 在同一支撑下的半最大周期内。另一方面 e' 在相同的支撑下,我们可以达到 A{By}B 向后延伸的图案 AB型 . 但我发现我们可以 AB{yB} 向前延伸 AB型 我也是。有更多的重叠,例如 ABAB 我们将得到相同的结论;我们可以增长初始值 AB型 向前延伸到 AB{*A*B} ,但我们不能向半最大周期添加任何字符 A{*}B ,因为我们无法从 AB型 而PrefixSpan仅以向前扩展的方式增长。例如,如果我们发现 x 在 AB型 有了同样的支持,我们就必须停止增长 AB型 等待PrefixSpan增长 AxB 在 A -> Ax -> AxB 一路走来,不断成长 AxB公司 模式而不是 AB型 图案。Ofc公司。我们在这里寻找的是封闭的频繁模式,而不是频繁模式,因此我们可以通过这种方式安全地删减搜索空间。我不确定是否有可能设计一个频繁模式挖掘算法,它可以进行前向和后向扩展。也许稍后我会尝试为challange设计这样一个算法,但是现在BIDE对于我正在做的事情来说还不错。