第二章利用用户行为数据

本章节代码来源

实现个性化推荐最理想的情况是用户注册的时候主动告诉我们他喜欢什么，但其缺点有三：

1)NLU技术难以理解用户描述兴趣的自然语言.

2)用户的兴趣不断变化,但用户不会不停地更新兴趣描述.

3)用户不知道自己喜欢什么/很难用语言描述自己喜欢什么.因此,需要算法挖掘用户行为数据进而推荐.

啤酒尿布/购物车分析的例子就说明了用户行为数据蕴含不是那么显而易见的规律,个性化推荐算法的任务就是通过计算机发现这些规律.

基于用户行为分析的推荐算法是个性化推荐系统的重要算法,学术界一般将这种类型的算法称为协同过滤算法.即用户可以不断地与网站互动,使自己的推荐列表能够不断过滤掉自己不感兴趣的物品来满足自己的需求.

2.1 用户行为数据简介

推荐系统会汇总原始日志生成描述用户行为的会话日志.这些日志记录了用户的各种行为,如在电子商务网站中这些行为主要包括网页浏览、点击、评分等.

用户行为在个性化推荐系统中一般分两种（按明确性分）

显性反馈行为：明确表示对物品喜好的行为，如评分、喜欢/不喜欢等
隐性反馈行为：不能明确反应，如页面浏览（浏览不一定是喜欢，可能只是因为在首页）

按反馈的方向分为正反馈（用户行为倾向于喜欢该物品）和负反馈（反之）。

互联网行为有很多种，用统一的方式表示这些所有行为比较困难。一般不同的数据集包含不同的行为.

无上下文信息的隐性反馈数据集每条行为记录包含用户ID,物品ID.数据集Book-Crossing
无上下文信息的显性反馈数据集每条行为记录包含用户ID,物品ID和用户对物品的评分
有上下文信息的隐性反馈数据集每条行为记录包含用户ID,物品ID和用户对物品产生行为的时间戳.数据集Lastfm
有上下文信息的显性反馈数据集每条行为记录包含用户ID,物品ID,评分和时间戳.数据集Netflix Prize提供的就是这种类型的数据集.

本章使用的都是第一种.

2.2 用户行为分析

本节介绍用户行为数据中蕴含的一般规律

2.2.1 用户活跃度和物品流行度的分布

长尾分布——流行度大的物品占物品总数少;活跃度大的用户占用户的比例小

2.2.2 用户活跃度和物品流行度的关系

一般认为新用户倾向于浏览热门物品,而活跃用户会逐渐开始浏览冷门物品.

仅基于用户行为设计的推荐算法一般称为系统过滤算法.协同过滤算法有很多种,如基于邻域的方法(neighborhood-based),隐语义模型(latent factor model),基于图的随机游走算法(random walk on graph)

基于邻域的方法主要包含下面两种算法:

基于用户的协同过滤算法给用户推荐和他兴趣相似的其他用户喜欢的物品
基于物品的协同过滤算法 给用户推荐和他之前喜欢的物品相似的物品

2.3 实验设计和算法评测

2.3.1 数据集

本实验采用GroupLens提供的中等大小版本的MovieLens数据集.

这是一个评分数据集(1~5分),包含6000多用户对4000多部电影的100万条评分.

由于本章研究隐反馈数据集中的TopN推荐问题,因此忽略数据集的评分记录(TopN推荐的任务是预测用户会不会评分,而非预测在其准备评分的前提下评多少分).

2.3.2 实验设计

使用K_Fold分割数据集

文件结构:

├── ml-1m/
    ├── movies.dat     // MovieID::Title::Genres
    ├── ratings.dat    // UserID::MovieID::Rating::Timestamp
    ├── users.dat      // UserID::Gender::Age::Occupation::Zip-code

对数据集进行划分:

本实验使用的是ratings.dat文件,首先对其进行预处理:

import random
import math
import time
from tqdm import tqdm

# 定义装饰器，监控运行时间
def timmer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        res = func(*args, **kwargs)
        stop_time = time.time()
        print('Func %s, run time: %s' % (func.__name__, stop_time - start_time))
        return res
    return wrapper

# 处理数据:
class Dataset():
    
    def __init__(self, fp):
        # fp: data file path
        self.data = self.loadData(fp)
    
    @timmer
    def loadData(self, fp):
        data = []
        for l in open(fp):
            data.append(tuple(map(int, l.strip().split('::')[:2])))
        return data
    
    @timmer
    def splitData(self, M, k, seed=1):
        '''
        :params: data, 加载的所有(user, item)数据条目
        :params: M, 划分的数目，最后需要取M折的平均
        :params: k, 本次是第几次划分，k~[0, M)
        :params: seed, random的种子数，对于不同的k应设置成一样的
        :return: train, test
        '''
        train, test = [], []
        random.seed(seed)
        for user, item in self.data:
            # 这里与书中的不一致，本人认为取M-1较为合理，因randint是左右都覆盖的
            if random.randint(0, M-1) == k:  
                test.append((user, item))
            else:
                train.append((user, item))

        # 处理成字典的形式，user->set(items)
        def convert_dict(data):
            data_dict = {}
            for user, item in data:
                if user not in data_dict:
                    data_dict[user] = set()
                data_dict[user].add(item)
            data_dict = {k: list(data_dict[k]) for k in data_dict}
            return data_dict

        return convert_dict(train), convert_dict(test)

每次实验选取不同的$k(0\leq k\leq M-1)$和相同的seed，由于相同的seed产生的随机数序列一样，且范围在$0\sim M-1$，当选取不同的$k$时,得到的test也不同,且test和$k$一一对应,因此能得到$M$个训练/测试集.

这样做是为了防止某次实验过拟合.

经上述步骤处理后数据格式如下,表示用户ID1看过的电影为ID608,ID3114,ID1246.用户ID2看过的是ID1537和ID2628.

1	`{1: [608, 3114, 1246], 2: [1537, 2628]}`

2.3.3 评测指标

对用户$u$推荐$N$个物品(记为$R(U)$),令该用户在测试集上喜欢的物品集合为$T(U)$,可通过$precision$和$recall$评测算法精度:

