本科生毕业论文

论文题目: 一种基于项目聚类的推荐算法

作者、学号：何芸娜 **********

学院、年级：数学与信息科学学院2010级

学科、专业：数学  信息与计算科学

* * * *****   

完 成 日 期：2014年5月27日

曲靖师范学院教务处

一种基于项目聚类的推荐算法

摘 要

推荐系统是帮助用户评估他没有发现的内容,从而克服信息超载的一种有效工具.对于推荐系统的研究,既有重大的社会意义,又有重大的经济价值.推荐系统早在上世纪九十年代就已经被提出并进行了广泛的研究.

在现代信息爆炸的年代,用户在网上留下的评分数据成了一个很大的数据库.本文介绍了一种基于项目聚类的协同过滤推荐算法及比较简单实用的聚类分析算法—k-means算法,利用该推荐算法合理开发并利用这些资源.主要通过k-means算法求出根据项目相似性度量,从而对项目进行聚类.

文中介绍的推荐算法,其核心目的在于解决数据稀疏性优势的基础上,使用聚类分析技术对原始信息进行处理,通过简单实用的k-means聚类算法将用户的行为模型转化为兴趣模型从而实现了更精准的推荐.

关键词:推荐系统；聚类分析；相似性度量；k-means算法

Based on the project clustering recommendation algorithm

Abstract:Recommendation system is to help users assess the content he did not found an effective tool to overcome the information overload. Recommendation system for the study of both major social significance, but also of great economic value. Recommendation system early in the last century ninety years has been proposed and carried out extensive research.

In the modern era of information explosion, leaving the score in the online user data into a large database. This paper describes a project-based clustering collaborative filtering algorithm is relatively simple and practical clustering algorithm-k-means algorithm, using the recommended algorithm development and rational use of these resources. mainly determined by k-means algorithm based on project similarity measure, so the project cluster.

This article describes the recommendation algorithm, its core purpose is to solve the data sparsity-based advantages, the use of cluster analysis techniques to process the original information through simple and practical k-means clustering algorithm to model the behavior of the user interest model thus transformed into to achieve a more accurate recommendations.

Key word:  recommendation system  clustering analysis

similarity measurement  k-means arithmetic

1引言

文献[1]“互联息环境中信息超载问题研究”中介绍了计算机及互联网的飞速发展而使得人类从信息贫乏时代进入了信息超载时代.在这个信息爆炸[1]的时代,无论对于作为信息消费者的用户和信息生产者的媒体与商家都受到了海量信息带来的新挑战.

一方面,普通用户很难从海量信息中发现自己感兴趣的部分；另一方面,对于媒体和商家来说,海量的信息成为网络中的“暗信息”无法产生价值,而这些“暗信息”中或许存在着大量用户感兴趣的项目[2],如何利用这些信息提供给用户良好的服务来增加用户粘性也是一个很重要的事情.文献[2]中介绍了一种基于项目聚类的推荐算法,利用k-means算法挖掘这些海量的信息.从中开发这些海量信息的隐藏价值.

作为当前解决信息超载问题的最有效工具之一,搜索引擎以一定的策略在互联网中搜集与发现信息,同时完成对信息的提取、组织和理解等处理,从而为用户提供检索服务,起到信息导航的目的[3].搜索引擎提供的信息导航服务目前已经成为互联网上非常重要的网络服务,搜索引擎也已经成为计算机工业界和学术界广泛研究的对象.但是,随着互联网技术与需求的不断发展,搜索引擎技术不可避免的显露出一些不足之处：首先,现有的搜索引擎工具只能为用户找到已知的信息或已知关键字的信息,而不能帮助用户找到其未知但有意义或有兴趣的信息.有些潜在的携带用户偏好等信息如果无法用文字准确描述则无法通过搜索引擎得到,例如对电影的不同偏好或者对服装首饰搭配的审美特点都不容易使用明确的文字进行描述.另外,现有搜索引擎呈献给用户的是“千人一面”的分类体系和网页内容,信息结果的排列方式也是仅仅按照关键字的相关度进行排序,这往往无法满足用户的个性化需求.

文献[3]“搜索引擎及网络信息资源的分类组织”一文中介绍了几种常用的搜索引擎，从搜索引擎算法的原理到实现介绍了搜索引擎的功能,分析了搜索引擎的优点和带来的便捷之处,同时也分析了搜索功能的局限性和不足之处.

个性化推荐技术的出现从一定程度上解决了现有搜索引擎所面临的两个问题.推荐系统帮助用户评估他从未看过的产品,这些产品既包括书、电影、CD、网页等结构化信息,也可以是音乐、绘画、视频等非结构性信息.相对于搜索技术,个性化推荐系统能对用户没搜索到的信息准确描述未知领域信息进行有效的挖掘.同时,推荐系统也有助于把确切的信息传递给合适的用户,提高用户体验,这也就加强用户的对于系统的忠诚度.对于推荐系统在电子商务领域的应用,准确高效的推荐系统可以挖掘用户潜在的消费倾向,在日趋激烈的电子商务竞争中,个性化推荐系统作为一种已经被广泛应用的商业营销手段,可以大大提高用户的浏览体验,增进用户的黏着性,在这个层面上,推荐系统已经给电子商务领域带来了巨大的商机利益.

