和上下文敏感SVM的协同过滤推介新方法.doc

李展 等:基于模糊处理和上下文敏感SVM的协同过滤推介新方法基于模糊处理和上下文敏感 SVM的协同过滤推荐新方法* SupportedbyProgramforNewCenturyExcellentTalentsinUniversity under grant NCET-07-0693(教育部新世纪优秀人才支持计划项目); * 作者简介: 李展(1973),男,陕西户县人,博士,讲师,主要研究领域为图像推介,SVM,上下文,局部描述子;李 展1, 马翔2 彭进业31(西北大学 信息学院,西安 710069)2(偏转集团 信息中心,咸阳 712000)3(西北工业大学 电子学院,西安 710072)A New Image Recommendation Algorithm Based on Fuzzy and context-aware SVM*Li Zhan1, MA Xiang2, PENG Jin Ye31(Department of Information, Northwest University, XiAn 710071, China)2(Department of Electronic, Northwestern Polytechnical University, XiAn 710072, China)3(Development Department, 771 Institute, XiAn 710065, China)Abstract:Recommendation system is one of the most important technologies applied in e-commerce. The Similarity measuring method is fundamental to recommendation systems performance. The Traditional methods ignore the context, so it brings poor similarity result. Based on fuzzy and context-aware SVM, a novel similarity measuring method FSVMCF has proposed to solve this problem. By using the images containing car, plane and train, the experimental results show that this method can efficiently improve the recommendation systems performance, and provide better recommendation results than traditional collaborative filtering algorithms.Key words:Image recommendation; Fuzzy; Context-aware; SVM摘 要:协同过滤系统是电子商务最重要的技术之一,用户相似度算法的优劣直接决定推荐性能的准确程度.现有推荐方法忽略用户上下文特征,因而用户相似度判定较差.针对该问题,本文提出了FSVMCF方法.该方法采取模糊上下文数据及上下文敏感 SVM和协同过滤相结合方法,提高了推荐准确度.本文实验以汽车、飞机、火车等交通工具图像作为推荐对象,实验结果验证了该方法对于图像推荐的性能有较大提高.关键词:图像推荐; 模糊处理;上下文敏感 ;支撑向量机1 引 言随着Internet信息爆炸式发展,用户主动方式获取信息变得越来越困难1 .网络信息获取方式经历了信息检索(IR) ,信息过滤(IF)2到信息推荐(RS)3过程.针对Internet用户,推荐系统利用用户评价信息以帮助用户迅速、快捷地获取需要信息3. 图1是IR、IF和RS之间的关系. 图1 IR、IF和RS之间的关系 图2 用户项目矩阵推荐系统(RS)已成为电子商务领域一个重要的研究内容.目前几乎所有的大型电子商务网站,如Amazon, eBay,阿里巴巴,豆瓣等都采用了各种形式的推荐系统.Typestry4是最早提出基于协同过滤的推荐系统,当前目标用户需要明确指出与自己行为比较类似的其他用户.GroupLens5是基于用户评分的自动化协同过滤推荐系统,用于推荐电影和新闻.Ringo推荐系统6和Video推荐系统通过电子邮件的方式分别推荐音乐和电影.Breese7等人对各种协同过滤推荐算法及其改进进行了深入分析. 传统的协同过滤推荐通过用户的最近邻居产生最终的推荐,基于项目的协同过滤推荐首先计算项目之间的相关性,然后通过用户对相关项目的评分预测用户对未评分项目的评分8. Bayesian网络技术利用训练集创建相应的模型9,模型用决策树表示,节点和边表示用户信息.训练得到的模型非常小,所以对模型的应用非常快.这种方法适合于用户的兴趣爱好变化比较慢的场合.聚类技术将具有相似兴趣爱好的用户分配到相同的簇中10,11,聚类产生之后,根据簇中其他用户对商品的评价预测目标用户对该商品的评价.关联规则挖掘可以发现不同商品在销售过程中的相关性.基于关联规则的推荐算法根据生成的关联规则模型和用户当前的购买行为向用户产生推荐12.关联规则模型的生成可以离线进行,因此可以保证有效地推荐系统的实时性要求.Horting图技术是一种基于图的方法13,节点代表用户,边代表两个用户之间的相似度.在图中搜索近邻节点,然后综合近邻节点的评分形成最后的推荐.Horting图技术可以跳过中间节点寻找最近邻居,考虑了节点之间的传递相似关系.目标用户对推荐信息接受与否,很大程度受上下文环境影响,因此忽略上下文信息会降低推荐的质量.本文提出了一种基于模糊处理和上下文敏感 SVM的协同过滤图像推荐方法(FSVMCF)以提高图像推荐系统的性能.为了验证本文提出的方法,我们在LabelMe和Google搜索的图像上进行实验.本文其余章节组织如下：第二部分为传统相似性度量方法介绍及其分析；第三部分给出了上下文概念,同时提出模糊化上下文信息及上下文SVM和协同过滤结合的具体方法.第四部分针对汽车、飞机、火车等图像进行实验,将传统协同过滤法和本方法进行了比较,最后给出了实验结果.第五部分总结了本文的工作.2 传统相似性度量方法介绍及其分析推荐系统通常采用协同过滤算法进行推荐.协同过滤算法根据邻居用户的评价对当前目标用户生成推荐表.在这里存在一个假定8,认为任何人的兴趣都不是孤立的,归属于某个群体所关心的兴趣中.该算法使用统计算法寻找与目标用户有相同爱好的邻居,然后根据目标用户多个邻居的观点向目标客户进行推荐.协同过滤推荐过程可分成三个步骤.1、 计算当前目标用户和推荐系统所有用户的相关性2、 通过评估算法,选择和当前目标用户相似性较高的邻居用户3、 基于选中邻居用户,提交推荐信息给当前目标用户为了寻找当前目标用户的邻居,需度量用户之间的相似性.根据相似性,选择相似程度最高的若干个用户作为当前目标用户的邻居.邻居用户的判断准确与否将直接决定推荐系统的性能.用户相似性判断方法是整个协同推荐成功的关键.用户评分数据可以用一个mn阶矩阵x(m,n)表示,m行代表m个用户,n列代表n个项目,第i行第j列的元素代表用户i对项目j的评分.用户评分数据矩阵如图2所示.2.1 传统相似性度量方法介绍及分析度量用户间相似性的方法有多种,主要包括如下3种方法：平均方差14、相关相似性15和余弦相似性13.l 平均方差（MSD Mean squared difference）:设m是用户a和u都曾经评价过图像的个数,ra,i是当前目标用户a对项目i的评价, ru,i是用户u对项目i的评价.则用户a和用户u之间的相似性sim(a,u)为 (1)如果用户a和u对所有m个项目的评价完全相同,则msd值为0;如果用户a和u对所有m个项目的评价完全相反, 则msd值为1. Ringo音乐推荐系统使用了平均方差作为用户和的相似性判别方法. 14l 相关相似性(correlation): 该方法通过计算两个变量间的线性关系来判断相似性.设ra,i是当前目标用户a对项目i的评价, ru,i是用户u对项目i的评价, 和分别是和和平均评价信息. 则用户a和用户u之间的相似性sim(a,u)为 (2)GroupLens则使用相关相似性作为用户和的相似性判别方法15.l 余弦相似性(cosine): 13用户评分被看做是n维项目空间上的向量,如果用户对项目没有进行评分,则将用户对该项目的评分设为0,用户间的相似性通过向量间的余弦夹角度量.设用户i和用户j在n维项目空间上的评分分别表示为向量和, 则用户a和用户u之间的相似性sim(a,u)为 (3)3 上下文的模糊处理以及SVM和协同过滤结合方法推荐系统中目标用户的需求是和上下文环境密切相关的.上下文环境数据信息,如性别、年龄、所处行业、教育背景、天气温度、天气湿度、天气状况、季节、时间、所处地点都会导致用户对于推荐信息需求的差异.Dey16在文章中将上下文环境看作用户本身信息、用户相关对象信息、地理位置、时间等特性的实体.3.1 上下文模糊处理上下文信息定义为：性别、年龄、所处行业、教育背景、天气温度、天气湿度、天气状况、季节、时间、所处地点信息.上下文的数据信息可以通过传感器、公共平台网站和推荐服务系统本身提供.这些信息的获取方法和数据类型如表1:定义1：令表示上下文数据信息的集合,则 为上下文信息的个数. 令表示一维自然数空间, 表示一维实数空间, 则或. 数据 获取方式数据类型 温度 温度传感器 连续 湿度 湿度传感器 连续 天气情况 公共平台网站 连续 季节 本机系统信息 离散 时间 本机系统信息 连续 所处地点 图像传感器 离散 性别 推荐服务系统 离散 年龄 推荐服务系统 离散 所处行业 推荐服务系统 离散 教育背景 推荐服务系统 离散 表1 上下文信息的获取方式与数据类型定义2: 如果,则是离散数据,令 k为用户个数.定义归一化操作为: (4)针对教育背景,规定 分别对应教育程度为(小学,初中,高中,本科,硕士,博士).针对所处行业,规定 分别对应行业(农业、工业、化工、政府、流通业、信息业).定义3: 如果,则是连续数据, 且.定义模糊化操作为: (5) 图3 F函数图形 通过以上模糊方法就解决了上下文数据连续信息的离散化与归一化问题.离散归一后的数据作为核特征向量就可应用SVM进行分类.3.2 SVM和协同过滤 支撑向量机(SVM)是由Vapnik于1995年提出的统计学习理论,它在小样本学习分类问题上具有优于传统分类方法. SVM很好地解决了神经网络分类存在的网络结构参数选择、以及局部极小点问题.3.2.1 SVM介绍在线性可分情况下,线性SVM分类器的目地就是寻找一个最优分割超平面.图1是SVM线性可分情况. 图4 SVM线性可分 图5 SVM线性不可分图1中 H1和H2分别为过各类样本中离分类线最近的点且平行于分类线的直线.H1和H2之间的距离称为两类分类间隙或分类间隔(margin).寻找最优面的问题也就是要求分类面间的距离要最大化,同时最小化,且满足 . (5)定义如下的拉格朗日函数: (6)如为最优解,则,得最优分类函数为 .在引入核函数后,最优分类函数变为. (7)线性不可分的情况下,可引入容错因子,惩罚因子C, K0, 则以上问题变为: 满足 ，同时最小化 .这样线性不可分问题就转变为线性可分情况.3.2.2 上下文SVM方法论述上下文SVM是常用SVM的扩展17.它将上下文信息加入SVM特征空间组成新的特征空间.设样本图像集和其特征空间为和.定义如下: m为图像样本的个数 k为特征空间的维数.上下文信息所组成的子空间规定为,令新的特征空间. 这样就变成了由和组成的维空间.其关系如图6 图6 上下文特征空间和图像特征空间 图7用户A的上下文SVM 图8用户B的上下文SVM协同过滤推荐寻找当前目标用户的邻居,需度量用户之间的相似性.上下文SVM方法对于用户间相似性可以通过计算分割超平面间的相似性得到.图7是用户A上下文SVM模型. .图8是用户B上下文SVM模型.定义用户A和用户B的正例和反例特征为: A的正例和反例特征为,B的正例和反例特征为,.是上下文信息和样本图像特征构成的空间维数.A的正例、反例个数分别为m1,m2. B的正例、反例个数分别为n1,n2用户A和用户B相似性通过如下步骤进行计算:1、将用户B的训练样本映射到用户A的SVM模型中,定义 (8)2、假定f1和f2分别为用户A和用户B的SVM分类函数.使用f1对和进行分类,规定NAp为映射集中分类结果仍为正例个数, NAn为映射集中分类结果仍为反例个数.3、计算用户A相对于用户B的相似度SimAtoB. (n1+ n2 是B的样本个数和) (9)3、与此类似计算用户B相对于用户A的相似度. (10)MAp为用户A的正例训练样本映射到用户B的SVM模型中仍为正例的个数, MAn为用户A的反例训练样本映射到用户B的SVM模型中仍为反例的个数.4、用户A和B的相似性和用户A相对于用户B的相似度及用户B相对于用户A的相似度成线性关系,令 (11)其中：.3.2.3 上下文SVM和协同过滤结合方法将上下文SVM计算的用户相似结果与协同过滤度量用户相似性的方法结合,可以很好的解决上下文信息对推荐性能的影响.协同过滤中度量用户间相似性的传统方法主要有3种方法:平均平方差、相关相似性和余弦相似性. 这里协同过滤度量用户相似性方法选择相关相似性(correlation)计算,实践表明GroupLens选用该计算公式取得了一定的成效定义为FSVMCF过滤下下用户A和用户B的相似性.则 (12)为上下文SVM计算用户A和用户B相似性结果. 为相关相似性(correlation). 为的比例系数.的计算公式为: (13)为用户A和用户B上下文维数之和, 为用户A获取到上下文信息个数和用户B获取到上下文信息个数之和.显然有 .无上下文信息时, FSVMCF过滤就变成了传统的CF协同方法.4 实验结果及其分析 本文使用LabelMe(/)和Google搜索的图像作为测试数据集.图像集共2300张,LableMe图像1300张,Google搜索图像1000张.图像中汽车图像600张、飞机图像900张、火车图像800张.学习用例汽车图像400张,飞机图像500张, 火车图像600张.25个用户分别对100张图片进行评价.本文使用图像的HSI颜色直方图、一二三阶颜色矩、Gabor小波和SIFT特征作为图像的特征. SVM使用Libsvm.下图9为图像特征和部分程序界面. HIS颜色直方图 一二三阶颜色矩 Gabor小波 SIFT特征 程序界面图9 图像特征和部分程序界面推荐质量的评价标准主要有两类:统计精度度量方法和决策支持精度度量方法18,19.统计精度度量方法中的平均绝对偏差MAE(mean absolute error),是一种常用度量方法. 平均绝对偏差(MAE)通过计算预测的用户评分与实际的用户评分之间的偏差度量预测的准确性,MAE越小,推荐质量越高.假设预测的用户评分集合为p1,p2,pN,对应的实际评分集合为q1,q2,qN,则MAE可由下式计算: 把本文的算法与传统的基于平均方差法、相关相似性法和余弦法的协同过滤推荐算法进行比较.使用MAE为度量标准,得到如图10所示的MAE随最近邻居数变化而变动的折线图.可见,本文提出的算法有较好的性能表现. 图10 MAE随最近邻居数变化图5 结束语本文首先深入分析了协同过滤相似性判别法, 平均方差、相关相似性和余弦相似性度量方法在计算目标用户的最近邻居时存在未考虑上下文信息问题.针对上述问题,提出了一种FSVMCF过滤推荐算法,这种方法可以有效地解决上述度量方法存在的不足,使得计算得到的目标用户的最近邻居比较准确.实验结果表明,基于模糊处理和上下文敏感 SVM的协同过滤算法可以有效地解决用户推荐需求和上下文相关时 ,传统的相似性度量方法存在的弊端,显著地提高推荐系统的推荐质量.References:1 P. Resnick, N. Iacovou, M. Suchak, P. Bergstorm, and J. Riedl. GroupLens: An Open Architecture for Collaborative Filtering of Netnews. Proceedings of ACM Conference on Computer Supported Cooperative Work, 1994. 122 Paul Resnick and Hal R. Varian. Recommender systems, volume 40. ACM Press, 1997. 183 P. Melville, R. Mooney, and R. Nagarajan. Content-boosted collaborative Filtering, volume 40. In Proceedings of the 2001,124 Goldberg D, Nichols D, Oki BM, Terry D. Using collaborative filtering to weave an information tapestry. Communications of the ACM, 1992,35(12):6170. 5 Resnick P, Iacovou N, Suchak M, Bergstrom P, Riedl J. Grouplens: An open architecture for collaborative filtering of netnews. In: Proceedings of the ACM CSCW94 Conference on Computer-Supported Cooperative Work. 1994. 175186. 6 Shardanand U, Maes P. Social information filtering: Algorithms for automating “Word of Mouth”. In: Proceedings of the ACM CHI95 Conference on Human Factors in Computing Systems. 1995. 210217. 7 Hill W, Stead L, Rosenstein M, Furnas G. Recommending and evaluating choices in a virtual community of use. In: Proceedings of the CHI95. 1995. 194201 8 Sarwar B, Karypis G, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms. In: Proceedings of the 10th International World Wide Web Conference. 2001. 285295. 9 Chickering D, Hecherman D. Efficient approximations for the marginal likelihood of Bayesian networks with hidden variables. Machine Learning, 1997,29(2/3):181212. 10 Dempster A, Laird N, Rubin D. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 1977,B39:138. 11 Thiesson B, Meek C, Chickering D, Heckerman D. Learning mixture of DAG models. Technical Report, MSR-TR-97-30, Redmond: Microsoft Research, 1997. 12 Sarwar B, Karypis G, Konstan J, Riedl J. Analysis of recommendation algorithms for E-commerce. In: ACM Conference on Electronic Commerce. 2000. 158167. 13 Wolf J, Aggarwal C, Wu K-L, Yu P. Horting hatches an egg: A new graph-theoretic approach to collaborative filtering. In: P