召回率:label中的评分记录有多少在预测的推荐列表中,因此分母是label中的正样本数.
准确率:预测的推荐列表中有多少是发生过的评分记录

e.g.$+$表示label/predict中用户喜欢的物品

此例有:

$|U|=1(用户总数),N=7(推荐列表长度,在这里假设label长度也是7)$,

$R(U)\cap T(U)=4,R(U)=7,T(U)=5$

$\Rightarrow recall=\frac{\sum_{u\in U}|R(U)\cap T(U)|}{\sum_{u\in U}T(U)}=\frac{4}{5},precision=\frac{\sum_{u\in U}|R(U)\cap T(U|}{\sum_{u\in U}R(U)}=\frac{4}{7}$

再次强调,该实验的目的是预测用户会不会评分

覆盖率$Coverage=\frac{\cup_{u\in U}\ R(u)}{|I|}$
新颖度,在这里使用平均流行度度量推荐结果的新颖度,平均流行度越高,新颖度越低.

由于物品流行度分布满足长尾分布,因此在计算平均流行度时对每个物品的流行度取对数,使流行度平均值更加稳定.

class Metric():
    
    def __init__(self, train, test, GetRecommendation):
        '''
        :params: train, 训练数据
        :params: test, 测试数据
        :params: GetRecommendation, 为某个用户获取推荐物品的接口函数
        '''
        self.train = train
        self.test = test
        self.GetRecommendation = GetRecommendation
        self.recs = self.getRec()
        
    # 为test中的每个用户进行推荐
    def getRec(self):
        recs = {}
        for user in self.test:
            rank = self.GetRecommendation(user)
            recs[user] = rank
        return recs
        
    # 定义精确率指标计算方式
    def precision(self):
        all, hit = 0, 0
        for user in self.test:
            test_items = set(self.test[user])
            rank = self.recs[user]
            for item, score in rank:
                if item in test_items:
                    hit += 1
            all += len(rank)
        return round(hit / all * 100, 2)
    
    # 定义召回率指标计算方式
    def recall(self):
        all, hit = 0, 0
        for user in self.test:
            test_items = set(self.test[user])
            rank = self.recs[user]
            for item, score in rank:
                if item in test_items:
                    hit += 1
            all += len(test_items)
        return round(hit / all * 100, 2)
    
    # 定义覆盖率指标计算方式
    def coverage(self):
        all_item, recom_item = set(), set()
        for user in self.test:
            for item in self.train[user]:
                all_item.add(item)
            rank = self.recs[user]
            for item, score in rank:
                recom_item.add(item)
        return round(len(recom_item) / len(all_item) * 100, 2)
    
    # 定义新颖度指标计算方式
    def popularity(self):
        # 计算物品的流行度
        item_pop = {}
        for user in self.train:
            for item in self.train[user]:
                if item not in item_pop:
                    item_pop[item] = 0
                item_pop[item] += 1

        num, pop = 0, 0
        for user in self.test:
            rank = self.recs[user]
            for item, score in rank:
                # 取对数，防止因长尾问题带来的被流行物品所主导
                pop += math.log(1 + item_pop[item])
                num += 1
        return round(pop / num, 6)
    
    def eval(self):
        metric = {'Precision': self.precision(),
                  'Recall': self.recall(),
                  'Coverage': self.coverage(),
                  'Popularity': self.popularity()}
        print('Metric:', metric)
        return metric

2.4 基于邻域的算法

分为两种,基于用户的协同过滤算法和基于物品的协同过滤算法

2.4.1 基于用户的协同过滤算法(UserCF)

1. 基础算法

两个步骤:

找到和目标用户兴趣相似的用户集合
找到这个集合中用户喜欢的,且目标用户没听说过的物品推荐给目标用户

步骤1的关键是计算两个用户的兴趣相似度,而协同算法主要利用行为的相似度计算兴趣的相似度.令$N(u)$表示用户$u$曾经有过正反馈的物品集合,$N(v)$为用户$v$曾经有过正反馈的物品集合.两者的用户相似度可通过下面的$Jaccard$公式计算:
$$
w_{uv}=\frac{|N(u)\cap N(v)|}{|N(u)||N(v)|}
$$
也可通过余弦相似度计算:
$$
w_{uv}=\frac{|N(u)\cap N(v)|}{\sqrt{|N(u)||N(v)|}}
$$

def UserSimilarity(train):
    W=dict()
    for u in train.keys():
        for v in train.keys():
            if u==v:
                continue
            W[u][v]=len(train[u]&train[v])
            W[u][v]/=math.sqrt(len(train[u])*len(train[v])*1.0)
    return W

这种计算相似度矩阵的方法时间复杂度为$O(|U|*|U|)$,然而大多数用户之间并没有共同购买的商品,即$|N(u)\cap N(v)|=0$,这会加长计算时间.

下面这种计算相似度的算法首先建立物品到用户的倒查表,对于每个物品,保存对该物品产生过行为的用户列表.然后建立矩阵$C_{|U|\times |V|}$.该矩阵的每个元素代表两个用户间共同交互物品的个数,即$|N(u)\cap N(v)|$,可以先计算出$|N(u)\cap N(v)|\neq 0$的用户对$(u,v)$,然后再对这种情况除以$\sqrt{|N(u)||N(v)|}$.

如上图,对于物品$a$,用户$A,B$都对其产生过行为,因此将$C[A][B]$和$C[B][A]$加1,以此类推.得到完整的$C$后,除以分母得到$W$.

得到用户间相似度矩阵$W$后,$\ UserCF$算法会给用户推荐和他兴趣最相似的$K$个用户喜欢的物品,用户$u$对物品$i$的感兴趣程度为:
$$
p(u,i)=\sum_{v\in S(u,k)\cap N(i)}w_{uv}r_{vi}
$$
$S(u,k)$:与用户$u$兴趣最相似的$k$个人; $N(i)$:对物品$i$感兴趣的用户集合

$w_{uv}$:$u,v$两个用户的兴趣相似度; $r_{vi}$:用户$v$对物品$i$的感兴趣程度

因此,由上图可得:$\quad p(A,c)=w_{AB}+w_{AD}=0.7416\qquad p(A,e)=w_{AC}+w_{AD}=0.7416$

$UserCF$推荐算法的实现:

# 3. 基于用户余弦相似度的推荐
def UserCF(train, K, N):
    '''
    :params: train, 训练数据集
    :params: K, 超参数，设置取TopK相似用户数目
    :params: N, 超参数，设置取TopN推荐物品数目
    :return: GetRecommendation, 推荐接口函数
    '''
    # 计算item->user的倒排索引
    item_users = {}
    for user in train:
        for item in train[user]:
            if item not in item_users:
                item_users[item] = []
            item_users[item].append(user)
    
    # 计算用户相似度矩阵
    sim = {}
    num = {}
    for item in item_users:
        users = item_users[item]
        for i in range(len(users)):
            u = users[i]
            if u not in num:
                num[u] = 0
            num[u] += 1
            if u not in sim:
                sim[u] = {}
            for j in range(len(users)):
                if j == i: continue
                v = users[j]
                if v not in sim[u]:
                    sim[u][v] = 0
                sim[u][v] += 1
    for u in sim:
        for v in sim[u]:
            sim[u][v] /= math.sqrt(num[u] * num[v])
    
    # 按照相似度排序
    sorted_user_sim = {k: list(sorted(v.items(), \
                               key=lambda x: x[1], reverse=True)) \
                       for k, v in sim.items()}
    
    # 获取接口函数
    def GetRecommendation(user):
        items = {}
        seen_items = set(train[user])
        for u, _ in sorted_user_sim[user][:K]:
            for item in train[u]:
                # 要去掉用户见过的
                if item not in seen_items:
                    if item not in items:
                        items[item] = 0
                    items[item] += sim[user][u]
        recs = list(sorted(items.items(), key=lambda x: x[1], reverse=True))[:N]
        return recs
    
    return GetRecommendation

从$UserCF$的实验结果可得出以下结论:

RS的精度指标$recall,precision$与$K$不是线性关系
$K$越大,推荐结果越热门(因为参考了更多人的意见)
$K$越大,覆盖率越低

2. 用户相似度计算的改进

两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度（如果两个人都购买了《新华字典》，很难不能说明他们兴趣相似）。

$John\ S.\ Breese$提出:
$$
w_{uv}=\frac{\sum_{i\in N(u)\cap N(v)}\frac{1}{log(1+|N(i)|)}}{\sqrt {|N(u)||N|v||}}
$$
即通过$\frac{1}{log1+|N(i)|}$惩罚用户$u$和$v$共同兴趣列表中热门物品对他们相似度的影响.

将其称为$User-IIF$算法:

# 4. 基于改进的用户余弦相似度的推荐
def UserIIF(train, K, N):
    '''
    :params: train, 训练数据集
    :params: K, 超参数，设置取TopK相似用户数目
    :params: N, 超参数，设置取TopN推荐物品数目
    :return: GetRecommendation, 推荐接口函数
    '''
    # 计算item->user的倒排索引 ...
    # 计算用户相似度矩阵
    sim = {}
    num = {}
    for item in item_users:
        users = item_users[item]
        for i in range(len(users)):
            u = users[i]
            if u not in num:
                num[u] = 0
            num[u] += 1
            if u not in sim:
                sim[u] = {}
            for j in range(len(users)):
                if j == i: continue
                v = users[j]
                if v not in sim[u]:
                    sim[u][v] = 0
                # 相比UserCF，主要是改进了这里
                sim[u][v] += 1 / math.log(1 + len(users))
    for u in sim:
        for v in sim[u]:
            sim[u][v] /= math.sqrt(num[u] * num[v])
    
    # 按照相似度排序 ...
    # 获取接口函数 ...
    return GetRecommendation

class Experiment():
    
    def __init__(self, M, K, N, fp='../dataset/ml-1m/ratings.dat', rt='UserCF'):
        '''
        :params: M, 进行多少次实验
        :params: K, TopK相似用户的个数
        :params: N, TopN推荐物品的个数
        :params: fp, 数据文件路径
        :params: rt, 推荐算法类型
        '''
        self.M = M
        self.K = K
        self.N = N
        self.fp = fp
        self.rt = rt
        self.alg = {'Random': Random, 'MostPopular': MostPopular, \
                    'UserCF': UserCF, 'UserIIF': UserIIF}
    
    # 定义单次实验
    @timmer
    def worker(self, train, test):
        '''
        :params: train, 训练数据集
        :params: test, 测试数据集
        :return: 各指标的值
        '''
        getRecommendation = self.alg[self.rt](train, self.K, self.N)
        metric = Metric(train, test, getRecommendation)
        return metric.eval()
    
    # 多次实验取平均
    @timmer
    def run(self):
        metrics = {'Precision': 0, 'Recall': 0, 
                   'Coverage': 0, 'Popularity': 0}
        dataset = Dataset(self.fp)
        for ii in range(self.M):
            train, test = dataset.splitData(self.M, ii)
            print('Experiment {}:'.format(ii))
            metric = self.worker(train, test)
            metrics = {k: metrics[k]+metric[k] for k in metrics}
        metrics = {k: metrics[k] / self.M for k in metrics}
        print('Average Result (M={}, K={}, N={}): {}'.format(\
                              self.M, self.K, self.N, metrics))

# 1. random实验
M, N = 8, 10
K = 0 # 为保持一致而设置，随便填一个值
random_exp = Experiment(M, K, N, rt='Random')
random_exp.run()
# 2. MostPopular实验
M, N = 8, 10
K = 0 # 为保持一致而设置，随便填一个值
mp_exp = Experiment(M, K, N, rt='MostPopular')
mp_exp.run()
# 3. UserCF实验
M, N = 8, 10
for K in [5, 10, 20, 40, 80, 160]:
    cf_exp = Experiment(M, K, N, rt='UserCF')
    cf_exp.run()
# 4. UserIIF实验
M, N = 8, 10
K = 80 # 与书中保持一致
iif_exp = Experiment(M, K, N, rt='UserIIF')
iif_exp.run()

关于实验的总结

数据集分割的小技巧，用同样的seed
各个指标的实现，要注意
为每个用户推荐的时候是推荐他们****没有见过****的，因为测试集里面是这样的
倒排物品-用户索引，可进行时间优化
推荐的时候K和N各代表什么意思，要分开设置，先取TopK，然后取TopN

$UserCF$存在的问题,随着网站的用户数增加,计算用户兴趣矩阵越来越困难,其运算空间复杂度和时间复杂度和用户数的增长近似于平方关系.其次,这种方法很难对推荐结果做出解释.

2.4.2 基于物品的系统过滤算法(ItemCF)

目前业界应用最多的算法

1. 基础算法

$ItemCF$给用户推荐那些和他们之前喜欢的物品相似的物品.但该算法并不利用物品的内容属性计算物品间的相似度,而是通过分析用户的行为记录来计算物品间的相似度.该算法认为,物品$A$和$B$具有很大的相似度是因为喜欢物品$A$的用户大都也喜欢物品$B$.

同时该算法可以给推荐结果提供一个合理的解释,例如给用户推荐《深度学习》是因为该用户之前浏览过《机器学习》.

$ItemCF$算法主要分两步:

计算物品间的相似度
利用物品间的相似度和用户的历史行为给用户生成推荐列表

物品相似度的定义:

我们购物时常能看到”购买了该商品的用户也经常购买的其他物品”,实际上,物品的相似度定义也是如此,喜欢$i$的人中有多少喜欢$j$:
$$
w_{ij}=\frac{|N(i)\cap N(j)|}{|N(i)|}
$$
$|N(i)|$是喜欢物品$i$的用户数,$|N(i)\cap N(j)|$是同时喜欢物品$i$和$j$的用户数.

存在的问题:当$j$是热门商品时,$w_{ij}$接近1，即热门商品$j$和任意的商品$i$相似性都很高,会影响RS挖掘长尾信息.为了避免推荐出热门商品.可用下面的公式.
$$
w_{ij}=\frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}}
$$
这个公式惩罚了物品$j$的权重,减轻了热门物品会和很多物品相似的可能性.

