（计算机应用技术专业论文）基于web日志挖掘的用户会话聚类算法的研究与应用.pdf

摘要 摘要 随着万维网的不断发展，用户从海量数据中提取有效信息变得越来越困难。 聚类分析作为w e b 数据挖掘的重要方法，对降低数据规模，过滤无效信息起着 至关重要的重用。本文以基于w e b 同志挖掘技术的用户会话聚类算法为研究对 象，详细剖析了聚类分析技术的原理和应用。 本文首先探讨了w e b 日志挖掘的日志预处理技术的流程和实现方法，它是 用户会话聚类重要基础步骤。本文对日志采集，日志清洗，用户识别，路径补充， 会话识别和事务识别各个日志处理阶段的任务和实现算法进行了细致的分析，并 通过实验模拟和演示了日志预处理的整个过程，并给出了每一阶段的预处理算法 运行的结果，实验结果表明了日志预处理算法的有效性和噪声去除能力。 然后，本文深入地研究了聚类分析技术的理论基础，对聚类分析处理的数据 类型，所使用的数据结构和分类方法进行了总结和阐述。本文的重点部分放在对 典型层次聚类算法r o c k 的改进上，r o c k 聚类算法利用共享邻居数，即连接 的概念，来建立新的相似度量方法，以处理一些高维稀疏数据，但算法具有较高 的时间复杂度和空间复杂度，以及过多的参的缺点。q r o c k 算法是已有的对 r o c k 算法的改进版，它利用连通子图的概念来改进r o c k 算法，提高了执行 效率，消除了参数期望聚类数。q r o c k 算法虽然一定程度了提高了算法效率， 但依然有o ( n 2 ) 的时间复杂度，对此，本文提出了一种适用于大规模用户会话聚 类的算法h r o c k ，算法以原子簇聚类为第一聚类阶段，进一步降低了聚类规模， 第二聚类阶段在原子簇的基础上运行传统的r o c k 聚类算法，这种两阶段混合 聚类算法，具有近似线性的时间复杂度和很好的聚类效果，而且，h r o c k 算法 通过引入图的孤立点的概念消除了算法对聚类数目参数的依赖。 其次，本文给出了一个基于本文所提出的大规模用户会话聚类算法h r o c k 的网页推荐系统原型设计，系统基于b s 架构，符合j 2 e e 规范，由日志解析模 块，日志预处理模块，用户会话聚类模块和网页推荐模块这几个重要模块构成， 整体上分为离线聚类部分和在线推荐部分。 最后，本文总结了所做的工作，给出了聚类算法h r o c k 今后的改进方向。 关键词h r o c k 聚类算法；聚类分析；w e b 日志挖掘；推荐系统 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n t e r n e t ，i ti sg e t t i n gm o r ea n dm o r ed i f f i c u l tt o o b t a i nu s e f u li n f o r m a t i o nf r o mam a s so fd a t a a sa ni m p o r t a n tw e bd a t am i n i n g m e t h o d ，t h ec l u s t e r i n ga n a l y s i st e c h n o l o g yp l a yac r u c i a lr o l ei nd e c r e a s i n gt h ed a t a s c a l e ，f i l t e r i n gt h ei n v a l i d a t e di n f o r m a t i o n b a s e do nt h ew e bl o gm i n i n gt e c h n o l o g y , t h i sp a p e rc h o o s e st h eu s e rs e s s i o nc l u s t e r i n ga l g o r i t h ma st h er e s e a r c h i n go b j e c t i v e ， a n dd i s c u s s e st h ep r i n c i p l ea n da p p l i c a t i o no fc l u s t e r i n ga n a l y s i st e c h n o l o g yd e e p l y a tf i r s t ，t h i sp a p e rd i s c u s s e st h ep r o c e d u r ea n di m p l e m e n t a t i o no ft h ew e bl o g p r e p r o c e s s i n gm e t h o d i ti st h ef o u n d a t i o no ft h eu s e rs e s s i o nc l u s t e r i n g t h i sp a p e r g i v e st h ed e t a i l sd e s c r i b i n g o ft h ee a c h s i n g l ep h a s eo ft h ee n t i r e w e bl o g p r e p r o c e s s i n gw o r k f l o w , i n c l u d i n gl o gc o l l e c t i n g ，l o gc l e a n i n g ，u s e ri d e n t i f i c a t i o n ， p a t hc o m p l e t i o n ，s e s s i o ni d e n t i f i c a t i o na n dt r a n s a c t i o ni d e n t i f i c a i t o n t h ew h o l e p r o c e d u r eh a sb e e ns i m u l a t e dt h r o u g ht h ee x p e r i m e n t ，a n dt h er e s u l td e m o n s t r a t e st h a t t h ew e b l o gp r e p r o c e s s i n ga l g o r i t h mi sv a l i d a t e da n dn o i s ei m m u n e t h e n ，t h et h e o r yo ft h ec l u s t e r i n ga n a l y s i sh a sb e e nr e s e a r c h e d t h ed a t at y p e ， d a t as t r u c t u r ea n dt h ec a t e g o r yf o r t h e c l u s t e r i n ga l g o r i t h ma l s o h a v eb e e n s u m m a r i z e da n dd i s c u s s e d t h em a i n jo bo ft h i sp a p e rf o c u s e so nt h ei m p r o v e m e n to f t h ec l a s s i c a lh i e r a r c h i c a l c l u s t e r i n ga l g o r i t h m r o c k t h er o c ka l g o r i t h mi s c a p a b l eo fd e a l i n gw i t hs p a r ed a t aw i t hh i g hd i m e n s i o n ，b ye m p l o y i n gt h el i n k c o n c e p t ( n u m b e ro fc o m m o nn e i g h b o r s ) t oe s t a b l i s han e ws i m i l a rm e a s u r e h o w e r v e r , t h er o c ka l g o r i t h mh a st h ed i s a d v a n t a g e so fh i g h c o m p l e x i t ya n dt o om a n y p a r a m e t e r s t h e r e i s a l r e a d ya ni m p r o v e dv e r s i o no fr o c ka l g o r i t h mn a m e d q r o c k i tc o m p u t e st h ec l u s t e r sb yd e t e r m i n i n gt h ec o n n e c t e do fg r a p ha n d e l i m i n a t e st h ep a r a m e t e ro fd e s i r e dn u m b e ro fc l u s t e r s t h i sl e a d st oa ne f f i c i e n t c l u s t e r i n ga l g o r i t h m ，o fw h i c ht h ec o m p l e x i t yi so ( n 2 ) t h i si sn o te f f i c i e n te n o u g h f o rt h ec l u s t e r i n ga l g o r i t h m w i t hr e g a r dt ot h i sp r o b l e m ，t h i sp a p e rp r o p o s e san e w u s e rs e s s i o nc l u s t e r i n ga l g o r i t h mn a m e dh r o c k i ti ss u i t a b l ef o rl a r g e s c a l ed a t a t h ea l g o r i t h mc o n s i s t so ft w op h a s e s t h ef i r s tp h a s ee m p l o y st h ea t o m i cc l u s t e r i n g a l g o r i t h mt or e d u c et h es c a l eo ft h ei n p u td a t a t h es e c o n dp h a s ee x e c u t e st h er o c k c l u s t e r i n gb a s e do nt h er e s u l to ft h ef i r s tp h a s e t h i sk i n do fh y b r i dc l u s t e r i n g a l g o r i t h mh a sl i n e rc o m p l e x i t ya n dc a np r o v i d eg o o dc l u s t e r i n gr e s u l t m o r e o v e r , t h i s a l g o r i t h ma l s oe l i m i n a t e st h ep a r a m e t e ro fd e s i r e dn u m b e ro fc l u s t e r sb yb r i n g i n gi n t h ec o n c e p to fi s o l a t e dc h i l d r e ng r a p h n e x t ，t h i sp a p e rp r o p o s e sap r o t o t y p ed e s i g no ft h ew e bp a g er e c o m m e n d a t i o n i i i 北京工业大学工学硕士学位论文 s y s t e mb a s e do nt h ec l u s t e r i n ga l g o r i t h mh r o c k b a s e do nt h eb sf r a m e w o r ka n d t h ej 2 e es p e c i f i c a t i o n ，t h ed e s i g nc o n s i s t so fw e bl o gp a r s i n gm o d u l e ，w e bl o g p r e p r o c e s s i n gm o d u l e ，u s e rs e s s i o nc l u s t e r i n gm o d u l ea n dw e bp a g er e c o m m e n d a t i o n m o d u l e t h ed e s i g nc a nb ea l s od i v i d e di n t ot w op a r t si n c l u d i n go n l i n em o d u l ea n d o f f i i n em o d u l e f i n a l l y , t h i sp a p e rg i v e sas u m m a r yo ft h ew o r k sh a sb e e nd o n e ，a n dt h e d i r e c t i o n sf o r t h ef i a r t h e rr e s e a r c h k e y w o r d s h r o c k c l u s t e r i n ga l g o r i t h m ；c l u s t e r i n ga n a l y s i s ；w e bl o g m i n i n g ； r e c o m m e n d a t i o ns y s t e m i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：金里擅隰牛 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：虚2 掘 导师签名： 第1 章绪论 1 1 研究背景 第1 章绪论 随着万维网越来越迅速的发展，计算机用户不断地被庞大芜杂的信息海洋 淹没，变得无所适从。大型网站通常包含成千上万的网页，而具体用户感兴趣的 信息可能仅仅包含在少数几个网页之中。对每个用户而言，所需要信息也各不相 同，但目前绝大多数网站只能针对所有用户提供完全一样的服务。针对这些问 题，w e b 日志挖掘技术【l ，2 j 应运而生。 w e b 服务器目志文件记录了所有用户与服务器的交互信息，w e b 日志挖掘技 术通过分析这些日志信息，可以有效地掌握w e b 服务器的运行情况、分析用户 的行为、了解用户群体的需求、维护系统安全、辅助站点维护人员优化站点。用 户的行为在w e b 日志中体现为对页面点击的记录，w e b 日志挖掘可以有效地找出 用户点击页面的序列，这些页面和序列在一定程度上反应了用户的习惯和兴趣。 通过使用聚类分析技术【3 j 可以从这些页面和序列中得到不同的用户群体的访问 习惯和兴趣。这对调整网站的结构，响应每个用户的特定需求，提供个性化服务 一有重要意义。 将w e b 日志挖掘技术和聚类分析技术相结合，可以实现网页的个性化推荐 p j ，基本思路一是把当前访问网站的用户归类到已经识别出的用户类别中，然后 向该用户推荐他所属的用户经常访问的页面，二是得到当前用户访问的页面，判 断这些页面所属的类别，然后从中取出和当前页面相似的页面推荐给用户。 不难看出，聚类分析技术在w e b 日志挖掘和个性化推荐系统中有极为重要 的作用，它能有效地过滤噪声数据和降低数据处理规模，是w e b 日志挖掘其他 算法的预处理步骤。正因为聚类分析技术的重要意义，它已成为数据挖掘技术的 研究热点。基于此背景，本文从聚类分析技术在w e b 日志挖掘中的应用为研究 方向，从传统聚类算法改进的角度，探索聚类分析如何在w e b 日志挖掘中更好 的应用，以提高网页的个性化推荐。 1 2 国内外研究现状 对已有聚类算法的改进还在进行：付辉【6 】针对目前模糊c 均值聚类算法不适 用于有噪声和样本不均衡等问题，借助改进算法a f c m 和w f c m 的思想，提出另 一种新的聚类算法。覃俊华，张洪伟和赵世政【7 】为了克服传统聚类算法对初始化 敏感的缺点，提出了一种基于增强型遗传算法的模糊聚类方法。它把遗传结束的 准则与传统算法的终止准则有机地结合起来，不仅提高了算法的聚类分析性能， 北京工业大学工学硕士学位论文 也提高了算法的收敛速度。s h i h m i n gp a n 和k u o s h e n gc h e n g s l 针对一些传统聚 类算法需要事先指定聚类个数的问题，提出了一种自动获取聚类数目的聚类模 型。l i p i n gj i n g ，m i c h a e lk n g ，和j o s h u a z h e x u eh u a n g 9 1 针对高维数据聚类的问 题，提出了一种基于熵的加权k m e a n s 聚类算法，该算法通过对数据的每一维度 加权来识别子空间和进行子空间聚类，聚类的目标函数因引入了权重熵而加快了 聚类算法的收敛。 混合聚类算法的研究还在深入：如曾志雄【1 0 l 在综合分析基于划分的k 均值 聚类算法和基于层次的凝聚聚类算法的基础上，借鉴各种混合聚类方法，提出了 一种效率更高和聚类质量更好的分阶段混合聚类算( h c a p ) 。刘志成，钱建刚【l l j 以图论和改进遗传算法为基础，提出了一种求最小生成树的遗传算法。该算法采 用二进制表示最小树问题，并设计出相应的适应度函数、算子以及几种控制策略， 以提高执行速度和进化效率。传统算法一次只能得到一个候选解。用该算法对其 求解，可以在较短的时间内以较高的概率获得多个候选解。l a x m ik a n k a n a l a 和 m n a r a s i m h am u r t y 1 2 1 将c f t r e e ，k d t r e e 和k 最近邻分类方法想结合提出了一 种混合聚类算法。 新的聚类方法不断涌现：张泽洪，张伟【1 3 1 针对许多算法不适合对分类数据 进行聚类的特点，提出了一种基于最长频繁闭项集( l f c i ) 的聚类算法。使用改造 后的频繁模式树，得到每个事务的l f c i ，由于l f c i 的两个重要属性，将l f c i 作 为该事务的描述，从而直接得到聚类结果。m u h a m m e tm u s t a f ao z d a l 和c e v d e t a y k a n a t 1 4 】针对传统商品聚类算法相似关系局部度量的不足，通过重新定义数据 模式语义，提出了一种数据模式和超图聚类模型的聚类算法，算法通过基于数据 模式在全体数据集上的出现次数的全局函数指导聚类过程。r a n af o r s a t i ， m o h a m m a d r e z a m e y b o d i ，m e h r d a dm a h d a v i $ - i ：l a z a d e h g h a r in e i a t 1 5 l ：将h a r m o n y 搜索技术应用于k m e a n 聚类算法，缩短了近似全局最优解的搜寻时间。 1 3 本文研究内容及结构 本文的研究内容如下： ( 1 ) 综述了当前聚类分析技术在推荐系统的应用和聚类算法新的研究内容 和方向。 ( 2 ) 阐述了w e b 日志预处理技术的原理和方法，通过实验验证预处理算法的 有效性。 ( 3 ) 剖析了聚类分析的数学模型和聚类思想，并提出了对传统层次聚类算法 r o c k 的改进算法h r c o c k ，通过实验验证了算法近似线性的执行效率、很好的 聚类效果、噪音去除能力和其适用于大规模用户会话聚类的特点。 ( 4 ) 给出了一个基于用户会话聚类算法h r o c k 的网页推荐系统原型设计， 2 第1 章绪论 详细论述了系统的体系结构、数据库设计、模块设计和工作流程。 论文的结构如下： 第1 章介绍课题背景，研究现状和主要工作：第2 章探讨了w e b 日志预处 理的相关方法技术，为下一章的聚类分析做好数据准备；第3 章深入地研究了聚 类分析技术的理论基础，分析了了常用的几种聚类算法的聚类思想、适用范围和 优缺点；第4 章提出了一种改进的r o c k 聚类算法h r o c k ，并通过试验数据 验证了改进算法的效率和质量；第5 章提出了基于改进聚类算法h r o c k 的网页 推荐系统原型；最后对本文的工作进行了总结和展望。 第2 章w e b 日志预处理技术研究 第2 章w e b 日志预处理技术研究 2 1w e b 日志挖掘概述 w e b 日志【l6 】是指网站服务模块相关活动的各种日志文件。包括访问日志、 引用日志、代理日志和错误日志等文件。这些文件包含了大量的用户访问信息， 如用户访问的i p 地址、访问的u r l 、访问日期和时间、访问方法( g e t 或p o s t ) 访问结果、访问信息量的大小等。这些日志文件分布在服务模块端、客户端、以 及代理服务模块上。日志的格式与服务模块的系统配置有关，常见的有通用日志 格式( c o m m o nl o gf o r m a t ，c l f ) 1 6 ，1 7 1 、扩展性日志格式( e x t e n d e dl o gf o r m a t ) 1 6 ，1 7 】 以及a p a c h e 1 6 ，1 7 】和i i sw 3 cw e b t l 6 ，1 7 1 日志格式。比较完整的日志格式如表2 1 所示： 表2 1w e b 日志格式 t a b l e2 - 1f o r m a to fw e b l o g 域 描述 日期请求页面的时间、日期和时区 客户端i p远程主机的i p 或d n s 入口 用户名远程登陆的用户名 字节发送和接收的字节 服务模块信息包括服务模块名称、p 和端口 请求 u r l 查询 状态返回h t l p 状态标识 服务名用户请求的服务名称 时间开销完成浏览所用的时间 协议及版本传输用的协议及版本 用户代理服务提供者 c o o k i e 标识号 参考页本页的上一页 w e b 日志挖掘【l8 】是w e b 挖掘技术中内容和结构挖掘外的项重要内容，它 通过相关算法在海量的w e b 日志数据中自动分析和探索w e b 日志记录中的规律， 识别出电子商务的潜在客户，增强对最终用户的英特网信息服务的质量和交付， 为站点管理员提供站点结构和性能改进的有效信，也可以为网络用户提供个性化 信息服务。同时，对于w e b 网站，可以通过分析其访问日志，发现潜在的威胁 和漏洞，增强网站的安全性。此外，为提高挖掘的质量，众多研究者将w e b 内 容和结构挖掘与w e b 日志挖掘相结合以挖掘更多有用的信息。w e b 日志挖掘的 主要过程如图2 1 所示： 5 原始日志文件用户会话文件 规则和模式兴趣规m 9 和模式 图2 - 1w e b 日志挖掘的过程 f i g u r e 2 - 1p r o c e s so f w e b l o g m i n i n g ( 1 ) 数据采集【i8 】：w e b 上的使用数据很丰富，收集地点有多处，包括客户 端、h t t p 代理端、w e b 服务模块端、甚至底层网络通路。使用数据的特性与收 集方法相关。w e b 服务模块软件自动记录的w e b 日志是目前最常用的使用数据。 ( 2 ) 数据预处理f ls 】：数据预处理在数据挖掘中占有很重要的位置，它关系 到之后挖掘算法的选取，是挖掘算法能否挖掘出高质量模式的关键，后面将做详 细论述。 ( 3 ) 模式发现【i w ：模式发现是整个w e b 日志挖掘的核心，模式发现的方法 有多种，主要是统计分析和智能分析两大类。统计分析利用统计学的基本技术， 进行一些简单的诸如流量分析、广告效益分析、网站出入口分析等。而智能分析 则是利用现在人工智能领域的各种方法，来挖掘关联规则，对用户进行聚类和分 类，发现用户频繁访问路径等。 ( 4 ) 模式分析l l w ：发现的模式是否有用，以及如何解释模式是模式分析阶 段的主要任务。因为模式发现的结果往往包含许多无用的模式，同时用挖掘算法 挖掘的模式是抽象的这就需要我们结合具体领域知识，进行模式过滤和筛选， 并对其做出合理的解释，同时针对所挖掘得模式，做出相应的对策。 2 2w 曲日志预处理技术 w e b 日志预处理i i ”就是在挖掘前，对w e b 日志进行清理、过滤以及重新组 合的过程。w e b 日志预处理的目的就是剔除w e b 日志中对挖掘过程无用的属性 及数据，井将w e b 日志数据转化为挖掘算法可识别的形式保存。预处理过程输 入的数据有：服务模块w e b 日志、站点拓扑结构图和其它可供选择的信息。输 出的数据有：用户会话文件、事务文件和页面分类等，对日志进行预处理的结果 直接影响到挖掘算法产生的规则和模式，所以预处理技术也成为数据挖掘中重要 翱目目w目 c国粤 第2 章w e b 日志预处理技术研究 的研究方向。w e b 日志预处理一般包括数据清理、用户识别、会话识别、路径补 充、事务识别几个阶段，如图2 2 所示： 图2 2w e b 日志预处理过程 f i g u r e2 - 2p r o c e s so fw e bl o gp r e p r o c e s s i n g 2 2 1 数据清理 数据清洗1 1 9 j 的目是删除w e b 日志中与挖掘目的不相关的数据和记录，为后 面的建立用户会话和事务识别建立数据基础，因为w e b 服务模块记录了很多与 用户意图不相关的信息。由于w e b 日志挖掘主要是对w e b 用户使用行为的研究， 所以只有利用准确描述用户浏览行为的数据进行挖掘，才能发现正确的规则和模 式。用户的浏览行为可以通过用户的请求来准确描述，而w e b 服务模块响应用 户的该请求却有多个日志记录，一般来说，把用户对h t m l 的请求作为用户的该 次请求，所以数据清理阶段通过检查u r l 的后缀删除不相关的数据。例如：将 日志中文件后缀名为g i f 、j p e g 、j p g 、g i f ,j p e g 、j p g 、 s w f 、c $ s 、j s 和 m a p 的请求项删除。另外，后缀名为c g i 的脚本文件也应被删除。实际的系统 应用中一般使用一个缺省的后缀名列表帮助删除无关请求，列表可以根据正在分 析的站点类型进行修改，例如，对一个主要包含图形文档的站点，日志中的g i f 和j p e g 文件可能代表了用户的显式请求，此时就不能将图形文件删除。这些 对w e b 日志数据的清理工作就由数据清理步骤完成。 2 2 2 用户识别 用户识别【1 9 , 2 0 要求识别出每个访问网站的用户，这一任务因为本地缓存、公 司防火墙和代理服务模块的存在变得复杂。一般会遇到下面几类问题： ( 1 ) 单个i p 对多个服务模块用户访问会话：i s p 利用p r o x y 代理为用户提供 服务，统一i p 访问一个w e b 站点时可能是不同的用户。 ( 2 ) 多个i p 对单个服务模块用户会话：有些i s p 对来自同一个用户的请求， 会随机分配若干个i p 中的一个给用户，这样一个用户进程会有不同的i p 。 ( 3 ) 多个i p 对单个用户：从不同机模块上访问w e b 的同一个用户因为不同 7 北京工业大学工学硕士学位论文 的进程而拥有不同的i p ，这也使得追踪同一个用户变得复杂。 ( 4 ) 多个服务模块进程对单个用户：这种情况发生在用户打开多个浏览模块 窗口，同时对同一个站点的不同部分进行访问。 ( 5 ) 单客户端对多用户：如家庭，很多人共用一台机模块。 对这个问题的通常解决方式是通过一些启发式规则帮助识别用户。这些启发 是一个总的原则是：若没有证据表明是不同的用户，就认为是同一用户。根据这 个原则，可以得出以下启发规则： ( 1 ) 不同的i p 代表不同的用户。 ( 2 ) 如果i p 相同，则不同的操作系统或浏览模块代表不同的用户。 ( 3 ) 如果i p 和操作系统和浏览模块都相同则由引用页区别，如果引用页为空 的话，则认为是一个新的用户；若引用页不空且多个用户包含此页，则把它划为 时间上最近访问用户。 需要注意的是，识别用户是一个很复杂的过程，上面这启发式规则仅仅只能 帮助我们识别用户，但并非就能很准确的识别出用户。例如相同i p 地址的用户 若在同样操作系统和同样类型的浏览模块上，并且请求的页面集合也大致相同， 则就很容易混淆为同一个用户。另外用户使用两种类型的浏览模块，或者是没有 使用站点的链接结构而是直接输入u r l ，则很容易认为是多个用户。大多数网 站为了能更好的识别用户，都采取了一些用户跟踪机制。常用的用户跟踪技术有： c o o k i e 和w e bb u g 。c o o k i e 是由w e b 服务模块自动生成的字符串，并有w e b 服务模块发送给浏览模块，浏览模块将这一字符串以文本方式保存在本地硬盘 上。对同一站点而言，每个用户对应一个唯一的c o o k i e 。当用户首次访问网站 时，w e b 服务模块将c o o k i e 发给用户，并将之保存在用户计算机中，用户在此 访问该站点时，浏览模块将对应于该站点的c o o k i e 值发送给w e b 服务模块， w e b 服务模块根据用户的c o o k i e 值自动识别用户。对于这些跟踪方法的使用， 受到了用户以及专家的非议。对用户而言，希望享用网站提供完善的服务，但不 希望远程服务模块跟踪监视自己的网络行为，自己的隐私不被侵犯。而对于网站 而言，希望能很好的识别用户的身份，以改善服务质量。 2 2 3 会话识别 会话【1 9 】是指用户在一次访问网站期间从进入网站到离开网站所进行的一系 列活动。在跨度时间较大的w e b 服务模块日志中，用户可能多次访问了该站点， 会话识别的任务就是把属于同一用户的同一次访问请求识别出来。文献 1 9 给出 日志和会话的形式化定义。 定义2 1w e b 服务模块日志可以看成是按照时间邮戳排序的集合 l = 1 1 1 1 2 ，t ，厶) ( 1 f 刀) ，l l l = 以表示日志集合包含的元素数目，经过用户 8 第2 章w e b 日志预处理技术研究 识别之后日志的纪录= u s e r i d ，u r l ，t i m e ，r e f e r ) 。此处的u s e r i d 是经过识别用户 后赋予每个用户的唯一识别码。 定义2 - 2 当三元组，= u s e r d , s ，( ( ( z r ，如鸺2 ：均白) ，( 洲，l j i i r n g , l j 粥白) ) ( 1 f 歹，7 j ，三) ，满足，f u s e r i d = 6 u s e r i d ，l r t i m e l j t i m e 时，被称为会话。 为构造后的会话标示。l e n g h t ( r ) 表示会话，的长度，即会话，所包含的页面请 求数目。 文献 2 1 总结了常用的4 种方法用于会话识别： ( 1 ) 给定用户在整个站点的停留时间一个上界0 ，如果超过这个阈值则认为 新的会话开始。设，0 为会话初始页的时间戳，同一用户的一个u r l 请求的时间，如 果满足t - t o 9 ，则被加入当前会话，第一个满足岛+ 臼f 的页面成为下一个会 话的初始页。一般矽取3 0 分钟。 ( 2 ) 给用户一个页面停留时间阈值出，如果2 个连续请求的时间间隔没有超 过这个值f ，这属于同一会话，否则分属于两个会话。岔一般取1 0 分钟。 ( 3 ) 利用用户访问历史和引用页来划分，如果一个用户的请求不能通过引用 页上的链接进入，则很可能属于另一个会话。即当前请求的引用页在前面访问过 的页面中没有出现，则是一个新的会话开始。 ( 4 ) 最大向前参照引用模型，即在一个用户会话里不会出现用户先前已经访 问过的页面。如果用户在向前浏览到一个网页时，按下了“返回”按钮，则表示当 前会话结束，一个新的会话开始。 文献 2 2 1 给出了一种混合会话识别算法，其思想如下：首先利用会话的时间 特性来进行区分，这里设定会话时间阈值0 为3 0 分钟。如果大于这个值则认为 一个新的会话开始了，否则再根据用户的浏览特性和页面之间的连接结构确定最 终的会话集，假设同一用户依次发出相邻的两个请求p 和g ( 其中p 属于会话 s ) ，p 和f g 分别表示页面请求p 和q 的时间戳( fp b a r c b 1 0 a b r - c c r b c r a a r a b r - b c r 一 c 图4 1 数据点邻居数与连接的关系 f i g u r e4 1r e l a t i o n s h i pb e t w e e n n u m b e ro fn e i g h b o r sa n dn u m b e ro fl i n k s 依照聚类的定义，有较多连接的簇是好的聚类簇。所以，聚类的目标函数应 该在最大化同一聚类簇中任意两个数据点名，e 间连接z f 础( 0 ，p ，) 的同时，最 北京工业大学丁学硕士学位论文 小化属于不同聚类簇的任意两个数据点乞，e 间连接，f 舭( 名，e ) 。由此，得到将 数据集划分为k 个聚类簇的目标评价函数如下： 五玉木巴篆q 攀斧 睁5 ， 其中c j 表示第i 个包含数据点数为- 的聚类簇。该聚类目标评价函数互的合 理性可以解释如下：既然聚类的目标是最大化所有数据点对，p 间的连接 f f 放( 乞，只) ，那么，这样一个简单的计算所有数据点对间的连接的和的目标评价 函数，加七( 乞，只) 应该满足要求。尽管这个目标评价函数能够确保所有具有 f = 1 名只ec i 大量连接的数据点划分到同一个聚类簇中，但它无法阻止所有的点划分为一个 簇。也就是说它无法强制使所有具有较小连接的数据点被分到不同的聚类簇。 为了克服这个缺点，在目标评价函数蜀中，簇g 中数据点的连接总数除以 期望连接，并乘以g 包含的数据点数吩。g 的期望连接的估计值为砖+ 2 朋，其 中函数p ) 是依赖于具体的数据集，函数( 护) 具有这样一个特性：c l 中每一个 数据点有大约口个近邻。如果确实存在这样一个函数厂，我们可以假设c f 之 外的数据点对c j 内的连接的贡献可以忽略不计，g 中的每一个数据点贡献的连 接为砰刚。因而，我们得到c 期望连接的估计值为一+ 2 ，。在评价函数互中除 以这个期望连接的估计值可以很好地阻止具有较小连接的数据点被聚为一个簇， 因为这样将导致期望的连接比实际的连接大，引起评价函数值的下降。 当然，得到函数f ( o ) 的一个精确估计值不是一件容易的事。然而，实验已 经表明即使不精确但合理的估计也可以使聚类算法很好的工作。深入地讲，在目 标评价函数e 中，所有的簇的连接除以耐+ 2 朋规范化，对f ( o ) 的估计误差将均 匀地分布在每一个簇中，对每一个聚类簇的影响都是相同的，不会针对某一个簇。 一般而言，对厂( 臼) 的一个合理估计通常取为若号。它基于一个这样的假设： c 包含的交易事务数据中，事务的大小f 是近似的，并且均匀地分布在肌个交易 商品中( 也即分类属性) 中。则存在一个常数c 1 ，使c 中的事务数据个数近似为 2 4 第4 章一种改进的r o c k 聚类算法h r o c k ( 了) ，并且使q 中那些与一个特定事务z 的相似度超过阈值秒的事务数据个数 近似为( 等) ( 也即与事务z 至少有为个商品属性相同) 。因此，g 中的一个交 易事务数据的邻居个数近似为刀了i - 0 ，且厂( p ) = 1 1 - _ + _ 0 口_ o 。不难看出，当乡= i 时，交 易事务数据的邻居个数近似为刀? 州，且厂( p ) = ，。不难看出，当乡= 时，交 易事务数据的邻居是它自己，期望连接是啊( 因f ( o ) = 0 ) 。当秒= 0 时，每一个交 易事务数据的邻居是其他交易事务，期望连接是霄( 因厂( 目) = 1 ) 。 4 1 4 聚类方法 4 1 4 i 算法流程 算法包括三个阶段，从数据库采样之后，在样本上采用基于连接的层次聚类 算法进行聚类，最后，利用采样聚类的结果，把数据库中剩余的数据分配到适合 的聚类簇，算法的过程如图4 2 ： 图4 - 2r o c k 聚类算法过程 f i g u r e4 - 2p r o c e s so ft h er o c kc l u s t e r