协同过滤算法

说明：本博客是学习《python机器学习算法》赵志勇著的学习笔记，其图片截取也来源本书。

协同过滤(ccollaborative Filtering，CF)算法是最基本的推荐算法，CF算法是从用户的历史行为数据中挖掘出用户的兴趣，为用户推荐其感兴趣的项。
根据挖掘方法的不同，协同过滤算法可以分为基于用户的(User-based)协同过滤算法和基于项的(Item-based)协同过滤算法。

1、推荐系统的概述

1.1、推荐系统

在信息过载的时代，信息呈现出爆炸式增长，大量的信息给用户不断带来新的信息的同时，也增加了用户筛选信息的难度，当用户有明确的需求时，比如需要
查找信息，可以利用搜索引擎查找到相关的信息。

但是并不是任何情况下用户都是有明确要求的，纯粹是为了打发时间，为了能够帮助用户筛选出一批他们可能喜欢的信息，就需要分析出该用户的兴趣，
从海量的信息中选择与用户相似的信息，并将这些信息推荐给用户。推荐系统(Recommendation System，RS)正是在这样的背景下被提出的，推荐算法根据用户的历史行为，挖掘出用户的喜好，并为用户推荐与其喜好相符的商品或者信息。推荐系统的任务就是能够连接信息与用户，帮助用户找到其感兴趣的信息，
同时让一些有价值的信息能够推荐给潜在的用户。

1.2、推荐问题的描述

推荐系统的核心问题是为用户推荐与其兴趣相似度比较高的商品。此时，需要一个函数f(x),并用来计算商品与用户之间的相似度，并向用户推荐相似度比较高的的商品。为了能够预测出函数f(x)，可以利用到的历史数据主要有：用户的历史行为数据，与该用户相关的其他用户信息，商品之间的相似度、文本的描述等。

假设集合C表示所有的用户，集合S表示所有需要推荐的商品。函数f表示商品s到用户c之间的有效性的效用函数，例如：
f：C*S -> R , 其中，R是一个全体的排序集合。对于每一个用户c属于C，希望从商品的集合中选出商品，即s属于S，以使得函数f的值最大。

1.3、推荐的常用方法

在推荐系统中，常用的推荐算法主要有：

协同过滤的推荐(Collaborative Filtering Recommendation)

基于内容的推荐(Content-based Recommendation)

基于关联规则的推荐(Association Rule-based Recommendation)

基于效用的推荐(Utility-based Recommendation)

基于知识的推荐(knowledge-based Recommendation)

组合推荐(Hybrid Recommendation)

2、基于协同过滤的推荐

2.1、协同过滤算法的分类

上面讲过基于协同过滤算法有两种方法：

1、通过相似用户进行推荐，通过比较用户之间的相似性，越相似表明两者之间的品味越相近，这就是基于用户的协同过滤算法

2、通过相似项进行推荐。通过比较项与项之间的相似性，为用户推荐与其历史行为相似的项。

在基于用户的协同过滤算法中，利用用户访问行为的相似性向目标用户推荐其感兴趣的项，如下图所示。

在上图中，假设用户分别为u1、u2、u3，其中用户u1互动过的商品有i1和i3，用户u2互动过的商品为i2，用户u3互动过的商品有i1、i3和i4。通过计算知道u1和u3较为相似，对于u1来说，u3互动过的商品i4是u1没有互动过的，因此会将商品i4推荐给u1。

在基于项的协同过滤算法中，根据所有用户对物品的评价，发现物品的相似度，然后根据用户的历史偏好将类似的物品推荐给该用户，如下图所示。

在上图中，u1对应i1和i3；u2对应i1、i2和i3；u3对应i1。通过计算知道i1和i3较为相似，对于用户i3来说，u1互动过的商品i3是u3没有互动过的，因此会将i3推荐给u3。

2.2、相似度的度量方法

相似性的度量方法有很多种，不同的度量方法的应用范围也不一样。相似度的度量方法在不同机器学习算法中都有应用。

相似性的度量方法必须满足拓扑学中的度量空间的基本条件：假设d是度量空间M上的度量：d:M*M -> R,其中度量d满足：

非负性：d(x,y) >= 0,当且仅当x=y时取等号；

对称性：d(x,y) = d(y,x)

三角不等式性：d(x,z) <= d(x,y) + d(y,z)

这里主要介绍三种相似性的度量方法，分别为：欧式距离、皮尔逊相关系数和余弦相似度。

欧式距离 略

皮尔逊相关系数
在欧式距离中，不同特征之间的量级对欧氏距离的影响比较大，因此计算欧式距离一般都要将特征值进行归一化。而皮尔逊相关系数的度量方法对量级不敏感，其具体形式为：

其中< X,Y >表示向量X和向量Y的内积，||X||表示向量X的范数。利用皮尔逊相关系数计算。

余弦相似度
余弦相似度是文本相似度度量中使用比较多的一种方法，对于两个向量X和Y，其对应的形式如下：

其对应的余弦相似度为：

3、基于用户的推荐系统

import numpy as np
from math import sqrt