从上面的定义可以看到，在协同过滤中两个物品产生相似度是因为它们共同被很多用户喜欢，也就是说每个用户都可以通过他们的历史兴趣列表给物品“贡献”相似度。这里面蕴涵着一个假设，就是每个用户的兴趣都局限在某几个方面，因此如果两个物品属于一个用户的兴趣列表，那么这两个物品可能就属于有限的几个领域，而如果两个物品属于很多用户的兴趣列表，那么它们就可能属于同一个领域，因而有很大的相似度.

得到相似度后,通过以下公式计算用户$u$对一个物品$j$的兴趣:
$$
p_{uj}=\sum_{i\in N(u)\cap S(j,k)}w_{ji}r_{ui}
$$
$r_{ui}$是用户对物品$i$的兴趣,$w_{ji}$是物品$j$与物品$i$的相似度.$N(u)$为用户$u$喜欢的物品集合,$S(j,k)$是与物品$j$最相似的$k$个物品

e.g.

# 1. 基于物品余弦相似度的推荐
def ItemCF(train, K, N):
    '''
    :params: train, 训练数据集
    :params: K, 超参数，设置取TopK相似物品数目
    :params: N, 超参数，设置取TopN推荐物品数目
    :return: GetRecommendation, 推荐接口函数
    '''
    # 计算物品相似度矩阵
    sim = {}
    num = {}
    for user in train:
        items = train[user]
        for i in range(len(items)):
            u = items[i]
            if u not in num:
                num[u] = 0
            num[u] += 1
            if u not in sim:
                sim[u] = {}
            for j in range(len(items)):
                if j == i: continue
                v = items[j]
                if v not in sim[u]:
                    sim[u][v] = 0
                sim[u][v] += 1
    for u in sim:
        for v in sim[u]:
            sim[u][v] /= math.sqrt(num[u] * num[v])
    
    # 按照相似度排序
    sorted_item_sim = {k: list(sorted(v.items(), \
                               key=lambda x: x[1], reverse=True)) \
                       for k, v in sim.items()}
    
    # 获取接口函数
    def GetRecommendation(user):
        items = {}
        seen_items = set(train[user])
        for item in train[user]:
            for u, _ in sorted_item_sim[item][:K]:
                if u not in seen_items:
                    if u not in items:
                        items[u] = 0
                    items[u] += sim[item][u]
        recs = list(sorted(items.items(), key=lambda x: x[1], reverse=True))[:N]
        return recs
    
    return GetRecommendation

