（计算机软件与理论专业论文）模糊聚类的混合推荐算法研究.pdf

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 i l l u 1 1 1 1 1 1 1 1 1 1 1 1 1 i i i i i i i i i l u l y 17 3 9 12 9 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：妖如乡y 9 o 年l 旯y 。日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 学校可以公布论文的部分或全部内容。 请选择发布时间： 。函口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者躲狐花聊签名稿敢外年易胁日 模糊聚类的混合推荐算法研究 摘要 在2 0 世纪9 0 年代提出推荐系统的概念之后，经过十多年的发展，推 荐系统已经被应用到了许多大型电子商务系统中。在对推荐系统的研究中， 如何对现有系统中的推荐算法进行改进，以及提出新的推荐算法是其中的 研究热点，其中混合策略的推荐算法是研究的主要内容，而如何避免推荐 系统中过拟合问题带来的兴趣缺失和系统的冷启动带来的评价障碍更是算 法设计与研究的难点。 本文完成的主要工作如下： ( 1 ) 在对现存的推荐算法进行分析的基础上，指出了这些算法的优点和局 限性。认为采用混合策略推荐策略是解决现存推荐系统中缺陷的较好途径， 因此设计了个基于协同过滤和项目聚类的混合策略推荐算法( h y b r i d r e c o m m e n d a t i o n a l g o r i t h mb a s e do n c o l l a b o r a t i v ef i l t e r i n ga n di t e mc l u s t e r i n g ， h r c i ) 。该算法经过项目聚类降低用户向量的维度，简化用户相似度计算。 在对项目进行评价估计时，结合了u s e r - b a s e d 和i t e m b a s e d 协同过滤算法 结果作为推荐结果。实验结果表明，该算法在推荐性能上有很好的改善， 但是在评分估计方面还存在进一步改进的空间。 ( 2 ) 将隶属度函数应用到数据聚类中，提出了一种用户聚类效果的度量方 法。并且在迭代思想和f c m 算法( f u z z yc m e a n s ) 基础上，设计了基于层 次的隶属度矩阵迭代的i m c 聚类算法( i t e r a t i o nm e m b e r s h i pd e g r e em a t r i x c l u s t e r i n g ) 。实验证明，该算法便于确定最佳的用户簇的数目，并且对簇的 边界的划分更为恰当。 ( 3 ) 将i m c 聚类算法的思想融合到h r c i 推荐算法中，提出了一种新的模 糊聚类的混合推荐算法( h y b r i dr e c o m m e n d a t i o nb a s e do nf u z z yc l u s t e r ， h r f c ) 。并提出了一种初始隶属度矩阵的构造方法，以及基于模糊聚类的 项目评分估计方法。实验结果表明，h r f c 算法比原有算法提高了项目评分 估计的准确度，从而使得算法的推荐性能进一步提高，并且在不同稀疏程 度的情况下算法性能稳定，具有较高的实际应用价值。 关键词：推荐系统相似度混合策略模糊聚类 n r e s e a r c ho fh y b r i dr e c o m m e n d a t i o n a l g o r i t h mb a s e do nf u z z yc l u s t e i u n g a bs t r a c t a f t e rt h ec o n c e p to fr e c o m m e n d e rs y s t e mp r o p o s e di n19 9 0 s ，w i t hd e c a d e o fd e v e l o p m e n t ，r e c o m m e n d e rs y s t e mh a sb e e na p p l i e dt ol a r g ee l e c t r o n i c c o m m e r c es y s t e m a m o n gt h er e s e a r c ho fr e c o m m e n d e rs y s t e m ，h o wt oi m p r o v e t h ee x i s t i n gr e c o m m e n d a t i o na l g o r i t h m sa n dp r o p o s i n gn e wr e c o m m e n d a t i o n a l g o r i t h m s h a v eb e e n h o t s p o t s h o w e v e r , t h e r e s e a r c ho f h y b r i d r e c o m m e n d a t i o na l g o r i t h m si sa nm a jo rp a r t w h a t sm o r e ，t oa v o i dl o s ti n t e r e s t s r e s u l t i n gf r o mu s e r so v e r s p e c i a l i z a t i o no f r e c o m m e n d e rs y s t e ma n dd i f f i c u l t i e s a r i s e nf r o mc o l d s t a r ta r et h em o s td i f f i c u l tt a s ki nt h ed e s i g na n dr e s e a r c h r e c o m m e n d a t i o na l g o r i t h m s t h em a i nr e s e a r c hw o r ko ft h i sp a p e ra r el i s t e da sf o l l o w s ： ( 1 ) o nt h eb a s i so fa n a l y s i so fe x i s t i n gr e c o m m e n d a t i o na l g o r i t h m s ，i t i n d i c a t e dt h ea d v a n t a g e sa n dd e f e c t s ，a n ds u g g e s t e dt h a ti ti st h eb e r e rw a yt o a d o p th y b r i dr e c o m m e n d a t i o na l g o r i t h m st oo v e r c o m et h ep r o b l e m se x i s t i n gi n t h er e c o m m e n d e rs y s t e m s t h e r e f o r e ，ah y b r i dr e c o m m e n d a t i o nb a s e do n c o l l a b o r a t i v e f i l t e r i n g a n di t e m c l u s t e r i n g ( h r c i ) h a s b e e n d e s i g n e d a c c o r d i n g l y i tr e d u c e dt h ed i m e n s i o n s o fu s e rv e c t o ra n ds i m p l i f i e dt h e c a l c u l a t i o no fs i m i l a r i t yb e t w e e nu s e r sb yi t e mc l u s t e r i n g i ne v a l u a t i o n e s t i m a t e o fi t e r n s i tc o m b i n e dr e s u l to ft h eu s e r - b a s e da n di t e m b a s e dc o l l a b o r a t i v e f i l t e r i n ga st h er e c o m m e n d i n gr e s u l t a si ss h o w n i nt h ee x p e r i m e n t a lr e s u l t ，t h i s a l g o r i t h mi m p r o v e dt h ep e r f o r m a n c e so fr e c o m m e n d a t i o n si nag o o dw a y , b u t m o r ew o r ks h o u l db ed o n eo nt h ee v a l u a t i o ne s t i m a t eo fi t e m s ( 2 ) i ta p p l i e sg r a d eo fm e m b e r s h i pf u n c t i o ni n t oc l u s t e r i n g ，i n t r o d u c e sa i i i s u i t a b l em e t h o do nm e a s u r i n gt h ee f f e c to ft h ec l u s t e r i n g b a s e do nt h ei t e r a t i o n i d e aa n df c ma l g o r i t h m ，a ni m cc l u s t e r i n ga l g o r i t h mb a s e do nh i e r a r c h i c a l c l u s t e ra n dg r a d eo fm e m b e r s h i pm a t r i xi t e r a t i o nh a sb e e nd e s i g n e d p r o v e db y e x p e r i m e n t ，t h i sa l g o r i t h mi sc o n v e n i e n to nc o n f i r m i n gt h en u m b e r so ft h eb e s t u s e rc l u s t e r , b e s i d e s ，i ti sm o r ea p p r o p r i a t eo nt h ep a r t i t i o n i n go ft h eb o u n d a r yo f t h ec l u s t e r s ( 3 ) m e r g i n g i m cc l u s t e r i n g a l g o r i t h m w i t hh r c ir e c o m m e n d a t i o n a l g o r i t h m s ，i ti n t r o d u c e san e wa l g o r i t h mo fh r f c ( h y b r i dr e c o m m e n d a t i o n b a s e do nf u z z yc l u s t e r ) ac o n s t r u c t i o n a lm e t h o do fi n i t i a l i z i n gg r a d eo f m e m b e r s h i pm a t r i xi sa l s oi n t r o d u c e d ，a sw e l la s t h ei t e me v a l u a t i o nm e t h o d b a s e do nf u z z yc l u s t e r a si ss h o w ni nt h ee x p e r i m e n t a lr e s u l t ，h r f ci m p r o v e d t h e p r e c i s i o n o fe v a l u a t i o n e s t i m a t eo fi t e m s ，t h e r e f o r e ，i tm a k e st h e r e c o m m e n d a t i o np e r f o r m a n c e s u p g r a d e d ，a n d t h ea l g o r i t h mi ss t a b l ei n s i t u a t i o n so fd i f f e r e n ts p a r s el e v e l s ，a n dw i t hh i g h e rv a l u e so f p r a c t i c a lu s e k e yw o r d s ：r e c o m m e n d e rs y s t e m ； s i m i l a r i t y ；h y b r i ds t r a t e g y ； f u z z yc l u s t e r i v 目录 摘要i a b s t r a c t ：i i i 第一章绪论1 1 1 研究背景1 1 2 研究现状及存在的问题2 1 3 研究内容。3 1 4 论文结构4 第二章数据挖掘与个性化推荐算法6 2 1 推荐问题的提出和基本概念6 2 2 基于关联规则的推荐算法8 2 3 基于内容的推荐算法9 2 4 协同过滤算法1 0 2 4 1 基于用户的协同过滤1 0 2 4 2 基于项的协同过滤1 1 2 5 常见推荐算法的比较11 2 5 1 基于内容的推荐算法的优劣1 1 2 5 2 协同过滤算法的优劣1 2 2 6 推荐系统的工作流程1 3 2 7 本章小结1 4 第三章混合策略的推荐算法1 6 3 1 概j 签1 6 3 2 算法的设计思路1 7 3 2 1 目前采用的方法1 7 3 2 2 算法的提出1 7 3 3h r c i 算法的具体实现。18 3 3 1 项目聚类18 3 3 2 相似度计算2 1 3 3 3 做出推荐2 2 3 3 4 两种推荐的实验比较2 5 3 。4 实验比较2 6 3 5 本章小结3l 第四章隶属度矩阵迭代的模糊聚类算法3 2 4 1 模糊聚类的基本思想3 2 4 2 基础知识3 2 4 2 1 关系3 2 4 2 2 模糊数学中的关系3 3 4 2 3 模糊关系3 3 4 2 4 模糊矩阵3 4 4 2 5 模糊等价关系3 4 4 3 模糊聚类的一般过程3 4 4 3 1 数据标准化3 4 4 3 2 找出模糊关系3 4 v 4 3 3 模糊聚类3 5 4 4 模糊c 均值( f c m ) 算法3 6 4 5 迭代隶属度矩阵的模糊聚类算法3 7 4 5 1 判断标准3 7 4 5 2 算法流程3 8 4 6 实验与比较3 8 4 7 本章小结4 0 第五章模糊聚类的混合策略推荐算法一4 1 5 1 算法的改进4 l 5 1 1 隶属度矩阵的建立。4 1 5 1 2 基于项的模糊聚类4 2 5 1 3 基于隶属度矩阵的评分估计4 3 5 2 一种新的模糊聚类混合策略推荐算法4 4 5 3 对比实验4 6 5 3 1 实验准备4 6 5 3 2 实验结果与分析4 7 5 4 稀疏性处理实验与结果分析4 8 5 4 1 数据准备4 8 5 4 2 实验结果与分析4 8 5 5 本章小结5 0 第六章结束语。5 1 6 1 全文总结5 1 6 2 工作展望51 参考文献5 3 致谢5 7 攻读硕士学位期间发表的学术论文目录5 8 v i 模糊聚类的混合推荐算法研究 第一章绪论 1 1 研究背景 推荐系统的概念产生于上世纪末，是随着信息科技和互联网的迅速发展带来的信息 过载产生的。搜索引擎技术的出现在一定程度上缓解了信息过载带来的问题，但是还有 许多不足之处。一方面用户需要提出信息主题，限定了潜在兴趣的发掘；另一方面系统 缺乏个性化的主动推荐。推荐系统是在认知科学、近似理论、信息检索和预测学的理论 基础上产生的。它最初应用于电子商务领域，人们所认同的推荐系统是以电子商务网站 为依托，通过提供商品的属性和评价，对用户的购买行为起到积极的建议作用【l 】。推荐 系统的工作原理，是通过分析用户的行为表现出来的个性化特征，结合特定的推荐算法， 分析系统本身采集到的数据库信息，得出推荐项返回给用户。 协同过滤算法是最早应用于实际的推荐算法，通过计算用户之间兴趣爱好的相似 度，估计出未知评分，从而做出推荐。t a p e s t r y 系统是最早的协同过滤算法的实现【2 】。 b s a r w a r 等提出一种基于项的协同过滤算法【3 】，是对传统协同过滤算法的一种改进。基 于内容的推荐则是一种自动提取项目属性并根据相似度进行推荐的算法，主要适用于文 本属性的项目对象。此外，机器学习和数据挖掘技术的发展，推荐算法有了更多的选择。 通过分析行为项之间的关联关系，可以为用户提供更多有用的推荐。对用户建模的研究， 可以收集到更多有用的用户信息，建立更精确的用户模型【4 】【5 1 。合理的用户模型还可以 发现更多潜在的用户兴趣【2 5 1 。目前数据存储的最大载体是w e b ，结合w e b 数据挖掘， 获取用户的访问记录和关联关系，是构造用户模型的重要途径7 】【5 5 1 。图论、贝叶斯网 络、分判8 1 、聚类分析和人工神经网络 9 】，也从不同角度提高了推荐效率。 文献 1 0 提出了一种基于项目评分预测的协同过滤算法，改进了传统的协同过滤算 法，是对推荐系统中存在的稀疏矩阵问题的一种很好的解决方案，即通过采用计算项目 之间的相似度，并引入修正余弦度量和稀疏等级的概念，从而用固定值或者平均值来填 充目标用户的评分，在一定程度上弥补了评分矩阵的缺失。p a z z a n i 等人【l l j 则从另一个 角度来解决稀疏矩阵的问题，利用统计学领域知识，获取了更多的用户个人信息，作为 用户相似度的计算标准。利用神经网络的方法来计算缺失的稀疏矩阵【1 2 】，在填充效果上 要更加精确一些，有一定的噪声处理能力，但同时，时间效率上比前两种方法要差一些。 目前，推荐系统主要应用于各个电子商务领域，为用户提供个性化服务，有利于提 广西大掌硕士掌位论文模糊聚类的混合推荐算法研究 高用户的满意度和防止客户流失。在电子商务领域，a r a g o n 和e b a y 主要采用了协同过 滤的推荐算法；网页推荐领域，主要有斯坦福大学的f a b 和采用实体知识库的f o x 仃o t 论文主题推荐系统；在电影推荐领域，n e t f i l x 和明尼苏达大学的m o f i e l e i l s 公开自己的 实验数据集，已经成为推荐系统领域常用的实验测试数据；在新闻过滤方面，有 u p l e i l s ，p h o a k s 等。在学术研究领域，推荐系统作为一个交叉学科也受到各类相 关会议越来越多的重视，数学、统计学、计算机科学和管理学的国际会议上，相关论文 的发表也越来越多。a c m 于2 0 0 7 年开始举办第一届推荐系统年会，另外在i e e e 和a c m 在机器学习和人工智能领域的会议，推荐系统的研究文章占据了一定的比重。m i t 、明 尼苏达大学、卡内基梅隆大学都有专门的推荐系统研究小组【1 2 1 。g o o g l e 等搜索引擎公 司己将个性化推荐作为研发下一代搜索引擎的主要工作。因此，个性化推荐技术具有很 广阔的应用前景。 1 2 研究现状及存在的问题 推荐系统的问题研究，主要包括以下方面：用户建模，推荐算法的选择，信息的反 馈。 早期的用户建模只获取用户少量的固定信息。随着数据挖掘技术的完善，这样的用 户建模已经不能满足系统的需要，考虑到用户的兴趣广泛和兴趣转移等问题，对于用户 信息，一般采用交互式采集方式，采集的客户信息如果过多，就推荐效果而言是最好的， 但是可能会降低客户满意度，同时还存在推荐系统可信度的问题，用户因为担心系统的 安全性而不敢把真实的数据提供给系统；而采集的信息过少，在建立用户模型的时候会 出现信息缺乏，导致建模不准确。总之，用户建模的优劣，很大程度上决定了推荐系统 性能和准确率。 对于推荐算法，常用的算法有协同过滤、基于内容和基于网格的推荐算法。也可分 为基于个人历史、基于社会活动和基于产品的推荐。无论哪种推荐算法，均是由用户的 兴趣出发，经过不同的算法策略，最终对用户未来的兴趣做出预测。 协同过滤算法是最早提出的推荐算法【1 3 】。主要分为基于用户的协同过滤、基于项的 协同过滤和基于模型的协同过滤算法。它的思想就是收集相关项( 用户) 信息，然后搜 索最近邻居，根据邻居的相关性做出推荐。基于过去具有相同偏好的用户( 项) 会具有 相似关联的假设，将已知用户的兴趣推荐给未知用户。 基于内容的推荐算法，是传统信息检索技术的一种演化算法【5 1 。通过寻找某一用户 2 广西大学硕士学位论文模糊聚类的混合推荐算法研究 偏好的项，从而寻找跟这一项相关度最高的项作为推荐项。这一推荐算法主要应用于推 荐项包含很多文本信息的应用当中，由于可以从文本中提取特征，并且对用户的描述过 程中也包含了对用户兴趣和偏好的描述，因此可以在用户建模的过程中通过收集用户信 息，用来详细的估计出用户的兴趣。基于内容的推荐算法经常用于新闻、网页和文档的 推荐。 两种常用的推荐算法都涉及到一个相似度度量的问题，无论是用户之间的相似度， 还是项之间的相似度，对于推荐系统都是至关重要的。对于用户之间的相似度，可以通 过用户个人信息或者用户对项的评分来计算，主要计量方式都是采用向量余弦距离及其 变式、p e a r s o n 相关系数等。 在基于用户的协同过滤算法中，随着系统用户的增多，在海量用户中搜索最近邻居 项成为制约系统的瓶颈。在这方面，基于项的协同过滤则是利用项之间的相似关系，降 低了计算量，很好的提高了系统的可扩展性和稳定性。协同过滤算法的系统冷启动】， 即对新加入用户和项很难做出推荐，特别是在新用户加入，采集信息过少时尤其如此。 而新的项加入数据库之后，则需要更长的时间才能获得用户评分，这种情况则需要考虑 应用组合推荐策略。随着系统数据库规模的增长，效率会急剧衰减。通过维度简化和矩 阵分解技术，可提高协同过滤算法的精确度和推荐速度f 剐。稀疏矩阵问题，在推荐系统 数据库当中不可避免存在大量未被用户评分的项，这种情况应当超过整个评价矩阵一半 以上的空间，这是因为用户之间兴趣的差异性造成的，稀疏矩阵的解决也是推荐系统研 究中的热点问题。 此外，推荐的精确度和多样性之间的平衡问题【1 9 1 ，也是目前推荐系统的热点问题。 在文献 2 0 】中，作者提出使用一种对分网络的数学模型对用户兴趣进行预测，该算法基 于协同过滤的原理，通过对复杂网络的研究，利用网络动力学原理对用户的共同兴趣进 行划分【5 3 】，得到了比协同过滤算法更高的精确度。 开源项目中也有许多关于推荐系统的资源：t a s t e 是一个基于j a v ae e 平台的开源 的推荐引擎，定义了完整的推荐模型包和实现了常见的推荐算法，已经成为一个推荐器 的集合，并加入了a p a c em a l l o u t 开源项目。d u m e 是一个推荐框架，改进了用户模型， 反馈和解释模块和模块间的交互。g m u p l e i l s 是明尼苏达大学计算机科学工程学院的研 究小组，该小组采集了多种应用领域的不同规模的数据，是目前推荐实验的常用数据集。 1 3 研究内容 3 模糊聚类的混合推荐算法研究 推荐系统是- 1 7 新型课题。经过十多年的研究，虽然取得了一些进展，但仍然存在 很多有待解决的问题。本文首先在总结传统推荐算法和前人研究成果的基础上，设计出 一种基于项目聚类的混合策略的推荐算法，提高了推荐精度，在一定程度上解决了系数 矩阵问题。此外为了提高评价估计的精度和准确度，本文提出了一种聚类效果判别方式， 并采用模糊聚类和构造隶属度矩阵方法对项目聚类，达到更好的聚类效果，提高评分估 计精度。通过对比实验，本文提出的基于模糊聚类的混合推荐算法提高了推荐精度和评 价估计。通过对五组不同稀疏程度的数据集进行实验表明，这种推荐效率和评价估计的 提高是稳定的。 1 4 论文结构 本文的主要研究内容是希望提出一种混合策略的推荐算法，该算法能在整体上提高 推荐的准确度，同时很好的处理原始数据中的离群点。基于以上目的，在以往研究的基 础上，本文针对提高推荐系统的精度，以及推荐精确度和多样性之间的平衡，提出了一 种基于模糊聚类的混合推荐算法。 本文各个章节的组织结构如下： 第一章绪论，介绍了推荐系统的产生和及相关研究背景，简要概述了推荐系统的不 同推荐方法、研究现状和存在的问题 第二章将介绍传统的个性化推荐算法，以及加入数据挖掘领域知识的新的推荐算 法，通过对算法性能的分析，比较这些传统算法的优点和局限。 第三章将介绍提出的一个混合策略的推荐算法h r c i ( h y b r i dr e c o m m e n d a t i o n a l g o r i t h mb a s e do nc o l l a b o r a t i v ef i l t e r i n ga n di t e mc l u s t e r i n g ) 。该算法结合了项目聚类和 协同过滤算法，即通过项目聚类降低用户向量的维度，简化用户相似度计算。并且利用 同类对象之间的相关度，对目标项的评分进行估计。最后从基于用户和基于项两种方式 的结合，得出推荐列表。 第四章从f c m 模糊聚类算法出发，将隶属度函数应用到数据聚类中，提出了一种 适用于用户聚类的效果度量方法。介绍了基于迭代思想的f c m 算法，基于f c m 算法的 迭代思想，设计了基于层次的隶属度矩阵迭代的i m c 聚类算法( i t e r a t i o nm e m b e r s h i p d e g r e em a t r i xc l u s t e r i n g ) 。实验证明，该算法便于发现用户的簇的数目，并且对边界数据 的处理方式恰当，适合项目聚类的要求，为改进h r c i 算法提供了条件。 第五章将i m c 聚类算法思想融合到h r c i 推荐算法中，提出了一种新的h r f c 推 4 广西大掌硕士掌位论文模糊聚类的混合推荐算法研究 荐算法( h y b r i dr e c o m m e n d a t i o nb a s e d o nf u z z yc l u s t e r ，h r f c ) 。并提出了初始化隶属 度矩阵的构造方法，证明了模糊聚类算法在评分估计中的作用。经过验证，新的推荐算 法提高了原算法的评分估计精确，算法性能稳定，具有实际使用价值。 最后总结了论文的工作，为进一步研究做出展望。 5 广西大学硕士学位论文模糊聚类的混合推荐算法研究 第二章数据挖掘与个性化推荐算法 2 1 推荐问题的提出和基本概念 推荐系统是融合多个学科知识相结合，用以解决信息过载问题的一种工具。在推荐 过程中，用户不再需要向系统提交自己的索引关键字来查找内容，而是将整个过程转变 为系统为主导的主动向用户做出推荐，不需要用户向系统描述对象的详细特征。目前推 荐系统已经在实际应用中发挥着作用，推荐问题的实质就是寻找用户集中的元素与项集 中的元素兴趣度关联的关系问题。比如，对于一个销售c d 的商店来说，推荐系统就的 用途就是根据销售的历史记录，帮助店主找出目标客户可能喜欢听的c d 是哪些，以便 向客户进行推荐。 推荐系统按功能划分可以分为三个模块：用户模块、项目模块和推荐模块 图2 1 推荐系统的组成模块 f i g 2 - 1t h ec o n s 删i o no fr e c o m m e n d e rs y s t 啪 设矩阵u = ( u u ) 。埘是用户特征矩阵，是用户i 的第，个特征分量；设矩阵 i = ( i v ) m 。是推荐项目的特征矩阵，屯是项目i 的第个特征分量；矩阵r = ( 勺) m 。是用 户的评分矩阵，如图，其中0 是第f 个用户对第项的打分，的初始值都为0 。利用收 集到的数据，构建评分矩阵r 和用户特征矩阵u ，继而建立用户模型，并选用适当的推 荐算法，提取用户模型中隐含的用户兴趣，对目标用户可能会感兴趣的项做出预测。 6 模糊聚类的混合推荐算法研究 r = o 8 5o 0o 40 oo 7o o5 0 7 3o o0 o8 0 0 2o o 0 o 0 08 o o o o 0 0 0 0 09 0 o 2 0 o 8 图2 2 构造用尸评价矩阵 f i g 2 - 2b u i l d i n gt h ee v a l u a t i o nm a t r i xo f u s e r s 推荐算法是推荐系统的核心部分。目前推荐算法仍存在以下几个关键的问题有待解 决： 1 、数据的获取。推荐系统的数据，特别是从用户收集而来的数据，隐含了大量的 用户信息。获取用户数据有两种手段，即隐式方式和显式方式。隐式方式是指不需要强 迫用户通过提交表单或者给项目打分等手段，而是当用户在系统中随意浏览的过程中， 记录下用户的操作序列，对不同的操作赋予不同的权重，比如浏览记为1 ，收藏记为3 ， 购买记为5 ，从而从中发掘用户兴趣；显式方式是指通过用户给浏览过的数据的打分和 评价，用分值构造评分矩阵，从中得到的用户兴趣数据。两种方式相比，显式获取到的 数据更加精确，但是频繁的让用户做出评价可能会导致用户失去耐心；而隐式的获取数 据具备良好的用户友好性，但是由于用户的操作过程误操作率极大，因此数据的精确度 大大降低。 2 、相似度度量。推荐系统中的每一个用户和项，都可以表示成空间中的向量，因 而相关用户和项之间的相似度，是推荐的重要依据。后面介绍的推荐算法大多涉及到大 量的相似度的计算。常用的相似度度量标准有向量余弦、欧几里德距离、皮尔逊相关系 数和改进的向量余弦。 3 、用户的评分估计。评分矩阵r 既隐含了大量的用户兴趣信息，又是做出推荐时 的依据，但是这个矩阵在通常情况下是一个稀疏矩阵。由于相对于数据库中众多的项目， 每一个用户能够做出评价的项目数量是相当有限的，因此造成评价矩阵中绝大多数元素 都保持初始状态0 ，这一现象叫做评价矩阵的稀疏问题。稀疏矩阵是推荐问题不可避免 的问题。对用户评分进行估计，用估计值填充稀疏矩阵是解决这个问题的方法之一，此 7 模糊聚类的混合推荐算法研究 外，评分的估计值也可以为推荐项与用户的关联程度提供一个量化标准。 4 、冷启动问题。冷启动问题是针对新加入系统的用户和项提出的。一个新加入系 统的用户，由于没有历史记录，推荐无从入手，因此也无法做出有效推荐。对每一个用 户，系统也都必须要经过一段时间的学习，才能充分了解用户的兴趣；同理，对于新添 加的项也是如此。系统中的新添加项，由于没有用户对其评分，因而算法无法将其加入 推荐列表。 个性化推荐技术经过十多年的研究，已经取得了许多研究成果，也提出了一些相关 的推荐算法，下面介绍几种常用的推荐算法。 2 2 基于关联规则的推荐算法 关联规则反映的是事务之间的联系。关联规则的主要任务就是根据最小支持度找出 频繁项集，然后根据频繁项集导出规则。设j 口和是项集中的两项，如果集合冬。，) 满 足最小支持度阈值，那么。，) 就是频繁项集，已j 屯就是强关联规则。根据关联规 则的这种特性，我们可以认为，如果s 。和j 。具有强关联关系，对j 。感兴趣的用户很可能 对感兴趣。 对于关联规则算法，最核心的问题就是寻找频繁项集。而在算法实现上，最重要的 问题是减少扫描数据集的次数。因为候选的项集数据很大，重复扫描会造成很大的系统 负载，系统的稳定性很难保证。另外，生成的候选项集的数量会更大，加重了存储负担。 因此在算法实现上应该尽量避免重复扫描数据集和产生尽可能少的候选项集。a p r i o r i 算法是一种快速挖掘频繁项集的算法【1 4 1 ，它利用a p r i o r i 性质对产生的候选项集进行剪 枝，即g 是频繁项集，它的所有非空子集也都是频繁项集；反之，如果g 一。是非频繁项 集，那么它的任意超集c 必然不是频繁项集。因此，包含非频繁项集q 一的超集不需要 再进行扫描和计算，即可认定不是频繁项集，利用这一性质，减少了存储候选项集的空 间，但是由于仍需要重复扫描数据集，时间上没有显著提高。f p 增长算法利用递归的 策略，通过构造f p 树的方法来存储频繁项集。由于不需要频繁的扫描数据集，而且不 产生候选项集，f p 树算法【1 5 】在时间和稳定性上都有很好的优化，但是由于采用递归的 策略，因此当处理数据集很大的时候，f p 算法不能很有效的产生规则。e c l a t 算法【1 6 】 采用的是与前两种不同的垂直数据格式，并利用a p r i o r i 算法挖掘事务项集。 由此可知，关联规则推荐算法不同于传统的推荐算法，除了评分矩阵r = ( 白) 朋。外， 8 广西大掌硕士学位论文模糊聚类的混合推荐算法研究 它还要记录用户每一次与系统交互的操作序列【l 刀。由于不需要对项目属性进行具体分 析，不需要相关的领域知识对数据项进行分类，而只是依靠事务数据库中的关联关系， 因此关联规则很容易发现用户的隐藏兴趣；但同时，关联规则算法在时间和空间上的效 率依赖于候选数据集的数量，在处理大数据集的数据时产生规则时间长，效率不高。关 联规则算法可以在一定程度上解决系统冷启动问题的制约，但另外对于推荐系统的最大 问题评价矩阵稀疏性问题，关联规则很难处理，个性化程度不强，目前针对关联规 则算法的一些改进，在这方面也没有明显改善。 2 3 基于内容的推荐算法 基于内容的推荐算法，用户c 对项s 的效用函数u ( c ，s ) 是依据项之间的关联来估计 的。当系统向用户推荐某一项j 时，会先在数据库中查找用户的评分记录，找出评分比 较高的几项之间的共性，作为用户的偏好，然后找出与用户偏好相似度比较高的项作为 推荐。比如前面提到的f a b 推荐系统，主要功能是向用户推荐网页文本，它首先从网络 上抓取网页，使用分词工具处理文本，从每个网页提取1 0 0 个关键词来表示网页。并且 每个关键词依据不同的标准，赋予不同的权重。 常见的计算方法有t f i d f ( 词频逆向文档词频) 【2 3 】，它假设关键字的重要性与它 在文件中出现的次数成正比，与它在所有文档库中出现的频率成反比。这样的假设是为 了防止因文本的长度不同，因为对于同一个关键词，长文档比短文档有更高的出现频率， 但是它未必是关键词。 碣= m a x l zf z j ( 公式2 - 1 ) 码就是关键词毛在文档d ，中的词频，乃疋i = it 在文档办中出现的次数，m a x ：厶是 文档中出现次数最多的关键词屯出现的次数。 但是考虑到如果有一篇并不相关的文档，对岛关键词也有很高的词频，说明这个关 键词在分类效果上就不是很好。所以要引入i d f 度量。关键j , 司k i 的逆向文档频率即： 脚：l o g n( 公式2 - 2 )幽= 一( 公式 n i n 是所有文档的总数，是包含关键词t 的文档总数。 则该关键词屯的t f - i d f 权重嘞 9 广。西r 大掌硕士学位论文模糊聚类的混合推荐算法研究 嘞= 玛x l d f ， ( 公式2 - 3 ) 由此，就可以用t f i d f 将一个文档表示为一个k 维向量。在此向量空间使用向量 余弦度量或者p e a r s o n 度量，衡量文档之间的相似度 2 4 协同过滤算法 协同过滤的基本思想是对一大群人进行分析，找出与目标用户品味相近的- d , 群 人，考察他们的兴趣差异，构造一个推荐候选集。根据信息过滤的对象不同，协同过滤 算法又分为基于用户的协同过滤和基于项的协同过滤【2 l 】。1 9 9 2 年，d a v i dg o l d b e r g 设计 出的t a p e s t r y 系统2 1 ，是第一个基于协同过滤思想的推荐系统。 2 4 1 基于用户的协同过滤 基于用户的协同过滤算法就是最初传统的协同过滤算法，就是计算训练样本集中与 目标用户的相似度毛，找出相似的k 个邻居，估计目标用户对未评分项的打分，将推 荐项按照估计评分输出推荐列表。 基于用户的协同过滤算法的描述【1 3 】【2 l 】： c o l l a b o r a t i v ef i l t e r i n g ( r , i lp ) ；n - 目标用户的邻居集合 l ：推荐列表 f o r ( a l l 甜f ，u ，u ) s = s i m ( u j ，u j ) ； e n d f o r f o r i j = lt ok ) t o p ( s d ) 一n ； e n d f o r f o r ( i t = i j i s ) 如2 寺如岛； 一l ； e n d f o r s o r t ( l ) ； 算法2 - 1 基于用户的协同过滤算法 a l g o r i t h m 2 - 1c o l l a b o r a t i v ef i l t e r i n gb a s e do i lu s e r s 最终得到目标用户u i 推荐列表l ，并根据对目标用户的有用程度如排序。 基于用户的协同过滤算法是早期提出的推荐算法，因此该算法存在许多问题。前面 所提到的用户冷启动问题，在基于用户的协同过滤算法中体现的尤为明显。对于一个新 l o 模糊聚