（计算机应用技术专业论文）基于聚类协作过滤的商品个性化推荐.pdf

摘要 互联网技术以及电子交易安全技术的不断成熟，为电子商务的发 展提供了广阔的发展前景。数据挖掘作为一种从海量数据中发现蕴藏 在数据内的规律的技术，电子商务则是其最理想的应用领域之一。 电子商务网站作为众多实施电子商务企业直接面对客户的第一 窗口，如何真正实现个性化的商品推荐甚至全面的个性化服务，是实 现稳定的客户群体、挖掘潜在的客户源，保持企业利润源泉的重要方 面。近年来，如何提高商业网站的有效性，尤其是如何运用个性化推 荐技术实现电子商务个性化服务已逐渐成为一个能引起广泛兴趣的 热点课题。 本文简要归纳了在电子商务网站个性化商品推荐中采用的主要 的聚类挖掘技术；针对商品相似性和用户购买相似性这两种不同的情 况分别给出了基于划分的聚类协作过滤推荐和基于层次的聚类协作 过滤推荐的方法和具体步骤及算法，并采用目前主流的开发平台 m i c r o s o f tv i s u a ls t d i o 。n e t 对不同的方法进行了具体实现和相互 分析对比。 本文着重在以下两个方面进行了探讨： 1 根据目前电子商务网站中商品个性化推荐的现状，本文提出对 不同性质的商品应采用不同的商品个性化推荐方法。具体做法是：对 易于获取用户评价的商品可根据商品的相似性采用均值聚类协作过 滤推荐而对于其它无用户评分的商品或不易获取用户评分的商品则 应根据顾客购买相似性采用基于类别聚类的协作推荐方法。聚类算法 在电子商务个性化服务的应用中最常用的是基于数值型的均值聚类， 而将基于类别的属性聚类应用于电子商务系统则是对原有应用的 个拓展。 2 针对基于类别的层次聚类往往需事先确定预期的聚类个数这 一先天不足，本文对传统r o c k 算法进行了改进提出了i m p r o v e d - - r o c k 算法。该聚类算法充分运用图中孤立点的性质，能自动终止聚 类过程并形成合理的聚类集。经数据测试表明，该算法有效实用，对 电子商务个性化服务、个性化营销的推动具有积极的意义。 关键词：电子商务，w e b 挖掘，个性化推荐，r o c k 算法，协作过滤 a b s t r a c t w i t i lt h em a t u r a t i n go fi m e m 眦t e c l m o l o g ya n de l e c t r o n i ct r a n s a c t i o ns e c u r i t y t e c h n o l o g y , e b u s i n e s s i sd e v e l o p i n gr a p i d l y d a t a - m i n i n g a sak i n do ft e c h n o l o g y t of i n dr u l e sf r o mag r e a t 耻a g i t yo fd a t a , i sp r a t i e a l l yu s e di ne b u s i n e s s o n eo ft h e b e s tf i e l d si nw h i c hi ti su s e d t oe n t e r p r i s e sa p p l y i n gw i t he - b u s i n e s s , i ti sc b u s i n e s sw e b st h a td i r e c t l yf a c e t h e i rc u s t o m e r s h o wt or e a l i z ep e r s o n a lc o m m o d i t i e sr e c o m m e n d a t i o n ，a n de v e n w h o l e l yp e r s o n a ls e f v i c e s ，i sa ni m p o r t a n ta s p e c tt ok e e ps t a b l ec u s t o m e r s , t od e v e l o p p o t e n t i a lc u s t o m e r s ，a n dt ok e e pp r o f i t s r e c e n t l y , h o wt oi m p r o v ee f f e c t i v e n e s so f c o m m e r c i a lw e b s ，e s p e c i a l l yh o wt os u p p l yp e r s o n a le - b u s i n e s ss e r v i c e sw i t ht h eh e l p o fp e r s o n a lr e c o m m e n d a t i o nt e c h n o l o g y , h a sg r n d u r a l l yb e e nah o ts u b j e c ta t t r a c t i n g w i d e s p r e a di n t e r e s t s t h i sp a p e rb r i e f l yc o n c l u d e st h ep r i m a r y c l u s t e r - m i n i n gt e c h n o l o g i e sa p p l i e di n p e r s o n a lc o m m o d i t i e sr e c o m m e n d a t i o nb y e - b u s i n e s s w e b s a c c o r d i n gt o t h e d i f f e r e n c eb e t w e e nc o m m o d i t i e ss i m i l a r i t ya n dc u s t o m e r s p u r c h a s i n gs i m i l a r i t y , i t g i v e st h em e t h o d s ，p r o c e d u r e sa n da r i t h m e t i c so fc l u s t e r i n gc o l l a b o r a t i v ef i l t e r i n g r e c o m m e n d a t i o n ，b a s e do nd i v i d e dc l u s t e r i n gc o l l a b o r a t i v ef i l t e r i n gr e x , o r n m c n d a t i o n ， a n dh i e r a r c h i c a la g g l o m e r a t i v e t h er e a l i z a t i o no f t h e md e p e n do n m i c r o s o f tv i s u a l s t u d i o n e t , t h ec u r r e n t l ym a j o rd e v e l o p i n gp l a t f o r m m e a n w h i l es o m ea n a l y s ea n d c o m p a r eb e t w e e n d i f f e r e n tm e t h o d sh a v eb e e ng i v e n t h i sp a p e rm a i n l yp r o b e si n t ot h ef o l l o w i n gt w oa s p e c t s ： 1 a i m i n ga tt h ep r e s e n ts i t u a t i o no fs p e i f i cc o m m o d i t yr e c o m m e n d a t i o ni nt h e e l e c t r o n i cc o l n m e r c ew e b s i t e s ，t h ep a p e rp u t sf o r w a r dp e r s o n a l r e c o m m e n d a t i o nt o v a r i o u se o m m o d i d i t i e s i tw o r k sa sf o i l o w s ：t 0t h ec o m m o d i t i e sw h i c hc o u l db ee a s i l y c r d i t e db yc u s t o m e r s ，e q u a lv a l u ec l u s t e r i n gc o l l a b o r a t i v ef i l t e r i n gr e c o m m e n d a t i o n c o u l dh ea p p l i e di na c c o r d a n c ew i t ht h es i m i l a r i t i e so f t h ec o m m o d i t i e s ；w h i l et ot h e c o m m o d i t i e sw h i c ha r ed i f f i c u l tt ob ec r e d i t e do rh a v i n g1 1 0c r e d i tb yc u s t o m e r s ， c o l l a o r a t i v ef i l t e r i n gr e c o m m e n d a t i o nb a s e do l lc a t e g o r i c a la t t r i b u t ec l u s t e r i n gc o u l d i l l b eu s e d c l u s t e r i n ga r i t h m e t i ci su s u a l l ya p p l i e dt ot h ek - m e a nc l u s t e 血gb a s e do i l f i g u r e s i nt h e a p p i l i c a t i o n o fe l e d t r o n l cc o m m a f c cp e r s o n a l i z e ds e r v i c e w h i l e c l u s t e r i n gw i t hc a t e g o r i c a la t t r i b u t ea p p l i e dt ot h ee l o c 日的n i c m m e r c es y s t e mi s0 1 1 1 e x t e n s i o nt oi t sa p p l i c a t i o n 2 t 0t h ec l u s t e r i n gw i t hc a t e g o r i c a la t t r i b u t e s , w h o s ec o n g e n i t a l l yd e f i c i e n to f p r e d e t e r m i n i n gt h en u m b e r so f t h ec l u s t e r i n g , t h ep a p e rb r i n g sf o r w a r dt h ei m p r o v e d r o c ka r i t h m e t i c t h ec l u s t e d n ga r i t h m e t i ct a k e sf u l l yu s eo ft h en a t t w eo fi s o l a t e d p o i n t si nt h eg r a p h w h i c hm a k e si ta u t o m a t i c a l l ye n dt h ec l u s t e r i n gp r o c e s sa n d f o r map r o p e rc l u s t e rs e t s t h ea r i t h m e t i cp r o v e st ob ev a l i da n dp r a c t i c a lb yd a t a t e s t i n g , a n di ti n e b l k sal o tt op u s hf o r w a r dt h ep e r s o a n l i z c x ls e r v i c ea n dm a r k e t i n go f e l e c t r o n i cc o n l m e l c e k e yw o r d s ：e l e c t r o n i cc o m m e r c e 。w e bm i n i n g ，p e r s o n a lr e c o m m e n d a t i o n ， r o c k a r i t h m e t i c c o l l a b o r a t i r ef i l t e r i n g i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本论文属于 保密口，在年解密后适用本授权书。 不保密哦 学位论文作者签名：导师签名： 签字目期：驯。) 。签字日期：沁占【1 i i 乙 学位论文作者毕业后去向：常州信息职业技术学院 】：作单位：常州信息职业技术学院 邮编：2 1 3 0 6 4 通讯地址：常州大学城常州信息职业技术学院信息管理系 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本 论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：，t 年 月 ? 日 江苏人学硕十研究生毕业论文 第1 章绪论 1 1w o b 数据挖掘与个性化推荐 1 1 1w e b 数据挖掘 w e b 挖掘是数据挖掘在w e b 上的应用，它利用数据挖掘技术从与w w w 相 关的资源和行为中抽耿感兴趣的、有用的模式和隐含信息，涉及w e b 技术、数 据挖掘、计算机语言学、信息学等多个领域，是一项综合技术。 1 w e b 挖掘的特点 w e b 数据挖掘具有以下特点： ( 1 ) w e b 数据挖掘的对象是海量的、分散的、动态的w e b 文件。w e b 是一 个动态性极强的信息源。w e b 不仅以极快的速度增长，而且其信息还在不断地更 新。怎样对这些数据进行复杂的应用是数据挖掘技术的研究热点。 ( 2 ) w e b 在逻辑上是由文件结点和超链接构成的网络，因此w e b 数据挖掘 的模式可以足关于内容、结构或使用方面的。 ( 3 ) 异构的数据环境。w e b 页面的复杂性远比任何传统的文本文档复杂得 多。w e b 上的每一个站点就是一个数据源，每个数据源都是异构的，各自的信息 和组织不一样，构成了一个巨大的异构数据环境。如果想要利用这些数据进行数 掘挖掘，必须要解决站点之日j 异构数据的集成问题。 ( 4 ) w e b 文件是半结构化或无结构的。每一站点的数据都各自独立设计， 并且数据本身具有自述性和动态可变性，没有特定的模型描述。需要研究统一的 语义模型，并解次半结构化或无结构数据的抽取技术。 ( 5 ) w e b 上的信息只有很小的一部分是相关或有用的。事实上，一个人只 关心w e b 上的很少一部分信息。所以，其他信息对用户来说是不感兴趣的，而 且这些冗余信息的存在可能会淹没用户所希望得到的搜索结果。 2 w e b 数据挖掘的基本步骤 数据挖掘最初针对的是大型数据库，而w e b 挖掘则是基于网络的，它除了 处理传统数据库中数据值型的结构化数据外，更多的是处理文本、图形图像、 江苏人学硕十岍究生毕业论文 w w w 信息资源等半结构、非结构的数据，是利用数据挖掘技术，自动地从w e b 文档以及服务中发现和抽取信息的过程。 w e b 数据挖掘可以分为以下三个主要的步骤： ( 1 ) 数据准备 w e b 数据挖掘的数据来自两个方面：一是用户的背景信息，主要来源于用户 登记表；另一部分主要来自浏览者对网页的请求和浏览过程中的点击流，该部分 数据主要用于考察用户的行为表现。由于用户的背景信息涉及个人隐私，一般不 愿意如实进行登记或注册，因此w e b 挖掘的数据目前大多来源于第二种。 ( 2 ) 数据挖掘：对所得到的数据进行挖掘，发现普遍的模式，也称为模式发 现。 ( 3 ) 结果分析：对挖掘出的结果，即普遍模式进行确认或者解释将分析所 得到的知识和模式用于网站的设计和改造，也称为模式分机。 基于w e b 只志文件的数据挖掘流程图如图1 1 所示。 国 救荆m 傩艘 固 捕处” 的故揪略 图卜l 基丁w e b 日占文什的数据挖措f c 流程幽 3 w e b 数据挖掘的类型 w e b 挖掘对象包含三方面的内容：w e b 上的文档信息、w e b 结构、用户浏 览w e b 页面的记录数据。相应地，按挖掘对象的不同可将w e b 挖掘分成如图l 之 所示的三种类型，即w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘【”。 l 笙ii - 2w e b 数据挖桐的分类 2 江苏人学硕十研究生毕业论文 ( 1 ) w e b 内容挖掘( w e bc o n t e n tm i n i n g ，w c m ) w e b 内容挖掘的目标是从大量w e b 文档的非结构化数据中自动查找和检索 用户感兴趣的知识，因此是对页面中的信息资源进行挖掘。w e b 内容挖掘有两种 策略：直接挖掘文档的内容，或在搜索引擎的查询结果基础上进行进一步处理。 w e b 信息内容是由文本、图像、音频、视频、数据等形式的数据组成，因此属于 一种多媒体数据挖掘形式。 w e b 内容挖掘目前主要用于权威页面的发现，以及分析相关的页面联接结 构，并且通过分析这类信息来获取更多的有用信息。例如，现在许多w e b 搜索 引擎就利用w e b 内容挖掘中的w e b 超链分析算法来提高搜索的效率和准确性 传统的w e b 搜索引擎大多数是基于关键字匹配的，返回的结果包含查询项的文 档，也有基于目录分类的搜索引擎，这些搜索引擎的结果并不十分令人满意。有 些站点会看准这些算法的弊端，有意提高关键字出现的频率来提高本身在搜索引 擎中的重要性，破坏搜索引擎结果的客观性和准确性。另外，有些重要的网页本 身并不包含查询项，在这样的算法下可能就会被忽略了。而搜索引擎的分类目录 也不可能把所有的分类考虑全面，并且目录大多数靠人工维护，主观性强费用 高，更新速度慢。因此，像现在比较著名的搜索引擎g o o g l e 就用了一种w e b 超 链分析算法p a g e r a n k 算法来提高其准确性，能比较准确的将相关的权威网页 排在搜索结果的前面。 ( 2 ) w e b 结构挖掘( w e bs t r u c t u r em i n i n g ，w s m ) 结构挖掘的目标是生成关于某个w e b 站点的结构和页面结构的概括信息， 因此结构挖掘的重点在于链接信息。给定一个相互关联的w e b 文档集合，通过 分析其网页链接和被链接数量以及对象来建立w e b 自身的链接结构模式。这种 模式可以用于网页归类，并且由此可以获得有关不同网页b j 相似度及关联度的信 息。挖掘w e b 结构的目的是发现页面的结构和w e b 的结构，在此基础上对页面 进行分类和聚类。 页内结构可以用h t m l 、x m l 表示成树形结构，页间结构则可用连接不同 网页的超链接结构表示。 ( 3 ) w e b 使用挖掘( w e b u s a g e m i n i n g ，w u m ) 江苏人学硕十研究生毕业论文 w e b 内容挖掘和w e b 结构挖掘的挖掘对象是网上的原始数据，而w e b 使用 挖掘面对的则是在用户和w e b 交互的过程中抽取出柬的第二手数据，主要包括 网络服务器访问记录、代理服务器同志记录、浏览器只志配录、用户注册信息、 交易信息等 w e b 使用挖掘是通过挖掘相应站点的r 志文件和相关数据束发现该站点上 的浏览者和顾客的行为模式。w e b 服务器的同志中一般会自动保存用户的请求信 息以及访问w e b 页面的方式等，通过分析这些数据可以帮助理解用户的行为， 不仅要找出用户经常访问的u r l 路径，而且也要找出用户有可能访问的相关站 点的链接。由此可调整站点的结构，或为用户提供个性化服务。网络日志中包含 的用户行为模式，通常可用i p 地址，u r l 、同期、时自j 等表示。 1 1 2 个性化推荐 所谓个性化推荐，就是依据用户的兴趣爱好，在页面上或者通过电子邮件等 其他手段向用户推荐用户感兴趣的内容。这种1 对l 的营销手段在市场营销领域 早有研究，近年来将其应用于电子商务领域j 下受到越柬越多的重视。 用户浏览电子商务网站时面对网上品种繁多的商品广告及其它相关内容，对 每个广告的点击次数、访问时间和访问频度是不同的。一个网站的管理者，为了 使自己的网站吸引更多的用户，在网上业务量的竞争中立于不败之地，就要本着 “以人为本”的方针，针对用户不同的兴趣、爱好，提供不同的服务口j 。对于以 商品销售为主要目标的网上商城则更应能根据顾客的个人爱好、对商品不同的兴 趣度或以往的商品购买行为为其提供个性化的商品，这样才能稳固已有顾客，挖 掘潜在顾客。例如，假设顾客想买一台打印机，但是，顾客并不能确定哪个产品 最适合自己。自信的网民往往一心想在网站上搜寻出让自己感到满意的产品信 息，但这往往很难做到。倘能给顾客类似的建议，如“假如您每天的打印量超过 5 0 张，您最好选择”；“当前个人用的激光打印机购买的最多的型号是 这样不仅可以把顾客吸引到网上商店，丽且为其提供针对性更强的商品推荐，这 样才能实现在正确的时间促销正确的产品。 个性化推荐是个性化服务的关键，个性化服务是针对不同用户提供不同的服 务策略和服务内容的服务模式。网站通过发现的用户喜好，动态地为用户定制测 江苏人学硕十研究生毕业论文 览的内容或提供浏览建议甚至购买推荐的服务就是个性化服务。个性化的基本目 标是尽可能使得每个用户在浏览该商业网站时都有他就是该刚站唯一用户的感 觉；尽可能迎合每个用户的浏览兴趣并且不断调整来适应用户浏览兴趣的变化。 因此，支持个性化服务的系统具有主动学习功能，能通过概括和分析用户的行为， 自动地实现某种程度的个性化。在电子商务应用中，最直接的实现方式就是当用 户上网浏览、访问时，由系统自动地向用户推荐相关的商品内容和用户可能感兴 趣的页面，主动为用户导航，从而使网站变得更有效、更富有吸引力；或者为用 户提供其感兴趣的商品，为用户提供更优质的服务。根据网站所推荐内容的不同， 个性化页面推荐和个性化商品推荐是电子商务网站中最常见的两种个性化推荐。 1 1 3 个性化推荐中的主要技术 个性化服务中最关键的技术是个性化推荐根据实现途径的不同，个性化推 荐的方法主要可分为基于规则的推荐、基于内容的推荐和协作推荐等p j 。 ( 1 ) 基于规则的推荐 基于规则的推荐是指根据事先生成的规则向用户推荐信息的方式。比如事先 生成的适合于某用户的购买规则是“如果购买了牛奶，就会同时购买面包”，那 么当用户再次浏览牛奶相关的商品时，网站可以同时向用户推荐与面包相关的信 息。基于规则的推荐方式在电子商务网站中应用较多，网站根据用户浏览和购买 的r 志生成规则，向用户推荐感兴趣的商品。像i b m 的w e b s p h c r 基于规则的推 荐系统，允许系统管理员根据用户的静态特征和动态属性柬制定规则，规则决定 了在不同的情况下如何提供不同的服务。这种推荐主要运用关联挖掘，其系统简 单直接，但无法动态更新，且随着规则数量的增多，系统的管理较困难【| j 。 ( 2 ) 基于内容的推荐 基于内容的推荐是是信息过滤的派生和继续，是用相关特征来定义所要推荐 的商品。如w e b w a t c h e r n e w w e e d e r 文本推荐系统等。系统通过学习客户已评 价过的商品的特征来获得对客户兴趣的描述。判定树、神经网络、基于向量的表 示等技术都可应用于其中。基于内容的推荐的缺点是必须分析资源的具体内容信 息。因此对音乐、图像、视频等信息无能为力，无法分析信息的质量，无法提供 新颖的推荐1 5 1 。而且在系统使用初期，由于系统资源还未获褥足够多的评价， 5 江苏人学硕十研究乍雎业论文 系统很难利用这些评价来发现相似的用户；而髓着系统用户和资源的增多时，系 统的性能又会急剧降低 f 3 1 协作推荐 协作推荐是指通过相同或相近兴趣的用户对资源的评价向用户推荐信息的 方式。如两个兴趣相近的朋友相互推荐爱听的音乐、爱看的书等。协作推荐目前 已经成为商业应用领域，尤其是电子商务应用系统中所采用的主流技术。 该方法的最大优点足不需要分析对象的特征属性，对推荐对象没有特殊要 求，能处理非结构化的复杂对象。该方法主要有两类： 基十内存的坍作过滤，先用统计的方法得到具有柏似兴趣爱好的邻居客 户，再基于邻居进行计算，所以该方法也称基于客户的协作过滤或基于邻居的协 作过滤： 基于模型的协作过滤，先用历史数掘得到一个模型，再用此模型进行预测。 目前这方面的研究多集中对协作过滤推荐算法的改进研究。 在基于规则的推荐中，一般采用关联挖掘技术生成帽关规则用以决定即将显 示给用户的内容：基于内容的推荐方法本质上采用了w e b 内容挖掘技术，通常 依赖个人特征和页面文档的相似性来产生推荐，因此士要运用的挖掘技术有分类 和聚类；l 办作推荐方法中使用最广泛的推荐技术是协作过滤( c o l l a b o r a t i v e f i l t e f i n g ) ，主要采用的挖掘技术是聚类挖掘1 6 】 本文中着重讨论基于聚类挖掘技术的协作过滤推荐方法及实现。 1 1 4 个性化推荐的发展现状 1 9 9 5 年，卡内基梅隆大学的ar o b e r t 等人在美国人工智能协会上提出了 个性化导航系统w e bw a t c h e r i ”，标志着个性化服务的丌始；1 9 9 7 年3 月， c o m m u n i c a t i o n so f t h e a c m 组织了个性化推荐系统的专题报道，标志着个性 化服务已经为技术界高度重视；1 9 9 9 年，德国d r e s d e n 技术大学的j t a n j a ，实现 了个性化电子商务原型系统t e l l i m ，标志着个性化服务开始向全球发展；2 0 0 0 年，n e c 研究院的d b k u r t 等人为搜索引擎c i t e s e e r 【。i 增加了个性化推荐功能。 实现c i t e s e e r 的个性化；同年，我国也丌始了个性化服务的研究，清华大学的路 海明等提出了基于多a g e n t 混合智能实现个性化推荐。2 0 0 1 年5 月w e b 之父 6 江苏人学硕十研究生毕业论文 t i mb e m e r s l e e 和合作者在( s c i e n t i f i ca m 两c 杂志上发表了“t h es e m a n t i c w e b ”一文，正式提出了语义网的概念，鉴于t i mb e r n e r s l e e 在w e b 领域的巨 大影响。该文后来一直被公认为是丌辟语义网研究的源头文献【9 l 。许多学者预测 语义w e b 挖掘将可能成为未来的热点技术。目前几乎所有的大型电子商务网站。 a l l a z o n 、c d n o w 、e b a y 、当当网上书店都不同程度地运用了个性推荐服务 a m a z o n 是全球著名的电子商务网站，提供的商品非常丰富。从锅碗瓢盆到 大小家电，应有尽有。丰富的商品可以吸引更多的用户，但同时也增加了用户找 到感兴趣商品的时间。为了使用户能够直接浏览感兴趣的商品a l l l a z o l l 推出个 性化服务。a m a z o n 网站的商品推荐服务主要体现在以下几个方面： ( 1 ) r e c o m m e n d e d f o r y o u ：主要提供一些热门商品推荐，新货推荐等，不能 体现个性化特征。 ( 2 ) i m p r o v e y o u r r e c o m m e n d a t i o n s ：通过获取用户的一些兴趣点以便今后的 个性化推荐。 ( 3 ) 根据记录用户以往的访问与购买情况进行协作推荐。 其中第( 3 ) 种服务主要通过p l o g ( p e r s o n a l i z e d w e b l o g ) 对用户浏览过的商品 和购物记录进行筛选。并将相似用户的商品推荐给该用户，即协作推荐。亚马逊 商店以客户个性化需求为进一步追求的目标，是电子商务个性化服务实施最好的 网站之一，而我国在这一方面不仅意识以及具体行动都要远远落后于它。 1 2 本文的研究意义 本文研究的意义主要体现在以下两个方面： l 、目前国内大多数电子商务网站所实施的商品个性化推荐尚属个性化推荐 的初级起步阶段，研究有效可行的个性化推荐方法对推对电子商务的的发展有现 实意义。 目酊国内大多数电子商务网站的商品推荐通常是；推荐畅销产品( 即根据当 前的购买量推荐) ；推荐相关产品( 推荐相似的产品) ；根掘用户浏览历史的推荐 ( 较常见的是显示该用户曾经购买的商品) 。可以说，前两种推荐由于根本未考 虑不同用户的个性特点，因此推荐完全不具备个性化的特点，第三种推荐有一定 江苏人学硬十研究生毕业论文 的个性化成份，但多数网站还仅仅停留在仅针对该用户一个人的购买历史只是 为每个用户建立了一个个人购买档案，没有横向进行信息综合，因此没有协作推 荐价值，所以也无法实现商品的实时综合推荐。 2 ，目前商品个性化推荐技术中使用较多的是根据商品的相似性进行推荐 而根据用户相似性进行的个性化推荐应用还较少，所用的传统算法在电子商务这 一特殊领域中也存在很明显的缺陷针对这一方面的研究有助于电子商务个性化 服务的推动与推广。 据商品相似性推荐的共同特征是根据用户对商品的评价进行同类商品推荐 这种推荐有其合理性，但一个明显缺点就是评分的获墩问题。而用户的相似性可 根据用户的浏览模式、所购买的商品情况来进行，而这些数据可通过后台服务器 实时采集。所以对这类推荐的研究有助于个性化服务的全面实现 1 3 本文的研究内容及论文组织 本论文研究的主要内容是：利用基于聚类协作过滤思想实现电子商务网站商 品的个性化推荐，并通过算法的改进j 实现在保证一定精度下有效提高个性化商品 推荐的时阊或提高推荐的精度，从而为电子商务网站个性化服务的真实实施提供 保障。 具体内容： ( 1 ) 概括商品个性化推荐中的聚类挖掘技术。 ( 2 ) 给出基于聚类协作过滤的商品个性化推荐的基本思路及处理流程，提出 将商品个性化推荐分为有用户评分和无用户评分两大类的分类方法。 ( 3 ) 给出有用户评分下商品推荐的具体算法及实现方法，并分析不同的近邻 数、相似阈值下的推荐精度及推荐速度，以说明有评分商品的推荐无需在目标商 品的所有邻居中进行协作推荐，而只需在与目标商品相似性最高的若干聚类中查 找即可。 ( 4 ) 对于无用户评分商品的个性化推荐，探讨采用层次聚类r o c k 算法的可 行性，并针对传统的r o c k 算法在屯子商务领域应用时所存在的缺陷，提出了 i m p r o v e - - r o c k 改进算法，不仅给出具体的算法过程及示意。同时运用m i c r o s o i t 江苏大学硕十研究生毕业论文 v i s u a lc # 及s q ls e r v e r 对其进行了具体的实现，同时对r o c k 及i m p r o v e d - - r o c k 这两种算法作了相应的分析与比较。 论文组织： 全文共分六章，第l 章为概述，简要介绍个性化推荐、个性化推荐中主要技 术及目前国内外发展现状，明确本文研究的意义和内容。 第2 章简要概括了商品个性化推荐中的主要聚类挖掘算法，基于聚类协作 过滤的商品个性化推荐的分类、通用结构及处理流程。 第3 章介绍有用户评分商品推荐的算法及实现，并分析不同的近邻数、相 似阈值下的推荐精度及推荐速度。 第4 章重点阐述经改进的i m p r o v e d - - r o c k 算法的具体方法，详细介绍了 算法的聚类过程。并通过具体实例进行了算法分析，在此基础上对i m p m v e d - - r o c k 算法与传统的r o c k 算法进行了相关比较。 第5 章综合第3 章和第4 章的两大类推荐方法，给出了基于聚类协作过滤 的商品个性化推荐系统的运行效果图。 第6 章论文的总结和进一步的展望。 江苏人学硕十研究生毕业论文 第2 章商品个- 性化推荐中的聚类挖掘技术 物以类聚，人以群分”，聚类的用途十分广泛。在基于w e b 的电子商务应 用中，商务网站的经营者可以根据客户的浏览模式，或者根据客户的特征聚类客 户，把和当前用户事务最相近的聚类中的页面推荐给用户，从而实现向客户提供 更适合、更富个性化的服务。基于w e b 的聚类挖掘既可以针对浏览用户，也可 以针对网页或商品进行 本章主要介绍商品个性化推荐中经常使用的聚类方法及个性化推荐质量的 评价方法。 2 1 聚类的相关概念 2 1 1 聚类概述 聚类是一个将对象划分为若干组或类井使同一个组内的对象具有较高相似 度，而不同组中的对象则不相似的过程。相似与不相似的度量是基于数据对象描 述属性的取值来确定，通常是利用各对象日j 的距离来判断。电子商务个性化推荐 中的聚类可分为页面聚类和商品聚类 通过聚类分析，可以从w e b 访问信息数据中聚集出具有 b 似特性的客户， 从而发现不同的客户群。例如，有一些客户都花了一段时日j 浏览婴儿玩具和婴儿 衣服等页面经过分析这些客户被聚类成为一组销售商根据分析出来的聚类信 息，就可以知道这是一组可能即将为人父母的客户，并可能采用相应的措施，比 如在相关的页面中添加育书籍页面的链接，发送奶粉或尿布产品信息给这些客 户，做到商务活动的有的放矢，提供个性化的服务。 聚类与分类都是对一组对象进行归类但二者的归类方法不同。聚类分析是 根据一组耒分类的样本，并且这些样本应分成几类事先也不知道，希望用某种方 法对其进行合理的分类，使得同一类的相似。，：同类的相差较多，是一种 无指导学习；分类则是已知分类然后总结出判别规则，是一种有指导学习因此， 与分类相比，聚类不依赖于预先定义好的类，也不需要训练集i 。 江苏大学硕十研究生毕业论文 聚类算法很多，需根据应用所涉及的数据类型、聚类的目的以及具体应用要 求柬选择合适的聚类算法。视角不同，聚类分析方法的分类也不同。 ( 1 ) 按聚类的尺度来分 按照聚类的尺度，聚类方法可分为基于距离、密度和互连性这三类 基于距离的聚类方法 距离是聚类分析常用的度量方式，许多聚类算法都用距离来衡量数据对象之 间的相似度，如k - 平均、k 中心点、b l r c h 、c u r e 等。算法通常需给定聚类数 目k 或区分两个类的最小距离。基于距离的聚类算法简单易理解，对数据维度具 有伸缩性，但只适用于欧几黾得空削和曼哈坦空日j ，对孤立点敏感，只能发现类 圆形类。 基于密度的聚类方法 大多数划分方法是基于对象问距离进行聚类的，这类方法只能发现圆形或球 开的聚类而较难发现具有任何形状的聚类。基于密度概念的聚类方法实际上就是 不断增长所获得的聚类直到“邻近”( 数据对象或点) 密度小于给定的阈值( 如， 一个聚类中的点数，或一个给定半径内必须包含最少的点数) 为止。这种方法可 以用于消除数据中的噪声( 异常数据) ，以及帮助发现任意形状的聚类。常用的 算法有d b s c a n 和o p t i c s 基于互连性的聚类方法 基于互连性的聚类算法通常基于图或超图模型，通常将数据集映像为图或超 图，满足连接条件的数据对象之问画一条连度度连通的数据对象聚为一类。属 于此类的算法有：r o c k 、c h a m e l e o m a r h , s t i r r ，c a c t u s “峰。此类算法可适 用于任意形状的度量空间，当数掘量很大时通常忽略权重小的边使图变稀疏， 提高效率，但影响聚类质量，因此不适合处理太大的数据集。 ( 2 ) 按聚类算法的思路来分 按聚类算法的分析方法可以分为划分、层次、密度、网格和模型这五种。 划分方法 给定一个n 个对象的数据集，划分方法将数据集划分为k 个子集每个子 集表示一个聚类。一个好的划分的一般准则是：在同一个类中的对象之日j 尽可能 “相近”或相关，而不同类中的对象之蚓尽可能“远离”或不同。目f ；i 常用的算 江苏人学硕十研究生毕业论文 法有：k 一平均算法及k 冲心点算法。在k 平均算法中，每一个聚类簇用该簇中 对象的平均值来表示；而k - 中心点算法中，每一个聚类簇则用该簇中接近聚类中 心的对象来表示。这两种算法均为启发式方法，适台于在中小规模的数据库中发 现球状簇。 层次方法 层次方法就是对给定数据集进行层次分解。根据层次分解形成的方式，可以 将层次方法分为自下而上( 称为凝聚) 和自上而下( 称为分裂) 两种。自下而上 的层次方法从每个对象均为一个( 单独的) 组丌始，然后相继合并相近的对象或 组，直到所有的组合合并为一个( 层次的最上层) ，或者达到一个终止条件。自 下而上的层次方法从所有对象均属于个组开始，每一次循环将其分解为更小的 组，直到每个对象在一个单独的簇中，或者达到一个终止条件。常用的算法有 b i r c h , ( ；u r e ，r o c k 和c h a m e l e o n 算法等。 基于密度的方法 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合，这种方 法将簇看作是数据空间中被低密度区域分割丌的高密度对象区域。基于密度的聚 类可以发现任意形状的聚类结果。 基于网格的方法 基于网格的方法把对象空自j 划分为有限数目的单元以形成网格结构。所有的 聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方法的主要优点是处 理时间由于与数据对象个数无关而仅与对象空间中的每一维单元数目有关，从而 显得速度较快。常用的算法有s t i n g 和c l i q u e 。 基于模型的方法 基于模型的方法就是为每个聚类假设一个模型，再去发现符合相应模型的数 据对象。一个基于模型的算法可以通过构造一个描述性数据点空闻分布的密度函 数来确定具体聚类。它根据标准统计方法并考虑到“噪声”或异常数据，可以自 动确定聚类个数，因而它可以产生很健壮的聚类方法。典型的算法有c o b w e b ( 基于统计学模型) 和s o m ( 基于神经网络模型) 。 江苏人学项十研究生毕业论文 21 2 聚类相似度计算标准 一个聚类分析过程的质量取决于对度量标准的选择，由于聚类是按对象的相 似程度来进行划分的，因此聚类相似度的计算方法显得尤为重要。 比较常用的聚类相似度有距离相异度、余弦相似度和连接相似度，假设分别 用d ( x ，y ) 和s ( x ，y ) 表示。很显然，相异度与相似度的含义相反，即；当x 和y 相 似时，d ( x ，y ) 的值很小，s ( x ，y ) 较大；当x 和y 不相似时，则d ( x ，y ) 的值很大，而 s ( x ，y ) 较小。 1 、距离相异度的计算 设x f ( x l ，x 2 ，x n ) ，y = ( y 1 ，y 2 ，”) 是两个具有n 特征维数的对象- 则 计算这两个对象日j 的距离相似度的最常用的公式便为明可夫斯基距离函数。 m 川= 再鬲 ， 当r 取不同的值时，还可得到其它所熟知的距离公式。例如： f 1 时，即为绝对值距离，也称为曼哈坦距离； 72 12 时，明可夫斯基距离便为欧几毕得距离； 因此，明可夫斯基距离是曼哈坦距离和欧几罩得距离的概化，在实际应用中， 也可根据需要对每个变量据其重要性赋予一个权重。加权的明可夫斯基距离函数 公式如式( 2 2 ) 所示： r f 一 a ( x ，y ) = i f h h 一只l 7 ( 2 2 ) y i 为了抵消不同属性值之删的度量标准的差异，可以将属性值都归一到区自j 【o 。l 】上 2 、余弦相似度的计算 y s 0 ，y ) ( 2 3 ) 余弦相似度的取值范围在 0 1 ，是电子商务个性化推荐中常用的度量标准 之一，本论文中将用在有用户评分的商品推荐系统中。 3 、连接相似度的计算 江苏人学硕十研究生毕业论文 啦棚= 鲁吲 旺。， 连接相似度实际上是j a c c a r d 系数在基于类别、布尔类型数据的聚类分析 中常用到。例如：若x ，y 分别表示两个顾客的购买商品序列，则连接相似度则表 示两个顾客所购买的相同商品数除以两个顾客购买商品总数。很显然，连接相似 度的取值范围也在f 0 ，1 ，这一相似度将用在本论文的无用户评分推荐系统中。 2 2 常用的聚类算法 在商品个性化推荐中所用的聚类算法中最常见的当属划分类聚类，但近年来 原先一些主要用于图像检索领域的层次聚粪算法也丌始应用到电子商务中，因此 本小节中着重介绍划分类聚类算法中的三个代表算法：k 平均算法、k 中心算法、 最近邻算法以及本文中将使用的r o c k 层次聚类算法。 22 1k 一平均算法 k - 平均算法是使用最广泛的聚类算法之一，它将对象集分成k 个簇簇内 具有较高相似度，蔟闯相似度较低，相似度的计算根据一个