它通过观望到的有所用户给货品的打分,用户给商品打分

1. Alternating Least Square

ALS(Alternating Least
Square),交替最小二乘法。在机械学习中,特指使用最小二乘法的一种共同推荐算法。如下图所示,u表示用户,v表示商品,用户给商品打分,可是并非每三个用户都会给各个商品打分。举个例子用户u6就向来不给商品v3打分,必要我们估计出来,那就是机器学习的义务。

图片 1

鉴于并非各种用户给每个商品都打了分,可以固然ALS矩阵是低秩的,即三个m*n的矩阵,是由m*k和k*n多个矩阵相乘获得的,个中k<<m,n。

Am×n=Um×k×Vk×n

这种若是是创造的,因为用户和商品都包罗了部分低维度的藏匿特征,比方大家借使掌握某人喜爱碳酸饮品,就足以测度出他喜欢百世可乐、7-Up、芬达,而不须要分明建议他爱怜那三种果汁。这里的碳酸果汁就约等于叁个东躲江苏特征。上边的公式中,Um×k意味着用户对隐身特征的偏心,Vk×n意味着产品含有遮掩特征的档期的顺序。机器学习的职务正是求出Um×k和Vk×n。可知uiTvj是用户i对货物j的偏幸,使用Frobenius范数来量化重构U和V发生的固有误差。由于矩阵中比非常多地点都是一穷二白的,即用户并未有对货色打分,对于这种情状大家就毫无总计未知元了,只总括观望到的(用户,商品)会集酷路泽。

图片 2

如此就将联合推荐难点转换到了三个优化难题。指标函数中U和V相互耦合,这就供给动用交替二乘算法。即先假诺U的起首值U(0),那样就将题目转化成了二个小小的二乘难题,能够依附U(0)可以测算出V(0),再根据V(0)计算出U(1),那样迭代下去,直到迭代了迟早的次数,或然未有截止。就算不可能保障未有的全局最优解,可是影响很小。

率先片段 算法原理及推导

2. MLlib的ALS实现

MLlib的ALS采纳了数码分区结构,将要U分解成u1,u2,u3,…um,V分解成v1,v2,v3,…vn,相关的u和v存放在同四个分区,进而收缩分区间数据交流的资金。举例通过U总结V时,存款和储蓄u的分区是P1,P2…,存款和储蓄v的分区是Q1,Q2…,必要将区别的u发送给差异的Q,存放那个关系的块称作OutBlock;在P中,总括v时要求什么样u,存放这么些涉及的块称作InBlock。

比如R中有a12,a13,a15,u1存放在P1,v2,v3存放在Q2,v5存放在Q3,则供给将P1中的u1发送给Q2和Q3,这些消息存款和储蓄在OutBlock;CR-V中有a12,a32,因而总结v2需要u1和u3,这一个音信存储在InBlock。

直接上代码:

import org.apache.log4j.{ Level, Logger }
import org.apache.spark.{ SparkConf, SparkContext }
import org.apache.spark.mllib.recommendation.ALS
import org.apache.spark.mllib.recommendation.Rating

/**
  * Created by Administrator on 2017/7/19.
  */
object ALSTest01 {

  def main(args:Array[String]) ={
    // 设置运行环境
    val conf = new SparkConf().setAppName("ALS 01")
      .setMaster("spark://master:7077").setJars(Seq("E:\\Intellij\\Projects\\MachineLearning\\MachineLearning.jar"))
    val sc = new SparkContext(conf)
    Logger.getRootLogger.setLevel(Level.WARN)

    // 读取样本数据并解析
    val dataRDD = sc.textFile("hdfs://master:9000/ml/data/test.data")
    val ratingRDD = dataRDD.map(_.split(',') match {
      case Array(user, item, rate) =>
        Rating(user.toInt, item.toInt, rate.toDouble)
    })

    // 拆分成训练集和测试集
    val dataParts = ratingRDD.randomSplit(Array(0.8, 0.2))
    val trainingRDD = dataParts(0)
    val testRDD = dataParts(1)

    // 建立ALS交替最小二乘算法模型并训练
    val rank = 10
    val numIterations = 10
    val alsModel = ALS.train(trainingRDD, rank, numIterations, 0.01)

    // 预测
    val user_product = trainingRDD.map {
      case Rating(user, product, rate) =>
        (user, product)
    }
    val predictions =
      alsModel.predict(user_product).map {
        case Rating(user, product, rate) =>
          ((user, product), rate)
      }

    val ratesAndPredictions = trainingRDD.map {
      case Rating(user, product, rate) =>
        ((user, product), rate)
    }.join(predictions)

    val MSE = ratesAndPredictions.map {
      case ((user, product), (r1, r2)) =>
        val err = (r1 - r2)
        err * err
    }.mean()

    println("Mean Squared Error = " + MSE)

    println("User" + "\t" + "Products" + "\t" + "Rate" + "\t" + "Prediction")
    ratesAndPredictions.collect.foreach(
      rating => {
        println(rating._1._1 + "\t" + rating._1._2 + "\t" + rating._2._1 + "\t" + rating._2._2)
      }
    )

  }

}

