集体智慧编程（一）推荐系统之欧里几德距离

  在网上购物，听歌，看电影的网站上，网站都会根据我们的购物记录，听歌记录或着是观看记录给我们推荐一些商品，音乐或者是电影。那这些推荐系统是怎么实现的呢？首先，推荐一个东西，得是购物者所感兴趣的，那么怎么判断购物者对该物品感兴趣呢？那么，就得根据购物者的记录来判断了，假定购物者所购买的物品都是他所感兴趣的。那么跟该购物者的物品相似的物品就是可以推荐的，这种推荐是基于相似条目的。另外，可以相似的人会大都会有相同的爱好，因此可以根据购物者的该买记录找出相似的购物者，并把相似购物者购买的物品推荐出来，这就是基于相似用户的推荐。

  这里简单讲解一种基于用户相似度的简单的经典算法——欧里几得距离算法。

  欧里几得距离指的就是平面上的两个点的距离，即是如下方式计算：

   扩展到N维的空间上，两个点的距离为:

 那么，假定两个购物者X,Y，他们都购买了某一件物品，或者都没有购买某一件物品，那么该点的距离为0，如果只有一人购买了，那么距离为1，通过计算他们所买的所有物品的距离，就可以计算处X和Y的距离distance(X,Y)

可以通过以下程序来实现：

#!/usr/bin/python
#data
x_user={'pen':1,'pencil':0,'knife':1,'notebook':1,'book':0}

y_user={'pen':0,'pencil':0,'knife':1,'notebook':1,'book':0}

#calculate distance
from math import sqrt
def distance(person1,person2):
        dis=0
        dis=sum([pow(person1[item]-person2[item],2)
                for item in person1])
        return sqrt(dis)

print distance(x_user,y_user)

初始距离，即是最小距离为0.对于相通的商品，0表示没有购买，1表示购买了的。通过计算，得知X和Y的距离为1。

这样计算存在一个问题，对于不同数目的商品，计算出来的距离会不在同一个范围内，所以需要对结果进行处理。相似度在0-1的范围内，越大表示相似度越高。那么相似度公式为：

                     

经过这样的处理，就可以保证相似度和距离成反比，且保持在0-1的范围内。

代码修正如下：

#!/usr/bin/python
#data
x_user={'pen':1,'pencil':0,'knife':1,'notebook':1,'book':0}

y_user={'pen':0,'pencil':0,'knife':1,'notebook':1,'book':0}

#calculate distance
from math import sqrt
def distance(person1,person2):
        dis=0
        dis=sum([pow(person1[item]-person2[item],2)
                for item in person1])
        return 1/(1+sqrt(dis))

print distance(x_user,y_user)

此时，计算出的相似度为0.5

以上只是欧里几德方法的一种简单实现，这种算法精度不是很高，还有很多几个可以提高的方面：

1、对于每个物品的距离，可以更加精确，不只是0或者1，可以是0-5之间的值

2、不同物品可能贡献的权值不一样，例如有些物品很多人都喜欢，有些物品很少有人喜欢，也可以根据物品的受欢迎程度赋予不同的权值来提高精度。