（计算机科学与技术专业论文）无线移动环境下图片信息推荐系统的研究与实现.pdf

k一，_ i 。 攀 一 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标记和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：堇 溺 日期：型! 咝主笪! 至鱼 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅 和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印 或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密 论文注释：本学位论文不属于保密范围， 本人签名：茎 茧 导师签名： 焉授笔蒜神2 日日期：圣型竖圣笪! 兰鱼 日期：让2 砗三笪13 臼 _ 、 无线移动环境下图片信息推荐系统的研究与实现 摘要 随着信息的急剧膨胀，推荐系统在用户浏览中扮演着越来越重要 的角色。对移动设备用户而言，如何快速而高效的共享和浏览图片对 于移动设备的推广非常重要。目前绝大多数的推荐系统可分为三类： 基于内容的推荐系统，基于用户协作的推荐系统以及混合型推荐系 统。基于内容的推荐系统在众多领域有着广泛的应用，包括网页推荐， 文章推荐，餐馆推荐，电视节目推荐等，因此也一直推荐系统研究的 热点方向。典型的基于内容的推荐系统通常使用贝叶斯分类算法实现 对象的分类排序，通过对系统中的所有对象进行分类排序，再结合当 前用户的喜好，选择出用户可能喜欢的对象向用户推荐。 传统的基于内容的推荐系统对一类对象进行分类，得到的对某一 类对象的推荐排序是一致的结果。这种分类方法的一个缺点是忽视了 同一类对象之间的差异性。为了在推荐系统中综合考虑图片的多种属 性信息，需要设计新的基于内容的推荐系统，通过把对象的特性关系 映射到带权限的无向图中，实现对每个对象生成独有的推荐排序。这 样的推荐系统的特点是专门针对用户当前正在浏览的对象进行推荐。 如何确定图片的不同元数据对图片相似性的影响，是设计满足课题目 标的推荐系统的主要问题，同时在系统中的需要实现图片数据获取， 用户管理等方面的服务，这些都是完善k a l e i d op h o t o 软件功能的重 要环节。 论文首先介绍了与课题相关的背景技术，包括w e b 服务技术， r e s t f u l 技术，推荐系统技术和基于推荐内容的推荐系统技术。着重描 述了本文中使用的基于语义关系图的推荐系统技术。在此基础上，论 文重点讨论了在针对移动用户的图片共享系统k a l e i d op h o t o 中的图 片推荐系统的设计与实现。论文介绍了k a l e i d op h o t o 服务器的架构， 并对其中的图片上传服务，用户管理服务和推荐服务三个服务进行了 需求分析，搭建了实现服务器端的体系结构，并详细描述了各服务的 接口和具体实现方式。 然后，论文给出了k a l e i d op h o t o 中图片推荐系统的测试环境和 测试结果。最后对全文进行了总结，分析了研究中的不足并指出了今 后研究工作的方向和下一步需要做的工作。 关键词语义关系图移动业务推荐系统 r e s e a r c ha n di m p l e m e n t a t i o no f p h o t oi n f o r m a t l 0 nr e c o m m e n d a t i o n s y s t e mf o rm o b i l ee n v i r o n m e n t a bs t r a c t a l o n gw i t ht h ee x p l o s i o no fm o d e mi n f o r m a t i o n ，r e c o m m e n d a t i o n s y s t e m sa r ep l a y i n ga l li m p o r t a n tr o l ei no u rd a i l yl i f e f o rm o b i l ed e v i c e m a n u f a c t u r e s ，h o wt of a s ta n de f f e c t i v e l ys h a r ea n db r o w s ep h o t o si sa k e yf a c t o r f o r t h e p r o m o t i o n o fm o b i l ed e v i c e s m o s t c u r r e n t r e c o m m e n d a t i o ns y s t e m sc a nb ed i v i d e di n t ot h r e ec a t e g o r i e s ：c o n t e n t b a s e dr e c o m m e n d a t i o ns y s t e m s ，c o l l a b o r a t i v er e c o m m e n d a i o ns y s t e m s a n dh y b r i dr e c o m m e n d a t i o ns y s t e m s c o n t e n tb a s e dr e c o m m e n d a t i o n s y s t e m s a le w i l d l y u s e di nm o d e m i n d u s t r i e s ，i n c l u d i n g w e b r e c o m m e n d a t i o n ，a r t i c l er e c o m m e n d a t i o n ，r e s t a u r a n tr e c o m m e n d a t i o n ， a n dt vs h o w sr e c o m m e n d a t i o na n ds oo n a n di t i sah o tr e s e a r c h d i r e c t i o no fr e c o m m e n d a t i o n r e s e a r c h e s t y p i c a l c o n t e n tb a s e d r e c o m m e n d a t i o ns y s t e m su s ec l a s s i 研n ga l g o r i t h m sl i k eb a y e sc l a s s i f i e r t oc l a s s i f yi t e m si n t os e v e r a ld i f f e r e n tg r o u p s t h e yt h e ns o r ta l li t e m si n e a c hg r o u pa n dm a k er e c o m m e n d a t i o n s a c c o r d i n gt h er a n k i n gl i s ti ne a c h g r o u p c o n v e n t i o n a lc o n t e n tb a s e dr e c o m m e n d a t i o n s y s t e m sm a k e a r a n k i n g l i s tf o ra g r o u po fs i m i l a ri t e m sa n dg e n e r a t et h es a m e r e c o m m e n d a t i o n sf o ri t e m si nt h es a m eg r o u p o n ed r a w b a c ko ft h e a p p r o a c hi st h a ti ti g n o r e sd i f f e r e n c e sb e t w e e ni t e m si nt h es a m eg r o u p i no r d e rt om a k eu s eo ft h er i c hm e t a d a t ai n f o r m a t i o no f p h o t o s w en e e d an e wd e s i g no ft h ec o n t e n tb a s e dr e c o m m e n d a t i o ns y s t e m w ef i r s tm a p r e l a t i o n sb e t w e e ni t e m st oa nu n d i r e c t e dw e i g h t e dg r a p ha n dt h e nm a k ea r a n k i n g 1 i s tf o re a c hi t e mi nt h e g r a p h t h ep r o p o s e dc o n t e n t r e c o m m e n d a t i o ns y s t e mm a k e sr e c o m m e n d a t i o n sb a s e do nw h i c h p h o t o t h eu s e ri sc u r r e n t l yv i e w i n g h o wt od e t e r m i n et h ei n f l u e n c eo fe a c h m e t a d a t ao v e rt h er e l a t i o n s h i po fe a c hp a i ro fi t e m s ，i st h ek e yp r o b l e m t h ep a p e rt r i e st or e s o l v e m e a n w h i l e ，s o m eo t h e rs e r v i c e sa r ea l s on e e d e d t oe n r i c ht h ef u n c t i o n a l i t yo fk a l e i d op h o t os o f t w a r e t h ep a p e rf i r s ti n t r o d u c e ss o m er e l a t e db a c k g r o u n dt e c h n o l o g i e s ， 产 i n c l u d i n gw e bs e r v i c e ，r e s t f u l ，r e c o m m e n d a t i o ns y s t e m so v e r v i e wa n d c o n t e n t b a s e dr e c o m m e n d a t i o n s y s t e m s t h e n i t d e s c r i b e s t h e ! s e m a n t i c r e l a t i o n - g r a p h b a s e dp h o t or e c o m m e n d a t i o ns y s t e m a f t e rt h a t ， w es h o w s o u r d e s i g n a n d i m p l e m e n t a t i o n o ft h e p r o p o s e d r e c o m m e n d a t i o ns y s t e mi nk a l e i d op h o t oi n d e t a i l s ，i n c l u d i n gp h o t o u p l o a d i n gs e r v i c e ，u s e rm a n a g e m e n ts e r v i c ea n dr e c o m m e n d a t i o ns e r v i c e t h e nw el i s to u rt e s t i n ge n v i r o n m e n ta n dt e s t i n gr e s u l t s a tl a s t ，w e c o n c l u d eo u rw o r k ，d i s c u s so u rw e a k p o i n ta n dp o i n to u t o u rf u t u r ew o r k k e yw o r d ss e m a n t i cr e l a t i o ng r a p h ，m o b i l es e r v i c e ，r e c o m m e n d a t i o n s y s t e m s ， 目录 第一章绪论1 1 1 课题背景 1 2 论文研究内容与工作 1 3 论文结构 第二章技术背景 2 1w e b 服务 2 1 1 传统w e b 服务 2 1 2r e s t f u iw e b 服务 2 2 推荐系统技术 2 3 使用语义关系图的基于内容推荐系统 2 4 本章小结 第三章使用语义关系图的推荐系统算法设计 3 1 算法设计背景 3 2 算法概要 3 3 生成单维度的语义关系图 3 4 生成全维度的语义关系图 3 5 生成图片推荐列表 3 6 本章小结 第四章k a i e i d op h o t o 中推荐系统服务器的设计与实现 4 1k a i e i d op h o t o 软件的需求分析 4 2k a i e i d op h o t o 服务器架构设计 4 3 系统的详细设计 4 3 1 图片上传服务详细设计 4 3 2 用户管理服务详细设计 4 3 3 使用语义关系图的图片推荐服务详细设计 4 4 本章小结 第五章系统测试 5 1 测试原理和测试步骤 5 1 1 测试原理 5 1 2 测试步骤 5 2 测试环境 v 一 5 3 功能测试4 9 5 3 1 图片上传服务功能测试4 9 5 3 2 用户管理服务功能测试5 2 5 3 3 推荐服务功能测试5 4 5 4 容错性测试5 5 5 5 性能测试5 6 5 6 本章小结5 7 第六章结束语5 8 6 1 全文总结5 8 6 2 下一步研究工作5 8 6 3 研究生期间的工作5 8 参考文献6 0 附录6 1 缩略语索引6 1 致谢6 2 v i 1 _ 产 1 1 课题背景 第一章绪论 近年来，随着移动终端处理能力的提升，以及无线网络带宽的增长，无线移 动业务蓬勃发展，越来越多的移动用户通过移动终端设备享受移动业务。这其中， 图片共享业务在移动设备的应用中占有非常重要的位置。同时，随着现代信息的 急剧膨胀，用户拥有的图片越来越多，移动用户在面对大量图片的时候需要一个 合适的浏览方式。这为移动设备图片共享服务的设计和开发提出了新的需求。 为了满足新业务的需求，我们在开发和部署移动设备上的图片共享服务的时 候需要解决以下几个主要问题： 如何合理地组织和管理移动用户的图片； 如何快捷地存取用户的图片； 如何有效地向用户呈现图片； 如何高效地把图片与图片，图片与其他用户关心的资源联系起来； 课题“k a l e i d op h o t o ”就是要解决上述问题，提供一种快速便捷的方式帮助移 动设备用户管理、共享和浏览图片。论文依托的课题是由北邮诺基亚联合实验 室资助的一个基础应用研究课题，论文的工作重点是探索新的图片共享和管理方 法，研究未来移动设备上的图片共享业务。课题的目标是在移动环境下向用户提 供方面快捷的图片共享策略和管理方法，并实现原型。 1 2 论文研究内容与工作 论文是课题“k a l e i d op h o t o ”的一个子课题。论文的主要研究内容是寻找一种 合理利用图片元数据向用户推荐相关图片的方法和系统架构。不同于文本信息获 取，图片的元数据包含了非常丰富的信息，可以为我们寻找更准确的图片推荐方 法提供便利。 语义关系副1 】是图像获取领域的一种数据组织方法，它把图片的属性关系映 射到一个属性关系图中，从而获得一种快速的图片查询方法。本文把语义关系图 的组织方法运用到推荐系统中，把图片的元数据映射到一个带权值的无向的语义 关系图中。再根据这个语义关系图，对每个图片生成独有的推荐列表，从而实现 了利用多种元数据提供合理推荐图片的目的。 在设计和实现中，使用表述性状态转移( r e p r e s e n t a t i o n a ls t a t et r a n s f e r ， r e s t ) w e b 服务框架设计服务器架构，同时借鉴日志分析系统的架构设计思想， 使用主从数据库存放数据，从从数据库读入数据生成语义关系图和推荐列表，从 而实现服务器的简单高效以及高扩展性，同时降低推荐系统对k a l e i d op h o t o 服 务器的其他服务的性能影响。 在该课题中，论文作者的具体工作包括： k a l e i d op h o t o 服务器架构设计，提出适合软件需求的服务器架构和服务 通信方式； 用户管理服务的设计与实现，实现服务软件需求的用户注册，认证和用 户信息管理机制； 图片上传服务的设计与实现： 图片推荐索引服务的设计与实现，设计实现合理利用图片元数据生产推 荐图片列表的方法； 1 3 论文结构 论文的结构和主要内容安排如下： 第一章绪论，介绍课题背景和论文的主要研究和工作内容，以及论文的结构。 第二章介绍与论文相关的背景技术，包括w e b 服务技术、s o a 技术、服务 组合技术的概念、原理和相关标准，还分析了与移动业务标准制定组织o m a 的 相关标准。 第三章设计一种移动环境下的服务组合机制，通过形式化的描述来阐述该机 制的主要思想。还给出了服务组合关键元素“组件”和“构件”的定义、多维服务的 含义，以及利用该机制部署新业务的过程。 第四章介绍在服务组合机制基础上如何实现移动业务t r a v e lg u i d e 的服务器 端功能。包括对业务的需求分析、系统的总体设计、构成业务的组件和构件的详 细设计、对服务进行组合的b p e l 业务流程设计。 第五章给出了验证移动环境多维服务框架中实现的服务组合机制的测试目 标、测试用例和测试结果，对测试结果进行了分析。 第六章对整篇论文进行总结，提出了下一步改进和完善的方向。最后列出了 论文作者在硕士研究生期间的工作情况和取得的成果。 2 1w r e b 服务 第二章技术背景 w e b 服务是一种适用于松耦合的分布式环境的应用程序开发和部署的方式， 也可称作一种部署在网络上的对象。它具有一些面向对象技术的特点，如抽象定 义，封装，通过接口与外界联系等。同时，为了满足异构网络环境中跨平台的调 用，w e b 服务还具有自包含、自描述、松耦合、接口与实现技术分离等重要特性 【2 】 o 当前的w e b 服务可以大致分为两类：传统w e b 服务( b i gw e bs e r v i c e s ) 和 r e s t f u lw e b 服务p j 。 2 1 1 传统w e b 服务 传统w e b 服务是指传统的使用简单对象访问协议( s i m p l eo b j e c ta c c e s s p r o t o c o l ，s o a p ) ，w e b 服务描述语言( w e bs e r v i c ed e s c r i p t i o nl a n g u a g e ，w s d l ) 和统一描述、发现、集成协议( u n i v e r s a ld e s c r i p t i o n ，d i s c o v e r ya n di n t e g r a t i o n , u d d i ) 实现的w e b 服务，通常用于大型的企业级应用。传统w e b 服务通过发 布发现绑定的流程向w e b 服务的请求者提供服务，其体系结构如图2 1 所示。 色： 图2 1w e b 服务体系结构 这种体系结构中包含了服务提供者、服务请求者和服务注册中心【4 】三种角 服务提供者：发布服务，并对使用自身服务的请求进行响应； 服务注册中心：也被称为服务代理，用于注册已发布的服务，并且对其 进行归类，提供索引查找； 服务请求者：向服务注册中心查找发现所需的服务，根据服务描述与服 务进行绑定( 确定通信方式) ，然后调用。 传统w c b 服务使用到了s o a p ，w s d l 和u d d i 三种开放的标准协议。其中 s o a p 是由万维网联盟( w o r l dw i d ew e bc o n s o r t i u m ，w 3 c ) 制定发布的基于可 扩展标记语言( e x t e n s i b l em a r k u pl a n g u a g e ，x m l ) 的不依赖传输协议的表示层 协议。s o a p 定义一个x m l 文档格式，该格式描述如何调用一段远程代码的方法。 s o a p 定义了一种简单的机制，用一个模块化的包装模型和对模块中特定格式编 码的数据的重编码机制来表示应用的语义。这样，s o a p 可以支持远程过程调用 ( r e m o t ep r o c e d u r ec a l l ，i 冲c ) 类型的通信方式，同时也支持文档类型( 面向 消息) 的通信方式。s o a p 解决了互联网中分布式计算所存在的互操作性问题， 成为了传统w e b 服务的消息传递机制。 u d d i 是用于传统w e b 服务注册和发现的基于x m l 的协议，最初由i b m 、 m i c r o s o f t 和a r i b a 公司提出，并由结构化信息标准促进组织( o r g a n i z a t i o nf o rt h e a d v a n c e m e n to fs t r u c t u r e di n f o r m a t i o ns t a n d a r d s ，o a s i s ) 标准化。u d d i 协议定 义了w e b 服务注册中心的s o a p 接口。 w s d l 是由w 3 c 组织制定的用于w e b 服务描述的规范，是一个描述w e b 服 务的x m l 词汇表。它定义了一种x m l 语法，包括w e b 服务的名称、它的方法 的名称、这些方法的参数和其它详细信息等，用一种与实现语言无关的方式对 w e b 服务的详细信息进行描述。 2 1 2r e s t 如lw 曲服务 r e s t 架构是由r o yf i e l d i n g 在2 0 0 0 年创建的一种分布式多媒体软件架构。满 足r e s t 架构的w e b 服务被称作r e s t f u lw e b 服务。r e s t f u lw e b 服务通过超文本 传输协议( h y p e r t e x tt r a n s f e rp r o t o c o l ，h t t p ) 的p u t ，g e t ，d e l e t e 和p o s t 四种方法实现w 曲服务，并且不依赖x m l 或者w s d l 报务接口定义【5 j 。 r e s t f u l 类型的w e b 服务需要满足六个约束条件【6 】： 客户端服务器结构； 服务器无状态，每条从客户端发送的请求都包含了服务器处理这条请求 所需的全部信息。； 可缓存，客户端可以缓存请求的结果； 服务器是一个分层的系统，客户端不知道自己是否是和最终服务自己的 服务器在通信。 随需应变的代码( 可选) ，服务器可以选择 统一的外部接口 r e s t f u lw 曲服务降低了w 曲服务开发的复杂性，提高了系统的可伸缩性。 基于r e s t 构建的系统其系统的扩展能力要强于s o a p ，这体现在它的统一接口 抽象、代理服务器支持、缓存服务器支持等诸多方面。由于其简单高效易于扩展 的设计原则，这种服务架构在互联网公司很受欢迎，r e s t f u lw 曲服务也成为 w e b 服务的一个重要架构实践领域。 典型的r e s t f u lw 曲服务是一个分层的应用环境，与大部分传统的w e b 应用 程序一样，w 曲服务可以从多层架构的关注点分离中受益【_ 7 1 。业务逻辑和数据可 以与客户端共享。此外，从数据访问中分离业务逻辑可实现数据库独立性，并为 各种类型的数据存储提供插件能力。图2 2 描述了一个典型的i 也s t 如l 服务应用框 架，其中客户端可以使用各种脚本语言，如j a v a 、p y t h o n 、p e r l 、r u b y 和p h p 等 实现，客户端向应用服务层的资源请求处理逻辑( r e s o u r c er e q u e s th a n d l e r ) 发 送h t t p 请求。客户端的无状态请求在头部包含方法信息，即p o s t 、g e t 、p u t 和d e l e t e ，这又将映射到资源请求处理逻辑中资源的相应操作。每个请求都包 含所有必需的信息，包括资源请求处理逻辑用来处理请求的凭据。 liil lill liii 厂 i 霹户螭翳l i 。j 洌蹙器涟求 鲎匕l 要逻辑 ii - i 圈l 圈 r ! l 敬镪稃储翳l 1一 图2 2 r e s t f u l 应用框架图 r e s t l e t 是一套基于j a v a 平台的开源开发框架【8 】。r e s t l e t 提供了一套符合 r e s t 架构的开发库，十分便于r e s tw e b 服务开发。r e s t l e t 使用n e o l i o s 引擎 ( n o e l i o sr e s t l e te n g i n e ，n r e ) 作为核心服务引擎。r e s t l e t 框架包括r e s t l e t 应 用程序编程接口( a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ，a p i ) ，扩展，服务插件接1 2 1 ( s e r v i c ep l u g i ni n t e r f a c e ，s p i ) ，和r e s t l e t 实现四个部分，其架构图如图2 3 所示。 5 2 2 推荐系统技术 应川程序 r e s t l e t 应川程序编程 援u 扩碰 r e s t l e t 服务桴序编棵 接阴 r e s t l e t 炱现 图2 3r e s t l e t 框架图 目前绝大多数的推荐系统可分为三类【9 】：基于内容的推荐系统 ( c o n t e n t b a s e dr e c o m m e n d a t i o ns y s t e m s ，c b r s ) ，基于用户协作的推荐系统 ( c o l l a b o r a t i v er e c o m m e n d a t i o ns y s t e m s ，c r s ) 以及混合型推荐系统( h y b r i d r e c o m m e n d a t i o ns y s t e m ，h r s ) 。基于内容的推荐系统向用户推荐与该用户之前 浏览的对象最相近的对象。基于用户协作的推荐系统向用户推荐具有相同兴趣和 喜好的用户群喜欢的对象。而混合型则把基于内容和基于用户协作二者的结果结 合起来向用户提供推荐。 基于内容的推荐系统是信息获取技术的延伸和扩展，是建立在内容信息上的 推荐系统，不需要依据用户对项目的评价意见。在基于内容的推荐系统中，对象 的相似性是通过相关的特征的属性来定义。 基于用户协作的推荐系统一般采用最近邻技术。这样的推荐系统首先依靠保 存在系统中的用户的喜好信息来计算用户兴趣之间的距离，然后使用距离当前用 户最近的邻居用户对商品评价来预测目标用户对某种对象的喜好程度，最后推荐 系统根据预测的对对象喜好程度来生成推荐列表。基于用户协作的推荐系统的最 大优点是对推荐对象没有特殊的要求，能处理非结构化的复杂对象。基于用户协 作的推荐系统是基于这样的假设：某一类用户的兴趣点是相同的，为某一个用户 找到他感兴趣的对象的好方法是把与该用户兴趣相似的用户感兴趣的对象推荐 给当前用户。这种算法的基本思想非常易于理解。在生活中，我们往往会向好朋 友咨询，希望好朋友推荐一些对象来进行选择。基于用户协作的推荐系统正是把 这种思想运用到推荐系统中来，基于其他用户对某一对象的评价来向当前用户进 行推荐。基于用户协作的推荐系统是从用户的角度来思考问题，对用户分类以生 成推荐列表的。用户获得的推荐列表是推荐系统从其他用户的选择模式或浏览行 为等方法获得的，不需要用户自己填写信息或许适合自己兴趣的推荐结果。 混合型推荐系统把基于内容的推荐系统和基于用户协作的推荐系统相结合。 通常的混合思路有七类【l o 】： 加权( w e i g h t ) ：加权多种推荐技术结果。 变换( s w i t c h ) ：根据问题背景和实际情况或要求决定变换采用不同的推 荐技术。 混合( m i x e d ) ：同时采用多种推荐技术给出多种推荐结果为用户提供参 考。 特征组合( f e a t u r ec o m b i n a t i o n ) - 组合来自不同推荐数据源的特征被另 一种推荐算法所采用。 层叠( c a s c a d e ) ：先用一种推荐技术产生一种粗糙的推荐结果，第二种 推荐技术在此推荐结果的基础上进一步作出更精确的推荐。 特征扩充( f e a t u r ea u g m e n t a t i o n ) ：一种技术产生附加的特征信息嵌入到 另一种推荐技术的特征输入中。 元级别( m e t a - l e v e l ) 用一种推荐方法产生的模型作为另一种推荐方法 的输入。 2 3 使用语义关系图的基于内容推荐系统 在基于内容的信息获取领域，属性关系图被用来匹配和索引对象。属性关系 图是根据对象的多种属性来确定不同对象之间的关系的一种模型。通常而言，在 属性关系图中，每个节点代表一个对象，而节点之间的连接线表示对象之间的关 系，连接线的属性标识了对象之间的具体关系属性。典型的属性关系图如图2 3 所示，其中各节点代表的对象具有时间相同、地点相同、事件相同等方面的关系 属性。 图2 - 3 属性关系图示例 把属性关系图中的连接线的属性改为对象关系的权值标识，就形成了语义关 系图。用语义关系图模型来组织管理对象的方法即语义关系图。在语义关系图和 基于内容的推荐系统的基础上，k a l c i d op h o t o 项目组提出了一种建立在语义关系 图基础上的基于内容的图片推荐系统。在这样的推荐系统中，首先需要对图片的 不同元数据分别建立一个语义关系图，即基于语义的图片属性关系图。然后把各 种元数据的语义关系图叠加起来，得到系统级的语义关系图。然后根据这个系统 级的语义关系图，对每张图片生成一个独有的推荐列表。这一过程的描述如图 2 4 所示，本文将在下一章节详细描述此算法。 2 4 本章小结 图2 - 4 推荐列表生成过程示例 本章介绍了论文要研究的问题所涉及的各种背景技术，着重介绍了w e b 服务 以及推荐系统的概念和分类，并简单描述了使用语义关系图的基于内容的图片推 荐系统的算法思想。后续章节中，将运用r e s t w e b 服务技术和基于内容的推荐 系统技术来设计和实现k a l e i d op h o t o 中相应的软件模块。 第三章使用语义关系图的推荐系统算法设计 3 1 算法设计背景 推荐系统在当前的互联网信息浏览中扮演着重要的作用。推荐系统的典型成 功应用包括亚马逊和淘宝等大型的电子购物网站。而当前各大搜索引擎正在努力 发展的针对用户的个性化搜索也在一定意义上是推荐系统在广义搜索领域的尝 试。由此可见，推荐系统算法无论在工业界的应用还是学术界的研究中都是一个 热点。 如第二章所述，典型的推荐系统可以分为基于内容的推荐系统、基于用户协 作的推荐系统和混合型推荐系统三类。 。 基于内容的推荐系统大多采用分类学习的方法，依靠对象属性的结构化描述 和用户兴趣信息生成推荐结果。典型的基于内容的推荐系统算法如采用贝叶斯分 类算法的基于内容的推荐系统【1 1 1 ，其特点是依据对象的相似性进行推荐，要求对 象具有结构化的属性，对分类后的同一类对象的推荐结果是一致的。 基于用户协作的推荐系统通过把用户按照兴趣的相似性分类来生成推荐结 果。典型的基于用户协作的推荐系统算法如g r o u p l e n s 算法【l2 1 ，其特点是依据用 户兴趣的相似性进行推荐，可以用于对象具有非结构化的属性的场景，需要大量 用户参与来获取丰富的用户兴趣信息，对新添加的对象不敏感，比较难于推荐系 统中新添加的对象。 混合型推荐系统是二者的结合。典型的混合型算法如f a b 算法【l3 】就是把基于 内容的推荐系统和基于用户协作的推荐系统相结合，用以克服基于用户协作的推 荐系统对新添加对象不敏感的缺点。 我们选择自行设计推荐系统算法主要基于以下两方面原因： 一方面，k a l e i d op h o t o 是由一系列图片相关的服务组成的一个针对移动用 户的图片共享系统。其中图片推荐服务只是一个功能服务，不一定能被用户大量 用到，故基于用户协作的推荐系统并不适合k a l e i d op h o t o 的要求。所以我们决 定采用更为关注图片相似性的基于内容的推荐系统。 另一方面，k a l e i d op h o t o 希望使用一种可以细致地描述图片相似性的推荐算 法，对每一张图片生成其独有的推荐结果。所以我们决定不使用传统的基于内容 的推荐系统，而自行设计一种能够对每张图片生成独有的推荐结果的推荐系统算 法。 通过调研和探索，我们设计了一种使用语义关系图的基于内容的推荐系统算 法。传统的基于内容的推荐系统、基于用户协作的推荐系统和使用语义关系图的 基于内容的推荐系统三种算法的特性如表3 1 所示。本章的后续小节将对使用语 义关系图的基于内容的推荐系统算法进行详细阐述。 表3 1 三种推荐系统算法的特性比较 算法类型属性用户兴趣推荐依据新对象敏感推荐结果 要求信息性 传统的基于内结构少量对象的相似能够推荐新对一类的对象 容的推荐系统 化性加入系统中 生成相同的推 的对象 荐结果 基于用户协作非结需要大量同一类的用比较难于推针对每个用户 的推荐系统 构化用户兴趣户具有相似荐到新加入生成个性化的 信息的兴趣点系统的对象推荐结果 使用语义关系结构少量对象的相似能够推荐新针对每个对象 图的基于内容 化性加入系统中 生成独有的推 的推荐系统的对象荐结果 3 2 算法概要 使用语义关系图的推荐系统算法通过把语义关系图和基于内容的推荐系统 相结合，形成了一种有效的评价图片相似性的方法。 首先，把图片按照单个维度的元数据信息，如时间、g p s 、标签等，把图片 聚类，分析每个维度的元数据信息对图片相似性的影响，对每个维度的元数据信 息生成一个单维度的语义关系图。第二步，把各种单维度的语义关系图合并形成 一个全维度的语义关系图。最后，利用全维度的语义关系图对每张图片生成一个 独有的推荐图片列表。 语义关系图是一个带权值的无向图。语义关系图中的每个节点都对应了图片 推荐系统中的一张图片。两个节点所对应的图片的相关度，决定了两个节点之间 连线的权值。因而语义关系图可以用来描述系统中所有图片之间的相似性。 本文定义连接两个节点a 和b 的连线的权值w y 为： w j = c o ( a ；，a j ) 八彳f ，乃)式( 3 1 ) 其中爿，和4 是对应的图片的单维度元数据属性。是由彳t 和乃之间的相似 度决定的权重函数。 各种单维度的语义关系图的合并是通过对图中的每条边的叠加来完成的。如 果对应的边存在，则把两条边的权值相加。这样得到的图仍然是一个带权值的无 向图，即全维度的语义关系图。这张语义关系图将表述全系统的图片相似性。 在全维度的语义关系图中，任何两张图片之间的相似性都是由连接这两张图 片对应的节点之间的边的权值来标识的。本文定义全维度的语义关系图中边的权 值为： w ( p i ，p j ) = o ) ( a i l ，a # ) f ( a i l , ，勘) 式( 3 2 ) 五 其中n 是图片元数据种类数，缈是根据图片a 和尼的属性么t 决定的图片尸f 和毋之间的相似性权值。函数厂描述两张图片a 和毋属性彳t 是否相关，其的定 义取决于传入的参数。本文把厂的返回值定义在0 和1 之间。 3 3 生成单维度的语义关系图 本小节以图片拍摄的时间维度为例，详细描述单维度语义关系图的生成算 法。其他维度的单维度语义关系图生成算法类似。 为了使用公式( 3 1 ) 生成单维度语义关系图，我们需要为该维度定义国和厂。 表格3 2 是k a l e i d op h o t o 的图片推荐系统使用的厂的集合。对每个图片元数据类 型，我们都选择一个数据粒度，用这个粒度把图片分成很多集合。每个集合都将 形成一个树形的单维度的属性分级。在同一个单维度的属性分级中的图片被认为 是相关的。同时两张图片所属的组越低，二者之间的相似度就越大，在语义关系 图中连接这两张图片对应的节点的边的权值也就越大。 表3 - 2 单维度语义关系图的厂定义 属性类型取值域 l 拍摄时间 年y y y yy l y 271 ：0 上传时间年y y y y y 1 一y 2 71 ：0 地点字符串 l 三ln 三2 。 g p s 双精度 ，l g l 一g 2 l 1 070 ：1 作者字符串 a 1 一a 2 7l ：0 事件字符串 e lne 2 e m x 标签 字符串 c o l l e c t i o n snn 丁2 丁m “ 例如，对图片拍摄时间维度而言，本章选择天为时间粒度，同时定义厂为： 知= ( y 1 一y 2 ) ? l ：o 式( 3 3 ) 其中y 1 和y 2 是图片拍摄的时间，单位是年。图片按照天为粒度分成了类 似于图3 - 1 的时间维度分级树。本章将使用这种分级来确定不同图片在拍摄时间 这个维度的相似度。 图3 - 1 拍摄时间维度分级树示例 在拍摄时间维度分级树中，所有在同一棵维度树里的图片都具有相似性。对 于这些图片之间的计算，公式( 3 1 ) 中的厂将返回1 。所有在同一个分组的图片 都被认为在拍摄时间这个属性维度上具有相同的相似性。在拍摄时间维度树中， 处于叶子分组节点中的图片被认为在拍摄时间这个属性维度上具有最高的相似 性，这样公式( 3 1 ) 中的将返回比较大的权值。处于同一个较上层的分组节 点，但不属于同一个下层分组节点的图片，被认为是有一定相似性，但相似性不 是很高，因而公式( 3 1 ) 中的缈将返回较小的权值。比如在图3 - 1 中，在2 0 0 9 年6 月9 日拍摄的图片之间具有1 0 的拍摄时间维度相似度权值。同时另外一组 图片，一张拍摄于2 0 0 9 年6 月9 日，另外一张拍摄于2 0 0 9 年6 月1 5 日，则具 有5 的时间维度相似度权值。另外一组图片，一张拍摄于2 0 0 9 年6 月9 日，另 外一张拍摄于2 0 0 9 年7 月1 3 日，则二者之间具有2 的拍摄时间维度相似度。 当计算出所有图片在拍摄时间维度的相似度之后，将得到一个类似于图3 2 的拍摄时间维度的语义关系图。 图3 - 2 拍摄时间维度语义关系图示例 在图3 2 中，每一个节点p f 都代表了系统中的一张图片。同时图中的边的权 重谢标识了两张图片在拍摄时间维度上的语义相似性。 另外，从图3 2 可以看到，由于系统