实验结果显示:

精度(准确率和召回率)$\quad ItemCF$推荐结果的精度与$K$不呈正相关或负相关
流行度$\quad$和$UserCF$不同,$k$对流行度的影响不是正相关的
覆盖率$\quad K$会降低系统的覆盖率

2. 用户活跃度对物品相似度的影响

假设一个开书店的人买了当当网上80%的书,意味着由于这么一个用户,有80%的书两两之间产生了相似度,也就是说内存里会产生一个很大的稠密矩阵.除此之外.该用户买这些书并非出于自身的兴趣,而且这些书覆盖了很多领域,因此该用户对于他所购买的书的两两相似度的贡献应该远远小于只买了十几本自己喜欢的书的人.

依旧是$John\ S.\ Breese$提出了$IUF(Inverse\ User\ Frequence)$,即用户活跃度对数的倒数的参数,此时活跃用户对物品相似度的贡献应该小于不活跃的用户.$N(\ast)$表示用户$\ast$有兴趣的物品集合.
$$
w_{ij}=\frac{\sum_{u\in N(i)\cap N(j)}\frac{1}{log(1+|N(u)|)}}{\sqrt {|N(i)||N(j)|}}
$$

# 只需要把上面的sim[u][v] += 1改为
def ItemIUF(train, K, N):
    # ...
	sim[u][v] += 1 / math.log(1 + len(items))
    # ...

在实际计算中,为了避免相似矩阵过于稠密,一般直接忽略该兴趣列表.

将这种算法记为$ItemCF-IUF$,实验结果显示它和$ItemCF$的精度类似,但提高了覆盖率,降低了准确度.

3. 物品相似度的归一化

将$ItemCF$的相似度矩阵按最大值归一化能够提高推荐的准确率,覆盖率和多样性.
$$
w_{ij}’=\frac{w_{ij}}{\mathop{max}\limits_{j}\ w_{ij}}
$$

