（计算机软件与理论专业论文）基于web点击流的频繁访问序列挖掘研究.pdf

摘要 摘要 对国内外w 曲使用挖掘研究情况分析可知，以往的频繁访问序列挖掘算 法在动静w e b 点击流环境中仍存在诸多问题。单纯的w e b 关联规则挖掘忽略 了会话的时间特性：简单的频繁访问序列挖掘由于没有采用合理的约束思 想，挖掘出的频繁访问序列相当庞大；增量挖掘方法大部分是处理单个序 列内部的插入，很少涉及序列本身往数据库中同时插入和删除的问题；在 处理动态w e b 点击流时，基于f a l s e - p o s i t i v e 方法的算法很难处理挖掘查全率 和精度之间的矛盾。这几类问题的研究对电子商务、商业智能以及市场决 策等领域具有重要的意义。 本文首先设计了两种极大频繁访问模式挖掘算法。第一种算法采用双 向驻留时间约束会话中每个页面，有效限制了无意义页面的出现。第二种 算法根据双向约束思想对访问序列的持续时间进行约束，解决了较长访问 序列带来的问题。在挖掘带有时间约束的极大频繁访问序列时，这两种算 法的性能优于同类算法g e n m a x 、f p m a x 、s p a d e 、m s p s 和g s p 。 其次，本文提出了解决同时往数据库中插入和删除整个访问序列问题 的方法，根据序列增量模型，设计了一种增量式频繁访问序列挖掘算法。 该算法采用约束策略和网站拓扑技术，仅从插入的和删除的序列中挖掘新 的频繁访问序列，缩小了频繁访问序列的搜索空间，减少了候选子序列的 规模。在利用先前挖掘结果和约束思想的前提下，该算法在处理时间和内 存消耗上比算法i n c s p a n 和m f t p 有明显优势。 最后，提出了解决访问序列查全率和挖掘精度之间的冲突问题的方法， 基于f a l s e - n e g a t i v e 方法和时间敏感滑动窗模型，提出了一种动态w e b 点击 流中挖掘频繁访问序列算法。该算法利用带约束的加权调和计数函数来计 算每个访问序列的支持度计数，通过调节因子 来调整相关比率p 的大小。 在变化最小支持度闽值和调整调节因子 大小的情况下，该算法能够同时满 足访问序列查全率和挖掘精度的要求，其性能优于算法l o s s yc o u n t i n g 和算 法m 证e s w 。 燕山大学工学硕士学位论文 本文使用j a v a i 吾言和c + + 语言对上述四种算法进行实现，分别对四类数 据集m 0 6 0 6 a 、m 0 6 0 7 b 、b m s w e b v i e w 1 和b m s w e b v i e w - 2 进行极大频繁 访问序列和频繁访问序列挖掘，通过对不同挖掘结果的对比分析，所提出 的四种算法在解决各自的问题上是有效的。 关键词w e b 点击流：频繁访问序列：驻留时间；会话；双向约束；时间敏 感滑动窗 u a b s t r a c t a b s t r a c t b y 锄a l y z i l l gw e bu s a g em i n i n gs i t u a t i o no ff o r e i g na n dd o m a i n , w ef o u n d t h a tt h ep r e v i o u sa l g o r i t h m se x i s tm a n yp r o b l e m sf o rm i n i n gf r e q u e n tt r a v e r s a l s e q u e n c e ( f t s ) ms t a t i ca n dd y n a m i cw e bc l i c k s t r e a m se n v i r o n m e n t t h e s e a l g o r i t h m sm a yb ei n e f f i c i e n t i nd e a l i n gw i t ht h ef o l l o w i n gf o u rp r o b l e m s f i r s t l y , w e ba s s o c i a t i o nr u l e sm i n i n go f t e ni g n o r e st h et e m p o r a lc h a r a c t e ro f s e s s i o n s s e c o n d l y , s i m p l ea l g o r i t h m s o ff r e q u e n ts e q u e n c e sm i n i n gm a y g e n e r a t ev e r yh u g ec a n d i d a t es e q u e n c e s ，s i n c et h o s ea l g o r i t h m sd on o ta d o p tt h e c o n s t r a i n tm e t h o d s t h i r d l y , m o s ti n c r e m e n t a lm i n i n ga l g o r i t h m sj u s tc o n s i d e r i n s e r t i n gt h et r a n s a c t i o n si n t ot h eo r i g i n a lt r a v e r s a ls e q u e n c e s h o w e v e r , f e w a l g o r i t h m sr e f e rt ot h es i t u a t i o nt h a tw h e nt h en e wt r a v e r s a ls e q u e n c e sa l e i n s e r t e di n t oa n dt h eo l dt r a v e r s a ls e q u e n c e sa r ed e l e t e df r o ms e s s i o nd a t a b a s e f o u r t h l y , t h e r ea r es o m ed i f f i c u l t i e st oe x t e n dt h em i n i n gt e c h n i q u et od y n a m i c w e bc l i c k s t r e a m s t h em a i nd i f f i c u l t yi st h a tt h ee x i s t i n gf a l s e - p o s i t i v eb a s e d a l g o r i t h m sc a l ln o to v e r c o m et h ed i l e m m ab e t w e e nt h er e c a l lo fs e q u e n c ea n d t h ep r e c i s i o no f m i n i n gr e s u l t f i r s t l y , t w o e f f i c i e n ta l g o r i t h m sa l ep r o p o s e dt od i s c o v e ri n a x i n l u l n f r e q u e n tt r a v e r s a ls e q u e n c e s t h et w oa l g o r i t h m s a l lu s et h eb i d i r e c t i o n a l c o n s t r a i n ts t r a t e g yt oc o l l g t r a l ne a c hp a g ea n ds e q u e n c ei ns e s s i o nd a t a b a s e t h e f i r s ta l g o r i t h ms u c c e s s f u l l yl i m i t st h ea p p e a r i n gf r e q u e n c yo ft h em e a n i n g l e s s p a g e ，a n dt h es e c o n da l g o r i t h ms o l v e st h ep r o b l e m sc a u s e db yt h el o n g e r s e q u e n c e t w ok i n d s o fa l g o r i t h m so u l p e r f o l t ng e n m a x , f p m a x , s p a d e ， m s p sa n dg s pf o rm i n i n gm a x i m u mf r e q u e n tt r a v e r s a ls e q u e n c e s n e x t , a c c o r d i n gt os e q u e n c em o d e l ，t h i sp a p e rp r o p o s e san o v e la l g o r i t h m , t oa c c o u n tf o rt h ei n c r e m e n t a lm i n i n gp r o b l e m s t h ea l g o r i t h mu t i l i z e st h e c o n s t r a i n ts t r a t e g ya n dw e bs i t es t r u c t u r et of i n dt h en e w f t sf r o mt h ei n s e r t e d a n dd e l e t e dp a r to f t h ed a t a b a s es u c ht h a tt h es i z eo f c a n d i d a t es e q u e n c es e t sa n d 1 1 1 燕山大学工学硕士学位论文 s e a r c hs p a c eo ff t sc a r lb er e d u c e d t h ep e r f o r m a n c eo ft h ea l g o r i t h mi sb e t t e r t h a ni n c s p a na n dm f t pw h e nt h ep r e v i o u sm i n i n gr e s u l t sa n dc o n s t r a i n ta r e u s e d f i n a l l y , b a s e d o nf a l s e - n e g a t i v e a p p r o a c ha n d t i m e - s e n s i t i v e s l i d i n g w i n d o w , t h i sp a p e rp r o p o s e sa l le f f i c i e n ta l g o r i t h mt ob a l a n c et h ec o n f l i c t b e t w e e nr e c a l la n dp r e c i s i o ni nd y n a m i cw e bc l i c ks t r e a m s 1 1 1 ea l g o r i t h m a d o p t st h ew e i g h t e dh a r m o n i cc o u n tr u n i o nw i t hc o n s t r a i nt oc a l c u l a t et h e s u p p o r tc o u n to fe a c ht r a v e r s a ls e q u e n c e ，a n da d j u s t st h ev a l u eo fr e l a x a t i o n r a t i op b yc h a n g i n gt h er e g u l a t o r yf a c t o r 1 1 1 ea l g o r i t h mc a ns i m u l t a n e o u s l y m e e tr e c a l la n dp r e c i s i o n ，a n do u t p e r f o r m sl o s s yc o u n t i n ga n dm i n e s w w ei m p l e m e n tt h ea b o v ef o u ra l g o r i t h m sw i t hj a v aa n dc + + a l lo fo u r e x p e r i m e n t s a r op e r f o r m e do nt h ef o u rd a t a s e t s ，m 0 6 0 6 a , m 0 6 0 7 b ， b m s w e b v i e w - 1a n db m s - w e b v i e w - 2t om i n em a x i m u m & e q u e mt r a v e r s a l s e q u e n c e sa n df t s t h ee x p e r i m e n t a l r e s u l t ss h o wt h ef e a s i b i l i t ya n d e f f e c t i v e n e s so fo u ra l g o r i t h m s k e y w o r d sw e b c l i c ks t r e a m s ；f r e q u e n tt r a v e r s a ls e q u e n c e ；d w e l lt i m e ；s e s s i o n ； b i d i r e c t i o n a lc o n s t r a i n t ；t i m e - s e n s i t i v es l i d i n gw i n d o w s i v 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于w e b 点击流的频繁访 问序列挖掘研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独 立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和 集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字；1 老帮舜。参1 日期：枷年1 1 月，j 日 燕山大学硕士学位论文使用授权书 基于w e b 点击流的频繁访问序列挖掘研究系本人在燕山大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大 学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解燕山 大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文 的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采 用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密叮： ( 请在以上相应方框内打“”) 作者签名： 导师签名： 佬啸纠 移缴、 日期：砌侔1 月留日 日期：协( 年j 1 月z 吁日 第1 章绪论 第1 章绪论 随着网络技术的快速发展，尤其是i n t e m e t 的广泛应用，使得数据挖掘 的对象从数据库中的数据延伸到网络上的数据，因此w e b 挖掘成为数据挖掘 研究的一个新的方向。根据数据资源的种类，w e b 挖掘可以分三类，分别为 w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘 1 】。课题主要涉及到w 曲使用 挖掘方面的内容。 1 1 w 曲使用挖掘技术 w e b 使用挖掘就是把数据挖掘技术应用到w 曲点击( 日志) 数据中，从而 发现使用模式的过程 2 1 。这些使用模式是隐含的和事先未知的，要通过w e b 点击数据的收集和预处理，才能获得有用的模式，最后经过分析，把使用 模式应用于决策、智能、个性化和推荐系统等领域。 1 1 1w e b 使用挖掘研究背景及意义 i n t e m e t 的通信量和w e b 的复杂度都以惊人的速度飞速发展，越来越多 的用户上网发布信息和查找信息。虽然i n t e r n e t 上的数据是海量的，但是由 于w e b 是无结构的和动态的，并且w e b 页面的复杂度远远超过了文本文件， 用户想在海量的w e b 数据里找到自己想要的信息非常困难。基于信息检索 技术出现了许多搜索引擎工具【3 】，但这些工具的查全率和精确度较低，不能 满足用户的特殊请求，个性化不强。为了解决这些问题，可以将传统的数 据挖掘技术和w e b 结合起来，进行w e b 使用挖掘【4 5 1 。目前，越来越多的数 据以流的形式出现。w e b 数据流就是数据流的一种。与静态w e b 数据相比， 它具有潜在无穷大、迅速、时变和连续到达等特点。其中的数据按照固定 的次序，只能被读取一次或几次，不再是永久的关系形式，数据无法全部 保存后再进行处理。数据流的出现直接给w e b 数据的快速分析、气象监测和 传感器网络分析等应用带来迅速的经济效益。实际上，w e b 使用挖掘要涉及 到多方面的知识，如统计学、机器学习、模式识别、数据库和数据可视化 燕山大学工学硕士学位论文 等多个领域 6 - 8 1 。 随着w e b 技术的进一步发展，w 曲站点设计、电子商务、信息组织和个 性化服务等各项工作变得越来越复杂。因此，如何有效的利用w w w 这个庞 大的信息仓库，已成为了等待解决的问题。由于w e b 本身分布的复杂性，直 接对其挖掘比较困难，而提供w e b 信息资源的w 曲服务器能够记录每次w e b 访问的详细点击信息，例如页面u r l 、i p 地址、日期、用户的w e b 站点及配 置信息和用户个人资料等。因此，w e b 站点和w e b 服务器的设计难度相应提 高，w e b 使用挖掘的目的就在于解决这些问题。通过对w e b 使用数据进行挖 掘，站点管理者可以发现用户的访问模式，改进w e b 服务器的设计和提高 w e b 服务器的性能，以方便用户使用，增加个性化服务和电子商务中发现 潜在的客户等。另# b w e b 使用挖掘还可以应用在w e b 数据管理、科学研究和 商业决策等方面。 1 1 2w | e b 使用挖掘的任务 w e b 使用挖掘的任务就是从w 曲点击日志中，挖掘用户的频繁访问序列 ( f r e q u e n tt r a v e r s a ls e q u e n c e ，简称f t s ) ，预测用户的浏览行为。通过频繁 访问序列分析可以识别用户的忠实度、爱好和满意度，也可以发现潜在用 户，增强站点的个性化和竞争力。在实际应用中，w e b 使用挖掘任务又可分 为统计分析、聚类发现、关联规则发现、频繁访问序列发现、分类发现和 依赖关系发现等。 统计分析是用统计技术挖掘w e b 使用数据中有用的知识。常用的统计技 术有贝叶斯定理、预测回归、对数回归和对数线性回归等。这些技术可用 于分析网页的访问频率，网页的访问时间和访问路径。可用于系统性能分 析、发现安全漏洞、为网站修改和市场决策提供支持。 聚类发现技术是在w e b 使用数据中寻找彼此相似的对象组，这些数据基 于距离函数求出对象组之间的相似度。根据对象的相似度与阈值之间的关 系，把满足条件的用户分成一组。聚类发现技术可以用于电子商务中市场 分片和为用户提供个性化服务等。 关联规则发现是在w e b 使用数据中挖掘使用数据之间的关联模式。常用 2 第1 荤绪论 在访问过的网页中，在这些页面中找出彼此之间的关联信息。这有利于优 化网站组织、网站设计、网站内容管理和市场分析，通过市场分析可以知 道哪些商品被频繁购买，哪些顾客是潜在顾客。 频繁访问序列发现是在w e b 使用数据中由不同的访问序列组成的集合。 其中每个访问序列由不同的元素按顺序有序排列，每个元素由不同项目组 成，同时给定一个用户指定的最小支持度阈值，频繁访问序列挖掘就是找 出所有的频繁子序列。在使用挖掘中用于发现会话内部网页之间的时间相 关性。 分类发现技术主要用途是将用户的访问信息归入某一特定类中，它与 机器学习联系紧密。常用的技术有决策树、k 最近邻居和支持向量机等。 依赖关系是发现两个元素之间的依赖关系，如果一个元素a 的值可以推 出另一个元素b 的值，则b 依赖于a 。在w e b 使用挖掘中依赖关系分析的结果 有时可以直接提供给用户。w e b 使用挖掘中的依赖主要是描述w e b 领域中各 种变量间的显著依赖关系。依赖关系发现可以提供理论化分析用户行为的 框架，提高网上产品销量，提高用户的访问量。常用的方法有马尔可夫链 和贝叶斯网络等。 其中，频繁访问序列挖掘由于在实际中具有广泛的应用，已经成为w e b 挖掘中的研究热点之一。 1 2 频繁访问序列挖掘技术 频繁访问序列挖掘即从w e b 点击数据中发现频繁的序列，它是指挖掘基 于时间或者其它顺序出现频率高的访问序列，是一类非常重要的w e b 使用挖 掘问题。 1 2 1 国内外研究现状 r a g r a w a l 和r s r i k a n t 在1 9 9 4 年提出了基于a p r i o r i 特性的算法【9 】。a p r i o r i 特性首先被应用在关联规则挖掘中。m a x - m i n e d l 0 1 、g e n m a x “1 、d m f i a t l 2 】 和f p m a x l l 3 1 等算法是针对整个数据库挖掘极大频繁项目集。当数据库非常 庞大时，m a x - m i n e r 和g e n m a x 算法会产生大量的候选项集，频繁扫描数据， 燕山大学工学硕士学位论文 形成n p 难度、频繁f o 操作等问题。f p m a x 和d m f i a 算法中的数据结构很可 能不再适合用主存存储，要利用磁盘存储数据集，这就出现挖掘时间效率 问题。另外，这些关联算法几乎没有考虑事务中的时间信息。 r a g r a w a l 等人在1 9 9 5 年针对超市购物篮数据分析问题首先提出了序列 模式挖掘的概念【1 4 】。现有的序列模式挖掘算法主要分为四类。第一类是基 于a p r i o r i 特性，人们提出了一系列类a p f i o f i 的序列模式挖掘算法，如g s p 算法1 5 1 、a p r i o r i a l l 算法 1 4 1 、p s p 算法【1 6 1 、s p a d e 算法【7 l 和s p a m 算法 18 】等。 第二类是j h a r t 等人提出的基于分而治之策略的算法，如f r e e s p a i l 算法【1 9 】和 p r e f i x s p a n 算法【2 明等。第三类是极大频繁序列挖掘算法，如m f s 口1 1 算法和 m s p s 2 2 1 算法，而这些算法由于没有采用约束策略，当序列过长时，会消耗 大量的内存空间。第四类是增量挖掘频繁访问序列算法，如i i l c s p a l l 算法瞄】、 m f t p 算法【州、i s m 算法【2 5 】和1 u e 算法 2 6 1 等。而这些算法没有考虑同时往数 据库中添加和删除的情况。 c o o l e y 和s r i v a s t a v a 调查了w 曲挖掘中的主要技术趋势和研究问题i 2 , s 】， 并对w e b 挖掘分类。c h e n 等人首先提出了f s 算法和s s 算法在w e b 点击流中 挖掘路径访问模式【2 ”。然而这两个算法只能够挖掘静态w e b 点击流，不能 用于处理动态w e b 点击数据。s p i l i o p o u l o u 等人提出了一种访问模式挖掘器 w u m l 2 刖，w u m 通过使用m i n t 挖掘语言来挖掘频繁访问模式。b o r g e s 和 l e v e n e 提出了一种超文本模型来获得用户的访问行为模式 2 9 。j p e i 等人基 于w a p - t r e e 数据结构提出了一种有效的频繁模式增长算法w a p i l l i n c 【3 0 l ， w a p m i l l e 是一个两次扫描w e b 数据库算法。当w e b 使用数据量非常庞大时， w a p - t r e e 结构也因变得庞大不再适合内存存储。 目前国外存在很多数据流项目，如s t a n f o r d 大学的s t r e a m 3 ，加州大 学b e r k e l e y 分校的t e l e 伊a p h 3 2 矧，布朗大学的a u r o m 【3 4 】等。s t r e a m 项目旨 在研究通用的数据流管理系统，主要研究数据流查询语言的语法及语义 3 5 1 ， 数据流系统中操作符的调度与资源优化管理问题 3 6 1 。t e l e g r a p h 项目的特点 是能够自适应的查询处理流数据【3 ”。a u r o r a 项目研究了数据元组在操作符 之间的优化路由问题，能够更加充分的优化使用系统资源以提高服务质量。 在数据流中挖掘频繁模式可分为三个不同领域，分别为界标窗口模型， 4 第1 苹绪论 倾斜时间窗模型和滑动窗模型。m a n k u 和m o t w a n i 提出了界标窗口模型【3 8 1 ， 利用特定时间点和当前时间之间完整的历史数据进行挖掘。g i a n n e l l a 开发 了倾斜时间模型，在较细的粒度上挖掘最近的数据，在较粗的粒度上挖掘 时间较久的数据【3 9 】。t e n g 提出了滑动窗模型，给出一个窗口大小为w ，只利 用最近的事务进行挖掘 4 0 】。也就是说，随着一个新事务的到达，旧事务在 滑动窗口中被作废。 目前现有数据流上频繁模式挖掘算法主要集中在界标窗口模型【3 8 4 1 , 4 2 1 。 m a n k u ，c h a n g 和l e e 提出t l o s s yc o l l n _ 血g 算法【3 研和c a l l m 算法【4 3 】，采用估 计策略挖掘频繁模式的近似集。然而，这些算法大部分采用固定粒度处理 数据流，不易区分旧数据和新数据。在许多情况下，频繁模式是对时间敏 感的，随着时间的变化，旧的频繁模式可能会失去其兴趣和重要性。为了 克服这些困难，许多基于滑动窗口模型的算法被提出。滑动窗主要关心数 据流最近的变化及趋势。l e e 基于滑动窗模型，提出了一种从候选2 项集中 挖掘频繁模式的方法，但这种方法由于产生大量候选项集而消耗大量存 储空间。c h i 提出的m o m e m 算法【4 5 】主要是用来发现滑动窗中封闭的频繁模 式，不适合挖掘频繁访问序列。y u 利用c h e m o f f 趔界理论提出了一种f d p m 算法【删，该方法使用预先定义的阈值来控制内存消耗和输出的质量。c h e n g 基于f a l s e - n e g a t i v e 方法提出了一种m i n e s w 算法 4 7 1 ，此算法设计一种逐渐增 加的最小支持度函数来计算每个项集的支持度。尽管这两种算法能够克服 由f a l s e p o s i t i v e 方法产生的一些弊端，但由于二者没有采用约束机制，不能 处理由相关比率p 引起的问题。以前的工作只考虑将固定数量的事务作为 滑动窗挖掘基本单元，即是事务敏感滑动窗模型。然而，这对用户来说不 容易指定基本单元的大小。相反，用户容易指定一个时间期间作为处理基 本单元。 1 2 2 存在的问题 通过分析目前国内外频繁访问序列挖掘领域的研究现状，以及在对频 繁访问序列挖掘算法的研究过程中，发现存在如下问题。 首先，w e b 关联规则挖掘问题核心是频繁页面和频繁页面集的挖掘问 5 燕山大学工学硕士学位论文 题。以往的挖掘算法很少考虑w e b 点击数据中的时间信息，而这些时间信息 在挖掘过程中是非常有用的。w e b 包含着海量的使用数据，发现的频繁页面 集和模式非常繁多，有些毫无意义，这样会耗尽内存空间。如何找到一种 节省内存空间，并且又能够自动删除那些无意义的页面集的高效挖掘算法 是一个需要解决的问题。 其次，传统的频繁访问序列挖掘算法是通过挖掘候选序列发现频繁序 列，而这些算法又很少能有适合挖掘长序列的，若长度为l 的序列是频繁的， 要全部罗列出2 0 个子序列，l 过长时，造成极大的空间浪费。而自治性找出 w e b 使用数据中所有频繁访问序列又不太现实。如何找到一种合适的算法来 解决上述问题是非常有必要的。 再次，w e b 使用数据增长迅速，一些数据可能过时，先前的频繁访问序 列会随着新序列插入和旧序列删除而改变，若从已更新数据库中重新挖掘 频繁访问序列，这样不仅会增加处理时间，而且还会增加数据存储量。以 前的增量挖掘算法一般只是考虑在单个序列中插入、删除操作，很少有考 虑序列本身从数据库中插入、删除的。因此，在数据库同时插入和删除整 个访问序列的增量式挖掘问题很值得研究。 最后，在w e b 数据流中挖掘频繁模式一般采用f a l s e p o s i t i v e 方法进行算 法设计，即是利用相关比率p 控制整个挖掘过程。如何有效控制p 的大小， 会使用户陷入两难局面。若使用较大的p ，内存消耗降低，一些访问序列 查全率提高，但挖掘结果的精确性降低。若使用较小的p ，能够提高挖掘 结果的精度，但同时要维护由于较小的p 而产生大量的候选序列，这样不 但增加了内存消耗，而且还降低了挖掘效率。因此，如何设计一个基于f a l s e - n e g a t i v e 方法的、能够克服相关比率p 所导致的问题的算法是一个急需解决 的问题。 1 3 课题研究内容 本课题“基于w e b 点击流的频繁访问序列挖掘研究”来源于河北省普通 高等学校博士科研基金项目和河北省教育厅二o o 六年科研计划项目。 本课题研究的目标是解决1 2 2 节中提到的四个问题。课题的具体研究 6 第1 章绪论 内容安排如下。 为了解决w e b 关联规则挖掘中存在的问题，本文提出一种新的挖掘算法 m f p s m ( m a x i m u mf r e q u e n tp a g es e tm i n i n g ) ，来挖掘极大频繁访问页面集。 由于极大频繁页面集已经包含了频繁页面集，因此利用这种方法能够减少 生成频繁页面集的数量。算法m f p s m 采用双向约束思想，深度优先构建 f p d t - t r e e - ( f r e q u e n tp a g et r e ew i t hd w e l lt i m e ) 结构，只把符合要求的页面 存储该结构中，这样能够缩小搜索空间，减少内存消耗，提高挖掘效率。 为了解决较长访问序列带来的问题，本文提出算法m f t p m ( m a x i m a l f r e q u e n tt r a v e r s a lp a t t e r nm i n i n g ) ，在静态w 曲点击流中挖掘极大频繁访问 序列，该算法能够适应访问序列长短的变化。并设计一种带约束的新型树 型数据结构d f t s t r e e ( d w e l lt i m ec o n s t r a i n e df r e q u e n tt r a v e r s a ls e q u e n c e s t r e e ) 存储频繁访问序列。算法m f t p m 在约束环境中更能显示其优越性。 为了解决从会话序列数据库中同时插入和删除访问序列的增量挖掘问 题，本文设计一种扩展格数据结构i e - l a t t i c e ( i m p r o v e de x t e n d e dl a t t i c e ) 来存 储先前的挖掘结果，基于这种结构提出一种有效的算法i m f t s ( i n c r e m e n t a l m i n i n gf r e q u e n tt r a v e r s a ls e q u e n c e ) 。该算法利用先前的频繁序列、约束策 略和网站拓扑结构，仅从插入的和删除的会话序列中挖掘新的频繁访问序 列，从而减少执行时间和存储空间。 为了解决相关比率p 导致的问题，本文给出p 的上下限参数，并采用 上下限参数的加权调和平均数来代替相关比率p 。基 ：f a l s e - n e g a t i v e 方法 提出一种新的基于时间敏感滑动窗的动态w e b 点击流频繁访问序列挖掘算 法f t s s t r e a m ( f r e q u e mt r a v e r s a ls e q u e n c em i n i n gi nc l i c ks t r e a m ) 。该算法采 用加权调和计数函数计算每个访问序列的支持度计数。算法f t s s t r e a m 不 仅能克服p 产生的问题，而且能够满足挖掘精度和序列查全率，同时降低 内存消耗。 1 4 本文的结构安排 本文的余下部分组织如下。 第2 章介绍了在静态点击环境下，挖掘极大频繁页面集算法m f p s m 和 7 燕山大学工学硕士学位论文 极大频繁访问序列算法m f t p m ，并给出相应的性能分析和实例说明。 第3 章给出了在会话序列库同时插入和删除相同数目访问序列时的挖 掘算法i m f t s ，并给出了算法分析和实例说明。 第4 章介绍了在动态w e b 点击流环境中，挖掘频繁访问序列挖掘算法 f t s s t r e a m ，并给出详细的性能和理论分析。 第5 章将对于前3 章所提出的算法利用j a v a 语言和c + + 语言进行编程实 现，介绍实验所用数据集的来源和开发环境的搭建，并给出较为全面的性 能实验分析。 最后，对研究内容做出总结，并对未来的研究方向进行展望。 8 第2 章静态点击流的极大频繁访问序列挖掘 第2 章静态点击流的极大频繁访问序列挖掘 2 1 引言 关联规则是在w e b 使用数据中挖掘频繁页面集的重要技术。目前大多数 关联规则挖掘算法是a p r i o r i 系列算法及其改进算法。但是，a p r i o r i 系列算 法有一个缺陷，即在挖掘时可能需要多次重复扫描数据库并且会产生大量 的候选集。同样，传统的频繁序列挖掘算法g s p i ”】、s p a d e t l 7 】等大多是通 过挖掘候选序列来发现频繁序列。若长度为l 的序列是频繁的，需要罗列出 2 。个子序列，l 过长时，造成极大的空间浪费。所以无论是挖掘频繁页面集 还是频繁序列都要考虑繁多的候选项集和候选序列。由于极大频繁模式已 经隐含了所有的频繁项和频繁序列，而且，许多挖掘应用也只需要极大频 繁模式，而不用挖掘所有的频繁集，因而近年来，许多研究者开始了对极 大频繁模式的研究。 本章针对挖掘频繁项和频繁序列中存在的问题，在f p - t r e e h 8 i 的基础上， 设计了两种树型存储结构f p d t - t r e e 和d f t s t r e e 。利用这两种结构对带有约 束的数据库进行压缩存储。在此基础上提出两种新的挖掘算法m f p s m 和 m f t p m ，实验表明这两种算法降低了挖掘时间，提高了挖掘效率。 2 2 双向约束策略的思想 由于w e b 包含海量的信息数据，发现的频繁页厦集和频繁序列非常繁 多，有些毫无意义，而自治性找出w e b 数据中的页面集和访问序列是不太现 实的。j h a n 提到数据挖掘是一个交互过程，决策者应该直接通过查询语言 或用户图形接口参与挖掘过程，找出决策者自己想要的页面集和访问序列 集【4 9 j 。因此，许多研究者把约束的思想加入挖掘过程中，调整候选集的生 成方法，只对与约束条件有关的项目进行了处理。现有的约束有项目约束、 长度约束、模型约束、集合函数约束和项目属性约束等。在这些约束基础 上的算法都存在一些弊端，约束条件改变较小时，有一定的效果，但对于 9 燕山大学工学硕士学位论文 约束条件改变很大时，不但不能提高效率，反而会降低算法的效率。因此 本章根据用户的挖掘目的提出了一种双向约束的思想，对用户的某个访问 属性进行双向约束。其具体思想是给出一个最小属性约束阈值和一个最大 属性约束阈值，利用这两个阈值同时约束用户的某个访问属性。根据最小 和最大约束阈值，决策者可以制定出多项约束规则，然后再根据这些约束 规则剔除数据集和候选集中不符合要求的项和序列。虽然这种方法限制了 一些项和序列的出现频率，但是，能够找出更加有意义的项和序列。 2 3问题定义与分析 为了描述问题的方便，此节给出了频繁访问页面集和频繁访问序列挖 掘问题的一些基本定义和基本分析。设非空集合i = 饵，只，只) ，其中 最( 1 k n ) 称为w e b 页面( p a g e ) 。 定义2 1 ：w e b 点击流是用户访问w e b 站点时一组连续的页面访问序列， 表示为w c s = ，只i ，1 i s m 。 定义2 2 ：会话( s e s s i o n ) 是某个用户阶段性的页面测览构成的点击流。 对于同一用户，在挖掘极大频繁访问页面集和极大频繁访问序列之前， 要对不同的会话重构。在重构过程中，有两个必要的时间约束是很重要的。 任一个会话持续的时间，不能超过预先定义的时间阈值，通常是3 0 分钟【5 0 1 。 任意两个连续被访问的页面时间间隔不能超过预先定义的时间阈值，通常 是1 0 分钟【5 i l 。 定义2 3 ：驻留时间( d w e l lt u n e ) 指的是用户在会话序列中浏览某个w e b 页面的实际时间。 设只和只+ 。是一会话序列中两相邻页面。z 为页面只的请求时间，l + 。为 页面只+ 。的请求时间。则页面只的驻留时间如图2 - 1 所示。 广 田臣，啮田 i 兰塑堡堡i 些型! ! ! ! 竺! ! 竺! 坐!l 堡业! ! 坚! ! 堡i t i t 1 t 2k l 图2 - 1p i 的驻留时间 f i g 2 - 1d w e l l t i m eo f p i 1 0 第2 章静态点击流的极大频繁访问序列挖掘 设五为页面只的加载时间，为p 的附属文件加载时间，页面只的驻 留时间设为t o 。则五= 五- t , ，正= 五一五。计算页面只的驻留时间t o 时有 两种情况，如公式( 2 1 ) 至( 2 - 4 ) 所示。 t o = z + 。一互一 ( 互一z ) + ( t o 一五) 】( 2 一1 ) 瓦= z + 一z 一( 互+ 五)( 2 2 ) 瓦= z 。一z 一( 互一z ) ( 2 3 ) 瓦= 0 。一霉一乃( 2 - 4 ) 在计算页面的驻留时间时，按照公式( 2 3 ) 或公式( 2 4 ) 的情况，不考虑 附属文件的加载时间正以及流媒体( 如r e a la u d i o ，m p e g 等) 的加载时间。 根据双向约束思想和决策者的意图，可以设定两个驻留时间阈值，最 小驻留时间阈值 和最大驻留时间阈值疋。利用 和九约束会话中的每个 页面，同时根据 和厶制定两条约束规则，用来排除会话、频繁访问页面 集和频繁访问序列中不合决策者要求的w e b 页面和序列。 ( 1 ) 若用户在某个页面的实际驻留时间小于 ，则表明该页面内容不符 合用户的需要或页面有错误。从会话序列中剪除该页面。 ( 2 ) 若用户在某个页面的实际驻留时间大于九，则表明用户离开该页面 或重新访问已在浏览器缓存中的该页面，而缓存中的页面不会在w e b 日志中 留下任何信息。该页面不属于访问序列。 2 4m f p s m 和m f t p m 算法的设计 2 4 1问题定义 假设d b 是由会话组成的数据库，i = 嘏，足，只) 为所有页面组成的 集合，只是被访问过的页面组成的集合( 只i ) ，s s e t = s 1 ，s 2 ，s 。) 是 由所有的会话组成的集合，其中，s ，表示d b 中的任意一个会话，并且记为 墨- - ，且s ，s s e t ，只s j ，1 j sr ，r 为 页面p 请求的时间。为便于用户计算每个页面的驻留时间，规定每个会话 的入口页面( e n t r yp a g e ) 对应请求时间 = 0 。设会话数据库中会话总数为 s s e t c o u n t 。页面集只的出现频率是d b v p 包含页面集只的会话数目，记为 燕山大学工学硕士学位论文 只c o u n t ，则页面集尸，的支持度可以表示为p r c o u n t s s e t c o u n t ，记为 s u p ( p ：) 。设f = 嵌，磊，五 为频繁访问的页面集，且z 只，1 歹k 。 包含七个页面的页面集称为缸页面集，包含个频繁页面的页面集称为如频繁 页面集。针对访问序列可以设置两个会话序列s l = 和 s ，= ，若s 是& 的子访问序列，则存在k n ，并且对于3 i ( 1 茎i ，一k + 1 ) ，使得6 f = 即龟+ l = a 2 ，包m l = a k 成立。当且仅当b ，= a ， ( 1 i s k ”) 成立时，会话序列s 。是是的一个前缀序列。当且仅当b ，= a n m ， ( 1 isk n ) 成立时，s 是的一个后缀。假设会话序列总数为s s e t c o u n t ， 访问序列s 。的出现频率为s ，c o u n t ，则s ，的支持度即为s ，c o u n t s s e t c o u n t ， 记为s u p ( s ，) 。含有七个页面项的序列长度为k ，称为缸序列。 定义2 4 ：频繁页面集只是指满足s u p ( 0 ) 2 m i