《Programming Collective Intelligence》读书笔记 (2)-- 协同过滤

# 电影评分数据集,用于后面的的测试  
# critics 字典里面每一项是一个用户对若干部电影的评分  
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}}  

# 通过 Pearson Correlation Coefficient 计算两个用户的相似性,数值绝对值越大相关性，正负表示正相关或负相关  
def similarUserWithPearson(scores,user1,user2):  
    commom = [movie for movie in scores[user1] if movie in scores[user2]]  
    if len(commom) == 0:  #no common item of the two users  
        return 0  
    average1 = float(sum(scores[user1][movie] for movie in scores[user1]))/len(scores[user1])  
    average2 = float(sum(scores[user2][movie] for movie in scores[user2]))/len(scores[user2])  
    # denominator  
    multiply_sum = sum( (scores[user1][movie]-average1) * (scores[user2][movie]-average2) for movie in commom )  
    # member  
    pow_sum_1 = sum( math.pow(scores[user1][movie]-average1, 2) for movie in commom )  
    pow_sum_2 = sum( math.pow(scores[user2][movie]-average2, 2) for movie in commom )

    modified_cosine_similarity = float(multiply_sum)/math.sqrt(pow_sum_1*pow_sum_2)  
    return modified_cosine_similarity  

def user_similarity_on_modified_cosine(scores, user1, user2):  
    commom = [movie for movie in scores[user1] if movie in scores[user2]]  
    if len(commom) == 0:  #no common item of the two users  
        return 0  
    average1 = float(sum(scores[user1][movie] for movie in scores[user1]))/len(scores[user1])  
    average2 = float(sum(scores[user2][movie] for movie in scores[user2]))/len(scores[user2])  
    # denominator  
    multiply_sum = sum( (scores[user1][movie]-average1) * (scores[user2][movie]-average2) for movie in commom )  
    # member  
    pow_sum_1 = sum( math.pow(scores[user1][movie]-average1, 2) for movie in scores[user1] )  
    pow_sum_2 = sum( math.pow(scores[user2][movie]-average2, 2) for movie in scores[user2] )

    modified_cosine_similarity = float(multiply_sum)/math.sqrt(pow_sum_1*pow_sum_2)  
    return modified_cosine_similarity  

def findSimilarUsers(scores,user,similarFunction = similarUserWithPearson):  
    similarUser = [(similarFunction(critics, user, otherUser), otherUser) for otherUser in scores if otherUser!=user]  
    # 使用了dict会将含有kv对的列表封装成一个字典,无法利用列表自带的排序函数sort  
    # similarDict = dict([(similarFunction(user,otherUser),otherUser) for otherUser in scores if otherUser!=user])  
    similarUser.sort()  
    similarUser.reverse()  
    #也可将上面两行改成:similarUser.sort(reverse = True)  
    return similarUser # 返回相似度从高到低排序的一个列表  
```  
### 小结

传统的计算相似度的方法就是上面提到的三种：**余弦相似度、修正的余弦相似度和相关相似性（也就是计算皮尔逊系数）**。下面是分别采用上面三种方法为测试数据集中的用户`Lisa Rose`找到前6个最相似用户的结果。完整的代码见文末

```  
# 欧几里得距离，第一个值是分数，第二个值是具体的用户  
(0.4444444444444444, 'Michael Phillips')  
(0.3333333333333333, 'Mick LaSalle')  
(0.2857142857142857, 'Claudia Puig')  
(0.2222222222222222, 'Toby')  
(0.21052631578947367, 'Jack Matthews')  
(0.14814814814814814, 'Gene Seymour')

# 皮尔逊系数，第一个值是分数，第二个值是具体的用户  
(0.9345507010964664, 'Toby')  
(0.747017880833996, 'Jack Matthews')  
(0.5940885257860046, 'Mick LaSalle')  
(0.5477225575051661, 'Claudia Puig')  
(0.39605901719066977, 'Gene Seymour')  
(0.3872983346207417, 'Michael Phillips')

# 修正的余弦相似度，第一个值是分数，第二个值是具体的用户  
(0.8093446482740976, 'Toby')  
(0.747017880833996, 'Jack Matthews')  
(0.5940885257860046, 'Mick LaSalle')  
(0.4743416490252569, 'Claudia Puig')  
(0.39605901719066977, 'Gene Seymour')  
(0.33541019662496846, 'Michael Phillips')  

# 给用户推荐物品，物品的评分采用与其他用户的相似度乘上其他用户的实际评分  
def recommendItem(scores,user):  
    userSimilarity = findSimilarUsers(scores, user)  
    swapUserSimilarity = {v:k for k, v in userSimilarity} # 交换键值，将存储kv对的列表转换为字典，交换后为无序  
    allMovies = []  
    for (k,v) in critics.items():  
        for movie in v:  
            if movie not in allMovies:  
                allMovies.append(movie)  
    itemScore = []  
    for movie in allMovies:  
        scoreSum = 0  
        similaritySum = 0  
        for similarity, otherUser in userSimilarity:  
            if critics[otherUser].has_key(movie):  
                scoreSum += critics[otherUser][movie] * similarity  
                similaritySum += swapUserSimilarity[otherUser]  
        itemScore.append((scoreSum/similaritySum, movie))

    itemScore.sort(reverse=True)  
    recommend_movies = [] # 为user推荐的电影  
    print 'all movies ranking:'  
    for i,j in itemScore:  
        print i,j  
        if j not in critics[user]:  
            recommend_movies.append(j)  
    print 'recommended movies for %s:%s' %(user, recommend_movies)  

将  
'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5},  
'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5}}  
转换为  
{'Lady in the Water':{'Lisa Rose':2.5,'Gene Seymour':3.0},  
'Snakes on a Plane':{'Lisa Rose':3.5,'Gene Seymour':3.5}} etc..