总之,对于推荐系统的研究既有重大的社会意义,又有重大的经济价值.根据学者们对于推荐系统的研究,推荐系统需要完成从数据收集到输出推荐结果的工作,这个过程中需要使用大量的模型与算法.目前比较成熟的推荐系统从整体上可以分为以下三个部分[4]： 

（1）收集记录模块：收集记录模块负责记录用户的喜好行为和评分信息等,例如用户对项目浏览、购买、点评和回答等信息.点评和打分的信息相对方便进行收集,称之为显性信息.但有的用户不愿意向系统提供这些信息,那就需要通过其它反馈信息对用户行为进行分析,例如用户浏览轨迹、购买行为信息等. 

（2）分析模型模块：分析模型模块通过这些用户的行为记录分析用户的潜在爱好产品和喜欢程度.模型分析模块的功能在于建立合适模型来描述用户的喜好信息,同时对用户的行为记录进行分析.

（3） 推荐算法模块：推荐算法模块利用模型分析的结果,设计和选择合适的推荐算法,实时或者离线的从产品集合中筛选出用户感兴趣的产品进行推荐.这个模块是整个推荐系统中最重要的部分,因为它将直接影响推荐质量的好坏,也是研究者们投入精力最多的研究部分.

随着互联网的快速发展,网络中的信息呈爆炸式的增长,怎样从这些信息中提取出有用的信息成为当今数据挖掘领域一个比较热点的话题.针对这一问题,以协同过滤推荐为代表的一系列个性化推荐算法应运而生.虽然个性化推荐技术已经在互联网领域内得到广泛应用,但是仍普遍存在数据稀疏性、算法可扩展性等亟待解决的问题.利用聚类分析等方法,在一定程度上解决推荐系统的现有问题[5].

2聚类分析

在对数据的分析和描述中,类的概念扮演着重要的角色.一方面,人类善于将各种对象划分成组或类,并将特定的对象分别指派到不同的类中.而完成这种工作的聚类分析方法已经被广泛的应用于各个领域之中,帮助用户快速的找出自己想要的结果.

电影中按照不同的电影类别归在不同的类别下,信息检索与模式识别使用聚类技术处理海量数据等.另一方面,正所谓“物以类聚,人以群分”,聚类技术也可以用于对处于社会中人类自身进行分析与研究当中.在商业领域,商家通过聚类将客户划分为若干组,以便进一步分析和开展营销活动.

总之,聚类分析就是自动发现这些类或簇的技术.聚类是数据挖掘领域用来发现数据分布和隐含模式的一项重要技术,在事先不规定分组规则的情况下将数据按照其自身特性划分成为不同的群组[7].与之相类似的是数据挖掘领域的分类技术,分类技术被称为监督分类,对新的、无标记的对象赋予类标号的过程.因此,有时聚类分析又被称为无监督分类[8].

目前被广泛应用的聚类算法很多,需要根据应用所涉及的数据类型,聚类的目的以及具体应用需求选择合适的聚类算法.视角不同,针对聚类分析方法的分类方式也不同.按照类的集合是否嵌套的划分方法,可以分为层次聚类与划分聚类.虽然研究者对于聚类技术已经有相对成熟的研究,但是在某种意义下,聚类分析只是解决其它问题的起点,算法的选择在一定程度上会直接影响后续工作的结果,对于聚类结果的应用方式也会影响实际问题的解决.

目前使用最广泛的聚类算法是k-means聚类算法[9].相似的ISODATA算法是在k-均值算法的基础上,增加对聚类结果的“合并”和“”两个操作,并设定算法运行控制参数的一种聚类算法.虽然这两种算法的理论基础与实现都非常简单,但是可以应用的范围却非常广泛.而k-means算法作为最广泛的聚类算法也具有它一定的简便优势.算法只使用对象之间的相似性度量,因此,算法产生以来在数据挖掘各个领域取得了广泛的应用.

聚类分析是数据挖掘中的一个很活跃的研究领域,并提出了许多聚类算法.传统的聚类算法可以被分为五类：划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法.计算聚类的距离指标的方法非常多：按照数据的不同性质,可选用不同的距离指标.欧氏距离、欧氏距离的平方、曼哈顿距离、切比雪夫距离、卡方距离等.

