分布式关联模式挖掘的设计与实现文献综述

 2022-11-20 15:36:42
  1. 文献综述（或调研报告）：
  2. 图的基础知识

标号图：一个标号图是一个五元组,G={V,E,Sigma;E,Sigma;V,L}。其中,V 代表图中节点的集合,Esube;Vtimes;V 代表图中边的集合。Sigma;V,Sigma;E 分别代表节点标号的集合与边标号的集合。L 是标号函数,用于完成标号向节点和边的映射:V→Sigma;V 与E→Sigma;E。

图的同构：图的同构是一个双射 f:V(G)harr;V(G′)。对于图G={V,E,Sigma;V,Sigma;E,L}与图G′={V′,E′,Sigma;V′,Sigma;E′,L′},若它们是同构的,则满足如下条件:

forall;uisin;V,L(u)=L′(f(u))

forall;u,visin;V,((u,v)isin;E)hArr;((f(u),f(v))isin;E′),且

forall;(u,v)isin;E,L(u,v)=L′(f(u),f(v))。

子图同构：给定标号图 G 与G′,若G′中存在子图GPrime;与图G 同构,则称G 与G′是子图同构的,记为Gsube;G′。

支持度：定一个图的集合GD,图G的支持度记为SUPG,计算方法为GD中与G存在子图同构的图G′的个数与整个图集中图的个数的比值,表示如下:

频繁图与频繁树：定一个图集GD,GD={Gi|i=0,1,hellip;,n},且给定最小支持度阈值为min_sup,我们称图G是频繁的,当且仅当G的支持度不小于最小支持度阈值,即SUPGge;min_sup.相应地,当图G是频繁的且其中无回路时,我们称G为频繁树.

频繁子图挖掘问题是给定一个最小支持度阈值min_sup,在图集GD 中找到所有支持度不小于min_sup 的子图.在以下章节中,使用大写字符表示集合,如G,E,V 等,而用小写字符表示元素,如g,e,v 等.

  1. 对gSpan的调研

gSpan算法中有两大技术：DFS字典序和最小DFS编码。gSpan在图之间建立了一种字典序，把每个图映射到一个独一无二的DFS编码上去，以这个编码代表该图。基于这个字典序，gSpan采用深度优先搜索挖掘频繁连通子图。

剩余内容已隐藏，您需要先支付 10元 才能查看该篇文章全部内容！立即支付

以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章