今天整理的是基础性应用算法，计算了相似度。 该算法在nlp、推荐系统领域很常见，但在其他地方如何使用取决于仁者~
相似度算法的算法名称简单描述LCS最长公共子序列Hamming Distance汉明距离
成本模拟
余弦相似度算法Euclidean Distance欧式距离http://www.Sina.com/http://www.Sina.com/http://www.Sina.com/http://www.Sina.com
kdl远离JAC卡模拟
什么是Jaccard系数1、LCS-“最长公共子串”(longest common sequence )和“最长公共子串”(longest common substring )子串？ 即，给定序列的子序列是去除给定序列中的零个或多个元素的结果。 图如下。
什么是子字符串？ 一个字符串中由连续字符组成的子串称为该字符串的子串。 用图来说明一下：
如上图所示，给定的字符串是{a、b、c、d、e、f、g、h}，其子串的例子是{a、c、e、f}即要素b、d、g、h被去除后，保持了原要素串同样，{a，h}、{c，d，e}等是其子串。
其字符串的例子： {c、d、e、f}即由连续要素c、d、e、f构成的字符串是给定系列的字符串。 同样，{a、b、c、d}、{g、h}等是其字符串。
一旦了解了这个问题，就很清楚最长公共子串(以下简称LCS )。
给定的序列s1={1、3、4、5、6、7、7、8}、s2={3、5、7、4、8、6、7、8、2}、s1和s2的同一部分序列，该部分序列的长度最长的是LCS
s1和s2的最长公共子串之一是{3、4、6、7、8}
2、欧式距离(Euclidean Distance )欧式距离全称是欧式距离，是最容易理解的距离计算方式，来源于欧式空间中两点之间的距离公式。
3. Python代码的简单实现：
defeuclideandistance(x，y ) :d=0for a，b in zip(x ) x，y ) :d=(a-b ) * * 2返回d * * 0.54) numpy简化：
importnumpyasnpdefeuclideandistance (dataa，dataB ) : # np.linalg.norm用于范数计算，默认值为二范数。 平方和开根号return 1.0/(1.0 NP.Lina LG.norm (dataa-datab ) )Pearson Correlation Coefficient首先，样本数据的夹角余弦不是真正几何意义上的夹角余弦
几何意义上的余弦
夹角越小，余弦值越接近1，相反为-1。 假设有两个向量： x1和x2 :
Python代码的简单表达式恢复： defcosine(x，y ) : sum_xy=0.0； normX=0.0； normY=0.0； for a，binzip(x，y ) : sum _ xy=a* bno rmx=a* *2normy=b * *2ifno rmx==0.03360 returnonelse 3330
defcosine(dataB，dataB ) : sumData=dataA *dataB.T # )向量表示dataa.t * datab denom=NP.Lina LG.norm (dataa )
dataa=NP.mat (1，2，3，3，2，1 )；datab=NP.mat (2，3，4，3，2 ) ) print ) Euclideandistance (欧洲安全)
比较以上结果的da
taA 与 dataB 这两组数据，会发现 dataA 与 dataB 的欧式距离相似度比较小，而夹角余弦相似度比较大，即夹角余弦更能反映两者之间的变动趋势，两者有很高的变化趋势相似度，而欧式距离较大是因为两者数值有很大的区别，即两者拥有很高的数值差异。 4、皮尔逊相关系数（Pearson Correlation Coefficient）如何理解皮尔逊相关系数（Pearson Correlation Coefficient）？www.zhihu.com
假如之不先介绍夹角余弦的话，第一次接触你绝对会对皮尔逊相关系数一脸懵逼。那么现在，让我们再来理解一下皮尔逊相关系数的公式：
皮尔逊相关系数公式实际上就是在计算夹角余弦之前将两个向量减去各个样本的平均值，达到中心化的目的。从知友的回答可以明白，皮尔逊相关函数是余弦相似度在维度缺失上面的一种改进方法。
1.Python 代码实现皮尔逊相关系数：
def Pearson(x,y): sum_XY = 0.0 sum_X = 0.0 sum_Y = 0.0 normX = 0.0 normY = 0.0 count = 0 for a,b in zip(x,y): count += 1 sum_XY += a * b sum_X += a sum_Y += b normX += a**2 normY += b**2 if count == 0: return 0 # denominator part denominator = (normX - sum_X**2 / count)**0.5 * (normY - sum_Y**2 / count)**0.5 if denominator == 0: return 0 return (sum_XY - (sum_X * sum_Y) / count) / denominator2. numpy 简化实现皮尔逊相关系数
def Pearson(dataA,dataB): # 皮尔逊相关系数的取值范围(-1 ~ 1),0.5 + 0.5 * result 归一化(0 ~ 1) return 0.5 + 0.5 * np.corrcoef(dataA,dataB,rowvar = 0)[0][1]用余弦相似度相同的方法实现皮尔逊：
# 余弦相似度、修正余弦相似度、皮尔逊相关系数的关系# Pearson 减去的是每个item i 的被打分的均值def Pearson(dataA,dataB): avgA = np.mean(dataA) avgB = np.mean(dataB) sumData = (dataA - avgA) * (dataB - avgB).T # 若列为向量则为 dataA.T * dataB denom = np.linalg.norm(dataA - avgA) * np.linalg.norm(dataB - avgB) # 归一化 return 0.5 + 0.5 * (sumData / denom) 5、修正余弦相似度1. 为什么需要在余弦相似度的基础上使用修正余弦相似度
X和Y两个用户对两个内容的评分分别为（1,2）和（4,5），使用余弦相似度得到的结果是0.98，两者极为相似。但从评分上看X似乎不喜欢2这个 内容，而Y则比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性 # 修正余弦相似度# 修正cosine 减去的是对item i打过分的每个user u，其打分的均值data = np.mat([[1,2,3],[3,4,5]])avg = np.mean(data[:,0]) # 下标0表示正在打分的用户def AdjustedCosine(dataA,dataB,avg): sumData = (dataA - avg) * (dataB - avg).T # 若列为向量则为 dataA.T * dataB denom = np.linalg.norm(dataA - avg) * np.linalg.norm(dataB - avg) return 0.5 + 0.5 * (sumData / denom)print(AdjustedCosine(data[0,:],data[1,:],avg)) 6、汉明距离（Hamming distance）汉明距离表示的是两个字符串（相同长度）对应位不同的数量。比如有两个等长的字符串 str1 = "11111" 和 str2 = "10001" 那么它们之间的汉明距离就是3（这样说就简单多了吧。哈哈）。汉明距离多用于图像像素的匹配（同图搜索）。
1.Python 的矩阵汉明距离简单运用：
def hammingDistance(dataA,dataB): distanceArr = dataA - dataB return np.sum(distanceArr == 0)# 若列为向量则为 shape[0] 7.曼哈顿距离（Manhattan Distance）没错，你也是会曼哈顿计量法的人了，现在开始你和cqdjz只差一张刘昊然的脸了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，那么驾驶的最近距离并不是直线距离，因为你不可能横穿房屋。所以，曼哈顿距离表示的就是你的实际驾驶距离，即两个点在标准坐标系上的绝对轴距总和。
曼哈顿距离
# 曼哈顿距离(Manhattan Distance)def Manhattan(dataA,dataB): return np.sum(np.abs(dataA - dataB))print(Manhattan(dataA,dataB)) 8、Jaccard系数 定义Jaccard系数值越大，样本相似度越高。
给定两个集合A,B，Jaccard 系数定义为A与B交集的大小与A与B并集的大小的比值，定义如下：
当集合A，B都为空时，J(A,B)定义为1。
与Jaccard 系数相关的指标叫做Jaccard 距离，用于描述集合之间的不相似度。Jaccard 距离越大，样本相似度越低。公式定义如下：
其中对参差（symmetric difference）
值域
python实现1、当两个集合元素个数相同，则直接调包
from numpy import *import scipy.spatial.distance as dist # 导入scipy距离公式matV = mat([[1,1,0,1,0,1,0,0,1],[0,1,1,0,0,0,1,1,1]])print ("dist.jaccard:", dist.pdist(matV,'jaccard'))2、当集合元素个数不同
def correlation(set_a,set_b):unions = len(set_a.union(set_b))intersections = len(set_a.intersection(set_b))return 1. * intersections / unions 实例主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。
1、如果比较X与Y的Jaccard相似系数，只比较xn和yn中相同的个数，公式如下：
如集合A={1,2,3,4};B={3,4,5,6};
那么他们的J(X,Y)=1{3,4}/1{1,2,3,4,5,6}=1/3;
2、样本A与样本B是两个n维向量，而且所有维度的取值都是0或1。例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。
概念浅析：假设A是坚果Pro2 , B是 苹果8x。 为了比较两个手机，给出了n个评价指标，即n维特征，也就是n维向量：1-是国产、2-有刘海、3-价格高于5000。那么对于A=（100），B=（011）。所以，n维向量指样本的N维特征，组成一个集合。而集合是由元素组成的，在对应的特征位置，如果样本有该特征，这个位置集合值取1，表示包含该元素；否则，取0，表示不包含该元素。可见，元素=特征。
P：样本A与B都是1的维度的个数
q：样本A是1，样本B是0的维度的个数
r：样本A是0，样本B是1的维度的个数
s：样本A与B都是0的维度的个数
那么样本A与B的杰卡德相似系数可以表示为：
这里p+q+r可理解为A与B的并集的元素个数，而p是A与B的交集的元素个数。
而样本A与B的杰卡德系数表示为：
以下题目和数据均来自于千里码，一个优质的程序员答题网站，由于站长食年常年失踪，于是我就无耻的分享出来啦。
现在从豆瓣的用户中抽取了500左右个比较活跃的用户，这些用户都是忠实的电影迷，大部分人涉猎了上百部电影。这里有个80多万行的 文本文件，文件的每行是三个数字，分别是 userid，movieid，rating。代表一个用户对一部电影的评分。rating代表评分的星级，如上图中的红框所示，星级从低到高依次是1-5。
接下来有个行数为10001的 文本文件（第一行为title），文件的每行为2个数字，分别代表userid和movieid，请你预测如果该用户观看了这部电影，会给该电影打多少分，你的预测值为1个大小为1-5的整数。
本题的答案是一个长度为1万的字符串，字符串的第k位代表你对第k行的预测结果。
如果你的预测结果和实际答案的差值的绝对值的和小于6000，通过该题。
简单来说就是：
train.txt（80w 12M） --- userid, movieid, ratetest.txt（1w 360KB） --- userid, movieid你要为 test.txt 中的用户预测当前电影的打分，你可以在以下地址提交你的答案。
协同过滤www.qlcoder.com
参考【1】汉明距离，汉明距离实现
【2】LCS
【3】常见相似度原理
【4】推荐算法入门（1）相似度计算方法大全
【5】Implementing the five most popular Similarity Measures in Python
【6】相似度方法总结
【7】Jaccard相似度