第39卷  计  算  机  学  报  Vol.39 2016 论文在线出版号  No.178  CHINESE JOURNAL OF COMPUTERS  Online Publishing No.178 ——————————————— 本课题得到国家自然科学基金项目(No. 1120165702)、中国博士后面上基金项目(No. ZX20150629)、浙江省科技厅计划项目(No.2016C31128, 2017C35014)、宁波市自然科学基金项目(No. 2015A610135)、2015年度浙江省统计研究重点课题(201522)资助.  王乐,  女, 1978年生,  博士,  讲师,  主要研究领域为金融数据挖掘, E-mail: wangleboro@163.com.  王水  (通讯作者),  男, 1967年生,  学士,  教授,  主要研究领域为数据挖掘, E-mail: seawan@163.com.  刘胜蓝,  男, 1984年生,  博士,  博士后,  主要研究领域为计算机视觉、机器学习, E-mail: liusl@mail.dlut.edu.cn.  王辉兵,  男, 1989年生,  男,  博士生,  主要研究领域为计算机视觉、机器学习, E-mail: whb0842005@mail.dlut.edu.cn. 基于索引树的带通配符序列模式挖掘算法   王乐1，2)  王水1)  刘胜蓝2)  王辉兵2) 1)(宁波大红鹰学院  信息工程学院  浙江宁波  315175)   2)(大连理工大学  创新创业学院  辽宁大连  116024)   摘  要  随着有序时间序列数据的出现，序列模式挖掘成为数据挖掘领域的一个分支；其中带通配符的序列模式挖掘又是该领域中一个重要的研究问题，同时随着数据规模越来越大，算法的挖掘效率尤为重要。现有算法多采用树型结构来实现数据的压缩表示；树的结构和模式匹配方法对挖掘效率有决定性的影响。本文首先设计一个新的树结构索引树I-Tree (Index-Tree)  来维护原始序列数据、以及序列模式和模式索引信息；然后在索引树的基础上，提出一个新的带通配符的序列模式挖掘算法ITM(Index-Tree based sequential pattern Mining)。算法ITM主要用4个策略提高算法的挖掘效率：(1)将原始序列中相同项压缩到一个节点上，该节点只记录项在原始序列中的索引；(2)采用迭代的方式，长度k+1的序列模式是用长度k的候选序列模式产生(k>0)；(3)采用前缀树的结构，逐层将k+1的候选序列模式压缩到索引树上，叶子节点上记录序列模式最后一项的索引；(4)整个挖掘过程，只用一棵索引树。算法ITM通过采用以上索引树压缩原始序列数据以及存储候选序列模式，有效地降低搜索空间，从而算法效率得到显著提升。另一种提高挖掘效率的思路，是在挖掘过程中允许有小部分的模式丢失，来换取挖掘效率的大幅度提升，即所谓的近似模式挖掘。本文也给出一个近似序列模式挖掘算法AITM (Approximate Index-Tree based sequential pattern Mining)，该近似算法通过估计超序列模式的支持数，将非候选节点提前删掉，减少索引树上的节点个数，从而提高算法的时空效率；但是也因为估计的支持数可能会小于实际值，从而丢失了部分频繁的序列模式。本文实验中，提出的两个算法分别与算法MGCS, MAPB, 和MAPD进行了对比实验，采用3个典型数据序列进行测试，并设计3组实验：(1)不同的最小支持度对算法的效率影响；(2)算法的扩展性；(3)通配符长度对算法效率的影响。实验结果验证了本文提出算法的有效性，时空效率得到一定的提高；针对不同的阈值，最小支持度越小、原始序列长度越长、通配符长度越长，算法的时间效率提高幅度越大；同时近似挖掘算法的精确度接近100%。 关键词  数据挖掘；序列模式；通配符;  模式匹配；索引树 中图法分类号  TP311 论文引用格式 王乐,王水,刘胜蓝,王辉兵，基于索引树的带通配符序列模式挖掘算法，2016，Vol.39：在线出版号  No.178 Wang  Le,Wang  Shui,Liu  Sheng-Lan,  Wang  Hui-Bing，An  algorithm  of  Mining  Sequential  pattern  with  wildcards  based  on Index-Tree，Chinese Journal of Computers,2016, Vol.39: Online Publishing No.178 An algorithm of Mining Sequential pattern with wildcards based on Index-Tree Wang Le1,2)      Wang Shui1)      Liu Sheng-Lan2)    Wang Hui-Bing2) 1) (School of Information Engineering, Ningbo Dahongying University, Ningbo, Zhejiang 315175) 2) (School of Innovation and Entrepreneurship, Dalian University of Technology, Dalian, Liaoning 116024)   网络出版时间：2016-11-29 12:54:02网络出版地址：http://www.cnki.net/kcms/detail/11.1826.TP.20161129.1254.006.html2  计  算  机  学  报  2016年  Abstract  Sequential Pattern Mining, which arose as a sub-field of data mining, focus on sequences of items or events occurring in an ordered metric space. Mining sequential pattern with wildcards is one important issue in this  field;  and  for  higher  volume  data,  more  efficient  algorithms are needed.  Most  of  the  previous  algorithms generally adopt tree structures for compressing data and searching for sequential patterns; therefore the structural design  and  the  pattern  matching  methodology  affect  mining  efficiency  significantly.  In  this  paper,  we  first propose  a novel  tree  structure  Index-Tree  (I-Tree),  which  stores  compressed  original  data  series  and  sequential patterns  as  well  as  pattern  indexing  information;  second, we develop  an  efficient  algorithm  ITM  (Index-Tree based  sequential  pattern Mining)  based  on  index-tree  for  mining  complete  set  of  frequent  sequential  patterns. Efficiency of the proposed algorithm  ITM is improved by four techniques: (1) the same candidate items of the original data series are compressed to the same node that records index of items, (2) sequential patterns of length k+1 are generated by scanning candidate sequential patterns of length k (k>0) and their index information on the index-tree, (3) adopting the prefix-tree structure, candidate sequential pattern of length k+1 are stored at the same index-tree,  and  leaf-nodes  record  the  index  of  last  item  of  the  candidates,  (4)  the  algorithm  ITM  creates  one index-tree  in  the  whole mining process.  The  index-tree  reduces  search  space  effectively  by  compressing  the original data series & candidate sequential patterns, and by recording index of the last item of sequential patterns, therefore  the  performance  of  algorithm  ITM  is  improved  significantly. To  achieve higher  mining  performance, we discussed another approach that allows a small portion of sequential patterns to be omitted during the mining process  in  exchange  for  a  substantial  increase  of  mining  efficiency;  this  kind  of  approach  is  what  we  call approximate  algorithm.  In  this  paper,  we  develop  an  approximate  algorithm named AITM  (Approximate Index-Tree based sequential pattern Mining) based on the algorithm ITM; by estimating the support number of super  sequential  pattern,  non-candidate  nodes  are  deleted  prematurely  to  reduce  the  number  of  nodes  on index-tree,  and  therefore  to reduce the search  space of  the  mining  process  and promote  efficiency  of  pattern matching;  the  algorithm  AITM  may  lose  some  sequential  patterns  because  the  estimated  support  number  of patterns  may  be  less  than  their  actual  values,  but  the  space-time  efficiency  of  algorithm  AITM  is much better than that of algorithm ITM. Our experimental results show that the proposed algorithms are efficient and scalable for mining sequential pattern with varied parameter on different data series. Three classical datasets were used in our  experiments  for  comparing  with  the  state-of-art  algorithms  MGCS,  MAPB,  and  MAPD;  3  different experiments are designed: (1) under varied minimum support threshold, (2) under varied volume of data, (3) and under varied length of wildcards; the experimental results verified the validity of the proposed algorithms with increase  of  time/space  efficiency;  the  smaller  the  minimum  support  is,  or  the  longer  the  length  of  the  original data series or  the  wildcards are,  the  more  significant  boosting  on  performance  the  proposed  algorithms  would have; and the accuracy of approximate algorithm AITM is up to 100%. Key words  Data Mining; Sequential Pattern; Wildcard Gaps; Pattern Matching; Index-Tree   1  引言 模式挖掘是数据挖掘领域一种重要和基础的技术，由最初的传统频繁模式[1-3]（frequent pattern）挖掘不断扩展到不确定数据集（uncertain  dataset）中的频繁模式挖掘[4-7]、带权重的频繁模式挖掘[8]、高效用模式挖掘（high utility pattern）[9-12]、大数据下的频繁模式挖掘[13,  14]、以及序列模式挖掘（sequential pattern）[15, 16]等。 序列模式挖掘最早由Agrawal 和Srikant提出[17]，其任务是从序列数据集中发现所有频繁的模式。序列模式挖掘广泛出现在股票分析及走势预测，DNA 序列分析、疾病预测、大型购物数据分析等应用领域中[18, 19]。如何在序列数据中找到频繁出现的序列模式，是序列模式挖掘的主要任务之一[15, 16, 20-24]。 Wu等[15]指出带有通配符的序列模式挖掘具有重要的研究价值，它允许挖掘出序列模式中含有灵活的通配符，不仅使序列模式挖掘具有理论研究价论文在线出版号  No.178  王乐等：基于索引树的带通配符序列模式挖掘算法  3  值，也使其具有巨大的应用价值，如在文本索引和生物信息学等领域。 但是序列模式中引入通配符后，使序列模式挖掘问题变得更为复杂，特别是随着数据规模的增加，挖掘算法的效率的提高是序列模式挖掘的一个重要研究问题[15, 16, 20-22]，另外序列模式挖掘中的一个重要工作是模式匹配，此后，Wu等针对模式匹配问题进行了研究，同时也给出了有效的模式匹配算法[25, 26]。 在已有序列模式挖掘研究成果的基础上，本文首先给出一个树结构来存储原始序列索引信息和序列模式的索引信息，该树结构命名为索引树 (I-Tree，Index-tree)；然后给出一个基于I-Tree的序列模式挖掘算法ITM (I-Tree based sequential pattern mining)。算法ITM 通过将序列中各项的索引存放到一棵索引树I-Tree上，然后通过访问树上相应索引进行序列模式的匹配，不需要再访问原数据集，同时通过索引进行模式匹配也降低了搜索空间，从而可以有效的提高算法的挖掘效率。在算法ITM的基础上，利用估计模式支持数进行剪枝的策略，本文又给出一个近似的序列模式挖掘算法AITM (Approximate ITM)。 本文的组织结构如下：第2节给出序列模式挖掘的相关定义和相关工作；第3节描述算法ITM；第4节介绍一个近似算法AITM；第5节对算法进行复杂度分析；第6节给出实验结果及其分析；第7节给出结论。 2  相关定义与相关工作 2.1相关定义 定义1.  在一个目标序列1 2 nS s s s =¼中，其包含的字符个数n为其序列长度，序列S 的字符集合记为∑（也称为字符表），S中不同字符的个数记为|∑|。 例1，一个DNA序列片段S = s1s2s3s4s5s6s7s8s9 s10s11s12s13s14s15 = gaattcatcagccat，其序列长度为15，字符表∑={a,c,g,t}，|∑|=4。 定义2.  通配符可以代表字符集中任意字符，记为Φ。 定义3.  设长度为m 的 一 个 模 式1 1 2 2 j m 1 m P p g p g p g p- = ¼ ¼，其中gi(i=1,  2,  …, m-1)是字符pi 和pi+1之间的通配符个数，gi 的取值区间为[M,N]（即gi 最小取值为M，最大取值为N），这里模式P就称为一个带通配符的序列模式或非固定间隔约束的序列模式，这里简称为序列模式。 定义4.  假设S 中依次存在m 个字符12 ml l ls s s ¼，其中字符ils(i=1,2,…m)的下标il为该字符在S中位置（或索引），只要前后两个字符下标值的范围在[M,N]，则序列12 ml l ls s s ¼是一个长度为m的偏移序列(offset sequence)，序列S中模式P的所有偏移序列就是所有长度为|P|的偏移序列，其个数记为ofs(|P|,S)。 例2：在目标序列S = s1s2s3s4s5s6s7s8s9= gaattcatc中，当间隔约束[M,N]中的M=3，N=4，则序列s1s5 = gt、s1s6 = gc、s2s6 = ac、s2s7= aa、s3s7 = aa、s3s8 = at、s4s8 = tt、s4s9 = tc、s5s9 = tc 是长度为2的偏移序列，ofs(2,S)=9；序列s1s5s9 = gtc是长度为3的偏移序列，ofs(3,S)=1。 定义5. 12 ml l lS s s s =¼ 1是S中一个偏移序列，1 1 2 2 j m 1 m P p g p g p g p- = ¼ ¼是一个长度为m的序列模式，若ili sp=(i=1,2,…m), 则字符串12 ml l lS s s s =¼ 1为模式P在S中的一次出现；同样满足上述条件的字符串12 mt t tS s s s =¼ 2，只要S1和S2中存在一个i 使ii tl¹，则S2就称为是模式P的另一次出现，即S1和S2是模式P在目标序列S中的两次出现；模式P在S中所有出现次数称为模式P的支持数,记为sup(P,S)。 定义6.  假设ρ为用户预定义的最小支持度，若( , ) | | r P S sup(P,S) ofs( P ,S) r =³，则模式P称为一个频繁序列模式，否则，模式P为非频繁序列模式。本文所研究模式挖掘就是从序列中找出所有( , ) r P S r ³的频繁序列模式。 定义7.  给定长度分别为m1和m2的模式P1和P2，如果P1是P2的一个子串，则称P2是P1的超模式，P1是P2的子模式；如果P1和P2的前m2-1个4  计  算  机  学  报  2016年  字符依次相同，则称P1是P2的前缀模式；如果P1和P2的后m2-1个字符依次相同，则称P1是P2的后缀模式。 从定义4和5可知，|| sup(P,S) ofs( P ,S) £,即0 ( , ) 1 r P S ££。设定模式P的长度为m，序列S的长度为n，1 W N M = - +， ( ) / ( 1) l n M M = + + êú ëû 1，( ) / ( 1) l n N N = + + êú ëû 2，根据文献[15]，目标序列S中长度为m的偏移序列个数ofs(m,S)的计算方法如公式1： ( 1)( , ) ( ( 1)(( ) / 2 1))mmlofs m S n m M N W m lcan be calculated by a recursive formular l m l-> ìï= - - + + £ íï<£ î12210             （1）引理 1.  对任意长度为m的模式P1和其长度为m+1的超模式P2，可得( , ) ( , ) sup P S sup P S W £* 21[15]。 证明：令12 ml l lS s s s =¼ 1是模式P1在目标序列S中的一个出现，模式P1为模式P2的一个前缀模式，则P2在序列S中至多有W个以S1为前缀的超模式，所以( , ) ( , ) sup P S sup P S W £21。同样地，当P1为模式P2的后缀模式时，也可以得到相同的结论。 引理2.  如果一个长度为m的序列模式P的支持率小于( 1)( 1)( 1)( 1)n d wn m wr- - +- - + ()dm>，那么它所有的超模式都是非频繁的，其中d表示最长的频繁模 式 长 度，n 表 示 主 序 列S 的 长 度 ，( ) / w N M =+ 2[15]。 证 明 ： 根 据 引 理 2 的 条 件 可 知( , ) ( 1)( 1)(| |, ) ( 1)( 1)sup P S n d wofs P S n m wr- - +<- - +。 假设模式Q是P的一个长度为k 的超模式k(m k d <£)，根据偏移序列计算公式（1）可以推断出(| |, ) ( ( 1)( 1))m ofs P S n m w W-= - - +1和(| |, ) ( ( 1)( 1))k ofs Q S n k w W-= - - +1。  由引理1可得到( , ) ( , )km sup Q S sup P S W-£， 所 以( , ) ( , ) ( 1)( 1)(| |, ) (| |, ) ( 1)( 1)( , ) ( 1)( 1)(| |, ) ( 1)( 1)sup Q S sup P S n m wofs Q S ofs P S n k wsup P S n m wofs P S n d wr- - +£×- - +- - +£ × <- - +， 由此引理2得证。 引理3.  假设P是一个长度为m的序列模式、目标序列S中最长频繁序列模式的长度为d、( 2)1( )( 1)n d wdmn d wb--= > >--，如果( , )dmr P S br-<，则模式P不存在超序列模式（超频繁序列模式）。 证明：假设Q是P的一个长度为k的超模式（m k d <£），则 sup( , ) sup( , )( , )(| |, ) ( )kmkQ S P S wr Q Sofs Q S n k w--=£--11 ()( , )()n m wr P Sn k w--=×--11      ()( , )()( 1) ( )( 2) ( 1)n m w n mwr P Sn m w n m wn m w n k wn m w n k w- - × -= × × ×- × - +- + - -- + - -L112 ( , )kmr P S b-< 其中，由于( 1)1n m wn mwa--=>-，所以( , ) ( , ) ( , )kmr P S r P S r P S b b b-< < < L2；因此可以推出当( , )dmr P S br-<，模式P不存在超频繁序列模式。 论文在线出版号  No.178  王乐等：基于索引树的带通配符序列模式挖掘算法  5  定义8：一个长度为m的序列模式P的支持率小于( 1)( 1)( 1)( 1)n d wn m wr- - +×- - +或( , )dmr P S b- ( 3) b见引理，则该序列模式称为非候选序列模式（当m=1时，称为非候选项），否则称为候选序列模式（当m=1时，称为候选项）。 定义9. 一个长度为m的序列模式的候选支持率记为( 1)( 1)()( 1)( 1)n d wmn m wrr- - +=×- - +。 2.2 相关工作 序列模式挖掘的约束条件主要有3个[25]：（1）间隔约束（gap condition /wildcards condition）、（2）模式重叠约束（overlapping  condition）、和（3）一次出现约束（one-off  condition）。本文主要研究具有间隔约束、可以重叠、并且满足非一次出现的序列模式挖掘；而这类序列模式的支持数计算复杂度较高，算法的效率尤为重要。 Zhang等人[16]最先提出了带有间隔约束的序列模式挖掘问题，并给出了第一个挖掘算法MPP。算法MPP采用类Apriori性质进行序列模式挖掘，首先扫描序列S产生长度为3的频繁序列模式集L3和候选序列模式集CL3；然后用长度为k(k>2)的候选序列模式来产生长度为k+1的候选序列模式集CLk+1，再计算候选模式集中每个模式的支持率，将不小于最小支持率的模式放到频繁序列模式集合中；至到某个k值使候选序列模式集CLk+1为空为止。算法MPP利用一种称为部分索引列表的结构来维护每个模式第一项对应的所有坐标及每个坐标下该模式对应的支持数，因此该算法计算每个候选项的支持率的时候不需要再次扫描原始序列，因此该算法的主要缺点为耗费大量空间来存储所有模式的索引列表，同时也影响了算法的时间效率。 算法GCS[21]将一个长度为m的模式P与长度为n的序列S的匹配关系用一个m*n的矩阵来表示，尽管计算模式的支持数的效率提高了，但是算法的效率仍不理想。在算法GCS的基础上，算法MGCS给出了改进，在模式P及其m*n的矩阵的基础上，同时计算模式P的所有以P为前缀、并且长度为m+1的超模式的支持数，因此算法MGCS的时空效率得到了较大的提升。 算法Amin[20]采用类Apriori算法的层次挖掘特点，首先产生长度为1的频繁项；然后用频繁项与序列中所有的项组合产生长度为2 的频繁序列模式；然后重复的用长度为k的频繁序列模式分别与序列中所有项组合产生长度为k+1的频繁序列模式集Lk+1，直到某个k值使Lk+1为空为止。相比算法MPP和MGCS，算法Amin很大程度上降低了检索空间，但同时也会导致一些频繁序列模式没有被挖掘到。 Wu等[15]提出算法MAPB和MAPD，这两种算法都是利用网树来提高计算模式支持数的效率，其中算法MAPB是采用广度优先搜索及创建新的网树，算法MAPD是采用深度优先搜索及创建新的网树。由于算法MAPB在挖掘的过程中，需要同时维护较多的网树；相对MAPB算法，MAPD在挖掘的过程中，同时维护树的棵数较少，导致算法MAPD的空间消耗较少，并且MAPD的算法时间效率也比MAPB也较高。和算法MPP、MGCS和AMIN相比，算法MAPD的时间效率提高幅度也较高。 通过以上算法的分析，目前算法MAPD的时空效率是较高的。本文提出的算法也将和该算法进行实验对比。 3  3 算法ITM 本文给出的算法ITM 首先通过一遍原始序列的扫描，将序列中各项的索引存放到一棵索引树I-Tree上；然后通过I-Tree，即可挖掘到所有的频繁序列模式，不再需要扫描原数据集。 3.1 树I-Tree的节点结构 树I-Tree中的节点结构分为3种： （1）根节点root（第0层节点）包含1个字段：child记录孩子节点。 （2）根节点的孩子节点（第1层节点）包含4个字段：①item 记录节点的名字、②SN记录支持数、③IND记录该节点对应项在原始序列中的下标列表、④child记录孩子节点。 （3）其余层节点记录包含4 个字段：①item记录节点的名字、②SN记录支持数、③IND 记录该节点对应项在原始序列中的下标信息列表（下标信息包含下标ind 及其下标对应的支持数sn）、④child记录孩子节点。这里的IND 字段和第一层节点结构中IND 不同，这里的IND 包含下标和下标的相应支持数。 6  计  算  机  学  报  2016年  3.2 算法ITM 描述算法之前，先给出算法中用到相关术语的定义。 定义10. 根节点root 到每个节点N路径上有序项组成的序列称为节点N的模式，其中第d(d>0)层节点对应的序列长度为d-1）。 定义11.  第d 层上节点N的支持率等于. / ( 1, ) N SN ofs d S -。 定义12.  一个节点的模式不是频繁的，则该节点称为非频繁节点；若节点的模式是频繁的，则该节点称为频繁节点；若节点的模式不是候选序列模式，则该节点也称为非候选节点；若节点的序列是候选序列模式，则该节点也称为候选节点。 算法1.    ITM步骤如下 步骤1：首先创建一个根节点root； 步骤2：扫描一遍原始序列，将序列中所有不同的项添加到root的孩子节点中，同时将每项在原始序列中的下标、以及支持数存放到节点中； 步骤3：扫遍一遍第一层的节点，将频繁节点对应的序列模式保存到频繁序列模式集中；同时删除非候选节点； 步骤4：处理第一层中每个节点N，假设N上的项为X： 子步骤4.1：项X与第一层每个节点N’上项Y组合，产生序列XY； 子步骤4.2：序列XY的支持数可以根据节点N和N’上索引信息进行计算(详见子算法CSN)； 子步骤4.3：如果序列XY满足候选序列模式，则在项Y的孩子节点上增加节点N，并将支持数、对应的下标和其支持数保存在节点N上； 子步骤4.4：如果序列XY是一个序列模式，将其保存到序列模式集合中。 步骤5：依次处理第k(k>1)层中每个节点N，假设节点N的序列模式为X，X’为X的前缀模式： 子步骤5.1：序列模式X与X’的每个孩子节点N’上项Y组合，产生模式XY； 子步骤5.2：序列模式XY的支持数可以根据节点N和N’上索引下标进行计算， 子步骤5.3：如果序列模式XY满足候选项集，则节点N上增加存放项Y的孩子节点，并将支持数、对应的下标和其支持数保存在节点上； 子步骤5.4：如果序列模式XY的支持率不小于最小支持率，则该序列就是一个频繁序列模式，将其保存到频繁序列模式集合中； 步骤6：循环执行第5步，直到第k层没有节点为止。 子算法CSN: CSN(IND1, IND2, IND3, D) 输入：节点N1和N2的下标列表IND1 和IND2，初始值为空的下标列表IND3，节点N1的层次D； 输出：支持数Tsn j1=0,Tsn=0; for i = 0 to IND2.size() // IND2.size()表示列表IND2中下标个数 ind2 = IND2[i]; sn=0; for j = j1 to IND1.size() ind1 = IND1[j]; // IND2[i].ind表示列表IND2中第i个位置存放的下标 if(IND2[i].ind - IND1[j].ind < M) break; else if (IND2[i].ind - IND1[j].ind > N)       j1 = j;       continue; else       if (D == 1) sn++; else sn = sn+ IND1[i].sn; // IND2[i].sn表示列表IND2中第i个下标对应的支持数 if (sn > 0)    IND3.add(ind2,sn);  //将新产生的下标及其支持数存放到IND3 中 Tsn = Tsn +sn; Return Tsn; 3.3  算法ITM的实例 这里以S =  s1s2s3s4s5s6s7s8s9s10s11s12s13s14s15 = gaattcatcagcca为例说明ITM的挖掘过程。这里设定M=3，N=5，ρ=14%。 步骤1：创建一根节点root； 步骤2：采用3.1节中步骤2的方式，得到一棵如图1(a)所示的树，如节点“a”上的“5”表示项a 的支持数，“{(2,1),(3,1),(7,1),(10,1),(14,1)}”表示这5 次分别出现的下标位置和相应位置的支持数（第2层节点所有相应位置的支持数都为1）。 roota5,{(2,1) ,(3,1),( 7,1),( 10,1),(14 ,1)}c4 ,{( 6,1),(9,1) ,(12,1),(13 ,1) }g2,{( 1,1),( 11,1)}t4,{(4,1),( 5,1),(8,1),( 15,1)}(a) 扫描 S后得到的I-Tr ee  roota c t(b )    处理(a)中第一层节点后的结果a3,{(7 ,2),( 14,1)}c3,{(6,1),( 9,1),(12 ,1)}t3,{ (8,2) ,(15,1) }a3,{(10,2),(14,1) }c4,{( 9,2),(12,1) ,(13,1) } 图1. I-Tree的创建 步骤3：“g”节点的支持率低于设定的阈值，论文在线出版号  No.178  王乐等：基于索引树的带通配符序列模式挖掘算法  7  则将该节点删除。 步骤4：采用3.1节中步骤4的方式，节点a上的项“a”分别和第一层节点上的项（即“a”、“c”、“t”）进行组合产生序列模式，如产生序列模式“aa”，然后根据节点“a”下标列表(图1中第2层)，用算法CSN计算序列模式“aa”的支持数、及该模式中第二个“a”出现的下标和相应下标位置的支持数。如图1（b）第3层节点“a”上的“3,{(7,2), (14,1)}”，其中数字“3”表示模式“aa”的支持数；“(7,2)”中的“7”表示模式“aa”中第2 个“a”（s7）的下标，(7,2)”中的“2”表示有2个“a”分别和s7组合产生模式“aa”（s2 s7, s3s7）。 如图1(b)上第3层节点“c”,首先根据节点“a”和“c”上的下标列表(图1中第2层)，用算法CSN计算序列模式“ac”的支持数、及该模式中最后一项“c”出现的下标和相应下标位置的支持数。“ac”的支持数为3，该模式中最后一项“c”出现的下标和相应支持数为“{(6,1),(9,1),(12,1)}”，其中“(6,1)”中的第一个数字“6”表示下标，“1”表示该下标下对应1次“ac”的出现（s2s6）；由于序列模式“ac”的支持率不低于候选支持率，即可能存在以该模式为前缀的超集序列模式是频繁的，因此节点“a”增加存放项“c”的孩子节点；根据模式“ac”的支持数可以计算到该模式的支持率低于最小支持率，因此该模式不是频繁序列模式。同样的方法，节点“a”上增加了3个孩子节点，节点“t”上增加了2个孩子节点，结果如图1(b)中第三层节点所示。当第2层节点处理完后，就删除第二层节点上存储的下标列表和支持数，结果如图1(b)所示。 步骤5：采用3.1节中步骤5的方式，依次处理第3层节点。如第3层最左边的节点“c”，该节点的序列模式为“ac”，其后缀模式“c”没有孩子节点(见图1（b）第2层节点“c”)，即不可能有以“ac”为前缀的频繁序列模式，所以该节点“c”没有孩子节点。第3层节点“t”的序列模式是“at”，其中其后缀模式“t”的孩子节点包含2个（见图1（b）第2层节点“t”的2个孩子结点），即以“at”为前缀的序列模式只可能是“atc”和“ata”；根据节点“t”（第3层）和“c”（第2层节点t 的孩子节点“c”）上的下标列表，用算法CSN计算序列模式“atc”的支持数为4，则该序列的支持率低于候选支持率，因此序列模式“atc”不是频繁的，同时也不会产生以该模式为前缀的频繁序列模式。同样的方式处理第2层其余节点，结果每个节点都没有孩子节点产生，即没有第4层节点产生。则算法执行完毕。 4  算法AITM 根据定义3，一个长度为m的序列模式P(假设P的最后一个字符是“x”)的任一超序列模式Q  =“P-y”(Q 长度为m+1)的 个 数 最 多 为( , ) sup P S W *，当( , ) ( , ) sup Q S sup P S W =*，即在目标序列S中，任一模式P出现的后面W字符都是“y”，实际上，假定每个字符在S中出现概率相同，则任一个字符“x”后的W个字符中“y”个个数为/ | | W å，因此用( , ) sup P S W *来估计Q的支持数会和实际值差距较大，从而算法ITM在挖掘序列模式的过程中，I-Tree上会维护一些不会产生频繁序列模式的节点，影响降低了算法的时空效率。 为此，在算法ITM的基础上，给出一个近似算法，当I-Tree每增加一层节点，都可以计算出模式“x”和“x- ∅”(“∅”指原序列S中任一字符，即通配符)的支持数。在给节点“x”（节点“x”的序列模式为P）增加孩子节点后，存在一个支持数( -y, ) sup P S最大的孩子节点“y”，即可得到一个数值( -y, ) / ( , ) sup P S sup P S a=(由于每处理完一个节点时，都会得到一个新的a值，如果新得到的值大于原来的值就进行更新来记录最大值)；当算法ITM再处理下一个节点时，就可以用a来代替引理2中的W来判断是否是候选模式，从而可以提前将一些非频繁的节点删除，减少空间需求，同时也降低算法下一步的计算量。 为了区别ITM，这里将改进后的近似算法记为AITM。 5  算法复杂度分析 假设目标序列S的长度为n，间隔约束为[N,M]，设w=M-N+1，以下分别从时间和空间复杂度对算法1进行分析。 （1）算法的时间复杂度分析 在算法ITM，产生一个2项模式，需要用两个8  计  算  机  学  报  2016年  项的下标列表进行计算，其时间复杂度为O(l1(w/|∑|))，其中l1表示这两项下标列表的最小长度；若产生一个3项模式，在算法1中，仍然需要两个下标列表计算，其时间复杂度为O(l2(w/|∑|))，其中l2表示这两项下标列表的最小长度；若一个模式长度为d，假设l1、l2、l3、…ld的均值为L，则计算该长度为d的模式的时间复杂度为O(dL(w/|∑|))。在算法ITM中，每一个最长的模式对应树I-Tree上的一个叶节点，假设叶子节点为g个，则算法ITM的时间复杂度为O( / | |)giiid L w=å å1(di 表示第i个模式的长度，Li 表示产生第i 个模式需要匹配下标列表的平均长度)，一般情况下，从根到叶子的枝上包含多个频繁序列模式，即g小于频繁序列模式个数。 （2）算法的空间复杂度分析 算法ITM的主要空间消耗在I-Tree树上，该树维护2类信息，一类是结点名、父结点、孩子节点，其空间复杂度为() ON，其中N表示树上的结点个数；另一类信息为下标列表信息，该类信息只存放到叶节点和其父节点两层节点上，假设下标列表平均长度为/ | | n å，叶结点和其父结点总数为G，则其空间复杂度为O( / | |) Gn å，即算法1的空间复杂度为( / | |) O N Gn +å。 针对算法AITM，引其提前对节点的模式进行估计，判断其是否会存在超序列模式，若不存在，则不需要保存下标列表，即是叶结点，也不需要保存下标列表，该结点也不会再继续参与模式挖掘，该结点也可从树上删除。因此算法AITM的时空复杂度都会低于算法ITM。 6  实验 6.1  实验环境和参数设置 在本节中，对ITM和AITM、MGCS、MAPB、MAPD这五个算法进行实验验证和算法性能对比。对比的所有算法都是采用Java编程语言实现。实验平台：Windows 7 operating system, 8G Memory (Java heap size is 1.5G), Intel(R) Core(TM) i7-3612 CPU @ 2.10 GHz. 测试数据集采用文献[15]中的数据集，共用3个数据集Homo Sapiens AX829174、Homo Sapiens AL158070和Homo Sapiens AB038490，数据集来自于网站http://wuc.scse.hebut.edu.cn/msppwg/index. Htm。另外从每个数据集第1个字符开始，分别取长度不同的字符串组成不同的序列片段，如表1所示。在本实验中，针对目标序列的长度不同，对算法也进行性能测试。 表1. 生物数据序列 序列片段  取自数据  序列片段长度 S1  Homo Sapiens AX829174  1000 S2  Homo Sapiens AX829174  2000 S3  Homo Sapiens AX829174  4000 S4  Homo Sapiens AX829174  8000 S5  Homo Sapiens AX829174  10011 S6  Homo Sapiens AL158070  20000 S7  Homo Sapiens AL158070  40000 S8  Homo Sapiens AL158070  80000 S9  Homo Sapiens AL158070  167005 S10  Homo Sapiens AB038490  15000 S11  Homo Sapiens AB038490  30000 S12  Homo Sapiens AB038490  60000 S13  Homo Sapiens AB038490  131892 在本文的实验中，同文献[15]，将最大频繁模式长度估计为13，序列模式的最小间隔M为9、最大间隔N为12。 本文共设计了3组实验，一组测试最小支持度对算法的影响；第二组测试数据规模对算法的影响；最后测试通配符长度对算法效率的影响。 And design  6.2  不同的最小支持度对算法的影响 由于不同的最小支持度阈值会产生的序列模式个数不同，阈值越小，产生的个数会越多，同样的，算法的运行时间也会随着阈值的降低而增加，第1个实验测试了算法在不同阈值下的表现情况。数据集采用3个原始数据集序列（即序列片段S5、S9和S13）。 论文在线出版号  No.178  王乐等：基于索引树的带通配符序列模式挖掘算法  9  0.055 0.045 0.035 0.025 0.015 0.0050369121518运 行 时 间 /s最 小 支 持 度 /% ITM AITM MAPD MAPB MGCS (a) AX829174(序列S5) 0.055 0.045 0.035 0.025 0.015 0.00550100150200250300350运 行 时 间 /s最 小 支 持 度 /% ITM AITM MAPD MAPB MGCS (b) AL158070(序列S9) 0.055 0.045 0.035 0.025 0.015 0.005050100150200250运 行 时 间 /s最 小 支 持 度 /% ITM AITM MAPD MAPB MGCS                             (c) AB038490(序列S13) 图2.不同最小支持度下的运行时间对比 实验结果如图2所示，正如预期的结果，算法的运行时间都随着阈值降低而增加；当最小支持度阈值取0.005%时，算法MAPB和ITM在执行过程中发生了内存溢出，因此这两个算法没有执行时间。 从图2可以明显看出，本文给出的算法ITM和AITM的时间效率较高，如最小支持度阈值为0.015%时，在目标序列S5上，算法ITM的运行时间为0.6秒，算法AITM的运行时间为0.3秒；在序列S9上，算法ITM的运行时间为11.9秒，算法AITM的运行时间为4.9秒；在序列S13上，算法ITM的运行时间为9.2秒，算法AITM的运行时间为4.4秒。 本文给出算法主要有效记录序列模式最后一个字符在原序列中出现的位置，从而可以高效的计算出超模式的支持数，从而使算法的时间效率较高；同时本文给出的算法只需要记录树上最后一层节点上记录序列模式在原序列中出现的位置，从而也有效的提高了算法的空间效率；但是仍然在最小支持度阈值取比较低的时候，如0.005%时，算法ITM在序列S9和S13上发生了内存溢出。 0.055 0.045 0.035 0.025 0.015 0.00599.099.299.499.699.8100.0精 确 度 /%最 小 支 持 度 /% AL167005 AB131892 AX10011 图3.不同最小支持度下的精确度 由于算法ITM 内存主要消耗在维护一棵索引树上，而算法AITM通过估计一个节点是否存在超序列模式，就会提前将该节点从树上删掉，一方面降低了空间需求，另外一方面也不再需要计算该节点超序列模式的支持数，从而也提高算法的时间效率。从实验结果上看，如图2所示，相对算法ITM，算法AITM的时间效率基本上提高了1倍。尽管算法AITM是一个近似算法，该算法在3个数据集中的精确度都在99.8%以上，如图3 所示，特别在AL158070 和AB038490上的精确度基本上都为100%。 6.3  算法扩展性 在当前大数据环境下，特别是数据量越来越大的情况下，算法的扩展性尤为重要，这里测试了算法在的扩展性，如表1中已经划分好的序列片段（不同大小）为测试数据，ρ=0.015%，测试结果如图4所示。 在相同的最小支持度阈值下，目标序列长度越长，算法执行的时间会越长的，如图4所示。从图4可明显看出，随着字符串长度的增加，算法ITM和AITM的运行时间增加较为缓慢，同时所需的执10  计  算  机  学  报  2016年  行时间较少。 020406080运 行 时 间 /s原始序列长度 ITM AITM MAPD MAPB MGCS131892 15000 30000 60000 (a) AX829174(S1~S5) 020406080100167005 20000 40000原始序列长度运 行 时 间 /s80000 ITM AITM MAPD MAPB MGCS (b) AL158070(S6~S9) 02468000运 行 时 间 /s原始序列长度 ITM AITM MAPD MAPB MGCS10011 1000 2000 4000                                 (c) AB038490((S10~S13)) 图4.算法扩展性 表2. 序列模式个数 (S1~S5) 算法 序列长度 1000  2000  4000  8000  10011 ITM  5319  5191  5246  5176  5139 AITM  5304  5180  5230  5174  5138 尽管数据规模增加，数据集中包含的序列模式个数变化不大，如表2所示。由于索引树I-Tree上的节点个数和模式个数相关，当数据量变化时，树上节点个数变化不大，只是最后一层记录序列模式在原序列中位置会增多；因此随着数据量加大，本文给出算法的运行时间增加较为缓慢。 在该实验中，由于算法AITM有效的删除树上的部分节点，算法AITM较ITM的运行时间效率提高了1倍以上，同时算法的精确度也比较高，如图5和表2所示，在3个数据集上的精确度都达到了99.6%以上，如当在目标序列S5上，AITM算法仅少挖掘到1个序列模式。 99.299.499.699.8100.0AX --> 1000             2000              4000             8000            10011AB --> 15000           30000            60000          131892                  AL --> 20000           40000            80000          167005                  精 确 度 /%原始序列长度 AX AB AL 图5.不同序列片段下近似算法的精确度 6.4  通配符长度对算法的影响 改变最小通配符个数M，最大通配符个数N不变，即1 W N M = - +会随着M的减少而增大，即模式的支持数会随着W的增加而增加，从而会导致挖掘算法在计算序列模式支持数的计算量增大，理论上，挖掘算法的时间效率会随着W的增加而降低。 在本组实验中，N值固定为12，M依次取8、7、6和5，即W从5到8，另外分别取了两个不同的最小支持度值进行了算法时间效率的实验对比，即ρ=0.035%和ρ=0.025%。 实验结果如图6和图7所示，随着W值的增加，所有算法运行时间都随着W值的增加而增加，但是算法ITM、AITM和MGCS运行时间增加比较平稳，算法ITM和AITM的时间效率仍然比较好。 在不同最小支持度阈值上的实验结果也一直，当W越大，算法的运行时间都会随之增加；另外当最小支持度阈值越小，挖掘算法的运行时间越长，这里的实验结果仍然同6.2节实验中的结果。 论文在线出版号  No.178  王乐等：基于索引树的带通配符序列模式挖掘算法  11   (a) AX829174(序列S5)  (b) AL158070(序列S9)  (c) AB038490(序列S13) 图6.  通配符长度对算法的影响（ρ=0.035%）  (a) AX829174(序列S5)  (b) AL158070(序列S9)  (c) AB038490(序列S13) 图7.  通配符长度对算法的影响（ρ=0.025%） 7  结论 本文提出一个新的带通配符的序列模式挖掘算法ITM，该算法通过一遍原序列的扫描，将产生的频繁1项集及其在原序列中的索引保存在树上，在此基础上产生长度为2的序列模式，并在原树上产生一层新的节点记录长度为2的序列模式、及其序列模式索引信息；然后通过长度为2的序列模式和频繁1项集产生长度为3的序列模式，并将其维护在树上，依次类推，直到产生所有的序列模式；该算法只在树上第1层和最后一层节点上记录序列模式的索引信息。同时本文也给出一个剪枝策略，将估计不会产生超序列模式的节点提前删掉，从而提高算法的时空效率；并将该策略应用在算法ITM，得到一个近似算法AITM。实验验证了本文提出算法的有效性，时空效率有了一定的提高，给出的近似挖掘算法的结果精确度接近100%。  12  计  算  机  学  报  2016年  致  谢  感谢武优西老师在个人网站上（http://wuc.scse.hebut.edu.cn/resume/）提供了部分算法代码和测试数据。  参 考 文 献   [1]  Han  J,  Pei  J,  Yin  Y.  Mining  frequent  patterns  without  candidate generation.  Proceedings  of  the  ACM  SIGMOD  International Conference on Management of Data, Dallas, USA, 2000: 1-12.   [2] Agrawal R, Imielinski T, Swami A. Mining association rules between sets  of  items  in  large  databases.  Proceedings  of  the  1993  ACM SIGMOD  International  Conference  on  Management  of  Data, Washington, USA, 1993: 207-216.   [3]  Wang  L,  Feng  L,  Jin  B.  Sliding  Window-based  Frequent  Itemsets Mining  over  Data  Streams  using  Tail  Pointer  Table.  International Journal of Computational Intelligence Systems. 2014, 7(1): 25-36.   [4] G Liao, L Wu, C Wan. Frequent Patterns Mining over Uncertain Data Streams  based  on  Probility  Decay  Window  Model.  Journal  of Computer  Research  and  Development.  2012,  49(05):  1105-1115.(In Chinese)       (廖国琼，吴凌琴，万常选.  基于概率衰减窗口模型的不确定数据流频繁模式挖掘.  计算机研究与发展. 2012, 49(05): 1105-1115)   [5]  Y  Liu,  Y  Liu,  C  Chen.  Efficient  Algorithm  for  Mining  of  Frequent Itemsets Over Uncertain Data Streams. Journal of Computer Research and Development. 2011, 2011(S3): 1-7.(In Chinese)       (刘殷雷，刘玉葆，陈程.  不确定性数据流上频繁项集挖掘的有效算法.  计算机研究与发展. 2011, 2011(S3): 1-7)   [6] Wang L, Feng L, Wu M. AT-Mine: An Efficient Algorithm of Frequent Itemset  Mining  on  Uncertain Dataset.  Journal  of  Computers  .  2013, 8(6): 1417-1426.   [7] Wan L, Chen L, Zhang C. Mining Dependent Frequent Serial Episodes from  Uncertain  Sequence  Data.  Proceedings  of  the  IEEE  13th International Conference on Data Mining (ICDM), Dallas, USA, 2013: 1211-1216.   [8]  Wang  L,  Wang  S,  Feng  L.  High  expected  weight  itemsets  mining  on uncertain  transaction  datasets.  International  Journal  of  Advancements in Computing Technology. 2012, 4(20): 625-632.   [9] L Wang, L Feng, S Wang. An Algorithm of Mining Top-K High Utility Patterns  Without  Generating  Candidates.  Journal  of  Computer Research and Development. 2015, 52(2): 445-455.(In Chinese)       (王乐，冯林，王水.  不产生候选项集的TOP-K高效用模式挖掘算法.  计算机研究与发展. 2015, 52(2): 445-455) [10]  L  Wang,  S  Xiong,  Y  Chang,  et  al.  An  Algorithm  for  Mining  High Utility  Patterns  Based  on  Pattern-growth.  ACTA  AUTOMATICA SINICA. 2015: 1616-1626.(In Chinese)       (王乐，熊松泉，常艳芬，等.  基于模式增长方式的高效用模式挖掘算法.  自动化学报. 2015: 1616-1626) [11]  Feng  L,  Wang  L,  Jin  B.  UT-Tree:  Efficient  mining  of  high  utility itemsets from data streams. Intelligent Data Analysis （SCI&EI）. 2013, 17(4): 585-602. [12] Tseng V S, Shie B, Wu C, et al. Efficient Algorithms for Mining High Utility  Itemsets  from  Transactional  Databases.  IEEE  Transactions  on Knowledge and Data Engineering. 2013, 25(8): 1772-1786. [13]  Riondato  M,  Debrabant  J  A,  Fonseca  R,  et  al.  PARMA:  A  parallel randomized  algorithm  for  approximate  association  rules  mining  in MapReduce.  Proceedings  of  the  21st  ACM  International  Conference on  Information  and  Knowledge  Management  (CIKM  2012),  Maui,   USA, 2012: 85-94. [14]  Lin  M,  Lee  P,  Hsueh  S.  Apriori-based  frequent  itemset  mining algorithms  on  MapReduce.  Proceedings  of  the  6th  International Conference  on  Ubiquitous  Information  Management  and Communication, Kuala Lumpur, Malaysia, 2012: 76. [15] Wu Y, Wang L, Ren J, et al. Mining sequential patterns with periodic wildcard gaps. Applied intelligence. 2014, 41(1): 99-116. [16]  Zhang  M,  Kao  B,  Cheung  D  W,  et  al.  Mining  periodic  patterns  with gap  requirement  from  sequences.  ACM  Transactions  on  Knowledge Discovery from Data (TKDD). 2007, 1(2): 7. [17]  Agrawal  R, Srikant R.  Mining  sequential patterns. Proceedings  of  the Eleventh International Conference on Data Engineering, Taipei, China, 1995: 3-14. [18]  Huang  T  C.  Mining  the  change  of  customer  behavior  in  fuzzy time-interval sequential patterns. Applied Soft Computing. 2012, 12(3): 1068-1086. [19]  Li  Z,  Han  J,  Ji  M,  et  al.  Movemine:  Mining  moving  object  data  for discovery  of  animal  movement  patterns.  ACM  Transactions  on Intelligent Systems and Technology (TIST). 2011, 2(4): 37. [20] Min F, Wu Y, Wu X. The Apriori property of sequence pattern mining with  wildcard  gaps.  International  Journal  of  Functional  Informatics and Personalised Medicine. 2012, 4(1): 15-31. [21]  Zhu  X,  Wu  X.  Mining  complex  patterns  across  sequences  with  gap requirements.  International Joint  Conference  on  Artifical  Intelligence. 2007, 1(S2): S3. [22] Wu Y, Tang Z, Jiang H, et al. Approximate pattern matching with gap constraints[J]. Journal of Information Science. 2016, 42(5): 639-658. [23]  H  Yang,  L  Duan,  B  Hu,  et  al.  Mining    top-k    distinguishing   sequential    patterns    with    gap  论文在线出版号  No.178  王乐等：基于索引树的带通配符序列模式挖掘算法  13  constraint[J]. Journal of Software. 2015(11): 2994-3009.(In Chinese)       (杨皓，段磊，胡斌，等.  带间隔约束的Top-k对比序列模式挖掘. 软件学报. 2015(11): 2994-3009) [24]  X  Chai,  X  Jia, Y  Wu,  et al. Strict pattern matching  with  general gaps and  one-off  condition.  Journal  of  Software.  2015(05):  1096-1112.(In Chinese)       (柴欣，贾晓菲，武优西，等.  一般间隙及一次性条件的严格模式匹配.  软件学报. 2015(05): 1096-1112) [25]  Wu  Y,  Shen  C,  Jiang  H,  et  al.  Strict  Pattern  Matching  under Non-Overlapping  Condition.  Science  China  Information  Sciences. 2015, 58: 1-15. [26]  Wu  Y,  Fu S, Jiang  H,  et  al.  Strict  approximate pattern matching  with general gaps. Applied Intelligence. 2015, 42(3): 566-580.          Wang Le, born in 1978, PhD, lecturer,. Her research interests include data mining, statistics learning theory, and financial data analysis.  Wang Shui, 1967,    Professor, his research interests include data mining and financial data analysis.    Liu  Sheng-Lan,  born  in  1984,  Ph.D.  His  research  interests include  Computer  Vision,  machine  learning  and  neural computing.    Wang  Hui-Bing, born  in  1989,  PhD  Candidate, his  research interests include Computer Vision and machine learning.   Background Mining sequential pattern with wildcards is one important issue in data mining; and for higher volume data, more efficient algorithm is needed.  Zhang  et  al  [16]  raised  the  issue  of  mining  sequential patterns  with  periodic  restraints,  and  proposed  the  first algorithm MPP. Algorithm MGCS [21] used an m*n  matrix to represent the matching relationship of pattern P and pattern S of length  m  and  n  respectively;  although  it  improved  the calculation  for  support,  but  the  overall  efficiency  is  not satisfactory. The algorithm AMIN [20] adopted layered mining technics  from  Apriori,  and  compared  with  MPP  and  MGCS, decreased  searching  space  significantly,  but  with  the disadvantage  of  missing  some  of  the  frequent  sequential patterns.Wu et al [15] proposed algorithms MAPB and MAPD; both algorithms utilized Nettree to get more efficient mining on support, where MAPB utilized breadth-first search and MAPD utilized depth-first search, and both with creating new Nettrees. MAPD  maintained  less  Nettrees  than  MAPB;  it  was  more efficient  in  both  space  &  time  than  MAPB,  as  well  as  MPP, MGCS and AMIN. We propose a new algorithm dealing this problem; first we create  a  tree  structure  (we  call  "index-tree")  to  maintain original  data  series  as  well  as  sequential  patterns  and  pattern indexing  information;  by  scanning  patterns  of  length k(k>0) and  their  index  information,  sequential  patterns  of  length k+1 are generated tier by tier.  An approximate  mining algorithm is also  proposed;  by  estimating  the  support  number  of  super sequential pattern, non-candidate nodes are deleted prematurely to  reduce  the  number  of  nodes  on index-tree,  and  therefore  to promote algorithm efficiency. Experimental results verified the validity  of  these  algorithms  with  increase  of  time/space efficiency,  and  the  accuracy  of  approximate  algorithm  boosts up to 100%.