间隙约束序列模式挖掘的对比研究

◆苗雪连

间隙约束序列模式挖掘的对比研究

◆苗雪连

（河北工业大学计算机科学与软件学院 天津 300401）

本文首先描述了间隙约束序列挖掘的分类及研究现状，最后给出了间隙约束的序列模式挖掘在实际生活中的发展趋势。在未来的研究领域中，具有间隙约束的序列模式挖掘仍是一个重要的研究方向。

间隙约束序列挖掘；算法

0 前言

近年来，随着人们对数据挖掘的不断深入研究以及信息的不断发展，序列模式挖掘也得到很大提升，应用范围不仅仅局限于传统的商业交易数据库，在医学、社会与科学等方面均有扩展。商业行为分析如客户购买行为模式的分析，医学领域如DNA分析，社科类的如自然灾害预测，等等。随着对序列模式挖掘不断深入的研究，序列模式挖掘划分越来越细，具有间隙约束的序列模式挖掘就是其中之一。

1 具有间隙约束的序列挖掘的分类及研究现状

具有间隙约束的序列模式挖掘问题是：给定序列S、支持度阈值和间隙约束，从序列S中挖掘出所有出现次数不小于给定支持度阈值的频繁序列模式，并且模式中任意两个相邻元素在序列中出现的位置满足间隙约束。为了满足用户的需求，在已有传统的的间隙约束序列挖掘研究中，对挖掘的出现加入一种或多种约束条件。目前已有的约束条件有无特殊条件的间隙约束[1]、一次性条件的间隙约束[2]和无重叠条件的间隙约束[3]等三种形式。

（1）一次性条件。一次性条件的间隙约束序列模式挖掘对具有间隙约束的序列模式挖掘的出现提出了要求，即模式在序列中的任意两次出现都不共享序列中同一位置的字符。

（2）无重叠条件。无重叠条件的模式匹配是模式在序列中的任意两个出现，出现的相同的位置上不能使用相同的字符，相同的字符只能使用在不同的位置上。

（3）无特殊条件。无特殊条件的模式匹配则对出现和位置都没有要求。

下面对这三种形式的相关研究进行了简要的介绍。

1.1 无特殊条件

Zhang等人对单序列中带有通配符的模式挖掘问题进行了研究，提出了MPP算法，同时在生物DNA序列上实验了该序列模式挖掘问题。虽然MPP算法采用Apriori-like性质对候选模式进行了裁剪，有效的解决了具有间隙约束的频繁模式不能使用Apriori性质挖掘的问题，减少了冗余候选模式的产生。但是由于MPP算法考虑模式的所有位置的出现，包括重复的出现，因此MPP算法产生的候选模式依然很多，这就导致了在处理大规模数据时，MPP算法运行效率较低。另外，MPP算法挖掘的频繁模式项集包含一些表面上看起来是频繁的模式。理论上，我们认为如果一个模式出现的次数更多的话，频繁的可能性应该更大，但是MPP算法计算得到的挖掘结果与理论上矛盾了。

针对MPP算法存在的问题，Min等人对MPP算法进行了改进，提出了AMin算法。首先，重新定义了具有间隙约束的频繁模式，使得AMin算法可以采用Apriori性质进行剪枝。方法就是在序列的末尾加上了虚拟字符，这使得一些模式的偏移序列个数增多了。AMin算法核心思想是:如果挖掘到的一个模式是频繁的，那么规定其子模式也是频繁的。

Zhu and Wu等人提出了MCPaS算法，该算法探索了从多序列中挖掘频繁模式。该算法虽然做了一些改进，但由于其同MPP算法一样，模式允许重复出现，所以挖掘效率也不高。

武等人[1]基于网树建立了不完全网树结构，提出了MAPD算法。MAPD首先对序列进行全面扫描，根据给定的序列和候选模式构建网树，然后通过计算网树中的候选模式在序列中的出现数，与给定的阈值进行比较，判断该模式是否是频繁模式，该算法高效的解决了在单序列上周期间隙约束的序列模式挖掘问题。

1.2 一次性条件

SAIL算法是Chen等人在2006年提出的，它是为研究具有长度约束和一次性条件的模式匹配问题的算法。SAIL算法旨在尽可能多的找到满足要求的出现。为了提高解的完备性，SAIL算法分为正向阶段和反向阶段两个设计阶段。根据模式P、序列S和间隙约束，SAIL算法通过建立一个二维表来解决模式匹配问题。若在模式挖掘过程中有多个位置出现时，SAIL算法选择位置最小的出现作为最优出现。

首次在带通配符的序列模式挖掘中引入一次性条件的是He等人，在MPP算法的基础上，通过对MPP算法改进，提出了两种启发式扫描策略:One-way scan和Two-way scan，即单向扫描和双向扫描算法。但是因为没有对通配符的范围进行具体的限制，所以不能够挖掘更加灵活的带有通配符的模式。

Wu等人[2]在One-off下的序列模式挖掘的条件下，提出了One-off Ming算法。该算法在生物DNA序列上进行了相关实验，实验结果表明，与其他的序列模式挖掘算法相比，One-off Ming算法能找到更多的出现，并且有效的缩短了挖掘时间。Wu等人在提出One-off Ming算法时，在计算序列模式的支持度时提出了两种计算支持度的方法，Calsup算法和i-Calsup算法。因为Calsup算法在计算支持度的时候可能会丢失一部分的出现，导致频繁模式项集不准确，因此对Calsup进行了改进，形成了第二种计算支持度的算法i-Calsup。i-Calsup为了找到更多的出现，在计算支持度时采用了前向搜索和后向搜索。在前向搜索阶段，通过可能匹配的所有位置以及满足间隙约束条件的所有前一个字符，找到当前的字符可能匹配的所有位置，并将它们保存在二维数组中，直到搜索到模式的最后一个字符的可能匹配的位置。在向后搜索过程中，采用最左优先策略，与前向搜索阶段搜索顺序相反，从最后一个字符开始，对二维数组中的每个模式的可能匹配位置进行选择。

