（计算机应用技术专业论文）基于站点访问矩阵的web日志聚类方法分析与改进.pdf

多 ! 吵 r v，c口all；，、 ， 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作孝签名：善码霄 如ff 年6 月oe t 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相二致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密 学位论文作者签名：善自雷 2 口1 1 年6 月7 口日 指剥嗽二以以 9 。l 年参月( p 日 江苏大学硕士学位论文 捅要 通过对w e b 日志进行挖掘，站点管理者可以发现用户的浏览模式，了解不 同用户的兴趣和整个站点页面的访问情况，从而可以通过调整网站的逻辑组织结 构来优化其拓扑结构。目前，一些用于从w e b 日志中挖掘用户访问模式的算法 还存在很多缺陷，如：未考虑对页面的访问顺序；仅将访问频度作为聚类的依据； 相似度度量时，只考虑”0 ”、”l ”特征值问的差异，却忽略实际访问次数等重要因 素。针对以上问题，本文提出两种改进的w e b 日志聚类算法，有效提高挖掘准 确度。本文的主要工作分为以下几个方面。 首先，本文描述最长相同顺序路径系数s o r 、访问频率兴趣度一f p 、以及访 问时间兴趣度t p 等概念，从而设计综合访问兴趣度c p 计算模型，以此为基础， 提出基于站点访问矩阵的频繁访问路径挖掘算法f v p m a 。算法的主要思想是： 计算每两个页面之问的综合访问兴趣度，将其与综合访问兴趣度阈值进行比较， 以此类推，得到频繁访问子路径2 项集。然后，对子路径集中的元素进行合并， 最终得到频繁访问路径集。实验表明，f v p m a 算法能较好地提高挖掘准确度。 另外，将f v p m a 算法作为m f l m a 算法的理论依据与技术支持。 其次，本文描述u s e r s 最长公共访问路径系数u p p 、余弦相似度等概念，从 而设计一种新颖的相似度度量模型，用于求取用户间、以及页面问的综合相似度。 对其进一步研究，。提出基于站点访问矩阵的多能w e b 日志挖掘算法m f l m a 。 该算法摒弃以单一因素作为挖掘条件的缺陷，综合考虑多种与w e b 页面访问相 关的因素。算法的主要思想是：计算每两个用户之间的综合相似度，以此类推， 得到综合相似度矩阵，以该矩阵为基础，计算综合相似度阈值，从而获取2 项子 用户集，然后，对子用户集中的元素进行合并，最终得到相似访问用户集；获取 频繁访问路径集的过程与获取用户集的过程类似。m f l m a 算法能较好地获取两 个挖掘结果集，分别为相似访问用户集与频繁访问路径集。 最后，对实际挖掘过程进行探讨。以多能w e b 日志挖掘算法m f l m a 为核 心算法，设计多能w e b 日志挖掘模型，从而实现多能w e b 同志挖掘系统m f l m s 。 实验表明，以上多能w e b 同志挖掘模型可以有效提高挖掘的准确度。 关键词：w e b 同志挖掘；f v p m a 算法；余弦相似度；m f l m a 算法；m f l m s 系统 江苏大学硕士学位论文 a b s t r a c t b ym i n i n gw e bl o g s ，s i t e sm a n a g e r sc a nf m du s e r s b r o w s i n gm o d e ，a n dk n o w i n t e r e s t so fd i f f e r e n tu s e r sa n dv i s i t i n gc o n d i t i o no fp a g e s ，t h e r e b y , t h e yc a no p t i m i z e s i t e s t o p o l o g ys t r u c t u r ev i aa d j u s t i n gs i t e s t o p o l o g ys t r u c t u r e a tp r e s e n t ，m a n y d e f e c t se x i s ti nt h ea l g o r i t h m su s e dt om i n eu s e r s a c c e s sp a t t e r nf r o mw e bl o g s ，f o r e x a m p l e ，t h eo r d e ro fv i s i t i n gp a g e si sn o tc o n s i d e r e d ；t h ef r e q u e n c yo fv i s i t i n gp a g e s i st r e a t e da st h ef o u n d a t i o no fc l u s t e r i n gs i m p l y ；w h e nm e a s u r i n gs i m i l a r i t y , t h e d i f f e r e n c eb e t w e e n “0 a n d 1 ”i so n l yc o n s i d e r e d ，b u tt h ea c t u a lv i s i t i n gt i m e sa r e i g n o r e d a sf o rt h ea b o v ep r o b l e m s ，t w om o d i f i e dw e bl o g sc l u s t e r i n ga l g o r i t h m sa r e p r o p o s e di nt h ep a p e r ，s ot h ea c c u r a c yo fm i n i n gi si m p r o v e de f f i c i e n t l y t h em a i n w o r ki sd i v i d e di n t ot h ef o l l o w i n ga r e a si nt h ep a p e r f i r s to fa l l ，t h i sa r t i c l ei sb a s e do na c c e s sm a t r i x ，a n dd e s c r i b e ss o r ，f p ，t pa n d s oo n ，a n dd e s i g n st h ei n t e g r a t e da c c e s si n t e r e s t i n g n e s sm o d e l ，b a s e do nt h i s ，p r o p o s e s t h ea l g o r i t h mo fm i n i n gf r e q u e n ta c c e s sp a t hb a s e do ns i t ev i s i t i n gm a t r i x t h em a i n i d e ao ft h ea l g o r i t h mi s ：t h ei n t e g r a t e da c c e s si n t e r e s t i n g n e s s e sa r ec a l c u l a t e db e t w e e n e v e r yt w op a g e s ，a n dc o m p a r e dw i t ht h ei n t e g r a t e da c c e s si n t e r e s t i n g n e s st h r e s h o l d ， s o ，t h ef r e q u e n ta c c e s s2 - i t e ms u b - p a t hs e ti so b t a i n e d ，t h e n ，t h ee l e m e n t si nt h es e ta r e m e r g e d ，s of r e q u e n ta c c e s sp a t hs e ti sf i n a l l yg o r e n t h ee x p e r i m e n t ss h o wt h a t f v p m aa l g o r i t h mi m p r o v e st h ea c c u r a c yo fm i n i n gw e bl o g sb e a e r i na d d i t i o n ， f v p m aa l g o r i t h mi st r e a t e da st h et h e r e t i c a lb a s i sa n dt e c h n i c a lo fm f l m a a l g o r i t h m t h e n ，t h i sp a p e rd e s c r i b e su p p , c o s i n es i m i l a r i t ya n ds oo n , s oak i n do f s i m i l a r i t ym e a s u r em o d eu s e dt oo b t a i nt h ei n t e g r a t e ds i m i l a r i t yb e t w e e nu s e r so r p a g e si sd e s i g n e d t h r o u g hf u r t h e rr e s e a r c h ，w ep r o p o s em u l t i - f u n c t i o n sw e bl o g s m i n i n ga l g o r i t h mb a s e do ns i t ea c c e s sm a t r i x m f l m a t h ea l g o r i t h ma b a n d o n st h e d e f e c tt h a tt h es i n g l ef a c t o ri st r e a t e da st h ec o n d i t i o no fm i n i n gw e bl o g s ，a n d c o n s i d e r sm a n i f o l df a c t o r sw h i c ha r er e l e v a n tw i t hv i s i t i n gw e bp a g e s t h em a i ni d e a i s ：t h ei n t e g r a t e ds i m i l a r i t yb e t w e e ne v e r yt w ou s e r sa r ec a l c u l a t e d ，s o ，t h ei n t e g r a t e d s i m i l a r i t ym a t r i xi sg o t t e n b a s e do nt h em a t r i x ，t h ei n t e g r a t e ds i m i l a r i t yt h r e s h o l di s i i i 江苏大学硕士学位论文 c a l c u l a t e d ，s ot h e2 - i t e ms u b u s e rs e ti so b t a i n e d ，t h e n ，t h ee l e m e n t sa r em e 唱e di nt h e s e t ，s ot h eu s e rs e ti sf i n a l l yg o t t e n ；t h ep r o c e s so fo b t a i n i n gf r e q u e n ta c c e s sp a t hs e ti s s i m i l a rw i t ht h ep r o c e s so fg e t t i n gu s e rs e t t w or e s u l ts e t sa r eb e t t e ro b t a i n e db y m f l m a a l g o r i t h m ，a n dt h e ya r eu s e rs e ta n df r e q u e n ta c c e s sp a t hs e tr e s p e c t i v e l y f i n a l l y , w ed i s c u s st h e a c t u a lm i n i n gp r o c e s s w et r e a tm f l m a a st h ec o r e a l g o r i t h m ，a n dd e s i g nm u l t i f u n c t i o n sl o g sm i n i n gm o d e l ，s om u l t i - f u n c t i o n sl o g s m i n i n gs y s t e m m f l m si sr e a l i z e d t h ee x p e r i m e n t ss h o wt h a tt h em o d e li m p r o v e s t h ea c c u r a c yo fm i n i n gw e b l o g se f f e c t i v e l y k e yw o r d s ：w e bl o gm i n i n g ；f v p m aa l g o r i t h m ；c o s i n es i m i l a r i t y ；m f l m a a l g o r i t h m ；m f l m ss y s t e m i v 江苏大学硕士学位论文 目录 第一章绪论1 1 1 课题的研究背景及意义l 1 2 国内外研究现状1 1 3 本文的主要研究内容2 1 4 论文的组织结构3 第二章w e b 日志挖掘相关基础理论5 2 1 数据挖掘概述5 2 2w e b 日志挖掘简述6 2 2 1w e b 日志挖掘的定义7 2 2 3w e b 日志挖掘的难点分析8 2 2 3w e b 日志挖掘的应用8 2 3w 曲日忐挖掘的过程9 2 3 1 数据预处理阶段9 2 3 2 模式识别阶段1o 2 3 3 模式分析阶段。l3 2 4 本章小结1 4 第三章基于站点访问矩阵的频繁访问路径挖掘算法1 5 3 1 频繁访问路径挖掘算法f v p m a 相关概念。1 5 3 2 频繁访问路径挖掘算法f v p m a 2 3 3 2 1 算法的意义2 3 3 2 2 算法的主要思想2 4 3 2 3 频繁访问路径挖掘算法流程2 4 3 2 4 举例说明2 7 3 3f v p m a 算法实验结果分析和评价2 8 3 3 1 开发环境和实验数据2 8 3 3 2 实验结果2 9 3 3 3 算法性能评价2 9 3 4 本章小结3l v 江苏大学硕士学位论文 第四章基于站点访问矩阵的多能w e b 日志挖掘算法3 2 4 1 多能w e b 日志挖掘算法m f l m a 相关概念3 2 4 2 基于余弦相似度的相似度度量方法3 7 4 2 1 方法介绍3 7 4 2 2 实例演示3 8 4 3 多能w e b 日志挖掘算法m f l m a 4 0 4 3 1 算法的意义4 0 4 3 2 算法的主要思想4 l 4 3 3 多能w e b 日志挖掘算法流程4 2 4 4m f l m a 算法实验。4 3 4 5 本章小结4 4 第五章 m f l m a 算法应用系统4 5 5 1m f l m s 系统功能结构4 5 5 2 多能w e b 日志挖掘4 6 5 2 1m f l m s 系统流程4 6 5 2 2m f l m s 系统核心挖掘算法4 7 5 3m f l m s 系统的实现5 0 5 3 1 开发环境及实验数据。5l 5 3 2w e b 日志预处理模块5 1 5 3 3w e b 日志挖掘实现及结果5l 5 4m f l m s 系统性能评价5 4 5 5 本章小结5 5 第六章总结与展望5 6 6 1 本文- t 作总结。5 6 6 2 进一步工作展望5 7 参考文献5 8 致谢6 l 攻读硕士期间发表的论文及参加的科研项目6 2 江苏大学硕士学位论文 第一章绪论 1 1 课题的研究背景及意义 随着网络技术的发展，w e b 站点的结构越来越复杂。因此，通过挖掘w e b 日志得到用户感兴趣的路径和网站隐藏的信息【lj ，来优化站点的拓扑结构，成为 了一项吸引众多学者的研究课题。较高质量的挖掘技术对于w e b 站点结构优化 是十分重要的。现如今，以w e b 使用挖掘1 2 1 技术迅猛发展的特点为依托，可以获 得页面的访问频率，页面的访问顺序，页面的访问时间，以及页面访问文件大小 等信息。然后，分析w e b 同志中存在的规律【3 j ，从而能够理解用户的访问行为， 得到相似访问特点的用户集，以及频繁访问路径集。 通过基于站点访问矩阵的w e b 日志挖掘方法，如：基于兴趣度计算的w e b 同志挖掘，以及基于相似度度量的w e b 日志挖掘，便能够得到用户的访问兴趣， 从而为站点设计者优化站点结构以及站点运营商设置商业广告赚取最大利润，提 供较好的参考。目前，用于w e b 日志挖掘的技术主要有：聚类分析【4 ，5 】、统计分 析、关联规则同等。其中，基于站点访问矩阵1 7 1 ，通过向量间相似性度量阴的聚 类挖掘技术较为流行。所谓相似性度量是指利用一种较好的相似度计算模型，度 量用户之间访问页面的相似兴趣，以及页面之间的链接情况。 基于站点访问矩阵的w e b 日志聚类方法的作用主要表现在：( a ) 为优化站点 拓扑结构，提供较好的参考信息。( b ) 为相似访问兴趣的用户，定制不同的产品 和服务。( c ) 在频繁访问路径【8 】的网页上放置价格较高的商业广告，为运营商获取 最大利润，提供支持。 从以上可以看出，基于站点访问矩阵的w e b 日志聚类方法正在成为一个较 为吸引人的研究领域，其在理论研究和商业应用上都体现了自身的价值。 1 2 国内外研究现状 目前，国内外对w e b 日志挖掘的研究主要还是采用将w e b 数据经过转换保 存于数据库或数据仓库中，然后，再采用数据挖掘技术进行处理。该课题逐渐成 江苏大学硕士学位论文 为众多学者关注的焦点，其主要集中于对用户浏览路径的挖掘【9 , 1 0 , 1 1 , 1 2 】。 1 国外研究现状 n e c ，i b m 等公司对w e b 日志挖掘进行了大量的研究，并取得了一定的成 果。k o b r ae t m i n a n i 1 3 】等人提出了利用s o m ，发现用户的导航模式的方法；s i m o n f r a s e r 大学开发了w e b l o g m i n e r 系统，其将w e b 日志数据组织成数据立方体，然 后进行数据挖掘和联机分析处理，用于发现用户的访问模式，并提出了 c r a p h m i n e r e l 4 】；s h a n t a n us h a n n a 【1 5 】等人提出了一种使用a r t 的有效w r e b 同志挖 掘方法；z u c k e r m a n 等学者介绍了基于m a r k o v 模型的用户访问预测【1 6 】，该模型 是一个多维的概率分析模型；t a s a w a rh u s s a i n l l 7 j 等提出了一种用于w r e b 使用挖 掘的分级聚类预处理方法；o s m a r r z a i a n e 等对w e b 多媒体数据挖掘进行了研 究，提出了一种多媒体数据挖掘的系统原型【1 8 1 ；m s h e p p e r d 等【1 9 1 把网站的拓扑 结构看成一个有向图，提出了一种基于向量分析和模糊理论的用户聚类和页面聚 类算法。 2 国内研究现状 相比国外对w e br 志挖掘的研究，在这方面，国内起步较晚，但也取得了 一定的成果。西安交通大学沈钧毅教授2 0 1 等学者提出了w e b 页面和客户群体的 模糊聚类算法；中国科学技术大学的王熙法教授f 2 l 】等学者提出了基于神经网络 的w e b 用户行为聚类分析方法；张文东，易轶虎等1 2 2 1 学者提出了基于兴趣相似 性的w e b 用户聚类；业宁，李威等吲学者提出了一种w e b 用户行为聚类算法： 肖国强，肖铁等冽学者提出了一种从w e b 日志中挖掘访问模式的新算法；赵银 春，付关友等学者提出了基于w e b 浏览内容和行为相结合的用户兴趣挖掘； 西安交通大学的宋擒豹等【7 1 学者，提出了一种w e b 日志的高效多能挖掘算法。 1 3 本文的主要研究内容 本文的研究内容主要依据w e b 站点访问矩阵，访问兴趣度计算模型，以及 相似度度量模型。首先，本文探讨了w e b 日志挖掘所用技术，并分析了其不足。 接着，本文详细分析研究了频繁访问路径挖掘算法，在现有经典聚类算法的基础 上，提出了一种基于站点访问矩阵的频繁访问路径挖掘算法一f v p m a 。另外，本 文还详细研究了矩阵向量间相似性度量的方法，从而提出基于站点访问矩阵的多 2 江苏大学硕士学位论文 能w e b 日志挖掘算法m f l m a 。最后，以m f l m a 算法为核心算法，设计并实 现多能w e b1 3 志挖掘系统一m f l m s 。 本文的主要研究工作： 本文在分析现有频繁访问路径挖掘算法不足的基础上，设计较为新颖的访问 兴趣度计算模型，从而提出频繁访问路径挖掘算法一f v p m a 。通过实验，验证 该算法的可行性与有效性，为b i f l m a 算法的设计，提供理论依据与技术支持。 本文设计了一种较为新颖的相似度度量模型，从而，以此为基础，提出多能 w e b 日志挖掘算法一m f l m a 。 本文以m f l m a 算法为核心算法，设计并实现多能w e b 日志挖掘系统- m f l m s 。 通过实验，验证该系统在挖掘相似访问兴趣用户集，以及频繁访问路径集中 的有效性。 1 4 论文的组织结构 本文研究的主要内容是以w e b 站点访问矩阵为基础，通过综合兴趣度模型， 挖掘频繁访问路径集，以及通过相似度度量模型，挖掘相似访问兴趣用户集和频 繁访问路径集。主要分为以下几章的内容。 第一章为绪论部分。主要介绍课题背景和研究意义，国内外研究现状，以及 论文的主要研究内容。 第二章为数据挖掘和w e b 数据挖掘。主要介绍一些重要的相关概念，w e b 数 据挖掘的分类，w e b 数据挖掘用到的技术，以及w e b1 3 志挖掘的应用。其中 较深入地介绍了w e b 日志数据预处理部分，因为数据预处理的好坏，直接影 响了数据挖掘的有效性。 第三章为基于w e b 站点访问矩阵的w e b 日志挖掘算法。首先，介绍最长相同 顺序路径系数，访问频率兴趣度，以及访问时间兴趣度等概念，从而设计了 综合访问兴趣度模型，提出了频繁访问路径挖掘算法- f v p m a ，进行有效的实 验，并对结果进行了分析。 第四章为基于站点访问矩阵向量间相似性度量的多能w e b 日志挖掘算法 一m f l m a 。首先，介绍与页面访问相关的访问矩阵，u s e r s 最长公共访问路径 系数，相似度度量距离，相似度度量方法等概念，从而设计了新颖的相似度 3 江苏大学硕士学位论文 度量模型，提出了多能w e b 日志挖掘算法一m f l m a 。 第五章为基于站点访问矩阵向量间相似性度量的多能w e b 日志挖掘系统 一m f l m s 。本章以多能w e b 日志挖掘算法一m f l m a 算法为核心算法，设计并实现 了m f l m s 系统，实验证明了该系统的有效性。 第六章为总结与展望。本章在回顾论文做的主要工作后，对进一步需要做的 研究进行展望。 4 江苏大学硕士学位论文 第二章w e b 日志挖掘相关基础理论 本章主要介绍数据挖掘和w e b 日志挖掘的相关概念，数据挖掘的过程，以及 w e b 日志数据的过程，并对w e b 日志挖掘过程中用到的相关技术进行探讨。 2 1 数据挖掘概述 数据挖掘是指从大量数据中提取或“挖掘”知识，也就是从存放在数据库、 数据仓库、以及其它类型信息库中的大量数据中挖掘有用知识的过程啪1 。现在， 我们用框图的形式表示数据挖掘环境，如图2 1 所示。 。 数据挖掘：i - 具可视化工其 。v 7 可 图2 1 数据挖掘环境框图 另外，知识发现即数据挖掘的主要过程包括：数据选择、数据预处理、数据 转换、数据挖掘、模式解释或评价，以及知识表示。现在，我们以图示的形式， 描述数据挖掘在知识发现过程中的位置，以及数据挖掘的基本过程和主要步骤， 如图2 2 所示。 k 鬻耩i 诱戆 图2 2 数据挖掘的基本过程和主要步骤 由图2 2 可以看出知识发现即数据挖掘的过程，其主要分为以下几个主要的 江苏大学硕士学位论文 步骤： 数据选择：从数据库或数据仓库存储的海量数据中提取与分析任务相关的数 据。 数据预处理：现实世界中，大部分数据都是不完整、不一致的脏数据，无法 直接进行数据挖掘过程，因此，产生了数据预处理技术。其主要包括的过程 有：数据净化，用户识别，会话识别，路径补充，以及事务识别。 数据转换：将数据转换或统一成适合挖掘的数据形式。 数据挖掘：使用智能方法提取数据模式。 模式解释评价：依据某种兴趣度度量，识别表示知识的真正令人感兴趣的 数据模式。 知识表示：利用可视化或知识表示技术，向用户展示挖掘的知识。 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 曲用户性质挖掘【2 7 1 。 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 服务器的同志记录文件转化为图表，接着，进行深一步的数据挖掘。 一般情况下，通过数据预处理技术处理数据后，就可以通过传统的数据挖掘 技术进行挖掘。 2 2w e b 日志挖掘简述 6 江苏大学硕士学位论文 随着网络技术的飞速发展，w e b 数据挖掘成为一项越来越吸引人的课题。通 过这种技术，对w e b 结构和规则，w e b 存取模式，以及动态的w e b 内容的查找 的功能得以实现。 本节中，我们将对w e b 日志格式，w e b 日志挖掘的定义，w e b 日志数据预 处理过程，以及w e b 日志挖掘的应用进行探讨。 2 2 1w e b 日志挖掘的定义 w e b 日志中记录了用户访问w e b 站点页面的信息，常见的w e b 服务器同志 格式如表2 1 所示，其中r e f e r r e r 是指向被请求文件的页面的u r l ，如果用户直 接在地址栏中输入u r l 进行访问或利用书签进行访问，则该栏为空。如何直观 地显现站点中的u r l 之问的访问频率，u r l 之间的访问顺序以及页面的访问时 间等信息，对于设计较好的w e b 日志挖掘算法显得尤为重要。 表2 1 服务器w e b 日志格式 域描述 i p u s e r i d d a t e s i z e u r l s t a t u s r e f e r r e r a g e n t 远程主机的i p 或d n s 入口 远程登录的用户名 请求页面的日期，时间和时区 传送的字节 请求页面的u r l 返同给h t t p 状态标识 指向被请求文件的页面的u r l 用户的操作系统和浏览器类型 据以上分析过程，w e b 日志数据，就是用户访问站点的记录信息。其主要来 自w e b 服务器中关于用户行为的记录，该部分数据主要用于研究用户的行为模 式。 w e b 日志挖掘是指通过对大量w e b 日志记录的分析，得到用户的访问频率、 访问顺序、访问时间、访问文件大小等信息，从而发现用户浏览行为的技术，也 就是，从服务器中记录的用户的访问日志中挖掘用户的访问模式的过程。w e b 日 志挖掘过程主要包括三个阶段：数据预处理、模式识别、以及模式分析。 数据预处理：原始日志文件中存在很多噪音数据，直接用其进行数据挖掘是 7 江苏大学硕士学位论文 不准确的。按照挖掘的目的，将原始日志文件进行提取、分解、合并、以及 转化格式等过程后，形成会话文件，然后，对其进行有效地挖掘。 模式识别：采用合适的挖掘算法，对经过数据预处理后的w e b 日志记录数据 进行挖掘，从而生成访问模式。 模式分析：对模式识别过程中生成的访问模式进行分析，从而提取出有用的 模式。 2 2 3w e b 日志挖掘的难点分析 w e b 是一个全球性的信息服务中心，其涉及体育、教育、军事、文化、广告、 销售、电子商务、娱乐等多种与人民生活息息相关的行业，如何对w e b 同志进 行有效的挖掘是一个非常具有挑战性的课题，同时，会面临很多具体的难点。 随着网络技术和信息安全技术的发展，代理服务器、本地缓存、用户i p 地 址的动态分配以及防火墙技术【2 8 】广泛应用到信息交换的过程中。然而，这些技 术却使w e b 日志记录数据不太准确，直接将这些数据运用到数据挖掘中，难免 会有较大的困难，以及产生错误的挖掘结果。另外，为了减少不必要的带宽丌销， 优化网络通信质量，本地缓存大量使用，用户第一次进入页面a 时，便会将其 存储于本地缓存中，当用户点击了”b a c k 按钮时，页面会从缓存中读出，而非 通过网络链接，这种情况下，站点服务器是不能知道用户重新访问了页面a 的， 这样就容易漏记用户的请求信息。同时，在代理服务器中，也会为用户设置中间 缓存机制，同样会漏记一些重要信息。 另外，多个用户可以使用同一个代理服务器，当多个用户通过代理服务器访 问站点时，多条w e b 日志记录中便会具有相同的标识，即代理服务器的i p 地址， 这也会降低w e b 日志记录数据的准确性。 通过以上分析，真j 下能够用于数据挖掘过程中的w e b 同志记录是不多的， 那么，如何设计较为高效的挖掘算法，从不多的记录中得到有用的模式，是一项 较为吸引入的课题。 2 2 3w e b 日志挖掘的应用 w e b 日志挖掘已经成为实现站点优化，对用户更友好，对商业更优化的w e b 8 江苏大学硕士学位论文 服务的必要工具。应用于w e b 数据的数据预处理，建模以及挖掘技术的进展已 经在许多应用中获得成功，如自适应信息系统，个性化服务，w e b 分析工具以及 内容管理系统。由于w e b 应用和这些应用中用户交互的复杂度越来越高，对w e b 日志记录数据进行智能分析的需求仍在不断提高。 2 3w e b 日志挖掘的过程 本节中，将对w e b 日志挖掘的过程：数据预处理、模式识别、以及模式分 析进行详细的介绍。 2 3 1 数据预处理阶段 w e b 日志数据预处理中所需的高级任务包括从多个日志问价中融合和同步 数据。w | e b 同志预处理的主要流程【2 9 】分为：数据净化，用户识别，会话识别， 路径补充，以及事务识别。数据预处理的质量，将直接影响到最终的挖掘结果， 故日志数据预处理是非常重要的。下面，我们将对主要过程做较为详细的探讨。 1 数据净化 数据净化通常根据站点不同而不同，一般指删除挖掘过程中不起作用的服务 器同志数据的记录行1 3 0 1 。另外，还涉及的工作有删除对挖掘分析不重要的或无 关的嵌入式对象的引用，包括样式文件，声音文件以及图形。数据净化过程可能 还涉及某些数据域的移除，如传递字节数或h t t p 协议的版本信息等，这些数据 域可能不包含对分析或数据挖掘任务有用的信息。 由于数据挖掘的目的是发现有用的用户行为模式，不会关心哪些用户显式地 请求页面，故可以通过检查页面u r l 的后缀，删除那些与挖掘无关的数据。另 外，当用户请求访问页面，w e b 服务器对其请求反应失败时，w e b 日志中会对 这种动作进行记录，然而，这是跟w e b 日志挖掘无关的，所以，检索到这种数 据时，可以通过判断日志中的状态码，删除服务器放映失败的日志记录。此外， 还可以根据分析，对w r e b 日志记录进行横向和纵向的缩减【3 l 】。 2 用户识别 从w e b 日志记录中区分不同的用户确实是必要的。由于一个用户可能多次 访问同个页面，服务器同志会为每个用户记录多个会话，我们使用用户活动记 9 江苏大学硕士学位论文 录的形式来表示同一个用户的同志活动序列。 不考虑认证机制时，大多用来区分不同用户的方法是使用客户端的c o o k i e s 信息。然而，并不是所有的网站都使用c o o k i e s ，且由于隐私设置，有时客户端 c o o k i e s 会被用户禁用。仅仅用i p 地址并不能将日志记录映射到具体的访问用户， 因为，有时一个i p 地址可能是两个不同的用户访问页面。如果想设别出不同的 用户，需要将i p 地址与其它相关信息相结合，比如用户代理或被调用域等。 3 会话识别 会话识别是将每个用户的用户活动记录分成一个一个会话的过程，每个会话 代表了一次对站点页面的访问。没有认证机制或内嵌会话i d 的网站必须依靠启 发式方法进行会话识别。会话识别的目的是从点击流数据中重构信息，以获得某 个用户访问站点的真实行为序列，也就是说将用户的访问记录区分为单个的会话 ( s e s s i o n ) 3 2 1 。 一个会话就是指用户从进入站点到离开站点的时间内的一系列请求。由于在 一段时间内，用户可能多次访问了某个站点的页面，所以，需要设置一个时间阈 值，如果该用户两次访问的时间差值超过了这个阈值，就说明该用户开始了一个 新的会话。 4 路径补充 另外一个通常在会话识别之后进行的重要的预处理任务是路径补充，客户端 或代理端的缓存功能经常会导致对那些被缓存的页面和对象的访问引用的丢失。 幸好，由于缓存而丢失的记录可以通过路径补充来补全。路径补充依靠服务器日 志上的站点结构和引用信息完成。总之，路径补充的目的就是确定访问日志记录 中是否还有重要的请求没有被记录。 2 3 2 模式识别阶段 数据预处理结束后，就可以采用合适的数据挖掘技术对数据进行分析挖掘， 从而获取数据中的模式。模式识别阶段包括的主要技术有：关联规则挖掘、序列 模式挖掘、聚类分析等。 1 关联规则挖掘 在数据挖掘研究领域，关联规则挖掘是一项重要的研究课题。r a g r a w a l l o 江苏大学硕士学位论文 等人于1 9 9 3 年首先提出了关联规则挖掘的概念3 4 1 ，即数据库中一组数据项问某 种潜在关联关系的规则。数据项间的关联，是指根据一个事务中某些数据项的出 现可以导出另一些数据项在同一事务中的出现。 事实上，关联规则技术主要用于从用户访问序列数据库的序列项中挖掘出相 应的规则【3 5 】。利用从网站的w e b 日志记录中挖掘出的记录间的关联规则，可以 为网站设计者提供可靠的依据，从而更为有效地优化站点拓扑结构。目前，该类 算法大多都是基于a p f i o d 算法【3 6 ，3 7 1 。 2 序列模式挖掘 序列模式是描述在时间标记有序的事务集合中，发现其中的某些事务伴随在 另外的一些事先没有安排的事务的模式。在w e b 日志记录中，以时间标记的序 列，反映了用户的浏览模式。例如：一个客户在购买了笔记本后，可能会接着购 买屏幕保护膜，还会购买一张系统盘，那么对应的序列就是：“笔记本岭屏幕保 护膜_ 系统盘”，这种分析方法能便于电子商务方面预测用户的行为，且能在站 点服务器方有针对地选择表现页面，从而站点运营商便能在较受欢迎的页面添加 有吸引力的商业广告，赚取最大的商业利润。 一 3 聚类分析 聚类分析被看作一种探查数据结构的工具。将对象划分为簇是聚类分析的核 心，也就是说，聚类分析是依据样本问关联的量度标准将其自动分成几个簇，同 一个簇的对象是相似的，而不同簇的对象是相异的。与分类有所不同，聚类分析 不需要以先验标识符来标定数据类别标号的假定。所以，分类属于监督学习技术， 而聚类属于非监督学习技术。在w e b 日志挖掘领域有两种聚类3 8 】：用户聚类和 页面聚类。 聚类分析是一个比较活跃的研究领域，许多流行的和经典的算法已经涌现到 人们的面前，例如c u r e 、d b s c a n 、c l i q u e 、b i r t h 、k - 平均、w a v ec l u s t e r 、 o p t i c s 、s t i n g 、k - 中心点等。下面介绍几种常用的聚类算法。 曲k 中心点 k 中心点算法被看作一个典型的划分算法。对于一个给定的k ，在数据集中 寻找k 个代表，使得把每个对象划归到它最邻近的代表所表示的簇中时，代表和 对象的距离之和最小是采用该算法的目标。 江苏大学硕士学位论文 k 中心点与k 均值例具有同样的处理过程。在k 均值算法中，均值点可以 是空间中的任何点( 接近数据点或数据点本身) ；然而，在k 中心点算法中，中心 点只能是样本空间中的数据点。中心点或者被交换或者被保留，直到那些假设的 中心点不再改变为止的过程是通过计算数据点和假设的中心点之间的代价来实 现的。 k 中心点算法 任意选取k 个对象作为初始中心点( 代表) 重复 将余下的对象分配到距它最近的中心点所在的簇； 随机选择一个非中心点对象s ； 计算随机用对象s 交换s i 的总代价h ； 若h o ，则用s