k-means 作为解决聚类问题的一种经典算法,它的主要优点是算法理论与实现都很简洁、快速.然而这种算法对不同的初始值可能会导致不同的聚类结果,一般需要进行多次重复聚类才能得到更加理想的聚类结果.另一个缺陷在于 k-means 采用了迭代方式寻找最优解,迭代过程只能保证误差的平方和的局部最优,因此易陷入局部极小值.由于这两大缺陷一定程度上了它的应用范围,聚类数量 k 需要人为指定,这也是算法存在的一个潜在的不足之处[10].

聚类分析算法原理步骤：

第一步：逐个扫描样本,每个样本依据其与已扫描过的样本的距离,被归为以前的类,或生成一个新类.

第二步,对第一步中各类依据类间距离进行合并,按一定的标准,停止合并.

综合聚类方法的计算和算法原理的步骤,聚类方法特征有：

（1）聚类分析简单、直观.

（2）聚类分析主要应用于探索性的研究,其分析的结果可以提供多个可能的解,选择最终的解需要研究者的主观判断和后续的分析.

（3）不管实际数据中是否真正存在不同的类别,利用聚类分析都能得到分成若干类别的解.

（4）聚类分析的解完全依赖于研究者所选择的聚类变量,增加或删除一些变量对最终的解都可能产生实质性的影响.

（5）研究者在使用聚类分析时应特别注意可能影响结果的各个因素.

（6）异常值和特殊的变量对聚类有较大影响.

本文将提出了一种基于项目聚类的推荐算法.算法的核心目的在于在保留了其它已有基于聚类的推荐算法在解决数据稀疏性优势的基础上,使用聚类分析技术对原始信息进行处理,并通过k-means算法求出项目之间的相似性度量[6],把同一类对象推荐给相似的用户,完成推荐过程.

3基于项目聚类的推荐算法

基于用户的协同过滤算法普遍的认为一个用户会喜欢和他有相似兴趣爱好的用户喜欢的商品.算法基于两个基本假设,即用户在空间上的一致性与时间上的一致性:算法假定在一个商品上有相同喜好的用户在其它商品上也有相同的喜好；用户过去喜欢的商品在今后也会喜欢.在这两个前提之下,要对用户进行推荐,首先要找到和他兴趣相似的用户.本章介绍了k-means算法和ISODATA算法,并对这两种算法进行比较,而本文主要介绍了简便的k-means算法,并从k-means算法的基本思想和算法的步骤具体介绍基于项目聚类的推荐算法的实践,并举例分析k-means算法的聚类过程.

3.1 ISODATA算法

ISODATA算法的基本思想：

ISODATA是迭代自组织分析,通过设定初始参数而引入人机对话环节,并使用归并与的机制,当某两类聚类中心距离小于某一阈值时,将它们合并为一类,当某类标准差大于某一阈值或其样本数目超过某一阈值时,将其分为两类.在某类样本数目少于某阈值时,需将其取消.如此,根据初始聚类中心和设定的类别数目等参数迭代,最终得到一个比较理想的分类结果.

ISODATA算法的具体步骤：

第一步：将ji个模式样本{ j,i=1,2,3,…, }读入,确定C个初始聚类中心和6个初始参数（K,θN,θc,θs,L,I）.

第二步：将N个模式样本分给最近的聚类,假如Dj=min(‖x-zj‖,i=1,2,…,),  即‖x-zj‖的距离最小,则x∈Sj.

第三步：如果Sj中的样本数Nj<,取消样本子集.

第四步：修正聚类中心值j=1,2,….

第五步：计算各聚类域Sj中诸聚类中心间的平均距离.

第六步：计算全部模式样本对其相应聚类中心的总平均距离.

第七步：判别、合并及迭代运算等步骤.

第八步：计算聚类样本距离的标准差向量.

第九步：求每一标准差向量中的最大分量.

第十步：在任一最大分量集{σj =1,2,…,}中,如有σj >θS（该值给定）,同时又满足以下二条件中之一.

（1）即Sj中样本总数超过规定值一倍以上.

（2）Nc≤K/2.

则将Zj为两个新的聚类中心,且类别数加1.如果本步完成了运算,则跳回第二步,否则,继续进行下一步.

第十一步：计算全部聚类中心的距离,i=1,2,…,j=i+1,….

第十二步：比较σj与θc值,将小于θc的值按最小距离次序递增排列.

第十三步：如将距离为Di1 ,Dj1的两个聚类中心zi1和zj1合并,被合并的两个聚类中心向量,分别以其聚类域内的样本数加权,使其为真正的平均向量.

第十四步：如果是最后一次迭代运算,算法结束,否则跳到第一步.

3.2 k-means聚类算法

基于项目聚类的协同过滤推荐算法通过用户对项目评分的相似性对项目进行聚类并生成对应的聚类中心, 在此基础上计算目标项目与聚类中心的相似性, 选择与目标项目相似性最高的若干个聚类作为查询空间, 在这些聚类中搜索目标项目的最近邻居, 从而能够在尽量少的项目空间上搜索到目标项目大部分的最近邻居, 有效提高推荐系统的实时响应速度.

