Programming Collective Intelligence No.1 推荐系统

前言

前几天和老师交流过，不推荐一上来就接触深度学习和神经网络，而应该先打好机器学习的基础。我在五月份已经看完了整本《基于python的深度学习入门》，这是一位日本人写的书，风格与众不同，很适合用来入门。虽然已经基本理解神经网络、误差反向传播等相关概念，但是尚没有动手实践其中的算法，而且看到一些实践技巧和流行算法时有点较懵，索性暂时搁置。之前被人推荐了《集体智慧编程》，Programming Collective Intelligence，五月份去图书馆借过英文影印版，可惜读起来有些困难，后来买了中文版，尚未看过。这本书适合用来进一步熟悉Python并打好机器学习的基础，很符合我现在的需求，于是毅然甩下其他锅刷起这本书。我并不是一个媒体人，不是说那些名词理解了就好了，而是一个计算机专业的学生，未来会成为一名工程师或是研究人员，理解只是最低的要求。如果说七月份的时候我生出了一种职业生涯要起步了的感觉，现在则是完全改变了学习的态度，我不再追求应用那些先进的工具、做出看起来最厉害的事情、学习那些五花八门的名词，而是专注于理解、实践每一个算法，用最简单的工具搞事情，同时提高整体的编程能力。

Time is relative, okay? It can stretch and it can squeeze, but…it can’t run backwards. It just can’t.时间可以伸缩和折叠，唯独不能倒退。时间是一场旅行，更像是一种投资，其精髓在于在最合适的时间选择做最合适的事情，以期获得最大的效益。因而，可以做的事情那么多，并不是每一件都要现在去做，并不是所有东西都要现在学，静下心来拿脑子想想，做出当前看来最合理的安排与选择。

以前高中搞OI的时候，同机房的松鼠非常骄傲地说：“我虽然AC掉的题不多，但是我每道题都是自己写的呀。”希望我在打基础阶段也可以自豪地说：“我虽然做的东西并不前沿，但是每一个函数都是我自己写过的，每一个细节都是我推敲过的。”还有一句话是，真正的厉害，是对看似简单的东西融会贯通。

与诸位共勉，开始吧！

提供推荐的系统

概述

以前，我们想要看电影、听音乐、购买商品，会先向他人询问。然而随着择越来越多，要想通过询问一小群人来确定我们想要的东西将会变得越来越不切实际，因为他们可能并不了解所有的选择。因而，发展出了一种协作型过滤的技术，根据群体偏好来为人们提供推荐，有许多针对于此的应用，如：在线购物中的商品推荐、热门网站的推荐，以及帮助人们寻找音乐和影片的应用。

搜集偏好

我们需要寻找一种方式，来表达不同的人及其偏好。当数据规模较大时，应该将数据存入数据库中。而对于规模较小的数据集，在Python中可以使用嵌套的字典。

寻找相近的用户——相似度评价值

在数值计算中，范数的选取会一定程度影响收敛效果，而神经网络中损失函数的选取也会影响学习率。正如高考选拔人才的方式会影响整个国家的基础教育一样，评价标准、衡量方法会带来不同的实际效果。不过，没有一种方法是绝对好的，使用哪一种方法最优，完全取决于具体的应用。

欧几里得距离

这是最好理解的一种评价方法，供人评价的每种物品为一个坐标轴，将参与评价的人按其评分绘制在图上，对于任意两人，计算出每一轴向上的差值，求平方后相加，对总和取平方根。然而我们希望偏好越相近相似值越大，将函数值加1（避免被零除），并取其倒数，得到一个返回值介于0和1直接的函数。

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]])
  # 示例代码这行有bug，已修正
  return 1/(1+sqrt(sum_of_squares))

皮尔逊相关度

使用欧几里得距离时有一个问题，我们求得的偏好值会受到人们打分标准的影响——有的人较为宽松，有的人则很严格。我们想要了解两个人偏好的相似度，应该剔除数据不规范造成的误差，修正“夸大分值”，在这一点上，较为复杂的皮尔逊相关度优于欧几里得距离。

