Recommended System

推荐系统

推荐系统的核心问题就在于为用户推荐与其兴趣相似度比较高的商品。比如在微博上，用户至上想打发时间，并不是想准确的查看某条信息，在首页中查看每一条微博，为了帮助他筛选出一批他们可能感兴趣的信息，此时就需要分析出该用户的兴趣，从海量信息中选择出与用户兴趣相似的信息，并将这些信息推荐给用户。推荐系统就是这样，根据用户的历史和社交情况推荐与其喜好相符的商品或信息。

这时候就需要一个相似度函数

，函数

可以计算商品和我用户之间的复杂度，向用户推荐相似度较高的商品。为了能够预测出函数

，可以利用到历史诗句主要有：用户的历史行为数据，与该用户相关的其他用户信息，商品之间的相似性，文本描述等等。假设集合

表示所有的用户，集合

表示所有需要推荐的商品。函数

表示商品s到用户c之间的有效用函数，例如：

其中，R是一个全体排序集合。对于每一个用户

，希望从商品的集合上选择出商品，即

，以使得应用函数

的值最大。

在功业场景一般都是这样，线下部分可以随意发挥，Python，MATLAB等等都可以，但是到线上部分就要考虑各种情况了，比如效率和并非，甚至是可移植可拓展性等等。

推荐系统的评估方法

准确度

这个概念应该比较熟悉的了，对于准确度的评估，也要分系统来看，推荐系统有两种，一种是打分系统，一种就是TopN系统。打分系统其实就相当于是一种拟合方法，拟合用户的打分过程，而TopN系统就是给出前N个好的商品而已，所以这两个的准确度的评判标准是不一样的。对于打分系统：设

为用户

对物品

的实际打分，

为预测得分，误差判定标准有两个：

对于TopN的推荐系统，

代表推荐的内容，

就是用户选择的内容：

这两个评价指标是互相牵制的，准确率高制约着召回率。

覆盖率

表示对物体长尾的发掘能力。有时候卖的多的物品会卖的更多，因为很多人看到别人也买就会跟风，但这样就会造成穷的会更穷，富的会更富，所以为了消除这种两极分化，也叫马太效应。可以用一个熵的概念来衡量

熵其实是个人都知道，平均的时候是最大的，这就有利于消除贫富差距。

多样性

多样性表示的就是推荐物品的种类多样程度，如果推荐的物品基本都是鞋子一类的，那么多样性就很差了，首先用

来表示这两个物品的相似度，多样性表示：

以上就是一些主要的推荐评价指标，当然还是很多，比如新颖度，惊喜度，信任度，实时性等等。

冷启动

冷启动指的就是在一个新用户和新商品进来的时候，推荐系统对这个用户和商品是一无所知的，如何在这种情况下做到有效的推荐，这就叫做冷启动问题了。对于一个一无所知的用户，解决方法有很多：可以收集一些非常热门的商品，收集一些信息，在用户注册的时候收集一些信息，比如弹出来问一下你喜欢什么，或者问一下你感兴趣的是什么。很多游戏知乎都会有这种举措。在用户结束之后还可以进行一些互动的小游戏来确定用户喜欢还是不喜欢。

对于新商品，可以根据本身的属性，求与原来商品相似度。可以用item-based-CF推荐出去。

相似度的衡量

欧式距离，是个人都知道，不提了。

Pearson Correlation相似度：

<x,y>指的就是內积操作、皮尔逊相似度的好处就在于对于级数不敏感，级数相差过大带来的影响不大。

余弦相似度：

这个就不用多说了，一般就是用在了文本编码之后的向量相似度比较，因为这时候很多向量都不在欧式空间上了，一般就用他们夹角的大小来

推荐算法

基于内容的推荐

基于关联规则的推荐

协同过滤的推荐

基于知识的推荐

基于图的推荐

组合推荐

当然不会讲解这么多，只会提到一两个。

基于内容的推荐系统

