个性化推荐算法中的相似性指标

个性化推荐算法中的相似性指标在互联网产品的以协同过滤为基础的⼀一系列个性化推荐算法中，相似性指标的计算无疑是非常重要的⼀一环。甚至可以说，定义和挑选相似性指标的好坏，在很大程度上决定了个性化推荐算法昀终的推荐质量，以及用户体验。并且，相似性本身也可以直接作为产品功能服务于用户，比如条目相似性可以作为“喜欢XX物品的也喜欢”、“读了XX文章的也读了”、“购买XX产品的也购买了”栏目出现，而用户相似性可以用来直接推荐口味相似的用户。这就使得我们在搭建个性化推荐系统中，需要对所选择的相似性指标有充分的了解。本文试图从相似性指标的起源谈起，在详细讨论几类常用的相似性指标各自特点的基础上，为如何在推荐系统中选取合适的相似性指标提供⼀一定的指导原则和基础。相似性指标的源流学术界对相似性指标的实用性研究可以追溯到⼀一个多世纪之前。1901年，瑞士苏黎世的植物学家PaulJaccard在⼀一篇论文中提出了⼀一种衡量不同采样集合之间相似性指标的方法，用两个集合的交集的数目比上并集的数目，被称为Jaccard指标或Jaccard相似系数(JaccardSimilarityCoefficient)：J(A,B)=ABAB(1)作为昀早提出的衡量二值数据(binarydata)相似性的指标之⼀一，Jaccard指标在生物学、社会学、心理学等领域有非常广泛的应用。并且，由于计算简单，意义明确，进入信息时代后，在信息抽取、模式识别和很多互联网产品中也大量使用这⼀一指标。比如对于个性化推荐领域比较经典的top-k推荐问题，往往可以把用户的评分数据二值化为0-1数据，然后用Jaccard指标来计算相似性进行推荐。对于点击阅读推荐、文章推荐、购买推荐等天然就是二值化的数据，应用Jaccard指标就更加方便了。对于非二值化的数据，特别是稠密的数据，早期人们倾向于使用统计学中的相关系数来描述两个数据集合之间的相似性。应用昀广泛的是英国统计学家KarlPearson在1880年代发展了其导师FrancisGalton的思想而建立起来的Pearson相关系数(PearsonCorrelationCoefficient)：rxy=(xi−x)(yi−y)i=1n∑(xi−x)2i=1n∑(yi−y)2i=1n∑（2）对于任意两列等长的实数向量，Pearson相关系数的定义是两个向量的协方差与其各自标准差之积的商，值在-1到+1之间，绝对值接近0表示两列向量不相关（未必是独立），绝对值接近1表示两列向量强相关（正或负），从相似性的意义上说，就是两个数据源很相似。随着统计学的蓬勃发展，Pearson相关系数作为各种统计推断模型的基础指标也被应用到各个学科领域。在个性化推荐算法中，也有不少直接利用Pearson相关系数作为相似性指标来做推荐的例子，主要是针对较为稠密的、规模并不是很大的数据集。人们很早就注意到相似性指标和距离度量之间的关系，距离度量表示两个数据集或向量之间的远近，那么很自然的，用极值减去距离度量，或者使用距离度量的倒数，就可以来表示相似性，比如公式(3)是用N维空间的欧式距离来定义相似性。早期研究中，人们对这个方向寄予了很大希望，因为距离度量有很扎实的数学定义和特性1，利用距离度量作为相似性有助于在理论研究中得到好的结果。但在信息抽取和文本挖掘的实际应用中，人们发现，由于在高维空间中维数灾(CurseofDimension)的影响，用距离度量作为相似性指标的算法往往表现很差，特别是对于高度稀疏的数据，与人们的直观感觉有很大差异。很快，人们在这⼀一领域找到了更好的替代性指标，即余弦相似性指标(CosineSimilarityCoefficient)。Sd(A,B)=Smax−d(A,B)=Smax−(Ai−Bi)2i=1n∑(3)余弦相似性指标昀早在1990年代被应用于文本信息抽取与挖掘，用来衡量两篇文档之间的相似性。把两列数据看做N维空间中的两个向量，向量的内积除以它们的模的积，就得到了两个向量之间的夹角余弦：cos(θ)=A⋅BAB=AiBii=1n∑Ai2i=1n∑Bi2i=1n∑(4)余弦相似性指标的取值是0到1之间，0表示两个向量之间的夹角是90度，也就是在高维空间中正交，互相之间的投影为零，可以说毫无相似性可言；而1表示两个向量夹角为零，虽然模的大小可能会不同，但方向重合、变化趋势⼀一致，可以认为完全相似。如果两个向量的模做了归⼀一化，那么其夹角余弦的大小也可以看做两个向量之间互相投影的大小，也就是其中的⼀一个向量“包含”了多少程度的另⼀一个向量，这也是我们对相似性指标的昀直观意义的理解。早期的个性化推荐系统尝试过很多二值化相似性指标和统计学中的相关性指标，随着亚马逊在2000年发表了基于条目的协同过滤算法2，人们逐渐都开始采用了这篇论文中使用的余弦相似性来作为标准的相似性指标。在大规模个性化推荐系统中，余弦相似性有几个明显的优势：首先，余弦相似性兼具二值化相似性指标和数值型相似性指标的优点，⼀一方面物理意义清楚，能够处理数值型数据，另⼀一方面计算简便，也适合二值化的数据。其次，余弦相似性能够更好的适应数据稀疏的情况。在均值为0的情况下，如果数据是稠密的，通过简单的推导可以得出，Pearson相关系数和余弦相似性是⼀一致的。但实际数据往往是稀疏的，均值也往往不为0，这样⼀一来，余弦相似性的直观含义和计算方法都很简便清楚。此外，笔者在本系列的前⼀一篇文章3中也讨论过相似性指标的计算复杂性问题，余弦相似性在这方面也表现不错。1比如距离度量要满足三角不等式23王守崑，两种基本的协同过滤算法，《程序员》，2013.01随着自然语言处理和个性化推荐系统的发展，相似性指标的应用越来越广泛，不少研究者也在尝试对相似性指标的定义和特性做理论上的探讨，很多业界的实践者也在各自的工作中对不同的相似性指标在不同场合下的表现做出归纳和整理。从应用的场景来看，我们大致可以分为二值化的相似性指标和⼀一般相似性指标，当然⼀一般性的相似性指标也可以应用在二值化的场景下。从指标的来源说，我们可以分为集合论、距离空间、信息论/概率模型、图模型等几个方面。不同的来源和定义，可以应用在不同的场景。二值化的相似性指标首先我们来讨论二值化的相似性指标，这些指标⼀一般都比较简单直观，应用也很广泛。二值化的相似性指标种类很多，有些文献4详细讨论了近百种不同的相似性指标的定义。要了解这些相似性指标，关键是要了解二值化向量的OTU定义(OperationalTaxonomicUnits），见表1。表1二值化向量的OTU定义i/j10和1a=i•jb=i•ja+b0c=i•jd=i•jc+d和a+cb+dn=a+b+c+d假设i和j是二值化的向量，即向量的元素是0和1。n是向量的维度，那么由表1可知，a表示向量i和向量j均为1的部分，称作正匹配(positivematches)，可以认为是两个向量的交集；b表示向量i为0同时向量j为1的部分，c则相反，表示向量i为1但向量j为0的部分；d则是向量i和向量j均为0的部分，称作负匹配(negativematches)。对角线之和a+d，表示向量i和向量j所有匹配的部分，包括正匹配和负匹配；反向对角线之和b+c，则表示向量i和向量j所有不匹配的部分。而两者之和则是向量的维度n。有了OTU定义，我们可以很轻松的理解或自己定义各种二值化的相似性指标。比如前文讨论的jaccard相似性指标，用OTU来定义就是：SJaccard=aa+b+c(5)即正匹配部分除以向量维度减去负匹配部分，通过这样的定义可以从另⼀一个侧面了解指标的不同含义。事实上，Jaccard指标代表了二值化相似性指标的⼀一个流派，即在指标定义中不使用负匹配项。与之相对应，二值化相似性指标的另⼀一个流派就是在定义中包含负匹配的项，比较著名的是Sokal和Michener在1963年提出的相似性指标：SSokal&Michener=a+da+b+c+d(6)4Seung-SeokChoi,et.lASurveyofBinarySimilarityandDistanceMeasure这个指标的定义也很直观，是两个向量中所有匹配的项（包括正匹配和负匹配）除以向量的维度n，在⼀一些社会学和生物学的研究中，经常使用这样的相似性指标。之所以对“负匹配”的不同处理会成为区分不同相似性指标定义的关键，是因为不同的研究者对“负匹配”在相似性指标中所起的作用有截然不同的看法。主张包含“负匹配”的研究者认为，选择权在用户手中，选或不选某个维度，代表了用户的态度和偏向，因此，“负匹配”对昀终用户的相似性有正的贡献。而另⼀一派研究者认为，当用户面临选择很多的时候，不可能面面俱到，“负匹配”并不意味着什么，仅仅可能是用户没有机会见到这些选择，如果见到了，两个人的选择可能截然不同。并且，如果数据非常稀疏，过多的“负匹配”甚至会淹没宝贵的“正匹配”数据，使昀终结果被稀释。还有⼀一些研究者根据自己领域的实际状况，在两种流派之间做折衷调和，比如对正匹配和负匹配乘以不同的系数，或者通过开方取对数等手段对OTU进行调整，也都在具体的时间中收到了不错的效果。两种流派都有各自的道理，我们在实际工作中需要按照具体的场景做出合理的判断。⼀一般性的相似性指标我们前边介绍的Pearson相关系数和余弦相似性就是⼀一般性的相似性指标，只要领域问题能够转化为数值向量的形式，都可以用它来解决。下面我们分别从信息论和图模型的角度来介绍两种更加具有普适性的相似性指标。考虑到很多对相似性指标感兴趣的研究者具有信息抽取、模式识别或自然语言处理的研究背景，从信息论的角度来审视和定义相似性指标，是很自然的事情。1990年代就有学者用熵和互信息来定义文档之间的两两相似性指标。DekangLin教授发表的⼀一篇论文5在此基础上给出了系统化的基于信息论的相似性指标定义。论文中用了接近公理化的方法，从⼀一系列与公理相当的直觉(Intuition)出发，引出若干形式化的假设，在这些假设的基础之上利用信息论证明了作者提出的相似性定理，定理给出了相似性指标的定义。论文提出的三条相似性应满足的直觉是：直觉⼀一：A与B的相似性与它们之间的共性(Commonality)有关，共性越多，越相似。直觉二：A与B的相似性与它们之间的差异(Difference)有关，差异越多，越不相似。直觉三：无论A与B有多少共性，当它们完全相等时，达到昀大相似性。这三条相似性应满足的直觉具有很高的普适性，它甚至不是数值化的，在这个原则之下，我们可以比较任意两个物体之间的相似性，而不仅仅局限在数据的集合或是高维空间中的向量。当然，为了更严格的进行定义和比较，我们需要借助数值化的手段来让这些直觉建立在更加坚实的基础之上。紧接着，这篇论文利用信息论的方法，提出了六条假设，包括用信息来定义物体之间的共性和差异，以及相似性函数应满足的若干性质。然后，论文利用这些假设证明了核心的相似性定理：相似性定理：A与B之间的相似性等于A与B的共性所包含信息与完整描述A与B所需信息之比。sim(A,B)=logP(common(A,B))logP(description(A,B))(7)5DekangLin,AnInformation-TheoreticDefinitionofSimilarity这⼀一定理虽然表述比较抽象，但实际应用起来还是很方便的。比如对于高维空间的向量A和B，其共性就是它们共同拥有的非零维度所包含的信息，而所谓完整描述这两个向量就是其非零维度所包含的信息。从这里我们也可以看出，这⼀一相似性指标在描述两个物体相似性时，有效利用了全局的信息。如果两个向量共同拥有的非零维度都是比较冷门的，那么描述它们共性所需的信息量就高，从而相似性就可能比较高；反之，如果两个向量自身比较冷门，但它们共同拥有的非零维度没那么冷门，那么共性的信息较低，描述他们自身所需的相似性较高，其整体相似性就会比较低。在实际应用中，这⼀一相似性指标具有很高的普适性，还表现在除了能对高维向量进行处理，还能计算表示次序的数据(OrdinalD