一种面向属性图集的频繁近似子图挖掘方法
一种面向属性图集的频繁近似子图挖掘方法
【技术领域】
[0001] 本发明属于图挖掘技术领域，具体涉及一种面向属性图集的频繁近似子图挖掘方 法。
【背景技术】
[0002] 频繁子图挖掘作为图挖掘中的重要任务，可以发现图中隐含的重要模式，而且挖 掘出来的模式可以用于进一步的研宄，例如分类、聚类和关联模式挖掘等。图匹配是频繁子 图挖掘中的关键步骤，目前存在两类图匹配方法：精确匹配和近似匹配。图精确匹配要求两 个图的结构和特征完全相同，虽然图精确匹配在数学上提供了严谨的方法，但是它只适用 于有限的问题中。由于现实世界中的对象常被噪声影响，且图建立过程中存在失真现象，例 如，属性值出现误差或者顶点和边的缺失等，所以图近似匹配在现实中的应用更为广泛。 [0003] 依据图近似匹配策略，近似子图挖掘方法主要分为五类：（1)基于图编辑距离：算 法SUBDUE、RNGV和MaxAFG探讨一个图潜在的编辑路径，并把最有可能的编辑路径作为候 选项；（2)基于-边的子同构：算法Monkey中允许边的缺失和边标号的替换，其中是边差异 阈值；(3)基于顶点或者边不相交的子同胚：算法CSMiner发现具有相同拓扑的近似结构； (4)基于不确定图上的子同构：算法MUSE计算每个候选项的期望支持度，根据期望支持度 寻找近似结构；（5)基于替换概率：算法gAppr〇X、APGM和VEAM依据顶点或者边的替换矩阵 寻找近似结构。在众多图近似匹配方法中，噪音和图失真现象的存在使得具有较强容错能 力的图编辑距离倍受青睐。在基于图编辑距离的图近似匹配中，编辑操作的代价函数决定 着图结构的匹配过程。算法SUBDUE、RNGV和MaxAFG中的代价函数均不能很好地用于属性 图上，且算法SUBDUE和MaxAFG是在单个大图上挖掘频繁近似子图，大图上的频繁子图挖掘 和图集上的频繁子图挖掘存在本质不同：首先，支持度的定义不同；其次，子图搜索过程不 同。针对以上不足，本发明提出一种面向属性图集的频繁近似子图挖掘方法。
【发明内容】
[0004] 本发明的目的是提出一种利用具有较强容错能力的图编辑距离进行图近似匹配， 符合现实世界中噪声和图失真普遍存在的现象，从而可以发现更多有意义的重要模式的面 向属性图集的频繁近似子图挖掘方法。
[0005] 本发明的目的是这样实现的：
[0006] (1)输入属性图集D、支持度阈值〇、近似度阈值t和代价函数d;
[0007] (2)构造属性图集S:对属性图集D中顶点特征向量集和边特征向量集分别进行聚 类，根据簇心特征向量构造一个新的图集S;之后在属性图集D和S上进行频繁近似子图搜 索；
[0008] (3)挖掘频繁近似顶点：根据属性图集D和S、两个阈值〇和t、代价函数d，挖掘 只包含一个顶点的频繁近似子图，将频繁近似顶点的三个相关信息加入到集合C，令频繁 近似子图集F=C;
[0009] (4)子图扩展：对于每个子图PGC，找到子图P在属性图集S中的扩展边集 ExtSet(P,S)，对于每条扩展边esGExtSet(P,S)，将子图P和边es连接得到扩展子图P' =P°es;同时计算扩展子图P'的三个相关信息：子图P'的最小DFS编码Min(P'）、子图P' 在图集S中的同构嵌入集0(P'，S)和子图P'在图集D中的近似嵌入集0(P'，D);
[0010] (5)计算扩展子图P'在属性图集D中的支持度，若supp(P'，D)彡〇，则有F=FUP'，并重复步骤（4)，直至所有子图均被发现或者子图的支持度小于支持度阈值〇 ;
[0011] (6)输出频繁近似子图集F;
[0012] 所述代价函数d，设〈Qi，Qj>是图编辑路径中的中一个编辑操作，其中以是Qi的第 k个特征值，qk是Qj的第k个特征值，d(<Qi，Qj>)表示编辑操作〈Qi，Qj>的代价函数，则有：
[0014] 近似嵌入集，给定图P，图G，图gi，其中图gi是图G的一个子图，若图P和图§1是 近似图，则称图gi是图P在图G中的一个近似嵌入；用o(P，G)表示图P在图G中的近 似嵌入集，则有〇(P，G) = {gi|gi是图G的子图，图P和图§1是t-近似图};用〇(P，D)表 示图P在图集D中的所有近似嵌入，则有0(P，D)=U^dO(P，G)。
[0015] 所述的t-近似图，给定两个图GpGj和近似度阈值t，如果G种G」的图编辑距 尚不大于1_T，即dism%，Gj) < 1_t，则称图Gi和图G』是t-近似图。
[0016] 在所述的属性图集D和S上进行频繁近似子图搜索，以属性图集S中的图为基准 进行子图搜索，同时根据属性图集D、两个阈值〇和t、代价函数d来判断子图是否为频繁 近似子图，图GsgS，存在子图gsGGs，若在属性图集D中存在包含子图gD的图GD，使得gD 和T-相似图，且图GD的个数不小于fX|D|，即supp(gs，D)彡〇，则称子图频繁近 似子图；接着在图集S中查找子图gs的所有扩展边，根据每条扩展边对子图gs进行扩展得 到新的扩展子图，并判断扩展子图是否为频繁近似子图；按照上述过程遍历属性图集S中 的所有子图，同时根据属性图集D、两个阈值〇和t、代价函数d找出所有频繁近似子图。
[0017] 本发明的有益效果在于：
[0018] 本发明提出一种面向属性图集的频繁近似子图挖掘方法，首先利用聚类算法将属 性图集中连续数值型特征向量分割成离散特征向量，从而构建一个新的属性图集S，方便子 图的搜索；然后在图近似匹配过程中采用具有较强容错能力的图编辑距离，符合现实世界 中噪声和图失真普遍存在的现象，可以发现更多重要模式，具有更实际的应用前景。
【附图说明】
[0019] 图1是本发明提出的面向属性图集的频繁近似子图挖掘方法流程图；
[0020] 图2是本发明中构造属性图集S的流程图；
[0021] 图3是本发明中属性图集D和S中各一实例图；
[0022] 图4是本发明中频繁近似子图挖掘流程图；
[0023] 图5是本发明的结果索引树。
【具体实施方式】
[0024] 下面结合附图对本发明做进一步描述。
[0025] 本发明的相关内容：
[0026] (1)属性图D:属性图G= {V，E，Fv，FE}，其中V是顶点集，E是边集，Fv是顶点特征 向量集，FE是边特征向量集。
[0027] 在属性图D中，每个顶点有n个连续数值型属性，组成顶点的n维特征向量，图G 中所有顶点的特征向量组成图G的顶点特征向量集，即巧是由所有顶点的n维特征向量组 成的集合。同理每条边有m个连续数值型属性，组成边的m维特征向量，FE是图G中所有边 的m维特征向量组成的集合。
[0028] (2)构造属性图集S:首先对图集D中所有顶点的特征向量集和所有边的特征向量 集分别进行聚类，然后将图集D中每个图的每个顶点的特征向量和每条边的特征向量分别 用它们所在簇的簇心特征向量代替，从而得到图集S。所以图集S和图集D只有对应顶点和 边上的特征向量不同，其他完全相同。
[0029] (3)编辑操作的代价函数：图的编辑操作通常包括顶点的插入、删除、替换和边的 插入、删除、替换，代价函数定义了这六个操作相关的代价。设〈Qi，Q，是图编辑路径中的一 个编辑操作，&是1的第k个特征值，qk是L的第k个特征值，^〈QdQ，）表示编辑操作 〈Qi，Qj>的代价函数：
[0031] 第一个实例和第二个实例分别表示顶点或者边的删除或者插入的代价。如果第一 个实例表示插入的代价，则第二个实例表示删除Q 代价；如果第一个实例表示删除 的代价，则第二个实例表示插入Qi的代价。最后一个实例是替换操作的代价。
[0032] (4)图编辑距离：给定两个属性图匕和6』，若h为从图GjljGj的一条编辑路径， cost(h)表示编辑路径h的代价，如果{hi，…，hj表示从匕到h的编辑路径集合，则G廊Gj之间的编辑距离为
[0033]disn^G"Gj) =minke{1，...，m}cost(hk)
[0035] 其中，we(0, 1)为权重系数，根据需求设置。
[0036] (5)t-近似图：给定两个属性图GpGj和近似度阈值t，如果G河G」的图编辑距 尚不大于1_T，即dism%，Gj) < 1_t，则称图Gi和图G』是t-近似图。
[0037] (6)近似嵌入集：给定三个属性图P、G和gi，其中图gi是图G的一个子图，若图P 和图近似图，则称图§1是图P在图G中的一个近似嵌入。用o(P，G)表示属性图P 在属性图G中的所有近似嵌入，则有o(P，G) = {gi|gi是图G的子图，图P和图§1是t-近 似图}。用〇(P，D)表示属性图P在属性图集D中的所有近似嵌入，则有0(P，D)=UcdCKP， G)〇
[0038] (7)同构嵌入集：给定三个属性图P、G和gi，其中图gi是图G的一个子图，若图P 和图81是同构图，则称图81是图P在图G中的一个同构嵌入。用0(P，G)表示属性图P 在属性图G中的所有同构嵌入，则有0 (P，G) = {gi|gi是图G的子图，图P和图gi是同构 图}。用? (P，S)表示图P在图集S中的所有同构嵌入，则有0 (P，S) =U^ 9 (P，G0。
[0039] (8)子图P在图集X中的扩展边集ExtSet(P，X):给定图集X和子图P，子图P在 图集X中的扩展边集
le|e是子图匕的邻接边}。
[0040]由此可知，子图P在图集D中的扩展边集ExtSet(P，D) =U%e0(勵| {e|e是子图 PD的邻接边}，子图P在图集S中的扩展边集ExtSet(P，S) = 灣{e|e是子图己的 邻接边}。
[0041] (9)支持度：给定属性图P，属性图集D和支持度阈值f，则图P在图集D中的支持 度为
[0043] 其中|D|为图集D的基数。若supp(RDmc，则称图P为频繁近似图。
[0044] (10)频繁近似子图搜索策略：在频繁近似子图挖掘过程中，以图集S中的图为基 准进行子图搜索，同时根据图集D、两个阈值〇和t、代价函数d来判断子图是否为频繁近 似子图。假设图&￡S，存在子图83￡Gs，若在图集D中存在包含子图gD的图GD，使得gD 和&am p;是t-相似图，且图GD的个数不小于-X|D|，即supp(gs，D)彡〇,则称子图&是频繁 近似子图；接着在图集S中查找子图gs的所有扩展边，根据每条扩展边对子图§3进行扩展 得到新的扩展子图，并判断扩展子图是否为频繁近似子图。按照上述过程遍历图集S中的 所有子图，同时根据属性图集D、两个阈值〇和t、代价函数d找出所有频繁近似子图。
[0045] (11)频繁近似子图P的存储信息：每个频繁近似子图P保存三个信息：子图P的最 小DFS(DeepFirstSearch)编码Min(P)、子图P在属性图集S中的同构嵌入集0 (P，S)、 子图P在属性图集D中的近似嵌入集0 (P，D)。其中Min(P)是一个字符串，用于唯一表示子 图P; ? (P，S)是一个二元组集合，每个元组包含子图P在图集S中的同构嵌入子图Ps和嵌 入子图Ps所在图的标号n，即0(P，S) = {(Psl，ni)，…（PSi，ni)，一} ;0(P，D)是一个三元组 集合，每个元组包含子图P在图集D中的近似嵌入子图PD、嵌入子图PD所在图的标号n和嵌 入子图PD与子图P之间的图编辑距离dism(PD，P)，即0(P，D) = {(PD1，ni，dism(PD1，P))，… ，（PDi，叫，dism(PDi，P))，〇
[0046] (12)由子图P的三个信息计算扩展子图P'的三个信息：由于P' =P°e且e= (u,v)，所以，
[0047] l)Min(P'）：在Min(P)后加上扩展边e的编码得到；
[0048] 2) 0 (P'，S):将PSG0 (P，S)与es= (us，vs)GExtSet(P，S)连接得到扩展子图 Ps' =Ps°es，若子图Ps'和子图P'是同构图，将子图Ps'加入到0 (P'，S);
[0049]3)0(P'，D):将PDG0 (P，D)与eD=(uD，vD)GExtSet(P，D)连接得到扩 展子图PD' =PD。eD，计算dism(PD'，P'），若dism(PD'，P'）彡 1-t，将PD' 加入到 0 (P，，D);否则计算子图PD和子图P'的dism(PD，P'），若dism(PD，P'）彡1- 了，将 卩1)加入到@(?'，〇)中。其中，（118111(?1/，？'）=(118111(? 1)，？）+(1(〈61)，65>)+(1(〈￥1)，￥ 5>)，
。此计算过程展现了在图匹配过程中允许 顶点或者边的缺失或者特征向量不同。
[0050] 本发明包括如下步骤：
[0051] (1)输入属性图集D、支持度阈值〇、近似度阈值t和代价函数d。
[0052] (3)挖掘频繁近似顶点：根据属性图集D和S、两个阈值〇和t、代价函数d，挖掘 只包含一个顶点的频繁近似子图，将频繁近似顶点的三个相关信息加入到集合C，令频繁近 似子图集F=C。
[0053] (4)子图扩展：对于每个子图PGC，找到子图P在属性图集S中的扩展边集 ExtSet(P，S)，对于每条扩展边esGExtSet(P，S)，将子图P和边es连接得到扩展子图P' =P°es。同时计算扩展子图P'的三个相关信息：子图P'的最小DFS编码Min(P'）、子图 P'在图集S中的同构嵌入集0 (P'，S)和子图P'在图集D中的近似嵌入集0(P'，D)。
[0054] (5)计算扩展子图P'在属性图集D中的支持度，若supp(P'，D)彡〇，则有F= FUP'，并重复步骤（4)，直至所有子图均被发现或者子图的支持度小于支持度阈值〇。
[0055] (6)输出频繁近似子图集F。
[0056] 参照图1，本发明提出一种面向属性图集的频繁近似子图挖掘方法，具体包括以下 步骤：
[0057]S1，输入属性图集D、支持度阈值〇、近似度阈值t和代价函数d。
[0058]S2,构造属性图集S。
[0059] 参照图2,构造属性图集S具体包括如下步骤：
[0060] 321，输入属性图集0。
[0061] S22,对属性图集D中所有顶点的特征向量组成的特征向量集进行聚类；对属性图 集D中所有边的特征向量组成的特征向量集进行聚类。
[0062] S23,将属性图集D中每个顶点的特征向量用其所在簇的簇心特征向量代替，将属 性图集D中每条边的特征向量用其所在簇的簇心特征向量代替，其他保持不变。
[0063] S24,输出属性图集S。图3是属性图集D和S中各一实例图，图3(a)是属性图集 D中一个实例图GD，图3(b)是属性图集S中一个实例图Gs。由图3可知，图Gs是将图GD中 每个顶点的特征向量和每条边的特征向量分别用它们所在簇的簇心特征向量替换、其他保 持不变得到的。
[0064] S3,根据属性图集D和S、支持度阈值〇、近似度阈值t和代价函数d，进行频繁近 似子图挖掘。
[0065] 参照图4,频繁近似子图挖掘具体包括如下步骤：
[0066] S31，输入属性图集D和S、支持度阈值〇、近似度阈值t和代价函数山发出请求。
[0067]S32,挖掘频繁近似顶点集C，并令频繁近似子图集F=C。
[0068] S33,子图增长和频繁近似子图挖掘，包括两步：
[0069] 1)对于每个子图PGC，找到子图P在属性图集S中的扩展边集ExtSet(P，S)，对 于每条扩展边esGExtSet(P,S)，将子图P和边es连接得到扩展子图P' =P°es，计算扩 展子图P'的三个相关信息Min(P'）、0 (P'，S)和0(P'，D)。
[0070] 2)计算扩展子图P'的支持度，若supp(P'，D)彡〇，将子图P'加入到频繁近似子 图集F，即F =FUP'，并重复步骤D，直至所有子图均被访问过或者子图的支持度小于支 持度阈值〇。
[0071]S34,输出频繁近似子图集F。图5为频繁近似子图集F的索引树。其中每个结点 表示一个频繁近似子图，其中存储频繁近似子图相关的三个信息：最小DFS编码、子图在 属性图集S中的同构嵌入集、子图在属性图集D中的近似嵌入集。
【主权项】
1. 一种面向属性图集的频繁近似子图挖掘方法，其特征在于，包括如下步骤： (1) 输入属性图集D、支持度阈值σ、近似度阈值τ和代价函数d; (2) 构造属性图集S :对属性图集D中顶点特征向量集和边特征向量集分别进行聚类， 根据簇心特征向量构造一个新的图集S ;之后在属性图集D和S上进行频繁近似子图搜索； (3) 挖掘频繁近似顶点：根据属性图集D和S、两个阈值〇和τ、代价函数d，挖掘只包 含一个顶点的频繁近似子图，将频繁近似顶点的三个相关信息加入到集合C，令频繁近似子 图集F = C; (4) 子图扩展：对于每个子图P e C，找到子图P在属性图集S中的扩展边集 ExtSet (P, S)，对于每条扩展边ese ExtSet (P, S)，将子图P和边e s连接得到扩展子图P' = P 〇es;同时计算扩展子图P'的三个相关信息：子图P'的最小DFS编码Min (P'）、子图P' 在图集S中的同构嵌入集Θ (P'，S)和子图P'在图集D中的近似嵌入集0 (P'，D); (5) 计算扩展子图P'在属性图集D中的支持度，若supp(P'，D)彡σ，则有F = F U P'， 并重复步骤（4)，直至所有子图均被发现或者子图的支持度小于支持度阈值σ ; (6) 输出频繁近似子图集F。2. 根据权利要求1所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 所述代价函数d，设〈Qi，Q，是图编辑路径中的中一个编辑操作，其中^是Q i的第k个特征 值，qk是Q」的第k个特征值，d (<Q i，Qj>)表示编辑操作说，Q，的代价函数，则有：3. 根据权利要求1所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 所述的近似嵌入集，给定图P，图G，图gi，其中图gi是图G的一个子图，若图P和图g 1是 τ-近似图，则称图81是图P在图G中的一个近似嵌入；用〇 (P，G)表示图P在图G中的近 似嵌入集，则有。（P，G) = {gi|gi是图G的子图，图P和图81是τ-近似图};用0 (P，D) 表示图P在图集D中的所有近似嵌入，则有0 (P，D) =U d〇 (P，G)。4. 根据权利要求3所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 所述的τ-近似图，给定两个图Gp GjP近似度阈值τ，如果GJPh的图编辑距离不大于 I- τ，即disn^Gi, Gj) < I- τ，则称图Gi和图G』是τ -近似图。5. 根据权利要求1所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 在所述的属性图集D和S上进行频繁近似子图搜索，以属性图集S中的图为基准进行子图 搜索，同时根据属性图集D、两个阈值〇和τ、代价函数d来判断子图是否为频繁近似子 图，图Gse S，存在子图gse Gs，若在属性图集D中存在包含子图gD的图GD，使得gD和g 3是 相似图，且图Gd的个数不小于cpX|D|，即supp(gs，D)彡σ，则称子图83是频繁近似子图； 接着在图集S中查找子图gs的所有扩展边，根据每条扩展边对子图g s进行扩展得到新的扩 展子图，并判断扩展子图是否为频繁近似子图；按照上述过程遍历属性图集S中的所有子 图，同时根据属性图集D、两个阈值〇和τ、代价函数d找出所有频繁近似子图。
【专利摘要】本发明属于图挖掘技术领域，具体涉及一种面向属性图集的频繁近似子图挖掘方法。本发明包括：输入属性图集D；构造属性图集S；挖掘频繁近似顶点；子图扩展；计算扩展子图P’在属性图集D中的支持度；输出频繁近似子图集F。本发明提出一种面向属性图集的频繁近似子图挖掘方法，首先利用聚类算法将属性图集中连续数值型特征向量分割成离散特征向量，从而构建一个新的属性图集S，方便子图的搜索；然后在图近似匹配过程中采用具有较强容错能力的图编辑距离，符合现实世界中噪声和图失真普遍存在的现象，可以发现更多重要模式，具有更实际的应用前景。
【IPC分类】G06F17/30
【公开号】CN104899292
【申请号】CN201510306230
【发明人】潘海为, 高琳琳, 韩启龙, 战宇, 翟霄, 李文博
【申请人】哈尔滨工程大学
【公开日】2015年9月9日
【申请日】2015年6月8日
【技术领域】
[0001] 本发明属于图挖掘技术领域，具体涉及一种面向属性图集的频繁近似子图挖掘方 法。
【背景技术】
[0002] 频繁子图挖掘作为图挖掘中的重要任务，可以发现图中隐含的重要模式，而且挖 掘出来的模式可以用于进一步的研宄，例如分类、聚类和关联模式挖掘等。图匹配是频繁子 图挖掘中的关键步骤，目前存在两类图匹配方法：精确匹配和近似匹配。图精确匹配要求两 个图的结构和特征完全相同，虽然图精确匹配在数学上提供了严谨的方法，但是它只适用 于有限的问题中。由于现实世界中的对象常被噪声影响，且图建立过程中存在失真现象，例 如，属性值出现误差或者顶点和边的缺失等，所以图近似匹配在现实中的应用更为广泛。 [0003] 依据图近似匹配策略，近似子图挖掘方法主要分为五类：（1)基于图编辑距离：算 法SUBDUE、RNGV和MaxAFG探讨一个图潜在的编辑路径，并把最有可能的编辑路径作为候 选项；（2)基于-边的子同构：算法Monkey中允许边的缺失和边标号的替换，其中是边差异 阈值；(3)基于顶点或者边不相交的子同胚：算法CSMiner发现具有相同拓扑的近似结构； (4)基于不确定图上的子同构：算法MUSE计算每个候选项的期望支持度，根据期望支持度 寻找近似结构；（5)基于替换概率：算法gAppr〇X、APGM和VEAM依据顶点或者边的替换矩阵 寻找近似结构。在众多图近似匹配方法中，噪音和图失真现象的存在使得具有较强容错能 力的图编辑距离倍受青睐。在基于图编辑距离的图近似匹配中，编辑操作的代价函数决定 着图结构的匹配过程。算法SUBDUE、RNGV和MaxAFG中的代价函数均不能很好地用于属性 图上，且算法SUBDUE和MaxAFG是在单个大图上挖掘频繁近似子图，大图上的频繁子图挖掘 和图集上的频繁子图挖掘存在本质不同：首先，支持度的定义不同；其次，子图搜索过程不 同。针对以上不足，本发明提出一种面向属性图集的频繁近似子图挖掘方法。
【发明内容】
[0004] 本发明的目的是提出一种利用具有较强容错能力的图编辑距离进行图近似匹配， 符合现实世界中噪声和图失真普遍存在的现象，从而可以发现更多有意义的重要模式的面 向属性图集的频繁近似子图挖掘方法。
[0005] 本发明的目的是这样实现的：
[0006] (1)输入属性图集D、支持度阈值〇、近似度阈值t和代价函数d;
[0007] (2)构造属性图集S:对属性图集D中顶点特征向量集和边特征向量集分别进行聚 类，根据簇心特征向量构造一个新的图集S;之后在属性图集D和S上进行频繁近似子图搜 索；
[0008] (3)挖掘频繁近似顶点：根据属性图集D和S、两个阈值〇和t、代价函数d，挖掘 只包含一个顶点的频繁近似子图，将频繁近似顶点的三个相关信息加入到集合C，令频繁 近似子图集F=C;
[0009] (4)子图扩展：对于每个子图PGC，找到子图P在属性图集S中的扩展边集 ExtSet(P,S)，对于每条扩展边esGExtSet(P,S)，将子图P和边es连接得到扩展子图P' =P°es;同时计算扩展子图P'的三个相关信息：子图P'的最小DFS编码Min(P'）、子图P' 在图集S中的同构嵌入集0(P'，S)和子图P'在图集D中的近似嵌入集0(P'，D);
[0010] (5)计算扩展子图P'在属性图集D中的支持度，若supp(P'，D)彡〇，则有F=FUP'，并重复步骤（4)，直至所有子图均被发现或者子图的支持度小于支持度阈值〇 ;
[0011] (6)输出频繁近似子图集F;
[0012] 所述代价函数d，设〈Qi，Qj>是图编辑路径中的中一个编辑操作，其中以是Qi的第 k个特征值，qk是Qj的第k个特征值，d(<Qi，Qj>)表示编辑操作〈Qi，Qj>的代价函数，则有：
[0014] 近似嵌入集，给定图P，图G，图gi，其中图gi是图G的一个子图，若图P和图§1是 近似图，则称图gi是图P在图G中的一个近似嵌入；用o(P，G)表示图P在图G中的近 似嵌入集，则有〇(P，G) = {gi|gi是图G的子图，图P和图§1是t-近似图};用〇(P，D)表 示图P在图集D中的所有近似嵌入，则有0(P，D)=U^dO(P，G)。
[0015] 所述的t-近似图，给定两个图GpGj和近似度阈值t，如果G种G」的图编辑距 尚不大于1_T，即dism%，Gj) < 1_t，则称图Gi和图G』是t-近似图。
[0016] 在所述的属性图集D和S上进行频繁近似子图搜索，以属性图集S中的图为基准 进行子图搜索，同时根据属性图集D、两个阈值〇和t、代价函数d来判断子图是否为频繁 近似子图，图GsgS，存在子图gsGGs，若在属性图集D中存在包含子图gD的图GD，使得gD 和T-相似图，且图GD的个数不小于fX|D|，即supp(gs，D)彡〇，则称子图频繁近 似子图；接着在图集S中查找子图gs的所有扩展边，根据每条扩展边对子图gs进行扩展得 到新的扩展子图，并判断扩展子图是否为频繁近似子图；按照上述过程遍历属性图集S中 的所有子图，同时根据属性图集D、两个阈值〇和t、代价函数d找出所有频繁近似子图。
[0017] 本发明的有益效果在于：
[0018] 本发明提出一种面向属性图集的频繁近似子图挖掘方法，首先利用聚类算法将属 性图集中连续数值型特征向量分割成离散特征向量，从而构建一个新的属性图集S，方便子 图的搜索；然后在图近似匹配过程中采用具有较强容错能力的图编辑距离，符合现实世界 中噪声和图失真普遍存在的现象，可以发现更多重要模式，具有更实际的应用前景。
【附图说明】
[0019] 图1是本发明提出的面向属性图集的频繁近似子图挖掘方法流程图；
[0020] 图2是本发明中构造属性图集S的流程图；
[0021] 图3是本发明中属性图集D和S中各一实例图；
[0022] 图4是本发明中频繁近似子图挖掘流程图；
[0023] 图5是本发明的结果索引树。
【具体实施方式】
[0024] 下面结合附图对本发明做进一步描述。
[0025] 本发明的相关内容：
[0026] (1)属性图D:属性图G= {V，E，Fv，FE}，其中V是顶点集，E是边集，Fv是顶点特征 向量集，FE是边特征向量集。
[0027] 在属性图D中，每个顶点有n个连续数值型属性，组成顶点的n维特征向量，图G 中所有顶点的特征向量组成图G的顶点特征向量集，即巧是由所有顶点的n维特征向量组 成的集合。同理每条边有m个连续数值型属性，组成边的m维特征向量，FE是图G中所有边 的m维特征向量组成的集合。
[0028] (2)构造属性图集S:首先对图集D中所有顶点的特征向量集和所有边的特征向量 集分别进行聚类，然后将图集D中每个图的每个顶点的特征向量和每条边的特征向量分别 用它们所在簇的簇心特征向量代替，从而得到图集S。所以图集S和图集D只有对应顶点和 边上的特征向量不同，其他完全相同。
[0029] (3)编辑操作的代价函数：图的编辑操作通常包括顶点的插入、删除、替换和边的 插入、删除、替换，代价函数定义了这六个操作相关的代价。设〈Qi，Q，是图编辑路径中的一 个编辑操作，&是1的第k个特征值，qk是L的第k个特征值，^〈QdQ，）表示编辑操作 〈Qi，Qj>的代价函数：
[0031] 第一个实例和第二个实例分别表示顶点或者边的删除或者插入的代价。如果第一 个实例表示插入的代价，则第二个实例表示删除Q 代价；如果第一个实例表示删除 的代价，则第二个实例表示插入Qi的代价。最后一个实例是替换操作的代价。
[0032] (4)图编辑距离：给定两个属性图匕和6』，若h为从图GjljGj的一条编辑路径， cost(h)表示编辑路径h的代价，如果{hi，…，hj表示从匕到h的编辑路径集合，则G廊Gj之间的编辑距离为
[0033]disn^G"Gj) =minke{1，...，m}cost(hk)
[0035] 其中，we(0, 1)为权重系数，根据需求设置。
[0036] (5)t-近似图：给定两个属性图GpGj和近似度阈值t，如果G河G」的图编辑距 尚不大于1_T，即dism%，Gj) < 1_t，则称图Gi和图G』是t-近似图。
[0037] (6)近似嵌入集：给定三个属性图P、G和gi，其中图gi是图G的一个子图，若图P 和图近似图，则称图§1是图P在图G中的一个近似嵌入。用o(P，G)表示属性图P 在属性图G中的所有近似嵌入，则有o(P，G) = {gi|gi是图G的子图，图P和图§1是t-近 似图}。用〇(P，D)表示属性图P在属性图集D中的所有近似嵌入，则有0(P，D)=UcdCKP， G)〇
[0038] (7)同构嵌入集：给定三个属性图P、G和gi，其中图gi是图G的一个子图，若图P 和图81是同构图，则称图81是图P在图G中的一个同构嵌入。用0(P，G)表示属性图P 在属性图G中的所有同构嵌入，则有0 (P，G) = {gi|gi是图G的子图，图P和图gi是同构 图}。用? (P，S)表示图P在图集S中的所有同构嵌入，则有0 (P，S) =U^ 9 (P，G0。
[0039] (8)子图P在图集X中的扩展边集ExtSet(P，X):给定图集X和子图P，子图P在 图集X中的扩展边集
le|e是子图匕的邻接边}。
[0040]由此可知，子图P在图集D中的扩展边集ExtSet(P，D) =U%e0(勵| {e|e是子图 PD的邻接边}，子图P在图集S中的扩展边集ExtSet(P，S) = 灣{e|e是子图己的 邻接边}。
[0041] (9)支持度：给定属性图P，属性图集D和支持度阈值f，则图P在图集D中的支持 度为
[0043] 其中|D|为图集D的基数。若supp(RDmc，则称图P为频繁近似图。
[0044] (10)频繁近似子图搜索策略：在频繁近似子图挖掘过程中，以图集S中的图为基 准进行子图搜索，同时根据图集D、两个阈值〇和t、代价函数d来判断子图是否为频繁近 似子图。假设图&￡S，存在子图83￡Gs，若在图集D中存在包含子图gD的图GD，使得gD 和&am p;是t-相似图，且图GD的个数不小于-X|D|，即supp(gs，D)彡〇,则称子图&是频繁 近似子图；接着在图集S中查找子图gs的所有扩展边，根据每条扩展边对子图§3进行扩展 得到新的扩展子图，并判断扩展子图是否为频繁近似子图。按照上述过程遍历图集S中的 所有子图，同时根据属性图集D、两个阈值〇和t、代价函数d找出所有频繁近似子图。
[0045] (11)频繁近似子图P的存储信息：每个频繁近似子图P保存三个信息：子图P的最 小DFS(DeepFirstSearch)编码Min(P)、子图P在属性图集S中的同构嵌入集0 (P，S)、 子图P在属性图集D中的近似嵌入集0 (P，D)。其中Min(P)是一个字符串，用于唯一表示子 图P; ? (P，S)是一个二元组集合，每个元组包含子图P在图集S中的同构嵌入子图Ps和嵌 入子图Ps所在图的标号n，即0(P，S) = {(Psl，ni)，…（PSi，ni)，一} ;0(P，D)是一个三元组 集合，每个元组包含子图P在图集D中的近似嵌入子图PD、嵌入子图PD所在图的标号n和嵌 入子图PD与子图P之间的图编辑距离dism(PD，P)，即0(P，D) = {(PD1，ni，dism(PD1，P))，… ，（PDi，叫，dism(PDi，P))，〇
[0046] (12)由子图P的三个信息计算扩展子图P'的三个信息：由于P' =P°e且e= (u,v)，所以，
[0047] l)Min(P'）：在Min(P)后加上扩展边e的编码得到；
[0048] 2) 0 (P'，S):将PSG0 (P，S)与es= (us，vs)GExtSet(P，S)连接得到扩展子图 Ps' =Ps°es，若子图Ps'和子图P'是同构图，将子图Ps'加入到0 (P'，S);
[0049]3)0(P'，D):将PDG0 (P，D)与eD=(uD，vD)GExtSet(P，D)连接得到扩 展子图PD' =PD。eD，计算dism(PD'，P'），若dism(PD'，P'）彡 1-t，将PD' 加入到 0 (P，，D);否则计算子图PD和子图P'的dism(PD，P'），若dism(PD，P'）彡1- 了，将 卩1)加入到@(?'，〇)中。其中，（118111(?1/，？'）=(118111(? 1)，？）+(1(〈61)，65>)+(1(〈￥1)，￥ 5>)，
。此计算过程展现了在图匹配过程中允许 顶点或者边的缺失或者特征向量不同。
[0050] 本发明包括如下步骤：
[0051] (1)输入属性图集D、支持度阈值〇、近似度阈值t和代价函数d。
[0052] (3)挖掘频繁近似顶点：根据属性图集D和S、两个阈值〇和t、代价函数d，挖掘 只包含一个顶点的频繁近似子图，将频繁近似顶点的三个相关信息加入到集合C，令频繁近 似子图集F=C。
[0053] (4)子图扩展：对于每个子图PGC，找到子图P在属性图集S中的扩展边集 ExtSet(P，S)，对于每条扩展边esGExtSet(P，S)，将子图P和边es连接得到扩展子图P' =P°es。同时计算扩展子图P'的三个相关信息：子图P'的最小DFS编码Min(P'）、子图 P'在图集S中的同构嵌入集0 (P'，S)和子图P'在图集D中的近似嵌入集0(P'，D)。
[0054] (5)计算扩展子图P'在属性图集D中的支持度，若supp(P'，D)彡〇，则有F= FUP'，并重复步骤（4)，直至所有子图均被发现或者子图的支持度小于支持度阈值〇。
[0055] (6)输出频繁近似子图集F。
[0056] 参照图1，本发明提出一种面向属性图集的频繁近似子图挖掘方法，具体包括以下 步骤：
[0057]S1，输入属性图集D、支持度阈值〇、近似度阈值t和代价函数d。
[0058]S2,构造属性图集S。
[0059] 参照图2,构造属性图集S具体包括如下步骤：
[0060] 321，输入属性图集0。
[0061] S22,对属性图集D中所有顶点的特征向量组成的特征向量集进行聚类；对属性图 集D中所有边的特征向量组成的特征向量集进行聚类。
[0062] S23,将属性图集D中每个顶点的特征向量用其所在簇的簇心特征向量代替，将属 性图集D中每条边的特征向量用其所在簇的簇心特征向量代替，其他保持不变。
[0063] S24,输出属性图集S。图3是属性图集D和S中各一实例图，图3(a)是属性图集 D中一个实例图GD，图3(b)是属性图集S中一个实例图Gs。由图3可知，图Gs是将图GD中 每个顶点的特征向量和每条边的特征向量分别用它们所在簇的簇心特征向量替换、其他保 持不变得到的。
[0064] S3,根据属性图集D和S、支持度阈值〇、近似度阈值t和代价函数d，进行频繁近 似子图挖掘。
[0065] 参照图4,频繁近似子图挖掘具体包括如下步骤：
[0066] S31，输入属性图集D和S、支持度阈值〇、近似度阈值t和代价函数山发出请求。
[0067]S32,挖掘频繁近似顶点集C，并令频繁近似子图集F=C。
[0068] S33,子图增长和频繁近似子图挖掘，包括两步：
[0069] 1)对于每个子图PGC，找到子图P在属性图集S中的扩展边集ExtSet(P，S)，对 于每条扩展边esGExtSet(P,S)，将子图P和边es连接得到扩展子图P' =P°es，计算扩 展子图P'的三个相关信息Min(P'）、0 (P'，S)和0(P'，D)。
[0070] 2)计算扩展子图P'的支持度，若supp(P'，D)彡〇，将子图P'加入到频繁近似子 图集F，即F =FUP'，并重复步骤D，直至所有子图均被访问过或者子图的支持度小于支 持度阈值〇。
[0071]S34,输出频繁近似子图集F。图5为频繁近似子图集F的索引树。其中每个结点 表示一个频繁近似子图，其中存储频繁近似子图相关的三个信息：最小DFS编码、子图在 属性图集S中的同构嵌入集、子图在属性图集D中的近似嵌入集。
【主权项】
1. 一种面向属性图集的频繁近似子图挖掘方法，其特征在于，包括如下步骤： (1) 输入属性图集D、支持度阈值σ、近似度阈值τ和代价函数d; (2) 构造属性图集S :对属性图集D中顶点特征向量集和边特征向量集分别进行聚类， 根据簇心特征向量构造一个新的图集S ;之后在属性图集D和S上进行频繁近似子图搜索； (3) 挖掘频繁近似顶点：根据属性图集D和S、两个阈值〇和τ、代价函数d，挖掘只包 含一个顶点的频繁近似子图，将频繁近似顶点的三个相关信息加入到集合C，令频繁近似子 图集F = C; (4) 子图扩展：对于每个子图P e C，找到子图P在属性图集S中的扩展边集 ExtSet (P, S)，对于每条扩展边ese ExtSet (P, S)，将子图P和边e s连接得到扩展子图P' = P 〇es;同时计算扩展子图P'的三个相关信息：子图P'的最小DFS编码Min (P'）、子图P' 在图集S中的同构嵌入集Θ (P'，S)和子图P'在图集D中的近似嵌入集0 (P'，D); (5) 计算扩展子图P'在属性图集D中的支持度，若supp(P'，D)彡σ，则有F = F U P'， 并重复步骤（4)，直至所有子图均被发现或者子图的支持度小于支持度阈值σ ; (6) 输出频繁近似子图集F。2. 根据权利要求1所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 所述代价函数d，设〈Qi，Q，是图编辑路径中的中一个编辑操作，其中^是Q i的第k个特征 值，qk是Q」的第k个特征值，d (<Q i，Qj>)表示编辑操作说，Q，的代价函数，则有：3. 根据权利要求1所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 所述的近似嵌入集，给定图P，图G，图gi，其中图gi是图G的一个子图，若图P和图g 1是 τ-近似图，则称图81是图P在图G中的一个近似嵌入；用〇 (P，G)表示图P在图G中的近 似嵌入集，则有。（P，G) = {gi|gi是图G的子图，图P和图81是τ-近似图};用0 (P，D) 表示图P在图集D中的所有近似嵌入，则有0 (P，D) =U d〇 (P，G)。4. 根据权利要求3所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 所述的τ-近似图，给定两个图Gp GjP近似度阈值τ，如果GJPh的图编辑距离不大于 I- τ，即disn^Gi, Gj) < I- τ，则称图Gi和图G』是τ -近似图。5. 根据权利要求1所述的一种面向属性图集的频繁近似子图挖掘方法，其特征在于： 在所述的属性图集D和S上进行频繁近似子图搜索，以属性图集S中的图为基准进行子图 搜索，同时根据属性图集D、两个阈值〇和τ、代价函数d来判断子图是否为频繁近似子 图，图Gse S，存在子图gse Gs，若在属性图集D中存在包含子图gD的图GD，使得gD和g 3是 相似图，且图Gd的个数不小于cpX|D|，即supp(gs，D)彡σ，则称子图83是频繁近似子图； 接着在图集S中查找子图gs的所有扩展边，根据每条扩展边对子图g s进行扩展得到新的扩 展子图，并判断扩展子图是否为频繁近似子图；按照上述过程遍历属性图集S中的所有子 图，同时根据属性图集D、两个阈值〇和τ、代价函数d找出所有频繁近似子图。
【专利摘要】本发明属于图挖掘技术领域，具体涉及一种面向属性图集的频繁近似子图挖掘方法。本发明包括：输入属性图集D；构造属性图集S；挖掘频繁近似顶点；子图扩展；计算扩展子图P’在属性图集D中的支持度；输出频繁近似子图集F。本发明提出一种面向属性图集的频繁近似子图挖掘方法，首先利用聚类算法将属性图集中连续数值型特征向量分割成离散特征向量，从而构建一个新的属性图集S，方便子图的搜索；然后在图近似匹配过程中采用具有较强容错能力的图编辑距离，符合现实世界中噪声和图失真普遍存在的现象，可以发现更多重要模式，具有更实际的应用前景。
【IPC分类】G06F17/30
【公开号】CN104899292
【申请号】CN201510306230
【发明人】潘海为, 高琳琳, 韩启龙, 战宇, 翟霄, 李文博
【申请人】哈尔滨工程大学
【公开日】2015年9月9日
【申请日】2015年6月8日
最新回复(0)