'''导入用户商品数据
input:  file_path(string):用户商品数据存放的文件
output: data(mat):用户商品矩阵
'''
users = {"小明": {"中国合伙人": 5.0, "太平轮": 3.0, "荒野猎人": 4.5, "老炮儿": 5.0, "我的少女时代": 3.0, "肖洛特烦恼": 4.5, "火星救援": 5.0},
         "小红":{"小时代4": 4.0, "荒野猎人": 3.0, "我的少女时代": 5.0, "肖洛特烦恼": 5.0, "火星救援": 3.0, "后会无期": 3.0},
         "小阳": {"小时代4": 2.0, "中国合伙人": 5.0, "我的少女时代": 3.0, "老炮儿": 5.0, "肖洛特烦恼": 4.5, "速度与激情7": 5.0},
         "小四": {"小时代4": 5.0, "中国合伙人": 3.0, "我的少女时代": 4.0, "匆匆那年": 4.0, "速度与激情7": 3.5, "火星救援": 3.5, "后会无期": 4.5},
         "六爷": {"小时代4": 2.0, "中国合伙人": 4.0, "荒野猎人": 4.5, "老炮儿": 5.0, "我的少女时代": 2.0},
         "小李":  {"荒野猎人": 5.0, "盗梦空间": 5.0, "我的少女时代": 3.0, "速度与激情7": 5.0, "蚁人": 4.5, "老炮儿": 4.0, "后会无期": 3.5},
         "隔壁老王": {"荒野猎人": 5.0, "中国合伙人": 4.0, "我的少女时代": 1.0, "Phoenix": 5.0, "甄嬛传": 4.0, "The Strokes": 5.0},
         "邻村小芳": {"小时代4": 4.0, "我的少女时代": 4.5, "匆匆那年": 4.5, "甄嬛传": 2.5, "The Strokes": 3.0}
        }

# 定义几种距离计算函数
# 更高效的方式为得把分向量化之后使用scipy中定义的distance
def euclidean_dis(rating1,rating2):
    """计算2个打分序列间的欧式距离，输入的rating1和rating2都是打分dict
        格式为{"小时代4":1.0,"疯狂动物城":5.0}
    """
    distance = 0
    commonRatings = False
    for key in rating1:
        if key in rating2:
            distance += (rating1[key] - rating2[key])^2
            commonRatings = True
    # 两个打分序列之间公共打分电影
    if commonRatings:
        return distance
    else:
        return -1

def manhattan_dis(rating1,rating2):
    """计算2个打分序列间的曼哈顿距离. 输入的rating1和rating2都是打分dict
       格式为{'小时代4': 1.0, '疯狂动物城': 5.0}"""
    distance = 0
    commonRatings = False
    for key in rating1:
        if key in rating2:
            distance += abs(rating1[key] - rating2[key])
            commonRatings = True
    #两个打分序列之间有公共打分电影
    if commonRatings:
        return distance
    #无公共打分电影
    else:
        return -1

def cos_dis(rating1, rating2):
    """计算2个打分序列间的cos距离. 输入的rating1和rating2都是打分dict
       格式为{'小时代4': 1.0, '疯狂动物城': 5.0}"""
    distance = 0
    dot_product_1 = 0
    dot_product_2 = 0
    commonRatings = False

    for score in rating1.values():
        dot_product_1 += score^2
    for score in rating2.values():
        dot_product_2 += score^2

    for key in rating1:
        if key in rating2:
            distance += rating1[key]*rating2[key]
            commonRatings = True
    #两个打分序列之间有公共打分电影
    if commonRatings:
        return 1-distance/sqrt(dot_product_1*dot_product_2)
    #无公共打分电影
    else:
        return -1

def pearson_dis(rating1,rating2):
    """计算2个打分序列间的pearson距离. 输入的rating1和rating2都是打分dict
       格式为{'小时代4': 1.0, '疯狂动物城': 5.0}"""
    sum_xy = 0
    sum_x = 0
    sum_y = 0
    sum_x2 = 0
    sum_y2 = 0
    n=0

    for key in rating1:
        if key in rating2:
            n += 1
            x = rating1[key]
            y = rating2[key]
            sum_xy += x*y
            sum_x += x
            sum_y += y
            sum_x2 += pow(x,2)
            sum_y2 += pow(y,2)
    # 计算分母
    denominator = sqrt(sum_x2-pow(sum_x,2)/n)*sqrt(sum_y2-pow(sum_y,2)/n)
    if denominator == 0:
        return 0
    else:
        return(sum_xy-(sum_x*sum_y)/n)/denominator

#查找最近邻
def computerNearestNeighor(username,users):
    """在给定username的情况下，计算其他用户和它的距离并排序"""
    distances = []
    for user in users:
        if user != username:
            distance = pearson_dis(users[user],users[username])
            distances.append((distance,user))
    # 根据距离排序，距离越近，排的越靠前
    distances.sort()
    return distances

# 对指定的user推荐电影
def recommend(username,users):
    nearest = computerNearestNeighor(username,users)[0][1]
    print("nearest : ",nearest)

    recommendations = []
    # 找到最近邻看过，但是我们没有看过的电影，计算推荐
    neighorRatings = users[nearest]
    # print("neighorRatings : ",neighorRatings)
    userRatings = users[username]
    # print("userRatings : ",userRatings)
    for artist in neighorRatings:
        if not artist in userRatings:
            recommendations.append((artist,neighorRatings[artist]))
    results = sorted(recommendations,key=lambda artistTuple:artistTuple[1],reverse=True)
    for result in results:
        print(result[0],result[1])

recommend('六爷', users)

nearest :  小红
肖洛特烦恼 5.0
火星救援 3.0
后会无期 3.0

# 简单的张量分解进行打分和推荐
import numpy as np

#手写矩阵分解
#现在有很多很方便对高维矩阵做分解的package，比如libmf, svdfeature等
def matrix_factorization(R,P,Q,K,steps=5000,alpha=0.0002,beta=0.02):
    Q = Q.T
    for