# 3. 基于归一化的物品余弦相似度的推荐
def ItemCF_Norm(train, K, N):
    '''
    :params: train, 训练数据集
    :params: K, 超参数，设置取TopK相似物品数目
    :params: N, 超参数，设置取TopN推荐物品数目
    :return: GetRecommendation, 推荐接口函数
    '''
    # 计算物品相似度矩阵...    
    # 对相似度矩阵进行按行归一化
    for u in sim:
        s = 0
        for v in sim[u]:
            s += sim[u][v]
        if s > 0:
            for v in sim[u]:
                sim[u][v] /= s
    
    # 按照相似度排序 ...
    # 获取接口函数 ...
    return GetRecommendation

# 1. ItemCF实验
M, N = 8, 10
for K in [5, 10, 20, 40, 80, 160]:
    cf_exp = Experiment(M, K, N, rt='ItemCF')
    cf_exp.run()
# 2. ItemIUF实验
M, N = 8, 10
K = 10 # 与书中保持一致
iuf_exp = Experiment(M, K, N, rt='ItemIUF')
iuf_exp.run()
# 3. ItemCF-Norm实验
M, N = 8, 10
K = 10 # 与书中保持一致
norm_exp = Experiment(M, K, N, rt='ItemCF-Norm')
norm_exp.run()

一般来说，物品总是属于很多不同的类，每一类中的物品联系比较紧密。假设在一个电影网站中，有两种电影——纪录片和动画片。那么，ItemCF算出来的相似度一般是纪录片和纪录片的相似度或者动画片和动画片的相似度大于纪录片和动画片的相似度。但是纪录片之间的相似度和动画片之间的相似度却不一定相同。假设物品分为两类——A和B，A类物品之间的相似度为0.5，B类物品之间的相似度为0.6，而A类物品和B类物品之间的相似度是0.2。在这种情况下，如果一个用户喜欢了5个A类物品和5个B类物品，用ItemCF给他进行推荐，推荐的就都是B类物品，因为B类物品之间的相似度大。但如果归一化之后，A类物品之间的相似度变成了1，B类物品之间的相似度也是1，那么这种情况下，用户如果喜欢5个A类物品和5个B类物品，那么他的推荐列表中A类物品和B类物品的数目也应该是大致相等的。从这个例子可以看出，相似度的归一化可以提高推荐的多样性。

那么，对于两个不同的类，什么样的类其类内物品之间的相似度高或者低?

一般来说，热门的类其类内物品相似度一般比较大。如果不进行归一化，就会推荐比较热门的类里面的物品，而这些物品也是比较热门的。因此，推荐的覆盖率就比较低。相反，如果进行相似度的归一化，则可以提高推荐系统的覆盖率。

实验结果显示归一化提高了ItemCF的各项指标。

2.4.3 UserCF和ItemCF的比较

$UserCF$是推荐系统领域较为古老的算法，1992年就已经在电子邮件的个性化推荐系统Tapestry中得到了应用，1994年被GroupLens用来实现新闻的个性化推荐，后来被著名的文章分享网站Digg用来给用户推荐个性化的网络文章。ltemCF则是相对比较新的算法，在著名的电子商务网站亚马逊和DVD租赁网站Netflix中得到了广泛应用。为什么Digg使用UserCF，而亚马逊网使用ltemCF呢？
首先回顾一下UserCF算法和ItemCF算法的推荐原理。UserCF给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品，而ItemCF给用户推荐那些和他之前喜欢的物品类似的物品。从这个算法的原理可以看到，UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点，而ItemCF的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反映了用户所在的小型兴趣群体中物品的热门程度，而ltemCF的推荐更加个性化，反映了用户自己的兴趣传承。

在新闻网站中，用户的兴趣不是特别细化，绝大多数用户都喜欢看热门的新闻。即使是个性化，也是比较粗粒度的，比如有些用户喜欢体育新闻，有些喜欢社会新闻，而特别细粒度的个性化一般是不存在的。比方说，很少有用户只看某个话题的新闻，主要是因为这个话题不可能保证每天都有新的消息，而这个用户却是每天都要看新闻的。因此，个性化新闻推荐更加强调抓住新闻热点，热门程度和时效性是个性化新闻推荐的重点，而个性化相对于这两点略显次要。因此，UserCF可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻，这样在抓住热点和时效性的同时，保证了一定程度的个性化。这是Digg在新闻推荐中使用UserCF的最重要原因。

UserCF适合用于新闻推荐的另一个原因是从技术角度考量的。因为作为一种物品，新闻的更新非常快，每时每刻都有新内容出现，而ltemCF需要维护一张物品相关度的表，如果物品更新很快，那么这张表也需要很快更新，这在技术上很难实现。绝大多数物品相关度表都只能做到一天一次更新，这在新闻领域是不可以接受的。而UserCF只需要用户相似性表，虽然UserCF对于新用户也需要更新相似度表，但在新闻网站中，物品的更新速度远远快于新用户的加入速度，而且对于新用户，完全可以给他推荐最热门的新闻，因此UserCF显然是利大于弊。

但是，在图书、电子商务和电影网站，比如亚马逊、豆瓣、Netflix中，ItemCF则能极大地发挥优势。首先，在这些网站中，用户的兴趣是比较固定和持久的。一个技术人员可能都是在购买技术方面的书，而且他们对书的热门程度并不是那么敏感，事实上越是资深的技术人员，他们看的书就越可能不热门。此外，这些系统中的用户大都不太需要流行度来辅助他们判断一个物品的好坏，而是可以通过自己熟悉领域的知识自己判断物品的质量。因此，这些网站中个性化推荐的任务是帮助用户发现和他研究领域相关的物品。因此，ItemCF算法成为了这些网站的首选算法。

此外，这些网站的物品更新速度不会特别快，一天一次更新物品相似度矩阵对它们来说不会造成太大的损失，是可以接受的。

同时，从技术上考虑，UserCF需要维护一个用户相似度的矩阵，而ItemCF需要维护一个物品相似度矩阵。从存储的角度说，如果用户很多，那么维护用户兴趣相似度矩阵需要很大的空间，同理，如果物品很多，那么维护物品相似度矩阵代价较大。

