打分矩阵是近乎低秩的,n两个矩阵相乘得到的

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

这种要是是客观的,因为用户和商品都带有了一些低维度的隐没特征,比如我们只要知道某个人喜好碳酸饮料,就能够想见出他欣赏百世可乐、百事可乐、芬达,而不需要明确指出他喜欢这两种饮料。这里的碳酸饮料就一定于一个掩蔽特征。下面的公式中,Um×k意味着用户对藏身特征的偏好,Vk×n意味着产品含有隐藏特征的水准。机器学习的职责就是求出Um×k和Vk×n。可知uiTvj是用户i对商品j的偏好,使用Frobenius范数来量化重构U和V暴发的误差。由于矩阵中诸多位置都是空白的,即用户并未对商品打分,对于这种意况我们就不要统计未知元了,只总计观望到的(用户,商品)集合R。

图片 2

这么就将一头推荐问题转换成了一个优化问题。目标函数中U和V相互耦合,这就需要运用交替二乘算法。即先倘使U的起首值U(0),这样就将题目转化成了一个微小二乘问题,可以依据U(0)可以统计出V(0),再根据V(0)计算出U(1),这样迭代下去,直到迭代了迟早的次数,或者消失截至。尽管无法确保没有的大局最优解,可是影响不大。

1. Alternating Least Square

ALS(Alternating Least
Square),交替最小二乘法。在机械学习中,特指使用最小二乘法的一种共同推荐算法。如下图所示,u表示用户,v表示商品,用户给商品打分,可是并不是每一个用户都会给每一种商品打分。比如用户u6就没有给商品v3打分,需要我们想见出来,这就是机械学习的任务。

图片 3

由于并不是每个用户给每种商品都打了分,可以假如ALS矩阵是低秩的,即一个m*n的矩阵,是由m*k和k*n五个矩阵相乘得到的,其中k<<m,n。

Am×n=Um×k×Vk×n

这种假设是理所当然的,因为用户和货物都带有了有的低维度的隐没特征,比如我们假如知道某个人爱不释手碳酸饮料,就足以测算出她喜好百世可乐、百事可乐、芬达,而不需要明确指出他欣赏这两种饮品。这里的碳酸饮料就相当于一个潜伏特征。上边的公式中,Um×k意味着用户对逃匿特征的偏好,Vk×n意味着产品含有隐藏特征的品位。机器学习的职责就是求出Um×k和Vk×n。可知uiTvj是用户i对商品j的偏好,使用Frobenius范数来量化重构U和V爆发的误差。由于矩阵中诸多地点都是空白的,即用户没有对商品打分,对于这种景色我们就毫无统计未知元了,只总计观看到的(用户,商品)集合R。

图片 4

诸如此类就将一同推荐问题转换成了一个优化问题。目的函数中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;R中有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个参数分别是锻练用的数据集,特征数据,迭代次数,和正则因子。

运行结果:

图片 5

足见,预测结果或者特别精确的。 

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;R中有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个参数分别是磨炼用的数据集,特征数据,迭代次数,和正则因子。

运行结果:

图片 6

足见,预测结果或者分外精确的。 

1.1 算法原理介绍

背景介绍:ALS是轮流最小二乘的简称,在机械学习上下文中,ALS特指使用交替最小二乘求解的一个联手过滤推荐算法。它通过阅览到的具有用户给物品的打分,来臆度每个用户的喜好并向用户推荐适量的物料。

主导假若:打分矩阵是近乎低秩的,也就是说一个mn阶的打分矩阵 Rmn
可以用五个小矩阵Xkm和 Ykn的乘积来仿佛,即:

图片 7

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

其中 k << min(m, n)
设若的合理性:描述一个人的喜好普通是在一个虚幻的低维空间拓展的,并不需要一一列出其切实喜好的事物,比如说一个人喜爱悬疑类电影,舞曲歌曲…..
为了找到使得矩阵X和Y的乘积尽可能地逼近R,拔取最小化平方误差损失函数:

图片 8

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

内部,rui 代表第u个用户对第 i 个物品的评分,xu (k1阶)表示用户 u
的偏爱隐含特征向量 1<= u <= m,yi (k
1阶) 表示商品 i
的涵盖特征向量 1<= i <= n,用户 u 对物品 i 的评分近似为:

图片 9

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

为了避免过拟合,出席正则化项:

图片 10

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

从这之后,协同过滤问题转化为一个优化问题,可是由于xu和yi耦合在一齐,并不佳求解,故引用ALS:先固定Y,由上式求解X,然后再固定求得的X,求解Y,如此交替执行直到误差知足阈值条件或者到达迭代次数上限。

1.2 推导过程

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

图片 11

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

同理,由对称性得:

图片 12

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

1.3 隐式反馈

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

图片 13

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

图片 14

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

个中rui表示动作的效能,比如购买、加购物车、收藏、点击的次数,或者看到/收听视频/音频的时长等等,α是置信度周全,cui表示信任度,依照这种措施,我们留存最小限度的信任度,并且随着我们观看到的正偏向的凭证越来越多,信任度也会更为大。
演绎过程看似显式反馈的公式推导,结果如下:

图片 15

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

1.4 伪代码

1.4 伪代码
评分矩阵R(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 的盈盈特征向量,Rj为所有用户对该物品的 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)

其次有些 Spark(Spark)实现

2.1 实现关键点

SparkMLlib实现ALS的关键点:通过合理的分区设计和RDD缓存来压缩节点间的数据沟通

先是,Spark会将每个用户的评分数据 u 和各种物品的评分数据 v
遵照一定的分区策略分区存储,如下图:u1和u2在P1分区,u3在P2分区,v1和v2在Q1分区。

图片 16

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

ALS求解过程中,如通过U求V,在每一个分区中 u 和 v
通过客观的分区设计使得在同一个分区中总括过程可以在分区内开展,无需从任何节点传输数据,生成那种分区结构分两步:

先是步、在P1旅长每一个U发送给需要它的Q,
将这种涉及存储在该块中,称作OutBlock

第二步、在Q1中需要精通每一个V和什么U有关系及其相应的打分,这一部分数目不仅富含原始打分数据,还富含从各类用户分区收到的向量排序音讯,称作InBlock。

据此,从U求解V,我们需要经过用户的OutBlock音讯把用户向量发送给物品分区,然后经过物品的InBlock消息构建最小二乘问题并求解。同理,从V求解U,我们需要物品的OutBlock信息和用户的InBlock信息。

对于OutBlock和InBlock只需扫描两遍建立好新闻并缓存,在事后的迭代总计过程中得以平昔总计,大大缩短了节点之间的数目传输。

2.3 斯帕克(Spark)(Spark)实现与1.4 伪代码区别

1.4
中的伪代码实现属于单机简化实现,在斯帕克(Spark)的MLlib中落实的分布式并行版本所做的重点调整和进程如下:

1、将数据分为若干个区,每个分区都只含有用户和物品的一有的数据块,通过分区实现互动更新用户仍旧物品的每个隐含特征向量

2、在每个分区中立异隐含特征向量时需要构建最小二乘法的两局部讯息,一部分是用户/物品特征矩阵,一部分是用户/物品评分向量;第二有些新闻通过2.1中牵线的兑现关键点构建用户/物品的InBlock和OutBlock信息得到。

3、
在每一步迭代过程中,每一个分区都会精打细算所在分区的用户依然物品物品特征向量,然后去革新对应用户仍然物品的特征向量,从而实现相互之间。

相关文章