协同过滤和K-Mean算法原理记录

发表于 更新于 分类于

协同过滤的基本原理的简单介绍
k-mean算法的简单介绍

根据数据源的不同推荐引擎可以分为三类

1
2
3
1.基于人口的统计学推荐
2.基于内容的推荐
3.基于协同过滤的推荐

基于内容的推荐

1
1.根据物品或内容的元数据，发现物品或内容的相关行，然后基于用户以前的喜好记录推荐给用户相似的物品

基于协同过滤推荐分为三类

基于用户的协同过滤推荐

1
2
3
4
5
基于用户的协同过滤推荐算法，先使用统计寻找与目标用户有相同喜好的邻居，然后根据目标用户的邻居的喜好产生向目标用户的推荐。
基本原理：利用用户访问行为的相似性来互相推荐用户可能感兴趣的资源

例子：
假设用户A喜欢物品A、物品C，用户B喜欢物品B，用户C喜欢物品A，物品C和物品D；从这些用户的历史喜好信息中，发现用户A 和用户C的口味和偏好都是比较类似的，同时用户C还喜欢物品D；那么我们可以推断用户A可能也喜欢物品D，因此可以把物品D推荐给用户A

基于项目的协同过滤推荐

1
根据所有用户对物品或者信息的评价，发现物品和物品之间的相似度，然后根据用户的历史偏好信息将类似的物品推荐给该用户

协同过滤小结总结

1
2
3
4
5
1.基于内容的推荐：只考虑了对象的本身性质，将对象按标签形成集合，如果你消费集合中的一个则想你推荐集合中的其他对象

2.基于协同过滤的推荐算法：充分利用集体智慧，即在大量的人群行为和数据中收集答案，以帮助我们对整个人群得到统计意义上的结论，推荐的个性化程序高，基于以下两个出发点
1.兴趣相近的用户可能会同样的东西感兴趣
2.用户可能较偏爱与其已购买的东西相类似的商品；考虑进了用户的历史习惯，对象客观上不一定相似，但由于人的行为可能认为其主观上是相似的，就可以产生推荐

k-mean算法

1
2
3
4
5
6
7
8
9
10
11
k均值聚类算法是一种迭代求解的聚类分析算法，其步骤是：
1.随机选取K个对象作为初始的聚类中心
2.然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给据离它最近的聚类中心
聚类中心以及分配给它们的对象就代表一个聚类
每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算；这个过程将不断重复直到满足某个终止条件
终止条件可以是以下其中一个：
1.没有（或最小数目）对象被重新分配给不同的聚类
2.没有（或最小数目）聚类中心再发生变化  （一般选用这个为终止条件）
3.误差平方和局部最小

原理：k-means算法是一种基于划分的聚类算法，以距离作为数据对象间相似性度量的标准，即数据对象间的距离越小，则他们的相似性越高，则它们越有可能在同一个类簇

摘取计算试题难度-能力值-回答正确概率的24个能力值

一维聚类函数，points表示实数域的点集，K表示簇的个数，iterNum表示迭代次数
返回值为从小到大排列的中心点，List(中心点值，中心点顺序号)

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
66
67
68
def oneDimKmeans(points:Seq[Double], k:Int, iterNum:Int ) ={
          def doKmeans(points:Array[Vector[Double]],initCenters:Array[Vector[Double]])={
            var centers = initCenters
            for(index <- 0 until iterNum){

              //这里我们根据聚类中心利用groupBy()进行分组，最后得到的cluster是Map(Vector[Double],Array[Vector[Double]])类型
              //cluster共k个元素，Map中key值就是聚类中心，Value就是依赖于这个中心的点集
              val cluster = points.groupBy { closestCenter(centers,_) }

              //通过Map集合的get()方法取出每一个簇，然后采用匹配方法match()进行求取新的中心，这里再强调一遍，Vector类型是不可更改类型，即数据存入Vector以后就不能改变
              //所以需要你人为的定义Vector类型的加减乘除运算
              centers = centers.map { oldCenter =>
        cluster.get(oldCenter) match{
          case Some(pointsInCluster) =>
            vectorDivide(pointsInCluster.reduceLeft(vectorAdd),pointsInCluster.length)
          case None => oldCenter
        }
      }
    }
    centers
  }

  def vectorDis(v1:Vector[Double],v2:Vector[Double]):Double={
    var distance = 0d
    for(i <- v1.indices){
      distance += (v1(i)-v2(i))*(v1(i)-v2(i))
    }
   math.sqrt(distance)
   }

  def vectorAdd(v1:Vector[Double],v2:Vector[Double])={
    val len=v1.length
    val av1=v1.toArray
    val av2=v2.toArray
    val av3=Array.fill(len)(0.0)
    var vector = Vector[Double]()
    for(i<-0 until len){
      av3(i)=av1(i)+av2(i)
      vector ++= Vector(av3(i))
    }
    vector
  }

  def vectorDivide(v1:Vector[Double],num:Int)={
    val av1=v1.toArray
    val len=v1.size
    val av2=Array.fill(len)(0.0)
    var vector = Vector[Double]()
    for(i<-0 until len){
      av2(i)=av1(i)/num
      vector ++= Vector(av2(i))
    }
    vector
  }

  def closestCenter(centers:Array[Vector[Double]],point:Vector[Double]):Vector[Double]={
    centers.reduceLeft((a, b) =>
      if (vectorDis(a,point) < vectorDis(b,point)) a else b
    )

  }

  val pointArray = points.sorted.map(List(_).toVector).toArray
  val initCenters =Array.range(1,k+1).toList.map(_*pointArray.length/(k+1)).map(pointArray(_)).toArray
  val finalCenter =doKmeans(pointArray,initCenters)
  finalCenter.toList.map(x=>x(0)).sorted.zipWithIndex
}
sqlContext.udf.register("oneDimKmeans", oneDimKmeans _)