在早期的研究中，大部分研究人员都是让少量的用户对大量的物品进行评价，然后研究用户兴趣的模式。那么，对于他们来说，因为用户很少，计算用户兴趣相似度是最快也是最简单的方法。但在实际的互联网中，用户数目往往非常庞大，而在图书、电子商务网站中，物品的数目则是比较少的。此外，物品的相似度相对于用户的兴趣一般比较稳定，因此使用ltemCF是比较好的选择。当然，新闻网站是个例外，在那儿，物品的相似度变化很快，物品数目庞大，相反用户兴趣则相对固定（都是喜欢看热门的），所以新闻网站的个性化推荐使用UserCF算法的更多。

该实验结果显示:$ItemCF$算法的覆盖率和新颖度没$UserCF$高,下一节会介绍如何对前者进行改进.

需要指出的是，离线实验的性能在选择推荐算法时并不起决定作用。首先应该满足产品的需求，比如如果需要提供推荐解释，那么可能得选择$ltemCF$算法。其次，需要看实现代价，比如若用户太多，很难计算用户相似度矩阵，这个时候可能不得不抛弃$UserCF$算法。最后，离线指标和点击率等在线指标不一定成正比。而且，这里对比的是最原始的$UserCF$和$ItemCF$算法，这两种算法都可以进行各种各样的改进。一般来说，这两种算法经过优化后，最终得到的离线性能是近似的。

哈利波特问题(原始$ItemCF$算法的局限性)

亚马逊网的研究人员在设计ItemCF算法之初发现ltemCF算法计算出的图书相关表存在一个问题，就是很多书都和《哈利波特》相关。也就是说，购买任何一本书的人似乎都会购买《哈利波特》。后来他们研究发现，主要是因为《哈利波特》太热门了，确实是购买任何一本书的人几乎都会购买它。

回顾:$ItemCF$之前采用的相似度计算公式尽管考虑到了$j$是热门商品会导致的问题,但在实际应用中,$j$依然会活得比较大的相似度.
$$
w_{ij}=\frac{|N(i)\cap N(j)|}{\sqrt{|N(i)||N(j)|}}
$$
解决方案1:
$$
w_{ij}=\frac{|N(i)\cap N(j)|}{|N(i)|^{1-\alpha}|N(j)|^\alpha} \qquad \alpha\in [0.5,1]
$$
通过提高$\alpha$,京可以惩罚热门的$j$,如果$\alpha=0.5$就是标准的ItemCF算法.

离线实验结果显示，$\alpha=0.5$时才会导致最高的准确率和召回率，而无论$\alpha<0.5$或者$\alpha>0.5$都不会带来这两个指标的提高。但是，$\alpha$越大，覆盖率就越高，并且结果的平均热门程度会降低。因此，通过这种方法可以在适当牺牲准确率和召回率的情况下显著提升结果的覆盖率和新颖性(降低流行度即提高了新颖性).

解决方案2:

不过，上述方法还不能彻底地解决哈利波特问题。每个用户一般都会在不同的领域喜欢一种物品。以电视为例，看新闻联播是父辈每天的必修课，他们每天基本就看新闻联播，而且每天不看别的新闻，就看这一种新闻。此外，他们很多都是电视剧迷，都会看央视一套8点的电视剧。那么，最终结果就是黄金时间的电视剧都和新闻联播相似，而新闻联播和其他新闻的相似度很低。
上面的问题换句话说就是，两个不同领域的最热门物品之间往往具有比较高的相似度。这个时候，仅仅靠用户行为数据是不能解决这个问题的，因为用户的行为表示这种物品之间应该相似度很高。此时，我们只能依靠引入物品的内容数据解决这个问题，比如对不同领域的物品降低权重等。这些就不是协同过滤讨论的范畴了。

2.5 隐语义模型

LFM(latent factor model)隐语义模型最早在文本挖掘领域被提出,用于找到文本的隐含语义.

2.5.1 基础算法

细节可以看这篇文章

核心思想是通过隐含特征(latent factor)联系用户兴趣和物品.与$UserCF$和$ItemCF$不同,这种方法不依赖于共同评分矩阵,他将用户和物品分别映射到某种真实含义未知的特征向量(也就是说向量每个维度的意义并不能人为给定).在预测时,对于任意一个空白评分的位置,就能通过两个向量的内积进行计算.

LFM通过下式计算用户$u$对物品$i$的兴趣:
$$
Preference(u,i)=r_{ui}=p_u^Tq_i=\sum_{k=1}^Kp_{u,k}\ q_{i,k}
$$
$p_{u,k}\ q_{i,k}$是模型的参数,前者度量了用户$u$的兴趣和第$k$个隐类的关系,而$q_{i,k}$度量了第$k$个隐类和物品$i$之间的关系.

这两个参数的计算需要学习一个训练集才能得到,而且这个训练集需要包含用户喜欢和不喜欢的物品.由于本章主要讨论的是隐性反馈数据集,因此需要生成负样本.

负样本采样一般需要遵循以下原则:

对每个用户,要保证正负样本的均衡
对每个用户采样负样本时,要选取那些很热门,而用户却没有行为的物品

一般认为,很热门而用户却没有行为更能说明用户对该商品不感兴趣.因为对于冷门的物品,用户可能没发现,所以谈不上是否感兴趣.

经过采样可以得到一个用户-物品集$K={ (u,i)}$,其中如果$(u,i)$是正样本,则有$r_{ui}=1$,否则$r_{ui}=0$,然后需要优化以下损失函数来找到最合适的参数$p$和$q$.
$$
C=\sum_{(u,i)\in K}(r_{ui}-\hat r_{ui})^2=\sum_{(u,i)\in K}\Big(r_{ui}-p_u^T\ q_i\Big)^2+\lambda\Vert p_u \Vert^2+\lambda\Vert q_i \Vert^2
$$
$\lambda\Vert q_i \Vert^2$是用来防止过拟合的正则化项,$\ \lambda$可通过实验获得.
$$
\frac{\partial C}{\partial p_u}=-2(r_{ui}-p_u^Tq_i)q_i+2\lambda p_u\
\frac{\partial C}{\partial q_i}=-2(r_{ui}-p_u^Tq_i)p_u+2\lambda q_i\
$$
更新参数：
$$
p_{u}=p_{u}+\alpha((r_{ui}-p_u^Tq_i)q_i-\lambda p_u)\
q_{i}=q_{i}+\alpha((r_{ui}-p_u^Tq_i)p_u-\lambda q_i)
$$

