分布式事务型内嵌树模式挖掘

分布式事务型内嵌树模式挖掘 A Distributed Approach for Transactional Embedded Tree Pattern Mining first-author 赵文，男，硕士生，主要从事云计算和数据挖掘方面的研究. E-mail：wenzhao@whu.edu.cn 赵文，男，硕士生，主要从事云计算和数据挖掘方面的研究. E-mail： wenzhao@whu.edu.cn wenzhao@whu.edu.cn 武汉大学 计算机学院，湖北 武汉 430072 武汉大学 计算机学院，湖北 武汉 430072 School of Computer, Wuhan University, Wuhan 430072, Hubei, China School of Computer, Wuhan University, Wuhan 430072, Hubei, China 为了从大规模数据集中更高效地发现有价值的规则，本文提出一种迭代的频繁内嵌无序树模式挖掘算法：TETPM.同时设计了两个工作负载划分策略：TETPM-P和TETPM-E.TETPM-P由模式划分工作负载，而TETPM-E则通过模式实例来划分工作负载.实验评估表明，两种算法均可以有效地从大型数据集中挖掘频繁内嵌模式，TETPM-P适合于模式实例数更均衡的数据集，而TETPM-E则更适合规模更大的数据集. To efficiently discover interesting rules from massive tree data, we come up with an iterative algorithm for mining frequent embedded unordered tree pattern: TETPM. And we design two workload-partitioning strategies: TETPM-P partitions the workload by pattern, while TETPM-E partitions the workload by pattern embeddings. The experimental evaluation shows that both algorithms can efficiently mine patterns from massive real and synthetic datasets. And TETPM-P is more suitable for datasets in which patterns have well-balanced number of embeddings, while TETPM-E is more suitable for greater-scale datasets. 内嵌树模式 分布式模式挖掘 MapReduce 工作负载均衡 embedded tree pattern distributed pattern mining MapReduce workload balancing 引言 1 在大数据时代，很多庞大的数据都通过树形结构来表示和存储，如xml和json文件，RNA序列和软件使用记录等 [ 1 1 , 2 2 ] .在这些树形结构数据中寻找隐藏的规则或者模式有很多实际应用价值，如通过多个用户的购物记录来寻找频繁购买的商品，通过有共同特性的RNA序列寻找实际发挥作用的子序列来预测新RNA序列的性状等.因此，频繁树挖掘研究取得了重要的进展 [ 1 1 , 3 3 ~ 6 6 3~6 ] . 通常情况，挖掘无序的内嵌模式是一个NP完全问题 [ 7 7 ] .当前，挖掘树模式的背景通常分为事务型和单树挖掘.在事务型背景下，频繁模式来自于拥有很多相对小的树集合或数据库中.而在单树挖掘中，频繁模式出现在树的不同位置 [ 2 2 , 8 8 , 9 9 ] .大部分研究以事务型为主 [ 1 1 , 3 3 , 5 5 , 6 6 , 10 10 ~ 13 13 10~13 ] ，并且在大多数的事务型树模式挖掘算法中，只有少部分用来挖掘无序的内嵌模式 [ 3 3 , 6 6 , 12 12 ] .本文中，我们以事务型模式挖掘为研究对象. TreeMiner [ 1 1 ] 是一个基于等价类扩展的有序树模式挖掘算法. SLEUTH [ 3 3 ] 是对TreeMiner的扩展：它提出了无序模式的标准型验证，并将TreeMiner的前缀等价类扩展思想运用到挖掘无序模式上.为了避免产生重复的模式实例，SLEUTH为每个模式维护一个实例列表.同时SLEUTH为模式及实例列表定义了一个连接操作来计算新模式和新模式的实例列表.挖掘无序树模式的算法除了SLEUTH外还有TreeFinder [ 6 6 ] 、U3 [ 12 12 ] 等，但实验表明他们的性能均不如SLEUTH [ 14 14 ] . Google在2004年提出了一种通用的分布式大数据处理计算框架MapReduce [ 14 14 ] ，它有两种基本的计算接口：Map和Reduce. MapReduce将数据抽象为键值对来处理：Map一一处理每一个键值对，而Reduce则同时处理相同键的键值对集合并输出结果. Apache基于MapReduce模型开发了开源的分布式系统Hadoop [ 15 15 ] ，并实现了底层的分布式文件系统HDFS.但是，Hadoop上的MapReduce存在局限，其分布式计算逻辑抽象层次低，需要手工编写代码来完成，并且只提供Map和Reduce两个操作，表达力欠缺，中间结果存储在HDFS上也使得作业不够高效. 2012年，伯克利大学在MapReduce的基础上提出了一个基于内存的分布式计算框架Spark [ 16 16 ] ，其核心是弹性分布式数据集(resilient distributed datasets，RDD).它是基于内存处理的分布式数据的抽象概念，RDD上主要有变化(transformation)和动作(action)两种类型的操作，并且RDD之间会形成依赖，各个RDD根据依赖关系可以串联形成有向无环图(directed acyclic graph，DAG)，从而作业可以更加高效地执行，因此Spark更擅长运行迭代类型的计算. Spark解决了Hadoop的一系列缺陷，如通过引入分布式内存数据概念RDD，使用户更加专注于数据的计算而不是数据的分布，中间结果也以RDD的形式存在内存中，减少了与外存的交互，使得计算效率更高，多种变化和操作也让数据的计算更加灵活. 在工作节点间均衡负载是分布式系统运行效率的一个关键因素.现在的大部分并行挖掘算法 [ 4 4 , 17 17 , 18 18 ] 通常是把数据划分到不同计算节点上分别挖掘本地频繁的模式，再根据本地频繁的模式，再次挖掘出全局频繁模式.这样的计算方法相当于两次挖掘过程，在大数据背景下无疑会浪费很多的计算资源.这种计算方法同时也存在着两个问题：一是会产生很高的内存和I/O消耗，第一轮的计算产生的本地频繁模式会远多于最后的全局频繁模式；二是频繁模式的各个实例一般不会均衡地分布在数据库的各个树中，不同的计算节点上可能会出现大量的频繁模式，使得某些计算节点的工作量远远高于平均值.这两个问题通常会导致在支持度较低的情况下某些节点出现内存不足的异常. 现有的大部分树模式挖掘算法都是设计运行在单机上的，不适合运行在大数据集上. MRFSM [ 4 4 ] 是基于MapReduce的图挖掘算法，用来挖掘诱发图模式，它包含筛选和优化两个阶段的算法.筛选阶段：在Map过程挑选出本地频繁模式，并使用基于概率模型的预测来挑选出本地非频繁但可能全局频繁的模式，在Reduce过程中统计出所有被筛选出的模式；优化阶段：根据筛选阶段选择出的模式，计算其所有分区上的频繁度，并汇总得出所有全局的频繁模式. MRFSM采用了随机分布数据的方式使得所有的图以大致均等的方式分到所有计算节点上. MRFSE [ 17 17 ] 和FSM-H [ 18 18 ] 是两个迭代式频繁子图挖掘算法.它们都包含一个迭代计算的过程，即在每一次迭代中从规模为 k 的频繁图模式中挖掘出规模为 k +1的频繁图模式. MRFSE提出了两种数据分区即负载均衡算法：随机法和轮询法.上述三个基于MapReduce的算法都讨论了均等划分原始数据集的分配负载方法.本文在上述分布式图模式挖掘算法的启发下提出了迭代式的频繁无序树模式挖掘算法.在实验中，我们实现了MRFSM提出的Preliminary Approach(即在第一轮挖掘中计算每个本地频繁模式，在第二轮中计算所有的本地频繁模式的支持度并得到全局的频繁模式)，本文中称之为BASELINE方法. 本文的创新如下： 1) 研究了基于MapReduce的事务型频繁树模式挖掘方法，提出了一种分布式树模式挖掘算法TETPM，解决了大数据环境下的树模式挖掘问题； 2) 研究了大数据环境下计算任务的工作负载均衡问题，并针对TETPM提出了两种负载均衡方案； 3) 分别针对Hadoop和Spark实现了TETPM算法，并分别给出了各自的优化点及两者的运行效率对比. 相关概念 1 定义1(树)   一棵标记的有根树 T =( V , E , L , l )是一个连通的有向无环图，其中 V 和 E 分别为边和顶点的集合， L 是顶点和边的标记集合. l 是一个将 V 中的顶点 v 和 E 中的边( v i , v j )映射到 L 中惟一的一个标记 l ( v )和 l ( v i , v j )的函数.如果一棵树中每个顶点的孩子节点是有序的，则这棵树是有序的，否则是无序的. 无序树可能具有多个同构的有序树表示形式.为了更高效地挖掘频繁树模式, 需要一个过程来减少同一棵树的同构表示, 即有效地检查两棵树是否同构.为此, SLEUTH [ 3 3 ] 定义了树的标准形式的概念，本文不再对树的标准形式检测作阐述.可以很容易地证明：无序树 T 及其的所有同构树中仅有一棵树为标准形式. 定义2(作用域)   树中每个节点的作用域表示为一个三元组(start, end, level)，三元组中的元素分别表示在深度优先遍历中开始遍历、完成遍历时计数器的值和节点的深度(计数器在每次开始和完成一个节点的遍历时自增). 对于树 T ，给定两个节点 a 和 b ，通过它们的作用域可以确定二者之间是否为父子、祖先或兄弟关系.一棵树的节点作用域在一次深度优先遍历后即可计算出来. 定义3(内嵌映射)   对于一棵树 T 和模式 P ，定义映射关系 m ：1)对于 P 中任意顶点 x ， l ( x )= l ( m ( x ))；2)( x , y )是 P 中的一条边, 当且仅当 m ( x )是 T 中 m ( y )的祖先.将满足内嵌映射的模式称为内嵌模式. 对于树 T 中的模式 P ，通过一个元组来表示 P 在 T 中的一个实例，包含 T 中各对应节点作用域的start值.如 图 1 图 1 中，树1的各节点的作用域为： A (1，8，1)， B (2，5，2)， C (3，4，3)， D (6，7，2). 定义4(支持度)   对于模式 P 和树的集合 F ={ T 1 , …, T n }，若 P 在 m 棵树中各存在至少一个实例，则模式 P 的支持度为 m .同时其相对支持度为 m / n .本文默认使用相对支持度计算. 如果模式 P 的支持度不小于用户定义的最小支持度minsup，则模式 P 为频繁模式. 基于扩展的频繁模式挖掘算法 1 频繁内嵌无序树模式挖掘算法SLEUTH [ 3 3 ] 提出了无序树模式的标准型验证，并将TreeMiner的前缀等价类扩展思想运用到挖掘无序模式上.对于已知的频繁模式，它总是通过向这个频繁模式的最右孩子节点所在路径的某个节点连接上新节点来产生新的候选频繁模式(连接的新节点为新的候选频繁模式的最右孩子节点).我们将这个添加新节点过程中的已知频繁模式称为前缀(prefix)，添加的新节点称为元素(element，即新的模式的最右孩子节点)，元素由tag和aid组成，分别表示新节点的标记和所连接的孩子节点在前缀中的编号(本文中使用深度优先遍历的序号为树或模式中的节点编号，从1开始). 定义5(前缀等价类)   所有前缀相同的模式均从属于同一个等价类[ P ]，其中 P 指代前缀. 如 图 2 图 2 所示，等价类[ P ]中包含3个模式“ A B $ C D E $ $ $ $”、“ A B $ C D $ E $ $ $”和“ A B $ C D $ $ E $ $”，它们的前缀均为 P =“ A B $ C D $ $ $”.特殊地，所有单节点模式均从属于同一个前缀等价类，其前缀为空，所有的element的aid均为0. 为了更方便地计算模式的支持度，在计算过程中，每个模式的所有实例都和这个模式绑定在一起.用 L ( P )来表示模式 P 的实例列表，其中每个实例的完整匹配信息用一个三元组来表示：[ t , c , s ]， t 表示实例所在树的ID, c 表示实例所在树的路径节点(不包含最右孩子节点)作用域的start域集合， s 表示最右孩子节点的作用域. 定义6(模式扩展运算)   对于前缀相同的两个模式 p i =( p , e i )， p j =( p , e j )，定义运算⊗来计算模式 p i 和模式 p j 连接产生的结果：1)若 e i .aid≥ e j .aid，则： p 不为空时， p i ⊗ p j =( p i e , e )，其中 e = e j ； p 为空时， p i ⊗ p j =( p i e , e )，其中 e .tag= e j .tag， e .aid= e j .aid+1, 此种连接方式称为Cousin-join(简称为cs-join).2)若 e i .aid= e j .aid，则 p i ⊗ p j =( p i e , e )，其中 e .tag= e j .tag， e . aid = e i .dfs_num， e i .dfs_num为元素 e i 在 p i e 中的深度优先遍历编号，此种连接方式称为Descendant-join(简称为ds-join). 定义7(节点作用域关系)   对于同一棵树中的两个节点的作用域 s x 和 s y ，1)若 s x .start＜ s y .start且 s x .end＞ s y .end，称作用域 s x 包含 s y ，表示为 s x ⊃ s y ；2)若 s x .end＜ s y .start或 s x .start＞ s y .end，称作用域 s x 与 s y 不重合，表示为 s x http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257620&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257620&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257620&type=middle s y . 根据节点作用域的关系，判断两个进行cs-join或ds-join的模式的实例 l x 和 l y 是否能连接计算出新模式的实例条件如下：1)两个模式可以进行cs-join时，若两个模式的实例的最右孩子节点的作用域 s x 和 s y 满足 s x http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257620&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257620&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4257620&type=middle s y ，实例的路径编号相同，则可以连接这两个实例产生一个新的实例：新实例的 m 域为 l x 的 c 域加上 l y 的 s 域start值，新实例的 s 域等于 l y 的 s 域. 2)两个模式可以进行ds-join时，若两个模式的实例的最右孩子节点的作用域 s x 和 s y 满足 s x ⊃ s y ，实例的路径编号相同，则可以连接这两个实例产生一个新的实例：新实例的 c 域为 l x 的 c 域加上 l y 的 s 域start值，新实例的 s 域等于 l y 的 s 域. 对于某个包含规模 k 模式的前缀等价类，我们依次尝试对任意一对模式(包括自身和自身)进行⊗连接操作，可以产生新的模式，这些模式又可以根据不同的前缀组织成新的等价类.如 图 3 图 3 所示, 一个等价类扩展的示例，包含两个前缀为“ A B $$”模式的等价类，元素两两进行连接操作，可形成两个新的等价类. 根据等价类中的模式及实例列表以及支持度的定义，可以将等价类中非频繁的模式筛选掉，这样可以在等价类的扩展中只对频繁模式扩展(频繁的 k 个节点的频繁模式只能由频繁的 k -1个节点的模式连接产生)，最后即可得到所有的频繁模式等价类.为了避免扩展出非标准形式的树模式，在对元素连接操作时，仅选择在连接前缀之后为标准形式树的部分元素作为连接操作的左值. 本文方法 1 TETPM算法 2 在SLEUTH的基础上，我们提出了基于MapReduce的频繁内嵌无序树模式挖掘算法TETPM. TETPM采用迭代式的计算流程，在每一轮迭代中根据上一轮计算出的 k 规模的频繁模式生成 k +1规模(模式的规模指这个模式中包含节点数的个数)的频繁模式. TETPM算法分为两个阶段：准备阶段和迭代阶段( 图 4 图 4 ). 1) 准备阶段. TETPM在准备阶段将原始的树集合数据转化为规模为1的频繁模式( 图 4(a) 图 4(a) 和算法1分别给出了准备阶段的计算流程图和伪代码).假设输入的数据可以按行分割：即每一行可以惟一表示一棵树的编码串.根据深度优先遍历，可以将每个树节点表示为一对元组，其中每个节点可以对应一个规模为1的模式，根据每个节点生成一个模式，将此模式作为键，对应这个模式的实例作为值.这样，可以得到所有规模为1的模式及其实例列表.最后通过模式字符串划分实例列表，可以计算出每个模式的支持度，根据用户给出的minsup筛选出规模为1的频繁模式及其所有实例. 算法1  TETPM准备阶段 输入：数据集 F ，阈值minsup 输出：规模1频繁树模式及实例集合 map (tree) 1. depth_first_traversal (tree); //discover vertices 2. for each vertex 3.  converting and generation, emit(pattern, embedding) 4. end reduce (pattern, embeddings) 1. count support in embeddings for pattern 2. if frequent 3.   emit (pattern, embeddings) 4. end 2) 迭代阶段.迭代阶段根据输入的 k 规模的频繁模式生成 k +1规模的频繁模式( 图 4-(b) 图 4-(b) 和算法2分别给出了迭代阶段的计算流程图和伪代码).在每一轮的开始，TETPM将此轮的频繁模式实例列表缓存或广播到每一个节点，然后在每一次Map过程中，对当前的模式和每一个缓存在该节点上模式尝试进行cs-join或ds-join，若能进行cs-join或ds-join，则测试每一个实例对是否满足节点作用域关系，从而计算出新模式的实例.在Reduce阶段中统计每个模式的频繁度并根据阈值minsup筛选出频繁的 k +1规模频繁模式. 算法2  TETPM迭代阶段 输入：size- k 频繁模式 F ，阈值minsup 输出：size- k +1频繁模式 cache or broadcast F to each node map (pattern p ) 1. for each pattern q in F 2.    if p can docs-join with q 3.      try cs-join each embeddings in p and q 4.      emit new pattern 5.     else if p can do ds-join with q 6.      try ds-join each embeddings in p and q 7.      emit new pattern 8.    end 9. end reduce (pattern, embeddings) //same with that of preparation phase TETPM算法在Hadoop上的实现 2 在Hadoop平台上的算法实现中，我们使用默认的FileInputFormat和CombineInput-Format来控制输入数据的划分.为了减少筛选模式及实例列表而需要再做一次MapReduce计算，在Map阶段(统计频繁度阶段)将计算出的所有模式和实例列表根据模式输出到不同路径(不再使用默认的write方法输出结果，采用MultipleOutputs来进行指定路径输出)，同时在Reduce阶段将每个模式的频繁度输出到另一个路径，这样准备阶段或一次迭代只需要一次MapReduce作业就可以得到所有的模式和模式频繁度计数.在每一次迭代开始，可以根据频繁度计数，为数据的输入设置路径筛选器，从而只将频繁模式作为每次迭代的输入数据. 以 图 1 图 1 的树集合为数据集的TETPM算法运算过程如 图 5 图 5 所示. TETPM算法在Spark上的扩展 2 Spark在Hadoop的基础上，提供了一系列基于内存计算的分布式计算接口，即前文所说的基于RDD的变形和操作.又因为RDD是分布在内存中的分布式数据集合，RDD在多迭代间可以保留在内存中使得Spark特别适合进行迭代式的计算. 1) 准备阶段.输入的数据以RDD的形式分布在各个计算节点，该RDD的每个元素为一棵树的字符串表示，根据深度优先遍历，可以将每个元素转化为多个树节点表示(通过flatMap函数实现RDD的变形)，其中每个节点都可以对应一个规模为1的模式，根据每个节点生成一个模式和对应这个模式的实例.这样，可以得到所有规模为1的模式及其实例列表.最后通过模式字符串划分实例列表，计算出每个模式的支持度，根据用户给出的minsup筛选出规模为1的频繁模式及其所有实例.其中考虑到Spark的惰性计算模型，需要多次用到RDD，最好将其缓存在内存中. 2) 迭代阶段.在每一轮的开始，TETPM将此轮的频繁模式实例列表广播到每一个节点，同时对数据集合重分区(保证数据均衡)，然后通过flatMap对实例列表RDD变形：数据集合的每一个元素表示一个模式及其完整的实例列表，将这个模式与本计算节点上的完整实例列表中的每一个模式进行连接操作，可能产生0~2个新模式.这样的变形会将当前 k 规模的频繁模式转化为所有可能由此模式集合扩展生成的 k +1规模的模式，通过一个支持度计数过程即可得到频繁模式和筛选出 k +1规模的频繁模式. 负载均衡 2 Hadoop默认的数据划分方式为按照数据大小基于行划分(FileInputFormat)，在每行数据大致相等的情况下可以做到数据划分基本相等. Spark提供自带的分区方式为RDD分区：HashPartitioner和RangePartitioner.但是这两个分区方式都不能均衡地划分RDD，尤其是HashPartitioner.因此我们根据轮询算法实现了自己的模式分区方法：每一个键值对的分区ID均为上一个键值对分区的ID加1对总分区数取模. 我们将使用上述分区方法的TETPM称为TETPM-P.然而这样的分区方式依然会导致负载的不均衡，即不能保证由每个模式带来的计算相同，因此我们改变了模式实例列表的数据结构：将TETPM-P(即一个模式和其完整的实例列表)进行了展开和重组：将embeddings拆分，每一个都绑定上相应的pattern，原来一个元素的计算(一个模式实例列表与 n 个模式实例列表的所有连接操作)转变为一个模式实例与 n 个模式实例列表的连接操作，更加平衡了数据集合中各个元素的计算时间.将改变了数据结构的算法称为TETPM-E，它是基于模式实例分区的.但这样增加了支持度的计算时间. TETPM-P算法在得到新模式的同时即可根据实例列表计算支持度，一个模式的所有实例并不保证在一个节点上，所以还需要将实例列表根据pattern分组(增加shuffle操作)，才能分别计算出每一个模式的支持度，同时增大了数据集合，可能会带来一定的资源耗费.我们将在后面的实验阶段比较两者的性能. 图 6 图 6 显示了TETPM-P和TETPM-E中模式及模式实例的数据结构示例(针对于包含三个频繁模式的集合，模式分别有5、3、8个模式实例).假设将这些模式划分为两块处理，partition index表示分区编号，那么对于TETPM-P，节点1和节点2上的模式实例分别有13和3个(假设每个模式实例的计算量相等)，因此节点1的工作量约为节点2的4.3倍；对于TETPM-E，节点1和节点2上的模式示例均有8个，二者的工作量基本相等.同时，TETPM-E的RDD结构比TETPM-P多存储了13个键，因此，当模式的实例个数差别愈大，二者在工作负载的不均衡和数据量规模上的区别愈大. TETPM-P与TETPM-E的比较 2 如上节所说，TETPM-E的划分工作负载的最小计算单元工作在实例层面，而TETPM-P的划分工作负载的最小计算单元工作在模式层面，又因为每一个模式的计算量远不如每一个实例的计算量均衡，因此TETPM-E会比TETPM-P在负载均衡上更有优势，但是这也是以牺牲数据存取量为代价的：更冗余的数据结构会加大节点间的通信.还有另外一种工作负载划分方式，是以前缀等价类(见定义5)来划分，这样会完全消除计算时的节点间通信(不需要将模式广播至每个节点)，因为等价类的扩展仅以自身进行.但是这种划分方式对于大多数情况都不适用，等价类的数量远少于模式数量，而且不同等价类也很难衡量其计算量，因此要做到基本的负载均衡也几乎不可能，这在本文的前期实验中就已经凸现出来了，在后续的实验部分将不再对此种工作负载划分方式进行讨论. 实验结果与分析 1 实验环境和数据集 2 分别使用Java 1.8和Scala 2.10.5实现Hadoop和Spark上实验程序.实验集群为Hadoop 2.6.4和Spark 1.6.0, 拥有20个节点(其中一个为master，其余为slave节点)，每个节点包含两个6核12线程2.6 GHz的Xeon-E5 CPU，master节点配备256 GB内存，slave各节点配备128 GB内存.其中Spark程序默认运行在Spark on YARN模式上. 比较BASELINE方法、TETPM-P和TETPM-E的执行时间.其中Spark环境下运行的默认参数mode=yarn-cluster，driver memory=4 GB，executor memory=4 GB，executor number=20，executor core=12，parallelism=720. 在5个数据集上进行实验，这5个数据集分为两类：一类是合成数据集，一类是实际数据集.1)合成数据集.使用一个合成数据生成器 [ 1 1 ] 来创建数据集.默认的参数为：标记个数 N =100，主树的节点个数 M =10 000，最大深度 D =10，最大扇出 f =10，树的个数 T =100 000.使用三个合成数据集：SYN包含所有默认参数，F5的 f 为5，F15的 f 为15. 2)实际数据集. CSLOGS数据集为一个计算机科学网站的所有用户在1个月内的网页浏览记录，它包含了59 691个用户浏览记录树形结构.平均的树字符串的长度为23.3.随机地重复CSLOGS中的某些树，使其树的个数增长到十万得到一个大型数据集CSLOGS1M(随机性导致了CSLOGS1M的频繁模式个数大致不变). 表 1 表 1 给出了5个数据集的属性. Dataset # Trees # Labels Size/MB CSLOGS 59 691 13 355 6.22 CSLOGS1M 1 000 000 13 355 107.01 SYN 100 000 609 2.94 F5 100 000 104 2.79 F15 100 000 458 2.59 在计算过程中，中间结果所占内存会远大于原始数据集，以CSLOGS为例， 表 2 表 2 给出了TETPM-E和TETPM-P的中间结果占用内存近似值.实际过程中内存的消耗会大于中间结果的大小.因此当原始数据集增大到一定规模时，单机版的SLEUTH算法将不再可用. 4 MB 2 Phase TETPM-P TETPM-E 2 Preparation phase 62.1 82.4 1 st iteration 5.7 5.8 Iteration phase 2 nd iteration 4.9 40.8 3 rd iteration 2.7 6.3 实验结果分析 2 图 7(a) 图 7(a) 给出了5个数据集在支持度为0.02时不同规模的频繁模式个数分布， 图 7(b) 图 7(b) ~ (f) (f) 给出了TETPM-P、TETPM-E和BASELINE在Spark环境下，5个数据集上对应minsup分别取10种不同值时的运行时间. 结果显示BASELINE方法仅在一些小型且分布均衡的数据集上有较好性能，在某些较大数据集或低支持度下不可行(会出现OutOfMemory异常，因此BASELINE方法缺失部分结果, 如 图 7(b) 图 7(b) , (c) (c) ，而TETPM-P和TETPM-E在大数据集和低支持度下均能有效运行，且TETPM-E效率比TETPM-P效率更高. 考虑到BASELINE方法的运行方式，原始数据的划分很大程度上决定了运行效率.一个极端的情况，某几块数据的全局频繁子树实例较多，会导致运行时间和内存使用较多地偏向于这些数据块所在的计算节点(特别是频繁子树在每一代迭代中会不断连接，产生的后代频繁子树会极速地消耗内存).相对地，TETPM-P和TETPM-E则更能保证每个节点上的子树实例数量一致(在每一次迭代后，频繁实例会再一次均衡地分布至每个计算节点).这样，由频繁子树实例连接产生的实例数量也更加平衡，在避免了内存不足异常的同时减少了计算资源的耗费(某些计算节点在完成当前任务后，会等待所有节点计算完成才进行下一阶段的任务). 实验结果显示随支持度变化，TETPM-P运行时间变化较大，而TETPM-E则变化不大，说明对于TETPM-E而言，运行时间更多地被任务的分配而不是挖掘计算消耗(由于TETPM-E使用了更加冗余的数据结构，更多的资源消耗在数据的分发上，而一旦数据的再分区完成，每个节点都能很快地完成计算任务)，对TETPM-P而言，运行时间更多地取决于计算任务，而且受数据均衡性影响.这也说明了TETPM-E更适合规模更大的数据集，而TETPM-P更适合于频繁模式的实例数更均衡的数据集. 图 8 图 8 给出了单机环境(3.6 GHz CPU和8 GB RAM)下SLEUTH在5个数据集上的运行情况.结果显示，CSLOGS、F5、F15和SYN在串行的SLEUTH算法下运行效率远高于TETPM-E和TETPM-P算法，这是因为分布式算法相较于单机算法有一部分时间用来通过网络做数据交换(这里对应于MapReduce框架的Shuffle过程)，但是CSLOGS1M在单机环境下即使支持度为0.1时也会运行失败(抛出OutOfMemory异常，在 图 8 图 8 中未给出结果)，因此相较于SLEUTH算法，TETPM-E和TETPM-P只适合大数据场景. TETMP在Hadoop和Spark上的对比 2 选取大型数据集CSLOGS1M来比较TETMP-P和TETMP-E在Hadoop和Spark上的运行时间， 图 9 图 9 给出了实验结果.结果显示相同条件下Spark上的TETPM-P和TETPM-E的运行时间均优于Hadoop上的运行时间.由于Spark的中间结果不存储在外存上，因此不对二者运行时的IO消耗作对比. Spark和Hadoop上程序的运行时间受很多因素影响，包括内外存读写、网络速度、集群可用资源等都会影响程序运行效率，因此结果略有偏差，但是其趋势大致能反映算法执行效率. 并行度对TETPM的影响 2 在Hadoop上，可以人为控制数据分块的个数(对应Mapper的个数)从而达到控制并行度的效果，Reducer的个数可以直接设置.在CSLOGS1M上考察并行度，即Mapper和Reducer个数对实验结果的影响， 图 10 图 10 给出了实验结果(Mapper和Reducer的个数与并行敏感度比)，结果显示尽管降低并行度会增加算法的运行时间，但却可以极大地降低整个过程中的数据传输.由于TETPM-P的数据结构减少了冗余，其数据存取流量远小于TETPM-E，因此并行度的改变对其I/O消耗的影响远小于对TETPM-E的影响，因此图中显示的I/O消耗近乎稳定.在Spark环境下，在executor number和executor core两个参数不变的前提下，考察并行度parallelism对TETMP-P和TETPM-E的性能影响(为了避免增加并行度带来的内存溢出，driver memory和executor memory均默认设置为8 GB). 图 11 图 11 给出了在minsup设置为0.025的前提下，两个算法在5个数据集上的运行时间变化.结果显示，在GSLOGSIM上，两者在parallelism参数上均有一个运行效率最高的峰值，而且TETPM-E更适合较高的并行度；在CSLOGS、SYN、F5和F15上两者均无明显变化.原因在于TETMP-P划分出的任务远远不需要这么高的并行度，而TETMP-E更适合大数据集，在小数据集上因并行度增加带来的效率并不明显.在parallelism和executor core总数不变的前提下，考察executor number和executor core对运行效率的影响.实验结果(不再给出图表)表明，在executor core总数不变的前提下，executor的个数和core的分布对运行效率没有显著影响. 结论 1 本文提出并研究了基于MapReduce的两种频繁内嵌无序树模式挖掘算法: TETPM-P和TETPM-E.两种算法都以迭代方式运行. TETPM-P和TETPM-E在划分工作负载的方式上不同：前者按模式划分工作量，后者以模式的实例为单位划分工作负载.我们在实验中比较了这两种算法的性能，并与根据使用数据分区方案的BASELINE方法比较性能.结果表明，我们的两种算法都能很好地处理大数据集和低支持度，而BASELINE方法则不可行. TETPM-P和TETPM-E针对的都是事务型频繁树模式挖掘，即在数量庞大的树集合中挖掘出频繁的树模式，而对于单树挖掘，即在一棵大规模树中挖掘出频繁出现在该树的各个部位的树模式，这两种算法并不适用.这是因为TETPM-P和TETPM-E采用的是将树拆分为单个节点再组合的方式来寻找频繁模式，针对单棵树的情况，拆分之后每个节点之间都是可以组合的，这将是一个更加耗时的过程，因此两种算法均无法表现出较好的性能.下一步将针对单棵树的情况展开研究，扩展TETPM-P和TETPM-E算法. 参考文献 ZAKI M J. Efficiently mining frequent trees in a forest: Algorithms and applications [J]. IEEE Transactions on Knowledge and Data Engineering , 2005, 17 (8): 1021-1035. DOI: 10.1109/TKDE.2005.125. WU X Y, THEODORATOS D. Leveraging homomorphisms and bitmaps to enable the mining of embedded patterns from large data trees [C]// Database Systems for Advanced Applications . Switzerland: Springer-Verlag, 2015: 3-20. DOI: 10.1007/978-3-319-18120-2_1 http://dx.doi.org/10.1007/978-3-319-18120-2_1 . ZAKI M J. Efficiently mining frequent embedded unordered trees [J]. Fundamenta Informaticae , 2004, 66 (1): 33-52. LIN W Q, XIAO X K, GHINITA G, et al . Large-scale frequent subgraph mining in MapReduce [C]// International Conference on Data Engineering . New York: IEEE Press, 2014: 844-855. DOI: 10.1109/ICDE.2014.6816705 http://dx.doi.org/10.1109/ICDE.2014.6816705 . CHI Y, YANG Y R, MUNTZ R R, et al . HybridTreeMiner: An efficient algorithm for mining frequent rooted trees and free trees using canonical forms [C]// Statistical and Scientific Database Management . Berlin: Springer-Verlag, 2004: 11-20. DOI: 10.1109/SSDM.2004.1311189 http://dx.doi.org/10.1109/SSDM.2004.1311189 . TERMIER A, ROUSSET M, SEBAG M, et al . TreeFinder: A first step towards XML data mining [C]// International Conference on Data Mining . New York: IEEE Press, 2002: 450-457. DOI: 10.1109/ICDM.2002.1183987 http://dx.doi.org/10.1109/ICDM.2002.1183987 . KILPELAINEN P, MANNILA H. Ordered and unordered tree inclusion [J]. SIAM Journal on Computing , 1995, 24 (2): 340-356. DOI: 10.1137/S0097539791218202. DRIES A, NIJSSEN S. Mining patterns in networks- using homomorphism [C]// SIAM International Conference on Data Mining . Pennsylvania: SIAM, 2011: 260-271. DOI: 10.1137/1.9781611972825.23 http://dx.doi.org/10.1137/1.9781611972825.23 . WU X Y, THEODORATOS D. Homomorphic pattern mining from a single large data tree [J]. Data Science and Engineering , 2016, 1 : 203-218. DOI: 0.1007/s41019- 016-0028-7. ASAI T, ARIMURA H, UNO T, et al . Discovering frequent substructures in large unordered trees [C]// International Conference on Discovery Science . Berlin: Springer-Verlag, 2003: 47-61. DOI: 10.1007/978-3-540-39644-4_6 http://dx.doi.org/10.1007/978-3-540-39644-4_6 . ASAI T, ABE K, KAWASOE S, et al . Efficient substructure discovery from large semi-structured data [C]// SIAM International Conference on Data Mining. Pennsylvania: SIAM, 2002: 158-174. https://www.researchgate.net/publication/220906833_Efficient_Substructure_Discovery_from_Large_Semi-structured_Data HADZIC F, TAN H, DILLON T S, et al . Model guided algorithm for mining unordered embedded subtrees [J]. Web Intelligence and Agent Systems: An International Journal , 2010, 8 (4): 413-430. DOI: 10.3233/WIA-2010-0200. CHEHREGHANI M H, BRUYNOOGHE M. Mining rooted ordered trees under subtree homeomorphism [J]. Data Mining and Knowledge Discovery , 2016, 30 (5): 1249-1272. DOI: 0.1007/s10618-015-0439-5. DEAN J, GHEMAWAT S.MapReduce: Simplified data processing on large clusters [J]. Communications of the ACM , 2008, 51 (1): 107-113. DOI: 10.1145/1327452.1327492. The Apache Software Foundation.Apache Hadoop [DB/OL]. [2016-02-11] . http://hadoop.apache.org http://hadoop.apache.org . The Apache Software Foundation.Apache Spark [DB/OL]. [2016-01-04] . http://spark.apache.org http://spark.apache.org . LU W, CHEN G, TUNG A K H, et al . Efficiently extracting frequent subgraphs using MapReduce [C]// IEEE International Conference on Big Data . New York: IEEE Press, 2013: 639-647. DOI: 10.1109/BigData.2013.6691633 http://dx.doi.org/10.1109/BigData.2013.6691633 . BHUIYAN M, HASAN M A. An iterative MapReduce based frequent subgraph mining algorithm [J]. IEEE Transactions on Knowledge and Data Engineering , 2015, 27 (3): 608-620. DOI: 10.1109/TKDE.2014.2345408. 10.14188/j.1671-8836.2018.06.005 TP311 whdxxblxb-64-6-507 国家自然科学基金(61202035) 2017-12-20 2018-12-24 2020-11-30 版权所有© 2018 《武汉大学学报(理学版)》编辑部 Copyright © 2018 Journal of Wuhan University(Natural Science Edition). All rights reserved. 2018 武汉大学学报(理学版) 6 64