《计算机科学COMPUTER SCIENCE》：基于人口统计学的改进聚类模型协同过滤算法（王媛媛、李翔）.pdf_大学文库

第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年日要 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．