当中ALS.train()函数的4个参数分别是陶冶用的数据集,特征数据,迭代次数,和正则因子。

运行结果:

图片 3

看得出,预测结果要么极其正确的。 

1.1 算法原理介绍

背景介绍:ALS是轮流最小二乘的简称,在机械学习上下文中,ALS特指使用交替最小二乘求解的三个齐声过滤推荐算法。它通过观望到的有着用户给货色的打分,来揆度种种用户的喜好并向用户推荐少量的物料。

主题借使:打分矩阵是近似低秩的,也便是说三个mn阶的打分矩阵 Rmn
能够用五个小矩阵Xkm和 Ykn的乘积来就像,即:

图片 4

56F7E703-B3F7-403E-818C-8CDAE9C8FAC3.png

其中 k << min(m, n)
一旦的合理性:描述一位的喜好普通是在多个抽象的低维空间进行的,并无需一一列出其具体喜好的东西,比方说壹位欣赏悬疑类电影,民谣歌曲…..
为了找到使得矩阵X和Y的乘积尽大概地逼近路虎极光,选拔最小化平方相对误差损失函数:

图片 5

28FDFDB0-98A7-42C3-92DB-1ABA9031A7DA.png

中间,rui 表示第u个用户对第 i 个货色的评分,xu (k1阶)表示用户 u
的偏爱隐含特征向量 1<= u <= m,yi (k
1阶) 表示商品 i
的蕴藏特征向量 1<= i <= n,用户 u 对货品 i 的评分近似为:

图片 6

3ABCE5FD-D3E3-47AE-B95A-85CE483F1F22.png

为了幸免过拟合,插手正则化项:

图片 7

E2A998D4-D1C5-465C-B48A-43E8A3B6D49F.png

时至前些天,协同过滤难题转化为三个优化难点,可是由于xu和yi耦合在一块,并不佳求解,故援引ALS:先固定Y,由上式求解X,然后再固定求得的X,求解Y,如此交替推行直到引用误差满意阈值条件可能到达迭代次数上限。

1.2 推导进程

演绎进度: 先随机生成Y,固定之,对损失函数L(X,
Y)在xu上求偏导,并令其导数=0:

图片 8

75AB4903-CBCA-44E5-A261-D8D595BDD61F.png

同理,由对称性得:

图片 9

4A411DEA-B20E-4F7B-8C47-BFF312455F9B.png

1.3 隐式反馈

如上针对显式反馈,对于隐式反馈的情况,损失函数如下:

图片 10

A208062F-CD5E-4824-8237-2B9E60F5EB8C.png

图片 11

D8126DCA-C623-4CB2-9376-26760993AA57.png

当中rui表示动作的效用,比方购置、加购物车、收藏、点击的次数,恐怕看到/收听摄像/音频的时间长度等等,α是置信度周密,cui代表信任度,遵照这种艺术,我们存在最小限度的信任度,并且随着大家重点到的正偏向的证据越多,信任度也会越加大。
演绎进度看似显式反馈的公式推导,结果如下:

图片 12

74A84B02-8F13-4897-9FC6-FE16213DB085.png

1.4 伪代码

