（计算机应用技术专业论文）一个基于搜索结果的个性化推荐系统.pdf

郑卅l 大学硕士学位论文一个基于搜索结果的个性化推荐系统 摘要 随着计算机技术和网络技术的不断发展，i n t e r n e t 上的信息剧增。面对信息的海洋， 用户试图通过浏览w 曲来发现信息、检索信息已经变得越来越困难，用户往往花费了 很多时间却收获甚少。这时，用户可以通过搜索引擎来帮助检索有用的信息。现有的搜 索引擎如g o o m e 、y a h o o 和i n f o s e e k 等常常返回一个长长的搜索结果列表，用户不得不 逐个的验证这些搜索结果片断是否是他们想要的结果，这是个很耗时的过程。 这个问题的一个解决办法是应用w 曲挖掘技术，对搜索结果进行聚类，使用户可 以按组察看结果。但是，由于h t r p 协议的无状态性，使得搜索引擎不能很好地跟踪用 户的偏好，虽然有些搜索引擎可以对搜索结果打分并按得分的高低呈现给用户，但是一 般没有考虑到用户的兴趣爱好，不同用户对于相同的检索关键词搜索出的信息是相同 的。再者，传统的聚类方法一般不能解决按用户兴趣提供搜索结果的问题。 搜索引擎返回的结果太多且不能根据用户的兴趣提供检索结果是当前较受关注的 问题。本论文把用户兴趣模型和s 1 聚类算法相结合，提出了改进的s t c 算法，并提 出个性化推荐的策略和兴趣描述更新的方法，实现了一个基于搜索结果的个性化推荐系 统( s r p r s ) 。s r p r s 基于改进的s t c 算法自动组织搜索结果，帮助用户利用主题的方式 发现所需的资源。通过实验，分析了s r p r s 系统的聚类特性、时间特性和推荐精度。 针对搜索引擎的列表显示结果，s r p r s 系统在快速查找用户感兴趣的文档上有较好的性 能。 关键词：搜索结果；w 曲挖掘；聚类；兴趣描述；个性化推荐； 郑州大学碗i 学位论史 个基于搜索结果的个性化推荐系统 a b s t r a c t w j t ht h ei n c e s s a n td e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n dn e t w o r kt e c h n o l o g y ，t h e i n f o 册a t i o no ni n t e m e ti si n c r e a s i n gq u i c k ly f a c i n gl a 唱en u m b e r so fi n f o 唧a t i o n ，i ti s a l r e a d ym o r ea dm o r ed i f f i c u l tf o ru s e r st ot r yt of i n da n ds e a r c hi n f o 蛳a t i o nt h r o u 曲 s c a n n i n gw c b t h e yo f t e ns p e n dm u c ht i m e ，b u tg a i nl i t t l e h e r cs e a r c he n g i n e sc a nb e u t i l i z e dt oh e l pt os e a r c hu s e f i l li n f o 硼a t i o n t h ee x i s t i i l gs e a r c he n g i n e s ，s u c ha sg o o 掣e ， y 她o o ，i n f o s k ，o f t e nr e t u ma1 0 n gl i s to fs e a r c hr e s u l t s s dt h eu s e f sh a v et ov a l i d a t e 协o s e s n i p p e t so fs e a r c hr e s u l t so n eb yo n et o 矗n dw h e t h e rt h e ya r et h eo n e st h eu s e r sw a n t ，w h i c h i sat i m e c o n s u m i n gc o u r s e o n em e t h o do fs o l v i n gt h eb e f o r e m e m i o n e dp r o b l e mi sc l u s t c r i n gt h es e a r c hr e s u l t s t h m u g h 印p l y i n gt e c l l i l o l o g yo fw e bm j i l j n g ；i nt h i sw a yt h eu s e r sc a nd e s c r yt h er e s u l t sb y g m u p s h o w e v e r ，a sn o 一s t a t ec h a r a c t e r0 fh t r pp m t o c o l ，s e a r c he n g i t l e sc a i l tt f a c ku s e r s f a v o fp e r f c c t l y 舢t h o u g hs o m es e a r c he n 百n e sc a nm a r kt h es e a r c hr e s u l i sa i i dd j s p l a yi tt o u s e r sb yr a n kt h e yc o m m o n l yd o n tc o n s i d c ru s e r ，si i l t e r e s t s d i f 传r e n tu s e r sg a j nt h es a m e r e s u l t sw i t ht h es 锄eq u e r yk e y s f u r t h e rm o r e ，t r a d i t i o n a lc l u s t e r i n gm e t h o d sc a n ts o l v et h e p r o b l c mo fs u p p l y i n gs e a r c hr c s u l t sb yu s e r si n t e r e s t sc o m m o n ly i ti sar e m a r k a b l ep r o b i e mt h a tt h ea m o u mo fr e s u l t sr e t u m e db ys e a r c he n 酉n e si st o o l a 唱ea n dt l i ee n g i n e sc a n tp m v i d et h eu s e r sw i t hr e q u j r e dr c s u l t sb a s e do nt h e j ri n t e r e s t a n i m p m v e ds t ca l g o r i t h mi sp u tf o r w a r di nt h i sp a p e rb yc o m b i j l i n gu s e 卜i n t e r c s tm o d e lw i t h s t cc l u s t e r i n ga l g o r i t h m h la d d i t i o n ，ap o l i c yo fp e r s o n a l i z a t i o nr e c o m m e n d a t i o na i l da m e t h o do fu p d a t i n gu s e 卜i n t e r e s tp r o f i l ea r ea l s op r o p o s e da tt h es a m et i me ap e r s o n a l i z a t j o n r e c o m m e n d a t i o ns y s t e mb a s e do ns e a r c hr e s u l c ( s r p r s ) h a sb e e ni m p l e m e n t e db yt h eu s eo f t h ei m p r o v e ds t ca l g o “t h m s r p r sc a i lo 唱a n i z es e a r c hr e s u l t sa u t o m a f i c a l ly a n dh e l pt h e u s e r sf i n dt h en e e d e dr e s u l t sw i t ht h es p e c i f i ct o p i c s 。f i n a l l y ，t h ep a p e ra n a l y z e sm ed u s t e r i n g a n dt j m ep m p e n i e so f t h es r p r s b yc x p e “m e n t s i na l l u s i o nt ot h es e a r c hr e s u l t l i s t ，s r p r s h a sab e t t e rp e r f o n l l a n c ei nf a s tf j n d i n gt h eu s e r si t e r e s l e dd o c u m e n t s k - e yw o r d s ：s e a r c hr e s u l t ；w e bm i n i n g ； c l u s i e r i n g ； i n t e r e s tp r o f i l e ； p e f s o n a l i z a t i o n r e c o m m e n d a t i o n ： 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽窃、抄袭等 违反学术道德、学术规范的侵权行为，否则，本人愿意承担由此产生的一切法律责任 和法律后果，特此郑重声明。 学位论文作者( 签名) ：幸易扫伟 少。6 年f 月f 日 郑卅人学硕士学位论文 一个基于搜索结果的个性化推荐系统 1 1 课题的研究背景 第一章绪论 在现代化信息服务环境下，用户的信息需求只趋多元化和个性化，不同的用户之 间存在着明显的个性差异。大规模的生产和服务是工业化时代的一个基本特征。随着 社会信息化进程的加速，个性化的生产和服务开始流行。与标准化的产品和服务相比， 个性的产品和服务更能满足用户的需要，更能提高产品的服务质量，信息技术的发展 使得生产个性化产品及提供个性化服务的成本大大降低，社会经济的进步导致用户的 个性化产品与服务的巨大需求。 a q n i c 发布的统计资料表明，网上信息检索已经占到网络应用的6 5 7 ，成为除 新闻浏览之外人们使用最多的互连网应用【1 1 。搜索引擎是最普遍的辅助人们检索信息 的工具，比如传统的搜索引擎y a l i o o 和新一代的搜索引擎g o o 西e 等。信息检索技术 满足了人们一定的需要，但由于其通用的性质，仍然不能满足不同背景、不同目的和 不同时期的查询请求，很多用户面对搜索出来的成千上万条结果没有一页一页翻找的 耐心，而又不会使用更多关键词帮助缩小搜索范围，这样搜索引擎搜索出来的内容真 正被用户使用的，可能只有最前面很少的一部分，而用户真正感兴趣的内容却不能被 找到。搜索引擎返回的结果太多且不能根据用户的兴趣提供检索结果是当前较受关注 的问题。个性化服务技术就是针对这个问题而提出的，个性化信息服务是指由人类个 体特性所决定的信息需求的一种信息的组合，也就是由人类个性对信息需求的决定关 系产生的一系列对个体有用的信息。个性化信息服务的主要目的就是要为用户提供一 种个性化的信息。个性化信息服务应该是能够满足用户的个体信息需求的一种服务， 即根据用户提出的明确要求提供信息服务，或通过对用户个性，使用习惯的分析而主 动地向用户提供可能需要的信息服务。个性化信息服务是网络信息环境发展的产物， 是信息服务发展的必然趋势。个性化推荐通过收集和分析用户信息来学习用户的兴趣 和行为，从而实现主动推荐的目的。w w w 缓存中的w e b 文档代表了用户当前的兴 趣，利用w e b 挖掘技术对搜索结果和w w w 缓存进行挖掘可以建立搜索结果和用户 兴趣之问的联系。 本课题来源于河南省重大科技攻关项目( 编号0 2 2 2 0 2 0 6 0 0 ) 和河南省优秀中青 年骨f 教师f 2 0 0 3 2 0 0 6 ) 资助项目。 1 2 信息检索技术 c n n l c 发柿的统计资料表明，刚上信息检索已经占到网络应用的6 5 7 ，成为除 第1 叭 郑州大学顾士学位论文 一个基于搜索结果的个性化推荐系统 新闻浏览之外人们使用最多的互联网应用峨搜索引擎的出现，在使用w e b 信息方面 给用户带来了很大的方便。 1 2 1 搜索引擎 搜索弓i 擎是一种用户最为常见的w 曲信息检索系统，其基本思想【l 】【2 】为： 1 、使用r o b o t 来遍历w e b ，将w e b 上分布的信息下载到本地文档数据库中； 2 、然后对文档内容进行自动分析并建立索引： 3 、对于用户提出的检索请求，搜索引擎通过检查索引找出匹配的文档( 或链接) 并返回给用户。 在查询时，用户并不知道搜索引擎的具体的组织形式。最为著名的搜索引擎有 g 0 0 e f 3 】i n f o s e e k 【4 j ，n h e m l j g i l t 【5 】等。 1 2 2 目录 目录，如m o o 【6 j ，与搜索引擎的工作方式不同。文献f 2 】认为，目录不使用r d b o t 下载w 曲文档，而是由人工收集或者由w 曲站点的作者主动提交；目录一般也不对 文档内容进行自动分析和建立索引，而是由人工对w 曲文档进行评价、分类，并给出 简要描述。经过上述处理的w 曲信息资源按照主题分类并以树状的形式加以组织，从 树的根结点逐层向下列出了从一般到特殊的分类及各级子类，而叶结点则包含了指向 w e b 信息资源的链接。用户可以通过浏览目录的分类来查询w 曲信息。当目录中包 含太多的分类和链接时，目录本身也变得不便于浏览。例如，目前y 曲0 0 包含有指向 5 0 0 ，o o o 个站点的链接，分布在2 5 ，0 0 0 个分类中。为此，目录通常也提供检索功能以 方便用户。 搜索引擎和目录这两种w 曲信息检索系统各有所长。通常，由于搜索引擎具有庞 大的全文索引数据库，因此适用于检索难于查找的信息或者一些比较模糊的主题；而 目录有助于逐步缩小主题或者查找某个主题的常见的、质量较高的信息。由于这两种 系统彼此互补，因此一些将两者结合起来的混合系统也开始出现。 另外，还有一种常见的搜索引擎称为元搜索引擎( m e t as e a r c he n g i n e ) ，这类搜 索引擎没有自己的索引数据库，它将用户的查询请求经过预处理后发给多个低层的搜 索引擎，当接到低层成员引擎返回的搜索结果后，元搜索引擎将这些结果按统一的评 分标准进行排序，最后将处理好的结果提供给用户。这类搜索引擎查询的结果比任何 单个搜索引擎覆盖面部大，但是不能充分使用原搜索引擎的功能，用户需要对搜索结 果做更多的处理。 郑州大学硕： - 学位论文一个基十搜索结果的个性化推荐系统 1 2 3 搜索引擎工作原理 虽然各个搜索引擎的具体实现不尽相同，但一般包含5 个基本部分：r o b o t ，分 析器，索引器，检索器和用户接口吼如图1 1 所示。 ，jr 。b o t t 卜一厂、 ，j用户 、一用 。一 分索 索引数据 检 声 析引 索 、1r o b 。 _ 器器 库 r 器 接 、 、 口 1用户 1 图1 1 搜索引擎的基本组成 1 、r o b o t ( 也称为s p i d e r ，c r a w l c f 或w a n d e r ) ：采用广度优先( 或者深度优先) 的 策略对w 曲遍历并下载文档。系统中维护一个超链接队列，其中包括一些起始u r l 。 r o b o t 从这些u r l 出发，下载相应的页面，并从中抽取出新的超链接加入到队列中。 上述过程不断重复直到队列为空。 2 、分析器：对r o b o t 下载的文档进行分析以用于索引。文档分析技术一般包括： 分词、过滤和转换等。 3 、索引器：将文档表示为一种便于检索的方式并存储在索引数据库中。 4 、检索器：从索引中找出与用户查询请求相关的文档。首先采用与分析、索引 文档相似的方法来处理用户查询请求。 5 、用户接口：为用户提供可视化的查询输入和结果输出界面。 w e b 信息是动态变化的，旧的页面不断被更新和删除，新的页面不断出现。因此， r o b o t 、分析器和索引器模块每隔一段时间要重复运行以更新索引数据库。 基于信息检索技术的搜索引擎是资源发现的主要w e b 工具。但现有的许多搜索引 擎还难以令用户满意【7 】 1 、搜索引擎无法覆盖到w c b 的全部信息； 2 、由于w e b 的动态性，搜索引擎的索引中包含许多“断链接”和“过时网页”； 3 、许多有用和相关页面并没有返回给用户； 4 、用户要从返回的大量文档片段中筛选出自己所需的文档： 5 、1 j 同的用户呵能有升i 同的需求； 6 、有时候一些搜索请求往往并不能通过一个关键词来表达： 郑卅f 大学硕二卜学位论文 一个基于搜索结果的个性化推荐系统 7 、同义词和多义词使得问题更加复杂。 1 3 个性化推荐技术 1 3 1 个性化的定义 个性化指的是不同的人和事物具有不同的特征。对物体而言，在材质、形状、颜 色、大小、功能等很多方面存在差异，而对于人来说，每个人在日常生活中都能表现 出与众不同的风格，包括身高外貌、衣着服饰、饮食习惯以及兴趣爱好等等方面，这 些就是个性化的具体表现。正因为有了个性化，世界才能如此多姿多彩。对于w e b 网站来说，每一个光顾网站的用户都有不同的访问习惯和兴趣，从而表现出不同的浏 览行为。商务网站的用户，面对网上不同的商品广告，对每个广告的点击次数、访问 时间和访问频度是不同的。教育网站的用户，面对不同的学习内容，所表现出的学习 兴趣和关注程度也是不同的。如果一个网站的网页内容能够尽可能地根据用户的浏览 兴趣自动调整，从而使得每个用户感觉好像他是网站的唯一用户，则该网站必然能留 住并吸引来更多的用户。这就为每一个网络服务提供者提出了新的要求，即改变过去 对所有用户提供统一界面、同样内容的方式，针对用户不同的兴趣、爱好，提供不同 的服务，朝着w e b 个性化的方向努力。 w e b 个性化即一个w e b 网站根据发现的用户喜好，动态地为用户定制观看的内 容或提供浏览建议i l 】，具体来说，就是网站为上网的每个用户提供一对一的服务和指 导1 2 ，3 】。个性化支持可以分为初级和高级两种方式i4 1 。初级方式是由系统在网页上提供 选项( 如c h e c kb o x ) ，由用户通过选择对网页的形式和内容进行定制。高级形式则是 系统具有主动学习功能，通过概括和分析用户的行为，自动地实现某种程度的个性化。 而后者最直接的实现方式就是当用户上网浏览、访问的时候，由系统自动地向用户推 荐相关的内容和用户可能感兴趣的页面，主动为用户导航【5 8 j 。这种推荐或导航一般应 在服务器端实现，理论上也可以在代理端1 9 _ l o 】和客户浏览器端实现。 1 3 2 个性化推荐的实现方法 支持个性化推荐的技术可以分为四类【l l - 1 3 】：第一类是手工决策技术；第二类是基 于超链接的技术；第三类是基于内容的过滤技术；第四类是协作过滤技术。 1 手工决策技术 手工决策技术足由w e b 站点管理员根据用户统计数、静态个性文件或者会话 ( s e s s i o n ) 历史，制定若干规则，系统根据这些规则为特定的用户提供特定的内容以及 郑州人学硕f 学位论文一个基于搜索结果的个性化推荐系统 网页结构，例如，意大利米兰理工大学开发的t o i 系统【1 4 】及其f i f e n y 等著名系统， 这种系统容易实现，但效率比较低。 2 基于超链接技术 采用基于超链接技术的系统一般使用图论的相关算法来发现给定集合当中最具 代表性或被集合当中其他元素引用最多的元素。采用这种技术的系统如著名的g o o g l e 搜索引擎等。 3 基于内容的过滤技术 基于内容的过滤技术是通过对用户的历史访问内容的分析，向该用户推荐新的类 似的或者相关的内容，其思想是根据用户的访问内容来判断用户的行为和需求【”d “。 例如，向购买过c d 唱机的用户推荐唱盘，向购买过乐器的用户推荐乐谱等等。基于 内容的过滤技术需要对每个用户的访问内容建立文档，同时，要将网站的内容f 如商务 网站中的商品、教育网站的课程内容等) 进行分类，当一个用户访问该网站时，根据该 用户的访问内容文档。查找网站中与该用户内容文档匹配或者相似的类，向用户推荐 该类中的内容。应用基于内容的过滤技术进行个性化推荐具有直接而准确的优点，但 是，在推荐之前需要做大量的分析工作，分析当前用户访问的内容是什么，网站中哪 些网页的内容与之相关等等。这涉及到网页特征的抽取以及所使用语言的语法、语义、 词法的分析等等。例如，确定两篇文章的内容是相关的或者相似的，最合适的方法是 从文章中抽取关键词进行相似性比较，而在目前半结构化或非结构化的网页中抽取特 征向量以及进行特征向量的相似性比较都是比较困难的，在网站中的网页和上网的用 户数量迅速而动态地增长的情况下，这类分析则更加困难。同时，当某个用户的访问 历史较短时，对该用户访问内容的分析也是难以得到正确结果的。 4 协作过滤技术 协作过滤技术所基于的不是当前用户自己的访问历史，而是许多与之具有相同或 相似的访问行为的用户的访问历史，即当一个用户上网浏览时，系统根据其他与该用 户具有相同或相似的访问模式( 访问了哪些网页或者网页中的哪些项) 的用户的访问历 史进行推荐眇”1 ，r i n 9 0 是应用这一技术的一个音乐主题的推荐原型系统l 。在r i n e o 中，系统要求每个用户提供对网站中各音乐主题的点击率( r a t i n g ) ，根据对不同音乐主 题的点击率对用户分组，同一组的用户对相同主题的音乐具有相近的点击率。与基于 内容的过滤技术相比，协作过滤技术对于用户行为的分析更加方便，它所分析的是用 户对于网页或者网页中各项内容的点击率，而非网页内容本身。点击率可以代表用户 的喜好，对棚同网页内容的点击率相近的用户具有相同或者相似的浏览兴趣和访问习 惯，即访问模式，因此可以根据对网页内容的点击率对用户进行分组。当一个用户e 网访问时，根掘其访问模式找到与其对应的组，为其推荐泼组巾点击率较高的网页内 筑5n 郑州大学硕一l 学位论文 一个摹于搜索结果的个性化推荐系统 容。应用这一技术进行推荐时，系统同样需要建立用户访问文档，但其中存储的是各 组用户的访问模式以及点击率较高的网页，而非某个用户的访问内容。对于一个初次 上网的用户，采用基于内容的过滤技术是难以实现推荐的，因为系统中不存在该用户 的访问历史数据。但应用协作过滤技术，系统便可以根据该用户当前的访问模式和对 其他用户历史数据的分析，为其找到相似的访问模式，根据该模式对应的点击率进行 推荐。当然，这也带来了协作过滤技术的一个问题，即一个用户上网的时候，如何根 据其访问模式确定该用户所在的组，这种确定是动态和实时的。因为一个用户浏览的 兴趣将随着其访问目的的不同而改变，在商务网站中尤其如此。例如，一个女性用户， 经常上网为自己浏览和购买计算机方面的书籍，但当她为女儿买书时，将更多地浏览 关于儿童书籍的网页，而为其丈夫买书时，又会更多地关注冶金技术方面的内容。显 然，在这三种情况下，该用户的访问模式是不同的，这就要求系统根据其模式的变化 动态地确定其所在的组，实施不同的推荐策略。同时，对于复杂商品的推荐，协作过 滤技术也是不适合的，因为对这类商品的喜好很难用点击率来衡量，更难以根据点击 率来推荐。例如，对于某一款手机，一些用户喜欢其颜色却不喜欢其功能，因而该手 机颜色的点击率很高，而对另一款手机，许多用户可能满意其功能而不满意其颜色， 这样，其功能的点击率则很高，如果仅仅根据点击率，系统是很难进行推荐的。由于 基于内容的过滤和协作过滤技术各自的特点，目前，已经有一些推荐系统探索将二者 结合的推荐方式，这种方式采用协作过滤的方式对用户分组，采用基于内容过滤技术 进行推荐。 文献【5 】提出了一种交互法的思想。交互法是通过用户与页面的交互，对用户当前 页面进行h t m l 语法分析，收集这些页面的连接，再利用数据挖掘中广泛使用的 t o p n 方法进行个性化推荐。 1 3 3 用户访问信息的收集方法 无论采用基于内容的过滤技术，还是协作过滤技术，要收到好的效果，均需要尽 可能准确地掌握用户的访问行为和浏览兴趣，即收集用户信息。目前，用户信息可以 采用显式收集( e x p l i c i tc 0 1 l e c t i o n ) 和隐式收集( i m p l i c i tc o l l e c t i o n ) 两种方式来进行收 集。 ( 1 ) 显式收集：采用显式收集方式时，要求用户指出自己的浏览兴趣，如喜欢的网 页或者网页中的内容。这是一种直接的信息收集方式，直接来自用户，需要用户的反 馈信息。 ( 2 ) 隐式收集：采用隐式收集方式时，系统通过分析用户的， ：网数据，如浏览的刚 页、贝商的点击情况等，获得刚广。的浏览兴趣。这足。种间接的信息收集方式，它不 郑州人学硕士学位论文 一个基于搜索结果的个性化推荐系统 是从用户的反馈信息中直接获得的，而是从用户的上网数据中分析得到的。 显式收集方式得到的信息直接来自用户，是用户的反馈信息，因而可望及时、准 确，但这需要用户的积极配合，否则，不全面、不及时的信息是难以反映用户行为的。 相比之下，隐式收集方式是通过对用户访问历史数据的分析而得到的，不需要用户的 配合，这样，就避免了用户信息不能及时反馈所带来的问题。但是，隐式收集方式又 带来了另一个问题，即这一方法必须建立在拥有大量用户访问数据的基础上，而且要 从中获得准确的用户信息，动态地生成用户个性文件。在如此巨大的用户数据中获得 可以利用的用户信息，如果没有一种强有力的支持手段和实现技术，实际上是很难做 到的。 1 3 4w e b 挖掘技术对个性化推荐的支持 数据挖掘技术、特别是w e b 挖掘技术的发展为个性化推荐技术注入了新的活力。 w e b 挖掘技术是实现隐式数据收集的一种有效的手段，更是支持基于内容过滤和协作 过滤技术的有力工具。通过w e b 挖掘，可以进行页面内容的相似性分析，从而实现 页面内容的分组，对基于内容的过滤技术给予支持；还可以进行用户访问模式的相似 性分析，从而实现根据访问模式对用户分组，对协作过滤技术给予支持。此外，通过 w e b 挖掘的具体方法，可以获得应用于推荐的相关信息；页面关联分析可以获得用户 经常浏览的页面的相关情况，页面访问量分析可以获得用户对网站中各网页的访问 量，用户访问模式归类可以获得用户按访问兴趣的分组情况，用户分类则可以获得在 用尸，分组基础上，每一组用户准确的类别。总之，通过w e b 挖掘，能够在准确获得 用户信息的基础上，为用户提供个性化推荐服务。 1 4 w e b 挖掘技术 数据挖掘是从大量数据中提取或“挖掘”知识。w e b 挖掘类似于数据挖掘，就是 从与w w w 相关的资源和用户浏览行为中抽取感兴趣的、有用的模式和隐含的信息。 对w e b 进行有效的资源和知谚 发现具有极大的挑战性。w 曲挖掘相对于数据挖掘具 有自已的特点：对有效的数据仓库和数据挖掘而言，w 曲似乎太庞大了；w c b 页面的 复杂性高于任何传统的文本文档；w e b 是一个动态性极强的信息源；w 曲面对的是一 个广泛的形形色色的用户群体；w e b 上的信息只有很小的一部分是相关的或有用的。 利片jw c b 挖掘技术，可以提高搜索引擎获取信息的准确性，并可以对用户搜索结 果进行年廿关处理，力图实现查准率和查全率的有机结合。w 曲挖掘在智能门户搜索引 擎的应用包括有f 2 】f 8 】【9 j ： 郑卅l 大学硕卜学位沦文一个基于搜索结果的个性化推荐系统 1 、文档自动分类。通过w 曲挖掘和机器学习的技术可以对搜索索引数据库中的 信息进行整理，对文档进行自动分类，从而提高用户的检索速度和检索的精确度； 2 、自动文摘的形成。大部分搜索引擎是机械地截取文档，利用w e b 文本挖掘中 的文本总结技术，可以从w 曲页智能地提炼出重要信息形成文档摘要，使用户快速、 方便地了解检索信息； 3 、检索结果的联机聚类。通过检索结果的聚类，可以使与用户检索结果相关的 文档聚类比较靠近。从而远离那些无关的文档； 4 、查询结果的相关度排序。这方面的工作有p a g e r a i i l 【和h u b a u t h o r i t y 方法； 5 、实现个性化的搜索引擎。用户能够根据简短的文档摘要进行判断，发现感兴 趣的内容后会访问该文档。 随着网络信息的爆炸性增长，人们发现对同一问题进行提问，这种搜索引擎往往 会返回给用户成千上万检索到的w 曲页，而其中很大一部分与用户的检索要求无关， 用户在浏览的过程中浪费了大量的时间且慢慢地失去了耐心，搜索引擎开始注重网页 质量和相关性的结合，这主要是通过三种方式： 1 、对网页内容进行聚类，w 曲内容挖掘( w e bc o n t e n tm i n i n g ) ； 2 、是对网上的超链结构进行分析，w 曲结构挖掘( w e bs t r i l c t u r em i n i n 2 ) ； 3 、是对用户的点击行为、访问行为进行分析，w 曲访问信息、w 曲日志挖掘( w 曲 u s a g em i n i n g ) 。 1 4 1w e b 内容挖掘 w 曲内容挖掘是指从w 曲的文件内容及其描述信息中获取潜在的、有价值的知 识或模式的过程。对于文本文档的挖掘称为文本挖掘。大多数基于数据库的数据挖掘 方法经过相应的改进处理后可应用于w e b 文本挖掘。多媒体挖掘主要是指通过对w 曲 上的音频、视频数据和图像进行预处理，应用存储和搜索技术与标准的数据挖掘方法 的集成、对其中潜在的、有意义的信息和模式进行发掘的过程。 1 4 2w e b 结构挖掘 w 曲挖掘是从w w w 的组织结构和衔接关系中推导知识。由于文档之间的互连， w w w 能够提供除文档内容之外的有用信息。利用这些信息，可以对页面进行排序， 发现重要的页面。这方面的：r 作有p a g e r a n k 和h u b a u t h o r j t y 方法。 p a g e r a n k 基本思想：。一个页面被多次引用，则这个页面很可能是重要的；一个页 尽管没有被多次引用，但被个重要页面引用，则这个页面很可能是重要的；一个 笫8 灭 郑州人学硕卜学位论文一个基于搜索结果的个件化推荐系统 页面的重要性被均分并传递到它所引用的页面。对于每个查询，搜索引擎干4 用相似度 函数与页面引用度来计算每个页面的重要性。 h u b a u t h o r i t v 方法基本思想：一个h u b 是指一个或多个w e b 页面，它提供了指 向权威页面的衔接集合。通常好的h u b 是指向许多好的权威的页面；好的权威页面是 指向许多好的h u b 所指向的页面。这种h u b 与a u t h o r i t v 之问的相互作用，可用于权威 页面的挖掘和高质量的w 曲结构和资源的自动发现，这就是h u b a u t h o f i t y 方法的基 本思想。算法h f r s ( h y p e r l i n k i n c l u d et o p i cs e a r c h ) 是利用h u b a u t l l o r i t y 方法的搜索 算法。 1 4 3w e b 使用挖掘 w 曲使用记录的挖掘的主要目标则是从w 曲的访问记录中抽取感兴趣的模式。 w w w 中每个服务器都保留了访问日志，记录了关于用户访问和交互的信息。分析这 些数据可以帮助用户的行为，从而改进站点的结构，或者为用户提供个性化的服务。 w 曲使用记录挖掘的基本流程： 1 、首先对w c bl d g 进行清洗、过滤和转换，从中抽取感兴趣的数据； 2 、建立d a t a c u b e ； 3 、利用成熟的数据挖掘技术进行w 曲分析，理解用户行为和w 曲结构。 1 与w e b 缓存技术 、v e b 缓存技术把经常访问的信息( w e b 文档) 放到用户的附近( 或本地) 。是一种在 本地存储经常访问的信息的方法。用户在附近的w c b 缓存中获取所请求的文件，以代 替从原始服务器获取文件，减少了传输距离，缩短了请求的响应时间、降低了网络带 宽的消耗、减轻了服务器负荷【2 6 _ 3 州。 1 5 1w e b 缓存分类 w e b 缓存是一个提高w 曲性能非常有效的方法，研究表明w 曲缓存命中率可以 达到3 0 一5 0 【1 5 】。它可以位于网络的不同位置：客户端，代理服务器端，服务器端 f 3 】。 根据w c b 缓存所处的物理位置不同，可以分为： 1 、客户端缓存； 2 、服务器端缓存； 3 、代理服务器端缓存。 郑州大学硕十学位沦文 一个基于搜索结果的个性化推荐系统 1 5 2w e b 缓存与传统缓存的区别 高速缓存的思想在计算机系统中有很多应用场合，比如为了提高访问文件系统的 速度而使用的文件缓存，为了提高访问主存的速度而使用的高速缓存等，称这些缓存 为传统缓存。以内存缓冲为例，内存缓冲机制可以提高数据访问性能是由以下两个内 存访问特性决定的：( 1 ) 内存访问的时间局部性( t e m p o r a ll o c a l i t y ) ，最近访问过的数据 对象被重新访问的可能性要高于其它对象；( 2 ) 内存访问的空间局部性( s p a t j a l k c a l i t y ) ，近邻对象被访问的可能性更大。虽然在w 曲中使用的缓存思想与传统缓存 相同，但是由于w c b 自身的特点使得w 曲缓存和传统缓存之间存在着某些区别。这 些区别可以归纳为以下三个方面： 1 传统缓存所缓存的对象大小固定( 以数据块为单位) ，而w 曲缓存所缓存的对 象大小不固定( 以文件为单位) 。这是由于h 1 r r p 协议所支持的是整个文件的传输， 同时w e b 文件在长度上的变化特别大从几k b 到几十m b ，这与文件所携带的信息类 型有关( 比如：文本、图像和视频信息等) 2 传统缓存中获取不同缓存对象的成本基本相同，而w 曲缓存中获取不同缓存 对象的成本可能相差很多。这是由于w 曲缓存对象的获取成本( 可以用下载时间来衡 量) 与链路和服务器相关，所以下载不同对象所花费的时间可能就会不同。 3 传统缓存一般只有很少的程序访问，而w 曲缓存( 除客户端缓存外) 会有很 多的客户访问，通常访问有可能来自于几十到几千个甚至更多的客户。 4 、e b 缓存需要维护缓存一致性( c o n s i s t e n c v ) 。 1 5 3w e b 缓存替换算法 缓存会存在空间不够，当其存储区已被文档占满后，新的文档就无法存储，这时 需要按照事先约定好的某种策略，将一部分当前不再具有存储价值的文档替换出去。 所谓缓存替换策略，就是决定文件进入或被替换出缓存的时机和方式。 客户端缓存常用的替换算法有u t u 算法1 6 】和u u 算法。 1 6 论文目标及创新 本沦文的闷标是在对搜索引擎返回的搜索结果研究的基础上，运用w 曲挖掘技术 和个性化推荐技术，采用内容过滤和文档聚类相结合的方法，对主动向用户推荐感兴 趣的文档进行研究，并实现一个基于搜索结果的个性化推荐系统( s r p r s ) ，在实验 的基础上给出性能评价。 郑州人学硕【j 学位论文一个基于搜索结果的个性化推荐系统 本论文的创新点有： 1 本论文利用内容过滤技术对搜索结果基本聚类进行评估，作为相似度计算的度 量标准。 文【2 5 】中提到的对搜索结果基本聚类的评估是采用比较两个基本聚类，考察它们 包含相同文档的数目，当它们包含相同文档的比率都大于一个预设值时，可以认为两 个聚类相似。这种方法有两个缺点，一个是预设值不容易确定，针对不同的预设值和 实验对象，算法的实验结果差异很大，结果是不稳定的：另一个是没有考虑用户的兴 趣，不能把用户兴趣相关度高的聚类标识出来。本文通过考察用户的兴趣描述和基本 聚类结果，计算每个基本聚类的用户兴趣相关度的评分，如果两个基本聚类评分相近， 则认为两个聚类相似。 2 本论文把用户兴趣模型和s t c 聚类算法相结合，提出了改进的s t c 算法，在 对搜索结果聚类的基础上进行相似度计算和内容过滤，并提出个性化推荐的策略和兴 趣描述更新的方法。 s t c 算法是先对搜索结果建立后缀树数据结构，通过遍历后缀树找出基本聚类， 然后再根据聚类包含相同的文档的比率合并基本聚类；合并基本聚类的算法是两两比 较判断，实际上采用的是聚类算法中层次凝聚法的s i n 甜e “n k 算法。改进的s t c 算 法是在找到基本聚类后，根据基本聚类的用户相关度评分，采用平面划分法中的 s i n g l e p a s s 算法进行合并基本聚类，并根据聚类的“质心”进行排序。 1 7 本论文内容组织 本文主要研究了基于搜索结果的个性化推荐系统的几个关键技术。具体内容安排 如下： 第一章绪论：提出用户在使用信息检索系统时面临的问题，并简要介绍信息检 索技术、个性化推荐技术、w 曲挖掘技术、w 曲缓存技术，课题背景、论文的创新点 及论文的内容组织。 第二章个性化推荐关键技术：讨论一个基于搜索结果的个性化推荐系统中必须 要用到或解决的几个关键技术，如h t m l 解析技术、用户兴趣描述、资源描述方法、 用户兴趣模型、相似性训算。 第三章基于搜索结果的个性化推荐系统设计与实现：介绍基于搜索结果的个性 化推荐系统的体系结构和各部分的设计实现过程。 第四章聚类分析和改进的s t c 算法：介绍了常用的聚类技术并比较了几种常用 的聚类算法的性能，对于基于搜索结果的个性化推荐系统的核心改进的s t c 算法， 给出了具体算法描述和基本数掘结构。 郑卅l 大学硕士学位论文一个基于搜索结果的个性化推荐系统 第五章测试以及性能评价：给出个性化推荐系统的测试结果和系统的性能评价。 第六章结论与展望：论文结论和下一步的工作。 t ；l ! 血 郑州大学坝士学位论文 一个基于搜索结果的个性化推荐系统 第二章个性化推荐关键技术 在基于搜索结果的个性化推荐系统中要解决的技术有很多，本章将就其中的关键 技术进行讨论，包括h t m l 解析技术、用户兴趣描述、资源描述方法、用户兴趣模型、 相似性计算等，是基于搜索结果的个性化推荐系统中必须解决的问题。 2 1h t m l 解析技术 一个面向w 曲的信息系统来说，w 曲文档不像传统的文本那样整齐、干净，其 中包含了大量的耵m l 标记和噪声【2 1 】，例如： 1 、为了增强用户交互性而加入的脚本( s c r i p t ) ； 2 、为了便于用户浏览而加入的导航链接； 3 、出于商业因素所加入的广告链接等。 此外，与传统的文本文档相比，w 曲文档在语义的内聚性上难以得到保证，有时 一篇语义内聚的文章往往分散在若干个w e b 页面中，而在有的时候，一个w 曲页面 中又包含了多个语义无关的部分。这些因素的存在，使得w e b 文档清洗工作具有特别 重要的意义。 h t m l 是超文本标记语言的缩写，是1 9 9 0 年提出的用于书写超文本文档的语言 规范。在其数年的演变过程中，h t m l 基于需求不断地更新，1 9 9 7 年w 3 c 推出了 h t m l 4 o 作为推荐规范，并在1 9 9 9 年1 2 月推出了其更新版本h t m l 4 0 1 。h t m l 解 析的过程是将h t m l 文档的流式数据结构化的过程。 2 1 1 词法分析 根据h 1 m l 的定义，其中词法分析是为了从字符中识别出有意义的符号( t o k e n ) ， 这些符号是h t m l 语法的最小单位。如 与 表示该文档是一个h 聊l 文 档； 与 表示的是一个w 曲文档的头部分，而 与 之间的内 容是w 曲文档的主体部分，其它还包括分隔符 、 、 等。 词法分析的主要过程就是逐字符地读取h t m l 源文件，不断地与系统预先定义好 的t o k e n 进行匹配，一旦匹配成功，就转入相应的语法处理。 如一个典型的h t m l 文档如下： 页面标题 郑州大学颁：l 学位论文 一个基于搜索结果的个性化推荐系统 。 页面内容 例：当系统读取到“ ”，就会知道该文档是用h t m l 语言书写的w 曲文档； 而 表示一个h t m l 文档的结束。 h t m l 标记非常多，而对于一个具体的搜索结果文档来说，并不会用到全部。相 对于浏览器一类的h t m l 分析器，针对搜索结果这种特殊的w e b 文档的词法分析相 应简单了许多。 2 1 2 语法分析 词法分析以后，解析器依据h t m l 语法确定这些符号之间的语法关系，如标签与 标签、标签与文本之间的层次包含关系等等；最后，h t m l 解析器将解析的结果以语 法树的形式输出。 搜索引擎g o o 酎e 一个典型结果文档的页面内容一般为： 搜索结果1 ； 搜索结果2 ； 搜索结果3 ； 搜索结果n ； 传统的语法分析技术很多，基本上分为自顶向下的分析技术( 如递归下降技术) 和 自底向上的分析技术。由于h t m l 的语法比较简单，所以一般采用递归下降技术来做 语法分析。递归下降技术是一种无回溯地自顶向下分析技术，其实现思想是让一个识 别程序由一组过程组成，其中每个过程对应于语法中的一个非终结符号f 在h t m l 语 法中对应各种标签) 。由于语法定义的递归性，这些过程往往是递归过程。 2 2 用户兴趣描述( 用户p r o f f e ) 用户个性化信息又叫用户的兴趣描述( 用户p r o n l e ) ，对个性化服务系统来说， 最重