（1） 

（2）

生成的s个聚类对应 s个聚类中心,用集合CC={cc1,cc2,…,ccs}表示,每个聚类中心cci=(i=1,2,…,s)表示用户对该聚类ci(i=1,2,…,s)中项目的平均评分.聚类中心作为该聚类的代表,表示用户对该聚类中项目的典型评分.

根据生成的s个聚类中心构造对应的聚类中心评分数据矩阵(m,s),聚类中心评分数据矩阵如图1所示,m行代表m个用户,s列代表s个聚类中心,第i行第j列的元素Ri,j代表用户i对项目聚类j中项目的平均评分.

图1 聚类中心评分数据矩阵

聚类中心评分数据矩阵用于计算目标项目与聚类中心的相似性,从而选择与目标项目相似性最高的前若干个聚类作为搜索空间,在此搜索空间中搜索目标项目的最近邻居.对项目进行聚类比较费时,但可以离线周期进行[11].

3.3 k-means聚类算法的算法步骤

输入:聚类数目s和用户评分数据库URDB

输出:s个聚类

步骤[12]:

（1）从用户评分数据库URDB 中检索所有n个项目,记为集合I={i1,i2,…,in};

（2）从用户评分数据库URDB中检索所有m个用户 ,记为集合U={u1,u2,…,um};

（3）任意选择s个项目,将用户评分数据库URDB对这s个项目的评分作为初始的聚类中心,记为集合CC={cc1,cc2,…,ccs};

（4）s个聚类c1,c2,…,cs均初始化为空,记为集合C={c1,c2,…,cs};

（5） repeat

 for each it em ii∈I

           for each cluster center ccj∈CC

　　　　　　 计算项目ii和聚类中心ccj的相似性sim(ii,ccj)

　　　 Endfor

 sim(ii,ccm) =max{sim(ii,cc1),sim(ii,cc2),…, sim(ii,ccs)};

　　　　  聚类cm=cm∪Ii

endfor

　　for each cluster ci∈C

　　　　for each user uj∈U 

　计算用户uj对聚类ci中所有项目的平均评分Ruj,ci,生成新的聚类中心cci;

　　　　endf or

　 　endfor

（6） unt il聚类c1,c2,…,cs上一轮循环中的聚类c1old, c2old,…, csold相同

（7） 返回;

3.4 k-means算法和ISODATA算法

k-means 方法和 ISODATA方法是两种比较基本的聚类方法了.顾名思义, k-means 就是指定有k个类,然后通过初始中心迭代得到最后的k个中心.ISODATA算法是在k-均值算法的基础上,增加对聚类结果的“合并”和“”的操作,ISODATA方法要复杂一点,而k-means算法更为简便和广泛的使用.

根据k-means算法和ISODATA算法的步骤和基本原理相比,总结了两种算法在算法步骤和计算方法中有以下的区别:

（1）K-均值算法通常适合于分类数目已知的聚类,而ISODATA算法则更加灵活;

（2）从算法角度看,两种算法的聚类中心都是通过样本均值的迭代运算来决定的；k-means算法的k类需要人为指定.

（3）ISODATA算法加入了一些试探步骤,并且可以结合成人机交互的结构,使其能利用中间结果所取得的经验更好地进行分类.

（4）主要是在迭代过程中可将一类一分为二,亦可能二类合二为一.

ISODATA算法与K-means相比在下列几方面有改进:

（1）考虑了类的合并与,因而有了自我调整类别数的能力.合并主要发生在某一类内样本个数太少的情况,或两类聚类中心之间距离太小的情况.为此设有最小类内样本数θN,以及类间中心距离参数θc.若出现两类聚类中心距离小于θc的情况,可考虑将此两类合并.则主要发生在某一类别的某分量出现类内方差过大的现象,因而宜成两个类别,以维持合理的类内方差.给出一个对类内分量方差的参数θc,用以决定是否需要将某一类成两类.

（2）由于算法有自我调整的能力,因而需要设置若干个控制用参数,如聚类数期望值K、每次迭代允许合并的最大聚类对数L及允许迭代次数I等.

k-means算法针对连续型数据,而ISODATA算法主要针对离散型数据,针对本文研究的电影评分的数据,这些数据是一些连续型数据,且本文只是把数据简单的分为两类,即可以指定k=2,数据也是0到10的数据构成的向量集,所以针对数据特点,k-means算法的聚类对于电影评分的分类较为简便.

3.5简单推荐过程的实现

我们以下面的推荐场景为例,为了简化问题,这里只举了四个用户甲、乙、丙、丁和三部不同类型的电影《里约大冒险》、《六福喜事》、《扫毒》,建立简单的推荐过程：