基于内容就是基于用户喜欢的物品的属性/内容进行推荐，需要分析内容，无需考虑用户和用户直接的关系。通常就是在文本相关的产品上进行推荐。所以一般就是通过内容上的关键词进行推荐，然后编码比对物品内容的异同进行推荐。事实上编码之后就可以随意发挥了，直接使用KNN都是可以的。

最简单的文本推荐，对于一份文本，首先就是要建立资料这个时候就是叫编码过程了，因为不可能把里面的文字都抽取出来，这样工作量非常大，使用首先就是要分词去掉重复的词语，然后抽取关键字做编码。TF-IDF，词袋模型，ont-hot编码，词

在文件

中权重

都是可以的，得到这些向量之后，就可以用相似度衡量，选择合适的算法做相似度排序选择了。比如对于书本《Building data mining application for CRM》这个本书感兴趣。

以上是商品总和。

出现过的单词扣一，没有的都是0，这种编码叫做one-hot编码，这里商品少，单词也就那么几个，所以ont-hot编码不长，就是一点点而已。比较牛逼点的就是TF-IDF了：

把文档出现词的概率算了进来。得到这些向量之后只需要做近似就好了，比如KNN最简单的。

协同过滤的推荐

NeiNeighborhood-based Algorithm是一种基于近邻的推荐，协同过滤有两种，一种是基于用户的协同过滤，一种是基于物品的协同过滤。

user-based CF

其实过程是非常简单的，简单到飞起。首先我们是要得到一个相似度矩阵，这个相似度矩阵首先是一个对称的，其次它的对角线都是0,。计算完用户之间的相似度之后利用用户之间的相似度为没有打分的项打分。其实就是

找到当前这个用户没有打分的商品，然后把对这个商品评价过的用户的得分乘上相似矩阵的对应权重相加即可。

代码实现

工具包的实现：

求余弦相似度：

def cos_sim(x, y):
    numerator = x * y.T
    denominator = np.sqrt(x * x.T)
    return (numerator / denominator)[0, 0]

求相似度矩阵：

def similarity(data):
    m = np.shape(data)[0]
    w = np.mat(np.zeros((m, m)))
    for i in range(m):
        for j in range(i, m):
            if j != i:
                w[i, j] = cos_sim(data[i, ], data[j, ])
                w[j, i] = w[i, j]
            else:
                w[i, j] = 0
    return w

求top N的商品是什么：

def top_k(predict, k):
    top_recom = []
    len_result = len(predict)
    if k >= len_result:
        top_recom = predict
    else:
        for i in range(k):
            top_recom.append(predict[i])
    return top_recom

基于用户的协同过滤：

def user_based_recommend(data, w, user):
    m, n = np.shape(data)
    interaction = data[user, ]
    not_inter = []
    for i in range(n):
        if interaction[0, i] == 0:
            not_inter.append(i)
    predict = {}
    for x in not_inter:
        item = np.copy(data[:, x])
        for i in range(m):
            if item[i, 0] != 0:
                if x not in predict:
                    predict[x] = w[user, i] * item[i, 0]
                else:
                    predict[x] = predict[x] + w[user, i] * item[i, 0]
    return sorted(predict.items(), key=lambda  d:d[1], reverse=True)

相似度矩阵

为每一个用户所推荐的商品。

item_based CF

也是一样，只需要把数据转置一下就好了。

def item_based_recommend(data, w, user):
    m, n = np.shape(data)
    interation = data[:, user]
    not_inter = []
    for i in range(n):
        if interation[0, i] == 0:
            not_inter.append(i)

    predict = {}
    for x in not_inter:
        item = np.copy(interation)
        for j in range(m):
            if item[0, j] != 0:
                if x not in predict:
                    predict[x] = w[x, j] * item[0, j]
                else:
                    predict[x] = predict[x] + w[x, j] * item[0, j]
    return sorted(predict.items(), key=lambda d:d[1], reverse=True)

相似度矩阵

每位用户的推荐。

