数据挖掘中的距离度量和相似度度量及Python实现.pdf

距离度量和相仞度度量个体间差异的计算方法汇总参考资料：集体智慧编程P35个性化推荐系统的研究进展，刘建国等基于协同过滤的个性化推荐算法研究，周张兰距离和相似度度量,网站数据分析蜗牛向前冲2013年6月1日星期六才既要*一.首景：目的，应用场景二.距离度量：欧氏(P)、曼哈顿(P)、切比雪夫(P)三.相似度度量：余弦(P)、调整余弦(P)、皮尔逊(P)、Jaccard(P),说明四.比较：结果，适用场景注：P代表Python源码实现，测试字典为prefs=H:l:122,b:l:4252013-06-01 Saturday2背景目的：计算个体间的差异，进而评价个体的相似性、类别。应用场景：数据分析：相关分析；数据挖掘：分类算法和聚类算法，eg.K最近邻(KNN),K均值(K Means)；说明：相似度是样本间相似程度的度量，亦称相似测度、近似系数，如 余弦相似度，夹角越小，相似度越大；相异度，亦称相异测度、相异系数，如距离，距离越大，相异度 越大。2013-06-01 Saturday3二、距离度量：跑离越远.，说明爱异越大,Distance1.欧氏品巨禺：Euclidean Distance 用于衡量各点间的绝对距离n X、Y必须是同一特征的不同值，如同是身高或同时体重 n=l,直线上两点的距离 n=2,二维坐标系中两点的距离 n=3,三维坐标系中两点的距离.2013-06-01 Saturday41.欧氏距离：Python实现#欧氏距耳计算用户相似度#欧氏距离=sqrt(sum(pow(xs-ys,2)#相似度=1/(1+欧氏距离)def sim_distance(prefs/personl/person2):si=for it in prefspersonl:if it in prefsperson2:siit=1if len(si)=0:return 00.1907435698305462pSum=math.sqrt(sum(pow(prefspersonlit-prefsperson2itz2)for it in si)return 1.0/(l+pSum)2013-06-01 Saturday5二,距离度量:距离越远，说明差异越大,Distance2.曼哈顿距 禺：Manhattan Distance将多个维度上的距离求和后的结果11dist(X.Y)=|小一如左图所示，绿线代表欧氏距离,红线代表曼哈顿距离，蓝、黄线 代表等价的曼哈顿距离2013-06-01 Saturday62.曼哈顿距离：Python 实现#曼哈顿距日计算用户相似度 0.14285714285714285#曼哈顿距离=su m|xi-yi|#相似度=1/1+曼哈顿距离def sim_manhattan(prefs,person1,person2):si=for it in prefspersonl:if it in prefsperson2:siit=1if len(si)=0:return 0 pSum=sum(math.fabs(prefspersonlit-prefsperson2it)for it in si)return 1.0/(l+pSum)2013-06-01 Saturday7二、距离度量：距离越远，说明星异越大,Distance3.切比雪夫距曷：Chebyshev Distance相当于从A(xl,yl)到B(x2,y2)最少要走的步数x.V)=inn(I,，|八一亿/-+X/.I/=1 I2013-06-01 Saturday3.切比雪夫距离：Python实现#切比雪夫距离计算用户相似度 0.25#切比雪夫距离二max|xiyi|#相似度=L0/(l+切比雪夫距离)def sim_chebyshev(prefs,person 1,person2):si=for it in prefspersonl:if it in prefsperson2:siit=1if len(si)=0:return 0pSum=max(math.fabs(prefspersonlit-prefsperson2it)for it in si)return 1.0/(l+pSum)2013-06-01 Saturday9相仞度度量：与距离度量相反,Similurily1.余弦相似度:Cosine Similarity相当于计算向量夹角的余弦值，以此作为两个个体间相似度大小的衡量基于用户的CF推荐中用户和用户v余弦相似性计算见式。.1）：sim（u,v）=-Z 色牡（凡J忘凝了基于项目的CF推荐中项目i和项目，之间的余弦相似性计算见式（3.2）：底（氏即x R j）Jz厘（凡（凡）心用户对项目i的评分用户已评分项目集。:用户和用户y共同评分过的项目集/HV=/Hn/y a：对项目，已评分的用户集乙：项目i和项目,共同评分的用户集合Lj=L取：用户的平均评分冗：项目i的平均评分2013-06-01 Saturday1.金弦相仞度：Python实现#余弦系数计算用户相似度#余弦相似度=sum(rxs*rys)/sqrt(rxs2*rys2),其中s为AnB0.9778024140774094def sim_cos(prefs,person 1,person2):si=for it in prefspersonl:if it in prefsperson2:siit=1if len(si)=0:return 0pSum=sum(prefspersonlit*prefsperson2it for it in si)sumlSq=sum(pow(prefspersonlit/2)for it in si)sum2Sq=sum(pow(prefsperson2it/2)for it in si)den=math.sqrt(sumlSq*sum2Sq)if den=0:return 0r=float(pSum)/den return r2013-06-01 Saturday11相仞度重：与距离度量相反,Siniilaritv2.调整余弦相似度：Adjusted Cosine Similarity相当于计算向量夹角的余弦值，以此作为两个个体间相似度大小的衡量，由于余弦 相似度对数值不敏感，如个体X、Y对两个条目的评分分别为（1,2）、（4,5）,其余弦相 似度为0.98,调整后需要减去各自的均值，计算相似度为08.通过求出每位用户的 平均打分，调整评分向量为评分偏差向量，再求解余弦相似度。W：用户”对项口/的评分基于用户的CF推荐中用户和用户V之间调整的余弦相丁的黑案詈的项目集3,L：对项目1已评分的用户集（凡厂取）（4厂取）sim(u)v)=工以（凡,七）T区,iRv)/“：项目i和项目/共同评分的用户集合=4nk二瓦：用户的平均评分2 _凡：项目i的平均评分基于项目的CF推荐中项目i和项目j之间调整的余弦相似性工叫出母）（凡心）Jx.（凡厂瓦）205（及见122.调整金弦相仞度：Python实现#调整余弦系数计算用户相似度#其中s属于AnB,i属于A,j属于B；和皮尔逊的差异在分厂def sim_ajcos(prefs/personl/person2):si=for it in prefspersonl:if it in prefsperson2:siit=1if len(si)=0:return 0avgl=float(sum(prefspersonlit for it in prefspersonl)/len(prefspersonl)avg2=float(sum(prefsperson2it for it in prefsperson2)/len(prefsperson2)pSum=sum(prefspersonlit-avgl)*(prefsperson2it-avg2)for it in si)sumlSq=sum(pow(prefspersonlit-avgl,2)for it in prefspersonl)sum2Sq=sum(pow(prefsperson2it-avg2,2)for it in prefsperson2)den=math.sqrt(sumlSq*sum2Sq)if den=0:return 0r=float(pSum)/den return r2013-06-01 Saturday13相仞度度量：与距离度量相反,Similurily3.皮尔逊相关系数：Pearson Correlation Coefficient即为相关分析中的相关系数r,分别对X和Y基于自身总体标准化后计算两个向量夹 角的余弦值。相当于对数据进行中心化处理，即数据移动了一个样本平均值以使其均值为零。基于用户的CF推荐中用户和用户v之间相关相似性计算不.3 I-X%区厂凡）（凡厂凡）儿：用户对项目i的评分4：用户已评分项目集：用户和用户羽共同评分过的项目集/“=/”n/yA：对项目i已评分的用户集%：项目和项目，共同评分的用户集合y=l n 区鼠区厂2）2 jZ%（K；瓦）2Ru：用户的平均评分 冗：项目i的平均评分sim(u,v)-基于项目的CF推荐中项目i和项目J之间相关相似性计算见式（3.4）；Z（&厂瓦）（&比）也许（凡冗）2和M（凡冗）2143 皮余逊相仞度：Python实现#皮尔逊相关系数计算用户相似度#通用的方法，下面一种只是本方法在某些情况下的特例 1.0def sim_stdpearson(prefs,personl,person2):si=for it in prefspersonl:if it in prefsperson2:siit=1lensi=len(si)if lensi=0:return 0suml=sum(prefspersonlit for it in prefspersonl)sum2=sum(prefsperson2it for it in prefsperson2)avgl=float(suml)/len(prefspersonl)avg2=float(sum2)/len(prefsperson2)sumlSq=sum(pow(prefspersonlit-avgl,2)for it in si)sum2Sq=sum(pow(prefsperson2it-avg2,2)for it in si)pSum=sum(prefspersonlit-avgl)*(prefsperson2it-avg2)for it in si)den=math.sqrt(sumlSq*sum2Sq)if den=0:return 0r=pSum/denreturn r2013-06-01 Saturday153 皮余逊相仞度：Python 实现/#皮尔逊相关系数计算用户相似度#并不是通用的，只有在特定条件下才能用 1.0def sim_pearson(prefs/personl/person2):si=for it in prefspersonl:if it in prefsperson2:siit=1if len(si)=0:return 0suml=sum(prefspersonlit for it in prefspersonl)sum2=sum(prefsperson2it for it in prefsperson2)sumlSq=sum(pow(prefspersonlit/2)for it in si)sum2Sq=sum(pow(prefsperson2it/2)for it in si)pSum=sum(prefspersonlit*prefsperson2itfor it in si)num=pSum-(suml*sum2)/len(si)den=math.sqrt(sumlSq-pow(suml/2)/len(si)*(sum2Sq-pow(sum2/2)/len(si)if den=0:return 0r=num/den return r2013-06-01 Saturday16三、相仞度度量:Similarity与距离度量相反,4.Jaccard相似系数：Jaccard Coefficient主要用于计算符号度量或布尔值度量的个体间的相似度；因为个体的特性主要由 符号度量或布尔值度量标识，因此无法衡量差异的具体值有多大，只能获得个体 间共同具有的特征是否一致的结论，故只比较相同特征的数目。/|/|7/Ji A.)=1 X U2013-06-01 Saturday174 Jaccard相似度：python实现#Jaccard计算用户相似度#Jaccard=|AnB|/|AuB|03333333333333333def simJaccardfprefsersonpersonZ):si_union=#舁集si_inter=#交集si_union=dict(prefspersonl/*prefsperson2)for it in prefspersonl:if it in prefsperson2:si_interit=min(prefsperson1itLprefsperson2it)suml=sum(si_interitfor it in sijnter)sum2=sum(si_unionit for it in si_union)if sum2=0:return 0r=float(suml)/sum2 return r1.0suml=len(sijnter)sum2=len(si_union)2013-06-01 Saturday18相仞度度量:与距离度量相反Similarity5.说明余弦、调整余弦、皮尔逊相似度均适用于：基于 用户相似度的CF和基于产品相似度的CF；区别在于：前者是基于评分矩阵中的行向量相似 度求解，而后者是基于评分矩阵中的列向量相似 度求解。6.数据稀疏问题数据稀疏的一种解决方法：填充基于用户评分：填充对应用户（行）的均值基于产品评分：填充对应产品（列）的均值参考资料：Toward the next generation of recommender systems:A survey of thestate-of-the-art and possible extensionsAdomaviciusG,Tuzhilin A2013-06-01 Saturday19dist(A,B)COS0B两点的距离显然在发生改变，这就是欧氏距离和余度cose是保持不变的，因为夹角不变 弦相似度的不同之处。从底上可以看出距离度量衡量的是空间各点间的绝对晅离,跟各个点所在的位置坐标（即个体特征 维度的数值）直接相关;而余弦相似度衡量的是空回回量的花鱼,更加的是体现在方向上的差异，而不是仓置。如臬彳就寺A点的位置不变,B点朝原方向远离坐标轴原点，那么这个时候余弦相似比较：distance和余弦相似度2013-06-01 Saturday20四、上匕皱.：调整余弦相仞度和皮东逊相仞度基于用户的CF推荐中用户和用户v之间调整的|余弦相似,V）=江姆厂瓦产厂瓦凡）2,曲旦广乩）2基于项目的CF推荐中项目i和项目J之间调整的余弦相似性二.、Ej（凡广无）（及）5加&1）=-j-J 一=F 二二-JEM凡厂兄）柩eA厂凡A基于用户的CF推荐中用户和用户y之间网关相似怖I算见式（3示立加4 冗）（为 一人）SlfriyUy VJ /二一 二：J生产-露）2 JZ国段厂比）基十项目的CF推荐中项目i和项目J之间相关相似性计算见式（3.4）：调整余弦相似度和皮尔逊相似度的区别在于，由左 图知，一般情况下，|调整余 弦相似度|二|皮尔逊相似度|晨叫（4厂口）（凡司）后M（4厂元,区花2013-06-01 Saturday21四、比较：实例用户的平均评分：Rpi=(1+2+4)73=7/3;Rp2=(4+5+2)/3=11/3;Rw=(1+2)/2=1.5,产品的平均评分：Rn=(l+4)/2=2.5;Rn=(2+5+1)/3=8/3:Rjs=(4+2)/2=3;Rj4=2;交集：I“2=?L/2,1功=尸L 尸3 II121314Pl1240P24502P30120调整余弦sim(尸L尸2)=(1-7/3 X4-11/3)+(2-7/3)(5-11/3)1-7/3)2+(2-7/3)2+(4-7/3)3-1/(4-11/3)2+(5-11/3)2+(2-11/3)2=-0.191由金0 zpi P7A(1-7/3 X4-1173)+(2-7/3 X5-11/3)皮小世 sim(PLP2)=-7=_=-f-=-0.471可见理论上，在计算用户的相似度时,阿整余弦目皮尔朝词整余弦 sim(/2 13)=,U/3-TeI-IfS-Is=4力。1/(2-7/3)3+(1-1.5)3 J(4-7/3)2+(2-1.5)2皮尔逊 sim(72 Z3)=己2),-3)+-8 3)(2-3)=0394J(28/3)2+(l8/3)Lj(4-3+(2-32013-06-01 Saturday22四、比较prefs=a:l:l,2:2,七,:142:5结果欧氏距离曼哈顿距离 切比雪夫距离 余弦相似度 调整余弦相似度 皮尔逊相关系数 广义 Jaccard0.19074356983054620,142857142857142850.97780241407740941.01.0033333333333333332013-06-01 Saturday23四、比较/适用场景：!距离度量：体现个体数值间的绝对差异，主要用于需要从维度的数值中体现差异的分析，如使用用户 行为指标分析用户爱好的相似度或差异相似度度量：体现方向的差异，对绝对的数值不敏 感，更多用于使用用户对物品的评分来区分用户爱 好的相似度或差异，同时修正了用户间可能存在的 度量标准不统一的问题2013-06-01 Saturday24Q&A2013-06-01 Saturday25