说明：根据上面可知甲乙、甲丁、丙丁有相似的喜好,可以把甲看过的《里约大冒险》推荐给丙,把丙喜欢的《新故事》推荐给甲,把丙看过的《六福喜事》推荐给乙,这就完成了简单的推荐过程,当然实际生活中不只这么简单.

当然在实际中,用户对电影的喜好可能不仅仅局限于电影的类别,也有可能是关注导演、演员或时间等信息.同时,人们对于文学作品,音乐美术和网上购物都存在着或多或少对于类型或者类别的偏好.目前广泛使用传统计算方式的相似度指标,如果两个用户之间没有或者很少存在共同喜欢的项目,计算得到的相似度也较小.聚类分析技术可以隐性的挖掘各种项目之间存在的潜在关联,将所研究的项目划分为不同的簇.在下面的工作中,我们将详细说明如何使用聚类技术将用户的行为向量模型转化为偏好向量模型,并在降低算法复杂度的基础上同时提高推荐预测的准确度.

4 k-means聚类算法的实现

设U={u1,u2,u3,…,uN}为用户集合,I={i1,i2,…,iM}为所有项目的集合,rui用户u对项目i的评分,如果没有评分则设为0.这样,U集合中的每一个用户都可以使用一个M维向量表征他的行为信息.本章提出的推荐系统首先使用聚类算法对系统中的项目进行聚类,根据聚类分析的结果记录这M个项目所归属类的情况[13].K-means聚类算法的划分原则有欧氏距离划分和曼哈顿距离.

4.1 k-means聚类算法模型建立 

k-means 聚类应用于n维连续空间内的对象,本文定义用户对电影评分的特征向量为样本集合,使用K-Mean法进行聚类分析,将对同一部影片评分中相同的用户聚到一类.K-Means聚类中,设定K个点为中心进行聚类,对最靠近他们的对象归类.通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果[14].

例1：用xij表示第i个样品的第j个指标,采用欧氏距离计算样品与中心的距离：

步骤如下:

步骤一:指定K个聚类中心,作为即将划分的K个类的初始均值.

步骤二:进行修改,逐个不同用户对该电影的评分分类.重新计算不同用户对该影片的评分和目标评分的距离.

步骤三:重复步骤二,直到把不同用户对该影片的评分进行分类.

例2：若例如在平面上,坐标（x1,y1）的i点与坐标（x2,y2）的j点的曼哈顿距离为：

注意：曼哈顿距离依赖坐标系统的角度,而非系统在坐标轴上的平移或映射.

曼哈顿距离满足如下数学性质:

（1）非负性:d(i,j)≥0 距离是一个非负的数值

（2）同一性:d(i,i)= 0 对象到自身的距离为0

（3）对称性:d(i,j)= d(j,i)距离是一个对称函数

（4）三角不等式:d(i,j)≤d(i,k)+d(k,j)从对象i到对象j的直接距离不会大于途经的任何其他对象k的距离.

4.2 k-means聚类算法的性能分析

k-means 作为解决聚类问题的一种经典算法,它的主要优点是算法理论与实现都很简洁、快速.并且对处理大的数据集,该算法是相对可伸缩的和高效率的.然而这种算法对不同的初始值可能会导致不同的聚类结果,一般需要进行多次重复聚类才能得到更加理想的聚类结果.另一个缺陷在于 k-means 采用了迭代方式寻找最优解,迭代过程只能保证误差的平方和的局部最优,因此易陷入局部极小值.由于这两大缺陷一定程度上了它的应用范围,聚类数量 k 需要人为指定,这也是算法存在的一个潜在的不足之处.

（1）主要优点:

①是解决聚类问题的一种经典算法,简单、快速.

②对处理大数据集,该算法是相对可伸缩和高效率的.因为它的复杂度是0 (n k t ) 是最小的,迭代次数也相对较少.

③当结果簇是密集的,而簇与簇之间区别明显时,它的效果较好

（2）主要存在的不足：

①在K-means算法中K是事先给定的,这个K值的选定是非常难以估计的.很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适.这也是 K-means算法的一个不足.

②在K-means算法中,首先需要根据初始聚类中心来确定一个初始划分,然后对初始划分进行优化.这个初始聚类中心的选择对聚类结果有较大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果,这也成为K-means算法的一个主要问题.

③从K-means算法框架可以看出,该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销是非常大的.所以需要对算法的时间复杂度进行分析、改进,提高算法应用范围.

4.3 MovieLens电影评分数据集 

文中使用的电影评分数据都是来自网络中MovieLens 电影评分数据集,下文中的4.4使用的实验数据都是来自这个数据集中,下面是对这个数据集的介绍.

