（计算机软件与理论专业论文）基于协同标记的个性化信息服务.pdf

摘要 互联网上信息的爆炸式增长使个性化的信息服务越来越显得必要。w e b 新应 用社会书签上协同标记的出现为个性化服务的发展提供了新的契机。标签为基于 内容的检索推荐提供了丰富的语义信息，标记行为的协同特性为协同过滤推荐创 造了条件。 社会书签上的协同标记是一件非常具有潜力的新生事物，本文将其与传统的 信息分析技术和个性化信息服务技术相结合，对基于协同标记的信息推荐和组织 管理进行了较为系统化的探索与研究。 本文在对协同标记特性研究的基础上，从三个层次提出了利用协同标记的个 性化推荐算法。首先是基于内容的b t a g 推荐算法，可用于非文本内容的推荐， 且保证了推荐内容的质量。其次，提出了在三阶分析基础上的协同过滤推荐 c u b e r e c 方法，克服了以往协同过滤推荐在多领域多兴趣环境下效果较差的缺 点，其中的分割算法也缓解了协同过滤所面对的数据稀疏性问题。最后是利用社 会书签站点的社会特性进行推荐的u s e r r a n k 算法，该方法模拟市场竞争机制来 计算不同领域下用户的权威性，进而依据用户的权威性差异对推荐内容项排序。 此外，本文还按标签的展示方式，从平板式浏览、标签的聚类、由协同标记 构建层次化的分类体系结构三个侧面分析了协同标记在信息的组织管理上的应 用潜力。 关键字 个性化服务，协同标记，信息推荐，信息组织 中图分类号：t p 3 9 1 a b s t r a c t p e r s o n a l i z e d1 n f o r m a t i o ns e r v i c e sb e c o m em o r ea n dm o r ei m p o r t a n tb e c a u s eo f t h ei n f o r m a t i o ne x p l o s i o n so ni n t e r a c t c o l l a b o r a t i v et a g g i n g ，w h i c he m e r g e sf r o m t h eb r a n d - n e wi n t e r n e ta p p l i c a t i o ns o c i a l b o o k m a r k i n g ，o f f e r sn e wo p p o r t u n i t yf o r p e r s o n a l i z e d i n f o r m a t i o ns e r v i c e t a g so ns o c i a l b o o k m a r k i n gs i t e sh a v er i c h s e m a n t i ci n f o r m a t i o nw h i c hc a nb eu s e df o rc o n t e n t b a s e dr e t r i e v a la n d r e c o m m e n d a t i o n 1 1 1 ec o l l a b o r a t i v ec h a r a c t e r i s t i co ft a g g i n gp r o v i d e sb e t t e rb a s i sf o r c o i l a b o r a t i v er e c o m m e n d a t i o n c o l l a b o r a t i v et a g g i n go ns o c i a l - b o o k m a r k i n gi so n l yo ni t si n f a n ts t a g ew i t hg r e a t p o t e n t i a l s t l l i st h e s i sc o m b i n e di t 、i t i lc o n v e n t i o n a lt e c h n o l o g i e so fp e r s o n a l i z e d i n f o r m a t i o ns e r v i c e s ，a n dm a k e se a r l yb u ts y s t e m a t i c a l l ye x p l o r a t i o no ni n f o r m a t i o n r e c o m m e n d a t i o na n dm a n a g e m e n tb a s e do nc o l l a b o r a t i v et a g g i n g b ya n a l y z i n gt h ec h a r a c t e r i s t i c so fc o l l a b o r a t i v et a g g i n g ，t h i st h e s i sp r o p o s e s t h r e ea p p r o a c h e so fd i f f e r e n tl e v e l sf o rp e r s o n a l i z e dr e c o m m e n d a t i o n t h cf i r s ti s b t a g ，w h i c hi sac o n t e n t b a s e da p p r o a c hb u tc a nb ea p p l i e do nn o n t e x ti n f o r m a t i o n t h es e c o n di sc u b e r e c ，ac o l l a b o r a t i v ef i l t e r i n ga p p r o a c hb a s e do nc u b i ca n a l y s i s t h el a s ti su s e r r a n k w h i c hu s e sm a r k e d - b a s e da p p r o a c ht oc a l c u l a t eu s e r s a u t h o r i t y a n dm a k er e c o m m e n d a t i o na c c o r d i n gt ot a g sm a d eb ya u t h o r i t a t i v eu s e r s b e s i d e sr e c o m m e n d a t i o n , t h i st h e s i sa l s oa n a l y s i st h ep o t e n t i a lo fc o l l a b o r a t i v e t a g g i n go ni n f o r m a t i o no r g a n i z a t i o na n dm a n a g e m e n t i ta n a l y s i sb yt h r e ed i f f e r e n t l e v e l sa c c o r d i n gt ot a g s d i s p l a yw a y ：t h ef l a tb r o w s i n g ，t a g s c l u s t e r i n g , a n db u i l d h i e r a r c h yc l a s s i f i c a t i o nf r o mc o l l a b o r a t i v et a g g i n g k e y w o r d s p e r s o n a l i z e di n f o r m a t i o ns e r v i c e ，c o l l a b o r a t i v et a g g i n g ，i n f o r m a t i o nr e c o m m e n d a t i o n ， i n f o r m a t i o no r g a n i z a t i o n 正 1 1 背景介绍 第一章引言 随着技术与经济的发展，互联网在人们生活中已日渐占据重要位置，它为 信息的发布传播共享提供了非常便捷的方式。这种便利也促使互联网上的信息 极其迅速地增长，以至于要用“信息爆炸”一词来形容。在海量信息的包围中， 人们的注意力越发成为稀缺资源。人们希望把自己有限的注意力放在对自己最 有用的信息上，而不是大量地耗费在寻找和浏览无益信息的过程中。因此，信 息化服务日趋重要，能根据用户兴趣爱好给出有针对性帮助的个性化信息服务 更是备受期待。 在互联网时代之前，图书馆管理员利用图书分类法、索引卡片以及自身的 知识为读者提供信息服务。数字图书馆中也沿用了传统图书管理的方法，通过 专家精心制作的编目和按标准严格添加的元数据来组织管理信息。但清晰有序 的组织管理仍不足以帮助用户从海量信息中迅速找寻自己所需要的内容，按一 定的层次化结构浏览始终是一件费时费力的事，它要求用户对信息的组织结构 有充分的了解。信息检索技术的发展使用户通过输入关键词就能找到想要的内 容，免去了一步步浏览查找之苦。但由于词汇的一词多义性，简单的关键词检 索可能返回众多不同的结果，对应于单词的多个含义，而只有关于某一个含义的 结果是用户所感兴趣的。针对这个问题，人们开始研究个性化检索以帮助用户 过滤其他结果。 尽管信息检索技术发展迅速，但无论是基于元数据的检索还是全文检索， 无论是否提供个性化检索功能，它们都要求用户要输入恰当的关键词。该方法在 用户明确自己要查找的内容时非常有效，当用户只是有一个大概的目的但无法明 确提出关键词时搜索就变得困难了。对于那些用户事先并不知道其存在的有价 值的信息，错过的可能性更是非常之大。检索很难像浏览那样，让用户在无明确 目的的情况下获取新信息。 由此，个性化推荐系统就显得非常必要了。信息服务不仅需要能帮助用户 迅速找到最相关的信息，还需要把有价值的内容主动推送给用户。能根据用户 的兴趣爱好进行有针对性推送的就是个性化推荐系统。 绝大多数个性化推荐都是为用户构建兴趣档案，根据用户以往的行为判断 用户兴趣所在，进而产生推荐。推荐算法主要可分为基于内容的推荐和基于协 同过滤的推荐。基于内容的推荐根据内容上的相似性产生推荐，多数用于文本 信息或有丰富元数据的内容，对于非文本内容能力有限。且它的推荐只能保证 内容的相关性，不能保证其质量。协同过滤的推荐是基于这样一个假设：对已 有信息喜好一致的用户对新的信息的喜好也趋向一致。因此协同过滤推荐分析 用户对他们已知内容的显式或隐式的评分，找出兴趣爱好相近的用户( 称之为邻 居) ，将受邻居好评的信息推荐给用户。协同过滤是依据信息的质量进行推荐， 可用于非文本内容，且推荐具有新颖性。但其往往由于得不到足够多用户的评 分而遭遇冷启动和稀疏性的困难。此外，协同过滤所基于的假设在单领域成 立，在用户有多种不同兴趣的多领域环境下就不那么有效了。 协同标记的出现为进行更方便更精确有效的个性化推荐创造了有利条件。 2 0 0 4 年互联网上出现了社会书签站点。用户将平时浏览网页时看到的感兴趣的 内容收藏到站点上，并添加标签以方便管理及日后的查找。由于添加标签操作 的高度便捷性，及网上收藏夹的有用性，社会书签站点受到了广泛的欢迎，每天 都有大量的信息被收藏并标记。大量的用户标记行为导致了一些非常有趣的协 同的特性，人们称之为协同标记( c o l l a b o r a t i v et a g g i n g ) 。协同标记为数据实体 ( 用u r l 来表示) 提供了丰富的语义信息，且这些语义信息往往是最能描述数 据实体的关键词汇。因而即便是对于非文本内容，协同标记也为使用基于内容 的推荐创造了前提。用户收藏u r l 并对之添加标签这一行为本身就说明了用户 对该u r l 上内容的关注，因此可被看作是一种肯定评分，可被利用于协同过滤 推荐。总之，社会书签站点上协同标记的出现为个性化推荐提供了更丰实的基 础，利用协同标记可设计出同时具备基于内容推荐和协同过滤推荐两者优点并 互补其缺点的混合推荐方法。 协同标记不仅能用于个性化推荐，由于其包含丰富的语义信息，可被视作 一种新的由用户创建的元数据。数字图书馆最初通过专业人士精心刨建编目、 为内容实体添加标准元数据的方式来组织管理信息。但由于专家人数和精力的 有限，这种方法的扩展性和实用性在面对海量信息时受到了挑战。一种替代的 方法是由作者来提供元数据。这种方法要求作者具备d u b l i nc o r e 元数据规范等 知识，能为自己提供的内容用最权威最公认的词汇作出正确描述，这在多语 言、多文化背景的环境中尤其困难。本文所研究的协同标记允许用户按自己的 方式为内容项自由添加标签。虽然这种不严谨的方法会导致标签的多样性甚至 是错误，但由于大量用户的标记行为使之具备协同的特性，通过技术手段有能 力提取出标签中正确有效的部分。这部分信息即可被看作是用户添加的元数 据，可用于组织管理信息。 6 1 2 本文主要贡献 本文的研究在对协同标记深度分析的基础上，提出了三种个性化推荐算 法。 b t a g 方法依据标签分布集中性的特点，通过l s i 技术构造全局的潜在语义 向量空间。再依据标签分布稳定性的特点，用相对稳定的表示算法将所有内容 项和用户兴趣分别映射到该向量空间上。最后在此基础上，通过计算用户兴趣 与内容在向量空问上的余弦相似性来产生推荐。该推荐算法属于基于内容的推 荐算法，但可用于非文本内容的推荐，且推荐内容的质量得到了保证。算法可 灵活地满足用户长期或短期的多个兴趣，用户可使用自己的词汇而不需要学习 全局统一的信息组织结构与表述。 c u b e s v d 方法将高阶奇异值分解技术用于标记行为提供的( 用户，标签， 内容项) 信息。一个用户有多种兴趣、一个标签有多个含义、一个内容项涉及多 个主题，通过三阶分析去除其中的歧义，从而得到了满足用户有多个兴趣的多 领域环境下的协同过滤推荐算法。该方法还依据协同标记的标签分布特性，提 出了张量分割算法以克服协同过滤中的数据稀疏性问题。 u s e r r a n k 方法引入了市场竞争模型，用户的注意力是稀缺资源，可类比为 货币，将用户浏览信息类比为消费行为。用户的标记行为将导致其标记的信息 会被推荐给其他用户，类比为销售行为，若信息也受其他用户好评则该用户会 收益，反之会遭受损失。通过这样的方式来计算用户在特定领域的权威性，进 而产生各个领域的权威推荐。该算法充分发挥了社会性软件的优势，有利于推 荐高质量且具有新奇性的内容。 在信息的组织管理上，本文从标签的展现方式角度，分析了三种利用协同 标记组织管理信息的方法。一是平板式的浏览搜索。通过一些易用性较好的表 现方式，用户同样能从平板式的大量标签列表中迅速找到自己感兴趣的内容， 但它比层次化的体系结构更自由，更符合维特根斯坦“家族相似”理论所表现出 的人们直觉式的思维方式。第二种方法是标签的聚类，并通过标签的聚类将它 们所标记的内容也聚类。它有助于用户发现与自己所用词汇内涵一致但更为一 般与公认的词汇，由此进一步发现相关的内容，往往会有妙手偶得意外发现的 意味。第三种方法是由协同标记构建层次化的分类体系结构。综合广大用户的 标记行为得到最受认同的类别划分及描述方式，通过这样的“自由路径”构建出 最符合大多数用户观点的分类体系结构。 7 1 3 本文结构 本文的组织结构如下：第二章介绍与个性化推荐相关的工作。第三到五章 分别介绍b t a g ， c u b e r e c ， u s e r r a n k 三种推荐算法。第六章对协同标记用于 信息组织进行了分析。第七章为总结与展望。 文中张量用大写字母( a ，b ，) 表示，矩阵用粗体大写字母( a ，b ，) 表示，向量 用粗体小写字母( a b ) 表示，标量用斜体小写字母( 口b ) 表示，常量用斜体大 写字母翻，b ，) 表示。 对于标记行为，本文用“用户”、u s e r 指代标记者，用“标签”、t a g 指代标记 的词汇，用“内容项”、i t e m 或u r l 指代被标记的数据实体。特别的，用u ，t ，e 分别代表单个u s e r ，t a g 或i t e m 。 8 第二章个性化推荐简介 2 1 个性化推荐系统的历史 信息时代互联网上海量信息的存在使用户寻找对自己有用的内容变得越来 越困难，因此人们开始研究如何利用机器学习、数据挖掘、人工智能等技术来 帮助用户克服信息过载的问题。个性化信息引擎、智能软件代理、推荐系统等 陆续被研发用于互联网上众多信息的搜索、排序、分类、过滤和共享。 个性化推荐系统根据用户的需求，自动生成恰当的内容项列表并将之主动 推送到用户面前。它有两个重要特征。一是个性化，它为用户创建独立的兴趣 档案，并根据兴趣档案来生成有针对性的推荐内容项列表。二是主动推送，而 不像信息检索那样仅当用户有明确要求时才将针对用户要求的内容呈现给用 户。它推送的内容不但符合用户的兴趣，还具备一定的新颖性。1 9 9 6 年一场关 于协同过滤技术的研讨会上开始首先使用“推荐系统( r e c o m m e n d e rs y s t e m s ) ” 这个词，并引出了1 9 9 7 年c o m m u n i c a t i o n so fa c m 关于这一主题的特刊 r v 9 7 。 个性化推荐系统得到了信息检索和信息过滤研究领域的关注，早期的著名 系统有t a p e s t r y 和g r o u p l e n s 等。 t a p e s t r y 是x e r o xp a r c 研发的一个具备协同过滤推荐能力的实验性邮件系 统 g n 0 9 2 。它允许用户对信息进行评注( a n n o t a t i o n s ) ，用户可以使用专用的 查询语言t q l 来查找与自己兴趣爱好相近的用户，并根据他们的评注来选择、 过滤信息。该系统是客户服务器两层结构，由索引、文档库、评注库、过滤 器、信箱、发信、评价、浏览等模块组成。由于它的查询语言要求用户之间必 须了解彼此的兴趣爱好，因此只适用于用户群体比较小的场合。 g r o u p l e n s 项目组自1 9 9 2 年开始研究自动协同过滤技术，并将其用于u s e n e t 新闻组 r i s + 9 4 】【k m m + 9 7 】。自动协同过滤技术通过用户的评分计算用户间相 似性，为用户自动搜索最近邻居，再根据最近邻居的评分信息产生推荐，适用 于用户数量比较大的场合。 2 2 个性化推荐系统的应用 个性化推荐系统在互联网上得到了广泛应用，比较典型的有推荐网页的 w e b w a t c h e r a f j + 9 5 】、f a b b s 9 7 】，推荐音乐的r i n g o s 9 4 】、s m a r t 9 r a d i o h c 9 9 】， 推荐电影的b e l l c o r ev i d e or e c o m h s r + 9 5 】、 m o v i e l e n s g s k + 9 9 】，推荐餐馆的移动代理 t s 0 4 等。个性化推荐在电子商务 上更是得到了高度的重视，商业上最为著名的应用有a m a z o n c o r n 的图书评论 及购买推荐m t t p ：w w w a m a z o n c o m ) 、c d n o w 的唱片购买向导 ( h t t p ：w w w c d n o w c o r n ) 等。 s 0 1 】中总结了不同电子商务网站应用推荐系统的六种方式及效果。一是一 般性推荐列表。它的个性化程度最低，甚至不利用用户的个性化信息，只是生 成一个面向大多数人的推荐列表。它有助于帮助新用户熟悉站点。二是针对性 推荐列表。它针对用户的某一些特征生成有一定针对性的推荐列表，用以满足 用户的特殊需求。三是用户评论及评分。它收集用户的评论信息，让其他用户 借鉴以决策自己的购买行为。四是针对性提醒服务。它通过发送有针对性地邮 件等方式将邀请用户频繁访问站点。五是交叉销售推荐。它依据商品之问的相 似性或者关联性进行推荐，将与用户已购买商品有关的商品推荐给用户。六是 深度个性化服务，它通过对用户浏览或购买行为的长期跟踪分析深度挖掘用户 特性并进行推荐。 2 3 个性化推荐算法 个性化推荐系统所用到的推荐算法主要可分为三类：基于内容的推荐，基 于协同过滤的推荐，以及混成的推荐算法。 2 3 1 基于内容的推荐算法 纯粹的基于内容的推荐依据用户定制的兴趣文档将用户可能会喜欢的内容 主动推送给用户，或者通过比较元数据、全文等方式来寻找与用户已浏览或f 在浏览的信息相似的内容。它的主要工作、采用的手段基本接近于信息检索、 信息过滤 b c 9 2 。 2 3 2 协同过滤推荐算法 通常个性化推荐更多采用的是协同过滤的方法。在a c mt o i s0 4 年关于推 荐系统的一期特刊中更是将推荐系统定义为利用社区中其他成员的观点来帮助 社区成员寻找他们各自最可能感兴趣的或最符合他们需求的信息或产品 k 0 4 。 l o t a p e s t r y g n 0 9 2 是最早的协同过滤推荐系统之一。g r o u p l e n s r i s + 9 4 】 k m m + 9 7 是最早的自动协同过滤系统之一。 2 3 2 1 基于用户的协同过滤推荐 协同过滤技术中，u s e r - b a s e d 协同过滤得到了最广泛的应用 s m 9 5 k m m + 9 7 【s k k + 0 0 。它基于这样一个假设：如果用户对一些内容项的喜好一 致，那他们对其他内容的喜好也趋向于一致。它通过如下三个步骤推荐t o p n 项 内容。首先，寻找与目标用户兴趣爱好最接近的k 个用户，称之为k 个邻居。其 次，将k 个邻居喜欢的内容合并，每项内容都有其在该集合中的重要性权重。 最后，将集合中目标用户尚未浏览过的个权重最大的内容项生成列表推荐给 目标用户。b h k 9 8 - - 文通过实验对多种u s e r - b a s e d 的协同过滤推荐算法的效果 进行了比较。 2 3 2 2 基于模型的办同过滤推荐 为了提高u s e r - b a s e d 协同过滤算法的效率和效果，多种m o d e l b a s e d 的协同 过滤算法被相继提出。 b p 9 8 将t o p - n 推荐问题划归成分类问题：喜欢与不喜欢 两类。为每个用户构造一基于神经网络的分类模型。尽管采用了s v d f m m 7 7 等降维技术，该方法的可扩展性仍较差。f b h k 9 8 文中给出了两种m o d e l b a s e d 的算法。一为通过e m d l r 7 7 方法将用户聚类的方法，另一为以内容项为节点 构造贝叶斯网络模型的方法。f h c m + 0 0 提出了一基于d e p e n d e n c yn e t w o r k 的推 荐算法，它对内存的需求和学习的效率都要优于贝叶斯网络。 a w w + 9 9 1 提 出了一种基于图的推荐算法，它将用户作为节点，用节点间的边表示用户间的 关联程度。这种基于图的模型可以找出最近邻算法不能表现出的用户问关联度 的传递关系。 2 。3 2 3 基于内容项的协同过滤推荐 除了以上的m o d e l b a s e d 的算法，另有多种依据寻找内容项之间相似性或关 联规则等i t e m b a s e d 的协同过滤算法被提出。不同于基于内容的推荐算法，此 处内容项的相似性基本是依据用户对内容的喜好来求得的。s m 9 5 在r i n g o 音 乐推荐系统中计算a r t i s t a r t i s t 相似性，以此来预测用户对新的a r t i s t 的喜好程 度。s k k + 0 1 在此基础上进一步比较了多种计算内容项相似性的方法，该文表 明i t e m b a s e d 的推荐算法整体效果要优于u s e r - b a s e d 算法。 m o b a 0 0 从用户们的 网页访问历史中挖掘网页间的关联规则，依据规则表明的访问顺序将后续网页 推荐给用户。 l i n 0 0 的方法与 m o b a 0 0 类似，他们的算法可用于找出数据库中 所有内容项之间的关联规则。 d 0 1 进一步提出了对这些规则计算权重的算法。 d k 0 4 给出了两种计算内容项相似性的模型：条件概率模型和高维模型，文章 提出的算法具有更高的效率，适用于实时推荐且不受u s e r - i t e m 矩阵大小的影 响。 2 3 3 混成推荐算法 协同推荐算法与基于内容的推荐算法相比，具有推荐非文本或无元数据内 容的能力，且其推荐具有新颖性。但协同推荐存在着两个严重问题：冷启动问 题及稀疏性问题。所谓冷启动问题即当新用户初用系统或者新的内容项被加入 到系统中时，由于没有相关的评价信息，因此无法依据评价信息为它们寻找邻 居或相似内容。为此，综合了基于内容的推荐和协同过滤推荐算法优点的混成 式推荐算法被提了出来。 f a b b s 9 7 根据内容维护用户兴趣档案，但利用协同过滤的技术寻找用户 兴趣档案的相似性。为具有相似兴趣爱好的用户生成用户组，对每一组利用基 于内容的信息过滤技术将符合该组用户兴趣的新信息推荐给组。每个用户可属 于多个兴趣组，对单个用户的推荐即若干他所属兴趣组的推荐的综合。该方法 的缺点是不精确的用户兴趣档案描述会导致不正确的分组。 g r o u p l e n s 研究组将过滤机器人( f i l t e r b o r s ) 加入到系统中 s k b + 9 8 】 g s k + 9 9 ，由这些基于内容的机器人为每个新添加到系统中的内容项打分，从 而克服协同推荐算法的稀疏性问题。该方法的优点是这些过滤机器人仅是协问 过滤推荐系统的可选的一部分，系统可依据它们的效果自动选择优质的过滤机 器人。 p r o f b u i l d e r w 9 9 1 同时采用了依据用户评分的协同过滤推荐和基于关键词分 析的推荐两种推荐算法，并将它们的推介列表分别独立呈现给用户。 用于在线新闻推荐的系统t a n g o c g m + 9 9 也同时采用协同过滤推荐和基于 内容的推荐两种推荐算法，并将两者的推荐结果依据它们对用户、文档的权重 以及它们以往推荐正确率综合成一个列表。 p t 0 3 提出了一种基于概念i 蛩( c o n e e p t u a lg r a p h s ) 的推荐算法。该算法通过 用户提供的喜好信息进行预测，因此是一种协同推荐算法。它同时也利用了内 容项的详细信息，因此也是一种基于内容的推荐算法。通过概念图为这两类信 息建模，从而进行混成式的个性化推荐。 1 2 第三章b t a g 推荐算法 基于内容的推荐算法一般只能处理文本信息或者是有充足元数据的信息的 推荐。协同过滤推荐算法依赖于用户对信息的评价，需要用户显示的评分或者 通过技术手段获取用户隐式评分。2 0 0 4 年互联网上诞生的新应用社会书 签，因其广泛流行而为网上的信息提供了大量的标签。这些标签可用于描述被 标记的信息，具有元数据的特性；同时它们又表明用户对被标记的信息感兴 趣，可被视为正面评分。但这大量标签构成的协同标记本身是粗糙、不精确、 具有多样性甚至包含很多错误的，只有在对标签清洗、挖掘出其中潜在的语义 关系，才能真正将其用于个性化推荐。 本章通过分析协同标记的标签分布，得到若干特性。利用这些特性，设计 了清理标签的方法，进而建立向量空间模型表示信息及用户兴趣，并在此基础 上进行个性化推荐。 3 1 相关工作 个性化推荐可被分解为三个关键问题：1 ) 如何描述信息? 2 ) 如何描述用户 兴趣? 3 ) 如何将信息与用户兴趣对应起来? 本节先分别介绍第1 ，2 两个问题的 相关工作，最后介绍l s a 技术_ b t a g 算法采用该技术将信息与用户兴趣映射 到同一空间。 3 1 1 信息的描述 基于内容的推荐或混成推荐都涉及到信息的描述问题。只有通过某种方式 表明信息的内容，才能对其进行基于内容的或混成推荐。对于文本信息，可以 直接以全文或部分关键词作为其描述。对于具有良好元数据定义的信息，如出 版物、c d ，可将元数据信息作为其描述。但对于互联网上的信息，即使针对它 已有定义完善的元数据结构，由于信息数量的巨大，为所有信息标注元数据仍 是一件不现实的事。因此基于内容的推荐或混成推荐在处理互联网上的非文本 或无元数据标记的信息时面l 临着较大的困难。 a n n o t e a ，m e l i t a ，a c e 等系统为用户提供接口，依靠用户力量为信息添加 标注。a n n o t e a k k 0 1 提供了一个基于r d f 的开放式框架，用户可以通过交互 式的方法为网上信g g , j 建形式复杂的标注。m e l i t a c d p + 0 2 也是一个交互式的 标注工具，利用训练数据集中已有的标注规则，它能为用户提供后续输入文字 的建议。a c e b g 0 4 在用户自由输入一段描述文字后，系统依据本体中的合法 表现形式，提出若干标准描述文字的建议，由用户选择其一为信息的标注。 另有很多研究致力于借助字典、本体，通过机器学习等方法为信息自动添 加标注。k e a w p f + 9 9 从文本中自动抽取关键词组，将其作为文本的元数掘。 它首先通过词汇学的方法辨识出若干词组作为候选，为每个词组计算特征值， 再用机器学习的算法来找出最好的关键词组。s e m t a g d e g + 0 3 依据t a p 字典 上列出的所有可能的概念对网页进行标注。b r i n b 9 8 b 提出的标注方式在初始 时系统只有少数标注模式，随后通过对结果的归约不断得到新的模式。 a r m a d i l l o c d g + 0 3 通过对互联网上冗余信息的分析归约出抽取模式的规则。 p a n k o w c h s 0 4 参照本体向g o o g l e 发送与待标注信息相关的查询，对查询结 果进行分析以获取正确的标注信息。c p a n k o w c l s 0 5 控制发送查询的数量 与质量，从而克服了p a n k o w 在本体较大时性能很差的问题。 3 1 2 用户兴趣档案的描述 m l r 0 3 - - 文总结了八种用户兴趣档案的表现方式，分别为：1 1 基于历史的 模型，如a n l a z o n c o m ，c d n o w c o m ，w e b s e l l c b s + 0 1 ，t a p e s t r y g n 0 9 2 等。2 ) 向量空间模型，如w e b m a t e c s 9 8 】；3 ) 加权n g r a m ，如p s u n s m 9 5 b 】；4 ) 加权 语义网络，如i f w e b m t 9 6 ，s i t e i f 【s s 9 8 ；5 ) 加权关联网络，如 r s 9 5 ；6 ) 基于 分类的模型，如 b 9 8 ， k b 9 6 ， b h c 9 8 】：7 ) 用户内容项评分矩阵，如 k m m + 9 7 ；8 ) 特征统计定制，如 k o b s a0 1 】。 在协同过滤推荐算法中，用户兴趣的获得可分为显式与隐式两种方式。显 示的方法有喜欢不喜欢评价 c m z + 0 0 ，评分 8 m 9 5 1 ，文本评论 r i s + 9 4 等。虽 然有研究通过显式评分获得了较好的推荐效果 b s 9 5 1 ，但显式评分存在的一个 严重问题即要求用户评分或给出文字评价对用户本身的浏览行为产生了干扰， p b 9 7 指出即便确实有好处，也只有1 5 的用户会给出评分。此外，用户评分 时的随意性也可能导致评分信息噪音非常大。 隐式的方法通过监视用户行为来猜测用户对信息的喜好程度。隐式评分可 以从用户点击链接 l 9 5 】，购买记录a n l a z o n t o m ，浏览历史 c t s 9 9 m c s 0 0 】， 浏览时间 m s 9 4 k k p 0 1 ，保存、打印网页 k b a 9 5 ，收藏、删除、回复或转 发e m a i l 等获得。通过隐式评分方法的到的用户评价数据比显示评分要密集，且 评分是通过用户非刻意的行为得到的，当评分规则指定得合理时，依据隐式评 分得到的用户兴趣档案进行推荐将会得到较好的效果。但如何制定规则，如何 1 4 保证效率仍是一个有待解决的问题。 3 1 3 l s a 信息检索研究中有两个重要的问题就是同义词与一词多义问题。因这两个 问题的存在，对文档的理想的表现方式不是通过文档中的词汇，而是通过其底 层的、潜在的概念，也即潜层语义信息。由此，利用线性代数手段来抓取潜在 信息的潜层语义分析技术( l a t e n ts e m a n t i ca n a l y s i s ，l s a ) d d l + 9 0 被提出用于信 息检索领域。它通过奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) ，将原来用 词汇向量来表示的文档映射到低维空间。该技术不仅大量节省了存储空间和查 询时间，由于降维后的空间反映了原本数据中的重要联系，而将微小的联系甚 至是噪音都忽略了，因此原本语义上关联密切的词汇、文档距离上更靠近，因 而还提高了信息检索的效果，特别是使用同义词的检索。b d 0 9 5 p r t + 9 7 除 此之外，l s a 还被广泛用于跨语言检索【l d l 9 8 、词汇上下位的自动抽取 c w 0 3 、文本分类 h 0 4 】、写作阅读评分 l p 0 1 】等教育类应用上。也有研究将 l s a 的s v d 与其他数据挖掘等技术结合起来。如【b b 0 3 】利用k 一平均聚类提高 l s a 方法的可扩展性。 信息检索将l s a 应用于“词汇文档”矩阵，在此基础上推广，将l s a 技术用 于“用户商品”矩阵或者“用户内容项”评分矩阵，从而挖掘出用户、商品、内容 项等之间的潜在联系，进而用于协同过滤推荐。【s 硒针0 0 b 】一文通过在电影推 荐系统m o v i e l e n s 上的实验表明l s a 有助于克服协同过滤的稀疏性问题一目有 较好的推荐准确性。 3 2 协同标记标签分布特性 本节通过分析社会书签站点上协同标记标签分布的特性，为后文利用协同 标记的个性化推荐算法建立基础。本节分析的社会书签站点包括d e l i c i o i i s ( h t t p ：d e l i c i o u s ) 和c o n n o t e a ( h t t p ：w w w c o n n o t e a o r g ) 。其中，d e l i c i o t l s 是最为 流行的社会书签站点，其用户群体广泛且数量巨大，每分钟都有几十甚至上百 个用户标记行为发生。c o n n o t e a 是由n a t u r e 开发的专注于科研的社会书签站 点，用户集中在科研学者中，且目前的用户基本为计算机、生物、地理等少数 学科的。用户数量较少，从2 0 0 4 年末开始使用至今，共发生标记行为十万余 次，但被多于一个用户标记的内容项不足两千项。也即目前c o n n o t e a 上的用户 多数是将该站点作为自己研究工作的个人工具，用于收藏管理平时看到的论文 等，但并未将其社会协同特性发挥出来。 3 2 1 在一个u r l 上标签的分布是稳定的 在社会书签站点上，任何信息如文档、音乐、图片，都是以其u r l 来表示 的。一个受到广泛关注的u r l 通常会被不同的用户添加几十个甚至上百个标 签。在这众多的标签中，只有很少一部分是被频繁用到的，并且这少量频繁使 用的标签各自所占的使用比例也逐渐稳定，因此可用它们表示该u r l 。且随着 收藏该u r l 的用户数量的增长，表示将趋向稳定。 百 5 ) - 比 百 分 比 图1 u r l 上标签分布变化图 图1 是d e l i c i o u s 和c o n n o t e a 上的u r l 的标签分布随时间变化图。其中a , b 是d e l i c i o t l s 上的内容项，分别被3 0 6 8 和6 2 4 个人收藏；c , d 是c o n n o t e a 上的内 容项，分别被2 0 2 和9 6 个人收藏。该图表明随时间变化，标签分布日趋稳定。 且收藏人数越多的u r l ，标签的分布越稳定。 标签分布的稳定性说明虽然用户看待事物的角度与侧重点各异，但总有一 些方面是会得到多数用户的共识。这些共识的信息在常用标签上得以表现，从 某种意义上说可以作为内容项的描述，这也是协同标记应用的潜力所在。 3 2 2 频繁使用的标签集是稳定的 社会书签站点上有数量巨大的不同标签是因为用户使用标签的习惯和风格 各异。有使用单数、复数、动名词形式的( 例如t a g ，t a g s ，t a g g i n g ) ，有不同的 1 6 窝蠹 一。 构造合成词方式( 例如t o r e a d ，2 r e a d ，t or e a d ) ，甚至有用到各类特殊符号的( 例 如! i m p o r t a n t ，：n e w s ，* f i c t i o n ) 。但在所有这些标签中，只有很少一部分是被多数 用户共同认可并使用的，其余那些有着明显个人风格习惯的标签只被少数甚至 只有一个用户使用。这个频繁使用标签集合是非常稳定的，并不随抽取u r l 的 样本的变化而有较大波动。因此我们可以通过仅保留频繁使用标签集来表示站 点上信息所覆盖的全部领域范围。 1 1 囊， 数 目1 图2 频繁使用标签数量随u r l 样本数量变化图 观察不同数量内容项样本中频繁标签的数量，可见只有很小一部分标签被大 多数用户共同认可并使用。( a ) 图表明在d e l i c i o u s 的全部1 7 9 2 0 个标签中，使用 频率超过0 5 的只有1 3 个，超过o 0 5 和o 0 0 5 的各只有2 7 9 个和1 5 6 7 个。 ( b ) 图表明在c o n n o t e a 的1 2 1 7 8 个标签中，虽然使用频率超过o 0 0 5 的达到了 3 4 1 8 个且随u r l 的添加仍有增长趋势，但超过0 0 5 和o 5 的都在早期就稳定 在1 2 1 6 和1 9 4 上再没有增长，这也表明了频繁使用的标签是有限的。c o n n o t e a 上标签集中的比例不如d e l i c i o u s 的主要原因是d e l i c i o u s 的用户数量要远大于 c o n n o t e a ，且成分复杂，而c o n n o t e a 的用户基本都为信息学、生物、地理等各门 学科的研究者。因此相比较d e l i c i o u s ，c o n n o t e a 上的用户有更多的共同词汇， 使用的标签一致的可能性也就更大。 表1 随机内容项样本的频繁使用标签集的平均重合率 1 0 02 0 05 0 01 0 0 0 d e l i c i o h s1 6 8 7 4 6 9 0 1 9 6 5 c o n n o t e a1 6 2 7 2 4 9 2 3 9 6 4 进一步的实验表明，频繁使用的标签集中，不但标签数目稳定，且标签本 身也是稳定的，即频繁使用标签集中的标签，并不随抽样u r l 的变化而有较大 不同。表1 是在u r l 抽取样本数目分别在1 0 0 ，2 0 0 ，5 0 0 ，1 0 0 0 时得到的频繁 使用标签集的平均重合率。( 即两个标签机的交集占它们的并集的百分比) 。由 表1 数据可见当样本取1 0 0 0 个u r l 时，已能获得绝大多数的频繁使用标签。 1 7 3 3 协同标记与l s a 社会书签站点上的协同标记为网上内容提供了大量的标签，这些标签是附 加在内容项的丰富语义信息，但要充分发挥其潜能，利用它来改进个性化推荐 的效果，还有很多问题要解决。其中一个主要障碍即标签的多样性。为了表达 同一个意思，用户们可能用到的标签有同一单词的各种变形，同义词，用户自 创的缩写或合成词，甚至是拼写错误。如何清理这些标签，如何挖掘出其中隐 含的更深层次的语义信息，就成为至关重要的问题。本节介绍潜在语义分析技 术，及其在协同标记上的应用。 3 3 1 潜在语义分析技术 基于内容的推荐需要计算内容项之间的相似性。对于文本内容，最直接的 方法是根据词汇在文档中是否出现或出现的次数建立“词汇文档”矩阵，也即以 各个词汇作为特征，获得文档在词汇所表示的空间上的特征向量。再通过余弦 相似性等方法求得文档向量之间的夹角，从而求得文档的相似性。但由于词汇 数量巨大，词汇文档矩阵非常稀疏，该方法存在着可扩展性差的困难。同义词 现象更是严重影响了该方法的精确度，语义上相似但使用不同词汇的文章的相 似性将会很低。 信息检索领域广泛使用潜在语义分析( l a t e n ts e m a n t i ca n a l y s i s ，l s a ) 技术来 解决以上的几个问题。该技术将文档和词汇从原来的向量空间中映射到低维的 语义空间上。在这个空间上数据更为密集，原先空间中的噪音被降低了，有关 联的词汇之间或文档之间的距离更为靠近，它们的潜在语义关系被挖掘了出 来。 l s a 是通过奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) 来实现映射降维 的。由包含了m 个不同词汇的n 篇文档构成的m x h 的矩阵a ，通过s v d 分解得 到a