$\alpha$是学习率,为超参数,通过反复实验获得.

1 2	`import numpy as np from tqdm import tqdm, trange`

def LFM(train, ratio, K, lr, step, lmbda, N):
    '''
    :params: train, 训练数据
    :params: ratio, 负采样的正负比例
    :params: K, 隐语义个数
    :params: lr, 初始学习率
    :params: step, 迭代次数
    :params: lmbda, 正则化系数
    :params: N, 推荐TopN物品的个数
    :return: GetRecommendation, 获取推荐结果的接口
    '''
    
    all_items = {}
    for user in train:
        for item in train[user]:
            if item not in all_items:
                all_items[item] = 0
            all_items[item] += 1
    all_items = list(all_items.items())
    items = [x[0] for x in all_items]
    pops = [x[1] for x in all_items]
    
    # 负采样函数(注意！！！要按照流行度进行采样)
    def nSample(data, ratio):
        new_data = {}
        # 正样本
        for user in data:
            if user not in new_data:
                new_data[user] = {}
            for item in data[user]:
                new_data[user][item] = 1
        # 负样本
        for user in new_data:
            seen = set(new_data[user])
            pos_num = len(seen)
            item = np.random.choice(items, int(pos_num * ratio * 3), pops)
            item = [x for x in item if x not in seen][:int(pos_num * ratio)]
            new_data[user].update({x: 0 for x in item})
        
        return new_data
                
    # 训练
    P, Q = {}, {}
    for user in train:
        P[user] = np.random.random(K)
    for item in items:
        Q[item] = np.random.random(K)
            
    for s in trange(step):
        data = nSample(train, ratio)
        for user in data:
            for item in data[user]:
                eui = data[user][item] - (P[user] * Q[item]).sum()
                P[user] += lr * (Q[item] * eui - lmbda * P[user])
                Q[item] += lr * (P[user] * eui - lmbda * Q[item])
        lr *= 0.9 # 调整学习率
        
    # 获取接口函数
    def GetRecommendation(user):
        seen_items = set(train[user])
        recs = {}
        for item in items:
            if item not in seen_items:
                recs[item] = (P[user] * Q[item]).sum()
        recs = list(sorted(recs.items(), key=lambda x: x[1], reverse=True))[:N]
        return recs
    
    return GetRecommendation

# LFM实验(运行时间较长)
M, N = 8, 10
for r in [1, 2, 3, 5, 10, 20]:
    exp = Experiment(M, N, ratio=r)
    exp.run()

在LFM中,重要的参数有4个:

隐特征的个数：$F$
学习率：$\alpha$
正则化参数：$\lambda$
负样本/正样本比例：$ratio$

在该实验中,$ratio>10$以后,精度就比较稳定.同时随着负样本数目的增加,覆盖率不断降低,流行度升高.说明该参数控制了推荐算法挖掘长尾的能力.

当数据非常稀疏时,$LFM$性能会明显下降,甚至低于$UserCF$和$ItemCF$.

2.5.2 基于LFM实际系统的例子

Yahoo的研究人员以CTR为优化目标,利用LFM来预测用户是否会单机一个链接,他们将用户历史上对首页上链接的行为记录在作为训练集.

在新闻推荐中,冷启动问题问题很明显.每天都有大量新新闻,在很短的时间内得到和失去人们的关注.因此实时性很重要.

但LFM模型在实际使用中很难实现实时的推荐.经典的LFM模型每次训练都需要扫描所有的用户行为记录才能计算出用户隐类向量$p_u$和物品引隐类向量$q_i$,此外,训练也比较费时.实际中往往是一天训练一次.因此不能实时地调整推荐结果来满足用户最近的行为.

他们的解决方案分为两部分
$$
r_{ui}=x_u^T\cdot y_i+p_u^T\cdot q_i
$$
用户向量$x_u$可以根据历史行为获得,每天只需计算一次.$y_i$根据物品的内容属性直接生成.$p_u$和$q_i$是根据实时拿到的用户最近几小时的行为训练LFM获得的.

因此对于一个新加入的物品$i$,可以通过$x_u^T\cdot y_i$估计用户$u$对物品$i$的兴趣,经过几小时后,就能通过$p_u^T\cdot q_i$得到更准确的预测值.

2.5.3 LFM和基于邻域的方法的比较

理论基础 LFM有比较好的理论基础,通过优化设定目标建立最优模型;基于邻域的方法是一种基于统计的方法
离线计算的空间复杂度 假设有$M$个用户和$N$个物品.在计算相关表的过程中可能会获得一张比较稠密的临时相关表,例如用户相关表$O(M \ast M)$或物品相关表$O(N\ast N)$,但$LFM$在建模过程中如果是$F$个隐类,那么需要的存储空间是$O(F\ast (M+N))$.
离线计算的时间复杂度 假设有$M$个用户,$N$个物品,$K$条用户对物品的行为记录.$UserCF$的时间复杂度为$O(N\ast (K/N)^2)$,$ItemCF$的时间复杂度为$O(M\ast (K/M)^2)$.$LFM$如果用$F$个隐类,迭代$S$次,复杂度为$O(K\ast F\ast S)$一般情况下$LFM$会稍高一点,但无本质区别.
在线实时推荐 $UserCF$和$ltemCF$在线服务算法需要将相关表缓存在内存中，然后可以在线进行实时的预测.$LFM$不能进行在线实时推荐，也就是说，当用户有了新的行为后，他的推荐列表不会发生变化。
推荐解释 $ltemCF$算法支持很好的推荐解释，它可以利用用户的历史行为解释推荐结果。但LFM无法提供这样的解释，它计算出的隐类虽然在语义上确实代表了一类兴趣和物品，却很难用自然语言描述并生成解释展现给用户。

2.6 基于图的模型

用户行为很容易用二分图表示,因此很多图的算法都可以用到推荐系统中

2.6.1 用户行为数据的二分图表示