MovieLens是推荐系统领域最古老和最著名的数据集之一,整个实验项目由GroupLen机构建立网站并提供实验数据.目前MovieLens网站包括用户超过 16万,评分总量超过1,500万.机构向学术界以及公众提供三种规模用户评分数据集及携带有标签信息数据集.这三个数据集的规模分别为:(i).ML.A:包含943个用户对1,682部电影的10万条评分(ii).ML.B:包含6,040个用户对3,900部电影的100 万条评分(iii).ML.C:包含71,567个用户对10,681部电影的包含评分信息的1,000 万条评分,以及100,000个用户对电影的标签数据.本文中使用的第二组数据集 ML.B,这个以文本形式的数据集大小约为1M,下文将简称该数据为MovieLens数据集[15].

4.4 k-means聚类算法实验过程及结果

实验环境:matlab编程

实验数据:来自MovieLens电影评分一部分数据集

实验基本思想:

把电影的评分分为两类,即k=2,把有过评分的归在用户看过的那一类,把没评过分归在未看过该影片的那一类,首先把偏爱于那一类影片的用户用k-means算法分类出来,然后在把邻近用户也就是喜欢同一类影片不同用户钟爱的其他类型影片进行推荐,本章就部分用户对不同类型的电影评分做了聚类,先计算出中心距离,建立目标向量函数,把用户对电影的评分进行分类,最后根据用户对电影的偏爱进行分类,最后再把不同用户之间偏爱的电影进行推荐.

实验的结果如下图所示:

图2 电影评分的分类

这里就列举了20个用户对电影的评分进行了聚类的推荐分析,电影评分数据是从mowielens数据库中找的,这里只是简单的对电影评分的数据进行分类,分成了两类,这是k-means算法分类中较为简单的,k-means算法分成两类是聚类中比较常见也是比较基础和简单的一种聚类的方法.在对电影评分分类的基础上,在搜索邻近用户,对邻近用户进行用户之间的偏爱电影的推荐即可.这就是简单的推荐过程,本文主要着重介绍了k-means算法的集中划分方法.下面再介绍两种简单的k-means算法的划分方法.

图3 评分数据分成四类

图3用欧氏距离的划分原则见附录二,用k-means算法在matlab里实现评分数据的划分,图2的电影评分数据分类只是简单的分成两类,在k-means算法中有很多不同的划分原则,图2用的是曼哈顿距离划分原则见附录一,相比图3较为简单,这只是相对数据较少的情况,若数据量很大,需要考虑其算法的空间复杂度和时间复杂度等等因素,所以在此基础上我们介绍了欧式距离的划分原则,程序说明见附录二,结果如图3所示, 

图4 随机选取数据的分类

若我们只要随机抽取一些数据进行分类,则可以直接调用matlab中的函数。图4介绍一种随机选取数据进行分类的方法见附录三.这里就把数据调到matlab数据库中,直接调用matlab中的函数,这较为简单,但这只能随机选择其中一部分数据分类,这只能用于根据随机选取的数据分类估计出哪些电影比较受用户喜欢,这种估算方法也较为方便.综上所述,数据的分类可以有多种,而根据分类的不同,也有很多划分原则,所及具体事例具体分析.本文就简单介绍这三种分类方法,对推荐系统有兴趣的可以再进一步研究.

总 结

本文主要介绍了一种基于项目聚类的推荐算法,算法利用用户对项目的评分信息进行项目的聚类分析,并在通过这种方法将真实用户的行为模型转化为兴趣模型从而进行了更高精度的推荐,算法同时还保留了其它已有基于聚类的推荐算法良好的算法可扩展性.

文中首先讨论了目前已经成熟并广泛使用的聚类分析方法,并详细介绍了k-means 这个早期的聚类算法,简要介绍了算法的优缺点.提出了通过一个假设的电影推荐系统的例子,说明了算法的思想来源,介绍算法的研究思路并给出了详细的算法流程说明.虽然在几年前已经有学者提出了一些利用聚类进行个性化推荐的算法,但主要目的都是 为了解决推荐算法中存在的数据稀疏性和可扩展性问题而简单对聚类后的项目类或用户类进行处理[16].在用户所属的用户类中选择最近邻用户并不能保证这些用户与目标用户具有更高的相似度,而仅仅是在实际应用中牺牲精确性的换取复杂度降低的一种现实应用策略.但是本文中将聚类分析挖掘出的项目关系应用于更加精准的反映用户对某一类项目的偏好,不但可以达到解决原始推荐系统中用户信息稀疏性问题和算法可扩展性问题的目的,而且对于协同过滤的原始思想给出了更加贴切的模型表现形式.

本文的目的在于将聚类的思路引入到现有对于推荐算法的研究中,在聚类分析阶段仅仅使用了一种较为简单 k-means 聚类算法.另外,我们考虑到使用个性化推荐这种实际应用形式的质量能否对聚类分析技术产生有新的有意义的评价体系[17].

参考文献