user-based vs item-based 这两种方法各有优缺点。对于UserCF，适用于用户较少的场景，如果用户是非常多的的情况下，计算用户相似度矩阵的代价是很大的。这个时候如果物品相对用户要少，那么就可以用ItemCF来计算相似度矩阵。对于两种算法的领域也有很大的区别，UserCF的时效性较强，对于用户兴趣不太明显的领域是有可能会推荐出来的，也就是说覆盖性会好一些，因为它是根据用户之间的相似度决定的，用户之间的兴趣点是相似但是不会都相同的，所以可以削弱马太效应。而对于ItemCF，这个物品相似度是死的，相似的基本都很相似，所以可能会有很大的长尾，一般是用户需求很强烈的地方使用。还有冷启动问题，对于一个新用户进来的时候，不能立刻对他进行推荐，因为用户的相似度矩阵是一段时间后离线计算的，新物品上线之后一旦有用户对这个商品产生行为就可以将物品推荐给它产生行为的用户了。但是这样就没有办法在不离线更新相似度表的情况下将新物品推荐给用户了。还有就是推荐理由，对于UserCF，用一个我根本不认识的人的习惯来推荐给我，对于用户的说服力肯定是不够的，商品就不一样了，商品是死的。 CF的优缺点 优点：基于用户的行为对于推荐内容是不需要先验知识的，只需要建立用户或者是商品的相似矩阵即可，结构很简单，在用户丰富的情况下效果很好，而且很简单。 缺点：需要大量的行为，也就是历史数据，需要通过完全相同的商品关联起来，相似的不行。而且·使用CF是有前提的了，要求就是用户只会完全取决于之前的行为，上下文是没有关系的了。而且在数据稀疏的情况下效果是不好的，还可能需要二度关联，因为如果一下商品没有什么人买，基本就没得推荐了。

基于隐语义的推荐

基于隐语义的推荐，其实就是矩阵分解。之前写过一篇叫Matrix Factorization的文章讲的就是这个：https://www.jianshu.com/p/af49053832c5

首先对用户进行一些简单的编码，因为用户如果是把名字记上去是做不了计算的，所以我们把用户进行编码，比如有4个用户，一号用户就

，二号

等等以此类推。

如果是使用神经网络来解决这个问题，首先就是要设计一个网络，

，N输入用户的数量，d就是网络的维度，M就是输出的结果，M就是物品的数量，因为最后的输出就是用户对商品的评分。

但实际上还是有一个问题，就是对于激活函数，也就是非线性函数是否需要的问题。事实上是不需要的，因为如果只有一个

是有效的，那么这个

就是只有一行有效的，所以只会有一个x经过了tanh函数，从效果上讲一个tanh(x)和x是没有什么区别的。所以可以忽略非线性：

整合一下公式

由于x就是一行有效，所以

所以，第m个用户的第n个商品的评分就是

这样就分解得到了我们要的公式，最后求导即可。事实上分解出来的两个矩阵里面的变量代表的数据的意义其实是不明确的，也就是说比较抽象，怎么想象都行。分解出来的矩阵

，k代表的就是分解的度，分解的越多有可能会过拟合，所以这里也是可以加正则化的。

不要尝试的去理解所有分解的赢语义，这是没有意义的，比如神经网络的每一个神经元，事实上你们是不知道他们到底是在干什么，只是知道他们在观察而又，这里也是一样的，这里面分解出来的东西，如果是电影，你可以说是喜剧成分，武大成分，也可以说是演员等等，相当于一指示变量而已，只是指明了这个物品是多少分，但是没有给出具体的意义。

具体的公式之前的博客都有，例子也提到，这里就不重复了。

上面提到的只是最简单的MF模型，但是这类模型有一个缺点，他们分解出来的东西会有负数，这就尴尬了，因为很少有变量因素会其负作用的，于是便出现了非负矩阵分解。

非负矩阵分解出现的根本原因就矩阵分解解释性差的问题。

NMF

矩阵非负分解，这个就有点厉害了。首先引入一下KL离散度：

KL损失函数 对于KL散度的推导其实很简单：

所以一阶Tayor逼近的误差是：

代入熵

：

这样推导出来了。平方差损失函数对应着高斯分布，那么KL肯定也对应着另一个分布——泊松分布：

因为

是随机数，所以求一下期望：

