（计算机应用技术专业论文）基于web客户端数据的个性化推荐技术研究.pdf

独创性声明 删川删 y 18 2 4 8 9 9 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得重庞由电太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 贯签 签字日期： 口o ，年岁月土2 日 学位论文版权使用授权书 本学位论文作者完全了解 重麽童电太堂 有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重庞查e 电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 专蛩 导师签名： 、 缮彤 签字同期： z o d 7 年岁月) z 日签字日期：z o d 年歹月2 2 日 重庆邮人学硕十论文摘要 摘要 随着网络信息的迅速膨胀，人们从w e b 上获取感兴趣信息越来越困 难。因此，为用户提供感兴趣信息的个性化推荐技术获得了广泛关注。 目前个性化推荐技术多数是基于w e b 服务器端数据的，无法从根本上解 决用户难以较好地获取感兴趣信息的问题。而w e b 客户端数据包含单个 用户对多个网站的上网记录，其数据能更好地反映用户兴趣，因此本文 主要研究了基于w e b 客户端数据的个性化推荐技术。 首先，研究了w e b 客户端的用户个性化信息提取。w e b 客户端的用 户个性化信息主要从i e 缓存、i e 历史记录、收藏夹等获取，其中i e 缓 存上网记录较多、数据冗余较大等特点加大了用户个性化信息的提取难 度。针对这一问题，本文研究了基于网页分块的网页正文信息提取方法， 实现了从i e 缓存中提取用户个性化信息。该方法引入网页分块的思想， 通过使用正则表达式，实现了网页内容块抽取及其正文信息提取。实验 结果表明，该方法能够较准确地抽取用户个性化信息，且具有较强的通 用性。 其次，本文分析比较了现有几种基于空间向量模型( v s m ) 表示的用 户兴趣模型，将互信息和层次聚类方法应用于用户兴趣建模。互信息的 引入使用户兴趣模型中兴趣特征之间能够相互关联，而基于互信息的兴 趣特征层次聚类又更好的将关联关系比较强的兴趣特征聚集在一起。实 验结果表明，该用户兴趣模型能够较好地匹配用户感兴趣的信息。 最后，设计并实现一个以用户为中心的基于客户端数据的个性化推 荐原型系统。测试结果表明，该原型系统能够从异构的w e b 客户端数据 中提取用户个性化信息，并根据用户个性化信息进行用户兴趣建模，向 用户推荐其感兴趣的信息。 关键词：个性化推荐，用户兴趣模型，w e b 信息抽取，互信息，层 次聚类 a b s t r a c t w i t ht h em p i de x p a n s i o no fn e t w o r ki n f b 珊a t i o n ，i ti s d i f f i c u l tf o rp e o p l et o 0 b t a i ni n t e r e s t e di n f 0 咖a t i o nf 如mw e b t h e r e f o r e ，w e bp e r s o n a l i z e dr c c o m m e n d a t l o n t e c h n o l o g y ，w h i c hc a i lp r o v i d ei n f o 珊a t i o no fi n t e r e s t f o ru s e r sf e c e l v e de x t e n s l v e a t t e n t i o n m o s tr e s e a r c ho nw e bp e r s o n a l i z e dr e c o m m e n d a t i o nt e c l l i l o l o g y a r eb a s e d o nw e bs e e r ，t h ed i f f i c u l t yo fo b t a i ni n t e r e s t e di n f b 咖a t i o nc a nn o tb e s o l v e d 如n d 啪e n t a l l y c o m p a r e dw i t hw e bs e e rd a t a ，w e bc l i e n td a t ac a n d e s c r i b eu s e r s i n t e r e s tm o r cd e t a i l e d t h e r e f o r e ， t h i s p a p e r r e s e a r c h e s o n p e r s o n a l l z e d r e c o m m e n d a t i o nt e c h n o l o g yb a s e do nw e bc l i e n td a t am i n i n g f i r s t l v ；w e bc “e n tu s e rp e r s o n a l i z e di n f b n n a t i o nr e t r i e v a li ss t u d i e d w e bc l i e n t u s e r sp e r s o n a l i z e di n f o r r i l a t i o ni n c l u d e st h e 正c a c h e ，正h i s t o 嘎f a v o r i t e s ，e t c f e a t u r e so fi ec a c h es u c h 勰d a t ar e d u n d a n c y i n c r e a s et h ed i f f i c u l t yo fu s e r p e r s o n a l i z e di n f b 啪a t i o ne x t r a c t i o n s oaw e bi n f o 加a t i o ne x t r a c t i o nm e t h o d 仃o m i e c a c h eb a s e do nv i s u a lb l o c ks e g m e n t a t i o n i sp r o p o s e dt oe x t r a c tp e r s o n a n z e d i n f o 咖a t i o nf 如mi ec a c h e t h i sm e t h o di s m u c hs i m p l e fo nt h ei m p l e m e n t a t l o n n e e d sn o tc o m p l e xc a l c u l a t i o n e x p c i i m e n tr e s u l tp r o v e dt h a tt h i sm e t h o di s9 0 0 d u n i v e r s a l i t ya i l dc a n o b t a i ni n f 6 m a t i v em e s s a g ea u r a t e l y s e c o n d l v a f t e rc o n s i d e r i n ga d v a n t a g e sa n dd i s a d v a n t a g e so ft y p i c a l r e s e a r c ho n i n t e r e s tm o d e lb a s e do nv e c t o rs p a c em o d e l ( v s m ) ，am e t h o do fi n t e r e s tm e t h o d b a s e do nm u t u a li n f o 吼a t i o na n dh i e r a r c h i c a ld u s t e t i n gi sp r o p o s e d i nt h i sm e t h o d ， t h ei n t e r e s tm o d e l i sd e s c r i b e da sat w o s t o r yt r e e ，a l l dm u t u a li n f 0 肋a t i o nr e n e c t st h e r e l a t i o n s h i pb e t w e e nt h ei t e mi ni n t e r e s tm o d e l ，a n di n t e r e s t h i e r a r c h i c a lc l u s t e r i n g c a ng e tt h ec o l l r e l a t i o ni t e mt o 萨t h e le x p e r i m e n t ss h o wt h a tt h eu s eo ft h ei i l t e r e s ti n t h em o d e lc a nb e t t e rm a t c ht h ed o c u m e n t st h a tu s e ri si n t c r e s t e di n t l l l i r d l y ar e c o m m e n d a t i o np r o t o t y p es y s t e m b a s e do nw e bd i e n td a t a i s p r o p o s e d n ep r o t o t y p es y s t e mc a n e x t r a c tu s e r sp e r s o n a l i z e di n f o 册a t i o n 仃o m h e t e r o 蓦r e n e o u sw e bc l i e n td a t a ， d 0u s e rm o d e l i n gb a s e do nu s e r sp e r s o n a l l z e d i n f o 肌a t i o na n dr e c o m m e n di n f 0 咖a t i o no fi i n e r e s tt ot h e u s e r k e y w o r d s ：p e r s o n a l i z e dr e c o m m e n d a t i o n ，u s e rp r o f i l e ，w e bi i l f o 珊a t i o ne x t r a c t i o n ， m u t u a lh l f o r m a t i o n ，h i e r a r c h i c a lc l u s t e r i n g 重庆邮电人学硕士论文目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究背景1 1 2 国内外研究现状2 1 3 主要研究内容4 1 4 论文组织结构5 第二章个性化推荐技术基础6 2 1 文本信息模型6 2 1 1 布尔模型6 2 1 2 向量空间模型6 2 2 信息论量度。7 2 2 1 信息熵7 2 2 2 互信息8 2 3 聚类分析技术9 2 3 1 聚类阶段9 2 3 2 聚类算法分类9 2 4 本章小结1 1 第三章w e b 客户端的用户个性化信息提取1 2 3 1w e b 客户端数据获取1 2 3 1 1i e 历史记录的获取1 2 3 1 2 收藏夹的获取1 2 3 1 3i e 缓存中网页内容的获取1 3 3 2 基于网页分块的正文信息提取方法1 3 3 2 1 网页正文内容块提取1 4 3 2 2 网页正文提取1 6 3 3 实验与分析1 7 3 4 本章小结2 0 第四章基于互信息和层次聚类的用户兴趣建模2 1 4 1 用户兴趣模型2 1 4 1 1 用户兴趣模型的概念及其特征2 1 4 1 2 用户兴趣模型的表示2 1 m r 一 重庆邮电大学硕士论文目录 4 2 基于互信息的词关联度表示2 3 4 2 1 基于正向乘法的词关联度2 3 4 2 2 互信息在文本处理中的应用2 4 4 2 3 基于互信息的词关联度表示2 5 4 3 基于互信息和层次聚类的用户兴趣模型2 8 4 3 1 用户兴趣模型的描述2 8 4 3 2 引入层次聚类的用户兴趣建模3 0 4 3 3 用户兴趣模型在个性化推荐中的应用3 2 4 4 实验与分析3 3 4 5 本章小结3 6 第五章基于w e b 客户端数据的个性化推荐原型系统3 7 5 1 开发环境3 7 5 2 个性化推荐原型系统的体系结构3 7 5 2 1 用户个性化信息提取模块3 9 5 2 2 用户兴趣建模模块4 0 5 2 3 个性化推荐模块4 3 5 3 原型系统测试4 5 5 4 本章小结4 8 第六章总结及未来工作4 9 6 1 总结4 9 6 2 未来工作5 0 致 射5 1 攻读硕士学位期间从事的主要科研工作及发表的论文5 2 参考文献5 3 i v 重庆邮电人学硕士论文 第一章绪论 1 1 研究背景 第一章绪论 随着网络的迅速发展，w e b 已经成为人们获取信息的重要途径，但 是网络上信息资源分布的广泛性给用户寻找感兴趣的信息增加了困难。 传统的信息搜索是通过像百度、谷歌等搜索引擎来实现的，用户在搜索 引擎中输入关键字，搜索引擎返回给用户大量的与关键字匹配的网页【1 | 。 然而，从搜索引擎返回的搜索结果中，用户感兴趣的信息并不会出现在 搜索结果的最前面，而且有可能返回的结果并没有用户感兴趣的信息， 所以用户查找到真正感兴趣的信息显得十分困难。 如何才能更有效地把感兴趣的信息推荐给用户，早已成为许多用户 及网站制作者共同关注的热点问题。因此，为用户提供有效信息推荐、 帮助用户找到感兴趣的信息的个性化推荐技术在w e b 信息检索领域获得 了广泛关注。个性化推荐技术是指根据用户的兴趣和特点，向用户推荐 感兴趣的信息，不同兴趣的用户得到不同的推荐集【2 1 。在个性化智能推 荐技术中，建立用户兴趣模型是研究是一个重点，这要用个人工智能的 一个重要研究领域一一数据挖掘。数据挖掘技术通过分析用户信息获取 反映用户兴趣的信息。从用户信息获取来源看，个性化推荐技术主要可 分为基于w e b 服务器端数据的个性化推荐技术、基于w e b 客户端的个性 化推荐技术这两类。 基于w e b 服务器端数据的个性化推荐技术是通过使用数据挖掘技术 对w e b 服务器端数据进行分析，获得反映用户兴趣的信息，并向用户推 荐其感兴趣信息。这种基于w e b 服务器的数据挖掘在个性化推荐技术中 起着非常重要的作用，但是也存在一些不足：第一，由于缓存、代理服 务器、防火墙等因素的存在，服务器端的数据通常不够完整；第二，w e b 服务器通常只记录了用户访问单一网站的记录，不能很全面地挖掘用户 兴趣；第三，w e b 服务器存储了多个用户的操作，用户识别是一个难点， 同一个用户可能用不同i p ，同一i p 也可能有不同用户使用。用户识别的 准确性直接关系到个性化智能推荐的效果；第四，基于w e b 服务器端数 据的个性化推荐技术主要目标是改善本网站的服务内容和服务器的性 能。然而，用户通常不会只在单个网站获取信息，当他需要在其他网站 重庆邮电大学硕士论文 第一章绪论 获取信息时，难以获得感兴趣信息的问题依然存在。 基于w e b 客户端数据的个性化推荐技术是通过分析w e b 客户端数据 来获得反映用户兴趣的信息，并向用户推荐其感兴趣信息。与w e b 服务 器端相比，w e b 客户端存放的是单个用户对多个网站的上网记录。因此， 基于w e b 客户端数据的挖掘是针对单个用户的，能够更详细地描述用户 的兴趣。 基于以上情况，本文主要研究以用户为中心的基于客户端数据的个 性化推荐技术。使用数据挖掘技术从w e b 客户端数据中获取反映用户兴 趣的信息，建立用户兴趣模型，从而使用户快速地获得其感兴趣的信息。 1 2 国内外研究现状 目前，个性化推荐的研究主要分为推荐技术的研究、用户兴趣模型 的研究研究两个方面pj 。 ( 1 ) 推荐技术的研究 推荐技术通常可以划分为三个种类，基于规则的推荐、基于内容的 推荐和基于协同过滤的推荐。 基于规则的推荐是根据用户的静态特征和动态属性来制定产生式规 则，通过规则匹配推算出用户还没有浏览过但可能是感兴趣的网页，然 后依据规则的支持度的大小对页面进行排序，将排在前n 项的页面推荐 给用户。基于规则的推荐技术较多地应用于电子商务网站，该推荐技术 根据用户浏览和购买商品的日志生成规则，向用户推荐感兴趣的商品。 基于规则的推荐技术的优点是简单直接，缺点是规则质量很难保证，而 且不能动态更新，此外，随着规则的数量增多，系统将变得越来越难以 管理。 基于内容的推荐是利用页面资源和用户资源的相似性来过滤信息的 技术【4 1 。基于内容过滤的推荐算法【5 】采用矢量空间模型作为用户兴趣和 资源描述模型，使用余弦相似度计算资源推荐度，并且基于效率考虑， 利用朴素贝叶斯分类算法减小搜索空间。基于内容的推荐能通过内容挖 掘来获得详细的用户兴趣描述，不足之处是仅通过用户已有的一些信息 来判断是否与资源相似，无法为用户获得新的兴趣点，只能发现与用户 兴趣点相似的资源。 基于协作过滤的方法是找到相似用户群来推荐相似兴趣页面。基于 2 重庆邮电大学硕士论文第一章绪论 协作过滤的推荐技术的优点是能根据相似用户群发现用户新的兴趣点， 缺点是协作过滤依赖于大量用户对大量资源的打分数据，在没有足够多 的信息情况下，系统很难发现相似用户并对他进行推荐，即新项目冷启 动问题l6 。基于评价矩阵列向量的图书协作过滤算法【7 】主要计算目标资 源之间的相似度而不是用户之间的相似度，可以大大降低计算量，并在 一定程度上克服了稀疏性带来的不利影响，提高了推荐的可信度。 目前多数研究结合了基于内容和协同过滤的两种技术的推荐。基于 内容预测与协同过滤的混合推荐算法利用基于内容的过滤方法，对项目 的内容进行简单的分析，根据用户对项目的评价和项目内容之间的关联， 对用户未评价过的新项目进行初步预测，并利用两种优化策略，过滤预 测不够精确的项目。在此基础上，再应用协同过滤的方法，为用户产生 最后的推荐。该算法提高了传统协同过滤推荐算法的覆盖度，在一定程 度上解决了协同过滤推荐系统的项目冷启动问题。基于内容预测和项目 评分的协同过滤推荐算法【8 l 根据基于内容的推荐计算出用户对未评分项 目的评分，并在此基础上采用一种基于项目的协同过滤推荐算法计算项 目的相似性，随后做出预测。该方法有效地解决用户评分数据极端稀疏 的问题，同时运用基于项目的相似性度量方法改善了推荐的精确性，显 著提高推荐系统的推荐质量。 ( 2 ) 用户兴趣建模的研究 用户兴趣信息获取的目的是获取用户获取信息的行为、用户反馈等 与用户兴趣相关的信息，为用户兴趣模型的建立、更新等提供必要的信 息。如何获取用户的兴趣信息，如何表示用户的兴趣信息，对个性化推 荐系统来说是至关重要的。根据建模过程用户的参与程度区分，用户建 模技术可以分为用户手工定制建模、示例用户建模和自动用户建模【9 1 。 ( a ) 手工定制兴趣建模 手工定制兴趣建模是指用户模型由用户自己手工输入或选择的用户 兴趣建模方法，如用户手工输入感兴趣信息的关键词列表，或者是选择 感兴趣的栏目等。用户手工定制兴趣建模的优点是实现简单，但是也存 在一些问题。第一，兴趣建模过程完全依赖于用户，给用户增加额外的 负担，容易降低用户使用系统的积极性。第二，用户经常不能准确地表 达自己的兴趣，因为用户自己也未必能详尽地列出自己感兴趣信息的关 键词。第三，用户兴趣通常不是固定不变的，由于兴趣模型完全依赖于 用户，因此手工建模往往不能及时更新用户兴趣。 ( b ) 示例用户兴趣建模 3 重庆邮电大学硕+ 论文第一章绪论 示例用户兴趣建模不需要用户列举自己的兴趣，而是提供与自己兴 趣相关的示例，然后通过相应机器学习算法来建立用户模型。与用户手 工定制兴趣建模方法相比，示例用户兴趣建模对用户的依赖更少，构建 的用户兴趣模型也更能全面地反映用户的兴趣和偏好。但是目前的示例 用户兴趣建模方法都仍需要用户的主动参与，严重地干扰了用户的正常 浏览，降低了个性化服务系统的易用性。现有个性化系统不少是使用示 例用户兴趣建模，如使用用户提问方式搜索文件的c i t e s e e r 、由用户提 供示例图片的图像检索引擎l i r a 等。 ( c ) 自动用户兴趣建模 自动用户兴趣建模是在用户没有明确参与的情况下，通过跟踪用户 行为来得到用户的兴趣，即通过隐式反馈来获取用户的兴趣。用户的信 息获取行为，如访问、重复操作、使用、打印保存、删除等，都可以作 为用户的隐式反馈。自动用户兴趣建模无需用户主动参与，因而不会造 成对用户的干扰，有利于提高个性化服务系统的易用性和用户使用系统 的积极性，促进个性化服务的发展。自动用户兴趣建模是用户建模技术 发展的趋势【1 0 】。自动用户建模在不打扰用户正常上网的情况下，通过分 析用户的隐式反馈来发现用户兴趣，从而进行兴趣建模，增强了个性化 服务系统的易用性。但是，隐式反馈存在大量冗余信息，如果不进行适 当的处理会大大增加用户兴趣建模的工作量，从而影响用户兴趣模型的 质量。因此，如何在隐式反馈中抽取用户的真正兴趣特征，随着用户兴 趣变化来更新用户模型是一个非常重要的问题。 1 3 主要研究内容 个性化推荐技术是指根据用户的兴趣为用户提供有效信息推荐，帮 助用户找到感兴趣的信息的技术，不同兴趣的用户得到不同的推荐集。 基于w e b 服务器端的个性化推荐的个性化推荐是以网站为中心的，主要 用于改进网站的功能，以吸引更多的用户，不能完全解决用户在网上难 以获取信息的问题。本文研究以用户为中心的基于w e b 客户端的个性化 推荐，主要内容如下： ( 1 ) 研究了w e b 客户端的用户个性化信息提取，w e b 客户端的用户个 性化信息主要从i e 缓存、i e 历史记录、收藏夹等获取，其中i e 缓存上 网记录较多、数据冗余较大等特点加大了用户个性化信息的提取难度。 针对这一问题，本文研究了基于网页分块的网页正文信息提取方法，实 4 重庆邮电人学硕士论文第一章绪论 现了从l e 缓存中提取用户个性化信息。 ( 2 ) 研究了基于互信息和层次聚类的用户兴趣建模，本文分析比较了 几种基于v s m 表示的用户兴趣模型，结合基于w e b 客户端数据的推荐 的特点，将互信息和层次聚类方法应用于用户兴趣建模中。 ( 3 ) 设计并实现一个基于客户端数据的个性化推荐原型系统，该原型 系统真正实现以用户为中心，通过从异构的w e b 客户端数据中获取反映 用户兴趣的信息，进行用户兴趣建模，从而使用户能够快速从网络中获 取感兴趣信息信息。 1 4 论文组织结构 本文组织结构如下： 第一章绪论，阐述了选题的背景及意义，介绍了w e b 个性推荐技术 目前在国内外的研究现状，并在此基础上引出了本文主要研究内容。 第二章个性化推荐技术基础，阐述了个性化推荐的基础，包括个性 化推荐简介、文本信息模型、信息论量度、聚类分析技术等。 第三章w e b 客户端的用户个性化信息提取，在获取i e 缓存数据、i e 历史记录数据、收藏夹数据等w e b 客户端数据的基础上，本文研究了基 于网页分块的网页正文信息提取方法，实现了从i e 缓存中提取用户个性 化信息。 第四章基于互信息和层次聚类的用户兴趣建模，本文分析比较了几 种基于v s m 表示的用户兴趣模型，结合基于w e b 客户端数据的推荐的 特点，将互信息和层次聚类方法应用于用户兴趣建模。 第五章基于客户端数据的个性化推荐原型系统，设计并实现了基于 客户端数据的个性化推荐原型系统。 第六章结论及未来工作，对本文进行了总结，并探讨了接下来的研 究方向和提出了进一步研究的建议。 5 重庆邮电入学硕士论文 第二章个性化推荐技术基础 第二章个性化推荐技术基础 2 1 文本信息模型 在基于内容的个性化推荐中，文本内容是主要的研究对象。自然语 言表示的文本内容需要转化为机器能够识别和机器能够计算的模型才能 进行进一步的研究。常用的文本信息模型有布尔模型和向量空间模型。 2 1 1 布尔模型 布尔模型是基于特征项的严格匹配模型，首先建立一个二值变量的 集合，这些集合中的变量对应于文本的特征项。文本用这些特征变量来 表示，如果出现某种特征，则特征变量取“t r u e ”；否则，特征变量取 “f a l s e 。文本查询由特征项和逻辑运算符“a n d 、“o r ”和“n o t 组成，文本查询的匹配规则遵循布尔运算的法则。布尔模型的缺点是不 能反映特征对于文本的重要性，缺乏定量分析，并且过分严格，缺乏灵 活性，不能进行模糊匹配。 2 1 2 向量空间模型 向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 最初用于文本的表示，即 把文本映射为一个由二元组组成特征向量( f e a t h e fv e c t o r ) ，如公式( 2 1 ) 所示。 d = 。，m ) ，p ：，w ：) ，o 。，) 】i ( 2 1 ) 其中也，) 1s 七s ，l 是特征气的特征二元组，在兴趣模型中 气 t1 ，2 ，1 ) 为文档中一列互不相同的词条项，m 是词条气的权值。生 成特征二元组包括特征项提取、加权和特征项变换等步骤。特征项权值 表示词条在文本中的重要程度，特征项权值计算方法有布尔权值，频度 权值，t f i d f 权值等。其中t f l d f 权值是使用的最为广泛的特征项权值 计算方法。该方法的主要思想是：一个特征如果在文本中出现得越多， 它就越重要，也就是说它越能标志该文本的特征；一个特征如果在不同 文本中出现次数越多，它就越不重要，也就是说它越不能区分文本之间 6 重庆邮电大学硕士论文第二章个性化推荐技术基础 的特征。常用的t f i d f 公式是如公式( 2 2 ) 所示。 形o ，d ) ：丝垒丝丝丝些( 2 2 ) 、 7 罗【矿o ，d ) l o g ( ，l 。+ o 0 1 ) 】2 、7 其中o ，d ) 为词f 在文本d 中的权重，矿( f ，d ) 为词在文本d 中的词频， 为训练文本总数，l ，为倒置频率，即训练文本集中出现词f 的文本数， 0 ，d ) 表达式的分母为归一化因子。 v s m 的最大优点是在知识表示方法上的优势。在该模型中，文本内 容被形式化为向量空间中的向量，使得文本研究的复杂性大为降低，而 权重的计算容易通过统计的方法自动完成。v s m 把文本以向量的形式定 义到实数域中，极大地提高了自然语言文本的可计算性和可操作性。 2 2 信息论量度 信息论即香农信息论，也称经典信息论，是研究通信系统的极限性 能的理论【1 1 】。信息论量度是全局性度量，将这些度量引入到特征选择和 分类学习中，可以从全局上把握特征相关性、特征与类别相关性的重要 性程度。本文将信息论量度应用于个性化推荐技术中的用户兴趣建模中。 本节主要介绍信息熵和互信息两个信息论量度。 2 2 1 信息熵 在信息论中，把概率分布的不肯定性作为熵的定义。就数据集合而 言，熵可作为数据集合中的不纯度或者说不规则程度的量度，所谓不规 则程度指的是集合中数据元素之间依赖关系的强弱。在介绍信息熵的定 义之前，首先需要了解自信息的定义，自信息定义如下。 自信息定义：设x 代表一组随机而，石：，z 。，其中p ；) 分别是它们 出现的概率，则定义事件t 的自信息为 ；) = 一l o g 足o ；) ，由此可见小概 率时间包含的信息量大，大概率事件包含的信息量小。 自信息公式的导出，使信息的度量成为可能，但它只能表示随机事 件集中某一特定事件五的自信息量，不同事件有不同的自信息量，因此 它不能作为整个时间的总体信息的测度，而信息熵的提出使表征总体信 息测度成为可能。 7 重庆邮电大学硕士论文第二章个性化推荐技术基础 信息熵的定义：离散随机变量x 的信息熵定义为自信息的平均值， 记为h ( x ) ： h ( 石) 。点) 【，o ) 】i 一荟p ( 而) 1 。g p “) ( 2 3 ) 其中，o ) 为事件x 的自信息，辱、表示对随机变量用p o ) 取平均运算； 熵的单位为比特( 奈特) 信源符号。 从信息熵的定义可以看出，熵是属性值概率分布的函数，熵用一个 非负实数描述了属性取值的不确定程度，是一个全局变量，它对于无序 结构来讲用得较多。 2 2 2 互信息 在信息理论中，为了更好地描述事物之间的普遍联系，引进了互信 息( m u t u a li n f o r m a t i o n ) 的概念。对于两个随机变量x 和y ，它们之间在 程度上是相互联系的，即它们之间存在一定的统计依赖关系，互信息量 反映了两个随机变量之间相互依存关系的强弱。 互信息定义：对两个离散随机事件集x 和y ，事件y ，的出现给出关 于事件t 的信息量定义为互信息，( 石；，y ，) ，其定义式【1 2 】如公式( 2 4 ) 所示。 眠幽) = l 。g 掣 ( 2 4 ) 互信息有以下性质： ( 1 ) 对称性，即 ，( x f ，y ，) - ，( y f ，石f ) ( 2 5 ) 该性质表明，由事件y f 提供的有关事件z ，的信息量等于由事件石，提 供的有关事件夕f 的信息量，即表明了两个随机事件z ；和) ，之间的统计约 束程度。 ( 2 ) 当事件相互独立时互信息量为o ，即 ，0 f ，y ，) = 0( 2 6 ) 当事件t 和y ，统计独立时，其互信息量为零。这意味着不能从观测) ， 获得关于另一个事件t ，的任何信息，即表示事件t 和y ，之间不存在统 计约束关系。 ( 3 ) 互信息可正可负。当后验概率p 0 ；iy ，) 大于先验概率p o 。) 时，互 信息量，阮，y ，) 为正值；反之，当后验概率p o ；iy ，) 小于先验概率p o ；) 时， 8 重庆邮电人学硕士论文 第二章个性化推荐技术基础 互信息量，“，y ，) 为负值。 ( 4 ) 任何两个事件之间的互信息不可能大于其中任意一个事件的自 信息量。自信息量， ，) 是为了确定事件t 的出现所必须提供的信息量， 它也是任何其他事件所能提供的关于事件t 的最大信息量。 2 3 聚类分析技术 聚类( c l u s t e r i n g ) 是当前数据挖掘领域中的一个重要分支，在识别数 据的内在结构方面具有极其重要的作用。事实上，聚类是一个无监督的 分类，它没有任何先验知识可用【1 3j 。所谓类，通俗地说，就是指相似元 素的集合。所谓聚类，就是将一个数据单位的集合分割成几个称为簇或 类别的子集，每个类中的数据都有相似性。聚类作为数据挖掘中一个重 要的组成部分，主要用于从潜在的数据中发现有价值的数据分布和数据 模式，作为数据预测、内容检索等方面研究的前期工作。在个性化推荐 技术中，聚类主要用于用户兴趣建模。 2 3 1 聚类阶段 聚类是一种无监督的学习过程，它的主要目的是把没有“标记 数 据分为有意义的“组 。一般来说，聚类技术可以分为以下几个任务阶段： ( 1 ) 数据表示：决定用什么模式来表示数据。这一阶段还包括特征 选择和特征抽取。特征选择是指在所有数据属性集合中选择一个子集来 代表数据。特征抽取则是由现有的数据属性产生新的属性。 ( 2 ) 相似度定义：定义如何表示数据相似度，一般使用的是基于距 离或基于相似度的表示方法。 ( 3 ) 聚类技术：通过多种聚类算法得到聚类。 ( 4 ) 对聚类结果的数据抽象和评估聚类等，此阶段任务可选。 2 3 2 聚类算法分类 ( 1 ) 基于层次的聚类方法 这种方法对给定的数据集进行层次分解，直到某种条件满足为止。 具体又可分为“自底向上”和“自顶向下两种方案。例如在“自底向 9 重庆邮电人学硕士论文第二章个性化推荐技术基础 上 方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的 迭代中，它把那些相互邻近的组合并成一个新的组，直到所有的记录组 成一个分组或者某个条件满足为止。其结果是形成一棵以数据子集为节 点的类别树。层次聚类的代表方法有：b i r c h 、c u r e 、r o c k 等【1 4j 。 b i r c h 引入了聚类特征( c f ) 和聚类特征树的概念，通过对所有叶节点设 定统一阈值来构建聚类特征( c f ) 树，并在各阶段采取不同的阈值来重建， 是一种适应于大规模数据集的聚类算法。c u r e 算法采用了基于质心和 基于代表对象方法之间的中间策率，它选择数据空间中固定树木的具有 代表性的点来代表一个蔟，并将这些点乘以一个适当的收缩因子，使它 们跟更靠近簇的中心。r o c k 通过将聚集的互连性与用户定义的静态互 连性模型来度量两个簇的相似度。 ( 2 ) 基于划分的聚类方法 给定一个有n 个元组或者纪录的数据集，划分法( p a r t i t i o n i n g m e t h o d s ) 将构造k 个分组( k n ) ，每一个分组就代表一个聚类。这k 个 分组满足下列条件：1 ) 每一个分组至少包含一个数据纪录：2 ) 每一个数 据纪录属于且仅属于一个分组( 这个要求在某些模糊聚类算法中可以放 宽) ；对于给定的k ，算法首先给出一个初始的分组方法，以后通过反复 迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好， 好的标准是：同一分组中的记录越近越好，而不同分组中的纪录越远越 好。该方法的典型代表是k m e a n s 算法，p a m 算法，c l a r a 算法， c l a r a n s 算法等。 ( 3 ) 基于密度的聚类方法 基于密度的聚类算法的主要思想就是根据密度来划分类，高密度区 形成类，低密度区划分类。与基于划分方法不同的是，基于密度的方法 没有假定聚类中心，而是根据数据集自身的密度分布探测获得聚类簇， 它可以发现任意形状的簇，而且可以有效去除噪声【1 5 】。也就是说，对给 定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目 的点。这样的方法可以用来过滤“噪声 孤立点数据，发现任意形状的 聚类。基于密度的聚类方法中典型的算法有d b s c a n 算法、0 p t i c s 算 法和k n n c l u s t 算法。d b s c a n 是一个有代表性的基于密度的方法， 它根据一个密度阈值来控制簇的增长，具有发现任意形状类的能力。 o p t i c s 算法不直接产生聚类，而采用可达距离分布图将聚类结构信息表 现出来，避免了其他算法在不了解数据集任何信息的情况下设定输入参 数进行聚类的盲目性。k n n c l u s t 算法利用了k 最近邻的概念，使其获 1 0 重庆邮电大学硕士论文第二章个性化推荐技术基础 得了根据局部密度自动调整聚类参数的能力，减少了对参数的依赖。 ( 4 ) 基于网格的聚类方法 基于网格的聚类方法是指采用一个多分辨率的网格数据结构，将对 点的处理转化为对空间的处理，通过对空间的划分达到数据聚类的目的。 它将数据空间划分成为有限个单元( c e l l ) 的网格结构，并且所有的处理都 是以单个的单元为对象的。但是所有的网格聚类算法都存在量化尺度的 问题。一般来说，划分太粗糙造成不同聚类的对象被划分到同一个单元 的可能性增加( 量化不足) 。相反，划分太细致则会得到许多小的聚类( 量 化过度) 。通常的方法是采用先从小单元开始寻找聚类，再逐渐增大单元 的体积，重复这个过程直到发现满意的聚类为止。改进的基于网格的聚 类算法有基于网格距离的融合式聚类算法( a c g d ) 【1 6 l 、基于最小聚类单元 ( l c c ) 的网格聚类算法【1 7 】等。 ( 5 ) 基于模型的聚类方法 基于模型的方法为每个类假定了一个模型，寻找数据对给定模型的 最佳拟合。这样一个模型可能是数据点在空间中的密度分布函数或者其 它。这种的方法经常基于这样的假设：数据是根据潜在的概率分布生成 的。基于模型的方法主要有两类：统计学方法和神经网络方法。 2 4 本章小结 本章主要讨论了研究个性化推荐所需的相关技术基础。介绍了文本 信息模型，信息论量度和聚类分析技术。文本信息模型将自然语言表示 的文本内容转化向量表示，使机器能够识别和计算。信息熵、互信息等 信息论量度用于发现文本之间的关联关系，能够很好地弥补文本信息模 型信息孤立的缺点。聚类作为数据挖掘中一个重要的组成部分，主要用 于从潜在的数据中发现有价值的数据分布和数据模式，如作为个性化推 荐中用户兴趣挖掘工作。这些知识为后续各章研究作了理论铺垫。 重庆邮电大学硕士论文 第三章w r e b 客户端的用户个性化信息提取 第三章w e b 客户端的用户个性化信息提取 3 1w e b 客户端数据获取 根据收集源的位置和数据特点，w e b 数据可分为服务器端、客户端 和代理服务器端。w e b 服务器端和代理服务器端的数据是日志信息。w e b 客户端数据是用户浏览网页在本地电脑上留下的记录，包括历史记录、 收藏夹、i e 缓存等。 3 1 1i e 历史记录的获取 历史记录中存储的是用户浏览网页的记录，包括时间、统一资源定 位符( u r l ) 、网页名称和对应缓存中的文件名等。在历史记录根目录下， 根据“今天”、“昨天”、“上星期 、“两周以前 、“三周以前 等形成了 一个个子目录。子目录的名称是根据时间来命名的。每个子目录下有一 个i n d e x d a t 文件，用来存放历史信息。i n d e x d a t 是一个二进制文件，是 微软公司制定的特殊文件格式。文件i n d e x d a t 的前1 2 8 0 1 6 个字节放的 是说明信息，然后搜索“u r l ，“u r l 所在的8 字节之后的2 8 个字 节分别放的是时间信息，也就是用户历史记录中的访问时间。因此，在 获取历史记录时，不能简单地用获取常规文件目录的方式，我们可使用 微软公司提供的应用程序编程接口( a p i ) 来获取，主要使用以下两个a p i ： ( 1 ) i u r l h i s t o r y s t gi n t e r f a c e ：当前用户管理历史记录的接口，文本使 用它的e n u m u r l s 方法，该方法返回历史记录集合的一个e n u m e r a t o r 接 口。 ( 2 ) i e n u m s t a t u r li n t e r f a c e ：列举历史记录中的每一条记录，本文 使用它的n e x t 方法，用来逐条遍历历史记录。 3 1 2 收藏夹的获取 用户常常会将自己感兴趣的网页加在收藏夹中。在w i n d o w sx p 系 统中，收藏夹的默认路径是： ：d o c u m e n t sa n ds e t t i n g s f a v o r i t e s 。收藏夹目录采用树形结构，用户可以在根目录底下创建 1 2 重庆邮电人学硕士论文第三章w 曲客户端的用户个性化信息提取 若干个子目录。收藏夹里的每个收藏页面，其实就是一个以u r