我们在平面上定位各个影片，以《Superman》为例，假如A评价3分，B评价5分，那么这部影片就被定位在(3,5)处。将所有影片都如此定位之后，我们得到了一张散点图，我们可以用最小二乘法对此进行拟合，绘制出一条直线，即最佳拟合线。而相关系数，这个在高中课本中被孤零零地介绍过的概念，可以用来衡量直线对散点的拟合程度，也可表示最佳拟合线下两者的相关程度。高中时介绍过两个公式，当时必须手算，现在写成代码就好了，实在是幸福。

$r={\frac {\sum \limits {i=1}^{n}(X{i}-{\overline {X}})(Y_{i}-{\overline {Y}})})^{2}}}{\sqrt {\sum \limits {i=1}^{n}(Y{i}-{\overline {Y}})^{2}}}}}$

$r={\frac {1}{n-1}}\sum \limits {i=1}^{n}\left({\frac {X{i}-{\overline {X}}}{\sigma {X}}}\right)\left({\frac {Y{i}-{\overline {Y}}}{\sigma _{Y}}}\right)$

# 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

其他相似性度量法

Jaccard系数

Jaccard（杰卡德）系数主要用于计算样本间的相似度。Jaccard系数的计算方式为：样本交集个数和样本并集个数的比值，用J(A,B)表示。公式为：

è¿éåå¾çæè¿°

jaccard系数相反的即为jaccard距离，用两个集合中不同元素所占元素的比例来衡量两个样本之间的相似度，公式为：

è¿éåå¾çæè¿°

曼哈顿距离算法

这也是一个非常常见的名词，纽约的市政规划做得很迷，曼哈顿区非常繁华，高楼林立，每个街区大小相近、四四方方，十分规整。因此，驾车在城市中行驶，往往是走折线，这也就是曼哈顿距离的来源。在中控杯中，不太厉害的队伍只能靠巡方格的边线来前进、定位，这时候走的最短距离就是曼哈顿距离。用来衡量相似度，加一求倒数即可。

参考与补充

网上有朋友整理了多达18种相似度计算方法。

https://en.wikipedia.org/wiki/Metric_(mathematics)#Examples

https://blog.csdn.net/solomonlangrui/article/details/47454805

https://www.cnblogs.com/AlvinSui/p/8931074.html

提供推荐

我们对寻找与自己有相似品味的影评者很感兴趣，这样我们就可以知道选择影片式采纳谁的建议。下面的代码可以得到影评者之间的相似度。

# Returns the best matches for person from the prefs dictionary. 
# Number of results and similarity function are optional params.
def topMatches(prefs,person,n=5,similarity=sim_pearson):
  scores=[(similarity(prefs,person,other),other) 
                  for other in prefs if other!=person]
  scores.sort()
  scores.reverse()
  return scores[0:n]

相比较于寻找趣味相投的影评者，我们更想得到的是一份影片的推荐。为此，我们需要做一些归一化的操作，对于我而言，我要得到我和其他影评者之间的相似度，再乘以他们为每部影片给出的评价值。这样的话，一部受更多人评论的电影会有更高的分支，为了修正这一问题，我们再除以相似度之和，如此，就可以预测自己对影片的评价情况。

# Gets recommendations for a person by using a weighted average
# of every other user's rankings
def getRecommendations(prefs,person,similarity=sim_pearson):
  totals={}
  simSums={}
  for other in prefs:
    # don't compare me to myself
    if other==person: continue
    sim=similarity(prefs,person,other)

    # ignore scores of zero or lower
    if sim<=0: continue
    for item in prefs[other]:
	    
      # only score movies I haven't seen yet
      if item not in prefs[person] or prefs[person][item]==0:
        # Similarity * Score
        totals.setdefault(item,0)
        totals[item]+=prefs[other][item]*sim
        # Sum of similarities
        simSums.setdefault(item,0)
        simSums[item]+=sim

  # Create the normalized list
  rankings=[(total/simSums[item],item) for item,total in totals.items()]

  # Return the sorted list
  rankings.sort()
  rankings.reverse()
  return rankings