1.4 伪代码
评分矩阵Lacrosse(mn),最大迭代次数K,均方根标称误差阈值a,正则化全面lambda
自由初叶化X(k
m), Y(kn), i = 0
While i < K and delta>=a
#测算每三个用户的隐含特征向量
for u = 1,2…….m do
#计量中间结果矩阵tmp01
tmp01 = Y
Y.T + lambdaE
#对中等结果矩阵tmp01求逆
tmp02 = tmp01.I
*
#计量中间结果矩阵tmp03
tmp03 = tmp02Y
#算算用户 u 的涵盖特征向量, Ru为用户对各样货物的 n 维评分向量
xu = tmp03
Ru
end for
#立异用户隐含特征向量
X(km) = (x1,x2,…..xm)
#总计每一个物料的隐含特征向量
for j = 1,2…….n do
#算算中间结果矩阵tmp01
tmp01 = X
X.T + lambdaE
#对中间结果矩阵tmp01求逆
tmp02 = tmp01.I
*
#算算中间结果矩阵tmp03
tmp03 = tmp02X
#计量物品 j 的盈盈特征向量,福睿斯j为全数用户对该物品的 m 维评分向量
yj = tmp03
Rj
end for
#更新物品隐含特征向量
Y(kn) = (y1,y2,…..yn)
#迭代次数 +1
i = i + 1
#计算此次迭代以后实际评分矩阵与X
Y的切近评分矩阵之间的均方根相对误差
sum = 0
for p =1,2…..m
for q = 1,2,…..n
tmp = Rpq – Xp.TYq
sum = sum + tmp
tmp
delta = sqrt(sum/m*n)
Return X, Y

1.5 预测验评定分

透过1.3的伪代码达成之后收获Xkm和 Ykn

若预测全数用户对具有物品的评分,即:Predict_All = X(km).T \ Y(k*n)

若预测某一用户 i 对负有货物的评分,即:Predict_User = X(ki).T \
Y(k*n)

若预测全体用户对某一货品 j 的评分,即:Predict_User = X(km).T \
Y(k*j)

若预测某一用户 i 对某一物料 j 的评分,即:Predict_User = X(ki).T \
Y(k*j)

第二某个 斯Parker落成

2.1 完结关键点

斯ParkerMLlib达成ALS的关键点:通过客观的分区设计和奥德赛DD缓存来压缩节点间的数据调换

首先,斯Parker会将各类用户的评分数据 u 和各类货品的评分数据 v
根据一定的分区战术分区存款和储蓄,如下图:u1和u2在P1分区,u3在P2分区,v1和v2在Q1分区。

图片 13

7A4336A0-383E-4E2C-BB33-E291DC493161.png

ALS求解进度中,如通过U求V,在每三个分区中 u 和 v
通过客观的分区设计使得在同二个分区中计算进程能够在分区内进行,没有须求从任何节点传输数据,生成这种分区结构分两步:

首先步、在P1上校每三个U发送给必要它的Q,
将这种关涉存款和储蓄在该块中,称作OutBlock

第二步、在Q第11中学需求知道每三个V和怎么样U有涉嫌及其相应的打分,那部分数据不仅仅涵盖原始打分数据,还包蕴从各种用户分区收到的向量排序消息,称作InBlock。

由此,从U求解V,大家须求通过用户的OutBlock新闻把用户向量发送给物品分区,然后经过货色的InBlock音信营造最小二乘难题并求解。同理,从V求解U,大家须要货品的OutBlock音讯和用户的InBlock音信。

对此OutBlock和InBlock只需扫描三次创设好新闻并缓存,在此后的迭代总结进度中得以平昔总括,大大减弱了节点之间的数据传输。

2.3 斯Parker完结与1.4 伪代码分化

1.4
中的伪代码完结属于单机简化实现,在斯Parker的MLlib中落到实处的布满式并行版本所做的首要性调节和进程如下:

1、将数据分为若干个区,各样分区都只含有用户和货色的一部分数据块,通过分区完结相互之间更新用户照旧货品的每种隐含特征向量

2、在种种分区中更新隐含特征向量时索要塑造最小二乘法的两有的新闻,一部分是用户/货物特征矩阵,一部分是用户/货物评分向量;第二片段新闻通过2.1中介绍的贯彻关键点营造用户/货物的InBlock和OutBlock新闻获取。

3、
在每一步迭代进程中,每二个分区都会计算机本事探究所在分区的用户照旧货品货品特征向量,然后去立异对应用户依旧货物的特征向量,进而达成相互之间。

相关文章