频繁量化模式图挖掘及应用

频繁模式挖掘(FPM)是图数据研究领域的一个经典问题,单一大图上的FPM问题近年来受到了更加广泛的关注。该问题被定义为根据用户给定的频率阈值查找在大图(Graph)中频繁出现的所有模式图(Pattern)。近年来,人们见证了FPM在多个领域的广泛应用,例如社交网络分析、欺诈检测等。然而,面对新兴的应用需求,人们需要更具语义表达力的模式图及其挖掘技术。为此,在传统模式图的基础上,首先提出了量化模式图(Quantified Graph Patterns,QGPs)——一类具有计数量词约束的模式图,实现了模式图语义的扩展;其次设计了一种在分布式场景下挖掘QGPs的算法,提出了量化图模式关联规则(Quantified Graph Pattern Association Rules,QGPARs)及其挖掘技术,用于预测(社交)网络中实体之间的潜在联系,然后利用真实图和合成图数据,通过翔实的实验验证了QGPs挖掘算法的计算效率,通过与经典链接预测方法进行对比,发现QGPARs可以取得更高的链接预测准确性;最后通过与传统图模式关联规则(Graph Pattern Association Rules,GPARs)的链接预测结果进行对比,验证了QGPARs与GPARs之间在链接预测结果方面存在显著差异,也进一步验证了QGPARs在链接预测中的有效性。

图数据挖掘技术的研究与进展

生物信息学(蛋白质结构分析、基因组识别)、社会网络(实体间的联系)、Web分析(Web链接结构分析、Web内容挖掘和Web日志搜索)以及文本信息检索等的迅速发展积累了大量图数据,对于图数据的挖掘逐渐成为研究领域的热点。一些诸如聚类、分类、频繁模式挖掘的传统数据挖掘研究逐渐拓展到图数据领域。通过介绍现阶段图数据挖掘技术的研究进展,总结了图数据挖掘的特点、现实意义、主要问题以及应用场景,讨论并预测了图数据,尤其是不确定图数据研究的发展趋势和热点。

一种新的基于频繁闭显露模式的图分类方法

由于图模型能够准确地表示科学与工程领域中数据的关键特征,图挖掘逐渐成为了数据挖掘领域的热点研究内容.图分类是图挖掘的一个重要研究分支.提出了一种新的基于频繁闭显露模式的图分类方法CEP,其基本思想是首先挖掘频繁闭图模式,然后从闭图模式中得到显露模式,最后根据显露模式构造一系列分类规则.实验结果显示:在对化合物数据分类时,CEP在分类性能上优于目前最好的图分类方法.而且,领域专家容易理解和利用CEP产生的分类规则.

从不确定图中挖掘频繁子图模式

研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3-5个数量级,有很高的效率和可扩展性.

基于分割图集的频繁闭图挖掘算法

为了解决大规模图集挖掘算法PartGraphMining必须重复扫描图集才能得到全部频繁子图的缺点,提出了一种改进的IPMC算法,通过hash表保存同构图的hash地址和支持度,不必重复扫描图集就可快速得到全部频繁子图,再经过少量的子图同构判断得到全部频繁闭图。在实际数据集上运行的实验结果表明它比原算法的挖掘效率有所提高。

基于频繁模式图的多维关联规则挖掘算法研究

关联规则挖掘是数据挖掘领域中重要的研究分支,频繁项集或频繁谓词集的计算是其中的关键问题.本文针对包括多值属性的关系数据库,以多维关联规则挖掘为目标,研究频繁谓词集的计算方法,提出了MPG算法及IMPG增量算法.MPG算法通过构建频繁模式图MP-graph,按照深度优先搜索方法,动态挖掘频繁谓词集,只需扫描数据库一次.此外,该方法至多增加一次数据库扫描,就能扩展为IMPG算法,进行增量关联规则挖掘.文章分析了算法时间和空间性能,用实验说明了算法的有效性.

一种基于频繁模式有向无环图的数据流频繁模式挖掘算法

