ALS算法介绍（协同过滤算法介绍）

一、ALS算法概括

1、ALS算法用来补全用户评分矩阵。由于用户评分矩阵比较稀疏，将用户评分矩阵进行分解，变成V和U的乘积。通过求得V和U两个小的矩阵来补全用户评分矩阵。
2、ALS算法使用交替最小二乘法来进行求解
3、ALS分为显示反馈和隐式反馈两种。显示反馈是指用户有明确的评分。对于商品推荐来说，大部分是通过用户的行为，获取隐式反馈的评分。隐式反馈评分矩阵需要进行处理，如果有用户评分则置为1，没有则赋值为0。但是对这个处理后的评分矩阵，再有一个置信度来评价这个评分。置信度等于1+a*用户真实评分
4、ALS的代价函数是估计值和现有的评分值误差的平方和，引入了L2正则

二、ALS算法原理及运用

ALS：交替最小二乘（alternating least squares）的简称。在机器学习中，ALS特指使用交替最小二乘求解的一个协同推荐算法。它通过观察到的所有用户给商品的打分，来推断每个用户的喜好并向用户推荐适合的商品。
在ALS算法出现前，协同过滤算法是最适合做类似的工作的，理解ALS算法工作原理前可以先了解一下协同过滤的工作原理。

（1）、协同过滤

1 什么是协同过滤
协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称 CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。

换句话说，就是借鉴和你相关人群的观点来进行推荐，很好理解。

2 协同过滤的实现

要实现协同过滤的推荐算法，要进行以下三个步骤：

收集数据——找到相似用户和物品——进行推荐

收集数据

这里的数据指的都是用户的历史行为数据，比如用户的购买历史，关注，收藏行为，或者发表了某些评论，给某个物品打了多少分等等，这些都可以用来作为数据供推荐算法使用，服务于推荐算法。需要特别指出的在于，不同的数据准确性不同，粒度也不同，在使用时需要考虑到噪音所带来的影响。

找到相似用户和物品

这一步也很简单，其实就是计算用户间以及物品间的相似度。以下是几种计算相似度的方法：

欧几里德距离

皮尔逊相关系数

Cosine 相似度

Tanimoto 系数

进行推荐

在知道了如何计算相似度后，就可以进行推荐了。

在协同过滤中，有两种主流方法：基于用户的协同过滤，和基于物品的协同过滤。具体怎么来阐述他们的原理呢，看个图大家就明白了

基于用户的 CF 的基本思想相当简单，基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到 K 邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。 下图给出了一个例子，对于用户 A，根据用户的历史偏好，这里只计算得到一个邻居 - 用户 C，然后将用户 C 喜欢的物品 D 推荐给用户 A。

基于物品的 CF 的原理和基于用户的 CF 类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他。从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。下图给出了一个例子，对于物品 A，根据所有用户的历史偏好，喜欢物品 A 的用户都喜欢物品 C，得出物品 A 和物品 C 比较相似，而用户 C 喜欢物品 A，那么可以推断出用户 C 可能也喜欢物品 C。

总结

以上两个方法都能很好的给出推荐，并可以达到不错的效果。但是他们之间还是有不同之处的，而且适用性也有区别。下面进行一下对比

计算复杂度

Item CF 和 User CF 是基于协同过滤推荐的两个最基本的算法，User CF 是很早以前就提出来了，Item CF 是从 Amazon 的论文和专利发表之后（2001 年左右）开始流行，大家都觉得 Item CF 从性能和复杂度上比 User CF 更优，其中的一个主要原因就是对于一个在线网站，用户的数量往往大大超过物品的数量，同时物品的数据相对稳定，因此计算物品的相似度不但计算量较小，同时也不必频繁更新。但我们往往忽略了这种情况只适应于提供商品的电子商务网站，对于新闻，博客或者微内容的推荐系统，情况往往是相反的，物品的数量是海量的，同时也是更新频繁的，所以单从复杂度的角度，这两个算法在不同的系统中各有优势，推荐引擎的设计者需要根据自己应用的特点选择更加合适的算法。

适用场景