所以KL离散度就对应了泊松分布。

对于这个KL离散度：

KL离散度一定是大于等于0的，当

的时候，这个离散度就是等于0的了，所以我们要求的就是不断的

即可。

所以现在NMF的损失函数有两种了①均方差损失函数:

；②KL离散度：

，还是用第一种吧！

问题来了，既然是非负数的，怎么保证是正数是一个问题，这里有一个很牛逼的技巧：

所以更新方式：

要做的就是设计一个n，使得乘上之后可以抵消前面的Q即可。

，带进去之后：

使用KL离散也是一样的。

代码实现

def train(V, r, maxCycles, e):
    m, n = np.shape(V)
    W = np.mat(np.random.random((m, r)))
    H = np.mat(np.mat(np.random.random((r, n))))

    for step in range(maxCycles):
        V_pre = W * H
        E = V - V_pre
        err = 0.0
        for i in range(m):
            for j in range(n):
                err += E[i, j] * E[i, j]
        if err < e:
            break
        if step % 1000 == 0:
            print("\Interator: ", step, " Loss: ", err)
        a = W.T * V
        b = W.T * W * H
        for i in range(r):
            for j in range(n):
                if b[i, j] != 0:
                    H[i, j] = H[i, j] * a[i, j] / b[i, j]
        c = V * H.T
        d = W * H * H.T
        for i in range(m):
            for j in range(r):
                if d[i, j] != 0:
                    W[i, j] = W[i, j] * c[i, j] / d[i, j]
    return W, H

效果：

效果还是可以的。

CF VS隐语义

隐语义其实还有一种分解方式，就是SVD，SVD也可以的，但是SVD的分解是

，而且如果原矩阵是有很多缺省值的话，那么SVD就会用0填充，这样不太好的。相比之下CF跟简单，而且可解释性也强，但是隐语义模型可以挖掘出更深层的物体或者是用户之间的关系，覆盖性会更好，双方各有优缺点。

基于图的推荐

PageRank Algorithm

首先要提到的就是PageRank算法，等下还要改进一下这个算法才会得到真正的推荐系统算法。这个算法是在Google初期使用的一个网页排序算法，用于对网页重要性的排序。一开始的网页排序都是按照人工筛选或者是关键词筛选的，但是这样效率不高而且效果不好，经常是有很多网页有很多重复关键词的然后被置顶，这个时候就需要一个新的方法来重新评估网页的质量，重新排序了。

把互联网上的网页模拟成一个节点，出链就是指向其他网页的一条有向边，也就是当前这个网页有一条指向其他网页的边，入链就是一个指向当前页面的边，也就是说有一个网页是指向了当前这个网页的。这个时候当前网页就是其他网页转进来的了。所以网页评估是带有以下的两个假设的：数量假设：一个网页的入度，也就是入链越大，质量越高。质量假设：一个节点的入度来源质量越高，那么当前节点质量就越高。但是，问题来了，网页A和网页B的质量有关系，网页B又和网页C有关系，以此类推要是网页C又和A有关系那就陷入了循环里面了。这样就解不出来了，所以简化一下模型，假设，所有的网页都和前一个网页有关系，这样就叫随机游走模型，也就是一阶马尔科夫模型。随机游走可以看做是马尔科夫链的一种特例。也叫做醉汉模型，没一次走的方向或者步数只于前一次走的有关系而已，这一点有点像布朗运动。

现在将这个模型数学化一下下，假设现在有N个网页，一开始初始化肯定每一个网页的概率都是一样大的，都是

，比如下图：

每一个网页的概率就是

，每一个网页转向其他网页的概率都是一样的：

记这个矩阵为

矩阵，

代表的就网页j跳转到网页i的概率，

。根据这个矩阵，我们是可以计算出用户访问每一个网页的概率：

当迭代多次之后，

这个矩阵会最终稳定下来，这个矩阵叫马尔科夫矩阵。

