(计算机应用技术专业论文)web日志数据挖掘技术的研究.pdf_第1页
(计算机应用技术专业论文)web日志数据挖掘技术的研究.pdf_第2页
(计算机应用技术专业论文)web日志数据挖掘技术的研究.pdf_第3页
(计算机应用技术专业论文)web日志数据挖掘技术的研究.pdf_第4页
(计算机应用技术专业论文)web日志数据挖掘技术的研究.pdf_第5页
已阅读5页,还剩58页未读, 继续免费阅读

(计算机应用技术专业论文)web日志数据挖掘技术的研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

w e b 日志数据挖掘技术的研究 易轶虎( 计算机应用技术 指导教师:张文东高工 摘要 在w e b 数掘挖掘研究领域中,w e b 日志挖掘是最重要的应用研究 方向之一。w e b 日志挖掘的目的是找出网站用户的访问模式,其过程主 要包含三个步骤:数据预处理、模式识别和模式分析。在研究w e b 日志 及相关的数据挖掘技术的基础上,提出一种基于链接的数据清理方法, 利用网页链接信息清理原始访问日志,使清理后的记录更加准确完整地 反映用户访问路径。然后经过用户识别、会话识别、路径补偿等步骤将 日志记录整理成适于挖掘的用户访问序列;根据序列模式挖掘理论,提 出基于动态矩阵预测的网页实时推荐算法,首先通过会话编码反映用户 访问路径的先后顺序,并利用动态矩阵和滑动窗筛选简化相似度计算, 同时,整个过程中动态矩阵对日志的扫描减少为一遍,从而在保证满意 度的基础上实现了网页在线实时推荐;通过对聚类算法的分析,提出基 于兴趣相似性的w e b 用户聚类算法,利用日志记录和网页内容综合描述 用户浏览兴趣,以提高聚类的准确性,应用传递闭包法对用户进行聚类 分析,不同截集的划分体现了用户类属的模糊性,最终实现了依据浏览 兴趣对用户的模糊聚类。这些研究可以为改善网络访问速度,提高网站 访问量,合理调整站点结构,发掘潜在客户以及网络欺诈检测等应用提 供新的思路和借鉴。 关键字:日志挖掘,序列模式,聚类,用户访问模式 r e s e a r c ho ft e c h n o l o g yo nw e b l o gm i n i n g y i h u ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db y :s e n i o re n 舀n rz h a n g w e n _ d o n g a b s t r a c t w e bl o gm i n i n gi so n eo ft h em o s ti m p o r t a n tr e s e a r c hd i r e c t i o n si nt h e w e bm i n i n gr e s e a r c hf i e l d , t h ea i mo fw e bl o gm i n i n gi st of i n do u tu s e r b c c c s sp a t t e r n s t h ep r o c e s sm a i n l yi n c l u d e sf o u rs t e p s :d a t ac o l l e c t i o n , l o g p r e p r o c e s s ,p a t t e r nr e c o g n i t i o na n dp a t t e r na n a l y s i s w i t hu t i l i z a t i o no fl i n k i n f o r m a t i o no nw e bp a g e ,w ec a nc l e a nt h el a wl o gr e c o r d sa n dm a k et h e c l e a n e dr e c o r d sm o r ea c c u r a t e l yt or e p r e s e n tu 辩rv i s i tp a t h t h e n , w i t l l p r o c e s s e so fu s e rr e c o g n i t i o n , s e s s i o nr e c o g n i t i o na n dp a t hc o m p e n s a t i o n , t h ew e bl o gi sp r o c e s s e dt ou s e ra c c e s ss e q u e n c ea v a i l a b l et om i n e i nt e r m s o ft h e o r yo fs e q u e n c e p a t t e r nm i n i n g ,s e q u e n c eo fw e ba c c e s sp a t hi s r e p r e s 即db yd i g i t a lc e d e ,c a l c u l a t i o no f s i m i l a r i t yi ss i m p l i f i e dw i t hu s a g e o fd y n a m i cm a r xa n ds l i d ew i n d o w m e a n w h i l e ,n e wr e c o m m e n d a t i o n a l g o r i t h mo n l ys c a l lo n et i m e b o t ho f a s p e c t sc a nr e d u c et h et i m eo f r e a c t i o n l a r g e l yt o g e t h e r r e s u l to fe x p e r i m e n ts h o w si tc a ni m p r o v ep e r f o r m a n c eo f r e c o m m e n d a t i o na n dh a sc e r t a i np r a c t i c a lv a l u e i nt e r m so fc l u s t e r i n g a n a l y s i s ,t h ep a g ec o n t e n ta n db r o w s i n gp a t ha r et a k e ni n t oa c c o u n ti n m e a s u r e m e n to fb r o w s i n gi n t e r e s tt o e f f i c i e n t l yi m p r o v ep r e c i s i o no f c l u s t e r i n g t h e r e a r e r , b e wm e t h o di sb r o u g h tf o r t ht oc a l c u l a t es i m i l a r i t yo f i n t e r e s ta n dr s e r $ a l eb ec l u s t e r e db yu s a g eo ft r a n s i t i v ec l o s u r ea l g o r i t h m t h ef u z z yq u a l i t yo f c l u s t e r i n gi sr e f l e c t e db yt h ev a r i o u sd i v i s i o no f x , f i n a l l y , a c c o m p l i s ht h e 呦c l u s t e r i n go fw e b u 跚,t h e s er e s e a r c h sw i l lb eh e l p f u l t op r o v i d en e wi d e ai na p p l i c a t i o no r l q u i c k e n i n gw e ba c c e s s ,i n c r e a s i n gw e b u s e r 9r a t i o n a l l ya d u s t i n gw e bs i t es t r u c t u r e ,m i n i n gt h ep o t e n t i a l u s e ra n d i n s p e c t i n gw e bf :r a u d k e yw o r d s :l o gm i n i n g ,s e q u e n c ep a r l e r r kc l u s t e r , u s e r a c 虻e s sp a t t e r n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论 文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得石油 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 签名:工一6 年牛月3日 关于论文使用授权的说明 本人完全了解石油大学有关保留、使用学位论文的规定,即:学校 有权保留送交论文的复印件及电子版,允许论文被查阅和借阅;学校可 以公布论文的全部或部分内容,可以采用影印、缩印或其他复制手段保 存论文。 ( 保密论文在解密后应遵守此规定) 学生签名: 导师签名: 篮i 孟1 2 0 0 年斗月弓f i 纱口莎年午月,日 中国石油大学( 华东) 硕十论文 第1 章绪论 1 。1 研究背景及意义 第1 章绪论 因特网( i n t e r n e t ) 的快速发展为用户提供了巨大信息资源。用户面对 如此海量资源,如何在w e b 上更有效地找到所需的信息是一个极具挑战 的课题。就目前面言,人们获取信息的主要工具还是搜索引擎。但目前 搜索引擎存在以下不足:需要手工操作;搜索结果完全依赖所输入的关 键字;无法充分描述用户需求;缺乏用户定制功能等。而对于网站管理 者,随着网站规模的扩大和复杂性的提高,站点的设计与维护变得越来 越繁杂。利用常规的统计方法来分析w e b 站点的访问情况已经难以满足 w e b 站点管理的需要。同时随着近几年电子商务的发展壮大,要求各 w e b 站点能够有效地理解用户的访问行为,根据不同用户兴趣智能地调 整站点结构或内容,提供个性化服务。另外鉴于w e b 是一个分布式、非 结构化、无完整性约束、可扩充的信息系统。大部分网上信息是以h t m l 文档的形式存在的,除了超级链接外,没有任何结构,因此对文档内容 的抽取和分析是相当困难的,难以对其进行数据挖掘。相比而言,w e b 日志却有比较固定完整的格式。随着数据挖掘技术的不断发展,将其与 w e b 应用相结合不仅可以发现有趣的知识,而且有助于数据挖掘理论的 发展和创新,因此基于w e b 日志的挖掘不仅现实可行而且是前景广阔。 本文研究通过w e b 日志挖掘,获取用户访问w e b 的目标、兴趣和 偏爱等行为模式,以此来改进w e b 站点的结构和w e b 提供服务的方式, 实现站点的智能化管理和个性化信息服务,从而帮助用户更容易地获取 中国石油大学( 华东) 硕士论文 第1 章绪论 所需信息。 1 2 国内外研究现状 w e b e l 志挖掘是w e b 数据挖掘中一项比较重要的研究方向,即通过挖 掘服务器的日志文件,得到用户的访问模式( 也称为w e b 使用挖掘) 。目 前。日志挖掘方法主要分为两类:基于事务的方法和基于数据立方体的方 法。 ( 1 ) 基于事务的w e be t 志挖掘方法 w c b 日志数据顶处理模式识别 模式分析 数据净化 用户识别 会话识剐 页面过滤 瞎径补充 图1 - 1 基于事务的w e b 日志挖掘 基于事务的w e b 日志挖掘最早是由c h e nms 等人提出的,如图卜l 所示。 将数据挖掘技术应用于w e b 服务器日志文件,提出最大向前引用算法的 概念并将用户会话分割成一系列的事务,然后采用与关联规则相类似的 方法挖掘频繁访问路径,从而取得用户访问模式。 ( 2 ) 基于数据立方体的日志挖掘方法 w e b 日志 暂据库 数据立方o l a p 联机分析数据挖掘技术 图1 - 2 基于数据立方体的w e b 日志挖掘 2 中国石油大学( 华东) 颂十论文 第1 章绪论 h a r tjw 提出基于数据立方体的w c b 日志挖掘方法如图1 - 2 所示,根据服 务器日志文件,建立w e b 数据立方体( d a t ac u b e ) ,然后对数据立方体进 行数据挖掘和联机分析处理( o l a p ) 。同基于事务的w e b h 志挖掘方法相 似,基于数据立方体的日志挖掘同样要经过预处理、模式识别、模式分 析等步骤。基于事务和基于数据立方体的两种方法,各有其特点。基于 事务的w e b h 志挖掘方法,侧重于用户序列模式的挖掘和分析,以事务 和序列为出发点的知识发现,从而找出每一个用户的访问模式,这正是 与应用的特性相符合。而基于数据立方体的日志挖掘,侧重于将日志转 变为结构化的数据立方体,从多角度进行挖掘和分析。本文主要研究基 于事务的w e b 日志挖掘方法。 1 2 1 国内研究现状 近年来,随着数据挖掘技术的进步,国内许多研究人员对w e b 日志 挖掘进行了深入的探索。在日志数据预处理方面,针对f r a m e 页面影响 日志清理质量的问题文献 1 分别提出将f r a m e 与s u b f r a m e 页面的嵌套 关系f s 扩展为传递闭包,以此来过滤f r a m e 页面。文献 2 将这种关系 用树结构进行存储,命名为f s 树结构,利用f s 树对f r a m e 页面过滤。 为了构建完整的用户会话,文献 3 提出一种面向时间的启发式会话识别 方法。 在模式识别中,针对日志中关联规则的挖掘,文献 4 将互关联后继 树( i n t e r r e l a t e ds u f f i xt r e e ,i r s t ) 模型应用于w e b 日志事务挖掘,构造 w e b h 志事务集的互关联后继树结构,从中挖掘频繁路径。 针对序列模式的挖掘,徐宝文等人 5 提出一种基于数据挖掘的预取 中国石油大学( 华东) 硕士论文 第l 章绪论 模型。模型利用客户端浏览器缓冲区数据,挖掘其中蕴含的兴趣关联规 则,以此预测用户可能选择的链接。在此模型中,用户兴趣表现为对词 条的兴趣,兴趣关联规则表示从一个词条转向其他词条的可能性。利用 兴趣关联规则,结合用户当前访问的页面的轨迹和用户访问的当前页面, 预测用户可能访问的链接。此模型在预取决策时,仅考虑了词条间转移 的可能性,未考虑用户对超链指向页面的感兴趣程度。同时,在挖掘兴 趣关联规则时也没有考虑词条间兴趣转移具有的传递性。 x u c h e n g z h o n g 等人 6 引入神经网络实现基于语义的网页预取。 通过抽取网页超级链接文字描述中的关键词作为神经网络的输入,神经 网络输出结果作为预取依据。用户浏览路径途径的页面作为训练样本反 馈给神经网络进行学习。由于关键词的多义性会影响预取的准确性,模 型对预取网页的范围采取分类处理,不同类别构造不同的预取器。虽然 这在一定程度上提高了模型的预取准确性,但却限制了模型的实用性。 朱培栋等人 7 提出提炼用户会话特征,按语义对用户会话进行分 类。在回应用户访问请求时,服务器计算当前用户访问路径与各类别中 心的距离,确定会话所属的类别。根据会话所属类别的共同特征,预测 用户可能访问的文档,一次性地预送到客户端。这种方法在计算会话与 类别中心的向量距离时,过于严格遵循访问模式的时序关系。 许欢庆 8 提出一种基于用户访问路径分析的服务器端预取模型。区 别于原有的基于访问时序关系的预取方法,该模型通过分析用户的访问 路径,挖掘其中蕴含的用户信息需求,据此预测用户的下一步访问请求。 为了实现用户访问序列中潜在意图的挖掘,模型还引入了隐马尔可夫模 型( h i d d e nm a r k o vm o d e l ,简称h m m ) 。 文献 9 提出一种结合用户使用挖掘和内容挖掘的w e b 推荐服务,该 4 中国石油大学( 华东) 硕士论文 第l 审绪论 推荐服务根据频繁最大前向访问路径,提出含有导航页和内容页的频繁 访问路径图概念,根据滑动窗口内的最近用户访问页面内容和候选推荐 集中页面内容相关性,来向用户提供个性化推荐服务。 文献 1 0 提出一种基于概念联想网络的网页预取模型,挖掘用户访 问模式中蕴含的概念间联想模式,结合在线学习和离线挖掘两种方式, 建立面向用户的概念联想网络,并基于概念联想网络实现网页预取评价。 文献e 1 1 从w e b 用户访问模式挖掘过程预处理的结果用户会话文件开 始,提出了一种基于w e b 拓扑结构( 图结构) 挖掘用户访问模式的方法。 在聚类分析中,文献 1 2 提出一种基于“矩阵聚类”的电子商务网 站个性化推荐系统,通过分析w e bs e r v e r e l 志文件中的访问页面序列行为 数据,构建较高购买者的顾客行为的矩阵模型;并使用一种新型的矩阵聚 类算法挖掘潜在购买者与较高购买者的相似特征,从而帮助顾客发现他 所希望购买的产品信息。文献 1 3 提出了一种集成w e b 使用挖掘和内容 挖掘的用户浏览兴趣迁移模式的模型和算法。通过相应聚类类别替代用 户事务中的页面的方法得到用户浏览兴趣序列。从用户浏览兴趣序列中 褥到用户浏览兴趣迁移模式。 1 2 2 国外研究现状 在模式识别中,文献 1 4 1 6 分别设计t h e m s e t c o d e 算法、s m - t r e e 算法、p d t r e e 算法,第一个算法可以快速发现小频繁集,而后两种算法 则利用了自动化原理中的状态机概念。针对序列模式的挖掘,a z e r 1 7 提出基于概率模型的预取方法。利用服务器f t 志数据,计算出在一定时 间间隔内,网页间被连续访问的概率,并建立条件概率矩阵。服务器以 中国石油大学( 华东) 硕士论文 第1 章绪论 此预测用户的访问请求。s a r u k k a i 1 8 运用马尔可夫链进行访问路径分析 和链接预测。在此模型中,用户访问的网页集作为状态集。根据用户访 问记录,计算出网页间的转移概率,作为预测依据。这两种方法在预取 决策时仅考虑用户当前访问请求,而没有从整个访问序列加以考虑。 s c h e c h t e r 等人 1 9 构造用户访问路径树,采用最长匹配方法,寻找与当 前用户访问路径匹配的历史路径,以此预测用户接下来的访问请求。路 径树的构造与匹配需要的时间和空间复杂度较高。文献 2 0 2 2 中提出 的在w e b 站点中根据页面访问统计进行聚类的方法。文献中相似度大小 是采用计算两个访问向量的角度的c o s 值得到。访问向量的元素是用户是 否访问该页面,或访问w e b 页面的时间,或在用户访问事务中w e b 页面 出现的次数。采用的聚类方法是k - 均值方法。文献 2 3 中提出一种非距 离的顺序排列方法,利用w e b 日志对用户进行聚类,它重点考虑了用户 会话的先后关系。 在w c b 日志数据挖掘的研究工作中 2 4 ,比较有代表性的是: h u m b o l d t 大学的w u m 、s i m o nf r a s e r 大学的w e b l o g m i n e r 和m i n n e s o t a 大学的w e b m i n e r 。w u m 系统挖掘w e b 日志中的序列模式,并提供一个 集成了日志准备、模式查询以及可视化的环境;还提供了一种挖掘语言, 以描述发现的频繁路径的特征,但其模式查询语言m i n t 在表达序列模式 上的约束时不够灵活。w e b l o g m i n i n e r 在对用户存取日志文件进行数据 清理的基础上,建立了一个多维网络日志数据立方体,然后在其上进行 o l a p ,可以进行关联规则挖掘、网络流量分析、用户行为模式分析、执 行分类和时序序列分析( 如事务序列分析、转换分析和趋事分析) ,并可以 用于对站点信息的重组。w e b m i n e r 系统提出了一种通用的w e b 日志 挖掘体系结构,采用诸如路径分析、关联规则挖掘等用户模式挖掘技术, 6 中国石油大学( 毕东) 硕卜论文第1 章绪论 自动地从w e b 日志中发现关联规则和序列模式等。尽管对w e b 访问日 志分析存在着各种各样潜在的应用,这类应用的成功与否依赖于人们可 以从大量原始数据中怎样发现和发现多少可靠的信息。 1 3 本文的组织结构 全文根据内容共分六章。第一章是绪论,介绍了本课题的研究背景 和意义,详细介绍y w e b b 志挖掘的国内外研究现状。 第二章重点分析了数据挖掘中与w e b 日志挖掘密切相关的序列模式 和聚类模式发现算法。介绍了相应的概念,分析比较了各主要算法的原 理和优缺点。 第三章介绍了w e b e l 志挖掘的相关知识,包括w e b 挖掘的概念、w e b 日志记录产生过程及格式、e b 日志挖掘的概念、过程以及当前的主要 应用领域。 第四章分析了w e b 日志挖掘的数据预处理过程。提出基于链接的数据 清理方法,并详细设计了数据预处理的关键算法。 第五章研究了w 曲日志挖掘中的两个具体模式分析网页实时推 荐和w e b 用户聚类。所分析的模式分别以第二章和第三章中的研究内容 为基础,分别提出基于动态矩阵预测的网页实时推荐算法和基于兴趣相 似性的w e b 用户聚类算法,通过试验分析其性能。 第六章对完成的工作和创新点进行了回顾和总结。 7 中国石油大学( 华东) 硕士论文 第2 章数据挖掘相关技术研究 第2 章数据挖掘相关技术研究 数据挖掘( d a t am i n i n g ) 是从大量不完全的、有噪声的、模糊的和随 机的数据中,提取隐含在其中的、人们事先不知道的,但又是潜在有用 的信息和知识的过程。它的任务主要包括关联分析、聚类分析、分类、 预测、序列模式和偏差分析等。鉴于w e b 日志是由不同用户对w e b 服 务器按时间顺序的访问记录构成,本文重点研究序列模式挖掘和聚类分 析。 2 1 序列模式挖掘 现实生活中有许多按时问进行排序的事件序列,例如一位顾客对某 超市的购买活动序列;网络用户对w e b 站点的访问序列等等。网站为了吸 引更多的用户,不仅需要分析用户在访问过程中最喜欢看哪些内容,还 需要分析用户在浏览某些内容之后,接下来会访问哪些网页;分析用户 每次访问的网页间的联系,这就导致了序列模式挖掘的产生。由于很多 商业交易、电传记录、天气数据、生产过程和疾病状态都是序列数据, 在针对目标市场、客户吸引、气象预报、疾病诊断等的数据分析中,序 列模式挖掘是很有用途的。 2 1 1 序列模式挖掘的概念 序列模式的定义最早由a g r a w a l 和s r i k a n t 提出的,其定义为:给定一 8 中囝自油大学( 华东) 硕士论文 第2 章数据挖掘相关技术研究 个由不同序列组成的集合,其中每个序列由不同的元素按顺序排列,每 个元素由不同的项目组成,同时给定一个用户指定的最小支持度阈值, 序列模式挖掘就是找出所有的频繁子序列,即该子序列在序列集中的出 现频率不低于用户指定的最小支持度阈值。 序列模式挖掘与关联规则和时间序列数据挖掘有许多相似之处,通 过三者之间的比较可以说明序列模式挖掘的特点。序列模式挖掘的许多 概念和算法都是由关联规则挖掘的概念和算法延伸发展而来的。它们之 间有很多相似之处,然而在本质上它们是不同的,以顾客购买商品的数 据为例来说明它们之间的区别。关联规则数据挖掘所要解决的问题是发 现哪些商品顾客在一次交易中购买某些商品后还会购买哪些商品,是顾 客喜欢一起购买的,它是发现交易内部规律的过程,从而使得售货方能 够按照顾客的购买兴趣来安排货架上的商品,达到卖出更多商品的目的: 而序列模式挖掘所要解决的问题是顾客在完成一次交易后,在以后的满 足特定时间约束的交易中,他还会购买什么商品,是发现交易之间关系 规律的过程,使得售货方能够根据当前的商品买卖情况来预测以后的商 品销售情况从而能更好地安排进货,防止顾客买不到要购买的商品。对 于同一交易数据库来说,序列模式挖掘所要挖掘的模式空间要比关联规 则挖掘的模式空间大得多,所要解决的问题也复杂得多。 序列模式挖掘和时间序列模式挖掘在概念上也很容易混淆,但是如 果从挖掘的数据对象和挖掘的目的来看,时间序列模式挖掘最早足统计 学上的一个概念,后来被数据挖掘所采用,并增添了一些新的内容。时 间序列模式挖掘根据数据随时自j 变化的趋势,发现某一时间段内数据的 相关处理模型,预测将来可能出现值的分布。它可以被看成是一种特定 的关联模型,它在关联模型中增加了时间属性;时间序列模式挖掘的目 9 中国石油大学( 华东) 硕上论文第2 章数据挖掘相关技术研究 标主要有趋势预测、相似性搜索和周期分析等。而序列模式挖掘的目的 是研究事件发生的先后关系,找出其中的规律,即不仅需要知道事件是 否发生,而且需要确定该事件与其它事件发生的先后顺序。序列模式挖 掘也有时间约束,但它的目的是更好的约束事件之间的先后关系,而不 是规定事件在时间上的变化。 2 1 2 主要序列模式挖掘算法分析 序列模式挖掘的方法有很多,比较经典的算法有三种g s p ( g e n e r a l i z e d s e q u e n t i a lp a t e r n s ) 算法、p r e f i x s p a n ( p r e f i xp r o j e c t e ds e q u e n t i a l p a t e r nm i n i n g ) 算法和s p a d e ( s e q u e n t i a lp a t e r nd i s c o v e r yu s i n g e q u i v a l e n c ec a l s s e s ) 算法。 ( 1 ) g s p 算法 g s p 算法是序列模式概念的提出者r a g r a w a l 和r s r i k a n t 在a p r i o r i a l l 算法的基础上提出的,是基于通过候选项集找频繁项集的理论,需要多 次扫描数据库。g s p 算法描述如下: 1 扫描序列数据库,得到长度为1 的序列模式l l ,作为初始的种子集。 2 3 根据长度为i 的种子集l j ,通过连接操作和剪切操作生成长度为i + l 的候选序列模式c 1 ;然后扫描序列数据库,计算每个候选序列模式 的支持数,产生长度为i + l 的序列模式l i + l ,并将k t 作为新的种子 集。 3 重复第二步,直到没有新的序列模式或新的候选序列模式产生为止。 其中产生候选序列模式主要分两步: 1 连接阶段:如果去掉序列模式s 1 的第一个项目与去掉序列模式s 2 的 i o 中国石油大学( 华东) 硕士论文第2 章数据挖掘相关技术研究 最后一个项目所得到的序列相同,则可以将s l 于s 2 进行连接,即将 s 2 的最后一个项目添加到s l 中。 【2 剪切阶段:若某候选序列模式的某个子序列不是序列模式,则此候选 序列模式不可能是序列模式,将它从候选序列模式中删除。候选序列 模式的支持度计算方法是对于给定的候选序列模式集合c ,扫描序列 数据库,对于其中的每一条序列d ,找出集合c 中被d 所包含的所有 候选序列模式,并增加其支持度计数。 g s p 算法存在的主要问题:如果序列数据库的规模比较大,则有可能 会产生大量的候选序列模式;需要对序列数据库进行循环扫描:对于序 列模式的长度比较长的情况,由于其对应的短的序列模式规模太大,本 算法很难处理。 ( 2 ) p r e f i x s p a n 算法 p r e f i x s p a n 算法是建立在投影数据库的概念基础之上的,采用分治的 思想,不断产生序列数据库的多个更小的投影数据库,然后在各个投影 数掘库上进行序列模式挖掘。其中相关定义如下 1 前缀:设每个元素中的所有项目按照字典序排列。给定序列o t = ,b = ( i i l 5 n ) ,如果c i = e i ( i s m - 1 ) ,e m c l i l ,并且( e m - e m ) 中的项目均在e m 中项目的后面,则称1 3 是a 的 前缀 2 投影:给定序列q 和1 3 ,如果d 是a 的子序列,则0 【关于p 的投影 0 【必须满足:b 是i f , 的前缀,o f , 是0 【的满足上述条件的最大子序 列 3 后缀:序列o 【关于子序列1 3 = 的投影为o t = ( er e 2 e 。 ( n = m ) ,则序列关于子序列1 3 的后缀为 ,其中e m 竹 中国石油大学( 华东) 硕七论文第2 章数据挖掘相关技术研究 一( e i l i - e m ) 4 投影数据库:设a 为序列数据库s 中的一个序列模式,则0 的投影数据 库为s 中所有以a 为前缀的序列相对于o 【的后缀,记为s i a 5 投影数据库中的支持数:设0 【为序列数据库s 中的一个序列模式,序列 p 以为前缀,则p 在a 的投影数据库s l0 【中的支持数为s i o l 中满足条件 p n 的序列y 的个数。 相应的算法描述如下: 1 扫描序列数据库,生成所有长度为l 的序列模式。 2 根据长度为1 的序列模式,生成相应的投影数据库。 3 3 在相应的投影数据库上重复上述步骤,直到在相应的投影数据库上 不能产生长度为l 的序列模式为止。 p r e f i x s p a n 算法不需要产生候选序列模式,从而大大缩减了检索空 间;相对于原始的序列数据库而言,投影数据库的规模不断减小;算法 的主要开销在于投影数据库的构造。算法改进主要通过逐层投影和伪投 影,即使用隔层投影代替逐层投影,从而减小投影数据库的个数和当序 列数据库可以直接放入内存时,可以使用伪投影操作代替实际的投影数 据库,从而减少构造投影数据库的开销。 ( 3 ) s p a d e 算法 s p a d e 算法将序列数据库由水平格式变成垂直格式,并在新的格式上 进行序列模式挖掘。它利用等价类别( e q u i v a l e n c ec l a s s ) 的观点,将原始 的问题分解成若干个较小的予问题,以便能更有效地使用网格式搜索策 略和简单的链接操作,独立地在主存储器中运行。所有的序列模式只需 在三次扫描序列数据库后即可得到。算法主要有以下几个特点:使用了 1 2 中国石油大学( 华东) 颂l 论文第2 章数据挖掘相关技术研究 垂直i d 列表( v e r t i e a l i d 1 i s t ) 的数据库格式,即记录每一个访问序列在什么 时间发生,而不是在某个时间发生了哪些访问序列。应用了网格理论, 将原始的搜索空问分解成若干个较小的子网格,每一个子网格都可以在 主存储器中独立的运行。整个过程只需三次数据库扫描,将t o 耗费 减到最小。在每一个子网格上搜索频繁序列时,有两种不同的搜索策略: 宽度优先搜索和深度优先搜索。 2 2 聚类分析 聚类( c l u s t e r i n g ) 就是将数据对象分组成为多个类或簇,但是与分类 不同,它要划分的类是未知的。在同一个簇中的对象之间具有较高的相 似度,而不同簇中的对象差别较大。相似度是根据描述对象的属性值来 计算的,距离是经常采用的度量方式。聚类分析源于许多研究领域,包 括数据挖掘,统计学,生物学,以及机器学习。 2 2 1 聚类的概念 将物理或抽象对象的集合分组成为由类似的对象组成的多个类或簇 的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对 象与同一簇中的对象彼此相似,与其他簇中的对象相异。在许多应用中, 可以将一个簇中的数据对象作为一个整体来对待。 在商务上,聚类能帮助市场分析人员从客户基本库中发现不同的客 户群,并且用购买模式来刻画不同客户群的特征。在生物学上,聚类能 用于推导植物和动物的分类,对基因进行分类,获得对种群中固有结构 的认识。聚类在地球观测数据库中相似地区的确定中都可以发挥作用。 中国石油大学( 华东) 硕士论文第2 章数据挖掘相关技术研究 聚类也能用于对w e b k 的文档进行分类,以发现信息。因为具有数据挖掘 功能,聚类分析能作为一个独立的工具来获得数据分布的情况,观察每 个簇的特点,集中对某些特定的簇做进一步的分析。此外,聚类分析还 可以作为其他算法( 如特征化和分裂等) 的预处理步骤,这些算法再在生 成的簇上进行处理。 2 2 2 聚类算法的衡量标准 聚类是一个富有挑战性的研究领域,它的潜在应用对聚类算法提出 了特定要求。数据挖掘对聚类的典型要求如下: ( i ) 可伸缩性:许多聚类算法在小于2 0 0 个的数据对象的小数据集合上工 作的很好;但是,一个大规模的数据库可能包含几百万个对象,在 这样的大数据集合样本上进行聚类可能会导致有偏差的结果,因此 数据挖掘需要具有高度可伸缩性的聚类方法。 ( 2 ) 处理不同类型属性的能力:许多算法被设计用来聚类数值类型的数 据。但是应用可能要求聚类其他类型的数据,如二元类型( b i n a r y ) , 分类标称类型( c a t e g o r i c a l n o m i n a l ) ,序数型( o r d i n a l ) 数据,或者 这些数据类型的混合。 ( 3 ) 发现任意形状的的聚类:许多聚类算法基于欧几里得距离或者曼哈 坦距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具 有相近尺度和密度的球状簇。但是,现实中一个簇可能是任意形状 的。 ( 4 ) 用于决定输入参数的领域知识最小化:许多聚类算法在聚类分析中 要求用户输入一定的参数,例如希望产生的簇的数目。聚类结果对 中围石油大学( 华东) 硕十论文第2 章数据挖掘相j 技术研究 于输入参数十分敏感。参数通常很难确定,特别是对于包含高维对 象的数据集来说,更是如此。 ( 5 ) 处理噪声数据的能力:绝大多数现实世界中的数据库都包含了孤立 点,空缺,未知数据或者错误的数据。一些聚类算法对于这样的数 据敏感,可能导致低质量的聚类结果。 ( 6 ) 高维性( h i g hd i m e n s i o n a l i t y ) :一个数据库或者数据仓库可能包含若 干维或者属性。 ( 7 ) 基于约束的聚类:现实世界的应用可能需要在各种约束条件下进行 聚类。要找到既满足特定的约束,又具有良好聚类特性的数据分组 是一项具有挑战性的任务。 ( 8 ) 可解释性和可用性:用户希望聚类结果是可解释的,可理解和可用 的。即聚类可能需要和特定的语义解释和应用相联系。 2 2 3 主要聚类方法的分析 目前存在大量的聚类算法。算法的选择取决于数据的类型、聚类的 目的和应用。如果聚类分析被用作描述或探查的工具,可以对同样的数 据尝试多种算法,以发现数据可能揭示的结果。大体上,主要的聚类算 法可以划分为如下几类: ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 给定一个包含n 个对象或元组的数据库,一个划分方法构建数据的k 个划分,每个划分表示一个聚簇,并且k n 。即它将数据划分为k 个组, 同时满足如下的要求:第一,每个组至少包含一个对象:第二,每个对象 必须属于且只属于一个组。为了达到全局最优,基于划分的聚类要求穷 1 5 中国石油大学e 华东) 硕士论文第2 章数措挖掘相关技术研究 举所有可能的划分。实际上,绝大多数应用均采用了以下两个比较流行 的启发式方法: 1 k 一平均算法,在该算法中,每个簇用该簇中对象的平均值来表示。 以k 为参数,把n 个对象分为k 个簇,以使簇内具有较高的相似度,而 簇闻的相似度较低。相似度的计算根据一个簇中对象的平均值( 被看 作簇的重心) 来进行。 2 k - 中心点算法,在该算法中,每个簇用接近聚类中心的一个对象来 表示。其基本策略是:首先为每个簇随意选择一个代表对象:剩余的 对象根据其与代表对象的距离分配给最近的一个簇。然后反复地用 非代表对象来代替代表对象,以改进聚类的质量。这些启发式聚类 方法对在中小规模的数据库中发现球状簇很适用。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) 层次方法对给定数据对象集合进行层次分解,可分为凝聚的和分裂 的两种。凝聚的方法,也称为自底向上的方法,一开始将每个对象作为 单独的一个组,然后相继地合并相近的对象或组,直到所有的组合并为 一个( 层次的最上层) ,或者达到一个终止条件。分裂的方法,也称为自 顶向下的方法,一开始将所有的对象置于一个簇中,在迭代的每一步中, 一个簇被分裂为更小的簇,直到最终每个对象在单独的一个簇中,或者 达到一个终止条件。 层次的方法虽然比较简单,但是在选择凝聚或者分裂点的时候经常 会遇到一些困难,这是非常关键的,因为一旦记录被凝聚或者分裂以后, 下一步的工作是建立在新形成的类的基础之上的。因此,如果其中任何 一步没有做好的话,就会影响最终聚类的结果。这个方法并不是太好, 因为要牵涉到很大数量的类和记录。 1 6 中国石油大学( 华东) 硕卜论文 第2 章数据挖掘相关技术研究 ( 3 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能 发现球状的簇,而在发现任意形状的簇上遇到了困难。随之提出了基于 密度的另一类聚类方法,其主要思想是:只要l 临近区域的密度( 对象或数 据点的数目) 超过某个闽值,就继续聚类。即对给定类中的每个数据点, 在一个给定范围的区域中必须至少包含一定数目的点。此方法可以用来 过滤“噪声”孤立点数据,发现任意形状的簇。 d b s c a n 是一个有代表性的基于密度的方法,它根据一个密度阈值 来控制簇的增长。o p t i c s 是另一个基于密度的方法,它为自动的和交互 的聚类分析计算一个聚类顺序。 ( 4 ) 基于网格的方法( g r i d - b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元,形成了一个网 格结构。所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这 种方法的主要优点是它的处理速度很快,其处理时闻独立于数据对象的 数目,只与量化空间中每一维的单元数目有关。 ( 5 ) 基于模式的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法为每个簇假定了一个模型,寻找数据对给定模型的 最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密 度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目,考 虑“噪声”数据或孤立点,从而产生健壮的聚类方法。 另些聚类算法集成了多种聚类方法的思想,所以有时将某个给定 的算法划分为属于某类聚类方法是很困难的。此外,某些应用可能有特 定的聚类标准,要求综合多种聚类技术。 1 7 中国石油大学( 华东) 硕士论文 第3 章w e b 日志挖掘 第3 章w e b 日志挖掘 3 1w e b 挖掘简介 w e b 挖掘是数据挖掘技术与i n t e m e 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 文档的文本挖掘。文本挖掘主要包括了对w e b 文档的 过滤、摘要、分类、聚类、关联分析等。除了文本挖掘以外,w e b 内容 挖掘还有针对其他类型媒体( 如音频、视频、图片等) 内容的挖掘。w e b 结构挖掘主要指的是通过对w e b 文档的内部结构和文档之间的组织结构 获取有用的模式。w e b 页面包含的不仅仅是页面的文本内容,同时还有 一页到另一页的超级链接,超级链接结构包含了大量的注释,通过挖掘 这些结构信息可以更加精确地理解w e b 勾容的相关性及质量。另外, w e b 结构还包含一个网页内部的可以用h t m l 、x m l 表示成的树形结构, 以及文档u r l 中的目录路径结构等。通过挖掘w e b 的结构信息,可以揭 示许多蕴涵在w e b 内容之外的隐含的有用信息。w e b 日志挖掘主要是通 过对用户在访问w w w 服务器时留下的日志记录进行挖掘,这些记录包 含了所访问的页面、时间、用户i d 、连接参数等大量数据,通过对其挖 掘发现其中的关联规则、序列模式、聚类模式,从而获得有关用户的访 问模式。这些模式可以为网络拥塞处理、自适应站点的建设、个性化推 s 中国石油大学( 毕东) 硕 论文第3 章w e b 日志挖掘 荐系统构建等现实应用提供帮助。 3 2w e b 日志记录 3 2 1 w e b 日志记录产生过程 当用户通过浏览器向服务器请求页面时,w e b 服务器将该页面对应 的h t m l 或者a s p 、p h p 等页面文件传送给用户,并将这次请求记录在 服务器日志中。当浏览器解释文件内容时,如果还需要向服务器请求新 的资源,如包含在该页面中的图片文件、脚本文件或其它超链接文件等, 浏览器就根据页面文件中提供的u r l 地址发出新的请求,服务器接到请 求后重复上述响应和日志记录的过程。正因为如此,w e b 服务器日志文 件所记录的日志,并没有真正反映出用户的浏览意图。换句话说,用户对 w e b 服务器的一次页面请求( 即一次点击) ,如果所请求的页面包含多个 文件( w e b 页面一般都包含多个文件) ,就会在服务器的日志文件中产生 多条记录。之所以如此,是由于h r r p 协议本身造成的,因为h t t p 协 议中对w e b 服务器的文件请求是每个文件一个单独的u r l 链接。也正 是由于这个原因,使得w e b 日志文件异常庞大。据! 苎回丝统计某些 大型门户网站的日访问量可以高达1 亿次,产生的日志记录每天多达几 百m b 。 3 2 2 w e b 日志记录格式 在i n t e m e t 上有各种各样的服务器,其中部有一个专门提供w e b 服 务的软件,称为w e bs e r v e r ,常见的有m i c r o s o f t 的i i s 、u n

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论