2018, Vol. 27
XML是可扩展标记语言(eXtensible Markup Language)的简称, 已经成为许多领域中数据交换、数据表示、数据存储的事实标准. 面对海量且不断产生的XML文档, 人们迫切需要从中发现有价值的信息和知识, 研究人员正在探索寻找合适的技术来解决与XML文档存储和分析相关的问题.
XML数据挖掘可分为XML文档结构挖掘和XML文档内容挖掘. 结构挖掘的主要目标是挖掘XML模式, 可以分为结构内挖掘(挖掘一篇XML文档内的结构)和结构间挖掘(挖掘多篇XML文档之间的结构). 挖掘出的频繁模式, 可在XML分类、XML聚类、XML索引、XML数据存储、XML数据压缩、XML查询、XML数据预测等多个XML相关领域获得应用. 例如: 通过用户访问模式挖掘改善网站架构; 将频繁查询作为结果缓存加快XML查询效率; 通过挖掘XML格式的订单数据进行消费者行为分析; 使用频繁路径作为特征向量来估量XML文档相似性从而用于XML文档分类、聚类. XML文档的结构信息可以通过解析表示在标签序列中, 因此, 我们可以将XML 文档树序列化, 借鉴序列挖掘算法对XML文档进行相应的频繁模式挖掘.
由于XML特殊的结构特点和表达含义, 对XML数据的挖掘具有更多的挑战性和创新性. 首先, XML本质上是基于树结构的, 传统的关系型数据库的数据挖掘方法不能直接被利用; 其次, XML的结构和文本内容一体化, 现有的方法还是以单独挖掘结构或者文本内容信息为主, 缺乏一体化的解决方案; 最后, 随着大数据时代的到来, 从因特网上获取XML文档成为主流应用, 因此找到代价(如内存资源)和精度平衡的解决方法成为重要任务之一. 本文提出一种XML文档序列的频繁路径挖掘算法PXFP(PrefixSpan-based mining for XML Frequent Paths). 它通过对XML文档的序列化来形成基于前缀技术的序列模式挖掘工作, 期望获得更高的时间和空间效率.
1 相关工作序列模式挖掘问题是最初由Agarwal等人[1]开创性提出, Agarwal等人借鉴频繁项目挖掘算法提出了AprioriAll算法, 该算法基于先产生后测试的策略, 依据的原理是所有频繁序列的子序列也都是频繁的. 1996 年, Srikant 和 Agrawal 又提出了 AprioriAll 算法的扩展算法 GSP 算法[2], 它考虑了时间约束、滑动时间窗口和分类层次技术, 从而大大地减少了产生的候选序列的数量, 减少了时间和空间开销. 然而由于类 Apriori 算法自身存在的局限性, 学者们纷纷开始寻找更高效的方法. 2000 年, Han 等人提出了基于模式增长的 FP-growth 算法, 该算法不产生候选集, 而是通过 FP-tree 的树状结构压缩数据库, 然后再利用 FP-tree 从下向上挖掘频繁序列, 加快了挖掘过程[3]. 其后, 学者们又研究并提出了一系列基于前缀思想的算法, 包括 Han 和 Pei 于 2000 年提出的 FreeSpan 算法[4]和2001 年提出的PrefixSpan算法[5], 其基本思想是: 递归地将当前挖掘的频繁序列作为前缀, 计算每一前缀的后缀, 生成投影数据库, 在每个投影数据库上进行子序列的增长. 这一过程将每一次的检验范围缩小到更小的投影数据库中, 降低了搜索代价. 这些都是经典的序列挖掘算法.
近年来, 在经典序列挖掘算法的基础上, 学者们相继提出了优化的序列挖掘算法. 2007年, 张坤等人针对PrefixSpan算法存在大量重复投影数据库的问题, 提出一种名为SPMDS的算法[6]运用哈希值判断投影数据库是否重复, 通过建立索引加快了检索速度, 进而提高了算法的性能. 2009年, 张利军等提出一种基于位置信息的序列模式挖掘算法PVS[7], 在PrefixSpan算法的基础上, 通过记录每个已产生的投影数据库的位置信息降低投影数据库的冗余, 提高了算法效率. 2012年, 刘栋等提出了基于Map Reduce的序列挖掘模式, 采用Hadoop分布式平台, 将PrefixSpan算法扩展到大数据集[8]. 2013年, 吴信东等设计了一种带有通配符的模式挖掘算法, 通配符的加入使模式的形式更加灵活[9]; 2015年, 刘端阳等首次在频繁序列模式挖掘算法中引入逻辑的思想, 提出了一种基于逻辑的频繁序列挖掘算法LFSPM, 通过逻辑规则对中间结果进行过滤, 该算法较好地解决了支持度阀值的设定问题, 并提高了挖掘结果的可理解性[10]. 2015年, Kaustubh Beedkar等提出了用于挖掘具有层次结构的频繁序列的并行算法[11], 并将其设计为可以扩展到大数据集.
XML频繁模式挖掘作为XML数据挖掘的重要研究方向之一, 也获得了许多学者的关注. 2005年, Leung Ho-pong等人提出的PBClustering算法将频繁路径作为特征向量来计算XML文档的相似度[12], 从而进行聚类. 其中频繁路径挖掘的具体方法是将每个XML文档树表示为Xpath路径集合, 然后利用AprioriAll序列挖掘算法来挖掘XML文档集的频繁路径. 2008年, 贝毅君提出了基于等价类的频繁标签序列挖掘算法XSM[13], 该算法将XML序列构建成垂直数据库, 通过应用概念格理论、以不同前缀为基础将标签序列分成互不相交的前缀等价类, 通过合并等价类产生频繁标签序列, 递归地从等价类中挖掘频繁标签序列, 该算法在实验数据集中取得了较好的时间性能. 2012年, 雷向欣等提出了数据流分页频繁子树挖掘模型Tmlist[14], 对XML数据流进行分页, 管理跨页节点及频繁候选子树的跨页增长, 逐页挖掘频繁子树, 在可控误差范围内降低了空间消耗, 提高了挖掘效率. 2013年, 李巍等提出了一种根据XML数据变化过程挖掘XML空间频繁变化结构SFCS的方法和发现SFCS的数据模型SC-DOM[15], 实验证明了算法的有效性和可扩展性.
2 相关的定义定义1. XML树模型. 一个XML文档的结构使用树XT(r, V, E, L, f)来表示. 其中, r是树的根节点; V是树的节点集合; E是树的边集合, 每条边(v1, v2)∈E表示节点v1是节点v2的父节点; L表示标签集合; f是从节点集合到标签集合的一个函数映射f: V->L.
例子1. 图1给出了一个XML文档对应的树结构, 其中: 它的根节点r=n1; 树的节点集合V={n1, n2, n3, n4, n5, n6, n7, n8, n9}; 边集合E={(n1, n2), (n2, n3), (n2, n4), (n2, n5), (n3, n6), (n4, n7), (n5, n8), (n5, n9)}; 树的标签集合L={a, b, c, d, e, f, g}; 节点集合到标签集合的一个函数映射f: {n1-> a, n2-> b, n3-> c, n4-> e, n5-> e, n6-> d, n7-> f, n8-> f, n9-> g}.
|
图 1 XML文档树模型示例 |
定义2. XML树的标签序列表示. 对XML文档树进行广度优先遍历, 即按层序从左到右输出XML树的每个节点的标签, 得到XML树的标签序列被称为该XML树的标签序列表示.
例子2. 图1中XML树的标签序列表示为<a, b, (c, e, e), (d, f, f, g)>. 注: 同层如果有多个标签用括号括起来, 如果只有一个标签, 括号可以省略.
定义3. XML树的标签路径. XML树的一个标签序列被表示为A=<a1, a2, ..., an>. 假如在A中ai均是ai+1的父节点(0<i<n), 则称序列A为该XML树的一条标签路径.
例子3. 对应图1中XML树, <a, b, c, d>, <a, b, e, f>和<a, b, e, g>都是它的标签路径.
定义4. 前缀路径. 对于路径A=<a1, a2,...an>和序列B=<b1, b2,...bm>, n≤m, 满足a1⊆b1, a2⊆b2,..., an⊆bn, 则称A是B的一个前缀路径, 简称前缀.
例子4. 对于标签序列数据B=<a, b, (c, e, e), (d, f, f, g)>. 依据定义4可知: 路径A=<a, b, c, d>是B的前缀, 但是C=<a, c, d>不是B的前缀. 当然B的前缀不止一个, 比如<a>, <a b>, <a b c>, <a b e>, <a b e f>, <a b e g>也都是B的前缀.
定义5. 直接后缀. 路径A={a1, a2,...an}是序列B={b1, b2,...bm}的前缀, 当n<m时, bn+1中an的子节点的集合被称为A在B上的直接后缀; 当n=m时, A在B上的直接后缀为空.
例子5. 在图1中, 令A=<a, b, c>, B=<a, b, (c, e, e), (d, f, f, g)>, 则A在B上的直接后缀为<d>. 这是因为在图1中, <(d, f, f, g)>中只有d是c的子节点.
定义6. 位置信息. 一个路径A={a1, a2,...an}在一个XML树中的位置信息用一个3元组来表示, 记为(s, v, m), 其中s表示XML标签序列数据库S中包含该路径的序列的序号; v表示对应的序列中该路径的结束位置为XML树的第几层; m表示该路径的结束位置在XML树该层的第几个. 当一个路径在数据库中多次出现时, 这个路径的位置信息表示为向量((s1, v1, m1), (s2, v2, m2), …, (sk, vk, mk)).
例子6. 对于图1(假设数据库中只有图1所示一篇XML文档), 路径A=<a, b, c>的位置信息可以表示为(1, 3, 1); 路径B=<a, b, e, f>的位置信息可分别表示为(1, 4, 2), (1, 4, 3).
3 PXFP算法 3.1 从XML文档集中挖掘频繁路径的基本步骤XML文档是半结构化数据, 对其进行频繁路径挖掘可以分为两步: XML文档序列化和序列挖掘, 基于此将从XML文档集中挖掘频繁路径的过程划分为五个阶段, 如图2所示.
|
图 2 从XML文档集中挖掘频繁路径的基本步骤 |
(1) 序列化阶段: 依据XML文档的树形结构和定义2得到XML标签序列. 此外为了不遗漏XML文档树的结构信息, 将每个节点表示为“节点: 父节点”的形式(根节点除外), 最终实现XML文档的序列化, 作为数据挖掘的格式化数据来用于分析.
(2) 频繁节点阶段: 找出支持度不小于阀值的频繁节点, 构造Hash映射表, 将频繁节点标签与数字一一对应.
(3) 转化阶段: 将频繁节点根据Hash表映射为数字同时去掉不频繁的节点, 得到转化后的序列数据库作为频繁路径挖掘阶段算法的输入.
(4) 频繁路径挖掘阶段: 本文将设计PXFP算法来完成这一工作. 算法的整体思想是: 首先扫描数据库来获取1阶频繁序列L1, 假设L1={1, 2, 3, 4}, 然后依次以L1中的元素为前缀递归挖据频繁序列…深度优先直到不再有更长的前缀产生时, 再以2为前缀…以此类推, 直到遍历过L1中所有元素后停止. 规范化的算法描述见4.2节.
(5) 最大频繁路径阶段: 去除频繁路径中包含于其他频繁路径中的子路径, 得到最大频繁路径.
下面以一个实例来介绍XML频繁路径的挖掘过程. 给定3个待挖掘的XML文档树, 如图3所示, 令支持度阀值为0.5.
|
图 3 待挖掘的XML文档树 |
(1) 序列化阶段
对各个XML文档树进行层序遍历, 即按照广度优先的策略按层序从左到右输出XML树的每个节点. 如图3中的XML树(1), order(第一层)(person, item) (第二层) (name, address, book) (第三层). 得到的XML标签序列集合如表1所示, 该集合表示出了XML树的层级关系.
|
表 1 XML文档的序列化表示 |
此外, 为了不遗漏XML文档树的结构信息, 需要将XML文档树的边, 即父子节点间的对应关系表示在序列中. 由于每一个节点都有且只有一个父节点(根节点除外), 因此把每个节点表示为“节点: 父节点”的形式(根节点除外). 例如: 对于XML树(1), 其标签序列表示为<order, (person, item), (name, address, book)>, 序列化的结果为 <order, (person: order, item: order), (name: person, address: person, book: item)>. 可以用同样的方式处理另外两个XML文档树,表1给出了序列化的结果.
(2) 频繁节点阶段
很显然, 一个频繁路径中的所有节点必须频繁, 所以发现频繁节点是挖掘频繁路径的基础性工作. 这个阶段相对比较简单, 只需要找出所有支持度不小于50%的节点即可. 这里的支持度是指出现该路径的文档数与总文档数的比值. 实际操作中, 将频繁节点映射成连续的整数, 结果如表2所示, 这样的映射纯粹是为了处理的方便和高效, 减少内存空间的占用.
|
|
表 2 支持度不小于50%的频繁节点 |
(3) 转换阶段
根据前一阶段得到的频繁节点集, 构造Hash映射表, 将频繁节点的标签与数字一一对应, 将频繁节点根据Hash表映射为数字同时去掉不频繁的节点得到转换后的序列, 如表3所示. 这样做可以减少XML文档标签序列集的表示空间, 并加快后面的挖掘速度.
|
|
表 3 转换后的序列数据库 |
(4) 频繁路径挖掘阶段
将上一阶段得到的转换后的序列数据库作为频繁路径挖掘阶段算法的输入, 调用序列挖掘算法找出所有可能的频繁路径. 本文将设计PXFP算法来完成这一工作. 我们先通过本例来说明PXFP的基本思想, 规范化的算法描述将在4.2节来完成.
频繁路径挖掘阶段采用的算法是基于前缀的思想, 首先找到长度为1的前缀, 包括<1>, <2>, <3>, <4>, <5>, <6>, 我们需要对这6个前缀分别递归搜索各个前缀对应的频繁路径. 依据表3的序列数据库, 表4是长度为1的前缀对应的直接后缀.
|
|
表 4 长度为1的前缀的直接后缀 |
这里我们以前缀<1>为例来说明挖掘过程, 对其他前缀进行递归的方法和前缀<1>一样. 方法如下, 首先统计<1>的直接后缀的出现次数得到{2:3, 3:3}. 由于此时<2>, <3>均满足支持度阈值, 因此我们得到前缀为<1>的2阶频繁路径为<12>和<13>, 并记录下<12>的位置信息为(1, 2, 1)(2, 2, 1)(3, 2, 1), <13>的位置信息为(1, 2, 2)(2, 2, 2)(3, 2, 2). 接着我们分别递归<12>和<13>为前缀所对应的直接后缀. 首先看<12>前缀, 由<12>的位置信息找到其对应的直接后缀为<(45)>, <4>, <4>, 进行计数得到{4:3, 5:1}, 因此得到以<12>为前缀的3阶频繁路径为<124>, 并更新<124>的位置信息为(1, 3, 1)(2, 3, 1)(3, 3, 1). 由<13>的位置信息找到其对应的直接后缀为<6>, <6>, <6>, 进行计数得到{6: 3}, 因此得到以<13>为前缀的3阶频繁路径为<136>, 并记录下<136>的位置信息为(1, 3, 3)(2, 3, 2)(3, 3, 2). 继续递归以<124>和<136>为前缀的频繁路径. 由于前缀<124>和<136>对应的直接后缀为空, 因此不能产生4阶频繁路径. 至此以1为前缀的频繁路径挖掘结束, 产生的频繁路径为<1><12><13><124><136>. 同样的方法可以得到其他前缀对应的频繁路径. 频繁路径挖掘结果如表5所示.
|
|
表 5 频繁路径挖掘结果 |
(5) 最大频繁路径阶段
去除频繁路径中包含于其他频繁路径中的子路径, 得到最大频繁路径. 根据Hash表找到原始的最大频繁路径, 结果如表6所示.
|
|
表 6 最大频繁路径 |
3.2 算法描述
PXFP算法是基于序列前缀的XML频繁路径挖掘算法, 其目标是挖掘XML序列数据库中满足支持度阀值的频繁路径. 下面我们对PXFP算法做一个归纳总结.
算法. PXEP 算法
输入: 序列数据库S和支持度阈值αα
输出: 所有满足支持度要求的频繁路径集
1) 扫描序列数据库, 找到所有长度为1的序列模式L1, 作为初始的种子集;
2) 对于L1中的每一个元素, 依次取出一个元素作为新候选模式的前缀, 以此来划分搜索空间;
3) 令前缀的长度i=1;
4) 对于每个长度为i且满足支持度要求的前缀进行递归挖掘:
a) 找出前缀所对应的直接后缀, 并记录其位置信息. 如果直接后缀为空, 则递归返回.
b) 计算直接后缀中各项的支持度. 如果所有项的支持度小于阈值αα, 则删除其位置信息并递归返回.
c) 将满足支持度阀值的各个单项和当前的前缀进行合并, 令i=i+1, 得到若干新的前缀, 将其加入长度为i的序列模式Li分别递归执行第4)步.
5) 重复2)–4), 直到遍历完L1中的所有序列.
值得注意的是, 与从单个XML文档中挖掘关键模式不同, 在多XML文档频繁路径的挖掘中, 如果某节点在前缀所对应的直接后缀中多次出现, 仍然只计数一次, 但位置信息都要记录下来.
3.3 算法伪代码基于如上分析, PXFP算法的伪代码描述如下.
|
|
4 实验与分析
本部分实验1的数据来源于图3, 实验2和实验3的数据来源于INEX XML挖掘竞赛(XML Document Mining Challenge)中结构挖掘部分的电影数据集[16], 这是从11个网站得到的XML文件.
实验的计算机采用的配置为: 4 GB内存、英特尔酷睿i3, 1.40 GHz处理器、Windows 7操作系统、Myeclipse运行环境. 采用的对比算法是同样基于前缀的PrefixSpan算法. 实验的目标主要是检测PXFP算法的空间效率和时间效率.
实验1. 比较内存空间使用情况
由于PXFP算法不需要产生投影数据库, 而只记录直接后缀的位置信息, 因此占用更少的内存. 实验1利用PrefixSpan算法和PXFP算法对图3中的3个XML文档序列化后得到的序列数据进行分析, 每一步的内存占用如表7所示. 由于两个算法都是基于前缀的分治思想, 因此表7中先讨论以1阶频繁序列为前缀的情况, 最后再从总体上进行讨论.
|
|
表 7 PrefixSpan算法和PXFP算法的内存使用情况 |
从表7的实验结果可以看出, 无论利用分治的思想在每一个小范围内讨论, 还是从总体上考虑最大内存使用和合计内存使用情况, PXFP算法的空间效率都要好于PrefixSpan算法. 虽然PXFP算法需要记录较多的位置信息, 但由于每个位置信息仅占用3个字符的内存, 相比于PrefixSpan算法投影数据库中的子序列相比, 仍然有优势.
图3中XML文档的数量少, 并且每个XML文档的节点数少, 当应用于实际中的XML文档集时, PrefixSpan算法将产生更多的投影数据库, 因而PXFP算法的空间优势将会更明显.
实验2. 比较不同支持度阀值下的执行时间
利用实验数据集, 在两个支持度区间进行实验, 分别是: ①小支持度区间(5%–30%); ②大支持度区间(10%-90%), 对比本文提出的PXFP算法和PrefixSpan算法的运行时间. 表8给出的是实验数据在小支持度区间范围内挖掘出的频繁路径的个数, 图4对应给出在该区间内PrefixSpan算法和PXFP算法运行时间的对比; 表9给出的是实验数据在大支持度区间范围内挖掘出的频繁路径的个数, 图5对应给出在该区间内PrefixSpan算法和PXFP算法运行时间的对比.
由表8和图4可以看出, 在小支持度区间, 实验数据集产生较多的频繁路径, 随着支持度阀值增大, PXFP算法和PrefixSpan算法的执行时间都在缩短, 原因在于随着支持度阀值的增加, 生成的各阶频繁路径在减少, 并且在该数据集中, 频繁路径减少的速度很快. 同时也可以看出, PXFP算法处理XML文档标签序列的时间效率明显高于PrefixSpan算法.
|
|
表 8 小支持度区间内挖掘出频繁路径个数 |
|
图 4 小支持度区间内算法时间效率对比 |
|
|
表 9 大支持度区间内挖掘出频繁序列个数 |
|
图 5 大支持度区间内算法时间效率对比 |
表9和图5从更宏观、更全面的角度进行实验, 展现了最小支持度在更大范围内变化时两算法的执行效率对比. 实验结果表明: 随着支持度阀值增大, PXFP算法和PrefixSpan算法的执行时间都在下降, 同时, PXFP算法在各支持度下的时间效率都要明显高于PrefixSpan算法. 其中, 最小支持度在10%–30%的范围内变化时, 由于挖掘出的频繁子路径数量减少速度很快, 因此算法执行时间下降速度很快; 最小支持度在40%–70%的范围内, 频繁子序列数量减少速度相对较慢, 因此挖掘算法的执行时间降速放缓; 然而, 在70%及以上的支持度下, 由于此时已经不再有频繁模式被挖掘出来, 算法执行时间再一次骤减, 并且由于两算法在扫描一次数据库后基本不用再进行后面的循环, 因此两算法的运行时间都趋于0, PXFP算法的优势也不如产生大量频繁子路径时明显.
实验3. 比较不同XML文档数下的执行时间
创建XML数据集, 其中存放的XML文档数量由1000, 2000, 3000, 逐渐递增至10000. 控制支持度阀值为20%, 对该数据集进行频繁路径挖掘, 考察随着XML文档数量, 即标签序列数量攀升的情况下, 两算法的执行效率. 实验结果如图6.
|
图 6 标签序列数量增加时执行时间的比较 |
图6表明, 在固定的支持度阀值下, 随着XML文档数据集规模的增大, 即标签序列数量的增加, PXFP算法和PrefixSpan算法的执行时间在攀升. 在数据量较小的情况下, 两算法的运行时间效率相差不多, 随着数据量不断增加, PXFP算法执行时间上的优势在增大, 特别地, 当序列数量为10 K时, PXFP算法所需要的时间几乎是PrefixSpan算法运行时间的60%, 并且可以预见的是, 当数据量更大时, PXFP算法的优势将更加明显. 因此可以得出结论, 在任何数据量下, PXFP算法有高于PrefixSpan算法的执行效率, 并且数据量越大, PXFP算法的优势越明显.
5 总结本文中提出了基于序列前缀技术的XML频繁路径挖掘算法—PXFP算法. PXFP算法结合了序列前缀、位置信息等思想及XML树形结构特征, 用于从XML文档集中挖掘出频繁模式. PXFP算法有如下的优点:
1) 广度优先遍历XML文档树并以“节点: 父节点”形式表示每个节点, 这种序列化的方式在不遗漏XML文档树的结构信息的同时降低了序列中的节点冗余, 减小了待挖掘的序列长度;
2) 较之PrefixSpan算法, 不需要产生投影数据库, 大大节约了存储空间;
3) 由位置信息直接定位到序列数据库中, 不需要多次扫描数据库及投影数据库, 减少时间开销.
在实验中, PXFP算法用于挖掘XML频繁路径在时间效率和空间效率上均优于经典的PrefixSpan算法, 证明了算法的有效性. 但是, 本文中提出的XML频繁路径挖掘算法在应用于大型XML文档或XML数据流还有改进和提升的空间, 这是未来进一步研究的方向.
| [1] |
Agrawal R, Srikant R. Mining sequential patterns. Proceedings of the 11th International Conference on Data Engineering. Washington, DC, USA. 1995. 3–14.
|
| [2] |
Srikant R, Agrawal R. Mining sequential patterns: Generalizations and performance improvements. Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology. London, UK. 1996. 3–17.
|
| [3] |
Han JW, Pei J, Yin YW. Mining frequent patterns without candidate generation. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York, NY, USA. 2000. 1–12.
|
| [4] |
Han JW, Pei J, Mortazavi-Asl B, et al. FreeSpan: Frequent pattern-projected sequential pattern mining. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA. 2000. 355–359.
|
| [5] |
Pei J, Han J, Mortazavi-Asl B, et al. PrefixSpan: Mining sequential patterns efficiently by prefix-projected pattern growth. Proceedings of the 17th International Conference on Data Engineering. Washington, DC, USA. 2001. 215.
|
| [6] |
张坤, 朱扬勇. 无重复投影数据库扫描的序列模式挖掘算法. 计算机研究与发展, 2007, 44(1): 126-132. |
| [7] |
张利军, 李战怀, 王淼. 基于位置信息的序列模式挖掘算法. 计算机应用研究, 2009, 26(2): 529-531. |
| [8] |
刘栋, 尉永清, 薛文娟. 基于Map Reduce的序列模式挖掘算法. 计算机工程, 2012, 38(15): 43-45. DOI:10.3778/j.issn.1002-8331.2012.15.010 |
| [9] |
吴信东, 谢飞, 黄咏明, 等. 带通配符和One-Off条件的序列模式挖掘. 软件学报, 2013, 24(8): 1804-1815. |
| [10] |
刘端阳, 冯建, 李晓粉. 一种基于逻辑的频繁序列模式挖掘算法. 计算机科学, 2015, 42(5): 260-264. DOI:10.11896/j.issn.1002-137X.2015.05.052 |
| [11] |
Beedkar K, Gemulla R. LASH: Large-scale sequence mining with hierarchies. Proceedings of the 2015 ACM SIGMOD Inter-national Conference on Management of Data. New York, NY, USA. 2015. 491–503.
|
| [12] |
Leung HP, Chung FL, Chan SCF, et al. XML document clustering using common XPath. Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration. Washington, DC, USA. 2005. 91–96.
|
| [13] |
贝毅君. XML数据频繁模式挖掘技术研究[博士学位论文]. 杭州: 浙江大学, 2008.
|
| [14] |
雷向欣, 杨智应, 黄少寅, 等. XML数据流分页频繁子树挖掘研究. 计算机研究与发展, 2012, 49(9): 1926-1936. |
| [15] |
李巍, 李雄飞, 郭建芳. XML空间频繁变化结构挖掘方法. 计算机学报, 2013, 36(2): 317-326. |
| [16] |
INEX. Initiative for the evaluation of XML retrieval. http://inex.mmci.uni-saarland.de/data/documentcollection.html, 2014.
|