[1]李书宁.互联息环境中信息超载问题研究[J].情报科学. 2005,(10):20-35

[2]张亮.基于聚类技术的推荐算法研究[D].网络投稿.中国知网. 2012

[3]陈树年.搜索引擎及网络信息资源的分类组织[J]. Library and Information Service. 2000,(04):45-50

[4]刘建国,周涛,郭强.个性化推荐系统的评价方法综述[J].复杂系统与复杂性科学,2009,(06):35-53

[5]刘建国,周涛,汪秉宏.个性化推荐系统的研究进展[J].自然科学进展.2009,(01):20-37

[6]阳明盛.matelab基础及数学软件[M].大连:大连理工大学出版,2003:63-65

[7] Ratish Agarwal. Dr. Mahesh Motwani. Survey of clustering algorithms for MANET[J]. IJCSE. 2009,(01):42-50

[8] Luis Guerra, Laura M. McGarry, Víctor Robles, et al. Comparison between supervised and unsupervised classifications of neuronal cell types[J]. Formerly Journal of Neurobiology.2011,(71):27-36

[9]许海玲.互联网推荐系统比较研究[J].软件学报.2009,(02):45-60

[10]王千,王成.Electronic Design Engineering[J].电子设计工程.2012,(07):15-28

[11]邓爱林,左子叶,朱扬勇,基于项目聚类的协同过滤推荐算法[J].小型微型计算机系统.2014,(02):41-55

[12]尚海昆.K-means聚类算法的研究[D].网络投稿.中国知网. 2009

[13] 蒋,李梓,程晓旭.K-Means聚类算法研究及图形演示的实现[J].信息技术. 2010,(03):56-70

[14]何晓群.多元统计分析[M].第三版.北京:中国人民大学出版.2012:4-10 

[15]http://www.datatang.com/data/

[16]崔丹丹.K-Means聚类算法的研究与改进[D].网络投稿.中国知网. 2012

[17]刘建国;周涛;汪秉宏.基于K-means聚类算法的研究[J].自然科学进展. 2009,(01):6-17

致 谢

本文的最后,我真挚地感谢我的导师刘永财老师.本课题从选题到调研,再到实现与论文的最后完成,都是在刘老师悉心的指导与不懈的支持下完成的.他严谨的治学态度、精益求精的工作作风以及平时对我无微不至的关怀都深深地感动着我、激励着我.大学四年的学习过程中,刘老师给我提供了良好的学习、生活环境,对于生活中遇到的困难也尽力的给予指导和帮助.对刘永财老师的感激之情是无法用语言表达的,他所教会我的都将是我一生的财富.

同时要感谢我们班白一青,杨丽华,胡庆婉等老师们平时对我的细心教育与培养.这篇论文的完成,不仅仅有着导师刘老师对我的悉心指导,也有着每位老师平时上课对我的谆谆教导,才有了这篇论文的完成.每次与他们的讨论学习都使我受益匪浅.同时还要感谢在我实习期间仍然对我各方面进行关心和照顾的各位老师.

我还要感谢在一起度过四年美好时光的各位同门和我亲爱的舍友们,由于你们的帮助和支持,我才能克服一个个的困难与疑惑,直至本文中的完成.尤其要感谢我们组的成员,他们为本课题也作出了努力和贡献.感谢所有参考文献的作者们,他们在相关领域的研究成果对本文有很大的参考和启发价值.

最后,我要感谢我的父母与亲人,感谢他们的养育之恩,感谢他们对我的一如既往的支持和无私的奉献.

附录

附录一：将电影的评分进行分类

clear all

clc

x=[0 1 0 1 2 1 2 3 6 7 8 6 7 8 9 7 8 9 8 9;0 0 1 1 1 2 2 2 6 6 6 7 7 7 7 8 8 8 9 9];

figure(1)

plot(x(1,:),x(2,:),'r*') %%第一步选取聚类中心,即令K=2

Z1=[x(1,1);x(2,1)];

Z2=[x(1,2);x(2,2)];

R1=[];

R2=[];

t=1;

K=1; %记录迭代的次数

 dif1=inf; %%第二步计算各点与聚类中心的距离

dif2=inf;

while(dif1>eps&dif2>eps)

for i=1:20

    dist1=sqrt((x(1,i)-Z1(1)).^2+(x(2,i)-Z1(2)).^2);

    dist2=sqrt((x(1,i)-Z2(1)).^2+(x(2,i)-Z2(2)).^2);

    temp=[x(1,i),x(2,i)]';

  if dist1        R1=[R1,temp];

    else

        R2=[R2,temp];

    end

end

Z11=mean(R1,2);

Z22=mean(R2,2);

t1=Z1-Z11; %%测试两次是不是相等,可以有多种方法这里只简单的列举一种

t2=Z2-Z22;

dif1=sqrt(dot(t1,t1));

dif2=sqrt(dot(t2,t2));

