第44卷第3期 Vol. 44 No. 3 2017年3月 COMPUTER SCIENCE Mar.2017 基于人口统计学的改进聚类模型协同过滤算法 王媛媛李翔 (淮阴工学院计算机与软件工程学院淮安223003)(河海大学计算机与信息学院南京211100 摘要针对传統基于用户的协冋过滤推荐算法在大教据环境下存在评分高维稀疏性、推荐精度低的问题,提出一种 基于人口统计学数据与改进聚类模型相结合的协同过滤推荐算法,以提高推荐系统精度和泛化能力。该方法首先通 过用户人口统计学数据属性,结合用户-项目评分矩阵计算各个用户间的相似度;然后对用户、项目进行分层近邻传播 聚类,根据用户对项目的评分数据计算用户或项目之间的相似性,产生目标用户或项目的兴趣近邻;最后根据兴趣最 近邻进行推荐。对 Epinions, MovieLents等数据集进行仿真实验,仿真的结果表明,与传统的协同过滤算法相比,提出 的算法提高了推荐精度,为传统的协同过滤推荐算法提供了参考。 关键词协同过滤,人口统计学,聚类,推荐系统 中图法分类号TP183文献标识码ADOI10.11896/isn.1002137X2017.03,016 Study on Improved Clustering Collaborative Filtering Algorithm Based on Demography WANG Yuanyuan LI Xiang Faculty of Computer and Software Engineering, Huaiyin Institute of Technology, Huai'an 223003, China (College of Computer and Information, Hohai University, Nanjing 211100, China) Abstract The traditional user based collaborative filtering recommendation algorithm in large data environment has the problem of high dimensional sparse and low recommendation accuracy. a collaborative filtering recommendation algo- rithm based on the combination of demographic data and improved clustering model was proposed to improve the accu racy and generalization ability of the recommendation system. Firstly, this method calculates the similarity among diffe- rent users through the user demographic data attributes and the user-item score matrix. Secondly, hierarchical neighbor clustering of user and project, calculates the similarity between users or items by the user's score data for the project and generates interest in a neighbor of a target user or project. Finally, according to the recent interest in the nearest neighbor to recommend Simulation experiments on Epinions and MovieLents data set, the simulation results show that the proposed algorithm improves the recommendation accuracy compared with the traditional collaborative filtering al gorithm, provide reference for the traditional collaborative filtering recommendation algorithm. Keywords Collaborative filtering, Demography, Clustering, Recommender systems 推荐系统( Recommender Systems)是一种根据用户历史较成功的推荐算法受到了最广泛的关注2。随着移动应用的 数据建立用户兴趣模型,协助用户过滤不相关信息,可为用户迅速发展信息数据量呈指数级增长可,在大数据环境下,推 提供最佳的数据以满足用户个性化需求的信息系统。推荐荐系统一般会涉及社会网络数据、人口统计学数据语境感知 技术近几年已成为国内外研究和应用的热点,在电子商务在等多方面数据,这些多源数据一般为高维稀疏性数据,数据存 线影视、新闻媒体等各领域均有广泛应用,如亚马逊购物 在噪声和高冗余。研究表明:大数据环境下使用混合推荐算 Amazon)、淘宝网( Taobao)、优酷视频( Youku)、搜狐新闻 (Sohu)等。推荐系统可以辅助企业实现个性化营销,提升服法的推荐准确度高于单独使用一种推荐算法的 务质量和产品销量,为企业创造最大的利润 传统推荐系统的输入数据规模、冗余度及噪声较小,数据 根据所使用的推荐算法推荐系统主要分为以下几类:基稀疏性容易解决,使用协同过滤算法推荐效果较好大数据环 于用户行为的推荐系统、基于项目内容的推荐系统、基于语境境下的数据规模更大数据稀疏性冗余度、噪声更强⑤。本 感知的推荐系统以及基于人口统计学的推荐系统等。其文提出使用人口统计学方法统计聚类计算用户间相似度,解 中,基于用户行为推荐算法中的基于用户的协同过滤作为比决大数据环境下的数据稀疏性问题,从而提高推荐准确度。 到稿日期:201510-01返修日期:20160220本文受国家自然科学基金(61403060),江苏重点研发计划产业前瞻与共性关键技术 BE2015127),江苏省高校自然科学研究面上项目(15KJB520004),江苏省先进制造技术重点实验室开放基金( HGAMTL-1401),江苏省科技厅 产学研联合研究项目(BY2014097),淮安市科技计划项目(HAG2015060,HAG201602,HAC201601)资助 王媛嫒(1981-),女,博士生,讲师,CCF会员,主要研究领域为机器学习、人工神经网络,Emai246104417@qcom;李翔(1980-),男 博士生,副教授,主要研究领域为机器学习
第 44卷 第 3期 2017年 3月 计 算 机 科 学 COM PU TER SCIENCE Vo1．44No．3 M ar．2017 基于人 口统计学 的改进聚 类模 型协 同过滤算 法 王媛媛 李 翔 (淮阴工学院计算机与软件工程学院 淮安 223003) (河海大学计算机 与信息学院 南京 211100) 摘 要 针对传统基 于用户的协 同过 滤推荐 算法在大数据环境下存在评分 高维稀疏性 、推荐精度低 的问题 ，提 出一种 基于人口统计学数据与改进聚类模型相结合的协同过滤推荐算法，以提高推荐 系统精度和泛化能力。该方法首先通 过 用户人 口统计 学数据属性 ，结合用 户一项 目评分矩 阵计算各 个用户间的相似 度 ；然后对用户 、项 目进行分层近 邻传播 聚类 ，根 据用户对项 目的评分数据计算用 户或项 目之 间的相 似性 ，产生 目标 用户或项 目的兴趣 近邻 ；最后根据 兴趣 最 近邻进行推 荐。对 Epinions，MovieLents等数据 集进行仿 真实验 ，仿真的结果表 明，与传 统的协 同过 滤算法相 比，提 出 的算法提 高 了推荐精度 ，为传统的协 同过 滤推荐 算法提供 了参考 。 关键词 协 同过 滤，人 口统计 学，聚类 ，推荐 系统 中图法分类 号 TP183 文献标识 码 A DOI 10．11896／j．issn．1002—137X．2017．03．016 Studyon Improved Clustering CollaborativeFiltering Algorithm Based 011Demography W ANG Yuan-yuan LIXiang (FacultyofComputerandSoftwareEngineering，HuaiyinInstituteofTechnology，Huai’an223003，China) (Co llegeofCo mputerandInformation，HohaiUniversity，Nanjing211100，China) Abstract Thetraditionaluserbasedcollaborativefilteringrecommendationalgorithm inlargedataenvironmenthasthe problem ofhigh dimensionalsparseand low recom mendation accuracy．A collaborativefiltering recommendation algo— rithm based on thecombination ofdemographicdataandim proved clusteringmodelwasproposedtoim provetheaccu— racy andgeneralizationability oftherecomm endation system．Firstly，thismethod calculatesthesimilarityam ongdifferentusersthroughtheuserdemographicdataattributesandtheuser-item scorematrix．Secondly，hierarchicalneighbor clustering ofuserandproject，calculatesthesimilaritybetweenusersoritemsbytheuser’sscoredatafortheproject， andgeneratesinterestinaneighborofatargetuserorproject．Finally，accordingtotherecentinterestinthenearest neighbortorecommend．SimulationexperimentsonEpinionsandMovieLentsdataset，thesim ulationresultsshow that theproposedalgorithm improvestherecomm endationaccuracy compared with thetraditionalcollaborativefiltering al— gorithm，providereferenceforthetraditiona1collaborativefilteringrecommendationalgorithm． Keywords Collaborativefiltering ，Demography，Clustering，Recomm endersystems 推荐系统 (RecommenderSystems)是一种 根据用 户历 史 数据建立用户兴趣模型，协助用户过滤不相关信息，可为用户 提供最佳的数据以满足用户个性化需求的信息系统Ⅲ。推荐 技术近几年已成为国内外研究和应用的热点，在电子商务、在 线影视、新 闻媒体等各领域均有广泛应用，如亚马逊购物 (Amazon)、淘宝 网 (Taobao)、优 酷 视 频 (Youku)、搜 狐 新 闻 (Sohu)等。推荐系统可以辅助企业实现个性化营销，提升服 务 质量 和产品销量 ，为企业创造最大 的利 润。 根据所使用 的推荐算法 ，推荐 系统主要分为以下几类 ：基 于用 户行为的推荐系统 、基 于项 目内容 的推荐 系统 、基 于语境 感 知的推荐 系 统 以及基 于人 口统 计学 的 推荐 系统 等E13。其 中，基于用户行为推荐算法中的基于用户的协同过滤作为比 较成功的推荐算法受到 了最广泛 的关注|2]。随着移动应用 的 迅速发展，信息数据量呈指数级增长[3]，在大数据环境下，推 荐系统一般会涉及社会 网络数据 、人 口统计学数据 、语境感 知 等多方面数据 ，这些 多源数据一般 为高维稀疏性数据 ，数据存 在噪声和高冗余 。研究表 明 ：大 数据环境 下使用混合 推荐 算 法的推荐准确度高于单独使用一种推荐算法的[4]。 传统推荐系统的输入数据规模、冗余度及噪声较小，数据 稀疏性容易解决 ，使用协 同过滤算法推荐效果较好 ；大数据 环 境 下的数据规模更大 ，数据 稀疏性 、冗余度 、噪声 更强 [。本 文提出使用人 口统计学方法统计聚类计算用户间相似度 ，解 决 大数据环境下的数据稀疏性问题 ，从而提高推荐准确度 。 到稿 13期 ：2015～10—01 返 修 日期 ：2016—02—20 本 文受 国家 自然 科学 基 金 (61403060)，江 苏 重 点研 发 计 划 业 前 瞻 与共 性 关键 技 术 (BE2015127)，江苏省高校 自然科学研 究面上项 目(15KJB520004)，江苏省先进制造技术重点实验室开放基金 (HGAMTI，1401)，江 苏省科 技厅 产学研联合研究项 目(BY2014097)，淮安市科技计划项 目(HAG2015060，HAG201602，HAC201601)资助 。 王媛媛 (1981一)，女 ，博士 生 ，讲师 ，CCF会员 ，主要 研究领域 为机 器学 习、人工 神经 网络 ，E-mail：461044170@qq．com；李 翔(198O一)，男 ， 博士生 ，副教授 ，主要研究领域为机器学习
计算机科学 2017年 1相关问题 2.1联合聚类预测未知项 使用联合聚类预测评分矩阵中的未知项,详细步骤如下: 1.1协同过滤算法 1)初始化评分属于某类别的概率p(ku,v,r),满足 协同过滤算法由 Goldberg等于192年提出,该算法2(kla,r)=1 据,使用算法分析用户兴趣特征,搜索与特定用户有相似兴趣 (k|a)+a×[p(k)+p (rm|k)+0 的邻居用户,分析相似用户评价生成指定用户喜好物品的推1D)+0又pkD+xDk2)+ (1) 荐值。基于用户行为的传统协同过滤推荐算法过分依赖历史其中,a,月,0为超参数,为避免分母为O,均一化为0.000 数据,对历史数据质量的要求较高,若缺少新用户和新项目的pka)为用户属于某类别的概率,p(k|)为项目属于某一类 评分信息,则对新用户的信息推荐准确率较低。 另外在大数据环境中,用户以及项目的评分数据相对较别的概率 p(ku, U, ra. v) 少导致评分矩阵具有稀疏性因此目前大数据环境下使用传p(kln)=2p(z1,,r 统协同过滤推荐算法推荐的准确度不理想。目前,国内外 学者提出了很多为克服评分矩阵稀疏性并提高推荐准确性的 p(ku, u,ru, v) p(klv) p(z (3) 改进算法,主要有以下的改进组合思路:混合、加权特征组 合、变换、特征扩充以及元级别等方式。例如,文献[9提出了 2)由式(2)式(3)重新计算p(k|u)和p(k|v) 用户人口统计结合专家评分的协同过滤算法,但是有些数据 3)计算评分值概率pdw(r,|k)。 集中不存在专家评分数据,专家与用户的背景知识可能有区 别,所以专家的评分数据存在准确性的问题;文献[10]提出使 Pagrete(ru, I k) 用人口统计信息分析技术融合EM算法进行用户聚类;文献4)选择概率最大的k作为此评分的类别,循环步骤2)至 [11]利用社交网络中的好友信任关系缓解了评分数据的稀疏收 性;文献[2]提出使用划分聚类改进推荐算法;文献13]提出2.2基于人口统计学数据计算用户相似度 高维无参数的分裂层次聚类技术;文献[14提出对多次提取 用户间的相似性计算是目前推荐算法的关键,其准确性 的大规模的样本进行聚类处理,进而确定自然族质心的初始直接影响到推荐的准确性。传统协同过滤推荐算法计算用户 位置对推荐算法进行改进;文献[15提出一种基于边缘度密相似性的主要方法有基于 Spearman相关系数的相似度基于 度距的聚类方法。 夹角余弦的相似度、基于 Jaccard相关系数的相似度、基于 1.2基于人口统计学数据的推荐 Tanimoto相关系数的相似度、修正余弦相似度以及绝对指数 基于人口统计学的推荐是根据人口统计学数据(一般包 相似性等计算方法。但是这类方法在大数据环境中的数 括人的年龄性别、国籍、民族、工作、学历、出生地等)对每个 用户建立一个用户剖面( User Profile)进行聚类,系统通过聚据稀疏概率较高,本文结合人口统计数据计算相似度。 类计算用户间相似度,得到当前用户的最近用户邻集并以这 用户相关的人口统计数据可以反映用户偏好,结合此类 些用户作为协同过滤的计算用户集最后系统将邻集中评分信息计算用户相似度的准确性更高。文献[19的研究发 较高的项目推荐给当前用户16。 现用户的人口统计数据属性如性别、年龄、职业、文化程度、地 文使用用户人口统计学数据计算用户之间必要相关属理位置、收入水平等特征信息对用户的兴趣偏好有影响。本 性的相似度,再使用文献[17提出的改进的分层近邻传播文根据上述特征维度属性进行用户聚类。用户人口统计属性 ( Hierarchical Affinity Propagation,HAP)算法对用户进行聚向量为(d:,d,…,dk,…,dhn),先计算用户在每一维属性上的 类处理,最后将组内所有的用户的推荐结果进行聚合按照推相似度,再结合需要使用的属性计算最后的相似度。文本考 荐评分数据推荐给指定用户 虑在数据稀疏情况下使用文献[19]提出的相似度计算方法: 2算法设计 使用传统的协同过滤算法计算用户相似度,一般不考虑其中,n为用户属性个数,mn(加,9s)为用户白和q在d属 与用户、项目相关的其他属性。本文使用用户的人口统计学性的相似度,w(d)是4属性的权值。用绝对指数相似性计 数据属性对用户之间的相似度进行判断,再使用改进的分层算sim(pa,4),公式如下 近邻传播算法对用户进行层次聚类,以达到更好的推荐效果 sim(Pa, g a)=e 1)使用联合聚类预测评分矩阵中的未知项; 相对权值t(dk)是dk属性区别不同用户的能力,那么用 2)使用用户人口统计学数据属性,并结合联合聚类结果户在d属性两个维度之间评分最高的t个项目不相同的平 3)根据上一步的结果对用户,项目进行分层近邻传播聚均个数是ad),权值ud4)为 类,由用户对项目的评分数据计算用户或项目之间的相似性 we(dk= 产生目标用户或项目的兴趣近邻; ∑ave(dh) 4)根据兴趣最近邻预测目标用户对待推荐项目进行目标 结合以上3个公式计算任意两个用户在人口统计学数据 推荐 中的用户相似度值
64 计 算 机 科 学 2017正 1 相 关 问题 2·1 1．1 协同过滤算法 协 同过滤 算法 由 Goldberg等l6于 1992年提 出 ，该算 法 主要 考虑用户 和项 目协 同过滤 ，根 据用户对各 项 目的评 分数 据 ，使用算法分析用户兴趣特征 ，搜索 与特 定用 户有 相似兴趣 的邻 居用户 ，分析相似用户评价 ，生成 指定 用户喜好 物品的推 荐值 。基于用户行为的传统协同过滤推荐算法过分依赖历史 数 据 ，对历史数据质量 的要求较高 ，若 缺少 新用户 和新项 目的 评分信息，则对新用户的信息推荐准确率较低。 另外 在大数据环境 中，用 户 以及 项 目的评分数 据相对 较 少，导致评分矩阵具有稀疏性，因此目前大数据环境下使用传 统协 同过滤推荐算法推 荐 的准确 度不理 想E 。目前 ，国内外 学者提出了很 多为克服评分矩阵稀疏性并提高推荐准确性 的 改进算法 ，主要有 以下 的改进组合思路[8]：混合 、加权 、特 征组 合、变换、特征扩充以及元级别等方式。例如，文献1-9]提出了 用户人 口统计结合专 家评分 的协 同过滤算法 ，但是 有些数据 集 中不存 在专家评分数 据 ，专 家与用户 的背景知识 可能有 区 别，所以专家的评分数据存在准确性的问题 ；文献Elo]提出使 用人 口统计信 息分析技术融 合 EM 算法进 行用户 聚类 ；文献 [11]利用 社交网络中的好友信任关系缓解 了评分数据的稀疏 性；文献[12]提出使用划分聚类改进推荐算法；文献[13]提出 高维无参数 的分裂层次 聚类技 术 ；文献E14]提 出对 多次提取 的大规模 的样本进行 聚类处理 ，进而 确定 自然簇 质心 的初始 位置对推荐算法进行 改进 ；文献 [15]提 出一种 基于边 缘度 密 度距 的聚类方法 。 1．2 基 于人口统计 学数 据的推荐 基于人 口统计学 的推荐是根据 人 口统 计学数 据 (一般包 括人 的年龄 、性 别 、国籍 、民族 、工作 、学 历、出生地 等)对每个 用户建立一个用户剖 面(UserProfile)进 行聚类 ，系统通过 聚 类计 算用户 间相 似度 ，得到 当前用 户的最近用 户邻集并 以这 些用 户作为协 同过滤 的计算 用户集 ，最后 系统 将邻集 中评 分 较高的项 目推荐给当前用户l1。 本文使用 用户人 口统计 学数据计 算用户之间必要相关属 性的相似度，再使用文献[17]提 出的改进 的分层近邻传播 (HierarchicalAffinityPropagation，HAP)算 法对用 户进行 聚 类处理，最后将组内所有的用户的推荐结果进行聚合，按照推 荐评分数据推荐给指定用户。 2 算法设 计 使用传统的协同过滤算 法计算 用户相似 度 ，一 般不 考虑 与用户 、项 目相关 的其他属 性。本文使用 用户 的人 171统 计学 数据属性 对用户之 问的相似度 进行判断 ，再使用 改进的分层 近邻传播算法对用户进行层次 聚类 ，以达到更好 的推荐效果 。 1)使用联合聚类预测评分矩阵中的未知项； 2)使用用户人 口统计 学数据属 性 ，并 结合 联合 聚类 结果 计算各个用户间 的相似度 ； 3)根据上一步的结果对用户、项 目进行分层近邻传播聚 类 ，由用户对项 目的评分数据计算用户或项 目之间 的相似性 ， 产生 目标用 户或项 El的兴趣 近邻 ； 4)根据兴趣最近邻预测 目标用户对待推荐项 目进行目标 推荐 。 联合聚类预测未知项 使用联合聚类预测评分矩阵 中的未知项 ，详细步骤如 下 ： 1)初 始化评分 属于某 类别 的概率 p(klU，， ，)，满 足 ： ∑ (愚I“，口， ，)一1。 p(kI“，， ，。)一 [ 垒j ± [垒!垒l ± !：l鱼± [户(愚l“)+口]×[户(忌I)-I-冈×[户(，l忌)+ 其中 卢，0为超参数 ，为避免分母为 0，均一化为0．000000001， p(kI“)为用户属于某类 别的概率 ，p(kf)为项 目属 于某一类 别的概率 。 ∑ p(kl“，， ，) p(k 一 厢 ∑ p(k1“，口， ，) p(kl 一 (3) 2)由式 (2)、式 (3)重新计算 p(kI“)和 p(kl)。 3)计算评分值概率 ( ．l愚)。 胪袁 端 ㈩ 4)选择概率最大 的 k作为此评分 的类别 ，循环步 骤 2)至 收敛 。 2．2 基于人 口统计学数据计算用户相似度 用户间的相似性计算是 目前推荐算法的关键 ，其准确性 直接影响到推荐的准确性。传统协同过滤推荐算法计算用户 相似性的主要方法有基于 Spearman相关 系数的相似 度 、基 于 夹角余 弦 的相 似度 、基 于 Jaccard相 关 系数 的相 似 度 、基 于 Tanimoto相关系数的相似度 、修正余 弦相似度 以及 绝对 指数 相似 性等计算 方法m]。但是 这类 方法在 大数 据环境 中的数 据稀 疏概 率较高 ，本文结合人 口统计数据计算相似度 。 用户相关的人 口统计数据 可 以反 映用户 偏好 ，结合 此类 信息计算用户相似度的准确性更高m]。文献[19]的研究发 现用户的人 口统计数据属性如性别 、年龄 、职业 、文化程 度 、地 理位置 、收入水平等 特征信 息对用户 的兴趣偏 好有 影 响。本 文根据上述特征维度属性进行用户聚类 。用户人 口统计属性 向量为 (dl，d2，…， ，… ， )，先计算用户在每一维 属性上 的 相似度 ，再结合需要使 用 的属 性计算 最后 的相 似度 。文本 考 虑在数据稀疏情况下使用文献[19]提出的相似度计算方法 ： sim(p，q)一Z[-sim(p战，％ )]× (dk) (5) 其 中， 为用户属 性个数 ，sim(p,~，％ )为用户 P和 q在 d 属 性 的相似度 ，w(d)是 以 属 性的权值 。用绝 对指数 相似性 计 算 sim(po~，‰ )[。，公式如下： 弓 ． sire( ，钕 )一 e =1’’ Tm,q (6) 相对权值 (dk)是 dk属性 区别不 同用户 的能力 ，那 么用 户在 属性两个维度之 间评分 最高 的 t个项 目不 相 同的平 均个数是 “ (以)，权 值 训(dk)为： w(dk)一 (7) 口ve(dk) 结合 以上 3个公式计算任意两个用户在人 口统计学数 据 中的用户相似度值
第3期 王媛媛,等:基于人口统计学的改进聚类模型协同过滤算法 65 2.3HAP用户聚类算法 线服务网站epinions.com上的49290个用户、139783个物 HAP聚类方法主要是分层获取数据集的聚类中心。首品、664824个评分以及487181个朋友关系数据 先在各个数据子集中分别执行AP聚类,得到子集的聚类中 Movielens数据集由美国 Minnesota大学计算机科学与 心后再对子集的聚类中心执行聚类,最终得到原数据集的聚工程学院Grouplens项目组收集Movielens网站(http:// 类中心;然后以各聚类中心为初始类,将数据元素重新划分至 movielens, umn.edu/)上大量用户的电影评分得到,评分等 与其相似度最大的聚类中心所在的类最终实现聚类。级为1-5,5表示最喜欢,1表示最不喜欢,用户通过评分 对于任意用户属性i计算其他用户对其的吸引度r(x,)的数值表达了自己的兴趣爱好,数据集下载地址:htp:/ 和归属度a(i,j)。HAP算法的核心是r(i,j)和a(i,j)两个 ww. grouplens.org/node/73。本实验中选取了 Movielens 值的不断更新,公式为 (M), Movielens(100k)以及 MovieLens+3个不同规模的 e_a(i,)=m(0,,)+.,mx,k,),()数据集作为实验数据,其中Myd(1MD包含了1mlon r(i,j)=s(i,j)-maxla(i, k)+s(i, k)) tings from 6000 users on 4000 movies: MovieLens (100k)a 基于人口统计学数据的用户聚类 A 100000 ratings from 1000 users on 1700 movies: Movie 在基于人口统计学数据计算用户相似度值的基础上,使Lems+包含了8598 ratings from2113 users on10197mo 用分层近邻传播聚类算法对用户进行聚类。结果显示,同类 用户比异类用户之间的属性更接近。 3.2实验计算框架 1)输入用户集U与用户相似度矩阵D 本文实验采用目前流行的大数据计算框架 MapReduce, 2)根据21节中的公式计算相似度,并从相似度矩阵中该框架可以实现对大型数据矩阵进行快速计算,也为个性化 求出最大相似度 x(sim(u, D) (10)推荐系统提供计算支持。实验中在服务器上搭建3台虚拟 机,第一台虚拟机用作 NameNode节点,第二台虚拟机用作 其中,和v为任意用户集中的任意两个对象 SecondNameNode节点,第三台虚拟机用作 JobTracker节点 3)若任意两个用户对象u和v的sim值相同,则将两个3台虚拟机同时也是 Data Node节点,模拟 Hadoop集群的负 用户对象划分为同类,再使用2.3节中的方法进行用户聚类 执行上述步骤,直到聚类数量达到实际应用系统的要求 载均衡环境。实验采用 MapReduce和Java代码实现 3.3推荐实验结果对比 再进行预测结果推荐。 2.5预测推荐 实验中选用NDCG2( Normalized Discounted Cumula 经过基于人口统计数据的相似度计算以及分层近邻传播 tive gain)排名和ER43( Expected Reciprocal Rank)作为 用户聚类系统根据式(7)预测某类用户对项目的评分并按分评价指标。训练数据集随机选择60%和80%两种比例,项目 值排序推荐给指定用户。 特征维度D取8和16两种维度。为了比较所提出的DCCF ∑.sin(p,q)r 方法的性能,选用WRMF, BPRME2, Weighted BPRMF pred(p, i) (11)(WBPMF)[28, Soft Margin Ranking MF (SMRMF)(29)CK Quadratic Matrix Factorization(QMF)5种方法做比较,同时 3实验结果与分析 i F Matrix Factorization(MF)(3o, Biased Matrix Factoriza- 3.1实验数据集 tion( Biased mr)3作为基准线 选取 epinions, Movielen(1M), Movielen(100k)以及 从图1-图4、表1-表4中可以看出,本文提出的DCCF velen+4个真实数据集进行实验。 方法在NDCG和ERR两种评价指标中排序准确率均较高, Epinions数据集(htp://ww.epinions.com)包含了在取得了较好的结果。 Hm1m富 (epinions, train=0. 60, D=8 (b)epinions, train=0. 60, D=16 M ESe NDCG5 NDOG10 NDCI DCOln NDX2 ERRS ERRI ER (e)epinions, train=0, 80, D=8 (epinions, train=0. 80, D=16 图1 Epinions数据集比较结果
第 3期 王媛嫒 ，等 ：基于人 口统计学 的改进聚类模型协 同过滤算法 65 2．3 HAP用户聚类算法 HAP聚类方 法主要 是分 层获取 数据 集 的聚类 中心 。首 先在各个数据子集 中分别 执行 AP 聚类 ，得 到子集 的 聚类 中 心后再 对子集 的聚类 中心 执行聚类 ，最终得 到原数据 集的 聚 类 中心 ；然后 以各聚类 中心为初始类 ，将 数据元素重新划分至 与其相似度最大 的聚类 中心所 在的类 ，最终 实现 聚类 l2 。 对于任意用户属性 ，计算其他用户对其 的吸引度 r(i，) 和归属度 a(i，)。HAP 算法 的核心 是 r(i，)和 “(i，)两个 值 的不断更新 ，公式为 ： r(i，)一s(i，)一max{a(i，)+ (i，是)) (8) ≠j a(i，)=min(0，r(j，)+ ∑ max(0，r(k，J)))，≠ (9) 2．4 基于人 口统计学数据的用户聚类 在基 于人 口统计 学数据计 算用 户相似度 值 的基 础上 ，使 用分层 近邻传播 聚类 算法 对用户进 行 聚类 。结 果显 示 ，同类 用户 比异类用户 之间的属性更 接近 。 1)输入用户集 U 与用 户相 似度 矩阵 D。 2)根据 2．1节 中的公 式计 算相似度 ，并从 相似 度矩 阵 中 求 出最 大相似度 ： 5‰ 一 max(sire(U， )) (10) 其 中，U和 为任意用户集中的任意两个对象 。 3)若任意两个用 户对象 U和 的 sim 值相 同，则将 两个 用户对象划分为同类 ，再使用 2．3节中的方法进行用户聚类。 执行上述步骤 ，直到聚类数量达到实 际应用 系统 的要 求 ， 再进行预测结果 推荐 。 2．5 预测推荐 经过基于人 口统计数据 的相似度计算 以及分层近邻传播 用户聚类 ，系统根据式(7)预测某类用户对项 目的评 分并 按分 值排序推荐给指定用户 。 一 sim(p，q)rq， pred(p)=口∈ neighl_(户) 丽 (11) 3 实验 结 果与分 析 3．1 实验 数据集 选 取 Epinions，MovieLen(1M )，MovieLen(100k) 以 及 MovieLen+ 4个 真实数据集进行 实验 。 Epinions数据集 (http：／／ epinions．corn)包 含 了在 ( l a)epin i ions，tr l ain蓬= 0l．6蠢0，Di=8 l ( lc) 蠢epinilons，triain蠢=Oi．80，Dl=8 l 线服务 网 站 epinions．corn 上 的 49290个 用 户 、139783个 物 品、664824个评分 以及 487181个朋友关系数据 。 MovieLens数据集由美 国 Minnesota大学计算机科学与 工程学 院 GroupLens项 目组 收 集 MovieLens网站 (http：／／ movielens．unln．edu／)上 大量 用户 的 电影 评 分 得 到 ，评 分 等 级 为 1—5，5表示 最 喜欢 ，1表示 最 不 喜欢 ，用 户通 过 评 分 的数值 表达 了 自己 的兴 趣 爱 好 ，数 据 集 下 载 地址 ：http：／／ grouplens．org／node／73。本 实验 中选 取 了 MovieLens (1M)，MovieLens(1OOk)以及 MovieLens+ 3个不 同规模 的 数据集作 为实验数据 ，其 中 MovieLens(1M)包含 了 1million ratingsfrom 6000userson4000movies；MovieLens(100k)包 含 了 100000ratingsfrom 1000userson 1700movies；Movie Lens+包含 了 855598ratingsfrom 2113userson10197moV les 。 3．2 实验计算框架 本 文实验采用 目前流行 的大数据计 算框架 MapReduce， 该框 架可 以实现对大型数据 矩阵进行快速 计算 ，也 为个性化 推荐 系统提 供计 算支持 。实验 中在 服务 器上搭 建 3台 虚拟 机 ，第一 台虚拟 机用 作 NameNode节点 ，第 二 台虚 拟机用 作 SeeondNameNode节点 ，第三 台虚拟机用 作 JobTracker节点 ； 3台虚拟机 同时也 是 DataNode节 点 ，模 拟 Hadoop集群 的负 载均衡环境 。实验采用 MapReduee和 Java代码 实现。 3．3 推荐实验结果对 比 实 验 中选 用 )C 船](NormalizedDiscountedCumulativeGain)排名 和 ERR[24253(ExpectedReciprocalRank)作 为 评价指标 。训练数据集随机选择 6O 和 80 两种 比例 ，项 目 特征维度 D取 8和 16两种维度 。为了 比较 所提 出的 I)(二CF 方法 的性能 ，选用 WRM ]，BPRM~。 ，WeightedBPRMF (WBPMF)[0 ，SoftMarginRankingMF (SMRMF) 以 及 QuadraticMatrixFaetorization(QMF)5种方法做 比较 ，同时 选 用 MatrixFaetorization(MF) ，BiasedMatrixFaetoriza— tion(BiasedMF)[“]作为基准线 。 从 图 1一图 4、表 1一表 4中可以看出 ，本文提出的 DCCF 方法在 NDCG和 ER 两种评 价指 标 中排序准 确率 均较 高 ， 取得 了较好 的结果 。 iil耋~I,Htl i蠢落l蠢ili 图 1 Epinions数据集 比较结果 ～ ■鼹 赫 耩 嚣一 ～ ■ 绻黟 ～霸 ．一 ～ ■耩 鞋 鹱 翁■ ～ —雅 霉 必 —■
计算机科学 2017年 表1 Epinions数据集比较结果 train=0. 60 Method D=8 NDOG@20 ERR@20 NDCG@20 ERR@20 NDCG@20 ERR@20 NDCG@20 ERR@20 0.7344 0.7652 0.734 0.7393 0.7393 0.7516 Biased 0.7344 76520.73440.76520.73930.75160.73930.7516 WRMF 0.73740.72330.7424 0.732 0.735 0.7397 0.736 0.7216 0.7367 0.7331 0.732 0. 0.7 0.73740.770.74590.76760.746 0.72390.74080.72370.7396.73390.7305.7343 0.8233 0.8691 8 0.8634 QMF-COS 0.807 0.850.79960.84190.80580.83310.7994 8246 0.8629 0.844 0.8433 (a Movielens (IM, train=0. 60, D=8 (b)Movielens( IM, train=0. 60, D16 ()Movielens(lM, train=0. 80, D8 (d)Movielens(IM), train=0. 80. D=16 图2 Movielens(1M数据集比较结果 表2 Movielens(IM数据集比较结果 train=0. 60 train=0& D=16 D=8 NDCG@20 ERR@20 NDCG@20 ERR@20 NDCG@20 ERR@20 NDCG@20 ERR@20 MF 0.611 0.680 0.61120.68010.63930.6725 0.6393 0.6725 W图 0.6112 0.6112 0.63930.6725 0.7120 0.7049 0.7304 0.78950.7265 0.7835 0.78720.69670.7749 0.7304 0.78690.7245 0.6252 0.6893 0.6663 0.7010 0.6660 0.7000 0.7424 0.671 0.7524 0.6987 MF-PL 74700.82310.74670.82350.77100.81740.77090.8174 QMF-COS 0.7239 0.70510. 0.7619 0.7562 0.8134 (a)Movielens(100k), train=0. 60. D b)Movielens(100k), train=0. 60, D=16 NDGS NDXXG1O NDCG20 ERRS ERRIO FRR2TX (c) Movielens(100k, train=0. 80. D=8 (dMovielens(100k), train=0. 80, D=16 图3 Movielens(100k)数据集比较结果
66 计 算 机 科 学 2017矩 表 1 Epinions数据集 比较结果 NDCGl5 NDCGj10 ND( 20 ERR委5 ERRl10 ERRl20 (a)Movielens(1M)。tra／r／=0．60．D=8 NDCC~ NDCG10 NDCG20 ERRS ERR10 ERR20 (c)Moviehns(1M)，train=O．8O．D一 8 毫 鏊强 QMF~,OS 辩 QMI,"一PI． SMRMF 嚣■WRBPRMF M F 豪鋈 QMF~3OS 雅 QMF-PL SM RM 壤WBPRMF ■ WRMF NDCGj5 NDCGl10 NDCGl20 ERR耋S ERRi10 ERR20 毫Bm蹦~xlM 喾QM FCOS 数 QMF—PI． SM RMF 嚣 WBPRMF — WRMF (b)Movielens(IM)，train= 0．60．D一 16 NDCGS N／X~．G10 NDCG20 ERRS ERRl0 ERR20 SM RMF W BPRMF ■WRMF (d)Movielens(1M)．train=0．8O。D一 16 图 2 Movielens(1M)数据集 比较结果 表 2 Movielens(1M)数据集 比较结果 NI)c‘ NDCG10 N1)CLT~20 ERRS ERR10 ERR20 (a)Movielens(10ok)，train= 0．60，D一8 NDCGS NDCG10 NDcG20 ERR6 ERR10 ERR20 (c)Movielens(100lO，train=O．8O．D 8 毫 翟QMF~()S 凝 QMF—PL Shn【MP 辩 WBPRMF iWRMF 墓蓄 。 强 QM E．．COS 鞣 QMF—PL SM RMF 莲 WBPRMF ■ WRMF NI)cGS NDCGIO NI}CG2~} ERRS ERRIO ERR20 童DCCF ■MF QMF．CC避 鞭 QⅦ 一PL SMRMF 蕊■WW BRPMRFMF (b)Movielens(100k)，train=O．6O，D= 16 NⅨ ：GS NDCG10 NDCG20 ERRS ERR10 ERR20 一 BiasedMF 誊QM F．COS 瓣qMF—PI S~tRM F 嚣 WBPRMF — WRMF (d)Movielens(100k)，train= 0．8O。D一 16 图 3 Movielens(100k)数据集 比较结果 ■■¨■■●=膏：=Ⅲ：==j疆jjl署 。鏊嚣融啊融暇隔 啪嘴 !詈啪嘴 !彗咖 啪嘴咖哺 嘶晰嘴呦 ■=：■：■：■=I=■甜■I¨t■¨t¨■■I 篓瞳隧隧隔 嘲 哪 啪嘶唧嘴咖 唧嘴 哺啪懈 咖 嘴啪嘛 !堇咖嘴呦!莹 嘴啪嘶啪嗡嗡{莹啪 嘶哪 啪旧啪嗡唧 l莹咖惦咖嘴蛳嘴呦
第3期 王媛媛,等:基于人口统计学的改进聚类模型协同过滤算法 表3 Movielens(100k)数据集比较结果 Method D=8 D=16 D=16 NDCG@20 ERR@20 NDCG@20 ERR@20 NDCG@20 ERR@20 NDCG@20ERR@20 6476 0.6372 0.6092 0.637 WRMF 0.7595 0.7691 0.7551 IPRMF 0.6961 0.7401 0.6904 0.7421 0.7402 BPRME 0.67330.63880.67160.6972 0.674 0.7179 QMF-PL. 0.76280.81 0.7619 0.7992 0.8077 QMF-COS 0 7106 0.7605 0.6873 0.7287 0.7242 9410.7674 4■ (aMovielens+, train=0. 60, D= (b)Movielens+, train=0. 60,D=16 (c)Movielens+, train=0. 80. D=8 (d) Movielens+, train=0. 80, D=16 图4 Movielens+数据集比较结果 表4 Movielens+数据集比较结果 air=0. 6 Method 0.523 0.57040.6037 0.7399 BPRMF 0.63730.6710 0.609 0.6442 0.6847 0.6983 0.6989 0.7751 0.73280.7636 0.6471 0.6230 0.7034 0.6909 0.7441 7412 图5和图6是NDCG@10以及ERR@10在 Epinions, Movielens(1M数据集上的迭代过程数据。 口 learning (a)epinions, train=0. 60 (b)epinions,train=0. 60 g~,的含 (epinions,train=0.80 图5NDG@10,ERR@10在 Epinions数据集上的迭代过程数据
第 3期 王媛媛 ，等 ：基于人 口统计学的改进聚类模型协 同过滤算法 67 表 3 Movielens(100k)数据集 比较结果 NDC~Gj5 NDCGl10 NlYCGl20叠ERR重5 ERR10 (a)Mo~elens+ ，train=O．60， NDC ( G c j5 )M NIX ov ?G i ie 10 le N n D s C + G2 ， O tr E a R in R45 =O．8Oi，D=R820 基黧 蒜 DccF ■ MF qMF-COS 耩 QMF—PL SMRMF 剖 W BPRMF ■ WRMF ■ Bia“ MF 爨簟MF QM Fc f 鼹 QMF’PL SMRM F ％ WBPRMF ■ WRMF 翻NDCG5 (b NDCG5 翮 瑚NDCG10 Nlx)G∞ ERR5 ER】tl0 ERK∞ ． D= 16 翻ERR20 (d)Movielens+ ，train= O．80．D一 16 图 4 Movielens+数 据集比较结果 表 4 Movielens+数 据集比较结果 暑嚣 DCCF ■ MF QMF_c0S 黼 QMF~PL SM RMF WBpRM F — WRMF ■B F 蚕QMF~COS 黼 QMF—PL SMP2dF 菇WBPRMF — WRMF 图 5和图 6是 NDCG@10以及 ERR@10在 Epinions， MovieLens(1M)数据集上的迭代过程数据。 0 10 lterstio (a)epinions，train=0．6O 20 30 40 50 Iteration (c)epinions，train= O．80 骨 [ean~ing ratenO05 △ l~rning ratc~O01 0 learning tn 锄瞒 日 learning rate~0,1 舟 learning 005 △ learnleg rate~0．01 甘 learning te一姐05 0 k~rnhag ra1 姐 l O耵 5 Q855 。 (1腼 爱o8l5 tt795 0775 n 755 2o ∞ 40 50 Iteration (b)epinions，train=O．6O 0 lo 20 鼬 40 50 Iteration (d)epinions．train= O．8O 图 5 NIX3G@10，ERR@10在 Epinions数据集上的迭代过程数据 learning r丑 司l加5 △ learningrat n0l 0 learning i~tt@t也05 0 learning m -0．I 静 learning Ie 彻 畸 △ learning r日t姐01 0 leanling rate-~ 06 口 learning rate~02 =：==：=== ==：㈣ 呻==：==：=鞠 鲞嚣盛睡 函匪 啪 嘶唧 嘴 咖啡唧啦咖 “ ¨ “ === “ ¨ 畚 惑匿 麓墼函露 ㈣嘛啪嘶哪嘶㈣ 嘶㈨哺㈣ ㈣ 嘶 呲 咖 0 宙 0_【固 o0Z {彗嘴吣 0_E@8 Z
计算机科学 2017年 日要 bernina a)Movielens (lM, train=0. 60 b)Movielens(IM) 雪 (c)Movielens(IM), train=0. 80 图6NDCG@10,FRR@10在 Movielens(1M数据集上的选代过程数据 从图5、图6可以看出,测试NDCG和ERR在训练过程 现[].计算机工程与设计,2014,35(1):130-143. 的开始快速收敛,经过几次迭代后收敛速度变慢。高学习率6] GOLDBERG D, NICHOLS D, OKI B M, et al. Using collabora- 的训练过程收敛速度快于低学习率的训练过程,但前者得到 tivefilteringtoweaveaninformationtapestry[j].communica 的NDCG和ERR更低。这表明本文提出的模型在低学习率 ns of the acm,1992,35(12):61-70 下具有更好的泛化能力 [7] TANG J, WU S, SUN J M, et al. Cross-domain collaboration 结束语用户的人口统计数据反映了用户的部分基本情 recommendation[C]// Proceedings of the 18th ACM SIGKDD 况,可以作为判断用户偏好的依据,因此本文在传统的基于用 International Conferen Knowledge Discovery and Data Mining. USA, ACM, 2012: 1285-1293 户的协同过滤算法基础上,将人口统计数据与HAP用户聚 类推荐算法相结合,提出推荐效果更优的方法。实验分析表[8] BURKE R. Hybrid recommender systems: Survey and exper ments[J]. User Modeling and User-adapted Interaction, 2002 明,与传统的协同过滤算法相比,本文方法误差更小,有更好 的推荐效果,为协同过滤推荐算法的应用研究提供了参考。[9] JIAO D J. Collaborative filtering algorithm based on user demo- 参考文献 graphics and expert opinions [J]. Computer Engineering &Scien ce,2015,37(1):179-183.( in Chinese) [1] ZHU YY, SUN J Recommender System: Up to Now [].Jour- 焦东俊基于用户人口统计与专家信任的协同过滤算法[].计 nal of Frontiers of Computer Science and Technology, 2015, 9 算机工程与科学,2015,37(1):179-183 (5):513-525.( in Chinese) [10 ZHANG C, CHEN G, WANG H M Recommendation Model Based 朱扬勇孙婧.推荐系统研究进展[.计算机科学与探索,2015, on Blending Recommendation Technology [J]. Computer Engi- 9(5);513525. neerIng,2010,36(22):248-250,253.( in Chinese) [2 SUN T H, LI A N, LI M, et al. Study on distributed improved 张驰,陈刚,王慧敏基于混合推荐技术的推荐模型[J].计算机 clustering collaborative filtering algorithm based on Hadoop[]. L程,2010,36(22):248250,253 Computer Engineering and Applications, 2015, 51(15)1 124-128. [11 HE J Y, MA B. Based on Real-Valued Conditional Restricted Boltzmann Machine and Social Network for Collaborative Filte- 孙天昊,黎安能,李明,等基于Hadp分布式改进聚类协同过 ring]. Chinese Journal of Computers, 2015, 38(1):183-195 滤推荐算法研究[]计算机工程与应用,2015,51(15):124 (in Chinese) 128. 何洁月,马贝,利用社交关系的实值条件受限玻尔兹曼机协同过 [3 LI G J. CHENG X Q Research Status and Scientific Thinking of 滤推荐算法[].计算机学报,2015,38(1):183-195 Big Data[J]. Bulletin of Chinese Academy of Sciences, 2012, 27 [12] WU H C, WANG X J, CHENG Y, et al. Advanced Recommen- (6): 647-657(in Chinese) dation Based on Collaborative Filtering and Partition Clustering 李国杰,程学旗.大数据研究:未来科技及经济社会发展的重大 UJ]. Journal of Computer Research and Development, 2011,48 战略领域一大数据的研究现状与科学思考[].中国科学院院 (Suppl. ):205-212. (in Chinese) 刊,2012,27(6):647657. 吴泓辰,王新军,成勇,等.基于协同过滤与划分聚类的改进推荐 [4] MENG X W, JI W Y, ZHANG Y J. A survey Recommendation 算法[J].计算机研究与发展,2011,48( Suppl.)205212 Systems in Big Data[J] Journal of Beijing University of Posts [13] XU W, DUAN F Combining clustering and collaborative filte- and Telecommunications, 2015, 38(2): 1-15. (in Chinese) ring for implicit recommender system[J]. Computer Engineering 孟祥武,纪威宇,张玉洁大数据环境下的推荐系统[].北京邮 and Design, 2014, 35(12):4181-4185 (in Chinese) 电大学学报,2015,38(2):1-15 许伟段富聚类与协同过滤相结合的隐式推荐系统[].计算机 [5] LI W H, XU S R Design and implementation of recommenda- 工程与设计,2014,35(12):4181-4185. tion system for E-commerce on Hadoop[J]. Computer Enginee- [14] LU Z M, FENG J G, FAN D M,et al. Novel partitional cluste- ring and Design, 2014, 35(1): 130-143. (in Chinese) ring algorithm for large data processing[J]. System Engineering 李文海,许舒人.基于 Hadoop的电子商务推荐系统的设计与实 and Electronics, 2014, 36(5):1010-1015(in Chinese)
68 计 算 机 科 学 2017矩 “71 0 7 063 0血 05g 057 ％ 0 10 ∞ ∞ 40 5o Iteration (a)Movielens(1M)，train=O．60 哥 learning rate=~ 6 △ l舶rⅡ rate=001 白 k时n珥 rate=O．(]5 l口 learning rate=~l m _岫 ntF OD05 △ k∞1liDg rate=~01 口 kIm'蛳 mte=0~6 母 l衄tn rate=O．1 ㈣ Q7t n72 030 0瑚 ％ O 咖 ram=O．O~ △ learmngmte=D．0] 0 l鞲托 rate=(~05 母 km lh堰 rote=0．1 JO 2o 3D 椰 s0 Iteration (b)Movielens(1^D ，train=O．60 0 l0 2o ∞ ．1o 50 0 l0 2D 30 柏 50 Iteration Iteration (c)Movidens(1M)ttrain=O．80 (d)Movielens(1M )。train=O．80 kafn_啦 f^ =0 △ I目lr ngrgte~Dl 哥 h rning rate-~105 廿 lesrning rate~0-1 从 图 5、图 6可 以看 出，测试 NDCG和 ERR在训 练过程 现EJ]．计算机工程与设计。2014，35(1)：130-143． 的开始快速收敛 ，经过几 次迭代后 收敛速度 变慢 。高 学 习率 [6] GOLDBERGD，NICHOLSD，OKIBM，eta1．Usingcollabora一 的训练过程收敛速度快于低学习率的训练过程，但前者得到 tirefilteringtOweaveaninformationtapestry[J]·Communica- 的NDCA~和 ERR更低。这表明本文提出的模型在低学习率 tionsoftheACM，1992，35(12)：61—70· 下具有更好的泛化能力。 [] 1 J，wu s，sL JM，eal·Cmsda玎 nco1laborati0n 结束语 用户的人口统计数据反映了用户的部分基本情 recomme． nda ，tC]∥Proceedin，gso，fhe hAcM ：! 登 ，里查 传统的萋璺 ： ：琶。 嘶 户的协同过滤算法基础上，将人 口统计数据与 HAP用户聚 [8] BLII R d’。 帅 ：s rvy nd 。)【p 一 类推荐算法相结合，提出推荐效果更优的方法。实验分析表 ment[J]Iu Mod。lingndu。 daptIml二。ti。，22， 明，与传统的协同过滤算法相比，本文方法误差更小，有更好 12(4)：331-370 的推荐效果，为协同过滤推荐算法的应用研究提供了参考。 [9] JIAODJ． Coilaborativefilteringalgorithm basedonuserdemo- 参 考 文 献 gmpmcSndxpen。pinion。 puter 咖ng [1] ZHUYY，SUNJ．RecommenderSystem：UptONow口]．Jour- 焦东俊．基于用户人口统计与专家信任的协同过滤算法口]．计 (5)：513—525．(inChinese) [10]ZHANGC，CHENG，WANG H M Recommer~tionModelBased 朱扬勇 ，孙婧．推荐系统研究进展 口]．计算机科学 与探索 ，2015， on~endingRecommendationTechnology[J]．ComputerEngi一 9(5)：513—525． neering，2010，36(22)：248-250，253．(inChinese) [2] SUNT H，LIA N，LIM，eta1．Studyondistributedimproved 张驰 ，陈剐，王慧敏．基于混合推 荐技术 的推 荐模 型[J]．计算 机 孙天吴 ，黎安能 ，李明 ，等．基于 Hadoop分布式改进 聚类协 同过 ring[J]．ChineseJournalofComputers，2015，38(1)：183—195． 128． 何沽月 ，马贝．利用社交关系 的实值条件受限玻尔兹曼机协同过 [3] LIGJ，CHENGXQ ResearchStatusandScientificThinkingof 滤推荐算法 [J]．计算 机学报 ，2015，38(1)：183—195． BigData[J]．BulletinofChineseAcademyofSciences，2012，27 [12]wU H C，WANGX J。CHENG Y，etaLAdvanced Reeommen- (6)：647—657．(inChine~) dationBasedonCollaborativeFilteringan dPartitionClustering 李国杰 ，程学旗．大数据研究 ：未来科 技及经济社 会发展 的重大 I-J]．JournalofComputerResearchandDevelopment，2011，48 战略领 域一 大数据 的研究现状 与 科学 思考 [J]．中国科学 院院 (Supp1．)：205—212．(inChinese) [41 M日NGXW ，jIW Y，ZHANG Y J．A surveyRecommendation 算法[刀．计算机研究与发展 ，2011，48(Supp1．)：205—212． andTelecommunications，2015，38(2)：1-15．(inChinese) ring forimplicitrecommendersystem [J]．ComputerEng ineering 孟祥武，纪威宇，张玉洁．大数据环境下的推荐系统口]．北京邮 andDesign，2014，35(12)：4181—4185．(inChinese) 电大学学报 ，2015，38(2)：1-15． 许伟 ，段 富．聚类与协同过滤相结合 的隐式 推荐 系统[J]．计算机 tionsystemforE-commerceonHadoop[J]．ComputerEnginee- [14] LU ZM ，FENG JG，FAN D M，eta1．Novelpartitionalcluste- 01 备 嘴蛳 晰％啪帆啷咐嘛 0_【雎 ㈣ ％器 0_I曲西uz
第3期 王媛媛,等:基于人口统计学的改进聚类模型协同过滤算法 卢志茂,冯进玫,范冬梅,等.面向大数据处理的划分聚类新方法 International ACM SIGIR Conference on Research 门.系统工程与电子技术,2014,36(5):1010101 ment in Information Retrieval(SIGIR 00). ACM n and Develop [15] WU M H, ZHANG H X, JIN C H, et al. Cluster Algorithm Ba- NY,USA,2000:41-48. ses on edge Density Distance [J]. Computer Science, 2014, 41 [23] CHAPELLE O, METLZER D, ZHANG Y, et aL. Expected re- iprocal rank for graded relevance[C]//Proceedings of the 18th 吴明晖,张红喜,金苍宏,等.一种基于边缘度密度距的聚类算法 ACM Conference on Information and Knowledge Management [].计算机科学,201441(8):245-249 (CIKM,09). ACM, New York, NY, USA, 2009: 621-630. 16] LI G, ZHANG Z B, LIU FX, et al. Nonlinear combinatorial col- [24] HU Y, KOREN Y, VOLINSKY C Collaborative filtering for laborative filtering recommendation algorithm[J]. Jouranal of implicit feedback data sets[C]//Proceedings of the 2008 Eighth Computer Applications, 2011, 31(11): 3063-3067 EEE International Conference on Data Mining(ICDM'08) [17] LIU X N, YIN MJ, LI MT, et al. Hierarchical Affinity Propa- IEEE Computer Society, Washington, DC, USA, 2008: 263-272. gation Clustering for Large-scale Data SetC]. Computer Science, [25] GANTNER Z, DRUMOND L, FREUDENTHALER C Baye- 刘晓楠,尹美娟,李明涛,等.面向大规模数据的分层近邻传播聚 Proceedings of Knowledge Discovery and Data Mining(KDD) 类算法[].计算机科学,2014,41(3):185-188,192. Cup and Workshop, 2011 [18] ALBERT R,JEONG HH, BARABASI A L. Attack and Error [26] WEIMER M, KARATZOGLOU A, SMOLA A Improving maxi- Tolerance of Complex Networks [J]. Nature,2000,406:378- num margin matrix factorization[J. Mach. Learn, 2008, 72(3): [19] WU Y F, WANG H R Collaborative filtering algorithm using [27] RENDLE S, FREUDENTHALER C, GANTNER Z Bayesian user background information[J]. Computer Applications, 2008 personalized ranking from implicit feedback [C]//Proceedings 吴一帆,王浩然.结合用户背景信息的协同过滤推荐算法[].计 (UAI'09). AUAI Press, Arlington, Virginia, United States 算机应用,2008,28(11):2972-2974. [20] SUN G M, WANG S Compute adaptive fast recommendation al- [28] SALAKHUTDINOV R, MNIH A Probabilistic matrix factor gorithm satisfied user interests drift[J]. Application Research of zation[cl//Proceedings of Ad Neural Information Pro Computers, 2013, 30(12): 3618-3621.(in Chinese) cessing Systems (NIPS08) 2008: 1257-1264. 孙光明,王硕基于项目兴趣度的协同过滤新算法[门.计算机应[29] PATEREK A Improving regularized singular value decomp 用研究,2013,30(12)36183621 tion for collaborative filtering [C]// Proceedings of Knowledge [21] KEPHART J, CHESS D. The Vision od Autonomic Computing Discovery and Data Mining(KDD)Cup and Work Shop. 200 UJ]. IEEE Computer Society, 2003, 36(1):41-50. 39-42 [22] JArvelin K, KekAlAinen J. Evaluation methods for retrieving [30] LIU W,WU C, Feng B, et al. Conditional preference in recom ighly relevant documents[Cl//Proceedings of the 23rd Annual mender systems [ J. Expert Syst. Appl. 2015, 42(2):774-785 (上接第37页) [2 HIO C, BERMINGHAM L, CAI G, et al. A Hybrid Grid-based Method for Mining arbitrary Regions-of-Interest from Trajecto- 如,们行盐时民比要 基本开行与优化后算法对问比收 ries[C]/The Workshop on Machine Learning for Sensory Data 基本并行 Analysis. 2013. [3] EHTESHAMI N SM, TABANDEH M, FATEMIZADEH E,A ew ROi extraction method for FKP images using global inter sity[C]//2012 Sixth International Symposium on Telecommuni- cations (IST). IEEE, 2012: 1147-1150. 臣控图像数量/幅 监控图像数量/ [4] SAIFULLAH A, LI J, AGRAWAL K, et al. Multi-core scheduling for generalized parallel task models[J].Re 图3并行算法时间折线图 ystems,2013,49(4):217-226. 而通过图3b可以看出,优化并行算法执行时间比基木[5] LIANG H,LUR,Uow. Performance of the Buffer Queue With Priority For Dynamic Spectrum Access[C]//2010 Interna 并行算法短 tional Conference on Advanced Intelligence and Awarenss Inter- 结束语经过验证,通过对算法进行分解,采取多线程处 net(AIAI2010).2010:109-112 理数据的处理方式,而提取ROI用其余的线程并行运行的方[6] BERGAN T,CEEL,DANG. Input- Covering Schedules for 式。在此基础上对线程进行分组,每8个线程一组,每组共享 Multithreaded Programs [J]. ACM Sigplan Notices, 2013,48 个缓存队列减少共享缓冲队列的线程数和每个缓冲区锁 (10):677-692. 定的次数以达到减少线程等待数据时间的目的。优化后的[7] CHEN G, STENSTROM P Critical lock analysis: diagnosing 算法运行时间相比串行时间能达到大约13.1倍的加速。 critical section bottlenecks in multithreaded applio 参考文献 Proceedings of the 2012 International Conference for High Per- formance Computing, Networking, Storage and Analysis, IEEE [1] FREJLICHOWSKI D, GRZEGORZEWICZ K, An approach to Automatic Detection and Extraction of Regions of Interest in [8] DICE D, MARATHE V J, SHAVIT N Lock cohorting: a gene- Still Images[ M//Image Processing and Communications Chal- ral technique for designing NUMA locks[J]. ACM Sigplan No- enges 4. Spring Berlin Heidelberg, 2013: 3-10 tices,2012,47(8):247-256
第 3期 王媛媛 ，等 ：基于人 口统计学的改进聚类模型协 同过滤算法 69 卢 志茂 ，冯进玫 ，范冬梅 ，等．面 向大数据处理的划分聚类新方法 [J]．系统工程与电子技术 ，2014，36(5)：1010—1015． E15]wU M H，ZHANG Hx，JIN CH，eta1．C1usterAlgorithm BasesonedgeDensityDistance[J]．ComputerScience，2014，41 (8)：245—249．(inChinese) 吴 明晖 ，张红喜 ，金苍宏 ，等．一种基于边缘度密度距的聚类算法 口]．计算机科学 ，2014，41(8)：245—249． [161LIG，ZHANGZB，uu FX，eta1．Nonlinearcombinatorialcol— laborativefilteringrecommendationalgorithm[刀 ．Jouranalof ComputerApplications，2011，31(11)：3063-3067． [17]LIU X N，YIN M J，U M T，eta1．Hierarchical AffinityPropagationClusteringforLarge-scaleDataSetD]．ComputerSdenee， 2014，41(3)：185-188，192．(inChinese) 刘 晓楠 ，尹美娟 ，李 明涛 ，等．面 向大规模数据的分层近邻传播 聚 类算法口]．计算机科学 ，2014，41(3)：185～188，192． [】83 ALBERTR，JEONG H H，BARABASIA L AttackandError ToleranceofComplexNetworks[J]．Nature，2000，406：378— 382． [19] wu Y F，WANG H R Co llaborativefiltering algorithm using userbaekgroundinformation[J]．ComputerApplications，2008， 28(11)：2972—2974．(inChinese) 吴一帆，王浩然．结合用户背景信息的协同过滤推荐算法[J]．计 算机应用 ，2008，28(11)：2972—2974． E20]SUNG M，WANGSCo mputeadaptivefastrecommendational— gorithm satisfieduserinterestsdrift[J]．ApplicationResearchof Computers，2013，30(12)：3618—3621．(inChinese) 孙光明，王硕．基于项 目兴趣度的协同过滤新算法[J]．计算机应 用研究 ，2013，30(12)：3618-3621． [21]KEPHARTJ，CHESSn TheVisionod AutonomicComputing [J]．IEEEComputerSociety，2003，36(1)：41-50． [22] JArvelinK，KekA1AinenJ．Evaluationmethodsforretrieving highlyrelevantdocuments[ }Proceedingsofthe23rdAnnual InternationalACM sIGIR ConferenceonResea rchandDevelop— mentin Information Retrieval(S IR OO)．ACM ，New York， NY，USA，2000：41—48． r23] CHAPELLE O，METI ER D，ZHANG Y，eta1．Expected reciprocalrankforgradedrelevance[ ?fProceedingsofthe18th ACM Co nfe：renceon Information and KnowledgeManagement (CIKM ’09)．ACM ，New York，NY，USA，2009：621-630． [24] Hu Y，KClREN Y，VOIINSKY CCo llaborativefiltering for implicitfeedbackdatasets[C]／／Proceedingsofthe2008Eigh出 IEEEInternationalConference on Data Mining(ICDM ’08)． IEEECo mputerSociety，W ashing ton，DC，UsA，2008：263—272． [25]GANTNER Z，DRUM0ND L，FRⅡ 刀DENTHALER C Bayesianpersonalizedrankingfornon-uniformlysampled items[ 77 Proceeding sofKnowledgeDi scovery and DataMining (KDD) CupandWorkshop．2011． [263wEIMER M，KARA OGu叫 A， 0I_rA A Improvingn】a m1．1lnmarginmatrixfactorization[J]．MackLearn，2008，72(3)： 263—276． [27] RENDLE S， [28] c，GANTNER Z．Bayesian personalizedranking from implicitfeedback[c]∥Proceedings ofthe25thConferenceonUncertainty in Artificia1Intelligence (UAI’09)．AUAIPress，Arlington，Virginia，United States， 2009：452—461． V R，MNIH Probabilisticmatrixfactori zation[q ，，ProceedingsofAdvancesinNeuralInformationPro— cessingSystems(NIPS’08)．2008：1257—1264． [29]PATEREK 八 Improvingregularizedsingularvaluedecomposi— tionforcollaborativefiltering [C]∥ProceedingsofKnowledge DiscoveryandDataMining(KDD)CupandW orkShop．2007： 39—42． E303 LIU W ，wU C，Feng B，eta1．Co nditionalpreferenceinrecom— mendersystems[J]．ExpertSyst．App1．，2015，42(2)：774—788． (上 接 第 37页) (a) (b) 图 3 并行算法时间折线图 而通过图 3(b)可 以看 出，优 化并行算 法执行 时间 比基本 并行算 法短 。 结束语 经过验证，通过对算法进行分解 ，采取多线程处 理数据 的处 理方 式 ，而提取 ROI用其余 的线程并行运 行 的方 式 。在此基础 上对线 程进 行分组 ，每 8个线程一组 ，每组共享 一 个缓存队列，减少共享缓冲队列的线程数和每个缓冲区锁 定 的次数 ，以达到减少线 程等待 数据 时间 的 目的 。优化 后 的 算法运行 时间相 比串行时间能达到大约 13．1倍 的加速 。 参 考 文 献 Eli FREJLICHOWSKID，GRZFf-,ORZEWICZK．AnApproachto Automa ticDetection andExtraction ofRegionsofInterestin StillImages[M]#ImageProcessingandCo mmunicationsCbal— leng es4．Spring Berlin H eidelberg，2013：3-10． [2] H10C，BERMINGHAM L，CAIG，eta1．A HybridGrid-based MethodforMining ArbitraryRegions-of-InterestfromTrajecto— riesEC]／／TheWorkshoponMa chineLearningforSensoryData Analysis．2013． [3] EHTESHAMIN SM，TABAN DEH M，FATEMIz lEH E A new ROIextractionmethod forPKP im agesusingglobalintensity[ 2012SixthInternationalSymposium onTeleeommuni— cations(IST)．IEEE，2012：1147—1150． [4] SAIFULLAH A，LIJ，AGRAⅥrAI，K，eta1．Multi-core real—time schedulingforgeneralized paralleltaskmodels[J]．Real—Time Systems，2013，49(4)：217—226． [5] LIANG H，LIU R，Gu0 W PerformanceoftheBufferQueue withPriorityForDynamicSpectrum Access[C]∥2010Interna— tionalConferenceonAdvan ced IntelligenceandAwarenssInternet(AIAI2010)．2010：109—112． [6] BERGAN T，CEZE L，DAN G．Input-co vering Schedulesfor MultithreadedPrograms[J]．ACM Sigplan Notices，2013，48 (1O)：677—692． [7] CHEN G，STENSTROM P．Criticallockanalysis：Diagnosing criticalsectionbottlenecksinmultithreadedapp1ications[C]∥ Proceedingsofthe2012InternationalCo nferenceforHighPerformanceCo mputing ，Networking，Storag eand 1alysis．IEEE ComputerSociety，2012：1-11． [8] DICE D，MARATHEVJ，SHAVIT N．Lockcohorting：age raltechniquefordesigning NUMAlocks[J]．ACM SigplanNo— tices。2012，47(8)：247—256．