矩阵T的条件 对于转移矩阵T是存在条件的： ①T要是随机矩阵：所有元素大于0，而且要求列相加要是等于1的。 ②T是不可约的：所谓的不可约就是强连通性，即图中任何一个节点可以到达其他任何一个节点。比如有某一个节点是不能到达任何一个节点的，在那个节点所在的列都是0，或者是只有回到自己，也就是自环路。这两种就是在后面提到的终止点和陷阱了。 ③T要是非周期的：也就是符合马尔科夫链的周期性变化。

周期性迭代之后最终结果会固定住，比如上面的结果就是

，也就是说第一个页面访问的频率是很高的。

终止点

终止点就是指没有任何出链的网页，比如：

节点C就是一个终止点。

这样的结果显然是毫无意义的。但是这并不意味着凉了，任何的算法都是人想出来的，也就是模拟人的做法。如果你遇到一个直进不出的网站，那么肯定是开溜去另外一个网站，所以遇到这种情况，那直接就是退出去啊。所以遇到这种情况就是直接把这个图的终止点改成到每一个节点都有一条边，因为退出重新选择网页就相当于是从这个网页转移到其他网页去了。成功改变结果。

陷阱

只是指向了自己，多次收敛之后：

这个结果也是毫无意义的。同样，一个用户是不可能总是在一个网页里面打转。刚刚的添加转移的边方法也是可以的，但是比较常用的一种方法是用一个概率转移的方法，没一次用户不是都是一定会按照状态转移矩阵走的，所以可以加上一个退出的概率。

这样就稳了。

Summary

首先一个就是链接的质量问题，有很多导航栏的链接是不能和正常的跳转链接相比较的，比如CSDN两边的那些博客，都是自己写的，这些很影响判断的。还有一个就是没有过滤广告的链接，这些也是影响判断的。还有一个是类似于冷启动的问题，一个新网友如果是刚刚加了进来，一般是没有什么入度的，出度可能有，可能还要花些时间适应。

对于PageRank的公式化

每一个节点我们都给一个PR值给他们，也就是说会根据这个PR值来判断哪个网站走的概率最大。

这个时候

，然而，图中的B是不止一条的，B到A有两条路径，那么就是二分之一了，所以

，不断往下迭代即可。所以一个网页的迭代公式：

N表示网页总数，in(i)表示的是指向网页i的网页集合，out(j)表示的就是网页j指向的网页集合。后面代码实现就是按照这个。

马尔科夫链的收敛性的证明

这个就有点牛逼了。

对于收敛性，有三个性质要证明的：

存在一个特征值

假设一个向量

，由于每一列相加都是1，所以

这个是直接根据性质证明的。

存在的特征值都是

假设一个函数

，假设

代表的就是列向量，那么有：

所以，

就还是马尔科夫矩阵，无论上面叠多少次方都还是。根据特征值的幂还有特征向量有

，如果

那么就是无限大了，但是马尔科夫矩阵是小于1的，所以和假设矛盾

。

收敛性

因为只有一个特征值是1的，其他都是小于1的，n次方更不要说了，所以迭代多次之后绝壁收敛，实锤。参考：http://blog.sina.com.cn/s/blog_80ce3a550102xas8.html

这样就完整证明了PageRank算法。

代码实现

from pygraph.classes.digraph import digraph
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

class pageRank(object):

    def __init__(self, dg):
        self.alpha = 0.85
        self.maxCycles = 200
        self.min_delta = 0.0001
        self.graph = dg

    def page_rank(self):
        #没有出链的点先加上和所有点的边
        for node in self.graph.nodes():
            if len(self.graph.neighbors(node)) == 0:
                for node2 in self.graph.nodes():
                    digraph.add_edge(self.graph, (node, node2))
        nodes = self.graph.nodes()
        graphs_size = len(nodes)

        if graphs_size == 0:
            return 'nodes set is empty!'

        page_rank = dict.fromkeys(nodes, 1.0/graphs_size)
        runAway = (1.0 - self.alpha) / graphs_size
        flag = False
        for i in range(self.maxCycles):
            change = 0
            for node in nodes:
                rank = 0
                for incident_page in self.graph.incidents(node):
                    rank += self.alpha * (page_rank[incident_page] / len(self.graph.neighbors(incident_page)))
                rank += runAway
                change += abs(page_rank[node] - rank)
                page_rank[node] = rank

            print("NO.%s iteration" % (i + 1))
            print(page_rank)

            if change < self.min_delta:
                flag = True
                break
        return page_rank

