Recommended System

2018-09-27 本文已影响46人冒绿光的盒子

相似度的衡量

欧式距离，是个人都知道，不提了。
Pearson Correlation相似度： $Corr(x,y) = \frac{<x-x',y-y'>}{|x-x'||y-y'|}$ <x,y>指的就是內积操作、皮尔逊相似度的好处就在于对于级数不敏感，级数相差过大带来的影响不大。
余弦相似度： $cos(x,y) = \frac{<x,y>}{|x||y|}$ 这个就不用多说了，一般就是用在了文本编码之后的向量相似度比较，因为这时候很多向量都不在欧式空间上了，一般就用他们夹角的大小来

推荐算法

基于内容的推荐

基于关联规则的推荐

协同过滤的推荐

基于知识的推荐

基于图的推荐

组合推荐

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

基于内容的推荐系统

基于内容就是基于用户喜欢的物品的属性/内容进行推荐，需要分析内容，无需考虑用户和用户直接的关系。通常就是在文本相关的产品上进行推荐。所以一般就是通过内容上的关键词进行推荐，然后编码比对物品内容的异同进行推荐。事实上编码之后就可以随意发挥了，直接使用KNN都是可以的。
最简单的文本推荐，对于一份文本，首先就是要建立资料这个时候就是叫编码过程了，因为不可能把里面的文字都抽取出来，这样工作量非常大，使用首先就是要分词去掉重复的词语，然后抽取关键字做编码。TF-IDF，词袋模型，ont-hot编码，词 $k_{ij}$ 在文件 $d_j$ 中权重 $w_{ij}$ 都是可以的，得到这些向量之后，就可以用相似度衡量，选择合适的算法做相似度排序选择了。比如对于书本《Building data mining application for CRM》这个本书感兴趣。

以上是商品总和。

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

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

协同过滤的推荐

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

user-based CF

其实过程是非常简单的，简单到飞起。首先我们是要得到一个相似度矩阵，这个相似度矩阵首先是一个对称的，其次它的对角线都是0,。计算完用户之间的相似度之后利用用户之间的相似度为没有打分的项打分。其实就是 $p(u,i) = \sum_{v \in N(j)}w_{u,v}r_{v,j}$ 找到当前这个用户没有打分的商品，然后把对这个商品评价过的用户的得分乘上相似矩阵的对应权重相加即可。
代码实现
工具包的实现：
求余弦相似度：

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个用户，一号用户就 $[1,0,0,0]$ ，二号 $[0,1,0,0]$ 等等以此类推。

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

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

整合一下公式

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

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

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

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

NMF

矩阵非负分解，这个就有点厉害了。首先引入一下KL离散度： $D(A|B) = \sum_{i,j}(A_{i,j}log \frac{A}{B}-A_{i,j}+B_{i,j})$

KL损失函数

对于KL散度的推导其实很简单：
$f(x) - f(x_0) = \nabla f(x_0)(x-x_0) \\ f(y) = f(x) - \nabla f(x) (x-y)$ 所以一阶Tayor逼近的误差是： $f(x) - f(y) - \nabla f(x) (x-y)$ 代入熵 $f(x) = \sum_{i=1}^k x_iInx_i$ ： $D(x||y) = xInx - yIny - (Iny + 1)(x-y) \\ D(x||y) = xlog \frac{x}{y} - x + y$ 这样推导出来了。平方差损失函数对应着高斯分布，那么KL肯定也对应着另一个分布——泊松分布： $P(X = x) = \frac{\lambda ^x}{x!}e^{-\lambda} \\ P_1(X = x) = \frac{\lambda_1 ^x}{x!}e^{-\lambda_1} \\ P_2(X = x) = \frac{\lambda_2 ^x}{x!}e^{-\lambda_2} \\ In \frac{P_1(X=x)}{P_2(X = x)} = xIn \frac{\lambda_1}{\lambda_2} - \lambda_1 + \lambda_2$ 因为 $x$ 是随机数，所以求一下期望： $\sum_{x = 0}^{+\infty}P_1(X=x)In(\frac{P_1(X=x)}{P_2(X=x)}) = \sum_{i=1}^{+ \infty}P_1{X=x}[xIn \frac{\lambda_1}{\lambda_2}-\lambda_1+\lambda_2] \\ = \lambda_1 In \frac{\lambda_1}{\lambda_2}-\lambda_1 + \lambda_2$ 所以KL离散度就对应了泊松分布。