此处我们发现，选择不同的相似性度量方法，对结果的影响是微乎其微的。（？）

匹配商品

之前我们已经实现了为某人寻找品味相近者，为某人提供影片推荐，现在我们想通过人们的评价来了解影片之间的相似度，这在购物网站中广泛应用。我们可以沿用之前的方法，将人与物对调，再确定相似度即可。

def transformPrefs(prefs):
  result={}
  for person in prefs:
    for item in prefs[person]:
      result.setdefault(item,{})
      
      # Flip item and person
      result[item][person]=prefs[person][item]
  return result

在本例中，如果A和B的相关值为负，则说明喜欢A的人，存在不喜欢B的倾向。

基于物品的过滤

对于一个数据集较大的大型网站而言，将每一个用户和其他所有用户进行比较，然后再对每位用户评过分的商品比较，其速度是无法忍受的。对于商品销售量很大的网站，用户在偏好方面少有重叠，数据会比较稀疏，在这种情况下，基于物品的协作型过滤能得出更好的结论，而且它允许我们将大量人物预先执行，从而更快地基于用户推荐结果。

总体思路就是为每件物品预先计算好最为相近的其他物品，然后，当我们想为每位用户提供推荐时，可以查看他曾经评过分的物品，并从中选出排位靠前着，再构造出一个加权列表。尽管第一步要求我们检查所有的数据，但是物品间的比较不会像用户间那样频繁变化，我们可以将这样的运算任务安排在网络流量不是很大的时候进行。

构造物品比较数据集

先利用倒置函数，获得一个有关物品及其评价的列表。然后循环遍历每项物品，求得最为相近的物品及相似度评价值，最后建立并返回一个包含物品及其最相近物品列表的字典。构建完一次数据集之后，我们就可以在需要的时候重复使用它。

def calculateSimilarItems(prefs,n=10):
  # Create a dictionary of items showing which other items they
  # are most similar to.
  result={}
  # Invert the preference matrix to be item-centric
  itemPrefs=transformPrefs(prefs)
  c=0
  for item in itemPrefs:
    # Status updates for large datasets
    c+=1
    if c%100==0: print（"%d / %d" % (c,len(itemPrefs))）
        #示例代码此处有误，已更正
    # Find the most similar items to this one
    scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
    result[item]=scores
  return result

只有频繁执行该函数，物品的相似度才不会过期。

获得推荐

记得进行归一化。

def getRecommendedItems(prefs,itemMatch,user):
  userRatings=prefs[user]
  scores={}
  totalSim={}
  # Loop over items rated by this user
  for (item,rating) in userRatings.items( ):

    # Loop over items similar to this one
    for (similarity,item2) in itemMatch[item]:

      # Ignore if this user has already rated this item
      if item2 in userRatings: continue
      # Weighted sum of rating times similarity
      scores.setdefault(item2,0)
      scores[item2]+=similarity*rating
      # Sum of all the similarities
      totalSim.setdefault(item2,0)
      totalSim[item2]+=similarity

  # Divide each total score by total weighting to get an average
  rankings=[(score/totalSim[item],item) for item,score in scores.items( )]

  # Return the rankings from highest to lowest
  rankings.sort( )
  rankings.reverse( )
  return rankings

使用MovieLens真实数据集

MovieLens数据集是一个涉及电影评价的真是数据集，由明尼苏达州立大学GroupLens项目组开发，下载链接为 https://grouplens.org/datasets/movielens/我选取的是迷你版的数据集，几个文件分别包括了影片名、影片标签、用户打分、影片链接，最后一次更新时间为2018年6月。

加载文件

CSV是英文Comma Separate Values（逗号分隔值）的缩写，顾名思义，文档的内容是由 “,” 分隔的一列列的数据构成的。CSV文档是一种编辑方便，可视化效果极佳的数据存储方式。Python中有着非常强大的库可以处理这种文档。

