《序列模式挖掘的研究与实现》由会员分享，可在线阅读，更多相关《序列模式挖掘的研究与实现（4页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 4 V 0 1 3 l 1 0 ( 增刊) 序列模式挖掘的研究与实现 R e s e a r c ha n dI m p l e m e n t a t i o no fS 。q u e n t l a lP a t t e r nM 1 n l “g 朱辉生李存华 ( 淮海工学院计算机科学系连云港2 2 2 0 0 5 ) A b s l r a c t S 2 q u e n t i a lp a t t e r nm i l l i “gb a s e do na s s o c 博t i o nr u l ec a n1 呲。g a t er e l e v a
2、n c ea m o n gd a t a sw i t ht i m e ，f i n d o u tt h em a x i m a l8 0 q u e n c eo nc o n d i t i o nt h a tr n e e t i n gt h en e e d so fm l m l m u m s u p p o r t ，a n dm i n et h ec r u c i a Ip a t t e r n s w h i c hc a nP r o v i d ea i d e dd e c i s i o nf o rr e l a t i v ed e p a r
3、t m e n t s A f t e ra n a l y z i “gt h ec o n c e p to fs e q u e n t i a lp a t t e r nm i n i “g ， t h bp a p e rs t u d i e 8t h eb a s i ci d e a sa 士l d r e a l i z i n gm e t h o d e so f t w oa l g o r i t h 啪o fs e q u e n t i a lp a t t e r nm i n i n g ，a n de x p l a i n st h e i r3 p e
4、 c i f i ca p p l i c a n o nc o m b i m “gw i t hs o m ee x a m p l e s K e y 啪r d sS e q u e n t i a lp a t t e mm i n i I I g ，G e n e r a l i z e ds 。q u e n t i a lp a t t e r n tP r e f I xp r o j e c t8 8 q u e n t i a lp a t t e r n 1 引言 当今，数据库系统可以高效地实现数据的录入、 查询、统计等功能，却无法发现数据间潜在的关系和 规则，无法根据现
5、有的数据预测未来的发展趋势，缺 乏挖掘数据背后隐藏的知识的手段，导致了“数据丰 富但知识缺乏”的现象。而数据挖掘是知识发现概念 的深化，是一门交叉学科它把人们对数据的应用从 低层次的简单查询，提升到从数据中挖掘知识，提供 辅助决策的关键性数据。在这种需求牵引下，汇聚了 不同领域的研究者投身到数据挖掘这一新兴的研究 领域，形成新的技术热点。 数据挖掘的任务是从数据中发现模式，实际应 用中可根据实际作用将模式细分为以下六种n 潮； ( 1 ) 分类( c l a s s i f i c a t i o n ) ：分类模式是从数据中 选出已经分好类的训练集，在该训练集上运用数据 挖掘分类的技术，建立
6、分类模型，对于没有分类的数 据进行分类。分类模式一般表现为一棵分类树，根据 数据的值从树根开始搜索，沿着数据满足的分支往 上走，走到树叶就能确定类别。 ( 2 ) 回归( R e g r e s s i o n ) ：回归模式的函数定义与 分类模式相似，不同之处在于前者的预测值是连续 的，而后者的预测值是离散的。如给出某名教师的职 称和工龄资料，就可以用回归模式判定该教师的月 工资在哪个范围内，是在3 0 0 0 元以下，还是在3 0 0 0 元 到5 0 0 0 元之间，还是在5 0 0 0 元以上。 ( 3 ) 预言( P r e d i c t i o n ) ：预言模式是通过分类或 回
7、归得出模型，该模型用于对未知变量的预亩。预言 没有必要分为一个单独的类，其目的是对未来未知 变量的预测，这种预测是需要时间来验证的，即必须 经过一定时间后，才知道预言准确性是多少。 ( 4 ) 聚集( c l u s t e r i “g ) ；聚集模式把数据划分到 不同的组中，组间的差别尽可能大，组内的差别尽可 能小。与分类模式不同，进行聚集前并不知道根据哪 些数据项来定义组以及将要划分成哪些组，如果产 生的模式无法理解，则该模式可能是无意义的，需要 回到上一阶段重新组织数据。 ( 5 ) 关联规则( A s s o c i a t i o nR u l e ) ：关联规则模 式是发现数据项
8、之间的关联规则，从而决定哪些事 件将一起发生如“某超市中客户在购买A 的同时， 经常会购买B ，即A B 是一个关联规则。 ( 6 ) 描述和可视化( D e s c r i p t i o na n dv i s u a l i z a t i o n ) ：是对数据挖掘结果的表示方式。 序列模式是基于关联规则n 3 的挖掘方法，它能 够将数据之间的关联性与时间联系起来。为了发现 序列模式不仅需要知道事件是否发生。而且需要确 定事件发生的时间，如已购买了啤酒的顾客有可能 在一周内购买罐头。本文旨在分析序列模式挖掘的 相关概念，研究G s P 和P r e f i x S p a n 两种序列
9、模式挖 掘算法的基本思想和实现方法，并结合实例阐述这 两种算法的具体应用。 2 序列模式挖掘的相关概念 序列模式挖掘是基于时间经常发生的模式，如 某顾客在某超市购物时的顺序总是香烟一啤酒一罐 头，但这三个行为并不定需要连续如果在上述顺 序中任意两个商品之间随便插买了其它商品，仍然 满足原序列模式。本文研究的数据源是一个由客户 交易组成的大型数据库，每个交易记录由客户号 ( c u s t o m e r i d ) 、交易时间( t r a n s a c t i o n t i m e ) 、交易 中购买的项( i t e m ) 组成，同一个顾客在一个交易时 间只能进行一次交易。表1 是按
10、客户号及交易时间排 朱辉生副教授碰士主研方向；数据库技术及应用、计算机网络李存华剐教授，在读博士主研方向：智能数据分析和处理、网络安垒 3 0 0 好序的客户交易表t r a n s i n f o 。 表l客户交易表t r a n s i n f o c u s t o m e r _ i dt r a n s a c t i o n t i m e i t e m 12 0 一1 0 月一0 33 0 11 0 1 1 月一0 38 0 2 1 5 0 8 月一0 31 0 ，2 0 2 2 0 一l O 月一0 33 0 2 2 5 1 2 月一0 34 0 6 0 ，7 0 3 1 0
11、 1 0 月- 0 33 0 ，5 0 ，7 0 41 6 一0 7 月一0 33 0 4 2 0 1 0 月一0 3 4 0 ，7 0 42 3 1 2 月一0 38 0 51 8 1 0 月一0 38 0 ( 1 ) 项目集( i t e m s e t ) ：由项目( i t e m ) 组成的一个 非空集合，一个项目集可以表示为( i 1 ，i z i 。) 。 ( 2 ) 序列( s e q u e n c e ) ：不同项目枭( i t e m s e t ) 组成 的有序排列。一个序列s 可表示为8 = ( s 1 s2 s n ，s ， ( 1 j n ) 称为序列s 的一个元
12、素。 ( 3 ) 序列的长度；一个序列所包含的所有项目集 的个数称为该序列的长度，如序列( ( 3 0 ，4 0 ) ( 7 0 ) ) 是 长度为z 的序列，长度为k 的序列称为k 一序列。 ( 4 ) 子序列：对于序列p ( p t ，p 2 ，p 。) 和q ( q I ， q2 ，若存在整数i t C ( ( 2 6 ) ) 前者表示项2 和项6 是先后购买 的，后者表示项2 和项6 是同时购买的。 ( s ) 序列的支持度( 8 u p p o r t ) ：序列数据库s 中 包含序列p 的序列个数，记为s u p p o r t ( p ) 。 ( 6 ) 客户序列( c u s
13、t o m e r s e q u e n c e ) ：一个客户 所有的事务可以看成是一个序列，每一事务都由相 应的一个项目集来表示，事务按交易时间序排列就 形成了一个客户序列。 ( 7 ) 序列模式( s e q u e n t i a lp a t t e r n ) 啪：给定支持 度阈值x ，如果序列p 在客户序列数据库s 中的支 持度不低于x ，则称序列p 为序列模式。 ( 8 ) 序列模式挖掘( s e q u e n t i a lp a t t e r nm i n i “g ) ： 给定序列数据库和最小支持度阈值- 序列模式挖掘 就是要找出序列数据库中所有的序列模式。本文以
14、表1 给出的客户交易表t r a n s i n f o 为例，假设最小支 持度为4 0 ( 最少支持2 个客户) 进行序列模式挖掘。 5G s P 算法的实现 5 1G s P 算法的描述 设h 为所有k 一序列组成的集合，c - 为候选k 一 序列组成的集合，p q 为两个序列。G s P 算法描述如 F2 ( 1 ) 形成客户序列数据库和满足最小支持度阈 值的转换数据库：首先将数据源以客户号为主键、交 易时间为次键进行排序，使原来的事务数据库转换 成由客户序列组成的数据库；然后根据给定的最小 支持度阅值将客户序列数据库形成转换数据库。 ( z ) 扫描序列数据库，得到长度为1 的序列模式
15、 L 。，作为初始的种子集，即L I 一( 1 一s e q u e n c e ) ； ( 3 ) 根据长度为i 的种子集L 。，调用候选序列产 生函数c a n d i d a t e s g e n e n t i o n ，通过连接操作和剪 切操作生成长度为i + 1 的候选序列c 。l 然后扫描 序列数据库，计算每个候选序列的支持度，产生长度 为i + 1 的序列模式L 一，并将L i + 1 作为新的种子集。 重复这一过程，直到没有新的序列模式或新的候选 序列模式产生为止。f o r ( k 一2 l L h I l k + + ) d o C k c a n d i d a t
16、e s g e n e r a t i o n ； f o r e a c h c u s t o m e r s e q u e n c e ci nt h e d a t a b a s e d oi n c r e m e n tt h ec o u n to fa l lc a n d i d a t e si n C tt h a ta r ec o n t a i n e di nc 。 L k = c a n d i d a t e si nQ w i t hm i n i m u ms u p p o r t ； r e t u r nm a x i m a ls e q u e n c e si na l lL k ； ( 4 ) 返回序列模式：设最长序列的长度为n ，利 用( 3 ) 得到的序列集找出序列模式。即： 候选序列产生函数c a n d i d a t e s g e n e r a t i o n 以 k 一。(
