用户画像个人收藏程序员

利用用户行为数据推荐

2017-09-15  本文已影响478人  TryEnough

利用用户行为数据分析的算法也称为协同过滤算法

用户行为日志通常存储在分布式数据仓库中,如支持离线分析的Hadoop Hive和支持在线分析的Google Dremel。

用户行为分为显性反馈行为(explicit feedback)和隐性反馈行为(implicit feedback)，举几个例子来解释下这两个名词：

用户行为例子

用户行为的一般规律

很多网站的普遍规律表明，用户行为大都遵循长尾分布

长尾图示

学术界对协同过滤算法进行了深入研究,提出了很多方法,比如基于邻域的方法(neighborhood-based)、隐语义模型 (latent factor model)、基于图的随机游走算法(random walk on graph)等。在这些方法中, 最著名的、在业界得到最广泛应用的算法是基于邻域的方法,而基于邻域的方法主要包含下面两种算法：

实验设计和算法评测

    def SplitData(data, M, k, seed):
        test = []
        train = []
        random.seed(seed)
        for user, item in data:
             if random.randint(0,M) == k:
                 test.append([user,item])
             else:
                 train.append([user,item])
        return train, test

这里,每次实验选取不同的k(0≤k≤M1)和相同的随机数种子seed,进行M次实验就可以得到M个不同的训练集和测试集,然后分别进行实验,用M次实验的平均值作为最后的评测指标。

准确率 
def Precision(train, test, N):
    hit = 0
    all = 0
    for user in train.keys():
        tu = test[user]
        rank = GetRecommendation(user, N)
        for item, pui in rank: 4
            if item in tu:
                 hit += 1
        all += N
return hit / (all * 1.0)

召回率

召回率 
def Recall(train, test, N):
    hit = 0
    all = 0
    for user in train.keys():
        tu = test[user]
        rank = GetRecommendation(user, N)
        for item, pui in rank:
            if item in tu:
                hit += 1
        all += len(tu)
    return hit / (all * 1.0)

覆盖率反映了推荐算法发掘长尾的 能力,覆盖率越高,说明推荐算法越能够将长尾中的物品推荐给用户。

覆盖度 
def Coverage(train, test, N):
    recommend_items = set()
    all_items = set()
    for user in train.keys():
        for item in train[user].keys():
            all_items.add(item)
        rank = GetRecommendation(user, N)
        for item, pui in rank:
            recommend_items.add(item)
    return len(recommend_items) / (len(all_items) * 1.0)

新颖度这里用推荐列表中物品的平均流行度度量推荐结果的新颖度。如果推荐出的物品都很热门,说明推荐的新颖度较低,否则说明推荐结果比较新颖。

def Popularity(train, test, N):
         item_popularity = dict()
         for user, items in train.items():
              for item in items.keys()
                  if item not in item_popularity:
                      item_popularity[item] = 0
                  item_popularity[item] += 1
         ret = 0
         n=0
         for user in train.keys():
              rank = GetRecommendation(user, N)
              for item, pui in rank:
                  ret += math.log(1 + item_popularity[item])
                  n += 1
         ret /= n * 1.0
         return ret

重点:

基于邻域的算法

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

用户相似度简单计算：
协同过滤算法主要利用行为的相似度计算兴趣的相似度。给定用户u和用户v,令N(u)表示用户u曾经有过正反馈的物品集合,令N(v)为用户v曾经有过正反馈的物品集合。

用户相似度

或者通过余弦相似度计算:

用户相似度2

举个例子解释一下：UserCF计算用户兴趣相似度的例子。在该 例中,用户A对物品{a, b, d}有过行为,用户B对物品{a, c}有过行为,利用余弦相似度公式计算用 户A和用户B的兴趣相似度为:

UserCF用户相似度

对两两用户都利用余弦相似度计算相似度。这种方法的时间复杂度是O(|U|*|U|),这在 用户数很大时非常耗时。事实上,很多用户相互之间并没有对同样的物品产生过行为,即很多时 候 N (u) 相交 N (v)等于  0 。

可以首先建立物品到用户的倒排表,对于每个物品都保存对该物品产生过行为的用户列表。令稀疏矩阵C[u][v]= N (u) 交 N (v) 。那么,假设用户u和用户v同时属于倒排表中K个物品对 应的用户列表,就有C[u][v]=K。从而,可以扫描倒排表中每个物品对应的用户列表,将用户列 表中的两两用户对应的C[u][v]加1,最终就可以得到所有用户之间不为0的C[u][v]。

def UserSimilarity(train):
        # build inverse table for item_users
        item_users = dict()
        for u, items in train.items():
             for i in items.keys():
                 if i not in item_users:
                     item_users[i] = set()
                 item_users[i].add(u)
        #calculate co-rated items between users
        C = dict()
        N = dict()
        for i, users in item_users.items():
             for u in users:
                 N[u] += 1
                 for v in users:
                     if u == v:
                         continue
                     C[u][v] += 1
        #calculate finial similarity matrix W
        W = dict()
        for u, related_users in C.items():
             for v, cuv in related_users.items():
                 W[u][v] = cuv / math.sqrt(N[u] * N[v])