在非社交网络的网站中，内容内在的联系是很重要的推荐原则，它比基于相似用户的推荐原则更加有效。比如在购书网站上，当你看一本书的时候，推荐引擎会给你推荐相关的书籍，这个推荐的重要性远远超过了网站首页对该用户的综合推荐。可以看到，在这种情况下，Item CF 的推荐成为了引导用户浏览的重要手段。同时 Item CF 便于为推荐做出解释，在一个非社交网络的网站中，给某个用户推荐一本书，同时给出的解释是某某和你有相似兴趣的人也看了这本书，这很难让用户信服，因为用户可能根本不认识那个人；但如果解释说是因为这本书和你以前看的某本书相似，用户可能就觉得合理而采纳了此推荐。

相反的，在现今很流行的社交网络站点中，User CF 是一个更不错的选择，User CF 加上社会网络信息，可以增加用户对推荐解释的信服程度。

如果想看更详细的说明，请参见http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy2/index.html

（2）、ALS算法工作原理

ALS算法是2008年以来，用的比较多的协同过滤算法。它已经集成到Spark的Mllib库中，使用起来比较方便。
从协同过滤的分类来说，ALS算法属于User-Item CF，也叫做混合CF。它同时考虑了User和Item两个方面。
用户和商品的关系，可以抽象为如下的三元组：<User,Item,Rating>。其中，Rating是用户对商品的评分，表征用户对该商品的喜好程度。
假设我们有一批用户数据，其中包含m个User和n个Item，则我们定义Rating矩阵，其中的元素表示第u个User对第i个Item的评分。
在实际使用中，由于n和m的数量都十分巨大，因此R矩阵的规模很容易就会突破1亿项。这时候，传统的矩阵分解方法对于这么大的数据量已经是很难处理了。
另一方面，一个用户也不可能给所有商品评分，因此，R矩阵注定是个稀疏矩阵。矩阵中所缺失的评分，又叫做missing item。

为了更好的实现推荐系统，我们需要对这个稀疏的矩阵建模。一般可以采用矩阵分解（或矩阵补全）的方式。

具体就是找出两个低维度的矩阵，使得它们的乘积是原始的矩阵。因此这也是一种降维技术。假设我们的用户和物品数目分别是U和I，那对应的“用户-物品”矩阵的维度为U×I，如下图所示：

要找到和“用户-物品”矩阵近似的k维（低阶）矩阵，最终要求出如下两个矩阵：一个用于表示用户的U×k维矩阵，以及一个表征物品的k×I维矩阵。这两个矩阵也称作因子矩阵。它们的乘积便是原始评级矩阵的一个近似。值得注意的是，原始评级矩阵通常很稀疏，但因子矩阵却是稠密的（满秩的），如下图所示：

这类模型试图发现对应“用户-物品”矩阵内在行为结构的隐含特征（这里表示为因子矩阵），所以也把它们称为隐特征模型。隐含特征或因子不能直接解释，但它可能表示了某些含义，比如对电影的某个导演、种类、风格或某些演员的偏好。

k隐藏因子的取值有一定的约束：

1.k一般是低阶，小于u和I

2.生产环境中，k的取值范围一般是10~50,不宜过小或是过大，如果k过大，会导致计算代价增大

由于是对“用户-物品”矩阵直接建模，用这些模型进行预测也相对直接：要计算给定用户对某个物品的预计评级，就从用户因子矩阵和物品因子矩阵分别选取相应的行（用户因子向量）与列（物品因子向量），然后计算两者的点积即可。如下图所示：

而对于物品之间相似度的计算，可以用最近邻模型中用到的相似度衡量方法。不同的是，这里可以直接利用物品因子向量，将相似度计算转换为对两物品因子向量之间相似度的计算，如下图所示：

因子分解类模型的好处在于，一旦建立了模型，对推荐的求解便相对容易。所以这类模型的表现通常都很出色。但弊端可能在于因子数量的选择有一定困难，往往要结合具体业务和数据量来决定。一般来说，因子的取值范围在10~200之间。注意：k越大，其计算复杂度越高

（3）、ALS算法输入的参数

参数一: 训练集（rating）

用户对我们这件商品的评分,用户点击了这件商品,我们就给一个评分,然后点击了这个商品的下一步又是多少评分,订单又是多少分,还有访问步长也有加权分,访问时常也有加权分,到最后付款,一共1分.

每一步的评分其实就是一个权重.也可以理解为用户对商品合适程度,喜好程度.用户和商品就组成了一个矩阵,只要用户点击了商品,就对这个商品有个评分了,而有的却没有点击,它是空白的,我们要做的就是填充这些空白,在空白处根据之前的权重预测一个评分.然后推荐.