1.3 无重叠条件

首次在具有间隙约束的序列模式挖掘研究中引入Non-Overlap的是Ding等人，所提出的算法主要挖掘无交叉出现的闭合序列模式。与He等人不同的是，Ding等人在基于INSgrow算法的基础上提出了模式挖掘算法，另外该算法挖掘的序列为多序列，Ding等人的算法有效的提高了挖掘效率。INSgrow算法是一种贪婪算法，该算法的主要思想是模式增长。首先建立大小为1的零号支持集；之后在每次的迭代过程中，都遵循最左原则进行模式增长，Chen和Wu等人已证明了最左原则寻找的模式是局部最优，但是可能会导致全局解的不完备。

因为INSgrow算法存在丢失解的现象，武等人在文献[3]首先论证了无重叠约束的模式匹配是一个P问题，之后基于网树结构，提出了NETLAP-BEST算法，找到了无重叠序列模式挖掘的完备解，实验结果验证了 NETLAP-Best 算法的正确性和有效性。NETLAP-BEST算法在求解时，首先根据模式匹配问题建立网树，在网树上迭代地寻找最右树根-叶子路径，之后剪去这条路径和无用的网树节点。

2 发展趋势

经过多年的发展与研究，具有间隙约束的序列模式挖掘已取得了较大的发展，无特殊条件的间隙约束序列模式挖掘已经能够快速高效的找到所有的出现，无重叠条件的间隙约束序列模式匹配问题已被证明为一种P问题，且能找到完备解。但仍存在一些问题，目前一次性条件的序列模式挖掘仍然是一个NP问题，如何优化算法，使得提高解的完备性的同时也能提高挖掘速度仍是一个难题。另外，在实际应用的研究过程中，如何合理的设定具有间隙约束的序列模式挖掘算法的阈值仍没有较好的评判方法。

具有间隙约束的序列模式挖掘在实际生活中已经有了许多的应用。在未来的研究领域中，具有间隙约束的序列模式挖掘仍是一个重要的研究方向。

[1]Wu Youxi，Wang Lingling，et al.Mining Sequential Patterns with Periodic Wildcard Gaps.Applied Intelligence，2014.

[2]吴信东，谢飞，黄咏明，胡学钢，高隽.带通配符和One-Off 条件的序列模式挖掘.软件学报，2013.

[3]Youxi Wu，Cong Shen，He Jiang，Xindong Wu.Strict pattern matching under non-overlapping condition.Science China Information Sciences，2017.

图1 加载OBJ文件的程序流程

图2 OBJ文件中的顶点相关参数

3 3D可视化中人机交互的实现

基于WebGL的交互主要是借助鼠标和键盘进行相应的操作，通过鼠标点触键盘来实现对事件的监听和加载代码。在系统操作实现中，鼠标所具有的功能是实现对镜头的有效缩放处理，在操作鼠标的时候就能控制镜头的移动。系统中网页的名称主要包括mousemove、mousedown、mouseup等。事件在发生的时候需要判断鼠标的具体操作，从而加强对镜头的操作控制。

网页中的键盘事件主要有keydown和keyup两种，在系统平台中键盘操作能够对模型的具体移动进行操控，具体按键是W键和S键，触发函数参数是HTML5标准中的全局变量event，其通过对按键的ACSII码判断能够执行相应的指令。

4 3D可视交互平台设计性能分析

4.1 跨浏览器的测试

在测试中将基于网络安全数据构建的三维可视模型直接运行在三大主流浏览器中。结果显示，可视模型能够实现无插件稳定运行。

4.2 基于WebGL技术模型载入时间测试

为了验证本文可视化方法的有效性，在Intel i7（3.5 GHz）处理器，8 GB内存，MacOS 10.12.3（64 bit）平台上对可视系统进行了实验。文章测试操作以网络安全数据三维可视模型为例，通过不同浏览器的载入来对模型的响应时间进行实验测试。选择的三维可视模型主要由13236个三角面单元构成，顶点的数量达到了6104个。在上述平台中分别使用Chrome浏览器、Opera浏览器、Firefox浏览器进行测试，最终的响应时间分别是1.12ms、1.58ms和1.09ms。经过分析比较之后发现可视模型载入时间短，且最终浏览器表现的性能结果良好。

5 结束语

基于WebGL技术构建高效能的三维可视平台是未来Web3D技术的热点发展方向，文章对基于WebGL的3D可视交互平台的设计和实现进行了分析测试，构建出性能良好、操作方便的3D可视交互平台，利用WebGL技术实现了更加丰富友好的用户体验。相信在未来WebGL凭借其在交互体验和实现效率上的优越性将在可视分析、虚拟现实等技术上得到更广泛的认可。

参考文献:

[1]丁晨溦，程星，袁慧，王岩，邓维维.Student Devision高校信息交互平台的设计与实现[J].软件工程师，2015.

[2]汪浩，田丰，张文俊.基于WebGL的交互平台设计与实现[J].电子测量技术，2015.