（计算机软件与理论专业论文）基于用户浏览路径的web用户聚类研究.pdf

摘要 基于用户浏览路径的w e b 用户聚类研究 计算机软件与理论专业硕士研究生马晓艳 指导教师唐雁教授 摘要 随着网络技术的发展，w e b 在信息共享、电子商务和提供在线服务方面得到广泛的应用。 越来越多的人利用i n t e i n e t 来查找自己所需要的信息，如何帮助用户快速的查找到自己想要的 信息，满足他们的个性化需求便成为现代网络技术关注的重要问题。为解决这一问题，研究 人员提出了w e b 用户聚类方法。w 曲用户聚类通过对相似用户归类，了解用户群体的需求和 兴趣，从而为用户提供更优质的服务。 w e b 用户聚类主要是对w e b 日志进行挖掘，主要包括三个步骤：首先对日志进行预处理 提取用户的特征；然后根据用户特征计算用户间的相似度；最后进行用户聚类。用户特征的 提取和用户相似度计算在聚类过程中非常重要，它们的好坏直接影响用户聚类的效果。目前， 用户特征或者采用用户会话路径来表示，或者采用事务识别出的目标页面来表示，但是会话 路径粒度通常太大，目标页面也很难发现用户的浏览行为；相似度计算时，已有方法主要进 行集合之间的交集运算，还有方法提出采用平均停留时间来计算相似度，但这些方法都不能 很好的发掘用户的真正兴趣。 针对上述的问题，本文提出一种新的用户特征表示方法，采用事务识别提取的路径来表 示用户特征。它比用户会话路径粒度小，同时弥补了目标页面表示用户特征的不足，能很好 的发现用户的浏览行为。并以此为基础，提出一种新的相似度计算方法堋7 s c ( w e bu s e r s i m i l a r i t yc a l c u l a t i n g ) 。该方法将事务路径看作一个有序序列，考虑用户问路径上的相同部分 和整条路径的关系，并充分结合用户浏览路径上的停留时间来计算用户间的相似度。用户浏 览路径上的停留时间主要通过路径上各个页面停留时间来计算，页面停留时间指下一页面开 始访问的时刻减去本页面开始访问的时刻，这种停留时间计算方法能较真实地反映用户的兴 趣。 最后，在新的用户特征表示方法和w u s c 方法基础上，使用u b p c 聚类算法完成基于用 户浏览路径的w e b 用户聚类，并进行对比实验。实验结果证明：本文方法对用户相似度的计 算更接近真实的情况，能够达到提高w e b 用户聚类的效果。 关键字：数据挖掘相似度w e b 日志用户聚类用户浏览路径 。t h es t u d yo fc l u s t e r i n 鬈w e bu s e r s b a s e do nu s e r ，sb r o w s i n gp a t h m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y s u p e r v i s o r ：p r o f t a n gy a n a u t h o r ：m a x i a o y a n a b s t r a c t w i t ht h ed e v e l o p m e n to f n e t w o r k i n g t e c h n o l o g y , t h ew e bi sw i d e l yu s e di ni n f o r m a t i o ns h a r i n g , e - c o m m e r c ea n do n l i n es e r v i c e s m o r ea n dm o r ep e o p l eu s et h ei n t e r n e tt os e a r c hi n f o r m a t i o nt h e y n e e d 。h o wt oh e l pu s e r sf i n dt h ei n f o r m a t i o nt h e yn e e dq u i c k l ya n dt om e e tt h ew e bu s e r s p e r s o n a l i z e dn e e d sa r ei m p o r t a n ti s s u e st h a tm o d e mn e t w o r kt e c h n o l o g ys h o u l dc o n c e l l la b o u t 。t o s o l v et h i sp r o b l e m , r e s e a r c h e sb r i n gf o r w a r daw e bu s e rc l u s t e r i n gm e t h o d b yc l a s s i f i e dt h es i m i l a r u s e r s ，w e b 雒s 糕c l u s t e r i n g 渤嫩u n d e r s t a n d 磷；e 然n e e d sa n di n t e r e s t s ，t h e np r o v i d eu s e r sw i t hb e t t e r s e r v i c e w e b 嚣s 嚣c l u s t e r i n gi sp r i m a r i l ym i n i n gb a s e do i lw e bt o g , i n c l u d e st h r e es t e p s ：f i r s t , e x t r a c t i n g t h el o gu s e rc h a r a c t e r i s t i c sb yp r o - p r o c e s s i n gw e bl o g , t h e nc a l c u l a t i n gu s e r s s i m i l a r i t i e sb a s e do n t h e i rc h a r a c t e r i s t i c s ，a tl a s tc l u s t e r i n gt h eu s e r s t h et w os t e p so f e x t r a c t i n gw e bu s e r s c h a r a c t e ra n d c a l c u l a t i n gs i m i l a r i t yb e t w e e nu s e r sa r es oi m p o r t a n tt h a tt h e yc a l li n f l u e n c et h ee f f e c to ft h eu s e r s c l u s t e r i n gs t r a i g h t l y a tp r e s e n t ，t h eu s e r sc h a r a c t e r i s t i c sa r et y p i c a l l ye x p r e s s e db yt h ep a t ho ft h eu s e r ) ss e s s i o no r t h et a r g e tp a g eo fu s i n ga f f a i ri d e n t i f i c a t i o n b u tt h e ya l lh a v ed i s a d v a n t a g e s ，t h eg r a n u l a r i t yo f u s e r s s e s s i o np a t hi st ol o n g ，a n dt h et a r g e tp a g ei sa l s od i f f i c u l tt oe x p r e s st h eu s e r sb r o w s i n g b e h a v i o r w i t hr e g a r dt oc a l c u l a t i n gu s e r s s i m i l a r i t i e s , m e t h o d st h a th a v eb e e ni sm a i n l yc o m p u t i n g i n t e r s e c t i o na m o n ga g g r e g a t i o n s ，t h e r ea r ea l s om e t h o d su s et h ea v e r a g es t a yt i m et oc a l c u l a t e s i m i l a r i t yb e t w e e nu s e r s ，b u tt h o s em e t h o d s 鑫畿n o tv e r yg o o dt oe x p l o r et h eu s e r sr e a li n t e r e s t a i m i n ga tt h ed i s a d v a n t a g e so ft h o s em e t h o d s ，t h i sp a p e rp r e s e n t san e wm e t h o dt oe x p r e s s u s e r s c h a r a c t e r i s t i c s t h em e t h o de x t r a c t sp a t ho fu s i n ga f f a i ri d e n t i f i c a t i o nt oe x p r e s su s e r s c h a r a c t e r i s t i c s ，t h eg r a n u l a r i t yo fa f f a i rp a t hi sf i n e rt h a nb s e r s s e s s i o np a t h ，a n di ta l s om a k e su pf o r t h el a c ko ft a r g e tp a g e ，s oi tc a l lf i n dag o o du s e rb e h a v i o r a n db a s e do nt h en e wc h a r a c t e r i s t i c s e x p r e s s i o nm e t h o d ，t h i sp a p e rp r e s e n t san e ws i m i l a r i t yc a l c u l a t i o nm e t h o d - - - w - u s c ( w e bu s e r s i m i l a r i t yc a l c u l a t i n g ) t h em e t h o dt r e a t su s e r s a f f a i rp a t ha sa l lo r d e r l ys e q u e n c e ，t a k i n gt h e 两南大学硕士学位论文 r e l a t i o n s h i pb e t w e e nt h es r l n ep a t ha n dt h ee n t i r ep a t ho ft h eu s e r s ，a n df u l l yi n t e g r a t i n gb r o w s i n g t i m eo ft h ep a g e so fu s e r s a f f a i rp a t h t h em e t h o dt oc a l c u l a t et h eb r o w s i n gt i m eo ft h ep a g ei st o u s ea c c e s s i n gt i m eo f n e x tp a g et om i n u st h ea c c e s s i n gt i m eo f v i s i t i n gp a g e a tl a s t ，b a s e d0 1 1t h en e wm e t h o do fu s e r s c h a r a c t e r i s t i c se x p r e s s i o na n dw u s c ，t h ep a p e ru s e s u b p ca l g o r i t h mt oa c h i e v et h ew e bu s e rc l u s t e r i n gb a s e d0 1 1u s e ：l b r o w s i n gp a t h , a n d h a v ea c o m p a r i s o ne x p e r i m e n t t h ee x p e r i m e n tp r o v e dt h a t ：c a l c u l a t e dt h es i m i l a r i t yo f t h eb s e r sb ym e t h o d o ft h i sp a p e ri sc l o s e rt ot r u e ，a n db e i n ga b l et oi m p r o v et h ee f f e c to fc l u s t e r i n gw e bu s e r s h at h ee n d ， w ep r e s e n tt h er e s e a r c he m p h a s i si nt h ef u r o r e k e y w o r d ：d a t am i n i n g ；s i m i l a r i t y ；w e bu s a g e ；u s e rc l u s t e r i n g ；u s e r s b r o w s i n gp a t h 1 v 独创性声明 学位论文题目：基王用应浏览整堡煎坠鱼周应塞娄盈究 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加 特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同仁 在文中作明确说明并表示衷心感谢。 学位论文作者：与嘞艳签字日期：伽7 年岁 月；2z 日 学位论文版权使用授权书 本人提交的学位论文是在导师指导下进行的研究工作及取得的 研究成果。论文中引用他人已经发表或出版过的研究成果，文中已加 特别标注。对本研究及学位论文撰写曾做出贡献的老师、朋友、同仁 在文中作明确说明并表示衷心感谢。 ( 保密的学位论文在解密后适用本授权书，本论文：由不保密， 口保密期限至年月止) 。 ，尸 学位论文作者签名：为骁毫乞导师签名： 噌( ，哆 签字日期：洳号年r 月z z 日 签字日期：吖年厂月。2 日 t 第一章绪论 第一章绪论 本章主要介绍基于用户浏览路径进行w e b 用户聚类的研究目的和意义，以及 w e b 用户聚类在国内外的研究现状。在分析现状的基础上，提出本文研究的主要 内容，最后给出论文章节的安排。 1 1 研究目的和意义 伴随着i n t e m e t 技术的发展，网络资源同时迅速增长，其重要性也越来越被人 们所注意到。它正在以绝无仅有的优势影响着全人类的生活，人们的生活、工作、 学习越来越依赖于网络。目前，政府部门、公司、学校、研究院等都拥有或正在 建立自己的网站，甚至个人也能拥有自己的网站。其次，w e b 在信息共享、电子 商务和提供在线服务方面的广泛应用，许多企业投入大量的资金来建立自己的网 站用于发布信息，或是在一些商业网站上为自己的产品和服务做广告，或者是在 网上开展电子商务活动。 客户浏览行为的数字化，使得通过收集大量用户行为数据来深入研究客户行 为变成可能。如何利用这个机会，从这些“无意义 的繁琐数据中找出大家都看 得懂的0 有价值的知识和信息是目前面临最紧要的问题之一。解决这个问题的办 法之一就是应用w e b 数据挖掘技术，即通过挖掘服务器中的日志文件，来得到用 户的访问模式，从而得到对改进网站的结构和个人化服务都有用处的信息。 目前网站的数据挖掘主要应用于对w e b 站点的日志挖掘。w e b 服务器日志文 件记录了所有用户与服务器的交互信息，通过对这些记录的挖掘可以找出浏览者 的浏览规律，这对于掌握w e b 服务器的运行情况、分析用户的行为、了解用户群 体的需求、维护系统安全、辅助站点维护人员优化站点具有重要作用。从而为网 站的管理者提供网站改进资料，使网站的管理者可以对站点进行有针对性地改进 和设计，来达到使w e b 站点吸引更多的客户的目的，这点在电子商务网站中更加 明显，因为吸引浏览者就意味着吸引潜在的客户。因此，准确地将用户的行为聚 类对这些迫切需要掌握用户群体需求的企业来说是至关重要的，同时表明w e b 站 点的日志挖掘有着极其现实的意义。 通过对w e b 日志挖掘，提取用户浏览路径，分析用户访问兴趣并进行准确的 用户聚类有以下的目的i l j ： 考虑每个用户的特殊要求，为用户提供个性化服务。网络上海量 的信息与用户狭窄专一的需求产生矛盾，一方面造成信息资源的巨大浪 费，另一方面，每个用户寻找所需要的信息造成巨大困难。因而，提供符 西南大学硕十学位论文 暑量曼鼍曼曼曼i i _i ioi i i 一一一一一一一 ；! i 合用户需求的个性化服务有利于用户快速得到所需信息。如：电子商务网 站中的推荐系统。 调整网站的结构，优化服务性能。根据相同兴趣的用户群体访问 行为和遍历的路径，以及发现的频繁访问页面组等信息，调整网站结构。 在一些逻辑上相关联，但并不位于同一条遍历路径的页面增加超链接，便 于用户访问所需要的页面。 合理的设置广告。通过对用户的聚类，把需求和兴趣非常相似的 用户归为一类。这样我们可以根据各个用户组的兴趣，在各类用户访问的 路径上设置和用户兴趣相关的广告。如电子商务广告的投放。 1 2 国内外研究现状 w e b 聚类挖掘作为数据挖掘的一个新兴的研究领域，主要集中在相似用户群 体的聚类和相关w e b 页面的聚类两个方面。w e b 用户聚类挖掘主要是通过w e b 日 志挖掘，提取用户浏览的信息进行用户聚类。 w e b 用户聚类属于w e b 日志挖掘，可以分为以c h e n 为代表的基于事务的方 法【2 】和以h a n 为代表的基于数据立方体的方法【3 1 。最初研究的重点放在对用户模式 发现中挖掘算法的设计、分析和改进，现阶段对日志文件预处理方法和模式分析 的研究也有所增加。 国内的w e b 日志挖掘研究还处于起步阶段，主要侧重于理论研究。陈才扣等 人【4 】提出了一种新的w e b 的序列模式，访问序列模式，并提出了识别最大前向访 问路径和发现最大访问路径的算法。上海交通大学提出了一种w e b 日志预处理阶 段的f r a m e 页面过滤算法【5 】，中科院提出了k - p a t h s 路径聚类方法，根据用户访问 兴趣对用户集进行划分【6 】。中国科技大学在文献【7 中提出了一个用户识别的通用 算法。 对于w e b 用户聚类，国内的大多数研究者还停留在主要依靠统计学方法和简 单聚类方法的阶段，主要的聚类方法有： 基于模糊等价关系的聚类算法【8 】。先建立用户间模糊相似矩阵，然后用传递闭 包法求模糊等价矩阵来对用户聚类。 黄松等人于2 0 0 1 年提出在聚类前根据网页的层次性【9 1 ，采用面向属性的推理 方法构造归纳化的会话向量，从而减少会话向量的维数，生成基于归纳法会话的 网络用户的聚类。 2 0 0 6 年，张文东，易轶虎【lo 】提出了一种页面内容和浏览路径的用户聚类方法。 着重考虑了用户访问页面的先后顺序和页面语义。 2 第一章绪论 2 0 0 7 年，付志涛【1 1 提出一种基于用户浏览路径内容的网络用户聚类方法。这 种用户聚类方法优点在于：注重了用户的兴趣的同时，降低了用户特征表示的维 度。 2 0 0 8 年陈敏】等提出一种基于用户浏览行为聚类w e b 用户的方法，把用户的 浏览模式作为序列模式，同时考虑了用户浏览的时间因素。 近年来，国外在w e b 用户聚类领域的研究上作取得了很大的进展，特别是在 聚类算法上取得了一定的成果，例如： 1 9 9 4 年r 了h a t h a w a y 、j c b e z d e k 提出n e r f ( n o n e u c l i d e a mf u z z yc m e a n s ) 算法 i2 1 。它是一种用于处理非欧几里得的关系数据的模糊聚类算法 19 9 9年o n a s r a o u i 、 h f r i 蛳、 a j o s h i和 r k r i s h n a p u r a m提出 c a r d ( c o m p e t i t i v ea g g o l m e r a t i o nf o rr e l a t i o nd a t a ) f l 向算法【l3 1 ，能够聚类非欧里得 的关系数据，可用于日志中自动发现用户的访问模式。缺点是不够健壮。同年， o n a s r a o u i 、a j o s h i 和r k r i s h n a p u r a m 提出r f c m d e ( r e l a t i o nf u z z yc - m a x i m a l d e n s i t ye s t i m a t o r ) 算法【1 4 1 。能够处理用户会话聚类中典型的噪音数据，并可用于聚 类非欧几里得的关系数据。作者通过实验证明了该算法在健壮性上优于n e r f 。 文 1 5 ，1 6 ，1 7 提出了在w e b 站点中根据页面访问统计进行聚类的方法。通过用 户对页面的访问时间和次数来聚类，并优化w e b 站点。 1 9 9 9 年y o n g j i a nf u 【1 8 】等人提出一种网页层次结构与用户会话相结合的方法来 进行用户聚类。 2 0 0 0 年a j o s h i 和k j o s h i 提出用户会话聚类的模糊聚类算法【1 9 i f c m d d ( f u z z y c m e d o i d s ) 及其健壮性改进算法f c t m d d ( f u z z yc t r i m m e dm e d o i d s ) 。它们都要求 在聚类前都要先确定一个固定的聚类数目。 1 3 本文研究内容 本文旨在研究和实现一种以w e b 日志为数据源，采用一种新的用户特征表示 方法，并在此基础上，使用改进的相似度计算方法堋7 s c 来计算用户相似度， 最后选用u b p c ( u s e rb r o w s i n gp a t hc l u s t e r i n g ) 算法完成的w 曲用户聚类，并最终 达到提高用户聚类效果的目标。 本文主要研究的内容如下： 1 分析和总结国内外关于w e b 用户聚类研究现状，将用户浏览路径的结 构和时间作为研究用户聚类的切入点。 2 在对现有用户特征表示方法分析的基础上，提出了一种新的用户特征 表示方法，采用事务识别提取的路径来表示用户特征。该方法把识别出的路径 看作用户的浏览路径，它比用户会话路径粒度小，弥补了目标页面表示用户特 西南大学硕士学位论文 征的不足，能很好的发现用户行为。 3 以新的用户特征表示方法为基础，提出一种新的相似度计算方法一 w u s c ( w e bu s e rs i m i l a r i t yc a l c u l a t i n g ) 。该方法将事务路径看作一种有序序列， 这里主要依据用户浏览页面的时间先后顺序，同时充分结合了用户在整条浏览 路径、浏览路径的相同部分及这两方面的时间因素来计算用户的相似度，时间 因素主要指用户的停留时间。 4 在新的用户特征表示方法和w u s c 方法的基础上，采用u b p c 算法实 现了基于用户浏览路径的w e b 用户聚类，并通过对比实验证明本文方法的优 越性。 1 4 本文的组织结构 论文整体组织结构安排如下： 第一章：阐述课题目的和意义，介绍与课题相关的国际国内研究情况和进展， 确定了研究内容和组织结构。 第二章：首先对w e b 挖掘的概念和分类进行阐述；然后详细介绍w e b 挖掘中 的w e b 日志挖掘，主要包括：w e b 日志挖掘的定义、步骤和前景。其中，对w e b 日志挖掘步骤进行重点介绍。 第三章：对聚类的理论知识、聚类的分类情况进行介绍，同时重点阐述了用 户浏览路径聚类算法u b p c 。 第四章：第一节主要介绍w e b 用户聚类的步骤及实现流程；第二节详细介绍 本文提出的用户特征表示方法；第三节详细介绍本文提出的计算相似度方法；第 四节，介绍在新的用户特征表示方法和相似度计算方法基础上，使用u b p c 算法 对用户进行聚类的步骤。 第五章：在本文提出的用户特征表示方法和计算相似度方法的基础上，完成 基于用户浏览路径的w e b 用户聚类的实验，并对用户聚类的结果进行分析。 第六章：总结本文所做的工作，提出今后进一步研究的方向。 4 第二章w e b 挖掘概论 第二章w e b 挖掘概论 本章主要介绍w e b 挖掘的概念和分类，对w e b 挖掘中的w e b 日志挖掘进行详 细介绍。其中，又结合w e b 用户聚类的步骤对w e b 日志挖掘的每个步骤进行重点 阐述，包括：数据预处理、模式发现、模式分析。 2 1w 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 中提取知识，改进站点设计。在文献【1 中对w e b 挖掘作如下定义： 定义2 1 ( w e b 挖掘) ：w e b 挖掘是指从大量的与w e b 相关的资源和使用集合s 中发现有用的、感兴趣的和隐含的模式m 。如果将s 看成是输入，m 看作输出， 那么w e b 挖掘的过程就是从输入到输出的一个映射： 孝：s 专m w e b 挖掘从数据挖掘发展而来，都是在对大量的数据进行分析的基础上，做 出的归纳性推理，预测客户的行为。特征化( c h a r a c t e r i z a t i o n ) 、分类( c l a s s i f i c a t i o n ) 、 预钡, 1 ( p r e d i c t i o n ) 、聚类( c l u s t e r i n g ) 、关联( a s s o c i a t i o n ) 和序列模式( s e q u e n t i a lp a t t e r n ) 分析等用于数据库知识发现的技术，都可以用于w e b 数据的知识发现。 2 2w e b 挖掘的分类 在w e b 挖掘中，可用来挖掘的数据源是多种多样的，一般这些数据源大致可 以分为以下几类【2 0 】： 1 、内容数据：用户在网页上看到和使用的真实数据，主要是文本和图像。 2 、结构数据：描述网页内容如何组织的数据。网页内的结构可用h t m l ，m l 谣南大学颈士学位论文 表示为树型结构，h t m l 标志成为树的根；网页阔结构可用连接不图网夏的超链 接来表示。 ， 3 、使魇数据：描述网页使蘧模式的数据，比如璎地址、u r l 、鼹页弓l 焉、访 问时间和日期等，表示用户的行为模式。典型的使用数据来自服务器的豳志。本 文主要对使用数据进行挖掘。 4 ；用户资料( p r o 蠡l e ) ：有关w e b 站点用户的统计信息，包括用户注册信息矛曩 个人资料，入用户名、学历、职务、年龄、收入、个人爱好等。 根据上瑟的数据资料分类，w e b 挖掘一般可以分为三类：w e b 内容挖掘：w e b 。 结构挖掘；w 曲使用挖掘。其中w e b 内容挖掘和w e b 结构挖掘分别是对前两类数 据进行挖掘，w e b 使用挖掘则主要针对的是用户和溺络交互过程中提取的数据， 主要包括：w e b 服务器日志记录、代理服务器的日志记录、浏览器的日志记录、 用户简介、注册信息、交易信息等。w e b 挖掘分类结构图如下图2 1 所示f 2 习： 图2 一 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 结构挖掘 6 第二章w e b 挖掘概论 w e b 结构挖掘1 2 5 】是从w w w 的组织结构和链接关系中推导知识，挖掘w e b 潜在的链接结构模式。通过分析一个网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。这种模式可以用网页归类，并且由此可以获得有关不同网 页间的相似度及关联度的信息。 w e b 结构包括页面内部的结构以及页面之间的结构。通过挖掘w e b 结构信息， 对于导航用户浏览行为、改进站点设计、评价页面的重要性等都非常重要。 p a g e r a n k 算法和c l e v e r 算法利用w e b 网页间的链接信息来查找“权威”网页 和“集线器 。w e b 结构挖掘在个性化搜索引擎或主题搜索引擎研究领域得到了广 泛的应用。 三、w 曲使用记录挖掘 w e b 使用记录挖掘【2 6 】面对的是在用户和w e b 交互的过程中抽取出来的第二手 数据，包括网络服务器访问记录、代理服务器日志记录、用户对话或交易信息、 用户提问方式等。w e b 使用挖掘是从一个或者多个服务器中发现用户访问模式， 并抽取感兴趣的模式，通常为w e b 使用挖掘提供数据的是w e b 服务器的日志。 w w w 中的每个服务器都保留了访问日志( w e b a c e e s sl o g ) ，记录了关于用户访问 和交互的信息，通过分析和探究w e b 日志记录中的规律可以识别电子商务的潜在 客户，理解用户的行为，从而改进站点的结构，或为用户提供个性化的服务。 本文实现的基于用户浏览路径的w e b 用户聚类就属于w e b 使用挖掘，它主要 是对w e b 服务器上的日志进行挖掘，在此，本文将对w e b 使用挖掘做详细介绍。 w e b 使用挖掘的过程一般分为三阶段阶：预处理阶段、模式发现、模式分析阶段， 挖掘过程如图2 2 所示： 图2 - 2w e b 使用挖掘的过程 1 、预处理：需要对收集的数据进行必要的预处理，例如清除“脏”数据。w e b 使用挖掘不是简单地把数据挖掘算法应用在w e b 日志上，因此在具体使用挖掘算 法之前要进行相应的数据预处理，包括：数据清洗、用户识别、会话识别、路径 西南大学硕士学位论文 暑i m l 一! , i i i , i i i ! ! ii i i ! i i ! i i i i i iiiiiiiiiiiiiii i l li i i i i ii i i ii i i i i , i 补金和事务识剐等泌l 。本文主要通过数据预处理得戮表示用户韵特征。 2 、模式发现：模式发现旨在使用各种数据挖掘技术发掘隐藏在数据背后的规 律和模式。可以使用统计、数据挖掘、机器学习和模式识别等各领域中己开发的 方法和算法，但把这些方法和算法应用予w e b 使用挖掇时，要考虑具体w e b 数据 的特性。 常焉酶技术有统计分析、关联规则发掘、生成序列模式、聚类和依赖关系的 建模等2 8 , 2 9 。本文采用聚类技术，通过用户的聚类来发现相同习惯和兴趣的用户 群体。 3 、模式分耄蓐：模式分析是从所挖掘的大量规贝| j 或模式中发现有实用价值的规 则或模式，模式分析的技术主要有s q l ，o l a p 3 ”1 1 技术和可视化技术【3 2 l 。 表2 护3 】对w e b 内容挖掘、w e b 结构挖掘和w e b 圈志挖掘中的数据特征、表 现形式、挖掘方法以及应用领域等方面进行了比较。 表2 - iw e b 内容挖掘、结构挖掘和昌恚挖掘 艺较 w e b 挖掘 w e b 爽窖挖攘w e b 结构挖撂 w e b 蠢恚挖擒 信息检索领域数据库领域 数攘文本文握：越文本文校链接练毒驽w e b 照务器疆志： 超文本文挡： p r o x y 目志： 浏览器日志： 数擐特征孥结构纯；半结拘亿： 辘接缝构；交要式数据； 半结构化；w e b 站点看作是一个 数据g g , 数据 无彦璃亭的攀诲集会；对象交换模登： 露；关系表； 表示形式概念实体；关系曲线；图； 关系曲线： 方法t f i d e f 及变彤：专利算法；专利算法； 统计： 机器学习；i l p ；关联规列及变形； 绕请；关联撬鲢及交形：聚类： 序列模式： 应用领域 聚类：发现频繁子结构：聚类； 站点结构优化： 寻找摘取规鹅：提取w e b 站赢大纲：用户建模 寻找文本模式：推荐系统 2 3w e b 曰志挖掘 2 3 1w e b 日志简介 数据挖掘中一个很重要的步骤就是要为挖掘算法找到合适的数据源。在w e b 目志挖掘中，数据最巍接的来源是w e b 服务器上的w e b 日志文件。w e b 日志文件 非常骧确地记录了访阆者的测览行为相关信息，逸此在w e b 匿志挖掘中有很重要 一r 第二章w e b 挖掘概论 的地位。 w e b 用户访问日志分别记录在三个地方【3 4 】：客户端、代理服务器端和w e b 服 务器端。三种日志数据集记录了用户使用网络资源的不同模式信息。 1 、客户端浏览器记录了单个用户对单个站点或单个用户对多个站点的用户访 问情况。 2 、代理服务器日志跟踪记录了多个用户访问多个网站的情况，同时代理服务 器内部的c a c h e 内，也记录了用户对多个站点的访问内容。 3 、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 日志主要包括以下几种日志【3 5 】： 1 、a c c e s s 日志：记录用户访问网站的具体信息包括用户d 或解析后的域名 地址、用户访问日期、请求时间、传输类型、用户访问页面的u r l 等。 2 、a g e n t 日志：可选日志，描述客户浏览器类型。 3 、e r r o r 日志：记录服务器执行过程中的错误日志。 4 、r e f e r r e r 日志：可选日志，记录用户的“f r o m t o ”导航行为，例如从u r l l 到u v , l 2 ( 也就是用户通过u r l l 到达了u r l 2 ，u r l l 是u r l 2 的引用页面) 。 5 、c o o k i e 日志：可选日志，记录访问者与服务器交互的c o o k i e 信息。 6 、e l f 日志：扩展日志，管理员定义的任何从服务器环境获得的数据，与a c c e s s 日志类似。它把以上几种日志信息合并成一行信息，目前的大部分w e b 服务器都 支持e l f 日志。 7 、a p p l i c a t i o n 日志：基于w 曲的应用程序日志。该类日志由应用程序产生一 般包括一些商用的或隐私的信息。 以上所述，w e b 服务器日志记录了用户访问本站点的信息，典型的w e b 服务 器日志包括以下信息【3 6 】：p 地址、请求时间、方法：被请求文件的u r l ，h t t p 版本号、返回码、传输字节数、引用页的u r l ( 指向被请求文件的页面) 和代理等属 性。而这些属性是否在日志中出现又取决于w e b 曰志的格式，比较常见的日志格 式有3 种：通用日志格式( c o m m o nl o gf o r m a t ) 、扩展日志格式( e x t e n d e dl o g 9 西南大学硕士学位论文 f o r m a t ) 、a p a c h e 和sw 3 cw 曲日志格式。表2 2 是w e b 日志记录的格式表【3 3 】： 表2 - 2w e b 日志记录格式 属性域属性域的描述 日期( d a t e l 用户请求页面的日期 时i 司( t i m e l 用户请求页面的具体时间 客户i p 地址f c - i p )客户端主机的i p 地址或d n s 入口 用户名( c s - u s e m a m e ) 客户端的用户名 服务器名( s c o m p u t e r n a m e ) 服务器的名称 服务器i p 地址( s i p ) 服务器的i p 地址 服务器端m ( s - p o r t )服务器的端口号 方法( c s - m e t h o d )用户请求的方法( g e t , p o s t ) u r l 资源( c s u r l - s t e m ) 用户请求的页面 u r l 查询( c s u r l - q u e r y ) 用户请求的查询 协议状态( ( s c - s t a t u s )返回h r r p 的状态标识 发送字节流( ( s c - b y t e s ) 服务器发送的字节数 接收字节流( ( c s - b y t e s )服务器收到的字节数 所花时间( t i m e t a k e n ) 完成浏览所花费的时间 协议版本( c s v e r s i o n )传输用的协议版本( 如h t r p 4 0 ) 主机( c s b o s t ) 服务器的操作系统 用户代理( c s ( l t s e r - a g e n t ) ) 服务的提供者 c o o k i e ( c s ( c o o k i c ) ) c o o k i e 标识号 引用页( c s ( r e f e r e r ) 1用户浏览的上一页 其中标有号的是扩展日志中增加的硬而其他的是通用日志和扩展日志郡存在的项在我们的日志分析过程中，并不是所有条且 都必须使用，我t r i p , 把日志记蒙中用到的e l 恚条目投影出来 在日志文件中，每条记录被称作项或者条目，其中客户端口地址是发出该请 求的客户端的d 地址，在p r o x y 代理服务器环境下为代理服务器口地址。用户名 一般不填写，只有当存取特定的文件，需要鉴别身份时才需要。时间表示w e b 服 务器接受该请求的时间，在整个日志文件中，每一项以时间递增排列。方法主要 指用户的请求方法，一般有：g e t ，p o s t ，h e a d 。g e t 从w e b 服务器得到对 象，p o s t 向w e b 服务器发送信息，h e a d 仅请求一个对象的h t t p 头。r e f e r e r 域表示上次被请求的页面，如果用户通过直接键入地址或通过书签访问，那么该 域为空。用户代理域能够指出客户端的操作系统和浏览软件。在某些日志中，不 记录r e f e r e r 域和用户代理域。 第二章w e b 挖掘概论 2 3 2w e b 日志挖掘的定义 w e b 日志挖掘【37 】属于w 曲使用挖掘的范畴，是指采用数据挖掘的技术，通过 对w e b 服务器日志中大量的用户访问记录深入分析，发现用户的访问模式和兴趣 爱好等潜在且有用的未知信息和知识，用于分析站点的使用情况，为用户提供更 好的，更为人性化的服务。 不同用户对同一网站的兴趣存在差异，但多多少少会有某些相同之处，这能 够从他们在服务器日志中留下的访问记录反映出来。因此，通过对日志的挖掘， 可以发现用户的共同偏好和交叉兴趣。另一方面，同一用户在不同时期可能有不 同的访问模式，但从长期来看，也表现出一定的规律和趋势，能够反映用户的兴 趣。统计数据表明【3 8 】：大多数用户在网站上的活动范围是有限的，因而他们的活 动中必然包含许多重复的动作，即用户的行为是有规律可循的，w e b 日志挖掘能 够发现这些规律。此外，由于w e b 服务器日志中记录了该服务器被外部访问的所 有过程信息，通过对这些过程信息的分析，可以客观地反映服务器的内部结构、 组成、内容、访问频度等有关服务器的重要信息，这对于评价和改进网站的服务 质量来说是非常宝贵的资源。并且，在任何一个服务器上都可以很方便地得到它 的日志文件，数据的来源很方便，随着数据挖掘技术的日趋成熟使得对巨大数据 文件的处理变得可能【3 9 1 ，因此w e b 日志挖掘是有效可行的。 2 3 3w 曲日志挖掘的步骤 w 曲日志挖掘的过程【4 0 】一般分为3 部分，即数据预处理阶段、模式发现阶段 和模式分析阶段。 数据预处理：是指根据挖掘的目的，对原始w e b 日志文件中的数据进行分解、 合并、最后转化为适合进行数据挖掘