导入数据代码我懒得写了，直接用了一个包里面的。

if __name__ == '__main__':
    dg = digraph()

    dg.add_nodes(["A", "B", "C", "D", "E"])

    dg.add_edge(("A", "B"))
    dg.add_edge(("A", "C"))
    dg.add_edge(("A", "D"))
    dg.add_edge(("B", "D"))
    dg.add_edge(("C", "E"))
    dg.add_edge(("D", "E"))
    dg.add_edge(("B", "E"))
    dg.add_edge(("E", "A"))

    pr = pageRank(dg)
    page_ranks = pr.page_rank()

    print("The final page rank is\n", page_ranks)

最后效果：

好像和推荐系统扯远了，但是这个算法要用到后面退出PersonalRank算法。

PersonalRank Algorithm

在PageRank算法中，计算出的PR值是每一个节点相对于全局的重要性程度，而在推荐问题里面要求的是商品对于用户的重要性了，而不是全局的重要性。比如，当这个用户U1计算的时候，就要遍历所有的商品进行计算，看看哪个商品的重要性相对于这个用户是最高的就推荐即可。

PersonalRank Algorithm是PageRank的变形，用于计算商品节点

相对于用户节点U的重要程度。假设用户为

，则从节点

开始在用户——商品二部图中游走，游走到容易一个节点的时候，和PageRank算法一样，会按照一定的概率选择停止或者继续游走。直到每一个节点访问的概率不再变化位置。

首先引入二部图：

二部图是无向图的一种，若无向图

中，其中，V是无向图中的顶点的集合，E是无向图中边的集合。在无向图G中，边的集合V可以分成两个子集

，而且满足这两个子集交集为空。回到PersonalRank算法，在这个算法中不用区分用户和商品，上述节点的感兴趣程度就变成了对用户

计算各个节点

的重要程度。算法具体流程：

①初始化：

。

②开始在图上游走，每次选择PR值不为0的节点开始，沿着边往前的概率为

，停在当前点的概率就是

了。

③首先U1开始，从U1到D2,D3,D4的概率就是

，则此时D1,D2和D4的PR就是

，U1的PR值就变成了

。

④此时PR值不为0的节点为

，则此时从这三点出发，继续上述的过程直到收敛为止。所以更新公式为：

如果是在当前节点那么就要加上一个停留的概率了。

代码实现

def generate_dict(dataTmp):
    m, n = np.shape(dataTmp)
    data_dict = {}
    for i in range(m):
        tmp_dict = {}
        for j in range(n):
            if dataTmp[i, j] != 0:
                tmp_dict["D_" + str(j)] = dataTmp[i, j]
        data_dict["U_" + str(i)] = tmp_dict
    for j in range(n):
        tmp_dict = {}
        for i in range(m):
            if dataTmp[i, j] != 0:
                tmp_dict["U_" + str(i)] = dataTmp[i, j]
        data_dict["D_" + str(j)] = tmp_dict
    return data_dict

转换成二部图。

def PersonalRank(data_dict, alpha, user, maxCycles):
    rank = {}
    for x in data_dict.keys():
        rank[x] = 0
    rank[user] = 1
    step = 0
    while step < maxCycles:
        tmp = {}
        for x in data_dict.keys():
            tmp[x] = 0
        for i, ri in data_dict.items():
            for j in ri.keys():
                if j not in tmp:
                    tmp[j] = 0
                tmp[j] += alpha * rank[i] / (1.0 * len(ri))
                if j == user:
                    tmp[j] += (1-alpha)
        check = []
        for k in tmp.keys():
            check.append(tmp[k] - rank[k])
        if sum(check) <= 0.0001:
            break
        rank = tmp
        if step % 20 == 0:
            print('NO: ', step)
        step += 1
    return rank

效果：

最后附上GitHub代码：https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/Recmmended%20System