大数据,机器学习,人工智能机器学习与数据挖掘Machine Learning

Recommended System

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

推荐系统

推荐系统的核心问题就在于为用户推荐与其兴趣相似度比较高的商品。比如在微博上,用户至上想打发时间,并不是想准确的查看某条信息,在首页中查看每一条微博,为了帮助他筛选出一批他们可能感兴趣的信息,此时就需要分析出该用户的兴趣,从海量信息中选择出与用户兴趣相似的信息,并将这些信息推荐给用户。推荐系统就是这样,根据用户的历史和社交情况推荐与其喜好相符的商品或信息。
这时候就需要一个相似度函数f(x),函数f(x)可以计算商品和我用户之间的复杂度,向用户推荐相似度较高的商品。为了能够预测出函数f(x),可以利用到历史诗句主要有:用户的历史行为数据,与该用户相关的其他用户信息,商品之间的相似性,文本描述等等。假设集合C表示所有的用户,集合S表示所有需要推荐的商品。函数f表示商品s到用户c之间的有效用函数,例如:f:CxS->R其中,R是一个全体排序集合。对于每一个用户c \in C,希望从商品的集合上选择出商品,即s \in S,以使得应用函数f的值最大。

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

推荐系统的评估方法

准确度

这个概念应该比较熟悉的了,对于准确度的评估,也要分系统来看,推荐系统有两种,一种是打分系统,一种就是TopN系统。打分系统其实就相当于是一种拟合方法,拟合用户的打分过程,而TopN系统就是给出前N个好的商品而已,所以这两个的准确度的评判标准是不一样的。对于打分系统:设r_{ui}为用户u对物品i的实际打分,r_{ui}'为预测得分,误差判定标准有两个:RMSE=\sqrt{\frac{\sum_{u,i \in T}(r_{ui}-r_{ui}')^2}{|T|}}
MAE=\frac{\sum_{u,i \in T}|r_{ui}-r_{ui}'|}{|T|}对于TopN的推荐系统,R(u)代表推荐的内容,T(u)就是用户选择的内容:Prescion=\frac{\sum_{u \in U}|R(u) \cap T(u)|}{\sum_{u \in U}|R(u)|} Recall = \frac{\sum_{u \in U}|R(u) \cap T(u)|}{\sum_{u \in U}|T(u)|}这两个评价指标是互相牵制的,准确率高制约着召回率。

覆盖率

表示对物体长尾的发掘能力。有时候卖的多的物品会卖的更多,因为很多人看到别人也买就会跟风,但这样就会造成穷的会更穷,富的会更富,所以为了消除这种两极分化,也叫马太效应。可以用一个熵的概念来衡量H=-\sum_{i=1}^n p(i)log p(i)熵其实是个人都知道,平均的时候是最大的,这就有利于消除贫富差距。

多样性

多样性表示的就是推荐物品的种类多样程度,如果推荐的物品基本都是鞋子一类的,那么多样性就很差了,首先用s(i,j)来表示这两个物品的相似度,多样性表示:Diversity(R(u))=1-\frac{\sum_{i,j \in R(u),i !=j}s(i,j)}{\frac{1}{2}|R(u)|(|R(u)|-1)}
Diversity = \frac{1}{|U|}\sum_{u \in U}Diversity(R(u))
以上就是一些主要的推荐评价指标,当然还是很多,比如新颖度,惊喜度,信任度,实时性等等。

冷启动

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

相似度的衡量

欧式距离,是个人都知道,不提了。
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_iD(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

上一篇下一篇

猜你喜欢

热点阅读