频繁模式挖掘中基于FP-growth的算法需要扫描两次事务数据库,预先给定支持度,且不支持时间敏感型数据。本文提出了一种基于频繁模式有向无环图的数据流频繁模式挖掘算法,它根据事务到来的时间给每个事务一个序号,每个事务中的数据项在存储前按数据项的顺序进行调整,频繁模式有向无环图的构建遵循这个顺序并用序号来记录事务与数据项的包含关系,模式增长过程只需要增加有向边上的序号。通过逆向遍历带有相同序号的有向边,产生条件模式基,根据动态定义的阈值抽取条件模式基信息,一次扫描数据库得到频繁模式。实验结果表明,本文算法的执行效率优于FP-growth算法,且存储节点的数目明显减少。

一种新的基于嵌入集的图分类方法

随着图数据收集技术在许多科学领域的发展,对图数据分类已成为机器学习和数据挖掘领域的重要课题.目前已经提出许多图分类方法.其中,一些图分类方法采用3步来构筑分类模型;一些图分类方法采用2步来构筑分类模型.这些方法在挖掘频繁子图或特征子图时,只考虑到子图的结构信息,而没有考虑到子图的嵌入信息.为此,在L-CCAM子图编码的基础上,提出了一种基于嵌入集的图分类方法.该方法采用基于类别信息的特征子图选择策略,不但考虑了子图的结构信息,而且在频繁子图挖掘过程中充分利用嵌入信息——嵌入集,通过一步即直接选择特征子图以及生成分类规则.实验结果表明:在对化合物数据分类时,在分类精度上该方法优于采用3步的图分类方法;在运行效率上该方法优于采用2步和3步的图数据分类方法.

基于类别信息的特征子图选择策略

选择频繁的特征子图在基于频繁子图的图数据分类中起着非常重要的作用。提出了一种基于类别信息的特征子图选择策略,即从候选的频繁子图中选出独有频繁子图和显著频繁子图作为特征子图。实验结果显示,在对化合物数据分类时,该选择策略在分类性能上优于SVM方法特征选择策略和CEP方法的特征选择策略。

基于数据流的大图中频繁模式挖掘算法研究

随着单个图数据规模的扩大以及应用领域的扩展,大规模单图的频繁模式挖掘的需求越来越强烈.传统的单机环境已经无法满足大规模图数据挖掘的要求,而现有的并行或者分布式环境下的挖掘方法,普遍受到并行性以及数据倾斜等问题的限制,论文在分析了现有的频繁模式挖掘算法后,提出了一种基于数据流的单个大图频繁模式挖掘方法.首先,建立基于数据流的频繁模式挖掘模型,将MapReduce模型中的“批”数据变成“微批”数据,提高了数据处理的并行度,并且其迭代方式也满足频繁子图挖掘的反单调性;其二,设计了数据流模型中的频繁模式检查、子图实例扩展以及正规编码计算等操作,实现了基于数据流模型的频繁模式挖掘算法;其三,为解决正规编码计算中的复杂性问题,提出了基于不变关系的正规编码计算策略以及基于编码树的优化策略,优化正规编码比未优化编码的计算性能提升了30%,基于编码树的优化策略比原始编码计算策略在性能上提升了10%;最后,对涉及的相关算法进行了实验测试,实验证明,算法提高了频繁模式挖掘的并行性,大幅度减少了大图的搜索空间,降低了正规编码的计算时间,相比于传统算法大规模单图中频繁模式挖掘的效率提升了30%.

从图数据库中挖掘频繁跳跃模式

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.

RAKING:一种高效的不确定图K-极大频繁模式挖掘算法

由于不确定图蕴含了指数级的可能图实例,基于确定图模型的频繁图模式挖掘算法通常难以在不确定图集合上高效运行.文中提出了一种不确定图数据集上的基于随机游走的K极大频繁子模式挖掘算法.首先,将每个不确定图转换为相应的确定图并挖掘候选频繁模式;然后,将候选频繁模式恢复为不确定图并生成极大频繁模式搜索空间;最后,通过随机游走以相同概率随机地选择K个极大频繁模式.理论分析和实验结果表明文中提出的算法能够高效地获得不确定图集合的K-极大频繁模式.

频繁子图挖掘研究综述

归纳了频繁子图挖掘方法的处理流程,分析评价了频繁子图挖掘的典型算法:广度优先搜索和深度优先搜索的频繁子图挖掘算法,概述了频繁子图挖掘研究的平台——图模型及其产生器,并对频繁子图挖掘方法未来研究方向进行了展望.

挖掘不确定频繁子图的改进算法的研究

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。

