第2卷第2期 智能系统学报 Vol.4 Na 2 2007年4月 CAAI Transactions on Intelligent Systems Apr.2007 一种挖掘带时间约束序列模式的改进算法 胡学钢，张圆圆 (合肥工业大学计算机与信息学院，安徽合肥230009) 摘要：针对带时间约束的序列模式，提出了一种改进的挖掘算法T$PM,克服了传统的序列模式挖掘方法时空开 销大，结果数量巨大且缺少针对性的缺陷.算法引入图结构表示频繁2序列，仅需扫描一次数据库，即可将与挖掘任 务相关的信息映射到图中，图结构的表示使得挖掘过程可以充分利用项目之间的次序关系，提高了频繁序列的生成 效率.另外算法利用序列的位置信息计算支持度，降低了处理时间约束的复杂性，避免了反复测试序列包含的过程」 实验证明，该算法较传统的序列模式发现算法在时间和空间性能上具有优越性. 关键词：数据挖掘：序列模式：时间约束 中图分类号：TP182文献标识码：A文章编号：1673-4785(2007)02-008905 An improved algorithm for mining sequential patterns with time constraints HU Xue-gang,ZHAN G Yuamyuan (School of Computer and Information,Hefei University of Technology,Hefei 230009,China) Abstract:An improved time constrained sequential pattern mining algorithm (TSPM)is proposed,overco- ming the problem of traditional sequential mining algorithm whose performance is poor,and result is nu- merous and short of pertinence.Graph is introduced to express the frequent 2-sequence.It need scan the transaction database only once,then mapping information related to the mining task into graph.The graph representation can fully utilize the property of item order in the mining process,thus improving the genera- ting efficiency of frequent sequences.Besides it makes use of the positional information of sequence to count support,therefore reducing the complexity of time constraints processing,and avoiding the process of testing whether a candidate sequence is contained in a data sequence.Experimental results prove the su- periority of the algorithm in time and space performance. Key words:data mining;sequential pattern;time constrain Rakesh Agrawal等对超市数据进行分析时首 展，加入了时间约束、滑动时间窗口和分类层次提 先提出了序列模式(sequential patterns),发现了这 出了泛化序列模式发现问题并给出了相应的GSP 一KDD分支.序列模式挖掘的主要任务是找出随 算法.其中时间约束是一种最基本且实用的约束，通 着时间或是特定顺序经常发生的模式.关于其挖掘 过限制模式中相邻元素间的最大和最小时间间隔 算法已经有很多研究6) (max_gap和min_gap),避免用户不感兴趣的模式 传统的序列模式挖掘过程与用户的交互限制在 产生.为处理时间约束，GSP算法通过一个前推阶 较低的范围，仅需指定抽取模式的最小支持度，最终 段(forward phase)和回溯阶段(backward phase)来 生成的模式数量很大，然而由于缺少针对性，有用的 判断一个客户序列是否包含一个候选序列.每次“前 却很少.因而需要进行大量的筛选抽取出有用的模 推”或“回溯”都要对序列元素的时间标签进行运算、 式.为此，文献[2]将序列模式的基本模型进行了扩 判断，计算量较大，并且该算法需要反复扫描数据 库，扫描的次数取决于数据库中最长频繁序列的长 收稿日期：20060620. 基金项目：安徽省自然科学基金资助项目(050420207) 度，如果数据库很大且最长频繁序列很长，则磁盘 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 2 期 智 能 系 统 学 报 Vol. 4 №. 2 2007 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2007 一种挖掘带时间约束序列模式的改进算法 胡学钢 ,张圆圆 (合肥工业大学 计算机与信息学院 ,安徽 合肥 230009) 摘 要 :针对带时间约束的序列模式 ,提出了一种改进的挖掘算法 TSPM ,克服了传统的序列模式挖掘方法时空开 销大 ,结果数量巨大且缺少针对性的缺陷. 算法引入图结构表示频繁 2 序列 ,仅需扫描一次数据库 ,即可将与挖掘任 务相关的信息映射到图中 ,图结构的表示使得挖掘过程可以充分利用项目之间的次序关系 ,提高了频繁序列的生成 效率. 另外算法利用序列的位置信息计算支持度 ,降低了处理时间约束的复杂性 ,避免了反复测试序列包含的过程. 实验证明 ,该算法较传统的序列模式发现算法在时间和空间性能上具有优越性. 关键词 :数据挖掘 ;序列模式 ;时间约束 中图分类号 : TP182 文献标识码 :A 文章编号 :167324785 (2007) 0220089205 An improved algorithm for mining sequential patterns with time constraints HU Xue2gang ,ZHAN G Yuan2yuan (School of Computer and Information , Hefei University of Technology , Hefei 230009 , China) Abstract :An imp roved time constrained sequential pattern mining algorithm ( TSPM) is proposed , overco2 ming t he problem of traditional sequential mining algorit hm whose performance is poor , and result is nu2 merous and short of pertinence. Grap h is introduced to express t he frequent 22sequence. It need scan t he transaction database only once , then mapping information related to t he mining task into grap h. The grap h representation can f ully utilize the p roperty of item order in the mining process , thus imp roving t he genera2 ting efficiency of frequent sequences. Besides it makes use of t he positional information of sequence to count support , t herefore reducing t he complexity of time constraints processing , and avoiding t he process of testing whet her a candidate sequence is contained in a data sequence. Experimental results prove t he su2 periority of t he algorit hm in time and space performance. Keywords :data mining ; sequential pattern ; time constrain 收稿日期 :2006206220. 基金项目 :安徽省自然科学基金资助项目(050420207) . Rakesh Agrawal 等对超市数据进行分析时首 先提出了序列模式 (sequential patterns) ,发现了这 一 KDD 分支. 序列模式挖掘的主要任务是找出随 着时间或是特定顺序经常发生的模式. 关于其挖掘 算法已经有很多研究[1 - 6 ] . 传统的序列模式挖掘过程与用户的交互限制在 较低的范围 ,仅需指定抽取模式的最小支持度 ,最终 生成的模式数量很大 ,然而由于缺少针对性 ,有用的 却很少. 因而需要进行大量的筛选抽取出有用的模 式. 为此 ,文献[ 2 ]将序列模式的基本模型进行了扩 展 ,加入了时间约束、滑动时间窗口和分类层次 ,提 出了泛化序列模式发现问题并给出了相应的 GSP 算法. 其中时间约束是一种最基本且实用的约束 ,通 过限制模式中相邻元素间的最大和最小时间间隔 (max_gap 和 min_gap) ,避免用户不感兴趣的模式 产生. 为处理时间约束 , GSP 算法通过一个前推阶 段(forward p hase) 和回溯阶段(backward p hase) 来 判断一个客户序列是否包含一个候选序列. 每次“前 推”或“回溯”都要对序列元素的时间标签进行运算、 判断 ,计算量较大 ,并且该算法需要反复扫描数据 库 ,扫描的次数取决于数据库中最长频繁序列的长 度 ,如果数据库很大且最长频繁序列很长 ,则磁盘
·90 智能系统学报 第2卷 VO开销会很高 1)s是d的子序列； 本文针对带时间约束的序列模式挖掘提出了一 2)transaction time (s)-transaction_time 种改进算法TSPM(time-constrained sequential (s.1)>min_gap 1及其子序 要处理的数据量.实验证明，该算法是精确和有效 列c,如果满足以下条件之一，则c是s的连续子序 的 列： 1 基本概念 1)c是由删除s中第一个元素或最后一个元素 中的某一项目得到的， 1.1序列模式的基本模型 2)c是由删除s中任一个具有多于两个项目的 定义1非空集合I=(i,2,:im}称为项集 元素中的某一项目得到的： (itemset),其中i(k=l,ml称为项item 3)c是c的连续子序列，c是s的连续子序列. 定义2序列(sequence是项集的有序表，记为 a=,其中，a(i=1,d为项集，称 2 TSPM算法 为序列的元素.含有k个项的序列长度为k,称为k 2.1算法采用的关键技术 序列(k=习a) 首先，引入图结构表示序列信息，加速频繁序列 定义3令序列a=,序列B= 的产生.算法中，以频繁项为顶点，每一频繁2序列 ,若存在整数i在 问题就是发现D中所有满足最小支持度的频繁序 Cid=20的序列中的位置有2 列，每一个这样的频繁序列代表了一个序列模式(a 个，分别为(20,2)和20,4).s在所有客户序列中的 sequential pattern) 位置组成了s的位置集合P(s).计算该集合中不同 1.2时间约束 的Cid值，得到序列s的支持数.这样，在判断候选 对于仅给定最小支持度的序列模式挖掘，可能 k+1序列是否频繁时，只需计算出其位置集合，省去 产生大量的模式，其中许多模式用户并不感兴趣.时 了反复测试序列是否被客户序列包含的过程，并且 间约束的加入，使得序列模式的定义更加灵活实用. 只需判断生成它的频繁k序列和频繁2序列之间是 用户可以根据需要限制所挖掘序列模式中相邻元素 否满足时间约束，避免了前推/回溯，简化了时间约 间的时间间隔，避免了大量冗余模式的产生，使得挖 束的处理 掘过程更有效率 2.2算法描述 给定用户指定的最大时间间隔max_gap和最 算法对数据库一次扫描，转换原交易数据库，得 小时间间隔min_gap,序列s=被客 到项目的位置集合.再通过频繁项的自连接和位置 户序列d=包含被重新定义如下： 集合的计算得到所有的频繁2序列及其位置集合， 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
I/ O 开销会很高. 本文针对带时间约束的序列模式挖掘提出了一 种改 进 算 法 TSPM ( time2constrained sequential pattern mining) ,主要策略是用图来表示所有的频 繁 2 序列 ,再利用频繁 2 序列进行时序连接逐层扩 展生成更长的序列. 考虑到时间约束只存在于相邻 元素之间 ,这种连接方式简化了处理时间约束的过 程 ,并且图中过滤了不可能成为频繁 2 序列的组合 , 因而在生成更长频繁序列的过程中 ,大大减少了需 要处理的数据量. 实验证明 ,该算法是精确和有效 的. 1 基本概念 1. 1 序列模式的基本模型 定义 1 非空集合 I = { i1 , i2 , …, im } 称为项集 (itemset) ,其中 ik ( k = 1 , …, m) 称为项(item) . 定义 2 序列(sequence) 是项集的有序表 ,记为 α= ,其中 , ai ( i = 1 , …, n) 为项集 ,称 为序列的元素. 含有 k 个项的序列长度为 k ,称为 k 序列( k = ∑| ai | ) . 定义 3 令序列α= ,序列β= , 若存在整数 i1 被客 户序列 d = 包含被重新定义如下 : 1) s 是 d 的子序列 ; 2) transaction _ time ( si ) - transaction _ time (si - 1 ) > min_gap , 1 及其子序 列 c ,如果满足以下条件之一 ,则 c 是 s 的连续子序 列 : 1) c 是由删除 s 中第一个元素或最后一个元素 中的某一项目得到的; 2) c 是由删除 s 中任一个具有多于两个项目的 元素中的某一项目得到的; 3) c 是 c′的连续子序列 , c′是 s 的连续子序列. 2 TS PM 算法 2. 1 算法采用的关键技术 首先 ,引入图结构表示序列信息 ,加速频繁序列 的产生. 算法中 ,以频繁项为顶点 ,每一频繁 2 序列 对应一条边构造图 ,再基于这张图逐层生成所有的 频繁序列. 方法是对已发现的频繁 k - 1 序列 ,从图 中获得其末项对应的顶点 ,以该顶点出发的频繁 2 序列覆盖了此频繁 k - 1 序列扩展成频繁 k 序列的 所有可能 ,因此将频繁 k - 1 序列和这些频繁 2 序列 连接 ,即用 2 序列扩展 k - 1 序列的末项 (包括项扩 展和序列扩展) ,生成候选频繁 k 序列. 另外 ,算法利用序列的位置信息计算支持度. 如 果顾客序列 c 包含序列 s , s 在 c 中的位置约定为 c 中包含 s 的最后一个元素的交易标识符 , 以 ( Cid , Tid) 表示. s 在 c 中可能有多个位置 ,例如 在 Cid = 20 的序列 中的位置有 2 个 ,分别为(20 ,2) 和(20 , 4) . s 在所有客户序列中的 位置组成了 s 的位置集合 P (s) . 计算该集合中不同 的 Cid 值 ,得到序列 s 的支持数. 这样 ,在判断候选 k + 1序列是否频繁时 ,只需计算出其位置集合 ,省去 了反复测试序列是否被客户序列包含的过程 ,并且 只需判断生成它的频繁 k 序列和频繁 2 序列之间是 否满足时间约束 ,避免了前推/ 回溯 ,简化了时间约 束的处理. 2. 2 算法描述 算法对数据库一次扫描 ,转换原交易数据库 ,得 到项目的位置集合. 再通过频繁项的自连接和位置 集合的计算得到所有的频繁 2 序列及其位置集合 , · 09 · 智 能 系 统 学 报 第 2 卷
第2期 胡学钢，等：一种挖掘带时间约束序列模式的改进算法 ·91· 以此构造频繁2序列图，用邻接矩阵表示.基于这张 表2项目及其位置集 图，通过对频繁k-1序列的末项进行频繁2序列扩 Table 2 Item and its position 展，逐层生成所有满足条件的频繁k序列.如此循 item P(s) 环，直到没有新的频繁序列产生 1,102,102,2) 算法框架： b 1.2)2.3)3.2) 输入：交易数据库D,最小支持数min_sup,最 C 1,3)2,4)3,1 小时间间隔min_gap,最大时间间隔max_gap d 1.2)2,2)3,2 1.42,5) 输出：所有满足min_sup,min_gap和max_gap (3,3 的序列模式 1)Scan D once to find all frequent items (1- 2.2.1图的构造及表示 sequences)and their positional data. 频繁2序列的生成，通过频繁1序列的自连接， 2)Generate all frequent 2-sequences and add 但是不需要再次扫描数据库来计算它们的支持度 their positional data to matrix IM and SM for ex- 而是利用频繁1序列的位置集合来构造频繁2序列 tension. 的位置集合 3)for(k=3;L.1≠φ：k++)/ 对项1和项的连接而成的序列，考虑项连接 4)Lk=中： 和序列连接2种情况： 5)for each sequence p in L. 1)项连接i和j形成序列,其位置集 6)for IM和SM中p项所在行中的非空元素{ 合由1和j的位置中完全相同的位置组成，例如对表 7)以该元素对应的频繁2序列扩展p得到k序 2中的项b和d进行项连接形成2序列，b 列p及其位置集合： 和d的位置集合中有相同的位置(3,2)，所以序列 8)if sup(p)min_sup 的位置集合为(3,2)}； 9)Lk=L&U!p子；}} 2)序列连接i和j形成序列,其位置集 10)Answer=UL 合由j的位置中能够找到1的某一位置与之匹配满 以表1中的交易数据库为例，来说明上述过程， 足i.Cid=j.Cid)and(min_sup,a的位置 给定最小支持数为2，得到频繁项也就是频繁1序 1,1)和b的位置1,2)匹配得到的一个位 列为2、:3、3、3、:2. 置(1,2)，a的位置(2,1)和b的位置(2,3)相匹配得 表1交易数据库 到的一个位置2,3)，所以的位置集 Table 1 Transaction database 合为{1,2)2,3). Cid tid item 通过对位置集合的计算可判断2序列是否频 1 繁.用图表示所有的频繁2序列，图中的顶点对应频 繁项，每条边对应一个频繁2序列，以其位置集合作 1 b,d 为边的权值.用邻接矩阵表示图，行表示序列的起 1 3 点，列表示序列终点 4 e 项连接和序列连接而成的频繁2序列代表了2 2 种类型的边，可分别用于序列的项扩展和序列扩展， 2 2 a.d 建立项扩展矩阵M和序列扩展矩阵SM来分别表 2 3 b 示.SM表示型边，其维数是频繁项的个数 2 4 M表示型边，由于同一交易中的项目不 重复且不区分顺序，所以M是一个三角矩阵，维数 2 5 e 为频繁项目数减1. 1 以表2为例，给定min_sup=2,min_gap=0, 3 b,d max_gap=2.所有频繁项两两连接得到的频繁2- 3 3 序列及其位置集合表示在图中得到SM和M如表 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
以此构造频繁 2 序列图 ,用邻接矩阵表示. 基于这张 图 ,通过对频繁 k - 1 序列的末项进行频繁 2 序列扩 展 ,逐层生成所有满足条件的频繁 k 序列. 如此循 环 ,直到没有新的频繁序列产生. 算法框架 : 输入 :交易数据库 D ,最小支持数 min_ sup ,最 小时间间隔 min_gap ,最大时间间隔 max_gap . 输出 :所有满足 min_sup ,min_gap 和 max_gap 的序列模式. 1) Scan D once to find all frequent items (1 - sequences) and t heir positional data. 2) Generate all frequent 2 - sequences and add t heir positional data to matrix IM and SM for ex2 tension. 3)for ( k = 3 ; L k - 1 ≠Φ; k + + ) { 4) L k =Φ; 5)for each sequence p in L k - 1 { 6)for IM 和 SM 中 p 项所在行中的非空元素 { 7) 以该元素对应的频繁 2 序列扩展 p 得到 k 序 列 p’及其位置集合; 8)if sup ( p′) ≥min_sup 9) L k = L k ∪{ p′} ; } } 10) Answer = ∪L k } 以表 1 中的交易数据库为例 ,来说明上述过程. 扫描数据库一遍得到项目及其位置集如表 2 所示. 位置集合中不同 Cid 个数即为项目的支持数. 假设 给定最小支持数为 2 ,得到频繁项也就是频繁 1 序 列为 :2、 :3、 :3、 :3、 :2. 表 1 交易数据库 Table 1 Transaction database Cid tid item 1 1 a 1 2 b, d 1 3 c 1 4 e 2 1 a 2 2 a , d 2 3 b 2 4 c 2 5 e 3 1 c 3 2 b, d 3 3 f 表 2 项目及其位置集 Table 2 Item and its position item P(s) a (1 ,1) (2 ,1) (2 ,2) b (1 ,2) (2 ,3) (3 ,2) c (1 ,3) (2 ,4) (3 ,1) d (1 ,2) (2 ,2) (3 ,2) e (1 ,4) (2 ,5) f (3 ,3) 2. 2. 1 图的构造及表示 频繁 2 序列的生成 ,通过频繁 1 序列的自连接. 但是不需要再次扫描数据库来计算它们的支持度 , 而是利用频繁 1 序列的位置集合来构造频繁 2 序列 的位置集合. 对项 i 和项 j 的连接而成的序列 ,考虑项连接 和序列连接 2 种情况 : 1) 项连接 i 和 j 形成序列 ,其位置集 合由 i 和 j 的位置中完全相同的位置组成,例如对表 2 中的项 b和 d 进行项连接形成 2 序列 , b 和 d 的位置集合中有相同的位置 (3 , 2) ,所以序列 的位置集合为{ (3 ,2) } ; 2) 序列连接 i 和 j 形成序列 ,其位置集 合由 j 的位置中能够找到 i 的某一位置与之匹配满 足(i. Cid = j. Cid) and (min_ sup , a 的位置 (1 ,1) 和 b的位置(1 , 2) 匹配得到 的一个位 置(1 ,2) , a 的位置(2 ,1) 和 b 的位置(2 ,3) 相匹配得 到 的一个位置(2 ,3) ,所以 的位置集 合为{ (1 ,2) (2 ,3) } . 通过对位置集合的计算可判断 2 序列是否频 繁. 用图表示所有的频繁 2 序列 ,图中的顶点对应频 繁项 ,每条边对应一个频繁 2 序列 ,以其位置集合作 为边的权值. 用邻接矩阵表示图 ,行表示序列的起 点 ,列表示序列终点. 项连接和序列连接而成的频繁 2 序列代表了 2 种类型的边 ,可分别用于序列的项扩展和序列扩展 , 建立项扩展矩阵 IM 和序列扩展矩阵 SM 来分别表 示. SM 表示 型边 ,其维数是频繁项的个数. IM 表示 型边 ,由于同一交易中的项目不 重复且不区分顺序 ,所以 IM 是一个三角矩阵 ,维数 为频繁项目数减 1. 以表 2 为例 ,给定 min_ sup = 2 ,min_ gap = 0 , max_gap = 2. 所有频繁项两两连接得到的频繁 2 - 序列及其位置集合表示在图中得到 SM 和 IM 如表 第 2 期 胡学钢 ,等 :一种挖掘带时间约束序列模式的改进算法 · 19 ·
·92· 智能系统学报 第2卷 3和表4所示. 列进行频繁2序列扩展的方式较传统的连接方式降 表3序列扩展矩阵SM 低了候选序列生成的数量和需要搜索的空间，并且 Table 3 Sequence-extention matrix SM 可以生成所有的频繁序列，可以证明其可行性， 定理1通过对频繁k序列进行频繁2序列扩 a b c d e 1,22.3)1.32,4)1,22,2 展，可以产生所有可能的频繁k+1序列 1.3)2,4) 1.402,5) 证明（反证）假设有一频繁k+1序列不能通 1,4)2,5 过频繁k序列进行频繁2序列扩展获得，那么或者 1,32,4 其前k项构成的k序列不频繁或者其最后2项构成 的2序列不频繁，但根据定义5，其前k项构成的k 表4项扩展矩阵M 序列和其最后2项构成的2序列均为此k+1序列 Table 4 Itemrextention matrix IM 的连续子序列，如果序列频繁，它的连续子序列必然 d 都频繁)，矛盾.因此，对频繁k序列进行频繁2序 列扩展，可以产生所有可能的频繁k+1序列. 1.2)3.2) 3分析与实验 d 3.1算法性能分析 2.2.2基于图(SM和M)逐层挖掘所有序列模式 与经典的针对时间约束的序列模式挖掘比较， 由SM和M,可以得到某一项可以向哪些项扩 TSPM方法有以下特点： 展，形成频繁2序列，并且详细记录了频繁2序列在 1)将与挖掘任务相关的信息表示在图中.从而 客户序列中的位置.这些提供了由频繁k:1序列向 减少了扫描原始交易数据库的次数； 频繁k序列扩展的所有信息.由频繁k-1序列生成 2)通过子序列位置集合上的先后的连接得到候 候选频繁k序列的方法如下： 选序列的支持度，避免了判断候选序列与顾客序列 对频繁k-1序列p的最后一项，扫描它所在 之间的包含关系，并简化了其中对时间约束的处理； SM和M中所在的行，其中非空元素代表了可以对 3)经典算法使用的是水平数据库的形式，在算 该k·1序列的末项进行扩展生成频繁k序列的频繁 法的第一步需要将交易数据库转换为顾客序列数据 2序列，分为序列扩展和项扩展2种.SM作序列扩 库，而TSPM算法直接由交易数据库构造项目的位 展，M作项扩展.即如果序列p的最后一项为1， 置集合，不需要做这样的转换 1)序列扩展：扫描SM第i行非空元素SM[i] 3.2实验结果 [j],把j作为独立的项集()追加到p末形成序列 通过试验，将本文提出的TSPM算法与经典的 p,p的位置由的位置中能够找到p的某 GSP算法进行比较，GSP算法是目前序列模式挖掘 一位置与之匹配满足条件(p.Cid=.Cid) 领域中广泛认可的一种算法，该算法已被引入BM and(min_sup.tid-p.tid 和序列p的完全相同的位 10%,min_gap=0,max_gap=10,运行TSPM算法 置组成 和GSP算法.TSPM算法与GSP算法得到的结果 以上一节的例子，比如对进行序列扩 相同，这说明它是正确的.同时还对它们的运算效率 展，扫描SM[b1IcJ可获得一个3序列及 做了初步的比较，实验结果如图1和图2所示.实验 其位置集合{1,3)，2,4)}，扫描SMb1le1可获得 证明随着支持度的增加，在时间性能上TSPM算法 一个3序列及其位置集合(1,4)，(2， 具有明显的优势，在空间性能上TSPM算法相对于 5)}.对进行项扩展，扫描M[blId]可获得一 GSP算法在最小支持度较低时略有改善，在最小支 个3序列及其位置集合{(1,2)} 持度较高时相差不多.空间上，TSPM不需要像 对于生成的候选序列，可以通过对位置集合中 GSP那样保存大量的候选序列，但需要保存一张频 不同Cid的计数判断其是否频繁.这种对频繁k序 繁序列图，因此，为了进一步改善其空间性能，对于 @1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
3 和表 4 所示. 表 3 序列扩展矩阵 SM Table 3 Sequence2extention matrix SM a b c d e a b c d e (1 ,2) (2 ,3) (1 ,3) (2 ,4) (1 ,2) (2 ,2) (1 ,3) (2 ,4) (1 ,4) (2 ,5) (1 ,4) (2 ,5) (1 ,3) (2 ,4) 表 4 项扩展矩阵 IM Table 4 Item2extention matrix IM b c d e a b (1 ,2) (3 ,2) c d 2. 2. 2 基于图(SM 和 IM) 逐层挖掘所有序列模式 由 SM 和 IM ,可以得到某一项可以向哪些项扩 展 ,形成频繁 2 序列 ,并且详细记录了频繁 2 序列在 客户序列中的位置. 这些提供了由频繁 k - 1 序列向 频繁 k 序列扩展的所有信息. 由频繁k - 1序列生成 候选频繁 k 序列的方法如下 : 对频繁 k - 1 序列 p 的最后一项 ,扫描它所在 SM 和 IM 中所在的行 ,其中非空元素代表了可以对 该 k - 1 序列的末项进行扩展生成频繁 k 序列的频繁 2 序列 ,分为序列扩展和项扩展 2 种. SM 作序列扩 展,IM 作项扩展. 即如果序列 p 的最后一项为 i , 1) 序列扩展 :扫描 SM 第 i 行非空元素 SM [ i] [ j] ,把 j 作为独立的项集 ( j) 追加到 p 末形成序列 p′, p′的位置由 的位置中能够找到 p 的某 一位置与之匹配满足条件 ( p. Cid = . Cid) and (min_ sup . tid - p. tid ≤max_ sup) 的位置组成. 2) 项扩展 :扫描 IM 第 i 行非空元素 IM[ i][ j ] , 把 j 作为最后一项追加到 p 的末项集中形成 p′, p′ 的位置集合由 和序列 p 的完全相同的位 置组成. 以上一节的例子 , 比如对 进行序列扩 展 ,扫描 SM[ b][ c]可获得一个 3 序列 及 其位置集合{ (1 ,3) , (2 ,4) } ,扫描 SM[ b][ e]可获得 一个 3 序列 及其位置集合{ ( 1 , 4) , ( 2 , 5) } . 对 进行项扩展 ,扫描 IM[ b][ d ]可获得一 个 3 序列 及其位置集合 { (1 ,2) } . 对于生成的候选序列 ,可以通过对位置集合中 不同 Cid 的计数判断其是否频繁. 这种对频繁 k 序 列进行频繁 2 序列扩展的方式较传统的连接方式降 低了候选序列生成的数量和需要搜索的空间 ,并且 可以生成所有的频繁序列 ,可以证明其可行性 , 定理 1 通过对频繁 k 序列进行频繁 2 序列扩 展 ,可以产生所有可能的频繁 k + 1 序列. 证明 (反证) 假设有一频繁 k + 1 序列不能通 过频繁 k 序列进行频繁 2 序列扩展获得 ,那么或者 其前 k 项构成的 k 序列不频繁或者其最后 2 项构成 的 2 序列不频繁 ,但根据定义 5 ,其前 k 项构成的 k 序列和其最后 2 项构成的 2 序列均为此 k + 1 序列 的连续子序列 ,如果序列频繁 ,它的连续子序列必然 都频繁[2 ] ,矛盾. 因此 ,对频繁 k 序列进行频繁 2 序 列扩展 ,可以产生所有可能的频繁 k + 1 序列. 3 分析与实验 3. 1 算法性能分析 与经典的针对时间约束的序列模式挖掘比较 , TSPM 方法有以下特点 : 1) 将与挖掘任务相关的信息表示在图中. 从而 减少了扫描原始交易数据库的次数 ; 2) 通过子序列位置集合上的先后的连接得到候 选序列的支持度 ,避免了判断候选序列与顾客序列 之间的包含关系 ,并简化了其中对时间约束的处理 ; 3) 经典算法使用的是水平数据库的形式 ,在算 法的第一步需要将交易数据库转换为顾客序列数据 库 ,而 TSPM 算法直接由交易数据库构造项目的位 置集合 ,不需要做这样的转换. 3. 2 实验结果 通过试验 ,将本文提出的 TSPM 算法与经典的 GSP 算法进行比较 , GSP 算法是目前序列模式挖掘 领域中广泛认可的一种算法 ,该算法已被引入 IBM 公司的数据挖掘产品中. 在 P Ⅲ1. 2 Gbp s ,256 MB 内存的机子上 ,以 JD K1. 4. 2 为开发环境进行试验. 实验数据库由 IBM 数据生成器生成. 在数据库 D1C5 T3N0. 05S4I1. 25 中 ,取最小支持度为 1 %～ 10 % ,min_gap = 0 ,max_gap = 10 ,运行 TSPM 算法 和 GSP 算法. TSPM 算法与 GSP 算法得到的结果 相同 ,这说明它是正确的. 同时还对它们的运算效率 做了初步的比较 ,实验结果如图 1 和图 2 所示. 实验 证明随着支持度的增加 ,在时间性能上 TSPM 算法 具有明显的优势 ,在空间性能上 TSPM 算法相对于 GSP 算法在最小支持度较低时略有改善 ,在最小支 持度较高时相差不多. 空间上 , TSPM 不需要像 GSP 那样保存大量的候选序列 ,但需要保存一张频 繁序列图 ,因此 ,为了进一步改善其空间性能 ,对于 · 29 · 智 能 系 统 学 报 第 2 卷
第2期 胡学钢，等：一种挖掘带时间约束序列模式的改进算法 ·93· 如何降低图的规模还有待于进一步研究 [5]HAN Peijian.FreeSpan:frequent pattermrprojected se- 1009 quential pattern mining [A ]In:Proc 2000 Int Conf Knowledge Discovery and Data Mining KDD.00)[C]. -TSPM 600 Boston,2000. 500 →GSP 400 [6]PEI J,HAN J,MORTAZAVFASL B,PINTO H, 300 200 CHEN Q,DA YAL U,HSU M C.PrefixSpan:mining 34 sequential patterns efficiently by prefix-projected pat- 最小支持度/6 tern growth[A].In:Proc 2001 Int Conf Data Engineer- 图1TSPM和GSP执行时间比较 ing (ICDE'01)[C].Heidelberg,Germany,2001. Fig.1 Comparison of time performance [7]邓明荣，叶福根，史烈，潘云鹤.挖掘泛化序列模式的一 种有效方法[U].浙江大学学报，200229(4)：415.422. 30 TSPM DENG Mingrong,YE Fugen,SHI Lie,PAN Yunhe. 20 +GSP Efficient algorithm for mining generalized sequential pat- 10 terns[J ]Journal of Zhejiang University,2002,29(4): 415.42 0 2345678910 [8]朱立运，朱建秋.带时间特征的序列模式挖掘算法TESP 最小支持度/% [U].计算机工程，2004,30(10)，51.54. 图2TSPM和GSP空间性能比较 ZHU Liyun,ZHU Jianqiu.Time-enriched equential pat- Fig.2 Comparison of memory performance tern mining algorithm TESP[J ]Computer Engineering, 结束语 2004,30(10),51-54 4 [9]周斌，吴泉源.序列模式挖掘的一种渐进算法卫].计算 序列模式发现是近几年越来越受到关注的研究 机学报，1999,22(10)：882-887. 方向.本文提出的带时间约束的序列模式发现算法 ZHOU Bin,WU Quanyuan.An incremental algorithm TSPM采用了图的数据结构和纵向数据存储格式， for mining sequential pattern [J ]Chinese Journal of 克服了经典算法在时空性能方面的不足，具有一定 Computers,1999,22(10):882.887. [10]陈金玉，樊兴华.序列模式的一种挖掘算法卩].重庆大 的优越性.未来的研究包括如何进一步降低图的规 学学报（自然科学版），2001,24(1)：92-94. 模，如何加入有效的约束条件以及与闭合序列相结 CHEN Jinyu,FAN Xinghua.Algorithm for mining se- 合，在改善时空性能的同时挖掘出更加有价值的序 quential pattern [J ]Journal of Chongqing University 列模式 (Natural Science Edition),2001,24(1):92-94. [11]刘月波，陆阶平，刘同明.基于CTD序列模式的一种改 参考文献： 进算法[U],微机发展，2005,15(3)：20.22. [1 ]A GRAWAL R,SRIKANT R.Mining sequential pat- LIU Yuebo,LU Jieping,LIU Tongming.An improved terns[Al.In:Proc of the 11st Int Conf on Data Engi- algorithm for mining sequential patterns based on CTID neering[C].Taipei,China,1995. [J].Microcomputer Development,2005,15(3):20- [2]SRIKANT R,A GRAWAL R.Mining sequential pat- 22. terns:generalizations and performance improvements 作者简介： [A].In:Proc of the Fifth Int.Conf.on Extending Da 胡学钢，男，1961年生，教授，主要 tabase Technology (EDBT)[C].Avignon,France, 研究方向为知识工程、数据挖掘、数据 1996. 结构.主持及参加国家自然基金课题、 [3]SPADE M.J.An Efficient algorithm for mining frequent 国家教委博士点专项基金课题、安徽省 sequences[A].In:Proceeding of Machine Learning 自然基金课题、安徽省教委基金课题等 Journal,Special issue on Unsupervised Learning[C].[s. 多项课题.发表论文20多篇，出版著作 1.],2003 多部. E mail jsjxhuxg @hfut.edu.cn. [4]MASSEGLIA F,CATHALA F,PONCELET P.The 张圆圆，女，1982年生，硕士研究 psp approach for mining sequential patterns[A ]In: 生，主要研究方向为知识工程、数据挖 Proc.1998 European symp.Principle of data mining and 掘 knowledge discovery (PKDD'98)[C].Nantes,France, Email zhangyuanyuan0401 @si- 1998. na.com 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
如何降低图的规模还有待于进一步研究. 图 1 TSPM 和 GSP 执行时间比较 Fig. 1 Comparison of time performance 图 2 TSPM 和 GSP 空间性能比较 Fig. 2 Comparison of memory performance 4 结束语 序列模式发现是近几年越来越受到关注的研究 方向. 本文提出的带时间约束的序列模式发现算法 TSPM 采用了图的数据结构和纵向数据存储格式 , 克服了经典算法在时空性能方面的不足 ,具有一定 的优越性. 未来的研究包括如何进一步降低图的规 模 ,如何加入有效的约束条件以及与闭合序列相结 合 ,在改善时空性能的同时挖掘出更加有价值的序 列模式. 参考文献 : [ 1 ] A GRAWAL R , SRIKAN T R. Mining sequential pat2 terns[ A ]. In : Proc of the 11st Int Conf on Data Engi2 neering[C]. Taipei , China , 1995. [ 2 ] SRIKAN T R , A GRAWAL R. Mining sequential pat2 terns: generalizations and performance improvements [ A ]. In : Proc of the Fifth Int. Conf. on Extending Da2 tabase Technology ( EDBT) [ C ]. Avignon , France , 1996. [3 ]SPADE M. J. An Efficient algorithm for mining frequent sequences [ A ]. In : Proceeding of Machine Learning Journal , Special issue on Unsupervised Learning[C]. [s. l. ] ,2003. [4 ] MASSEGL IA F , CA THALA F , PONCEL ET P. The p sp approach for mining sequential patterns [ A ]. In : Proc. 1998 European symp. Principle of data mining and knowledge discovery ( PKDD’98) [ C]. Nantes , France , 1998. [5 ] HAN Peijian. FreeSpan : frequent pattern2projected se2 quential pattern mining [ A ]. In : Proc 2000 Int Conf Knowledge Discovery and Data Mining ( KDD. 00) [ C]. Boston , 2000. [ 6 ] PEI J , HAN J , MORTAZAVI2ASL B , PIN TO H , CHEN Q , DA YAL U , HSU M C. PrefixSpan : mining sequential patterns efficiently by prefix - projected pat2 tern growth[ A ]. In : Proc 2001 Int Conf Data Engineer2 ing (ICDE’01) [C]. Heidelberg , Germany , 2001. [7 ]邓明荣 ,叶福根 ,史 烈 ,潘云鹤. 挖掘泛化序列模式的一 种有效方法[J ]. 浙江大学学报 ,2002 ,29 (4) :415 - 422. DEN G Mingrong , YE Fugen , SHI Lie , PAN Yunhe. Efficient algorithm for mining generalized sequential pat2 terns[J ]. Journal of Zhejiang University , 2002 ,29 (4) : 415 - 42. [8 ]朱立运 ,朱建秋. 带时间特征的序列模式挖掘算法 TESP [J ]. 计算机工程 ,2004 ,30 (10) ,51 - 54. ZHU Liyun , ZHU Jianqiu. Time2enriched equential pat2 tern mining algorithm TESP[J ]. Computer Engineering , 2004 , 30 (10) , 51 - 54. [9 ]周 斌 ,吴泉源. 序列模式挖掘的一种渐进算法[J ]. 计算 机学报 ,1999 ,22 (10) :882 - 887. ZHOU Bin , WU Quanyuan. An incremental algorithm for mining sequential pattern [J ]. Chinese Journal of Computers ,1999 ,22 (10) :882 - 887. [10 ]陈金玉 ,樊兴华. 序列模式的一种挖掘算法[J ]. 重庆大 学学报(自然科学版) ,2001 ,24 (1) :92 - 94. CHEN Jinyu , FAN Xinghua. Algorithm for mining se2 quential pattern [J ]. Journal of Chongqing University (Natural Science Edition) ,2001 ,24 (1) :92 - 94. [11 ]刘月波 ,陆阶平 ,刘同明. 基于 CTID 序列模式的一种改 进算法[J ]. 微机发展 ,2005 ,15 (3) :20 - 22. L IU Yuebo , LU Jieping , L IU Tongming. An improved algorithm for mining sequential patterns based on CTID [J ]. Microcomputer Development , 2005 ,15 (3) : 20 - 22. 作者简介 : 胡学钢 ,男 ,1961 年生 ,教授 ,主要 研究方向为知识工程、数据挖掘、数据 结构. 主持及参加国家自然基金课题、 国家教委博士点专项基金课题、安徽省 自然基金课题、安徽省教委基金课题等 多项课题. 发表论文 20 多篇 ,出版著作 多部. E2mail :jsjxhuxg @hfut. edu. cn. 张圆圆 ,女 ,1982 年生 ,硕士研究 生 ,主要研究方向为知识工程、数据挖 掘. E2mail : zhangyuanyuan0401 @si2 na. com. 第 2 期 胡学钢 ,等 :一种挖掘带时间约束序列模式的改进算法 · 39 ·