对于这个KL离散度： $D(A|B) = \sum_{i,j}(A_{i,j}log \frac{A}{B}-A_{i,j}+B_{i,j})$ KL离散度一定是大于等于0的，当 $A == B$ 的时候，这个离散度就是等于0的了，所以我们要求的就是不断的 $minimizeD(A||B)$ 即可。
所以现在NMF的损失函数有两种了①均方差损失函数: $loss = \frac{1}{2}(y - y')^2$ ；②KL离散度： $loss = \sum_{i,j}(A_{i,j}log \frac{A}{B}-A_{i,j}+B_{i,j})$ ，还是用第一种吧！
问题来了，既然是非负数的，怎么保证是正数是一个问题，这里有一个很牛逼的技巧：
$loss = [R - (PQ)]^2 \\ \frac{\delta loss}{\delta Q} = 2[R - (PQ)]P \\ = -2[(P^TR)-(P^TPQ)]$
所以更新方式： $Q = Q + n*[(P^TR) - (P^TPQ)]$ 要做的就是设计一个n，使得乘上之后可以抵消前面的Q即可。 $n = \frac{Q}{P^TPQ}$ ，带进去之后： $Q = Q \frac{(P^TR)}{(P^TPQ)} \\ P = P \frac{(RQ^T)}{PQQ^T}$ 使用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的分解是 $O(m^3)$ ，而且如果原矩阵是有很多缺省值的话，那么SVD就会用0填充，这样不太好的。相比之下CF跟简单，而且可解释性也强，但是隐语义模型可以挖掘出更深层的物体或者是用户之间的关系，覆盖性会更好，双方各有优缺点。

基于图的推荐

PageRank Algorithm

首先要提到的就是PageRank算法，等下还要改进一下这个算法才会得到真正的推荐系统算法。这个算法是在Google初期使用的一个网页排序算法，用于对网页重要性的排序。一开始的网页排序都是按照人工筛选或者是关键词筛选的，但是这样效率不高而且效果不好，经常是有很多网页有很多重复关键词的然后被置顶，这个时候就需要一个新的方法来重新评估网页的质量，重新排序了。
把互联网上的网页模拟成一个节点，出链就是指向其他网页的一条有向边，也就是当前这个网页有一条指向其他网页的边，入链就是一个指向当前页面的边，也就是说有一个网页是指向了当前这个网页的。这个时候当前网页就是其他网页转进来的了。所以网页评估是带有以下的两个假设的：数量假设：一个网页的入度，也就是入链越大，质量越高。质量假设：一个节点的入度来源质量越高，那么当前节点质量就越高。但是，问题来了，网页A和网页B的质量有关系，网页B又和网页C有关系，以此类推要是网页C又和A有关系那就陷入了循环里面了。这样就解不出来了，所以简化一下模型，假设，所有的网页都和前一个网页有关系，这样就叫随机游走模型，也就是一阶马尔科夫模型。随机游走可以看做是马尔科夫链的一种特例。也叫做醉汉模型，没一次走的方向或者步数只于前一次走的有关系而已，这一点有点像布朗运动。
现在将这个模型数学化一下下，假设现在有N个网页，一开始初始化肯定每一个网页的概率都是一样大的，都是 $\frac{1}{N}$ ，比如下图：

每一个网页的概率就是

节点C就是一个终止点。

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

陷阱

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

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

这个时候

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

PersonalRank Algorithm

在PageRank算法中，计算出的PR值是每一个节点相对于全局的重要性程度，而在推荐问题里面要求的是商品对于用户的重要性了，而不是全局的重要性。比如，当这个用户U1计算的时候，就要遍历所有的商品进行计算，看看哪个商品的重要性相对于这个用户是最高的就推荐即可。
PersonalRank Algorithm是PageRank的变形，用于计算商品节点 $D_j$ 相对于用户节点U的重要程度。假设用户为 $U_1$ ，则从节点 $U_1$ 开始在用户——商品二部图中游走，游走到容易一个节点的时候，和PageRank算法一样，会按照一定的概率选择停止或者继续游走。直到每一个节点访问的概率不再变化位置。
首先引入二部图：

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

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

Recommended System

推荐系统

推荐系统的评估方法

准确度

覆盖率

多样性

冷启动

相似度的衡量

推荐算法

基于内容的推荐

基于关联规则的推荐

协同过滤的推荐

基于知识的推荐

基于图的推荐

组合推荐

基于内容的推荐系统

协同过滤的推荐

user-based CF

item_based CF

user-based vs item-based

CF的优缺点

基于隐语义的推荐

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

NMF

KL损失函数

代码实现

CF VS隐语义

基于图的推荐

PageRank Algorithm

陷阱

PersonalRank Algorithm

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

猜你喜欢

热点阅读