（计算机软件与理论专业论文）基于用法的网站个性化.pdf

捧十用浩的闼站个性化摘要 摘要 迄今为止互联网和数据挖掘技术都得到了极大的发展，电子商务也吸引了 越来越多人的目光，海量的网页内容令用户目不暇接。简单意义上的链接模式不 能对用户的导航起到有意义的导向作用，很多用户面对林林总总的内容往往不知 所措。 于是就出现了一种非常矛盾的现象：一方面是可以获取的信息的快速增加， 另一方面是人们越来越难找到自己所需要的信息。在这种情况下，出现了很多相 应的解决方案。网站个性化就是其中之一。它借助数据挖掘技术对用户的使用模 式进行分析，从而达到根据用户的喜好来为用户提供有价值的内容的目的。 本文所要讨论的基于用法的网站个性化就属于网站个性化的一个分支，它通 过对网站日志中的u r l 进行聚类，在原有的网页基础上作少许静态修改或者不作 修改来为活动用户会话提供有价值的链接集即推荐集。 本文对基于用法的网站个性化系统所涉及的算法进行y i , - t 论和比较，在网站 口志的处理上提出自己的算法，并用面向对象的方法实现了a p r i o r i 算法，通过 对其中所涉及的主要数据集进行快速排序的方法降低了算法时间复杂度。并以此 为基础，实现了一个基于用法的网站个性化系统。相信可以为网站个性化提供有 意义的启示。 关键词： w e b 个性化，w e b 服务器曰志，数据挖掘，u r l 聚类，频繁项目集，用户 会活，用户事务，超文本传输协议，i s a p i 过滤器，动态服务器端页面 皓于用法的州站个性化 a b s t r a e t a b s t r a c t u pt i l l n o v v ，t h ei n t e m e ta n dd a t a m i n i n g t e c h n o l o g yh a v eb e i n gd e v e l o p e d r a p i d l y ，, a n dt h ee - c o m m e r c ei st h ef o c u so f m u c ha t t e n t i o n t h em a s s i v ec o n t e n to n t h ei n t e r a c ti s a l r e a d yb e y o n do u ri m a g i n a t i o n t h es i m p l eh y p e r - l i n ks t y l ei nt h e w e b p a g e c a l l , n o tg u i d et h eu s e rp r o p e r l ya n d e f f i c i e n t l y ，m a n yu s e r sl o s tt h e m s e l v e s i nt h e 射a a s s i v ei n f o r m a t i o no nt h ei n t e m e t a n i n t e r e s t i n gb u tc o n t r a r yp h e n o m e n a o c c u r s ：o no n eh a n d ，t h ei n t e r n e tg i v ea s m u c ha sp o s s i b l ei n f o m l a t i o n ；o nt h eo t h e rh a n d ，t h ei n t e m e tu s e r sc a n t g e tt h e i r a p p r e c i a t e dc o n t e n t m a n ys o l u t i o n sh a v eb e e nd e v e l o p e d t os o l v et h i sp r o b l e m ，a n d w e b p e r s o n a l i z a t i o n i so n eo ft h e m i tu s e st h ed a t a m i n i n gt e c h n o l o g yt oa n a l y z et h e i n t e r e s t i n go f s p e c i f i e du s e r , a n dp r o v i d eh i m t h ec o r r e c ta n d i m p o r t a n ti n f o r m a t i o n h e r e ，w ed i s c u s s e do n eb r a n c ho fw e b p e r s o n a l i z a t i o n - p e r s o n a l i z a t i o nb a s e do d t t l ew e b u s a g e i tg i v e sw e b u s e ras e to fh y p e r - l i n k sw h i c hh ew i l l p o t e n t i a l l y v i s i t 。 i nt h i sp a p e r , w eh a v ed i s c u s s e dt h ea r c h i t e c t u r eo f p e r s o n a l i z a t i o nb a s e do nt h e w e bu s a g ea n d c o m p a r e da l g o r i t h m si n v o l v e dt h e r e h e n c e 、w ed e v e l o p e do u r a l g o r i t h mi nl o gf i l ep r e p r o c e s s i n ga n dh a v eg i v e na no p t i m a li m p l e m e n t a t i o no f a p r i o r ia l g o r i t t u n w eb e l i e v et h a tt h i sp a p e rc a ng i v es o m ev a l u a b l eh i n tt ot h e b u i l d i n go f p e r s o n a l i z e dw e b s i t e ， k e y w m d s ： w e b p e r s o n a l i z a t i o n ，w e bs e r v e rl o g d a t a - m i n i n g ，u r lc l u s t e r ，f r e q u e n ti t e m s e t ， u s e rs e s s i o n ，u s e rt r a n s a c t i o n ，h t t p ，i s a p if i l t e r ，a s p 绪论 1 ，f 研究背景 第一章绪论 随瞢阔络豆联技术迅猛的发展和上网冲浪人数的激增，互联网的规模也达刘 ) 。个盼所未有的程度。根据c n n i c 公布的信息表明：截止到2 0 0 2 年1 月， 中圈屿上劂机器数为1 2 5 4 万台，而国内注册的各类网站( 包括中国域名和顶级 域名) 约为2 7 7 1 0 0 个。 髓d d 很多传统行业如生产、传媒、咨询、销售等等的一般同时以网页的形式 向h j 户提供信息：同时，很多互联网公司更是只选择互联网作为信息的唯一载体。 基于此，业界越来越认同互联网已经成为为一种全新的信息载体，跟报纸，电台， 电视等传统传媒相并列，被称之为第四媒体。由于这种全新的媒体上出现的信息 具有更强的时效性和和可交互性，越来越多的用户选择从互联网取得所需要的信 ，i 氮这种所淆能第四媒体大有取代传统媒体的趋势。 同时，随着动；冬服务器端网页技术，如c g i ，a s p ，j s p 以及等业务逻辑专 用技术如e j b ，j 2 e e 等的出现，为纯粹的电子商务网站的出现创造了条件。 事务在w e bt 实现的简便性和快捷性是推动电子商务快速增长的主要动 力：b 2 b 电子简务因为它的巨大容量，已经吸引了大量目光的注意。多年来， b 2 b 皂子商务的已经在一些方面取得了引入注目的成就，大部分体现在供应管理 和电子支付上。另一方面，b 2 c 电子商务也在进行着一场革命：目前对用户浏览 行为舱跟踪已经可以详尽到每次鼠标点击，这种跟踪使得销售商和客户的关系空 前紧密。技术l 已经允许销售商在海量的数量级上为客户进行产品信息的个性 化，业界称这种个性化为海量定制。 但是这种把货架简单地搬到网页的电子商务交易方式很快就暴露出很多问 题：首先是货物仅叹以图片和文字的方式加以陈列不能完全满足用户挑选商品的 种补蛭求，另夕 当电子商务商网上销售的产品过多时，就必须对商品进行分类缉 织，l i 便如此，一个用户为了找到自己需要的商品之前仍需要进行很多乏味的翻 页操作。电子商务所带来的那种便利很快被所带来的不方便所取代。 同时，非电子商务网站也存在同样的问题：在网站的建设初期，网站的内容 耍摊 往只是根据简单的需求分析，甚至完全根据工程师的经验来进行的。这种 最仞f 】勺安排大部分情况下是不尽合理的。举例来说：在某个服装业和出版业比较 缆达的地区有家购物向导网站，它的业务主要是向最终用户介绍多种类型的本 地特电产品，在网站中访问“书籍信息”页面的用户群由于收入较高，因此会有 大概辽一半的辟j 户同时会访问“服装信息”的，但是由于网站在设计的时候没有 绪论 做：宅：， 的用户需求，在网站的设计上存在明显的漏洞：网页中不存在“书籍信息” 与“服装销售”之阳j 的链接。网页的这种缺陷毫无疑问地给这部分用户的使用带 来少许不便。 我们知道在。j 前的这种互联网的“适者生存”时代，任何的服务质量上的 缺陷都有可能带来客户的流失，这对很多靠统计点击率维生的信息网站还有很多 以产品销售为目的的电子商务网站而言，这种客户的流失都是他们所不愿看到 的。 t j 5 么如何d 能提高服务质量，避免出现这种网站结构和内容设计上的缺陷就 成为问题的关键，目前已经出现了很多解决方式： 通过在网站建设初期对服务对象的需求进行充分的分析可以避免很多类似 的错误。这种方法实际上是软件工程中用户需求分析的一个特例，如果该过程得 以很好的执行，则可以避免很多这样的错误。另外，在网站的运营过程中，根据 用户的反馈信息修改网站的设计也是这种方式的延续，它有点类似于软件工程中 的用户需求增加或改变所带来的版本升级。 但是这种完全静态或者半静态的网站结构和内容的修改存在着很多问题：特 别是定期地网站手工升级方式的网站内容与结构的调整并不能很好地适应当前 瞬息力变的世界。 在这种情况下，就出现了对用户使用方式和访问特点进行分析，为网站内容 加卜自动调整引擎方式的网站动态调整升级技术，这种技术就是所谓的基于用法 的网! ，卜性化。 这种个性化网站根据分析技术的不同，可以在( 使用习惯相似的) 用户群甚 至单个用户为粒度，对网页的部分内容或者网站的链接结果进行动态调整，它相 对= | 二谴过网站升级方式实现的网站内容和结构调整而言，首先保证了调整的即时 而且不以牺牲少量用户的使用为手段，显然比后者更具有竞争力。 1 2 研究目标 雉爿二用法能网站个性化系统所要实现的功能之就是要根据可以得到的用 j m 持睦数据求对用户的使用习惯进行分析，这个阶段实际上是数据挖掘在我们这 种特定环境f 的应用。 那么如何才能得到这种用户特性数据呢? 这种用户特性数据的来源主要锝 眄方面：用户的注册信息和网站访问f = | 志。 其中，l b 于用户的注册信息并不总能够得到( 网站可能不需要这部分信息) ， 或者的得到的信息不准确( 用户出于隐私的考虑，登录不正确的个人资料) ，因 此在嘲站个性化的环境里面一般不使用这种数据。网站个性化的分析阶段中将主 4 绪论 要使用网站的f i 志数据。 稍：分析阶段得出用户的使用习惯数据( 根据分析阶段使用的算法的不同。这 螳分析结果可能匕、频繁集或者u r l 聚类的方式给出) 后，还需要个阶段来达到 对删站的内容和链接结果进行自动调整。这个阶段在用户对网站进行访问时柬运 行，一般通过为用户提供潜在有用链接的方式给出。 因此，基于用法的网站个性化系统的研究就可以分为这两个分离阶段加以研 究，其中前阿、段主要是解决数据挖掘技术如何在个性化的环境里面加以应用， 后。一阶段的主要任务是如何利用现存的动态网页技术来实现网站内容的调整。 研究的目标就是对构成系统的两个组件所涉及的算法进行比较和研究，进而 提出自己的改进癣i 实现。 1 3 研究工作 在论文中，我们对基于用法的网站个性化系统所涉及的算法作了分析和比 较并最终选择了基于频繁项目集来计算推荐的方式实现了基于用法的网站个性 化； 在本系统的实现中，我们在网站同志的预处理中提出了自己的算法，并通过 刑炎键过程和数据进行排序的方式，给出了a p r i o r i 算法的高效实现。 1 4 论文结；陶 本论文共分为五章： 第一j # 为绪论。主要介绍基于用法的网站个性化系统的研究背景，研究目标 还育论：迂的结构。 笫：章是综述。主要介绍了网站个性化的相关研究。 第三章是基于用法的网站个性化系统原理。主要介绍了如何实现一个基于用 法的个性化系统需要那些组件，每个组件的功能、作用和实现技术与算法。 第剀章是基于用法的网站个性化系统实现。主要介绍了如何实现按照个性化 系统的原理来实现一个现实系统，并对前面的算法进行了相应的比较。 笫i l 章是结语。主要介绍了论文的创新之处，提出了要建立一个更加完善的 j ，( _ 4 站个1 生化系统需要进行哪些方面的继续研究。 综述 第二章综述 2 1 数据挖掘技术简介 j ( h n n a is b e t t 在他的大趋势中提到：“人类正被数据淹没，但人类渴 魁知泠。” 数据挖掘这一术语最早出现在1 9 8 9 年，比较流行的定义是u f a y y a d 等在文 献1 中给出的： 数据挖掘就是从数据集中识别有效的、新颖的、潜在有用的、并且最终可 理解的模式的非平凡过程。 这罩要特别强调几点：这个过程通常是一个多阶段的过程，它包括数据准备、 模式搜索、知识评价、以及反复修改求精等等阶段；这个过程是非平凡的，即要 求柯定程度的智能性、自动性；模式的有效性指的是发现的模式对于新的数据 仍然碉一定的可信度；新颖性是指发现的模式是前所未知的；潜在有用性说明发 现的知识将来有实际效用。最终可理解性是指发现的模式可以被人所理解。有效 。r ：、新颖性、潜在有用性、最终可理解性综合在一起可以称为j nr e t e s t i n g ( 有 意义) 。 数据挖掘的前身即知识发现( k n o w l e d g e d i s c o v e r y ) ，它源自于人工智能的 机器学习领域，其内涵是在一个已知状态的数据集( d a 抬s e t ) 上，通过设定一 定的学习算法，从数据集中获取知识。人工智能领域中的知识发现技术已经发展 到了个很成熟的阶段，但是由于缺乏应用的土壤，它的路越走越窄。而与此同 时，数据库技术也已经发展到一定的阶段，并得到了广泛的应用，各个企业在多 年f 由数据库应用中都已经积累了巨大数量的数据，迫切需要有一种新的技术来帮 助他们从数据中发掘出知识，数据挖掘技术f 是应这一需求而出现的，它是知识 ，! 现技术在数据库领域中的应用。 传统的数据挖掘技术是对数据库或者数据仓库的数据以半自动( 即有用户交 f 的方式寻找出特定的模式关联规则、变化规律、异常信息等具有统计意义 的结f 和事件。简单的说，它负责从海量数据中挖掘有用信息。 2 1 1 数据挖掘的主要模型 荚麟规则模型 i 发模型旨在发现数据项之间的相互关系，并根据这种关系从数据中找到有意 义的幞式和趋势。以超市销售数据库为例，每个记录包含了一次采购商品的列表， 坫j 一使用的嘲站个性化 其中，黜陡关系告诉我们两件或更多商品之阳：】的关系。如8 0 的顾客购买了面包和 牛奶，其中有6 0 的顾客在买面包的同时买了牛奶。我们把这种面包和牛奶之间 的关联关系用下列规则表示：面包j 牛奶( 6 0 ，8 0 ) 。数据项的关联关系也可 以在多个项目之间产生，例如：面包、牛奶j 甜酱( 6 0 ，4 0 ) 等。目前采 用的蛆，弘关联规则发现算法有a p r i o r i 算法和p i f p 散列表算法等。 柚 神经网络：漠型 神经网络方法是模拟人脑神经元结构，以朋r 尸模型和y e b b 学习规则为基础而 建说的，主要有三大类多种神经网络模型。 o 1 | 馈式网络以感知机、反向传播模型、函数型网络为代表，可用于预 测、模式识别等方面。 反馈式网络以t t o p f i e j d 的离散模型和连续模型为代表，分别用于联想 记忆和优化计算。 由 自组织网络以a r t 模型、k o h o n e n 模型为代表，用于聚类。 = i ：咔 空网络的知识体现在网络连接的权值上，是一个分布式矩阵结构。神经网 络的学习表现在神经网络权值的逐步计算上( 包括反复迭代或累加计算) 。 籽i 糙集理论模型 ；糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家 z a w 】a k 于1 9 8 2 年首先提出。粗糙集的研究主要基于分类。分类中的类别与概 念( c o n c e p t ) 同义，一种类别对应于个概念( 类别一般表示为外延即集合， 而概念常以内涵的形式表示如规则描述) 。知识由概念组成，如果某知识中含有 不精磷概念。则该知识不精确。粗糙集对不精确概念的描述方法是：通过上近似 溉念秆f 近似概念这两个精确概念来表示。一个概念( 或集合) 的下近似( o w e r a ) i ) f o x i m a t i o n ) 概念( 或集合) 指的是，其下近似中的元素肯定属于该概念： 。个概念( 或集合) 的上近似( u p p e ra p p r o x i m a t i o n ) 概念( 或集合) 指的是， 其丘似中的元素可能属于该概念。粗糙集方法有几个优点：不需要预先知道额 外、曹，如统计中要求的先验概率和模糊集中要求的隶属度：算法简单、易于操 作。 2 1 2 数据挖掘用到的相关技术 人工神经网络( n e u r a ln e t w o r k ) 测模型，通过学习进行模式识别 种挖掘任务。 它仿照生理神经网络结构的非线形预 可以完成分类、聚类、特征挖掘等多 遗传算法( g e n e t i ca l g o r i t h m ) ：基于进化理论，并采用遗传结合、遗 传变异、以及自然选择等设计方法的优化技术。 基于使用的髑站个性化 决策树( d e c i s i o nt r e e ) ：用树形结构来表示决策集合，这些决策集合通 过对数据奂的分类产生规则。典型的决策方法为分类回归树( c a r t ) 算法， 般用于分类规则的挖掘。 近邻算法( n e a r e s tn e i g h b o r ) ：通过k 个与之最相近的硒史纪录的组合 来辨别新的纪录，有时也称为k 一最近邻方法。这种技术一般用于聚类、 偏差分析等挖掘任务。 规则归纳( r u l ei n d u c t i o n ) ：从统计意义上对数据中的“如果一那么”规 则进行寻找和推导，该算法应用在关联规则的挖掘。 2 2 基于w e b 的数据挖掘技术简介 面向w e b 的数据挖掘是数据挖掘技术在w e b 上的应用，一般称之为i n t e r n e t m i n i n g 或者是w e bm i n i n g 。面向i n t e r n e t 的数据挖掘比面向数据( 仓) 库的数据 挖掘要稍微复杂一些。这主要是因为传统数据库中的数据是结构化的，而 i n t e r n e t 上的数据其最大特点是半结构化的。 所谓半结构化是相对于结构化和非结构化而言的。例如传统数据库中的数据 结构性： 浸强。我们称之为完全结构化的数据，另外还存在一些方式的数据表现形 式如书、图片等等，这里面的数据是完全非结构化的。目前w e b 上存在的数据介 于这两者之间：它的页面具有一定的描述层次，也存在一定的结构，所以我们将 它称为半结构化的数据。 根据挖掘的对象不同，网络数据挖掘可以分为网络内容挖掘、网络结构挖掘、 网络用法挖掘以及网络用户挖掘。 网络内容挖掘：网络信息是由文本、图像、音频、视频、元数据等形式 的数据组成的。网络内容挖掘就是一个从网络信息中发现有用信息的过 程。由于网络信息内容有很多是多媒体数据因此网络内容挖掘也将是 一种多媒体数据挖掘形式。 网络结构挖掘：网络结构挖掘就是挖掘w e b 潜在的链接结构模式。通过 分析一个网页链接及被引用的数量以及对象来建立w e b 自身的链接结构 模式。这种模式可以用于网页归类，并且由此可以获得有关不同网页间 相似度及：建联度的信息。网络结构挖掘有助于用户找到相关主题的权威 站点。 网络用法挖掘：网络内容挖掘和网络结构挖掘的挖掘对象是网上的原始 数据，而网络用法挖掘面对的则是从用户和网络交互的过程中抽取出来 的第二手数据，包括网络服务器访问记录、代理服务器日志记录、浏览 器同志记录、用户特性、注册信息、用户对话或事务信息、用户访问方 8 攮十便_ 】的| 尚9 站个传化 轹还 式等。通过网络使用挖掘，可以把握用户网络行为数据所代表的意义。 网络用户挖掘：根据用户的网站访问日志和注册信息对用户的使用喜好 进行挖掘，进而根据网络用户的网络使用模式进行分组。 需要指出的是：w e bm i n i n g 绝对不是简单的将d a t am i n i n g 的相关算法瘁用 于新的w e b 数据，而是由自己特殊之处。 2 3 基于服务器曰志的数据挖掘技术简介 要建设基于用法的个性化站点。就要了解用户是如何访问这个网站的，也就 是要对用户的用法进行挖掘。通过网络用法挖掘，就可以了解用户的网络访问行 为所具有的意义。如前所述，挖掘的数据来源包括w e b 服务器访问日志记录、代 理服务器日志记录、浏览器历史记录、用户特性、注册信息、用户会话或事务信 息、用户的提问方式等。 本论文的研究目的，是要设计一个不需要用户协作的、具有自学习功能的个 性化系统。研究的对象，是一般意义上的网络用户，这一点决定了挖掘数据的主 要来源是服务器端的曰志。 下面讲述一下日志挖掘的处理流程： 2 3 1 日志挖掘处理流程 对月志进行挖掘的流程参见下图 即挖掘模块首先对服务器日志进行数据预处理以得到用户事务文件：然后在 事务文件的基础上进行数据挖掘，发现一些满足指定支持率阈值的关联规则；最 块予使圩j 的阚站个性化 后根据发现的关联规则进行用户使用模式分析，得到用户的兴趣所在，或者叫用 户喜好。其中服务器日志的内容以及用户的喜好跟网站的内容和结构密不可分。 为了让大家对网站日志有个感性认识，下面我们给出了e c l f 日志的格式介 绍，它是目前比较常用的网站日志格式。 2 3 。2e c l f ( e x t e n d e dc o m m o nl o gf o r m a t ) 日志格式简介 每个e c l f 日志记录项，都包含了用户地址、用户i d 、请求时间、请求方法、 u r i 、引用、所用传输协议、状态码、返回字节数和使用的代理等信息。e c l f 提 供了诸如跟踪引用网页和识别c o o k i e 的功能特性，其中用户i d 一项只有在需要 网页需要用户登录认证的时候才存在。 闷志中的请求方法为标准h t t p 请求方法，包括g e t , p o s t 和h e a d 三类。g e t 方法用来向服务器请求相应对象，总卵方法用来向服务器发送信息，h e a d 方法 用来向服务器请求相应对象的头部信息。 日志中的e 胛z 由相应的w e b 服务器所能提供的功能而决定，一般服务器会提 供静态网页文件和c g i 服务两种类型的网页内容，所以u r i 既可能是静态的文件， 也可能是可执行程序，在使用服务器端脚本或者c g i 的服务器上，u r i 中也含有 请求串信息。 同志中的状态码反映了本次操作的结果，该值由w e b 服务器设定，一般情况 ；用2 0 0 到2 9 9 代表操作成功，3 0 0 到3 9 9 代表重定向，4 0 0 到4 9 9 代表请求错 误，5 0 0 到5 9 9 代表w e b 服务器内部错误。 f 面是一个e c i f 日志中部分，它可以帮助读者加深理解。 l c a l ”yc 眦t nh _ g a 电= = n ：轴：融- , 0 s 0 0 。啦z ，b - r ，c 啦- i ，c 6 t = j t o 龃i i l 耵嚣，i q - 拍o9 3 为 n # b - 啦t 抽= j a t = 时吖a w , h 0 坼t 0 l i l 5 缸盼- o 釉】。，k t i w t i 。0 0 ，越l - g c 4 舭抽= j a i a 嘧| ， 嗨，t 嘶： ：# l ：h - 0 s 0 0 ：) 。i , m y ，i 一舡t t ，p - 一“盯t ，1 o 。神。鞠t 4 o s c _ 呦“- 扣丑国 i 口“l 墙：8 a ：6 3 螂1 堆f i - 一 “c ，c _ t 时j m 删i o 2 0 0t 彗萄 m e ( a c 口。i 胤 - 抽- 扭h 印鼍，l 坼：5 k 1 2 - a m o 幢t ，c 群啼l “咀钮耋，蕾- 口- _ t d 吒e f t = l 坩t p ，1 0 2 0 05 “ o 吣 - _ i - 4 血刈- i a - a w l 鼙，i 钾：0 l ：5 | l - 0 o 】。霉f ，“f h 嚣a w a i t 0 0 釉 t 垲o 1 i r a 曲抽i n 0 1 舭懈= o g f s l ：1 - o 町嚣t ，r h 赶，r 瑚o ，t 铲i 稿， 1 舶舯，c 甑d th a - q ，l “l 口坤：5 k 砷洲0 黔，“岫r ，c 蚰r _ l ，c 西a 毗o 啦2 自吐h t 狰 铲o1 4 0 7 2 o 峭c b t - a 由= j a t n 一时叭畔，i 口：仰：# 如i l 删】。趣t ，一v 土i 埘，臼c l f q h - il 耵，i 。- oi 鲋o l t f 舳，c 册“_ m j 一口，l 堰止鹪：o ：5 如”- o s 0 0 憎t ，一m 岫啪舭“t 一如，t 虹d b h 毗h m ，1 2 锄棚5 5 o 蚰“u - e ，一t 冉劓b _ 一【蚺，葺q 丑，婚6 ：筠1 5 0 删唁盯州山珂1 - h 吐h m ，i ，扩神o 瞄 m c 眦柚ut ，h 肿h 一【， n ，坤 ! ：辚：5 5 一姊删- c n ，_ t h h o h m ，1 蚺l _ hh m t o - 2 i 4 c t 啪em h _ l l - 【，“s 嶂懈：描：6 7 喵唧盯，_ h 珂们，抽蛐，ml n 矗，i o - i 柑 2 3 3w e b 日志的标准化数据模型 为了将日志数据整理为可以挖掘的数据集，需要对日志格式进行建模，其 中。w c a 提出的数据模型比较常用。它的数据抽象方法目前已经成为进行进一步 的静态分析、在线分析( o l a p ) 或者数据挖掘所要使用的合理数据模型。 l o 蕞于使用的网站个性化 下表给出了该数据模型中的各个数据项以及所代表意义： 项 u s e r p a g ef i l e b r o w s e r p a g ev i e w w e bs e r v e r c o n t e n ts e r v e r s e r v e rs e s s i o n 定义 通过浏览器访问网页的个体。每个用户可通过不同的机器不同 的代理来访问网站。 通过h t t p 应答传递给用户的网站文件 客户端软件负责显示页面和发送用户请求 浏览者一次单击得到两页视图。一般情况下由多个文件组成。 一个网页视图代表了一次用户行为 服务器端软件，负责处理浏览者请求 服务器端软件负责为请求提供相应文件 阚站用户的_ 次访问过稳中韵点击流( c l i c ks t r e a m ) 。也称为 一次访问， 用户会话点击流中有意义的都分，是用岿念话或服务器会话的 一个子集。注用声会话、( 事务) ：餍产韵酚段性的点击流，可 e p i s o d e 以跨越凡个目匪务器；服务器会话：用户在一个服务器上的骱段 性的点击流。 另外，对于一些配备有专门内容服务器的较大型的网站而言，为了能够对用 户行为进行准确跟踪，可以考虑对内容服务器上的日志也进行挖掘。 2 4 建立基于用法的个性化站点的步骤 2 4 1 个性化服务的定义 所谓个性化服务指的是通过对信息的结构，内容以及表现形式进行调整， 以适应不同用户的使用习惯。 个性化服务既可以通过用户自我定制的方式加以实现，目前大多数网站的 个性化服务指的就是这种类型；也可以借助一些成功的数据挖掘和知识发现算 法，对用户的使用习惯进行学习，由信息提供者( 在网站个性化中指的是网站) 来自动进行个性化服务。 为了实现个性化站点( 也叫智能导航站点) 需要根据用户的浏览模式来更 改、组织和展现网站内容，这就必须对用户的使用模式进行挖掘，也就是对用户 在以往会话中的交互历史纪录( 点击流) 进行分析，发现其使用规律。为了做到 这一点，必须借助数据挖掘技术对纪录用户使用行为的网站日志进行挖掘，挖掘 出诸如关联规则，事务、用法聚类以及频繁项目集等信息。这个发掘过程一般是 基于使用的阿站个性化 定期、离线进行的；另外一个在线推荐调整阶段也是必不可少的，它的任务是结 合用户当前进行的操作以及挖掘出来的知识对网页内容进行调整或者为用户进 行推荐。 一般的讲，完成这种意义上的网站个性化需要经过四个阶段： 2 4 2 信息收集 信息收集是数据挖掘、模式分析和个性化应用的基础。从理论上讲，凡是能 体现出用户在浏览网站时的兴趣和偏好的数据，都应该加以收集。在目前可以收 集到薛信息中，客户端的c o o k i e ，代理服务器、w e b 服务器以及内容服务器的日 志，都能或多或少地反映出用户访问情况，譬如说：用户是从哪个网页进入的： 他在哪些页面中停留的时间比较长，停留时间是多少；在哪些页面中引用的内部 链接最多；用户撮关心哪些方面的内容：他在这个网站上总共停留的时间；以及 该用户所在的地域等等。但是在一个实际的应用系统中没有必要也不可能对所 有的用户相关信息都进行收集，这既有技术上的限制，也有非技术原因( 如用户 的意愿) 。 另外。当前w e b 上使用的协议标准也限制了我们获得精确的信息。譬如说： w e b 服务器的访问日志不论是c l f ( 通用日志格式) 还是e c l f ( 扩展通用日志 格式) 格式，在记录每次用户访问时，都只是存储了时间、i p 地址、请求方法 等非常有限的内容。再譬如说：目前流行的浏览器只能保存总共3 0 0 个c o o k i e ， 每个c o o k i e 有4 k 的容量限制，每个域服务器只能在客户端放置2 0 个c o o k i e 。 i n f e r n e t 上普遍存在的代理服务器，也使得信息的收集更加复杂。这在后面的 章节中将做进一步的讨论。 技术上允许对浏览器或者w e b 服务器进行一些修改，让他们纪录更多一些的 浏览信息，这样就有可能不侵犯用户隐私的前提下，根据这些信息来合理引导网 站浏览。可惜的是对于个仅仅为用户提供内容服务的网站而言，这种做法显然 无法付诸实施。 目前也有不少的企业和标准化组织，一直在试图找到一种既能让网站不侵犯 到用户隐私和影响服务性能，又能保留“不多不少”的用户信息的完美方案。在 这些方案中，比较成功的是w 3 c 提出的p 3 p ( p l a t f o r mf o rp r i r a c yp r e f e r e n c e s ) 标准，它允许用户自己控制个人资料在网络上的暴露程度。 如果浏览器和网站都支持p 3 p 标准，浏览器就会在每次网页下载前向用户提 示该魄站的隐私保护等级。p 3 p 要求支持它的网站把隐私保护策略嵌入到网站的 代码中，所以一个同样实现了p 3 p 的浏览器就可以自动获知这个网站的隐私保 护策略。 基于使用的网站个性化 2 4 3 数据挖掘 阶段1 1 1 收集到的信息，将会被用于信息的挖掘和分析。在这一阶段里面， 需要使用数据挖掘技术的相应成果。 就分析和建立模型的技术和算法而言，网站的数据挖掘和普通的数据挖掘差 别不大，后者的很多方法和分析思想都可以运用到前者，所不同的是网站的数据 格式直接来自于用户的点击流，属于半结构化数据，与一般数据挖掘所使用的结 构化数据有所区别。因此为了能够让挖掘正常进行，就必须对这些原始数据进行 预处理，把这些杂乱无章的原始数据整理成合乎格式的数据。有关数据预处理要 使用到的技术，我们会在第三章里做较为详细的阐述。 2 4 4 模式分析 l _ 1 2 分析的得到的关联规则和聚类等知识，在这一阶段里面将被吸收学 习。对用户浏览模式的分析，主要用到了人工神经网络的相关技术。这个阶段的 任务是按照生理神经网络结构的非线形预测模型，对挖掘出的内容进行学习以及 模式识别。 2 4 5 个性化应用 经过前面几个阶段的处理，当一个用户再次访问网站时，分析结果马上就能 派上用场：一个浏览自适应网站可以根据该用户以前的使用模式，即时动态生成 相应页面或者对页面内容活结构进行动态调整。通过这种自动化的定制，再加上 手：e 定制的配合，可以帮助用户更为省时省力的获取所需信息。 幕于使厣的隔站个性化基于用法的网站个性化系统原理 第三章基于用法的网站个性化系统原理 3 1 基于用法的w e b 个性化系统架构 根据完成任务的不同，基于用法的w e b 个性化系统由两个组件构成，他们 分别是离线批量处理阶段和在线调整( 推荐) 阶段。 其中，离线组件由产生用户事务文件的数据准备任务和特定的使用挖掘任务 组成，这个挖掘组件的任务是根据网站日志得到相应的频繁项目集和u r l 聚类。 一旦挖掘任务完成。挖掘出的频繁项目集和u r l 聚类将被作为中间结果存放， 提供给架构中的在线组件，由在线组件负责根据当前的网络浏览活动和该中间结 果为用户提供动态推荐。 在线组件由推荐引擎和w e b 服务器组成：w e b 服务器负责在用户浏览器向 它提出1 - 1 1 7 p 请求时对用户会话进行跟踪。这种跟踪的实现可以通过多种方法譬 如u r l 重写，暂时缓存w e b 服务器访问日志等；推荐引擎结合活动用户会话、 ”r f 聚类和关联规则等计算出一个推荐u r l 集合。这个推荐集合在页面被送到客户 端浏览器前作为链接组被添加到最后请求页面中。 下图给出了该系统的通用架构。下面我们对架构的每个组件的细节展开讨 论。 1 4 捧于使斥f 的嘲站个性化 基于用法的网站个性化系统原理 3 2 离线组件( 挖掘组件) 挖掘组件所要完成的任务可以分成两个分离阶段：第一个阶段是预处理和数 据准备阶段包括数据清理、日志过滤以及事务确认等子任务；第二个阶段为挖 掘阶段，这个阶段通过各种方式，如关联规则挖掘和聚类等来发现用户的使用模 式。下面将分别就这两个阶段展开论述。 3 2 1 预处理阶段 识别用户会话 基于使用的问站个性化 基于用法的i 南9 站个性化系统原理 预处理阶段是所有为用户提供推荐的技术都必不可少的阶段，它负责从w e b 服务器所提供的原始使用数据中识别出用户会话集合。在最理想的情况下，用户 会话可以给出访问网站的每个用户账号的确切信息，如哪个网页被请求，用户花 费在每个网页上的时间等等。但是实际网络却完全不是那么回事。 为了提高性能和减少网络流量，大部分w e b 浏览器都对已经请求过的网页 进行缓存，这就是所谓的本地缓冲机制：另外很多局域网出于成本、安全和效率 的考虑为子网的用户提供了代理服务器，这两者都对形成精确用户会话造成了很 大障碍。 由于本地缓存的存在，当用户点击“回退”键时，w e b 浏览器显示的是被 缓存到本地的网页而不是由浏览器重新向w e b 服务器提出请求的结果，这种情 况下w e b 服务器自然就无法知道客户端是否发生了重复的网页访问。 代理服务器的目的是为其用户提供了全局的中间层次的高速缓存，它的存在 一方面提高了性能，减少了网络流量；另一方面也不可避免地给网站用户会话的 识别带来了很多的难题： 由于代理服务器的所有用户都通过它向目的w e b 服务器提出请求，w e b 服 务器的同志就必然把来自同一个代理服务器的所有请求都视作个单一用户的 请求，也就是说这些请求都具有相同的识别子( 代理服务器的识别子) ，而不管 这些请求实际上来自不同的现实用户。另外一方面。由于代理服务器的层次缓存 机制，多个用户在某一时间段内测览的网页可能来自代理服务器次请求的结 果。 在这种情况下为了能够把服务器日志细分到单个用户会话，必须采取一些 辅助措施，比较可靠的方法包括使用客户端c o o k e 和采用带有隐含会话耐的动 态u r l 。 但是，这些技术也不能总是有效：用户隐私方面的考虑决定了不能完全借助 于c o o k i e s ：另外由于w e b 服务器的容量有限，它也不可能为发生的每个会话创 建和维持会话f c ，。 为了处理这个问题，文献7 提出一种改进方法，它通过对服务器日志中的提 交者和代理字段进行一些简单的启发式处理，再借助于一些相对精确的附加信息 ( 如c o o k i e s ) ，就可以帮助识别出用户会话以及推断出丢失的引用。 建立网页视图列表 由于h t t p 协议的无状态连接特性，一次用户活动可能会涉及到多个文件 ( h t m l ，图像，声音等等) 的请求，而从使用的角度来看，这种因为一次用户点 击而引起的许多文件访问应该归为一个网页视图。 而日志中的记录一般是以请求作为粒度，因此除了识别用户会话外，预处理 1 6 撼于使用的嘲站个性化 基于用法的网站个性化系统原理 阶段还要负责对原始的日志数据进行另外一种清理，并把日志转化为一张网页视 图的清单。 为了建立网页视图，必须要删掉日志中多余的文件访问信息，使得每个网页 视图只存在一个代表性条目。对于那些使用了h t m l 帧集技术的网页，需要到 把帧集中涉及的所有网页归为一个视图；对于那些使用了服务器端动态网页技术 的网页，需要把那些具有相同模板名字而实际代表不同访问的情况则要归类为不 同的网页视图。 网页存在性过滤 除了上面提到的清理工作之外，可能还有必要对日志文件进行过滤，把引用 映射到代表网页间物理连接的站点拓扑图中。这部分清理工作对于基于用法的个 性化系统也非常重要，因为推荐引擎不应该向用户提供过时的动态链接和不存在 的网页。 识别用户：事务 用户会话文件中的每个会话可以分两种方式看待：既可以视为涉及至i 。z 艮多网 页访问的一次事务也可以视为很多只涉及单一网页引用的多个事务。为了动态 为每个用户产生有意义的引用聚类，必须对事务进行识别。 根据用户浏览行为的内在模式，网页引用可以分为内容引用，辅助( 导航性) 引用，和混合应用三种类型。根据这种引用分类方法，用户会话文件中的蕴含的 事务也可以分为两种不同类型：纯粹内容的事务( 纯粹涉及对内容网页的引用) ， 和导航内容事务( 涉及到几种网页类型的引用) 。事务识别的具体方法可以在文献 7 里面找到。为了论文论述方便，我们在论文里面假定每个用户会话均被视为单 一事务。 最后，可能还需要对会话文件进行过滤以删除极小事务和极低支持率引用( 那 些没有在一定的用户事务中出现的引用) 。这种类型的支持率过滤既可以删除噪 音数据，又能够有效地实现u r l 维数缩减，为数据挖掘阶段中以u r l 为特性的 聚类任务打基础。 在后续的章节中，我们都假设所有讨论的网页日志均经过预处理，处理后地 日志中存在一个大小为n 的u r l 集合： u = u r ll ，u r l2 ，u r l 。) 和一个大小为卅的用户事务集合： t = f 1 ，f 2 ，t 。) vt ，t ，有t ，u 且f ，。 接十使牙j 的嘲站个性化 基于用法的同站个性化系统原理 3 2 1 1 用户会话的识别 匿名用户w c b 使用挖掘处理的对象是从日志等信息中抽取出来的会话集。 w e b 日志信息可以以| h 举 表的形式存储，客户端的口地址作为h a s h 表的键。 因为很难将会话具体归入某个确定的用户对匿名用户w e b 使用挖掘来说， 我们更感兴趣的是从一个客户端的i p 中抽取出不同的会话。会话识别的目的就是 将用户的访问记录分为单个的对话。本节提出了两种启发式的规则。 超时启发式规贝i j 最常用的简单可行的方法就是超时划分的策略。如果在一段时间间隔t 内， 一个特定的客户端没有再次发出请求，则当前会话结束，同时一个新的会话开始， 即两页间请求时间的差超过了某个界限就可以认为用户开始了一个新的会话。 连接跟随启发式规则 这种方法利用站点的连接结构从客户端抽取用户的会话。我们称为 w e b c r a n l e r ，从站点的主页开始产生站点的有向图，节点代表一个页面，如果两 个页面之间有超连接，则它们之间有一条边，w e b c r a w l e r 的算法如下： l 是w e b 页面的堆栈，h 是h a s h 表，键是页面，取值为0 或1 ，1 表示被w e b c r a w l e r 程序访问过，0 表示相反的意思。 对任意页面w 我们定义函数g e t p a g e ( w ) 作凡 p 2 ) s 2 ：( p 3 ，p 5