（计算机应用技术专业论文）基于组织协同进化的web日志挖掘.pdf

摘要 摘要 i n t e r n e t 的迅速发展，在给人们带来丰富信息和极大便利的同时，也随之产 生了许多的问题，个性化的信息服务和构建智能化w e b 站点便是其中之一。直 接或间接地解决这个问题的途径之一就是将数据挖掘技术应用于w e b 服务器日 志的挖掘。本文研究了w e b 日志挖掘中的相关技术，并在组织进化算法的基础 上，提出了二种用于w e b 日志挖掘的算法。 本文的主要研究工作如下： 1 组织协同进化分类算法( o r g a n i z a t i o n a lc o e v o l u t i o n a r ya l g o r i t h m f o r c l a s s i f i c a t i o n 。o c e c ) 与现有遗传算法的运行机制不同，o c e c 算法中的个体不需 要进行编码，且个体以组织的彤式进行进化，为此定义了新的适合于组织操作 的进化算子；另外，o c e c 的进化操作直接作用予数据而不是规则，进化结束后 再从组织中提取规则。本文基于o c e c 的以上特点，提出了组织协同进化的w e b 日志挖掘算法。该算法针对w b b 日志挖掘的特点，改进了o c e c 中的合并算子， 并把增减算子和交换算子中的常数参数修改为百分数。仿真对比实验表明，该 算法不仅有效可行，丽且还有较快的收敛速度。 2 在组织进化算法的基础上，提出了基于组织多层次进化的关联规则挖掘 算法。该算法将初始数据以自由态组织形式加入进化种群中，进化种群每次进 化后，把包含相同属性集合的组织加入最优种群中；并同时用本文定义的聚合 算子对最优种群进行进化。把其中相同属性集合相等的不同组织聚合为一个更 大的组织；进化结束后，再从最优种群各组织的相同属性集合中提取出关联规 则。该算法避免了计算大量无效频繁项的支持度，而且进化种群和最优种群同 时进化，因此有较快的进化速度。仿真对比实验表明，该算法不但加快了挖掘 关联规则的速度，而且还保持了较高的有效关联规则提取率 关键词；w e b 日志挖掘组织进化相同属性用户分类关联规则 a b s t r a c t a b s t r a c t r e l e v a n tt e c h n o l o g ya b o u tw e bl o gm i n i n gh a sb e e ns t u d i e di nt h i sp a p e r b a s e do n o r g a n i z a t i o n a le v o l u t i o n a r ya l g o r i t h m t w ok i n d so f a l g o r i t h m s a 糟 p r o p o s e d i nt h i sp a p e r r n l em a i nr e s e a r c hw o r ka n dr e s u l t sa r ea sf o l l o w s ： 1 t h e0 c e c ( o r g a n i z a t i o n a lc o e v o l u t i o a a r ya l g o r i t h mf o rc l a s s i f i c a t i o n ) i s d i f f e r e n tf r o mt h eg ab a s e de l a s s i f i e a t i m e t h o d sa v a i l a b l e t h ci n d i v i d u a li n o c e cd o e sn o tn e e dt ob ec o d e d ，a n dt h ei n d i v i d u a li se v o l v e di no r g a n i z a t i o n s s o t h r e ee v o l u t i o n a r yo p e r a t o r s ，a d da n ds u b t r a c to p e r a t o r , e x c h a n g e o p e r a t o ra n du n i t e o p e r a t o ra r ec o n s t r u c t e di no c e c t h ee v o l u t i o n a r yo p e r a t i o n so fo c e c d on o ta c t o nr u l e s ，b u to nt h eg i v e nd a t ad i r e c t l y b a s e do nt h ec h a r a c t e r i s t i c so ft h eo c e c ， o r g a n i z a t i o n a lc o - e v o l u t i o a r ya l g o r i t h mf o rw e bl o gm i n i n g i sp r o p o s e di nt h i sp a p e r n 圮u n i t eo p e r a t o ri si m p r o v e d 。a n dt h ep a r a m e t e r so fa d da n ds u b t r a c to p e r a t o r , e x c h a n g eo p e r a t o ra m o d i f i e dt op e r c e n ti nt h i sa l g o r i t h m i ti ss h o w nt h a tt h i s a i o g r i t h mi se f f e c t i v ea n da v a i l a b l e 。a n di t sc o n v e r g e n ts p e e di sf a s t 、】l ，i mc o m p u t e r s i m u l a t i o n s 2 b a s e do no c e a ，a m u l t i p l e - l e v e lo r g a n i z a t i o n a le v o l u t i o n a r ya l g o r i t h m f o ra s s o c i a t i o nr u l e s m i n i n g ( m l o e a ) i sp r o p o s e d i nt h i s p a p e r a n e w e v o l u t i o n a r yo p e r a t o rn a m e d a sg a t h e ro p e r a t o ri sc o n s t r u c t e d , as a m ea t t r i b u t es e t f o r ma n dt w o p o p u l a t i o n s 黜d e f i n e di nt h i sa l g o f i t l m a n 埒a l g o r i t h mr e g a r d se a c h o fd a t aa sa no r g a n i z a t i o n 贰t h eb e g i i ：m i n g 。t h e nj o i na l lo r g a n i z a t i o n si np o p u l a t i o n 4 t h r o u g ht h ee v o l u t i o no fp o p u l a t i o na ，t h eo r g a n i z a t i o n sw i t hs a u l ea t t r i b u t es e t c a nb ef o u n do 峨t h e nt h e s eo r g a n i z a t i o n sa m o v e dt op o p u l a t i o n 且1 1 1 ed i f f e r e n t o r g a n i z a t i o nw i t l lt h eu n i f o r ms 出 f l ea t t r i b u t es e t si np o p u l a t i o nb w i l lm e r g ei n t oa n e w g r e a t e ro r g a n i z a t i o nb yu s i n gt h en e wg a t h e ro p e r a t o ro nt h eo r g a n i z a t i o n so f p o p u l a t i o nb a f t e re v o l v i n g , a s s o c i a t i o nr u l e sc 肌b ee x t r a c t e df r o mt h e 戳嘲e a t t r i b u t es e t so fo r g a n i z a t i o n si np o p u l a t i o nb t h i sa l g o r i t h md o e sn o tn e e dt o c a l c u l a t et h es u p p o r tv a l u e so f m a n yi n v a l i dl a r g ei t e m s e t s ，a n dt h ep o p u l a t i o n aa n d p o p u l a t i o nb a e v o l v e dt o g e t h e r , s oi t sr u n i n gs p e e di sf a s t e r i ti ss h o w nt h a tt h e p r o p o s e da l g o r i t h m h a sf a s t e rc o n v e r g e n t 印d ，a n da c h i e v e sh i g h e rd i s t i l l e dr a t eo f r u l e sw i t hc o m p u t e rs i m u l a t i o n s k e y w o r d s ：w e bl o gm i n i n g ，o r g a n i z a t i o n a lc o e v o l u t i o n a r ya l g o r i t h m ， s a m e a t t r i b u t e ，u s e rc l a s s i f i c a t i o n ，a s s o c i a t i o nr u l em i n i n g 声明 y6 9 5 5 0 5 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技 大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布 论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文( 保 密的论文在解密后遵守此规定) 。 本人签名： 导师签名： 日期兰! ! ：兰：全芷 日期 第一章绪论 1 1 1 研究背景 第一章绪论 1 1 论文的研究背景及意义 随着i n t e r n e t 作为传播各种信息的媒体迅速膨胀，许多机构的计算机系统 经过多年的积累产生了大量的历史数据。而巨量j 约数据本身不是信息，在其 背后隐含羞丰富的知识，这些知识才是我们最需要的。但是，目前的数据库技 术可以实现数据的高效查询、统计等功能，而通过对这些数据进行分析而得到 进一步隐含信息的能力则显得不足。 知识发现( k d d ) 就是在这样的背景下出现的，结合了数据库技术和人工智 能技术，利用数据库管理系统来存储数据。用机器学习方法来分析数据，挖掘 历史数据背后的隐含知识【1 1 。伴随着k d d 的出现，数据挖掘 d a t am i n i n g ) 也越 来越受到瞩目。在一定程度上，知识发现和数据挖掘是同义词，而一般情况下。 两者是有区别的。许多研究人员认为数据挖掘只是知识发现的一个重要组成部 分，而知识发现则是从大量历史数据中发现知识的完整过程闭 近年来，由于i n t e m e t 的广泛应用和w w w 的快速发展，如何在浩如烟海的 w w w 数据中找到需要的信息比传统的数据库领域更加复杂、困难w e b 挖掘 的困难在于：传统的数据挖掘是面向关系数据库的，或是面向数据仓库的，处 理的数据具有完整的结构，但w w w 数据是无序的、非结构的或半结构化的， 并且存在大量的冗余和噪声哪目前，该研究领域主要集中在t 用户浏览模式 识别，搜索引擎的设计，文件自动分类技术，关键词的自动提取。半结构化信 息的知识发现等 4 1 。 在从多的w e b 数据挖掘研究领域中，w e b 日志挖掘由于对于w e b 网站的结 构优化和w e b 页面内容的重组都起到重要作用，并直接会对w e b 网站产生经济 效益，因此对这个领域的研究也日渐增加。w e b 日志挖掘是将传统的数据挖掘 技术应用在w e b 访阋日志数据上从而发现用户访问模式的技术i ”。 1 1 2 研究意义 互联网的发展，使分析互联网背后的用户行为，成为获取用户行为偏好的 必要手段。对w e b 日志挖掘的研究将会对下面几方面的研究与法展提供便利 忙m ： 1 为用户提供个性化服务 根据用户访问历史。动态的向用户推荐商品，在电子商务嘲站上进彳亍商品 一2 基于组织进化的w e b 日志挖掘算法研塞 营销，具有很大的商业价值。 2 提高系统效率 我们知道，随着哪的信息量的增加，影响网站用户满意度的主要因素 除了w e b 内容，它的服务效率也很重要。通过w e b 日志数据挖掘，可以提供网 站服务效率全方位的信息。从而有助于找到平衡服务器负载，优化传输，减少 拥塞的方法，缩短用户等待时间，提高系统效率和服务质量。 3 提高网站结构设计的性能 w e b 结构的复杂度在飞速地发展着，因此。w e b 站点和w e b 服务器的设计 和维护难度也在增加。通过w e b 日志数据挖掘提供的用户访问信息，可以帮助 网站设计者改进网站结构。 4 电子商务网站确定用户群类 通过分析市场销售数据可以识别顾客的购买行为模式，帮助确定电子商务 商品在w e b 页面上的布局排放，向用户有效地摊荐商品，以达到扩大商品销售 量的目的。同时，也有助于找到顾客访问网站的规律，用来制定相应的营销策 略。 5 网络安全 通过分析网上银行、网上商品交易用户日志，可以防范黑客攻击和恶意诈 骗等。 6 网站评价 如何有效评价一个网站的受欢迎程度是许多业界人士所关心的一个问题， 通过w e b 日志数据挖掘可以获取用户对网站认识、使用情况的第一手资料，为 网站评估提供依据。 1 2w e b 日志挖掘的研究现状 从研究的角度，现有的基于w 曲服务器日志数据的研究大致可以分为三个 方向帆：分析系统性能；改进系统设计； 理解用户意图由于它们针对 的功能不同，采取的主要技术也不同。 以分析系统性能为目标的研究，主要是从统计学的角度，对日志数据项进 行多种简单的统计如频繁访问的网页，单位时间访问数，访问数据量随时间 分布图等 s l 。目前已有的绝大多数商用及免费的w e b 日志分析工具都属于这种 类型，这些工具的用户一般是w e b 服务器的管理者通过这些统计数据管理 员可以对w e b 服务器作相应的调节，如缓冲设置，镜像站点设置等。更进一步， 如果将w e b 日志视做关系表，利用数据挖掘技术还可以发现许多有价值的信息， 如利用关联规则可能发现用户所在地区与某被访问页面间的关系o i 。此外，许 第一章绪论 多数据挖掘的技术如时间序列分析，多层关联规则和分类技术等亦可用于w e b 日志的分析，帮助管理员发现用户的访问规律【l l 】。 以改进系统设计为目标的研究，由于w e b 服务器的设计与建设的主要复杂 性是它能随着设计者及用户的变化而不断自我调整，研究如何以日志数据为依 据，对w e b 服务器的组织和表现形式进行自动或半自动调整，从人机交互和软 件a g e n t 领域提出a d a p t i v e w e bs i t e 的概念，它在技术手段上与数据挖掘技术有 某些交叉和重型”】。 以理解用户意图为日标的研究，一般是通过算法从w e b 服务器日志中找出 频繁的用户访问路径或访问模式i i 。这些都是为了从大量的w e b 日志数据中找 出一定的模式和规则。 目前。w e b 日志挖掘方法主要有两种c h e r t 等人首先将数据挖掘技术应用 于w e b 服务器日志文件，以期发现用户浏览模式【i j 他们提出了最大前向引用 序列m f r 的概念，并用它将用户会话分割成一系列的事务。然后采用与关联规 则相似的方法挖掘频繁访问路径。h a r t 等人则根据w e b 日志建立数据立方体， 然后对数据立方体进行数据挖掘和o l a p ”。 w e b 日志挖掘是一个较新的研究领域，具有广阔的发展和应用前景。应该 指出的是，面对日益增加的商业需求，w e b 日志挖掘技术还有许多问题需要解 决，有待这一领域的研究者深人研究。将来很有用的几个研究方向是如下f f q 。 1 用户访问模式库的动态维护和更新、模式( 知识) 的评价体系和评价方法； 2 分类在电子商务市场智能提取中的研究； 3 关联规则和序列模式在构造自组织站点方面的研究l 4 智能站点服务个性化和性能最优化的研究： 5 挖掘算法在海量数据挖掘时的适应性和时效性研究； 6 w e b 日志挖掘中内在机理及新的挖掘体系和结构的研究。 1 3 本文的内容与结构 本文主要研究了w e b 日志挖掘的问题。并在刘静等人提出的组织进化算法 的基础上，提出了组织协同进化w e b 日志挖掘算法、基于组织进化的关联靓刚 挖掘算法和基予组织多层次进化的关联规则挖掘算法。 本论文的内容安排如下： 第二章主要介绍了w e b 日志挖掘的基本理论。主要包括了w e b 日志挖掘的 概念、w e b 日志挖掘的数据分析、数据预处理过程和几种w e b 日志中的事务模 型。 第三章主要介绍了组织进化计算的思想。分别讲述了组织进化算法，和组 一4 基于组织进化的w e b 日志挖掘算法研究 织协同进化分类算法。 第四章介绍了组织协同进化w e b 日志挖掘算法的思想，和算法的描述，并 进行了仿真实验。 第五章介绍了基于组织进化的关联规则挖掘算法的思想，和算法的描述。 并进行了仿真实验。 第六章介绍了基于组织多层次进化的关联规则挖掘算法的思想，和算法的 描述。并进行了仿真实验。 最后总结了全文。 第二章w e b 日志挖掘 2 1 1 数据挖掘 第二章w e b 日志挖掘 2 1 数据挖掘和w e b 挖掘技术 数据挖掘也被称作k d d ，即数据库中的知识发现，是一种决策支持过程， 它主要基于越、机器学习、统计学等技术，高度自动化地分析企业原有的数据， 作出归纳性的推理，从中挖掘出潜在的模式，预测客户的行为，帮助企业的决 策者调整市场策略、减少风险、作出正确的决策”l 。数据挖掘的对象不仅是数 据库，也可以是文件系统或其他任何组织在一起的数据集合l l ，例如，本文研 究的挖掘对象就是w w w 信息资源。数据挖掘豹结果表示为概, 念, ( c o n c e p t s ) 、规 则( r e l e s ) 、规律g u i a r i 船s ) 、模式( p a t t e r n s ) 、约束( c o n s t r a i n t s ) 、可视化 ( v i s u a l i z a t i o n s ) 等形式【1 9 1 ，这些知识可以直接提供给决策者，用以辅助决策过程： 或者提供给领域专家，修正专家已有的知识体系；也可以作为新的知识转存到 应用系统的知识存储机构中，如专家系统( e x p e r ts y s t e m ) 、规则库( r u l eb a s e ) 等 【卿。 数据挖掘是一个完整的过程，该过程能够从大型数据库中挖掘先前未知的、 有效的、实用的信息，并利用这些信息做出决策或丰富知识m 1 。其流程如图2 1 所示： 图2 1 数据挖掘流程 1 数据的选择：搜索所有与业务对象有关的内部和外部数据信息，并从中 选择出适用于数据挖掘应用的数据。 2 数据的预处理：研究数据的质量。为进一步的分析作准备，并确定将要 进行的挖掘操作的类型 3 数据的转换：将数据转换成一个分析模型。这个分析模型是针对挖掘算 !基于组织进化的w e b 日恚挖掘算法研究 法建立的。建立一个真正适合挖掘算法的分析模型是数据挖掘成功的关键。 4 数据挖掘：对所得到的经过转换的数据进行挖掘。首先根据所需要解决 的问题建立合适的数据挖掘模型，然后利用已知数据对模型进行训练和测试， 并应用该模型得到挖掘结果。 5 结果分析：解释并评估结果。其使用的分析方法一般应作数据挖掘操作 而定，通常会用到可视化技术。 6 知识的同化：将分析所得到的知识集成到业务信息系统的组织结构中 去，应用得到的知识解决问题。 由于数据挖掘源于多个学科，是一个交叉学科领域因此数据挖掘研究产 生了大量的不同类型的数据挖掘系统从不同的视角看，数据挖掘系统有各种 分类，主要有以下几方面矧。 1 根据挖掘的知识类型分类 这种分类方法将数据挖掘系统分为：关联规则( a s s o c i m i o n ) 、分类 ( c l a s s i f i c a t i o n ) 、特征化( c h a r a c t e r i z a t i o n ) 、聚类分析( c l u s t e r i n g ) 、演变分析 ( e v o l u t i o n ) 、孤立点分析( o u t l i e r ) 、偏差分析( d e v i a t i o n ) 等。 2 根据挖掘知识的抽象层次分类 这种分类方法将挖掘系统算法分为原始层( p r i m i t i v el e v e l ) 的数据挖掘、高 层抽象层饵i g hl e v e l ) l 拘数据挖掘、多层次( m u l t i p l el e v e l ) 的数据挖掘 3 根据挖掘的数据库类型分类 基于数据库的分类有：关系茬# ( r e l a i o n a l ) 、事务型( t m a s a c a o 捌) 、面向对 象型( o b j e c t - o r i e n t e d ) 、空间型( s p a t i a l ) 、时间型( t e m p o r a l ) 、文本型o e x t u a l ) 、 多媒体似t l l t i m e m a ) 、异质( h e t e r o g e n e o u s ) 数据库、遗留型( l e g a c y ) 和w w w 数 据挖掘系统等。 4 根据采用的技术分类 最常用的数据挖掘技术有；人工神经网络( a r t i f i c i a l n e u r a ln e t w o r k ) 、决策 树( d e c i s i o nt r e e ) 、遗传算法( g e n e t i ca l g o r i t h m ) 、最近邻技术( n e a r e s tn e i g h b o r ) 、 规则归纳( r u l ei n d u c t i o n ) 、可视化0 f m u a l i z a t i o n ) 。 2 1 2w e b 挖掘 w e b 数据挖掘是从w w w 资源上抽取信息的过程，是对w e b 资源中蕴含的、 未知的、有潜在应用价值的模式的提取，它反复使用多种数据挖掘算法从观测 数据中确定模式或合理模型，是将数据挖掘技术和理论应用于对w w w 资源进 行挖掘的一个新兴的研究领域。从理论上讲，数据挖掘的各种技术和理论都可 以直接或间接地应用于w e b 数据挖掘，然而由于w w w 资源的异构性、多样性、 第二章w e b 日志挖掘 分布的广泛性，特别是其数据的半结构化特性，导致了w e b 挖掘和普通大型数 据库挖掘有很大不同。 一般地，w e b 数据挖掘的基本原理跚可用图2 2 所示的处理过程表示。 图2 2w e b 效据挖掘的基本原理 1 目标数据集：根据用户要求，从w e b 资源中提取的相关数据，w e b 挖掘 将主要从这些数据中进行数据提取 2 预处理：从目标数据集中除去明显错误的数据和冗余的数据，进一步精 减所选数据的有效部分，并将数据转换成为有效形式，以使数据挖掘更有效。 3 模式发现t 根据任务要求，选择合适的数据挖掘算法( 包括选取合适的 模型和参数) ，寻求感兴趣的模型并用一定的方法表达成某种易于理解的形式 4 模式分析：对发现的模式进行解释和评估，必要时需要返回前面处理中 的某些步骤以反复提取最后，将发现的知识以用户能理解的方式提供给用户， 并试用这些信息。 目前，在该研究领域中，根据挖掘对象的不同，w e b 挖掘可以分为三类汹l ： w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘。w e b 结构挖掘是运用数据挖掘 技术来重建w e b 站点的结构w e b 使用挖掘是通过挖掘相应站点的日志文件和 相关数据来发现该站点上的浏览者和顾客的行为模式。 1 w e b 内容挖掘 w e b 内容挖掘是指对w e b 页面内容进行挖掘，从w e b 文档的内容信息中 抽取知识内容挖掘又分为文本挖掘( 包括t e x t ，h 曲l 等格式) 和多媒体挖掘 ( 包括i m a g e ，a u d i o , v i d e o 等媒体类型) w e b 内容挖掘的重点是页面分类和聚类。 w e b 页面的分类是根据页面的不同特征，将其划归为事先建立起来的不同的类。 w e b 页页面的聚类是指在没有给定主题类别的情况下，将w e b 页面集合聚成若 干个簇，并且同一簇的页面内容相似性尽可能大，而簇间相似度尽可能小 2 w e b 结构挖掘 w e b 结构挖掘是从w w w 的组织结构和链接关系中推导知识它不仅仅局 限于文档之间的超链结构，还包括文档内部的结构、文档l m 中的目录路径的结 基于组织进化的w e b 日志挖掘算法研究 构等。由于文档之间的互联，w w w 能够提供文档内容之外的有用信息。利用这 些信息，可以对页面进行排序，发现重要的页面。w e b 在逻辑上可以用有向图 表示出来，页面对应图中的点，超链按对应图中的边。通过把w e b 表示为有向 图，可以得到从一个站点的主页到它的任意一个顶点的最短路径。 3 w e b 日志挖掘 w e b 日志挖掘是指从用户的访问纪录中提取感兴趣的模式。当个人浏览 w e b 网站时，服务器会产生三种类型的日志文件嘲ls e r v e rl o g s 。e r r o rl o g s ， c o o k i e l o g s ，记录了关于用户访问和交互的信息w e b 日志挖掘正是对这三种 日志文件进行挖掘，从而发现用户的访问模式、相似用户群体、频繁路径等知 识。w e b 日志挖掘方法可分为基于w e b 事物的方法和基于数据立方的方法。前 者是将用户会话划分成事务序列，然后采用数据挖掘的方法挖掘频繁路径等知 识，后者则将w e b 日志组织成数据立方用于数据挖掘和o l a p ，w a p m i n e 采 用的是第一种方法。分析这些数据可以帮助理解用户的行为，从而改进站点的 结构，为用户提供个性化的服务。 2 2 】数据源 2 2w 曲日志挖掘的数据分析 w e b 日志挖掘的对象是w e b 上的信息，特别是w e b 上的访问日志、用户 信息以及和应用相关的w e b 内容在w e b 日志挖掘中。数据可以在服务器端、 用户端、代理服务器端或者是应用所需的数据库这些数据并不仅仅意味着存 放于不同的位置，其中还包含了w e b 世界中不同的浏览模式，例如单用户单站 点模式，单用户多站点模式，多用户单站点模式，多用户多站点模式。通常， 用户端的日志包含了单用户多站点的浏览模式，服务器上的日志则意味着多用 户单站点模式，代理服务器上的日志是多用户多站点模式的典型代表闭。 1 服务器端数据 w e b 服务器目志是w e b 日志挖掘中一个重要的数据源。它清楚地记录了网 站用户的访问浏览行为。这些日志文件通常采用普通日志格式( c l f ) 或扩展普通 日志格式( e c l f ) 。表2 1 给出了一个扩展通用日志格式嘲。 第二章w e b 日志挖掘 表2 1 服务器日志格式 f i e l d d e s c r i p t i o n d a t e d a t e ，t i m e , t i m eo f r e q u e s t c l i e n ti p r e m o t eh o s ti pa n d o rd n s e n t r y u s e rn s i l er e m o t e l o g n a m e o f t h eu s e r b y t eb y t e st r a n s f e r r e d s e r v e r s e r v e r n a m e ，i p a d d r e s sa n d p o r t r e q u e s t u r l q u e r y a n ds t e m s t a t u s h t t p s t a t l bc o d er c t o n l e dt ot h ec l i e n t s e r v i c en a m e r e q u e s t e d 辩r v i c e f l a m e r e f e r r e rp r e v i o u s p a g e p r o t o lv e r s i o nv e r s i o no f u s e dt r a n s f e r p r o t o c o l u s e r a g e n t s e r v i c e p r o v i d e r 9 其中，用户口地址是向w 曲服务器发出请求的机器的i n t e m e t 地址。这个 地址可能是用户机器的地址，也可能是用户使用的代理服务器的地址日期和 时间表示w e b 服务器收到请求的日期和时阔。请求项表示了用户使用的协议和 统一资源标识u r i ( u n i f o r m r e s o u r c ei d e n t i f i e r ) 请求服务包括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 d 岫则是仅获得一个对象的h t r p 头，u l u 是w e b 服务器上的静态文件或者 是响应请求盼可执行文件。状态项给出了请求成功或失败的代码，例如4 0 4 表 示w e b 服务器找不到相应的文件。索引项保存了所请求资源的u r i 最后的代 理项是个字符串，可以表示用户所使用的操作系统和浏览器软件。 另外，在w e b 服务器上，许多应用都需要支持动态内容，我们称之为内容 服务器或者应用服务器渊。例如大部分的商业应用服务器都提供了某种用户注 册服务，从而得到用户的注册信息。这种从应用服务器上取得用户访问信息直 接面向应用领域，得到的数据正确性高，内容丰富详实。 2 客户端数据 客户端的数据收集可以使用诸如s c r i p t 语言嗍或 即l 剌这样的远程代理来 实现，也可以修改用户的浏览器软件，使之具有数据收集的能力。客户端的数 据收集特别需要客户的合作，因为直接从用户端取得数据需要考虑用户的隐私 和占用用户的机器和网络资源从用户端收集数据最大的优点是可以直接取得 用户的各种真实信息，这些信息的完整性和真实性都要好于服务器上的。 3 代理服务器端数据 一1 0 基于组织进化的w e b 日志挖掘算法研塞 通常在网络中基于安全和效率的考虑，需要使用代理服务器技术p l j 。代理 服务器在用户端和服务器端扮演着中间传递的角色，而且代理服务器可以是多 级级联的。代理服务器通常为多个用户服务，这样从代理服务器上就可以得到 多个匿名用户的浏览信息。代理服务器上保存着一个最近访问过的页面集合。 如果这些页面是静态的，那么用户通过代理服务器访问该页面时，就不需要从 w e b 服务器上取得数据，可以将该静态页面直接发给用户但是对于电子商务 中经常使用的动态页面就要到w e b 服务器上取得所需数据。 2 2 2 数据的模型 这些w e b 上的信息异常丰富，但是并不能作为w e b 使用挖掘的直接对象， 需要抽象出更一般和更适宜挖掘的数据形式，这就需要对w e b 信息抽象出合适 的数据模型p 2 j 。w 3 c 组织刚己经定义了一些抽象数据类型以描述w e b 的访问使 用情况。这些数据类型可以构成进行w e b 使用分析的合适的数据模型 1 一个用户( u s e r ) ：是通过浏览器从一个或多个w e b 服务器上得到数据的 个体。实际上在网络环境中能够连续和唯一的确定一个单个用户是一件非常困 难的事情。因为一个用户可能使用不同的机器不同的浏览器访问w e b 服务器。 2 一个页面( p a g e v i e w ) ：是指在一次浏览中，展现给用户的所有文件的集 合( 以下简称页面) 页面通常和用户的一个动作对应，例如用户点击一次，则 展现给用户一个新页面。相对于用户的单个动作，一个页面则是一个集合，它 包括多个框架，多个图片等内容。 3 一个点击流( c l i c ks t r e a m ) ：是用户请求页面的一系列动作服务器端的 数据并不能得到一个用户或者一个站点完整的点击流，这是因为在用户端和代 理服务器上都存在缓存。 4 一个用户会话( u s 盯s e s s i o n ) 指一个用户访问整个w e b 的点击流。这个 信息通常只能在用户端取得，因为单个用户的访问信息并不对所有的站点公开， 每个站点都只能得到用户访问本站点的信息。一个用户会话中访闯一个特定站 点的点击流称之为一个服务器会话( s e v e rs e s s i o n ) ，以下简称会话。服务器会话 的终点是用户离开该w e b 站点的时刻由于服务器日志中并不记录用户的下一 次点击信息，所以这个信息在w e b 服务器上是很难得到的。 2 3 数据预处理 2 3 1 数据预处理的必要性 在w e b 使用挖掘的过程中有一个重要的基础就是w e b 数据的准确性，必须 第= 章w e b 日志挖掘 有准确的数据才能每次都正确地反映使用者的意图，从而可以使分析沿着正确 的方向进彳亍。实际系统中的数据一般都具有不完全性、冗余性和模糊性。要使 挖掘内核更有效地挖掘出知识，就必须为它提供干净、准确、简洁的数据。由 于日志记录和协议的自身原因，目志数据是杂乱的，还原h t t p 的信息可能包 含错误信息，因此对日志信息进行准确的预处理是非常关键的焖。 数据预处理的目的就是最终得到数据挖掘的输入，即不同使用者的所有服 务器会话。为了不涉及使用者的隐私权，对使用者只强调其不相同性，并不确 定具体的哪个使用者。 预处理的最终结果主要有两个p 习，一个是用户访阅的页面的集合，记为 p z p i ，- 见 页面通过其相应的u r l 地址来表示；另一个是包含了m 个用户 会话的集合，记为r = “，t 2 ，0 ， er ，是p 的一个子集为了便利于一系列 的数据挖掘操作( 如聚类分析) ，设每一个会话t 是浏燕页面空间内的一个维的 矢量，记为f z w ，t ) ，w 慨，t ) ，w 慨，t ) ) ，其中w ( a ，t ) ，是会话t 中测览页面 的权重，ne p 。权重可以通过多种方法来确定，如可以通过表示用户浏览该页 面时间长短的函数来确定，反映该用户对页面的兴趣程度 这种结果的表示方法具有很好的灵活性假如目标是为了发现用户的浏览 路径偏好，这些用户会话可以视为一个有序集合；假如目标是为了获悉页面之间 的联系，则可以视为一个无序集合。而且这样的表示方法也有利于推荐引擎的 匹配运算嗍 数据预处理过程共包括三个主要步骤和一个可选步骤1 3 力。这一预处理过程 负责将初始的w e b 网站访问使用数据转换为服务会话三个主要处理步骤分别 是：数据清洗、用户，会话识别和网页i l i 览识别一个可选处理步骤则是补全浏 览路径。用户会话识别和事务识别是关键步骤，也是最棘手的部分，如处理不 当而引入不良数据到后续的挖掘工作中，其结果可能是谬以千里。 2 3 2 数据清洗 数据预处理的首要任务是数据清理，在任何形式的w e b 日志分析过程中， 清除服务器日志中不相关数据的技术是非常重要的只有当服务器日志中表示 的数据能够准确地反映用户访问w e b 站点的情况时，经过挖掘得到的关联规则 才是真正有用的。数据清洗是指删除w e b 服务器日志中与挖掘算法无关的数据， 这些数据主要有三类 3 e j ： 里基于组织进化的w e b 日志挖掘算法研究 1 图片、框架等非用户请求逻辑单位。用户请求的是一个整体页面，而服 务器记录的是下传到客户端的一个个文件流，其中也包括非用户请求的m 个图 片和九个框架和脚术。因此需要结合网站结构图来过滤和抽取浏览页面。 2 w e br 0 的一q 的浏览日志记录。由于w e b r o b o t 对网站的浏览是不带任何 感性色彩的，所以通常将w e br o b o t 的这些请求过滤掉许多w e br o b o t 的代理 值与通常的浏览器不一样，可通过检查日志代理清除这些记录，还可以通过对 网站的定时熏复请求来标注出w 曲r o b o t 。 3 噪音和错误信息。虽然这些信息中可能包含着某些有用信息( 如测定网 站内容的完整性，链接的正确性等) ，但对浏览模式发现来说输入的信息必须是 正确的。 2 3 3 用户与会话识别 数据清洗完成后，接着就是用户识别，其目的是对用户唯一性的识别1 4 0 1 。 由于用户端高速缓存及代理服务器和防火墙的存在，使得这一任务的实现较为 复杂。在只利用i p 地址，a g e n t 信息和服务器( 用户访问的) 点击记录进行用户 识别时，常常会遇到以下几种典型闯题i 1 j ： 1 单个m 地址，多个服务器会话：i n t e m e t 服务供应商通常为其用户提供代 理服务，这样同一个代理服务器可能有多个用户同时访问同一个站占。 2 多个i p 地址，单个服务器会话：一些代理工具或隐私保护工具可以为一 个用户随机地提供多个p 地址，这种情况下，单个服务器会话就会有多个i p 地址。 3 多个坪地址，单个用户：一个用户可能在多次访问一个站点时，使用多 台计算机，这样就使多次跟踪同一个用户变得更为困难。 4 多个服务器会话，单个用户；如果一个用户访问同一个站点时，打开了多 个浏览器窗口，就会出现多个并发的会话。 5 单个计算机多个用户：当多个用户使用同一个计算机时，就会产生这种 情况。 服务器端最常用的用户和会话识别技术是c o o k i e ，而在用户端识别用户则 不需要任何特别的技术。用户端的最大问题在于对用户行为的跟踪侵犯了用户 的隐私权，很难得到用户的支持合作大部分的网站服务都要求用户进行注册， 对于这种注册用户，无论该用户从任何机器访问网站。都能很方便地跟踪其行 为。表2 2 给出了常用的几种识别方法的比较 4 2 1 。 第二章w e b 日志挖掘 表2 2 用户会话识别方法描述 1 3 方法描述侵犯优点缺点 隐私 i p 地址和假定每个l p 地址和代低可用性好，无须另外不能保证用户的唯一 代理理组合表示一个用户的技术和信息性。一个用户多个m 的情况无法处理 嵌套会话利用动态产生两页将低冲简单可行独立于m 没有重复访问概念， i di d 插入每个链接地址 需要完全动态网站 用户注册用户显示地登录网站中可以精确跟踪每个注无法职踪大量的非注 册用户册用户 软件代理当程序调入测览器后中高可以跟踪重复的访问可以技禁止 可以发回使用数据 c o o k i e在用户端保存一个用中 可以精确跟踪访问一用户可以中止使用 户标识个站点的信息c o o k i e ，可用性不高 修改浏览浏览器纪录使用效据高可以精确跟踪用户访用户必须同意使用修 罂问所有站点的信息改过的浏览器 针对以上可能出现的种种情况，我们用以下算法来解决； 1 一个m 地址，不同的a g e n t 类型代表不同的用户序列。 2 利用参考页文件，如果某个请求的参考页文件不是己打开用户序列的部 分，就认为这个请求来自一个新的用户 3 根据参考页文件，请求可能属于已打开的多个序列，这是我们将这种请 求归纳到在时间上最为接近的用户序列 会话识别是建立在对用户识别的基础上，其目的是将每个用户的访问信息 划分成若干个独立的会话进程 4 3 1 。当日志文件中的记录信息跨越了一个较长范 围的时间时，用户在这期间就可能对w e b 站点进行7 多次访问，而每次访闯皮 视为独立不同的一次会话。对会话识别的最简单的方法是使用时间戳t h n e o u t ， 即当对页面之间的请求时间间隔超出了给定的f i r e , o u t 。则认为用户开始了一个 新的会话。通常，在一些产品中缺省的超时时间以问隔3 0 分钟计这个时间参 数也可凭经验来设定