Z1=Z11;

Z2=Z22;

K=K+1;

R1=[];

R2=[];

end

hold on

plot ([Z1(1),Z2(1)],[Z1(2),Z2(2)],'g+')

附录二：将评分分成四类数据

function [cid,nr,centers] = kmeans(x,k,nc)

[n,d] = size(x);

% 设置cid为分类结果显示矩阵

cid = zeros(1,n); 

% Make this different to get the loop started.

oldcid = ones(1,n);

% The number in each cluster.

nr = zeros(1,k); 

% Set up maximum number of iterations.

maxgn= 100;

iter = 1;

while iter < maxgn

%计算每个数据到聚类中心的距离

for i = 1:n

  dist = sum((repmat(x(i,:),k,1)-nc).^2,2);

  [m,ind] = min(dist); % 将当前聚类结果存入cid中

  cid(i) = ind;

end

for i = 1:k

%找到每一类的所有数据,计算他们的平均值,作为下次计算的聚类中心

  ind = find(cid==i);

  nc(i,:) = mean(x(ind,:));

  % 统计每一类的数据个数

  nr(i) = length(ind);

end

  iter = iter + 1;

end

% Now check each observation to see if the error can be minimized some more. 

% Loop through all points.

maxiter = 2;

iter = 1;

move = 1;

while iter < maxiter & move ~= 0

move = 0;

% 对所有的数据进行再次判断,寻求最佳聚类结果

for i = 1:n

  dist = sum((repmat(x(i,:),k,1)-nc).^2,2);

  r = cid(i);  % 将当前数据属于的类给r

  dadj = nr./(nr+1).*dist'; % 计算调整后的距离

  [m,ind] = min(dadj); % 早到该数据距哪个聚类中心最近

  if ind ~= r  % 如果不等则聚类中心移动

   cid(i) = ind;%将新的聚类结果送给cid

   ic = find(cid == ind);%重新计算调整当前类别的聚类中心

   nc(ind,:) = mean(x(ic,:));

   move = 1;

  end

end

iter = iter+1;

end

centers = nc;

if move == 0

disp('No points were moved after the initial clustering procedure.')

else

disp('Some points were moved after the initial clustering procedure.')

end

%调用后代码如下

[n,d] = size(x);

bn=round(n/k*rand);%第一个随机数在前1/K的范围内

nc=[x(bn,:);x(2*bn,:);x(3*bn,:);x(4*bn,:)];%初始聚类中心

[cid,nr,centers] = kmeans(x,k,nc)%调用kmeans函数

for i=1:9,

    if cid(i)==1,

      plot(x(i,1),x(i,2),'r*') % 显示第一类

      hold on

    else

     if cid(i)==2,

         plot(x(i,1),x(i,2),'b*') %显示第二类

         hold on  

   else

         if cid(i)==3,

             plot(x(i,1),x(i,2),'g*') %显示第三类

             hold on

         else

               if cid(i)==4,

             plot(x(i,1),x(i,2),'k*') %显示第四类

             hold on

               end

         end

     end

    end

end

strt=['红色*为第一类；蓝色*为第二类；绿色*为第三类；黑色*为第四类' ];

text(-4,-3.6,strt);

附录三：

%随机获取150个点

X=[randn(50,2)+ones(50,2);randn(50,2)-ones(50,2);randn(50,2)+[ones(50,1),-ones(50,1)]];

opts = statset('Display','final');

%调用Kmeans函数

%X N*P的数据矩阵

%Idx N*1的向量,存储的是每个点的聚类标号

%Ctrs K*P的矩阵,存储的是K个聚类质心位置

%SumD 1*K的和向量,存储的是类间所有点与该类质心点距离之和

%D N*K的矩阵,存储的是每个点与所有质心的距离;

[Idx,Ctrs,SumD,D] = kmeans(X,3,'Replicates',3,'Options',opts);

%画出聚类为1的点.X(Idx==1,1),为第一类的样本的第一个坐标；X(Idx==1,2)为第二类的样本的第二个坐标

plot(X(Idx==1,1),X(Idx==1,2),'r.','MarkerSize',14)

hold on

plot(X(Idx==2,1),X(Idx==2,2),'b.','MarkerSize',14)

hold on

plot(X(Idx==3,1),X(Idx==3,2),'g.','MarkerSize',14)

%绘出聚类中心点,kx表示是圆形

plot(Ctrs(:,1),Ctrs(:,2),'kx','MarkerSize',14,'LineWidth',4)

plot(Ctrs(:,1),Ctrs(:,2),'kx','MarkerSize',14,'LineWidth',4)

plot(Ctrs(:,1),Ctrs(:,2),'kx','MarkerSize',14,'LineWidth',4)

legend('Cluster 1','Cluster 2','Cluster 3','Centroids','Location','NW')

Ctrs

SumD下载本文