对相似性算法的了解起源于最近在做使用协同过滤原理的推荐系统中，基于邻域的推荐算法（User-Based CF和 和 Item-Based CF）需要估算不同样本之间的相似性度量(Similarity Measurement)，这也是机器学习中在做分类的时候的一个常见场景。
而相似度通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究，甚至关系到分类的正确与否。
本文的目的在于对当下常见的相似度度量方法的原理，实现，优缺点，改进版本，适用场景等几个方面做一个总结
一、欧氏距离(EuclideanDistance)
欧氏距离是欧几里得距离的简称，是最易于理解的一种距离计算方法，其实就是空间中两点间的距离公式。
-
二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离（拓展到n维同理）
-
两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离
-
向量运算的形式：
-
就其意义而言，欧氏距离越小，两个用户相似度就越大，欧氏距离越大，两个用户相似度就越小。而在日常使用中，一般习惯于将相似度与1类比，对越相似的人给出越大的值，相似度在数值上反映为0<=sim_distance(x,y)<=1，越接近1，相似度越高。所以我们需要进行归一化处理，可以通过将其函数值加1(避免除以0)，并取其倒数的方法来构造欧几里得相似度函数：
用 python实现计算欧几里得距离，并构造相似度函数：
# @Author : XZP
# @Email : pcxzp@live.com
# @File : EuclideanDistanceSimilarity.py
from math import sqrt
# 找到二者相同评分项
def get_same_Item(prefs, person1, person2):
si = {}
for item in prefs[person1]:
if item in prefs[person2]:
si[item] = 1
return si
# 欧几里得相似度算法
def sim_euclid(prefs, p1, p2):
si = get_same_Item(prefs, p1, p2)
if len(si) == 0:
return 0
sum_of_squares = sum([pow(prefs[p1][item] - prefs[p2][item], 2) for item in si])
return 1 / (1 + sqrt(sum_of_squares))
if __name__ == '__main__':
critics = {'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5,
'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5,
'The Night Listener': 3.0},
'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5,
'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0,
'You, Me and Dupree': 3.5}}
print(sim_euclid(critics, 'Lisa Rose', 'Gene Seymour')) # 0.29429805508554946
- 缺点：当数据集出现异常值（即数据不是很规范）的时候，欧几里德距离表现不"稳定"，另除了异常值外，当这种情况：例如A、B明明都喜欢这个电影，品味相似，但是B对电影的评分向来比较苛刻（评分都不太高），所以导致这时候用欧氏距离得出二者不相似的结论，这显然不是我们所期望的结果。
二、标准化欧氏距离
三、曼哈顿距离
四、切比雪夫距离
五、 夹角余弦距离
如果高中正常毕业, 参加过高考, 那么肯定会这么一个公式
cos<a, b> = a • b / |a|•|b|
假设
a = (3, 1, 0),
b = (2, -1, 2)
分子是a,b两个向量的内积, (3, 1, 0) • (2, -1, 2) = 3•2 + 1•(-1) + 0•2 = 5
分母是两个向量模(模指的是向量的长度)的乘积.
总之这个cos的计算不要太简单
余弦距离(余弦相似度), 计算的是两个向量在空间中的夹角大小, 值域为[-1, 1]:
1代表夹角为0°, 完全重叠/完全相似;
-1代表夹角为180°, 完全相反方向/毫不相似.
余弦相似度的问题是: 其计算严格要求"两个向量必须所有维度上都有数值", 比如:
v1 = (1, 2, 4),
v2 = (3, -1, null),
那么这两个向量由于v2中第三个维度有null, 无法进行计算.
然而, 实际我们做数据挖掘的过程中, 向量在某个维度的值常常是缺失的, 比如
v2=(3, -1, null)
v2数据采集或者保存中缺少一个维度的信息, 只有两个维度.
那么, 我们一个很朴素的想法就是, 我们在这个地方填充一个值, 不就满足了"两个向量必须所有维度上都有数值"的严格要求了吗?
在填充值的时候, 一般我们用这个向量已有数据的平均值， 所以v2填充后变成
v2=(3, -1, 2),
接下来我们就可以计算cos<v1, v2>了.（由此引出皮尔逊距离）
七、皮尔逊相关系数
皮尔逊相关系数（Pearson Correlation Coefficient）是余弦相似度在维度值缺失情况下的一种改进
-
首先我们来看皮尔森相似度的公式：
假设有两个变量X、Y，那么两变量间的皮尔逊相关系数可通过以下公式计算：
公式一：
公式二：
公式三：
公式四：
以上列出的四个公式等价，其中E是数学期望，cov表示协方差，N表示变量取值的个数。
- 再来看皮尔逊相关系数的思路：皮尔逊是比欧几里德距离更加复杂的可以判断人们兴趣相似度的一种方法。该相关系数通过将两组数据与某一直线拟合的思想来求值，该值实际上就为该直线的斜率。其斜率的区间在[-1,1]之间，其绝对值的大小反映了两者相似度大小，斜率越大，相似度越大，当相似度为1时，该直线为一条对角线。
也被称为“最佳拟合线”
再从余弦相似度的层面来理解皮尔逊相关系数，我把这些
null的维度都填上0, 然后让所有其他维度减去这个向量各维度的平均值, 这样的操作叫作中心化。中心化之后所有维度的平均值就是0了(妙哇！), 也满足进行余弦计算的要求. 然后再进行我们的余弦计算得到结果. 这样先中心化再余弦计得到的相关系数叫作皮尔逊相关系数.由此再看计算皮尔逊相关系数的公式就明了了。用 python实现计算皮尔森相似度:
# @Author : XZP
# @Email : pcxzp@live.com
# @File : PersonSimilarity.py
from math import sqrt
def sim_pearson(prefs, p1, p2):
# Get the list of mutually rated items
si = get_same_Item(prefs, p1, p2)
n = len(si)
# if they are no ratings in common, return 0
if n == 0:
return 0
# Sums of all the preferences
sum_x = sum([prefs[p1][it] for it in si])
sum_y = sum([prefs[p2][it] for it in si])
sum_x2 = sum([pow(prefs[p1][it], 2) for it in si])
sum_y2 = sum([pow(prefs[p2][it], 2) for it in si])
sum_xy = sum([prefs[p1][it] * prefs[p2][it] for it in si])
# 计算系数
num = sum_xy - (sum_x * sum_y / n)
den = sqrt((sum_x2 - pow(sum_x, 2) / n) * (sum_y2 - pow(sum_y, 2) / n))
if den == 0:
return 0
r = num / den
return r
总结: 皮尔逊系数就是cos计算之前两个向量都先进行中心化(centered)，余弦计算和皮尔逊相关系数计算就是一个东西两个名字啊
- 优点：
- 它在数据不是很规范的时候，会倾向于给出更好的结果。
- 修正了“夸大分值”的情况：二者有相对近似的偏好，但某人一般倾向于给出更高的分值，而二者的分值之差又始终保持一致，则他们依然可能会存在很好的相关性（单纯的用欧几里得距离，相似度会偏低，得出不相关的结论，这显然不是我们所期望的。）
八、汉明距离
pass
九、总结
其实你会发现，选择不同的相似性度量方法，对结果的影响是微乎其微的。 ——《集体智慧编程》
