python算法学习之推荐系统

之前一直对算法不太感冒，感觉既乏味又务虚，除了用来考试/面试，实在找不出其他用途。毕竟平时实际项目中也不常遇到需要深入理解算法的地方。加上教科书的影响，对算法一直敬而远之。
直到开始阅读《集体智慧编程》。
才发现原来这也挺好玩的呀。
遂决定好好学习。

长期以来，受惠于推荐系统，日久生情，对此产生了兴趣。比如豆瓣能根据你的浏览记录（评分记录）推荐你可能喜欢的小组，可能喜欢的文章，可能感兴趣的活动。而且往往还真能猜准～
无觅阅读的文章推荐也很和我胃口，不必花太多时间就能轻松找到喜欢的文章。
这类系统能分析出你的品味，它居然知道我的品味！！想想都令人兴奋，系统居然像你的知音一样知道你的品味！！

如果不觉得一件东西有趣，实在很难硬着头皮学下去。既然发现它很好玩，想无视它，也难了。
那就开始我们的算法旅程吧。
从推荐系统开始～

这组文章偏向于总结吧，不是作为入门指南，如果你也对这类算法感兴趣，推荐去阅读《集体智慧编程》，而不是看博客。 这组文章使用的算法皆来自《集体智慧编程》，我只是做些摘录，为了方便日后使用.你也可以使用 这些代码，至于使用过程中你要受到哪些限制，请参考原书的申明部分。

###实例学习 在这个实例里，我们想知道用户的兴趣偏好（口味）。
情景是这样的：几位用户看过几部电影，他们对这些电影进行了评分，我们拿到了这组数据,r如下：

	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}, 
	'Michael Phillips': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0,
	 'Superman Returns': 3.5, 'The Night Listener': 4.0},
	'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0,
	 'The Night Listener': 4.5, 'Superman Returns': 4.0, 
	 'You, Me and Dupree': 2.5},
	'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 
	 'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0,
	 'You, Me and Dupree': 2.0}, 
	'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
	 'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5},
	'Toby': {'Snakes on a Plane':4.5,'You, Me and Dupree':1.0,'Superman Returns':4.0}}

这些数据是python的字典格式,你如果熟悉js,会发现它几乎就是json格式.
大多网站api接口返回的格式都是json，这样你就知道用python处理这些数据是多么容易.

现在我想挖掘一下这些数据，看看哪两个人的品味比较接近。
摆在我面前的问题是如何度量两个人的品味相似程度呢.毕竟口味这东西不是空间距离可以度量。
距离真是个很好的隐喻。两个品味不同的人就像来自两个星球
如果我们能找到一个数值来度量两个人品味的距离，那么这个问题就变成了数值计算问题！！
还真有这样的东西，我们可以用欧吉里德距离和皮尔逊相关度来度量两者相似度.
这里有一个很有趣的概念，叫偏好空间。我们使用以上数据作图：
两个人在偏好空间中距离越近，表示品味越近.如果有多项评分，那么这张图就对应多维。依然适用

我们直接给出计算相似度的欧吉里德方法吧：

	from math import sqrt

	# Returns a distance-based similarity score for person1 and person2
	def sim_distance(prefs,person1,person2):
	  # Get the list of shared_items
	  si={}
	  for item in prefs[person1]: 
	    if item in prefs[person2]: si[item]=1

	  # if they have no ratings in common, return 0
	  if len(si)==0: return 0

	  # Add up the squares of all the differences
	  sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) 
	                      for item in prefs[person1] if item in prefs[person2]])

	  return 1/(1+sum_of_squares)

这里的核心公式，就是数学中简单的两点间距离计算公式,代码只是对此的一个实现，理解时建议在旁边写个数学距离计算公式，那样比代码更能清晰表达算法的本质。

顺便把皮尔逊计算方法也写上，稍后解释：

	# Returns the Pearson correlation coefficient for p1 and p2
	def sim_pearson(prefs,p1,p2):
	  # Get the list of mutually rated items
	  si={}
	  for item in prefs[p1]: 
	    if item in prefs[p2]: si[item]=1

	  # if they are no ratings in common, return 0
	  if len(si)==0: return 0

	  # Sum calculations
	  n=len(si)
	  
	  # Sums of all the preferences
	  sum1=sum([prefs[p1][it] for it in si])
	  sum2=sum([prefs[p2][it] for it in si])
	  
	  # Sums of the squares
	  sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
	  sum2Sq=sum([pow(prefs[p2][it],2) for it in si])	
	  
	  # Sum of the products
	  pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
	  
	  # Calculate r (Pearson score)
	  num=pSum-(sum1*sum2/n)
	  den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
	  if den==0: return 0

	  r=num/den

	  return r

waiting