随着社会的飞速发展以及数据采集设备的广泛应用,数据库中存储了大量数据。从数据中发现的知识能够帮助理解过去以及预测未来,因而推动了大量的数据挖掘技术的研究。图挖掘是一种重要的数据挖掘任务。在过去的数十年里,图分析受到越来越多来自数据挖掘社区的广泛关注。一个重要原因是图能够很好地捕获很多领域里数据的结构。特别是,在一些新兴领域如社交网络,传感器网络、生物信息网络里,越来越多的图数据被大量采集。分析图的需求催生了很多技术,包括对社群、离群点、模式的发现。在图中发现的模式可以帮助理解图的结构,进而用于决策、预测任务。本论文研究的对象是动态属性图。“属性”指一个顶点由多个属性描述,“动态”指顶点的属性值及顶点间的连接关系都会随时间变化。以一个社交网络图为例,里面顶点表示用户,边表示用户间的关联关系,每一个用户会由年龄、居住地、职业等多个属性描述,用户间的关联、描述用户的各个属性值都会随时间变化。动态属性图是动态图更一般的表现形式,在许多场景下,它是对数据自然且有力的表达。考虑动态性允许捕获演化模式,同时考虑多个属性则是使用先验知识定义了一个更大的模式空间,因为模式涉及更多可能的属性组合和属性、结构的关联。本研究提出在动态属性图里挖掘强关联(显著)的序列模式。序列里每一部分是一个事件集合,且相邻两部分间是强关联的。比如序列模式?{A}→{B}→{C,D}?表示,事件B与事件A是强关联的,事件集{C,D}与事件B是强关联的。在动态属性图里挖掘强关联序列模式,意义主要体现在两个方面。一方面,很多动态属性图相关的任务场景下,需要被挖掘的模式具有关联性(显著性)度量,比如在一个通信网络里需要挖掘得到各个节点告警之间的关联关系,来过滤不重要的告警以及定位告警根源。而传统的图模式挖掘侧重于得到频繁的图模式,如在一个图集合中挖掘频繁子图,在图序列数据库中挖掘频繁子图子序列。以频率作为主要度量可以过滤噪声,但可能发现一些频繁而不重要的模式。比如在图序列数据库或动态属性图里挖掘得到的频繁子图子序列,这些子图序列可能是一些频繁子图的随机组合,没有太大价值甚至会对用户产生误导。假设现在任务是找到子图出现的因果关联关系,如果子图g1,g2,g3频繁出现,挖掘频繁模式可能得到序列如?g1,g2,g3?,?g2,g3,g1?,它们以序列的方式呈现,但序列各部分间却没有太大的关联关系。这种场景下,频繁模式往往不能完成需求。另一方面,在动态属性图这个方向里,目前还没有相关的研究。虽然在时间-空间数据挖掘里有关于挖掘强关联序列模式的工作,但该处使用的数据集与图数据有较大差异,主要表现在时间-空间数据集里,一般一个事件对应唯一的时间-空间点,而在图数据里对位置的表示是离散的,这样自然地在同一个时间-空间点有多个事件同时发生。考虑多个事件同时发生会使搜索空间呈指数增长,极大地增加运行时间。这种演化模式能够获取图数据里的事件间的关联关系,作为进一步推断的基础。论文对研究对象、提出的模式以及中间的重要概念做了完整的定义,使用详细的例子进行说明,并对算法使用到的一些性质给出了简要的证明。这种强关联模式的定义使用了频率度量,用于保证序列不是一个噪声序列,min Init Sup和min T ail Sup两个参数限制满足条件的序列的每一个部分都具有足够大的支持度。另一方面使用一个显著性度量来保证序列各部分间的强关联关系,对应参数为min Sig。显著性的定义参考了涌现模式挖掘里的一些概念。涌现模式指在两个数据库里支持度具有显著差异的模式。在本研究中,给定一个近邻关系定义,对一个事件A,考虑它发生的所有位置,根据近邻关系可以得到一个近邻空间。如果事件B在近邻空间中发生的频率显著高于事件B发生的整体频率(两个数据库中的频率,其中一个可以认为是虚拟的),就认为A的发生与B的发生具有强关联关系,显著性度量定义为二者的比值。只有当考虑的项集B在近邻空间中的出现频率显著大于整体频率,显著性度量才会比较高,说明B的出现的确受A的出现影响较大。这样就对关联程度进行了量化。一个序列的显著性定义为各个部分显著性的最小值。同时考虑一个顶点上具有多个属性,使得模式空间大小呈指数增长,这就需要算法具有高效的剪枝策略。针对提出的模式,研究首先对模式空间建立了一个清晰的图像。所有模式可以组织成一棵模式树,并且可以视为具有两个维度。外层的剪枝起作用最大,但比较简单。因而优化主要集中于如何高效地做内层的剪枝。模式挖掘里常用的剪枝方法是利用度量的单调或反单调性质来提前停止搜索。然而提出的显著性度量并不直接具有单调或反单调性质。因而本研究的主要贡献之一是设计了一种上界过滤策略。也就是我们提出一个新的度量,它是原显著性度量的上界,同时具有反单调性质。这样在对模式空间的搜索过程中,对某个序列模式,可以先检验其显著性上界,如果上界已经不满足要求,则对应的子空间可以直接被剪枝。上界值可以提前进行计算,存储空间和时间开销很小,能够显著提升算法效率。研究设计了深度优先及广度优先的两种搜索算法,算法利用提出的上界过滤策略来剪枝搜索空间。这两种算法需要分别建立搜索结构来组织搜索以及方便后续剪枝。另一种剪枝策略是针对深度优先和广度优先搜索的特性,进一步对上界过滤方法进行优化。具体来说,是考虑到显著性上界的计算时间消耗小,于是在对整体的上界剪枝失败后,可以尝试缩小考虑的剪枝范围,充分挖掘剪枝可能。算法的主要过程是:预处理部分,对一个动态属性图,将其转换为描述趋势的趋势图以减少原始数据中噪声的干扰。使用任意一个垂直频繁模式挖掘算法找到所有频繁的(支持度大于min Init Sup)趋势集及对应的支持点的集合。然后对这些频繁趋势集建立深度优先或广度优先的搜索结构。以深度优先或广度优先策略对模式树搜索,显著的序列前缀和当前趋势集构成当前序列模式。首先使用序列的尾支持度(大于min Tail Sup)进行过滤。然后使用显著性上界值检验是否能够直接剪枝当前子树(是否小于min Sig),如果不能,再计算真实显著性。如此进行下去。算法包含3个参数,如何快速确定这些参数对用户来说非常重要。研究首先分析了每一个参数改变对中间结果及最终模式的影响。依据这个分析结果制定的主要策略是对参数从高往低进行尝试,因为高阈值具有非常好的剪枝效果,尝试的时间开销小。因为提出的是一个图模式挖掘里的新问题,没有直接可以对比的算法,所以实验部分主要对比了两种算法的性能,剪枝技术对算法运行时间的影响,以及三个不同参数对模式数目和时间开销的影响。为了检验提出模式的有用性,使用了两个真实世界的数据集,一个DBLP数据集,一个美国航班数据集。在这两个数据集上的量化实验结果表明,提出的剪枝技术能够显著提升算法效率,深度优先和广度优先对应的优化策略能进一步减少时间开销。在两个数据集上,两种算法的性能优劣不同,说明对不同的数据集应该采用不同的算法。扩展性实验表明,算法对属性数目具有很好的扩展性,这也是研究提出的剪枝技术要解决的主要问题。这意味着提出的算法允许用户把其它更多图信息编码成属性,从而大大增加了算法的适用性。同时,对挖掘出的模式的分析表明,算法的确能够得到有意义的强关联模式。比如对美国航班数据集,把挖掘出的模式的支持点标注在地图上,并且联系飓风的作用时间,发现挖掘出的模式能够解释航班运行状态的变化趋势。综上所述,本研究针对序列模式只使用频率作为唯一度量的缺点,提出在动态属性图中挖掘强关联的序列模式。研究提出了一种新的显著性度量,并且完整地定义了提出的挖掘任务。由于同时考虑了多个属性,搜索空间呈指数增长。为解决这个问题,设计了两种剪枝技术,包括基于度量值上界进行剪枝的策略。接着设计了深度优先,广度优先两种搜索算法,并分别进一步紧化上界提高剪枝效率。最后在两个真实数据集上做了定量实验,展示各个参数对算法效率和结果的影响,以及剪枝带来的收益。对挖掘结果的分析表明,得到的序列模式的确能够正确解释数据,帮助进一步理解数据。