（计算机应用技术专业论文）从万维网日志中挖掘访问序列模式的算法研究.pdf

华中科技大学硕士学位论文 摘要 近年束，数据挖掰和万维网应粥研究是信息时代两大活跃游研究领域，将数据挖 掘技术应用予万维网就称为w e b 数据挖掘。w e b 数据挖掘的内释可以分为三个方面： 一个是w e b 海容蛉挖援，主要是从嶷大的嬲络数攒资源里发现傣愚；雯一个是w e b 结梅馥挖撼，主要是通过丈量兹w e b 链接售意来识掰援藏熬w e b 夏蘑；还有个是 w e b 访问模式的挖掘，主嚣是从网站的访问日志文件中挖掘出用户访问模式，包括关 联规则、序列模式等。 对于鼓w e b 西恚孛擦摇窭蘑户懿谤舞序囊模式，可鞋采鬻运褥懿彦囊搂式挖薅羹 法。但是对w e b 日志进行预处理后，得到的w e b 访润序列数据库中的序列长魔一般都 很长，此时采用通用的序列模式挖搠方法就会产生数量巨大的候选模式，从而降低了 挖掘速褒。 为了减少w e b 访润序列模式挖搠中产生韵候选模式，加快挖掘速度，掇出了一种 祈的w e b 访问序列模式 f j 掘算法w a p m ( w e ba c c e s sp a t t e r n sm i n i n g ) 。该弹法简化 了挖掇过程中娱遥模式煞生成爨作帮交耩褒抟诗辣，主要包含了以下秀点走骞：蔷竟 设计出一个新麓数据缭鞠w 强s - t r e e ( w e ba c c e s ss e q u e n c et r e e ) 寒记录访游序鳓释它豹 计数，避免冗长的支持艨计算。在本算法中，只要栩描两次原始的访问序列数据库就 可以构造滋一棵w a s - t r e e 。一旦构遣崽一操w a s - t r e e 后，历察剩下的挖掘互据都在 该瓣主避嚣，不再鬟要谤淹蘸嫱翡w e b 访逡亭受鼗箨毒；熬器爨漤了一个离教靛遂麴 算法从w a s t r e e 中挖掘出所有的访问序列模式。谯挖掘过程中傥用了条件搜潦技术， 使得只有那些满足最小支持度阀值的序列模式才被考虑，因此不会产生任何候选模 式，囊侠了挖疆速度。 最磺绘池了在w i n d o w s 2 0 0 0 s e r v e r 平台上酶瀛于w a p m 算法的w a p - m i n e r 系统 实现。 关键词：万维网目志，万维网访问模式，序列模式，万维网挖獭 华中科技大学硕士学位论文 a b s t r a c t i nr e c e n t y e a r s ，d a t am i n i n ga n da p p l i c a t i o n t ot h ew o r l dw i d ew e ba r ea c t i v er e s e a r c h f i e l d s ，a p p l i c a t i o no f d a t a1 1 1 i i l i n gt e c h n i q u e st ow w w ，r e f e r r e dt oa sw e bd a t am i n i n g w e bd a t am i n i n gc o n t a i n st h r e ei s s u e s ：t h ef i r s t ，c a l l e dw e bc o n t e n tm i n i n g ，i st h ep r o c e s s o fi n f o r m a t i o nd i s c o v e r yf r o ms o u r c ea c r o s st h ew o r l dw i d ew e b ；t h es e c o n d ，c a l l e dw e b s t r u c t u r em i n i n g ；t h et h i r d ，c a l l e dw e ba c c e s sp a t t e r nm i n i n g ，i st h ep r o c e s so fw e ba c c e s s p a t t e r n sd i s c o v e r yf r o mw e b s i t el o g s ，i n c l u d i n ga s s o c i a t i o nr u l e sa n ds e q u e n t i a lp a t t e m s e t c i nt h i sp a p e r , w ei n v e s t i g a t et h ei s s u er e l a t e dt oe f f i c i e n t l ym i n i n gw e ba c c e s sp a r e m s f r o ml a r g es e to f p i e c e so fw e bl o g a c c e s sp a t t e r n sc a r l _ b em i n e du s i n gs e q u e n t i a lp a r e r n m i n i n gt e c h n i q u e s h o w e v e r , i tm a yg e n e r a t eah u g eo fc a n d i d a t ep a t c e m s ，a n dr e d u c et h e m i n i n gs p e e d t or e d u c et h en u m b e ro fc a n d i d a t ep a t t e r n sd u r i n gw e ba c c e s sp a t t e r nm i n i n g ，w e p r e s e n t aw h o l l yn e wa l g o r i t h mw a p mf o rw e ba c c e s s p a t t e r nm i n i n g t h ek e y c o n s i d e r a t i o ni sh o wt of a c i l i t a t et h et e d i o u ss u p p o ac o u n t i n ga n dc a n d i d a t eg e n e r a t i n g o p e r a t i o n si nt h em i n i n gp r o c e d u r e t h ea l g o r i t h mm a i n l yc o n t a i nt w oi s s u e s ：an i c ed a t a s t r u c t u r ew a s t r e ei sd e v i s e dt o r e g i s t e r a c c e s s s e q u e n c e a n dc o r r e s p o n d i n gc o u n t s c o m p a c t l y , s ot h a tt h et e d i o u ss u p p o r tc o u n t i n gc a r lb ea v o i d e d o n c es u c had a t as t r u c t u r e i sb u i l t ，a l lt h er e m a i n i n gm i n i n gp r o c e s s i n gi sb a s e do nt h ew a s t r e e t h eo r i g i n a la c c e s s d a t a b a s ei sn o tn e e d e da n ym o r e t h ec o n s t r u c t i o no fw a s - t r e ei s q u i t ee f f i c i e n t l yb y s i m p l ys c a n n i n gt h ea c c e s ss e q u e n c ed a t a b a s et w i c e ；a ne f f i c i e n tr e e u r s i v ea l g o r i t h mi s p r o p o s e d t oe n u m e r a t ea c c e s s p a t t e r n sf r o mw a s - t r e e n oc a n d i d a t eg e n e r a t i o ni sr e q u i r e d i nt h e m i n i n gp r o c e d u r e ，a n do n l yt h ep a t t e r n sw i t he n o u g hs u p p o r tw i l lb eu n d e r c o n s i d e r a t i o n t h e i m p l e m e n t a t i o no f t h es y s t e m b a s e do nw a p m a l g o r i t h mi nw i n d o w s 2 0 0 0 s e r v e r p l a t f o r m ，w a s m i n e r , i sp r e s e n t e d k e y w o r d s ：w e b l o g ，w e b a c c e s sp a t t e r n ，s e q u e n t i a lp a t t e r n , w e b m i n i n g n 独创性声明 本人声明所呈交的举位论文是我个人在导师指导下进行的研究工作及取得的 褥究残果。尽我囊囊，狳文中己经豁饔零 惩戆蠹器癸，搴论支不篷含矮释莛缝个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贸献的个人嗣集体， 均已在文中以明确方式标明。本人党全意识到本声明的法律结果由本人承担。 学位论文作者煞名：儆 e l 期：跏午年5 月，日 学位论文版权使用授权书 本学位谂文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权僳鏊著囊黧家畜关部门域梳麓送交论文戆复露耱饔毫子舨，允诲论文被套酒移 储阅。本人授权华中科技大学可以将本学位论文的金部或部分内容编入有笑数据 麾进荦亍检索。可以采用影印、缩印或扫描等复制筝段保存和汇编本学位论文。 保密口，在年解密后遥瘸本授权书。 本论文属于 不保密口。 ( 请在以上方框癍抒“4 ”) 学位论文作者签名：噶浆 日期：跏孛年s - y lf 日 。击琴 墨日 笺膳 击谶咱笋 鹪 咿 蘑 0 劐 汀 导 期 指 日 华中科技大学硕士学位论文 1 , 1 谍邋背景 1 绪论 w w w ( w o r l dw i d ew e b ) 技术的日渐成熟使藻于这一技术的应用以惊人的速度 囱专会玺溪戆方方覆瑟渗透：扶教努、摹萼疆掇稳霜瓣售惑与鼹务戆交滚与共事，公司、 企业内部分布协同工作的管理到传缆商务模式向电子商务的转型，从而使人类交互信 息不可避免地电子化和海量化。以w e b 服务器目志为例，某些w e b 热点的翻志数据 蓐以每天数卡兆的速度绣长。扶这些大量数据中发疆毒t 鼋l 鲍、重簧款知识( 包援模式、 溉刚、可视化结搞等) ，建数据挖掘与知识发现瀚又一重要研究和应用领域。 w e b 挖掘是一项综合技术，涉及w e b 技术、数据挖掘、计算机语言学、信息学 等多个领域。不同研究卷从自身的领域瞧发，对w e b 挖掘的含义有着不同的嫒解，项 强行发也各有其髑重点。铡如，有些诗算机语言学象谈为，w e b 文挡为鱼然谗言静理 解提供了事富的语料可以从中自动地学习词语的意义，以进行词义辨析或确定词语 所属的概念。从更为一般的角度出发对w e b 挖掘作如下定义： 定义：w e b 挖摇是臻放大量w e b 文整弱集含c 孛发瑗簿禽懿模或p 。翅纂将c 看作输入，将p 看作输出，那么w e b 挖掘的过程就是从输入爱0 输出的一个映射e ： c p 。 w e b 挖援姨数据挖掘发展瑟采，霾越其定义与我粕熬知懿数据挖撼定义辍类镁。 但是w e b 挖掘与传统的数据挖掘相比有许多独特之处。首先w e b 挖掘的对象是大 量、异质、分布的w 曲文档。其次，w e b 在逻辑上是一个由文档节点和超链构成的 图，因此w e b 挖掘所褥到鲍模式霹是关于w 如内容的，墩w 是关于w 如结构 的。梵外，由于w e b 文档本身是拳络橡证或无绻籀靛，量缺芝机器可理瓣酶语义， 而传统数据挖掘的对象局限于数据库中的结构化数据，并利用关系表格等存储结构来 发现知识，因此有些数据挖掘技术并不适用于w e b 挖掘，即使可用也需要媾立在对 w e b 文稻遴行颈楚理懿蒺萋鑫之上。 w e b 挖掘从数据挖掘发展而来，数据挖掘方法通常可分为两类，一类是建立在统 计模型的然础上，采用的技术有决策树分类、聚类、关联规则等；另一类是建立一种 以礁器学习隽主懿人工餐链模型，浆怒豹方法鸯秘经霹终、遗传雾洼等。 w e b 挖掘可分为三类：w e b 内容挖掘、w 曲结构挖掘、w 酶用户访问模式挖掘h j 。 华中科技大学硕士学位论文 本文就w e b 用户访阿模式挖掘进行论述。在用户使用w e b 获取信息的过程中需要不 断地从一个w e b 站点通过超文本链接跳转到另一个站点，这种过程存在一定的普遍 性，发瑗此规喾瑟是w e b 瘸户访阔模式发瑗。这是耱完全不鼹予上述鼹诺瓣资源发 现的任务。它是对现代瓤子商务战略的一个重要支持。面向w e b 瘸户访闯模式的挖掘 是关于用户行为及潜在顾客信息的发现，包括三个阶段：即数据预处理、模斌发现及 模式分柝。数据预处理魁括：关于用户导航信息的预处理、关于内容预处理葶娃络梅的 颈处理；模式识剐除段采瘸篷方法惫括：统 辛法、税器学习帮模式识裂等方法。实现 算法可以怒：统计分析、聚类、分类、关联规则、序列模式识别等；模式分析阶段的 任务是从上一阶段收集的数据集中过滤搏不感兴趣和无关联的数据及模式。舆体的实 疆方法要佼具体采嚣躲w e b 挖蠡技术嚣定，透露蘩霜我方法蠢耀静：一瓣袋露s q l 查询语句滋行分析；另外一种将数据导入多维数据立方体中，而后利用o l a p 工具 进行分析并提供可视化的结果输出。 在此，数- 攥挖握懿主要 壬务是扶数据中发凌模式。攫握分凝要求懿不趱，笼掇出 的访问模式包括以下几种：路径分析、关联规则和序列模式等。w e b 访问关联规则是 事务内的模式，w e b 访问序列模式是零务间的模式。例如，通过路径分析发飙如下的 访问模式：访阀露址c o m p a n y p r o d u c t 2 兹客户端有7 0 先访阀怒o m p a n y ，然后依次谤 问c o m p a n y n e w ，c o m p a n y p r o d u c t s 和c o m p a n y p r o d u c t l ，这条规员 j 疆示在网页 c o m p a n y p r o d u c t 2 中包含有用的信息，但是因为用户一般通过遇回的访问路裰访问该 页，所以这个信息没有被注明；使用关联援则发现技术我们可以发现如下鲍嫂则：访 阔丽页c o m p a n y p r o d u c t l 静用户中有4 0 同时诱f 毽e o m p a n y p r o d u c t 2 ；使羯侉列挖掘 技术可以发现下列的w e b 访问序列模式：访 矗1 c o m p a n y p r o d u c t s 的用户中霄3 0 在 过去的周内在y a h o o 上使用关键字w 进行了搜索。 遥鬻实现方法是辩s e v e rl o g s 、e r r o rl o g s 秘c o o k i el o g s 等目恚文薛戆分耩挖撼 出用户访问行为、频度和内容等信息，从而找出寇的模式和规则。理解w e b 上的用 户访问模式有如下好处：针对单个用户的使用记泶对该用户进行建模，结合该用户基 本售怠分李嚣德戆使滔霹溪、令入喜好，翟弱是奁彀予离务巧壤下麓该惩户撬供与众不 同的个性化服务：w e b 服务( 数据滗、网络等) 的性能和其他服务质量是衡缀用户满 意度的关键指标，w e b 访问模式挖掘可以通过用户的拥塞记录发现站点的性能瓶颈， 姨疑示站点管理者改遴w e b 缓存繁旗、网络传输袋晦、滚量负载警衡枫制弱数攘匏分 布策臻。此舞，可戳遥过分析网络静 # 法入侵数攒找到系统弱点，提高站点寂全性， 2 华中科技大学硕士学位论文 这在电子商务环境下尤为重要；站点的结构和内容怒吸引用户的燕键。w e b 访问模式 挖掘通过挖掘用户的行为记录和反馈情况为站点设计者提供改进的依，比如页面连接 壤提应如秘缀织、那些黉嚣应筵够壹接谚垂霉等；用户怎撵馒爱w 秘筵点豹僖慧无疑是 电子商务销售商关心静邋点，用户一次访问的周期可分为被暇引、驻留、赡灏和离开 四个步骤，w e b 访问模式挖掘可以邋过分析用户点击流等w e b 日志信息挖掘用户行 为的动机，以帮助销售巍合理安捺锩鹰策略f 2 】。 在w e b 躲用户访瀚模式挖掘中，描述用户访闽模式的数掇包括l p 遗继、参考 页面、访问网期和时间、用户的w e b 站点及配置信息。这些数据可以来自于服务器端、 客户端、代理服务器端域者是公司的数据库。在开发w e b 访问模式挖掘的技术中，我 订露麓要考瘩懿下蠡冬鞠繇。 第，虽然w e b 暖惑分析可以设想出许多激动人心的潜在威用，但重簧的一点是 此类应用的成功要依赖予从这一巨大原始的日患数据中能发王觅什么样有效和可靠的 翔淤，能菠至冕多少。透露，疆i 始懿w e b 基恚数撵嚣要经过溥洗、浓缩程转换，| 三便检 索和分析有意义和有用的信息。原则上，这些预处理方法与挖掘关联规则的预处理方 法类似，只不过经常需臻定制的预处理方法。 第二，萋予u r l 、时阗、i p 建域程w e b 页瑟蠢容售患，以在w e b 匿悫数据库 上构造多嘏视图，进行多维o l a p 分析，用于找出头n 个用户，头n 个被访阔页面， 最频繁访问时间段等等，这有助发现潜在用户和市场。 第三，在w e be t 恣记录上可以进行数据挖搬，用于找出关联规则、序列模式帮 w e b 访澍懑势等。对w e b 访闯模式挖掘，逶常辩蘩采瑶迸一莎的手段获得髑户访闷 的附加信息，以便于做惩为详细的w e b 日志分析。此类附加信息包括w e b 服务器缓 冲区中用户浏览w e b 员阿的序列等。通过使用这类w e b 日志文件，可以进行些研 究工俸，蘩系统瞧戆分橱，逶遘w e b 缓存改进系统设诗，w e b 燹瑟羲取，w e b 页瑟 交换( s w a p p i n g ) ；认识w e b 访问信息的性质；瑷解用户的反成和动机。例如，有些 研究提出了可适应站点( a d a p t i v es i t e ) 的概念：即可以通过用户访问模式的举习改进 其垂身静w e b 蘧点。w e b 目恚分掇逐蠢蘩予建立镑对令薅震户戆定裁w e bl 蕤努一。 由于w e b 目志数瓣提供了不同的用户访问w e b 页面的信息，因此w e bl j 志信息 可以与w e b 内容挖掘和w e b 链接结构挖掘结合集成起来，用于w e b 页面的等级划分、 w e b 文搂瓣分类季曩多屡次w e b 信息疼躲稳造。 本课灏研究韵是扶w e b 日志中擦濑出用户访蠲序列模式，以往多采鬲邋翔的序列 华中科技大学硕士学位论文 模式挖掘算法从w e b 日志中挖掘用户的访问序列模式。但是对w e b 日志进行预处理 后，得到的w e b 访问序列数据库中的序列长度一般都很长，此时如果采用通用的序列 模式挖掘方法则会得到数量巨大的候选模式，从而降低了挖掘速度。本课题的目的就 在于研究高效的基于w 曲日志的w 曲访问序列模式挖掘算法。 1 2 国内外研究概况 访问序列模式的挖掘是w e b 挖掘的重要内容之一，有着广泛的实际应用，在提高 挖掘访问序列模式的效率方面还有许多工作值得去做。 1 2 1 国内外类似系统的研究概况 在数据挖掘技术日益发展的同时，许多数据挖掘的商业软件工具也逐渐问世。评 价一个数据挖掘工具，需要从以下几个方面来考虑：( 1 ) 可产生的模式种类的多少； ( 2 ) 解决复杂问题的能力；( 3 ) 易操作性：( 4 ) 数据存取能力；( 5 ) 与其他产品的 接口。 i b m 公司推出的w e b 文本挖掘工具i n t e l l i g e n t w e b m i n e r f o r t e x t ”，它是i b m 丌 发的i n t e l l i g e n tm i n e r 家族中的一员，它主要包括三部分：高级搜索器t e x t m i n e r ，其 最大特点是具有在线更新能力；w e b 访问工具w e b c r a w l e r ，w e b c r a w l e r 是一个可以 在一个或多个站点启动的自动机，它可以监视w e b 页的活动并变更检索使之更优化； 文本分析工具，这部分完成的才是对文本信息的挖掘，该软件是有文本提取器工具组 成，该工具提供了高效的文本信息挖掘，可以实现文本检索、文本分析、w e b 文档查 询和检索。 由s t e v e n t u r n e r 博士编写的免费个人软件a n a l o g 嗍是一个用来分析服务器日志文 件的工具，它适用于w m d o w s 及u n i x 操作系统，由于它的使用较简单，可以直接在 服务器端运行，也可以将日志文件下载到客户端，在客户端运行。比较适合个人和小 规模分析应用，是一个实用性很强的日志分析工具。 用户导航行为挖掘工具w u m ( w e bu t i l i z a t i o nm i n e r ) 9 1 是一种序列挖掘器。它 适用于从任何类型的日志文件中发现用户导航信息。w u m 是一个对日志文件进行集 成处理、查询、分析的工具，它的核心是m i n t 处理器，主要是对从w e b 臼志文件 中提取的集成信息进行分析，从而发现导航模式。m i n t 是用户和挖掘器接口的语言， 这种语言为用户提供了更为强大、灵活和全面的功能，它可以根据用户输入的语法进 行分析。正是因为w u m 能提供强大灵活的功能，所以对用户也提出了较高的要求。 4 华中科技大学硕士学位论文 要求用户掌握m i n t 语言，并具有能对挖掘结果进行分析处理的知识。m i n t 语言语 法是一个包含了s q l 查询语言中的通配符和变量的模板，它与s q l 查询语言有类似 的语法结构，对用户而言比较容易掌握和使用。 1 2 2 主要关键技术的研究概况 从w e b 日志中挖掘访问序列模式算法的研究主要包括以下几方面的技术： ( 1 ) 候选序列的产生技术 ( 2 ) 候选序列的支持度计算 这些关键技术是w e b 访问序列模式挖掘算法的研究重点和难点，下面我们逐一介 绍这几方面的关键技术。 ( 1 ) 候选序列的产生技术 为了减少产生的候选序列的数量，压缩搜索空间，目前主要有下列方法：序列 模式的a p f i o r i 性质 1 0 - t 6 】，即频繁序列的所有非空子序列都必须是频繁的。事务压 缩技术17 - 2 2 ，即不包含任何k 一序列的事务不可能包含任何( n 1 ) 序列。 ( 2 ) 候选序列的支持度计算 候选序列的支持度计算主要涉及到候选序列的匹配问题。目前的主要方法有： 使用模糊匹配技术【2 ”。在许多应用中模式并不会完全准确的出现在文本串中，拼写或 者试验数据的错误都可能导致文本串或者查询中的错误。大部分文本编辑器和查找工 具不支持带错误字符的查找，因为增加了复杂性。在文献 2 3 提出了一种灵活高效的 模糊匹配技术，以b a e z a - y a t e s 和g o n n c t 提出的字符串匹配算法【2 4 】为基础。该模糊匹 配技术支持多种测试标准和大部分类型的查询，包括任意正则表达式查询。使用字 符串的快速模式匹配算法【2 5 】。此算法可以在o ( n + m ) 的时间数量级上完成串的模式匹 配操作。其改进在于：每当一趟匹配过程中出现字符不等时，不许回溯i 指针，而是 利用已经的到的部分匹配结果向由滑动尽可能远的一段距离后，继续进行比较。使 用局部相同匹配技术【2 6 , 2 7 , 2 8 。局部相同匹配技术是从多个序列中找出相同的模式。它 的思想是先选出一个序列作为基本序列，然后在找出所有序列具有的相同片断，这些 片断在各个序列中的位置可以不同。使用该算法的时间复杂度为0 ( 1 1 l2 ) ，n 是序列 的数量，l 是序列的长度。 1 3 本课题主要研究工作 本课题研究的是基于w e b 日志的高效用户访问模式挖掘算法，从两个方面着手： 华中科技大学硕士学位论文 简化挖掘过程中支持度的计算和后选模式的生成操作，主要的研究工作包括： ( 1 ) 新的数据结构w a s t r e e ( w e ba c c e s ss e q u e n c et r e e ) 来记录w e b 访问序列 和它的计数，避免冗长的支持度计算。一旦构造一棵w a s t r e e 后，所有剩下的挖掘 工作都在w a s - t r e e 上进行，不再需要原始的w e b 访问序列数据库。在我们的算法中， 只要扫描两次数据库就可以构造一棵w a s t r e e 。 ( 2 ) 一个高效的递归算法从w a s t r e e 中枚举出所有的访问模式，在挖掘过程中 不会产生任何候选模式，只有那些满足最小支持度阀值的模式才被考虑。本算法扫描 两次序列数据库，我们将该序列数据库记为w a s d ( w e b a c c e s ss e q u e n c ed a t a b a s e ) 。在 第一次扫描中，它确定频繁事件集。一个事件是频繁事件当且仅当它出现在至少 ( i i w a s d i ) 个w a s d 的访问序列中。和i w a s d l 分别表示最小支持度阀值和w a s d 中访问序列的数目。在第二次扫描中w a p m 构造一棵w a s t r e e 。w a s t r e e 使用频繁 事件来记录用于进一步挖掘所需要的计数信息。然后w a p m 递归的挖掘w a s t r e e 以 得到所有的w e b 访问模式。 本文的章节安排如下： 第一章为序论，介绍了课题的背景、国内外研究发展概况和主要研究内容； 第二章对基本的w e b 访问模式挖掘算法及其实现进行了详述； 第三章是本文的重点，主要论述w a p m 访问模式挖掘算法； 第四章介绍了w a p m 挖掘系统的实现和性能评测； 第五章为本文的总结和展望。 6 华中科技大学硕士学位论文 2 序列模式挖掘算法分析 在介绍用于w e b 访问序列模式挖掘的序列模式挖掘算法前，先对序列模式的基本 概念和方法作出简要介绍。 2 1 序列模式挖掘定义 给定一个顾客事务数据库d ，其中的每一个事务由以下的字段组成：顾客i d 、交 易时间和在本次事务中购买的所有商品。同顾客进行的所有事务都分别具有不同的 交易时间。我们不考虑在一次事务中购买的各项商品的数量。 项集是由项组成的非空集合，序列是项集的有序表。不失一般性，假设项集被映 射为一组连续的整数，项集i 表示为( i i ：i 。) ，i ，为第j 项。序列s 表示为( s s ：s 。) ，s ， 为第j 个项集。序列( a la 。a 。) 包含在序列( b b ：b 。) 中仅当存在整数序列 i ， i ! i 。使得a ic b a2 b ，2 ，a 。量b 。成立。例如序y f j 包含在序列 中，n n ( 3 ) 至( 38 ) ，( 4j ) ( 456 ) ，( 8 ) 量( 8 ) 。但是序列 并不包含在序列 f 35 p 中，反之亦然。前者表示项3 和项5 是一前一后分别购买的， 后者表示项3 和项5 是一起购买的。在一个序列集中，如果序列s 不包含在任何其它 的序列中，则将序列s 称为最大的。 一位顾客的所有事务按照交易时间的升序排列组成的表视为一个序列，其中的每 一个事务对应于一个项集，我们将这样的一个序列称为顾客序列。如果一位顾客的顾客 序列包含序列s 则称该顾客支持序列s ，序列的支持度定义为在所有的顾客中支持该序 列的顾客所占的百分比。给定顾客事务数据库d ，挖掘序列模式的问题就是从所有的序 列中找出满足用户指定的最小支持度阀值的所有最大序列，每一个这样的最大序列就 是一个序列模式。我们将满足最小支持度阀值的序列称为频繁序列。 表2 1 是一个顾客事务数据库，表2 2 将表2 1 的数据库转换为顾客序列的集合。 将最小支持度阀值设置为2 5 ， 和 是满足最小支持度阀值条件 限制的最大序列，所以也就是我们要得到的序列模式。顾客1 和顾客4 支持序列模式 ，顾客4 在商品3 0 和9 0 之间购买了商品( 4 07 0 ) 但是因为不要求模式中的 商品是连续购买的所以他支持模式 。顾客2 和顾客4 支持序列模式 。不满足最小支持度阀值的个序列是 ，只有顾客2 支持该序列。序 华中科技大学硕士学位论文 y l j 、 、 、 、 、 和 虽然满 足最小支持度阀值但是它们都不是满足条件的最大序列。 表2 1 c u s t o m e ri d 作为主键的数据库 c l l s t o m e ti dt r a n s a c t i o nt i m e ( m d y )i t e m sb o u g h t 1 6 2 5 2 0 0 33 0 16 3 0 2 0 0 39 0 26 1 0 2 0 0 3 1 0 2 0 26 1 5 2 0 0 33 0 2 6 2 0 2 0 0 34 0 ，6 0 。7 0 36 ，2 5 2 0 0 3 3 0 ，5 0 ，7 0 46 2 5 9 33 0 4 6 3 0 2 0 0 3 4 0 ，7 0 47 2 5 2 0 0 39 0 )6 1 2 2 0 0 39 0 表2 2 顾客序列数据库 c u s t o m e rl dc u s t o m e r s e q u e n c e l i1 l ；k 一) f o re a c h k - s e q u e n c es d e l e t ef r o msa l ls u b s e q u e n c eo fs t 9 华中科技大学硕士学位论文 表2 5 变换后的数据库 c u s t o m e ri d原始的顾客序列变换后的顾客序列 映射后 l 2 ( 1 02 0 ) ( 3 0 x 4 06 07 0 p i 3 ( 3 0 ) ) ( 4 0 ) ( 7 0 ) ( 4 0 5 2 2 经典序列模式挖掘算法 挖掘序列模式的算法的总体结构是对数据库数据进行多次扫描。在每一次扫描过 程都从一个频繁序列集合种子开始，我们使用这个种子集合来生成新的候选序列，在 扫描的过程中还要同时计算这些候选序列的支持度。在本次扫描结束前，我们确定哪 些候选序列是频繁的，这些频繁的候选序列称为下次扫描的种子。在第一趟扫描时， 在挖掘频繁项集阶段得到的所有频繁1 序列作为种子集合。 有两类挖掘序列模式的算法分别叫做c o u n t - a l l 和c o u n t s o m e 。c o u n t a l l 类算法挖 掘出所有的频繁模式，包括非最大的频繁模式。在找出最大序列阶段必须将这些非最 大的频繁模式删除。c o u n t a l l 类算法的代表是a p f i o r i a l l 算法【1 。1 ，它们是从挖掘关联 规则频繁项集的a p r i o r i 算法发展而来。c o u n t s o m e 类算法的代表有a p r i o r i s o m e 1 。】 和d y n a m i c s o m e 1 0 1 两个算法。c o u n t s o m e 类算法的思想是既然我们只对最大的频繁 序列感兴趣，如果首先挖掘较长的频繁序列就可以避免挖掘那些包含在较长序列中的 子频繁序列。同时要注意不要挖掘那些不满足最小支持度阀值的较长非频繁序列，否 则挖掘这些序列的时间会超过避免挖掘那些包含在较长序列中的子频繁序列所节省 的时间。 a p d o r i s o m e 和d y n a m i c s o m e 两个算法都分为f o r w a r d 和b a c k w a r d 两个步骤。在 f o r w a r d 步骤中，找出所有具有某一特定长度的所有频繁序列，在b a c k w a r d 步骤中找 出剩下的频繁序列。这两个算法之间的本质差别在于在f o r w a r d 步骤生成候选序列的 过程不同。a p r i o r i s o m e 算法扫描一次数据库数据使用前一次扫描得到的频繁序列集 生成候选序列，然