def loadMovieLens(path='/data/ml-latest-small'):
  import csv
  import codecs
  # Get movie titles
  movies={}
  csvFile = open("movies.csv", "rb")
  reader1 = csv.reader(codecs.iterdecode(csvFile, 'utf-8'))  
  for item in reader1:
    if reader1.line_num == 1:
        continue    
    id = item[0]
    title = item[1]
    movies[id]=title
  
  # Load data
  prefs={}
  csvFile2 = open("ratings.csv", "rb")
  reader2 = csv.reader(codecs.iterdecode(csvFile2, 'utf-8'))
  for item in reader2:
    if reader2.line_num == 1:
        continue    
    (user,movieid,rating,ts)=item
    prefs.setdefault(user,{})
    prefs[user][movies[movieid]]=float(rating)
  return prefs

运行并获得推荐

reload(recommendations)
prefs=recommendations.loadMovieLens()

#基于用户的推荐
recommendations.getRecommendations(prefs,'87') [0:30]

#基于物品的推荐 构建相似度字典与获得推荐
itemsim=recommendations.calculateSimilarItems(prefs,n=50)
recommendations.getRecommendedItems(prefs,itemsim,'87')[0:30]

[(5.0, 'Zeitgeist: Moving Forward (2011)'), (5.0, 'Wow! A Talking Fish! (1983)'), (5.0, 'Wonder Woman (2009)'), (5.0, 'Woman Under the Influence, A (1974)'), (5.0, 'Woman Is a Woman, A (femme est une femme, Une) (1961)'), (5.0, 'Winter in Prostokvashino (1984)'), (5.0, 'Winnie the Pooh and the Day of Concern (1972)'), (5.0, 'Winnie the Pooh Goes Visiting (1971)'), (5.0, 'Winnie Pooh (1969)'), (5.0, 'Wings, Legs and Tails (1986)'), (5.0, 'When Worlds Collide (1951)'), (5.0, 'What Men Talk About (2010)'), (5.0, 'Watermark (2014)'), (5.0, 'War for the Planet of the Apes (2017)'), (5.0, 'Vovka in the Kingdom of Far Far Away (1965)'), (5.0, 'Very Potter Sequel, A (2010)'), (5.0, 'Vampire in Venice (Nosferatu a Venezia) (Nosferatu in Venice) (1986)'), (5.0, 'Vagabond (Sans toit ni loi) (1985)'), (5.0, 'Vacations in Prostokvashino (1980)'), (5.0, 'Unfaithfully Yours (1948)'), (5.0, "Tyler Perry's I Can Do Bad All by Myself (2009)"), (5.0, 'Two Family House (2000)'), (5.0, 'True Stories (1986)'), (5.0, 'Troll 2 (1990)'), (5.0, 'Travels of an Ant (1983)'), (5.0, 'Trailer Park Boys (1999)'), (5.0, 'Tokyo Tribe (2014)'), (5.0, 'Three from Prostokvashino (1978)'), (5.0, 'Thousand Clowns, A (1965)'), (5.0, 'There Once Was a Dog (1982)')]

To be continued

第二章的内容周三花了半个上午看完，然而实践起来却花了周日大半天。在实践的过程中遇到很多坑这些都是仅靠看书想想不到的困难：

reload重载文件
print的各种用法
csv文件的读取

还有很多事情可以做：

用MovieLens数据集探究不同评价方法对结果的影响程度
利用API构造数据集，尤其是中文网站的数据集，为身边的人做一个推荐系统
对MovieLens中的影片实现聚类（与第三章相关但方法不同）

之前在各种论坛上看到很多人说这本书第二章的代码不能用，以及书中的网站域名已经更改，相比较于改一改用一用示例代码，我更倾向于按照书中讲述的思路自己写一份符合自己需求的代码。

本书后面的章节更加吸引我，请期待我的后续整理。

No.1 推荐系统 Making Recommendations