return W
用户－物品倒排表

得到用户之间的兴趣相似度后,UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的 物品。如下的公式度量了UserCF算法中用户u对物品i的感兴趣程度:

S(u, K)包含和用户u兴趣最接近的K个用户,N(i)是对物品i有过行为的用户集合,wuv 是用户u和用户v的兴趣相似度,rvi代表用户v对物品i的兴趣,因为使用的是单一行为的隐反馈数 据,所以所有的rvi=1。

选取K=3,用户A对物品c、e没有过行为, 因此可以把这两个物品推荐给用户A。根据UserCF算法,用户A对物品c、e的兴趣是:
p(A,c) ＝ wAB＋  wAD ＝ 0.7416
p(A,e) ＝ wAC ＋ wAD ＝ 0.7416

用户相似度计算改进：

以图书为例,如果两个用户都曾经买过《新华字典》,这丝毫不能说明他们兴趣相似, 因为绝大多数中国人小时候都买过《新华字典》。但如果两个用户都买过《数据挖掘导论》,那可 以认为他们的兴趣比较相似,因为只有研究数据挖掘的人才会买这本书。换句话说,两个用户对冷门物品采取过同样的行为更能说明他们兴趣的相似度。

该算法减小了用户u和用户v共同兴趣列表中热门物品对他们相似度的影响。
比较上面的算法，只是在计算C[u][v]加1时做了改变：

//简单版
C[u][v] += 1
//优化版
C[u][v] += 1 / math.log(1 + len(users))

基础算法
ItemCF算法并不利用物品的内容属性计算物品之间的相似度,它主要通过分析用户的行为记录计算物品之间的相似度。该算法认为,物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品B。

1、基于物品的协同过滤算法主要分为两步。
(1) 计算物品之间的相似度。
(2) 根据物品的相似度和用户的历史行为给用户生成推荐列表。


分母|N(i)|是喜欢物品i的用户数,而分子 N(i)N(j) 是同时喜欢物品i和物品j的用户 数。因此,上述公式可以理解为喜欢物品i的用户中有多少比例的用户也喜欢物品j。虽然看起来很有道理,但是却存在一个问题。如果物品j很热门,很多人都喜欢,那么Wij就会很大,接近1。

这个公式惩罚了物品j的权重,因此减轻了热门物品会和很多物品相似的可能性。

和UserCF算法类似,用ItemCF算法计算物品相似度时也可以首先建立用户—物品倒排表(即 对每个用户建立一个包含他喜欢的物品的列表),然后对于每个用户,将他物品列表中的物品两 两在共现矩阵C中加1。

在得到物品之间的相似度后,ItemCF通过如下公式计算用户u对一个物品j的兴趣:


这里N(u)是用户喜欢的物品的集合,S(j,K)是和物品j最相似的K个物品的集合,wji是物品j和i 的相似度,rui是用户u对物品i的兴趣。(对于隐反馈数据集,如果用户u对物品i有过行为,即可令 5 rui=1。)

2、用户活跃度对物品相似度的影响:
活跃用户对物品相似度的贡献应该小于不活跃的用户\


上面的公式只是对活跃用户做了一种软性的惩罚 。

3、物品相似度的归一化
如果已经得到了物品相似度矩阵w,那么可以用如下公式得到归一化之后的相似度 矩阵w':


UserCF和ItemCF的综合比较

UserCF的推荐结果着重于反映和用户兴趣相似的小群体的热点,而ItemCF 的推荐结果着重于维系用户的历史兴趣。换句话说,UserCF的推荐更社会化,反映了用户所在的小型兴趣群体中物品的热门程度,而ItemCF的推荐更加个性化,反映了用户自己的兴趣传承。

UserCF和ItemCF优缺点的对比

隐语义模型

LFM(latent factor model)隐语义模型通过如下公式计算用户u对物品i的兴趣:


这个公式中 Pu,k 和 qi,k 是模型的参数,其中 Pu,k 度量了用户u的兴趣和第k个隐类的关系,而 qi,k 度量了第k个隐类和物品i之间的关系。这两 个参数是从数据集中计算出来的。

对负样本采样时应该 遵循以下原则：

def RandomSelectNegativeSample(self, items):
    ret = dict()
    for i in items.keys():
        ret[i] = 1
    n=0
    for i in range(0, len(items) * 3):
        item = items_pool[random.randint(0, len(items_pool) - 1)]
        if item in ret:
             continue
        ret[item] = 0
        n+=1
        if n > len(items):
             break
    return ret

LFM和基于邻域的方法的比较
LFM是一种基于机器学习的方法,具有比较好的理论基础。这个方法和基于邻域的方法(比 如UserCF、ItemCF)相比,各有优缺点。

基于图的模型

下图是一个简单的用户物品二分图模型,其中圆形节点代表用户,方形节点代表物品,圆形节点和方形节点之间的边代表用户对物品的行为。比如图中用户节点A和物品节点a、b、d相连,说明用户A对物品a、b、d产生过行为。

用户物品二分图模型

基于图的推荐算法：

上一篇下一篇

猜你喜欢

热点阅读