基于全局图遍历的加权频繁模式挖掘算法

为解决加权遍历模式挖掘问题,提出了一种从边加权有向图到顶点加权有向图的变换模型。基于该模型,提出了基于全局图遍历加权频繁模式挖掘算法。在该算法中,利用图全局拓扑信息评估遍历模式的加权支持度,将剪枝问题转化为模式可扩展性问题,进而利用可扩展模式的向下闭合特性产生候选模式集。实验结果表明,该算法是一个高效的基于图遍历的加权频繁模式挖掘算法。

基于联合意义度量的Top-K图模式挖掘

提出了一个新的研究问题:如何挖掘Top-K图模式,联合起来使某个意义度量最大化.利用信息论的概念,给出了两个具体问题的定义MES和MIGS,并证明它们是NP-难.提出了两个高效算法Greedy-TopK和Clus-ter-TopK.Greedy-TopK先产生频繁子图,然后按增量贪心方式选择K个图模式.Cluster-TopK先挖掘频繁子图的一个代表模式集合,然后从代表模式中按增量贪心方式选择K个图模式.当意义度量满足submodular性质时,Greedy-TopK能提供近似比保证.Cluster-TopK没有近似比保证,但比Greedy-TopK更高效.实验结果显示,在结果可用性方面,文中提出的Top-K挖掘优于传统的Top-K挖掘.Cluster-TopK比Greedy-TopK快至少一个数量级.而且,在质量和可用性方面,Cluster-TopK的挖掘结果非常类似于Greedy-TopK的挖掘结果.

基于中医方剂数据库的Top-Rank-k频繁模式挖掘算法

为降低中医(TCM)方剂频繁模式挖掘过程中对经验参数的依赖,提高挖掘结果的准确性,针对中医方剂的数据特点,提出一种基于带权无向图的Top-Rank-k频繁模式挖掘算法。该算法可以直接挖掘出频繁k-itemset(k≥3)而无需产生1-itemset和2-itemset,并随之快速回溯到核心药物组合的频繁项集所对应的方剂信息;此外,采用一种动态位向量(DBV)的压缩机制对无向图中边的权重进行压缩存储,以有效地提高算法的空间存储效率。分别对中医方剂数据集、真实数据集(Chess、Pumsb和Retail)和合成数据集(T10I4D100K和Test2K50KD1)进行测试和比较,结果表明该算法与i NTK和BTK相比具有更高的时间和空间效率,而且也可以应用于其他类型的数据集。

基于图论的化学分子数据挖掘研究

近年来,人们提出了很多频繁图模式挖掘的算法。首先分析了贪婪搜索策略,然后对各种不同的图数据挖掘的方法进行比较。受购物篮分析的影响,基于ILP方法引起了人们的重视。如何修改各种不同的图数据挖掘方法以适用化学分子数据的挖掘是人们研究的热点问题。因为化学分子不仅是标准的图结构,而且它有典型的频繁环和链结构,还有一些频繁出现的代表原子类型的结点,所以在这个领域有一些特殊问题需要考虑。

多关系频繁模式发现研究

频繁模式发现是数据挖掘的重要任务之一。现实数据通常存储于由多个关系组成的关系数据库中。传统的频繁模式发现方法只能直接完成单一关系中的模式发现,如果要完成多关系数据的挖掘,会产生操作复杂性和信息丢失等问题。多关系数据挖掘是当前数据挖掘研究中快速发展的重要领域之一。多关系频繁模式发现方法能够直接从复杂结构化数据中发现涉及多个关系的复杂频繁模式,避免了传统方法的局限。本文首先归纳多关系频繁模式发现方法的发生历史背景,其次分析总结多关系频繁模式发现方法,最后提出了多关系频繁模式发现将来发展需重点解决的问题和面临的挑战。

基于关联图的频繁闭模式挖掘

将关联图的数据挖掘思想应用到频繁闭模式的挖掘中,使用位向量的技术简化项集支持度的计算,构造关联图表示项集间的频繁关系。在此基础上,提出一种频繁闭模式挖掘算法,针对频繁闭模式的特点,结合剪枝策略、子集检测策略、搜索策略等技术手段,优化算法性能。实验结果表明,该算法在时间性能上优于经典的频繁闭模式算法CLOSET。