令$G(V,E)$表示用户物品二分图,$V=V_U\cup V_I$由用户顶点集合$V_U$和物品顶点集合$V_I$组成.对于数据集每一个二元组$(u,i)$,图中都有一套对应的边$e(v_u,v_i)$.图2-18是一个用户物品二分图模型,圆形节点代表用户,方形代表物品,边表示用户对物品的行为.

2.6.2 基于图的推荐算法

此时给用户$u$推荐物品的任务可以转化为度量用户顶点$v_u$和与$v_u$没有边直接相连的物品节点在图上的相关性,相关性越高的物品在推荐列表中的权重就越高.

图中顶点的相关性主要取决于下面三个因素:

两个顶点之间的路径数；
两个顶点之间路径的长度；
两个顶点之间的路径经过的顶点.

而相关性高的一对顶点一般具有如下特征：

两个顶点之间有很多路径相连；
连接两个顶点之间的路径长度都比较短；
连接两个顶点之间的路径不会经过出度比较大的顶点.

以下图为例;

用户$A$和物品$c、e$没有边相连，但是用户$A$和物品$c$有一条长度为$3$的路径相连，用户$A$和物品$e$有两条长度为$3$的路径相连。那么，顶点$A$与$e$之间的相关性要高于顶点$A$与$c$，因而物品$e$在用户$A$的推荐列表中应该排在物品$c$之前，因为顶点$A$与$e$之间有两条路径——$(A,b,C,e)$和$(A,d,D,e)$.其中,$(A,b,C,e)$路径经过的顶点的出度为$(3,2,2,2)$而$(A,d,D,e)$路径经过的顶点的出度为$(3,2,3,2)$.因此,$(A,d,D,e)$经过了一个出度比较大的顶点$D$，所以$(A,d,D,e)$对顶点$A$与$e$之间相关性的贡献要小于$(A,b,C,e)$.

基于上面三个主要因素,有很多计算图中顶点之间相关性的方法,如基于随机游走的$PersonalRank$算法.

$PersonalRank$算法

可以看看这篇笔记

假设要给用户$u$进行个性化推荐，可以从用户$u$对应的节点$v_u$开始,在用户物品二分图上进行随机游走。游走到任何一个节点时，首先按照概率$\alpha$决定是继续游走，还是停止这次游走并从$v_u$节点开始重新游走。如果决定继续游走，那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品节点被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。
如果将上面的描述表示成公式，可以得到如下公式：

def PersonalRank(train, alpha, N):
    '''
    :params: train, 训练数据
    :params: alpha, 继续随机游走的概率
    :params: N, 推荐TopN物品的个数
    :return: GetRecommendation, 获取推荐结果的接口
    ''' 
    
    # 构建索引
    items = []
    for user in train:
        items.extend(train[user])
    id2item = list(set(items))
    users = {u: i for i, u in enumerate(train.keys())}
    items = {u: i+len(users) for i, u in enumerate(id2item)}
    
    # 计算转移矩阵（注意！！！要按照出度进行归一化）
    item_user = {}
    for user in train:
        for item in train[user]:
            if item not in item_user:
                item_user[item] = []
            item_user[item].append(user)
            
    data, row, col = [], [], []
    for u in train:
        for v in train[u]:
            data.append(1 / len(train[u]))
            row.append(users[u])
            col.append(items[v])
    for u in item_user:
        for v in item_user[u]:
            data.append(1 / len(item_user[u]))
            row.append(items[u])
            col.append(users[v])
            
    M = csc_matrix((data, (row, col)), shape=(len(data), len(data)))
    
    # 获取接口函数
    def GetRecommendation(user):
        seen_items = set(train[user])
        # 解矩阵方程 r = (1-a)r0 + a(M.T)r
        r0 = [0] * len(data)
        r0[users[user]] = 1
        r0 = csc_matrix(r0)
        r = (1 - alpha) * linalg.inv(eye(len(data)) - alpha * M.T) * r0
        r = r.T.toarray()[0][len(users):]
        idx = np.argsort(-r)[:N]
        recs = [(id2item[ii], r[ii]) for ii in idx]
        return recs
    
    return GetRecommendation

# PersonalRank实验
M, N, alpha = 8, 10, 0.8
exp = Experiment(M, N, alpha)
exp.run()

$PersonalRank$算法有较好的理论解释,但算法复杂度很高.因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，直到整个图上的每个顶点的$PR$值收敛。这一过程的时间复杂度非常高，不仅无法在线提供实时推荐，甚至离线生成推荐结果也很耗时。

解决方案一:减少迭代次数，在收敛之前就停止。这样会影响最终的精度，但一般来说影响不会特别大。

解决方案二:将$PersonalRank$转化为矩阵的形式。令$M$为用户物品二分图的转移概率矩阵，即：
$$
M(v,v’)=\frac{1}{|out(v)|}
$$
迭代公式可转化为:
$$
r=(1-\alpha)r_0+\alpha M^T=(1-\alpha)(1-\alpha M^T)^{-1}r_0
$$
这时只需利用稀疏矩阵快速求逆的办法来计算$(1-\alpha M^T)^{-1}$即可.

推荐系统读书笔记

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

推荐系统实践（项亮）第三章上一篇

推荐系统实践（项亮）第一章笔记下一篇

推荐系统实践（项亮）第二章笔记

第二章 利用用户行为数据

2.1 用户行为数据简介

2.2 用户行为分析

2.2.1 用户活跃度和物品流行度的分布

2.2.2 用户活跃度和物品流行度的关系

2.3 实验设计和算法评测

2.3.1 数据集

2.3.2 实验设计

2.3.3 评测指标

2.4 基于邻域的算法

2.4.1 基于用户的协同过滤算法(UserCF)

1. 基础算法

2. 用户相似度计算的改进

关于实验的总结

2.4.2 基于物品的系统过滤算法(ItemCF)

1. 基础算法

2. 用户活跃度对物品相似度的影响

3. 物品相似度的归一化

2.4.3 UserCF和ItemCF的比较

哈利波特问题(原始$ItemCF$算法的局限性)

2.5 隐语义模型

2.5.1 基础算法

2.5.2 基于LFM实际系统的例子

2.5.3 LFM和基于邻域的方法的比较

2.6 基于图的模型

2.6.1 用户行为数据的二分图表示

2.6.2 基于图的推荐算法

$PersonalRank$算法

第二章利用用户行为数据