协同过滤算法

协作型过滤

协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。

协同过滤一般是在海量的用户中发掘出一小部分和你品位比较类似的，在协同过滤中，这些用户成为邻居，然后根据他们喜欢的其他东西组织成一个排序的目录推荐给你。

要实现协同过滤，需要以下几个步骤：

• 搜集偏好

• 寻找相近用户

• 推荐物品

搜集偏好

首先，我们要寻找一种表达不同人及其偏好的方法。这里我们用python的嵌套字典来实现。

在本章中所用的数据，是从国外的网站 grouplens下载的 u.data。该数据总共四列，共分为用户ID、电影ID、用户评分、时间。我们只需根据前三列，生成相应的用户偏好字典。

  #生成用户偏好字典
def make_data():
    result={}
    f = open('data/u.data', 'r')
    lines = f.readlines()
    for line in lines:
        #按行分割数据
        (userId , itemId , score,time ) = line.strip().split("\t")
        #字典要提前定义
        if not result.has_key( userId ):
            result[userId]={}
        #注意float,不然后续的运算存在类型问题
        result[userId][itemId] = float(score)
    return result

另外如果想在字典中显示展现电影名，方便分析，也可以根据 u.item中电影数据，预先生成电影的数据集。

  #将id替换为电影名 构造数据集
def loadMovieLens(path='data'):
    # Get movie titles
    movies={}
    for line in open(path+'/u.item'):
        (id,title)=line.split('|')[0:2]
        movies[id]=title

    # Load data
    prefs={}
    for line in open(path+'/u.data'):
        (user,movieid,rating,ts)=line.split('\t')
        prefs.setdefault(user,{})
        prefs[user][movies[movieid]]=float(rating)
    return prefs

根据上面两个函数中的一种，到此我们的用户数据集已经构造好了，由于数据量不是非常大，暂时放在内存中即可。
由于以上数据集比较抽象，不方便讲解，至此我们定义一个简单的数据集来讲解一些例子，一个简单的嵌套字典：

  #用户：{电影名称：评分}
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}
}

寻找相近用户

收集完用户信息后，我们通过一些方法来确定两个用户之间品味的相似程度，计算他们的 相似度评价值。有很多方法可以计算，我们在此介绍两套常见的方法：欧几里得距离和皮尔逊相关度。

欧几里得距离

欧几里得距离（euclidea nmetric）（也称欧式距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

数学定义：
已知两点 A = (x_1,x_2,...,x_n)和 B = (y_1,y_2,...,y_n)，则两点间距离：
$$|AB|=\sqrt{(x_1 - x_2)^2+(y_1 - y_2)^2+...+(x_n-y_n)^2}$$
接下来我们只要把数据集映射为坐标系就可以明显的比较出相似度，以"Snakes on a Plane"和"You, Me and Dupree"两部电影距离，有坐标系如下图：

计算上图中Toby和Mick LaSalle的相似度：

from math import sqrt
sqrt(pow( 4.5-4 , 2 ) + pow( 1 - 2 , 2))
1.118033988749895

上面的式子计算出了实际距离值，但在实际应用中，我们希望相似度越大返回的值越大，并且控制在0~1之间的值。为此，我们可以取函数值加1的倒数(加1是为了防止除0的情况)：

1/(1+sqrt(pow( 4.5-4 , 2 ) + pow( 1 - 2 , 2)))
0.4721359549995794

接下来我们就可以封装一个基于欧几里得距离的相似度评价，具体python实现如下：

  #欧几里得距离
def sim_distance( prefs,person1,person2 ):
    si={}
    for itemId in prefs[person1]:
        if itemId in prefs[person2]:
            si[itemId] = 1
    #no same item
    if len(si)==0: return 0
    sum_of_squares = 0.0    
    
    #计算距离 
    sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) for item in si])
    return 1/(1 + sqrt(sum_of_squares) )

基于测试数据集critics，则可以计算两个人的相似度值为：

sim_distance( critics , 'Toby', 'Mick LaSalle' )
0.307692307692

皮尔逊相关度

皮尔逊相关系数是一种度量两个变量间相关程度的方法。它是一个介于 1 和 -1 之间的值，其中，1 表示变量完全正相关， 0 表示无关，-1 表示完全负相关。

