k均值聚类算法【基于用户行为聚类的个性化推荐算法】

　　[摘要]将介绍一种基于用户行为聚类的协同过滤推荐算法苛刻算法首先采用web日志和数据库记录的方法,将用户的行为记录下来,并将这些隐性的用户行为转化为显性的用户对项目评价;然后采用改进后的相似度计算方法计算用户之间的相似度;接着对用户进行聚类,将用户按照他们的行为自动地划分为若干个用户聚类簇;最后根据用户对最近邻居的评分来预测其对目标项目的评分,进而产生推荐。
　　[关键词]个性化推荐聚类分析协同过滤平均绝度误差
　　中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)1120074-01
　　
　　一、研究现状
　　
　　1.传统算法中在线执行效率低的问题。所谓的执行效率低即在海量用户数据中在线寻找目标用户邻居的过程非常浪费时间,针对该问题新的算法将采用用户聚类的方法建立离线模型,从而缩小邻居用户查找时的搜索空间,节省在线处理数据的时间,然后可对数据进行定期的更新,提高算法的执行效率。2.数据稀疏性问题。通过分析Web日志信息,将一些隐性信息转化为显性信息,可以解决此类问题的产生。
　　
　　二、算法的整体框架
　　
　　该算法首先采用web日志和数据库记录的方法,将用户的行为记录下来,并将这些隐性的用户行为转化为显性的用户对项目评价;然后采用改进后的相似度计算方法计算用户之间的相似度;接着对用户进行聚类,将用户按照他们的行为自动地划分为若干个用户聚类簇;最后根据用户对最近邻居的评分来预测其对目标项目的评分,进而产生推荐。
　　
　　三、数据的预处理
　　
　　本文采取了隐性提取用户信息的方法,通过分析电子商务网站服务器日志的方法去寻找用户的兴趣所在。一个用户对商品(或项目)的兴趣度可以体现在以下几个方面:用户是否对对商品和项目进行显性的评分;用户是否购买或收藏过某商品或项目,购买的数目;用户是否将一个商品或项目从自己的收藏列表中移除;用户对某商品或项目的点击次数;用户在某商品或项目的页面上停留的时间。
　　以上提到的各个因素都可以以web日志或数据库的形式保存。用户对商品的评分值就可以根据上面的几个因素来设定。如公式1.1所示,i表示用户编号;j表示商品或项目编号;表示用户i对商品j的隐性评分值;
　　表示用户i对商品j的显性评分值;表示用户i购买商品j的数目;表示用户i是否将商品j添加到收藏,添加为1,否则为0;表示用户i对商品j的点击次数;表示用户i在商品j的页面上停留的时间。隐性评分的计算公式如下:
　　其中,公式1.1中的是线性权重系数,它的大小可以通过经验来人为地确定。比如说用户显性评分的重要性一定要高于其他的权重值,而相比之下的值应该是最小的。第二种确定权重系数的方法就是通过统计的方法,利用线性回归来计算出 的具体的值。
　　通过上面的数据的预处理方法,我们就可以将隐性的用户行为转化为显性的用户对商品的评价。这样我们就可以得到用户-项目评价矩阵,该矩阵就是聚类分析算法的输入。
　　
　　四、离线聚类过程
　　
　　聚类过程的输入就是上一节得到的用户-项目评价矩阵,通过这一矩阵,使用相似度计算方法,既可以计算出用户之间的相似度,将这些计算结果用矩阵表示,即得到了用户相似度矩阵。接着我们采用4基于K-Means的用户行为聚类算法将用户进行聚类。
　　算法大致描述如下:使用改进后的相似度计算方法计算两两用户之间的相似度,得到相似度矩阵;采用聚类初始中心选取算法选取K个用户样本点形成K个聚类,每个聚类中只有一个用户样本点,其评分向量作为初始的聚类中心;计算其他每个用户样本点与各个聚类中心的相似性,将加入到与其最相似的聚类 中,并调整 的聚类中心,以 中与其他所有样本点距离和最近的点作为新的中心量;聚类终止条件:经过第C步的调整后,比较各个聚类中心是否与上一次聚类一致;或者调整前后,两个聚类中心的误差不超过一定的阈值。如果满足聚类终止条件,则聚类结束,否则回到C继续。最后得到聚类簇 。
　　
　　五、最近邻居用户的查找
　　
　　由聚类的性质可知,目标用户的最近邻居大部分都在与它同属于一个聚类簇中,因此不需要在整个用户空间上查找目标用户的最近邻居。所以,基于项目聚类的方法可以大大提高在线的最近邻居查找速度,满足推荐系统的实时性要求。
　　当用户U登陆以后,个性化推荐系统就会启动一个后台进程,来查找当前用户U的N个邻居用户,查找算法的大致描述如下:在数据库中查找用户U的所属的聚类簇这一字段,如果这一字段为空,则运行步骤B;如果对应的字段为i,及用户U属于聚类簇,运行步骤C;计算用户U与每一个聚类中心的相似度,找到相似度最小时对应的聚类簇,记做,运行步骤C;计算中每一个用户样本点与用户U的相似度,取相似度值最大的前N个用户作为用户U的最近邻居用户。
　　
　　六、预测和推荐的产生
　　
　　通过第五部分提到的方法得到用户 的最近邻居后,根据邻居用户集合中用户对各个项目的实际评分,我们就可以预测用户 对各个项目的评分。假设,用户 的邻居用户集合是,则用户 对项目的预测评分的计算公式如下:
　　其中 表示用户 与用户之间的相似度,表示用户对项目 的实际评分, 表示用户对所有项目的平均评分, 。表示用户
　　 对所有项目的平均评分。
　　最后,根据上述方法预测的用户 对所有目标项目的评分,选取预测评分最高的前N个项目(top-N)作为推荐结果返回给用户。
　　
　　七、小结
　　
　　本文我们提出并实现了基于用户行为聚类的个性化推荐算法,对用户进行聚类,利用得到的用户聚类寻找目标项目的最近邻居,只需要在与目标项目最相似的若干个聚类簇中搜索邻居,最后根据用户对邻居的评分来预测他对目标项目的评分。
　　
　　参考文献:
　　[1]Pang-Ning Tan,Michael Steinbach,Vipin Kumar.Introduction to Data Mining[M].人民邮电出版社,2006,5:305-402.
　　[2]鲁为,协同过滤算法及其在个性化推荐系统中的应用[D].北京邮电大学信息工程学院,2007.
　　[3]Jiawei Han,Micheline Kamber.Data Mining Concepts and Techniques[M].机械工业出版社,2006,4:383-648.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文