假如预测分和真是分不匹配,我们就优化参数,线上观察效果,再优化权重分,参数.

训练集是用户，物品，评分.,是一个double类型

参数二: 特征值

给一个特征值,也是double类型的,可以很多参数,可以很少,这个是模型了,看你的模型设计了,如0.1,然后矩阵与特征相乘,所有的特征值与矩阵相乘的分相加,就得到了一个预测分.

假如预测分与实际分不同的话, 那就是特征值给的有问题了,可以修改特征值参数,直到和预测分类似即可.这就是那些算法工程师一直线上看效果,然后调参数了

参数三: 迭代参数（numIterations）

这个参数是让模型趋近于平稳,也是一个double值,也就是它的标准差越来越平稳,迭代之后会产生一个预测分,((预测分-真实分)的平方+预测分) / n 在发个方,这就是标准差,只要标准差越来越平稳,也就是收敛,就这OK了,.迭代参数就好了

参数四: 防过拟合参数

这个参数也是一个和double值,过拟合比如给机器看一个红色的苹果,突然给一张青色的苹果让它识别, 它就不认识这是一个苹果了,就是为了满足尽可能复杂的任务,我们给它的一个参数. 不妨参数的话,他就像一个单调函数,无法涵盖所有的点,而我们的目的就是为了涵盖大多数的点,如下图所示

参考：https://www.jianshu.com/p/740cb3a103df

三、代码实现

object AlsTest {

  val actToNum = udf{
    (str:String)=>{
      str match{
        case "BROWSE"=>1
        case "COLLECT"=>2
        case "BUYCAR"=>4
        case _ =>8
      }
    }
  }

  case class UserAction(act:String,act_time:String,cust_id:String,good_id:String,browse:String)
  def main(args: Array[String]): Unit = {
      val spark = SparkSession.builder().master("local[*]").appName("alstest").getOrCreate()
      val txt = spark.sparkContext.textFile("file:///D:/1016log/*.log").cache()
    //将读入的数据转为dataframe
    import spark.implicits._
    //计算出每个用户对该用户接触过的商品的评分
   var df =  txt.map(line=>{
      val arr = line.split(" ")
      UserAction(arr(0),arr(1),arr(2),arr(3),arr(4))
    }).toDF.select($"cust_id",$"good_id",actToNum($"act").as("score"))
        .groupBy("cust_id","good_id").agg(sum($"score").alias("score"))
     .cache()
    //为了防止用户编号或商品编号中含有给数字情况，所以要对所有的商品和用户编号给一个连续的对应的数字编号后在存到换存
    val wnd1 = Window.orderBy(desc("good_id"))
    val wnd2 = Window.orderBy(desc("cust_id"))

    val mm = new MySqlHandler
    
    val goodstab= mm.readMysql(spark,"goods")
      .select($"good_id",row_number().over(wnd1).alias("gid")).cache()

    val custtab = mm.readMysql(spark,"customs")
        .select($"cust_id",row_number().over(wnd2).alias("uid")).cache()
    //将df和goodstab和custtab join一下只保留元祖(gid uid score)

val df1 = df.join(goodstab, Seq("good_id"), "inner")
      .join(custtab, Seq("cust_id"), "inner")
      .select("gid", "uid", "score")

    //将稀疏表转为Rating对象集合
    val alldata = df1.rdd.map(row=>{
      Rating(row.getAs("uid").toString.toInt,row.getAs("gid").toString.toInt,row.getAs("score").toString.toFloat)
    })
    //将获得的Rating集合拆分为按照0.2.0.8两个集合
    val Array(train,test) = alldata.randomSplit(Array(0.8,0.2))
    //使用8成的数据去训练模型
    val model = new ALS().setRank(10).setIterations(20).setLambda(0.01).setImplicitPrefs(implicitPrefs = false).run(alldata)

//    val model = ALS.train(train, rank = 10, maxIter = 20, implicitPrefs = false)
    //对模型进行测试
    val tj = model.recommendProductsForUsers(30)
    tj.flatMap{
      case(user:Int,ratings:Array[Rating])=>
        ratings.map{
          case (rat:Rating)=>(user,rat.product,rat.rating)
        }
    }.foreach(println)
    spark.stop()
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65