数学公式：
$$\frac{\sum x_iy_i-\frac{\sum x_i\sum y_i}{n}}{\sqrt{\sum x_i^2-\frac{(\sum x_i)^2}{n}}\sqrt{\sum y_i^2-\frac{(\sum y_i)^2}{n}}}$$

与欧几里得距离不同，我们根据两个用户来建立笛卡尔坐标系，根据用户对相同电影的评分来建立点，如下图：

在图上，我们还可以看到一条线，因其绘制的原则是尽可能的接近图上所有点，故该线也称为 最佳拟合线。用皮尔逊方法进行评价时，可以修正“ 夸大值”部分，例如某人对电影的要求更为严格，给出分数总是偏低。

python代码实现：

  #皮尔逊相关度 
def sim_pearson(prefs,p1,p2):
    si={}
    for item in prefs[p1]: 
      if item in prefs[p2]: si[item]=1
    
    if len(si)==0: return 0
    
    n=len(si)
    
    #计算开始
    sum1=sum([prefs[p1][it] for it in si])
    sum2=sum([prefs[p2][it] for it in si])
    
    sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
    sum2Sq=sum([pow(prefs[p2][it],2) for it in si])   
    
    pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
    
    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

最后根据critics的数据计算Gene Seymour和Lisa Rose的相关度：

recommendations.sim_pearson(recommendations.critics,'Gene Seymour','Lisa Rose')

为评论者打分

到此，我们就可以根据计算出用户之间的相关度，并根据相关度来生成相关度列表，找出与用户口味相同的其他用户。

  #推荐用户
def topMatches(prefs,person,n=5,similarity=sim_distance):
    #python列表推导式
    scores=[(similarity(prefs,person,other),other) for other in prefs if other!=person]
    scores.sort()
    scores.reverse()
    return scores[0:n]

推荐物品

对于用户来说，找出与他具有相似爱好的人并不重要，主要是为他推荐他可能喜欢的物品，所以我们还需要根据用户间相似度进一步计算。例如为Toby推荐，由于数据不多，我们取得所有推荐者的相似度，再乘以他们对电影的评价，得出该电影对于Toby的推荐值，也可以认为是Toby可能为电影打的分数。如下图：

我们通过计算其他用户对某个Toby没看过电影的加权和来得到总权重，最后除以相似度和，是为了防止某一电影被看过的多，总和会更多的影响，也称“ 归一化”处理。

  #基于用户推荐物品
def getRecommendations(prefs,person,similarity=sim_pearson):
    
    totals={}
    simSums={}

    for other in prefs:
        #不和自己做比较
        if other == person: 
            continue
        sim = similarity( prefs,person,other )
        #去除负相关的用户
        if sim<=0: continue
        for item in prefs[other]:
            #只对自己没看过的电影做评价
            if item in prefs[person]:continue
            totals.setdefault( item ,0 )
            totals[item] += sim*prefs[other][item]
            simSums.setdefault(item,0)
            simSums[item] += sim
    #归一化处理生成推荐列表
    rankings=[(totals[item]/simSums[item],item) for item in totals]
    #rankings=[(total/simSums[item],item) for item,total in totals.items()]
    rankings.sort()
    rankings.reverse()
    return rankings

基于物品的协同过滤

以上所讲的都是基于用户间相似的推荐，下面我们看看基于物品的推荐。

同样，先构造数据集，即以物品为key的字典，格式为{电影:{用户:评分,用户:评分}}

  #基于物品的列表
def transformPrefs(prefs):
    itemList ={}
    for person in prefs:
        for item in prefs[person]:
            if not itemList.has_key( item ):
                itemList[item]={}
                #result.setdefault(item,{})
            itemList[item][person]=prefs[person][item]
    return itemList

计算物品间的相似度，物品间相似的变化不会像人那么频繁，所以我们可以构造物品间相似的集合，存成文件重复利用：

  #构建基于物品相似度数据集
def calculateSimilarItems(prefs,n=10):
    result={}
    itemPrefs=transformPrefs(prefs)
    c = 0
    for item in itemPrefs:
        c += 1
        if c%10==0: print "%d / %d" % (c,len(itemPrefs))
        scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
        result[item]=scores
    return result

基于物品的推荐值计算，通过Toby已看影片的评分，乘以未看影片之间的相似度，来获取权重。最后归一化处理如下图：

  #基于物品的推荐
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    

源码

思考

1. UserCF和ItemCF的比较

2. 归一化处理的更合适方法

3. 与频繁模式挖掘的区别