计算相似度

文章来源：

顾名思义，就是计算两个item的相似度，这些在数据挖掘中是个很基础的部分，很多数据挖掘的算法都要以此为基础，例如聚类。因为以前总结过，这里就不再详细说了，下面简单列举了4个方法，根据不同的数据样本选择不同的方式。

举个例子，这里有五本书，a，b，c三个童鞋看过，它们对这五本书的评价如下（分数为1～5）：

A = [1, 2, 4, 3, 5]
B = [2, 4, 3, 3, 4]
C = [3, 3, 2, 2, 3]

问题，谁和用户A的口味比较相似？

1，欧几里德距离。这个大家都熟悉，两点之间的欧几里德距离就是两点间距离公式，各维数据相减，平方后相加，再开方。

2，余弦值。将A，B看成两个向量，计算两个向量的余弦值，也就是这两个向量夹角的余弦值，越大表明越相似（即两向量的夹角越小）。考虑下面两个数 据，[1,2,1,2,2] 和 [2, 4, 2, 4, 4]， 可以看到第二组评分数据每项都是第一组的2倍，这说明两个人的品位也可能相同（只是第一个人要求更严格一些），但是这两个数据若采用上面的欧拉距离，那么 得出的差异值就比较大了，而当用余弦计算时，因为两个有倍数关系，这两个向量的夹角是0，所以cos(0) =  1，也说明了两个向量的相似度很高。

3，皮尔森系数。这个公式更复杂，考虑下面两个向量，加入引入了负值评分系统，打分可以从-5 ~ 5了，那么可能有这两个向量[-2, 1, 2, -2, 1] 和 [4, -2, -4, 4, -2]，这两个向量如果使用余弦计算，由于它们是－2倍数的关系，所以cos值仍然是1，但是这两个用户的品位是完全相反的。这时候使用皮尔森系数，结果 在-1 ~ 1 之间，对于正倍数关系，它可以象余弦一样得到正值；对于负倍数关系，它会计算产生负值，如上面这两个，它产生的结果是－1，符合我们的“品位相反”。

4。Tanimoto。广义Jaccard系数，在二元属性下归约为Jaccard系数。（Jaccard系数是很简单的公式，请google之），Jaccard系数适合处理非对称二元属性，Tanimoto系数在哪种情况下用的多还不清楚。

看代码就知道公式了，python版的(文件是utf-8编码的），。只要将文件中的sample改成开始我们设置的那三个ABC就可以得到相似度了，进而也就知道谁和用户a的口味比较接近。

- EOF -

代码来源：数据挖掘.html

Python语言:

from math import sqrt

def sim_distance(p1, p2):
    c=set(p1.keys()) & set(p2.keys())
    if not c: return 0
    sum_of_squares = sum([pow(p1.get(sk) - p2.get(sk), 2) for sk in c])
    p = 1/(1 + sqrt(sum_of_squares))
    return p

def sim_distance_pir(p1,p2):
    c = set(p1.keys()) & set(p2.keys())
    if not c: return 0
    s1 = sum([p1.get(sk) for sk in c])
    s2 = sum([p2.get(sk) for sk in c])
    sq1 = sum([pow(p1.get(sk), 2) for sk in c])
    sq2 = sum([pow(p2.get(sk), 2) for sk in c])
    ss = sum([p1.get(sk) * p2.get(sk) for sk in c])
    n = len(c)
    num = ss - (s1*s2/n)
    den = sqrt((sq1-pow(s1,2)/n) * (sq2-pow(s2,2)/n))
    #print s1,s2,sq1,sq2,ss,n,num,den
    if den==0: return 0
    p = num / den
    return p

def sim_distance_jacc(p1,p2):
    c = set(p1.keys()) & set(p2.keys())
    if not c: return 0
    ss = sum([p1.get(sk) * p2.get(sk) for sk in c])
    sq1 = sum([pow(sk,2) for sk in p1.values()])
    sq2 = sum([pow(sk,2) for sk in p2.values()])
    p = float(ss)/(sq1 + sq2 - ss)
    return p


def sim_distance_cos(p1, p2):
    c = set(p1.keys()) & set(p2.keys())
    if not c: return 0
    ss = sum([p1.get(sk) * p2.get(sk) for sk in c])
    sq1 = sqrt(sum([pow(sk,2) for sk in p1.values()]))
    sq2 = sqrt(sum([pow(sk,2) for sk in p2.values()]))
    p = float(ss)/(sq1*sq2)
    return p


#a={'a':4.5,'b':1.0,'c':7}

#from distance import *

def topsimilar(item, data, n=5, sim_func=sim_distance):
    score=[(sim_func(data.get(item), data.get(ik)), ik) for ik in data.keys() if ik!=item]
    score.sort()
    score.reverse()
    return score

prefs= {
        "A" : { "1" : 3, "2" : 4, "3" : 0, "4" : 3, "5" : 3},
        "B" : { "1" : 2, "2" : 3, "3" : 2},
        "C" : { "1" : 2, "2" : 4, "3" : 4, "4" : 3, "5" : 0},
        "D" : { "1" : 0, "2" : 4, "3" : 0, "4" : 2, "5" : 4}
}

print (topsimilar('A', prefs,))
print (topsimilar('A', prefs, sim_func=sim_distance_pir))
print (topsimilar('A', prefs, sim_func=sim_distance_cos))
print (topsimilar('A', prefs, sim_func=sim_distance_jacc))