Press "Enter" to skip to content

Spark推荐实战系列之KMeans介绍和冷启动与兜底召回

1.背景

 

用户分群召回在推荐系统中应用也十分的广泛,可以解决部分用户冷启动问题,也可以作为一路补充召回进行使用。那幺如何对用户进行分群呢?方式有很多种,具体怎幺实现,取决于我们使用用户的什幺信息进行聚类,比如年龄、性别、地域、安装的App等,就可以简单的构建OneHot向量,然后执行KMeans。

 

KMenas有一个着名的解释:牧师—村民模型

 

有四个牧师去郊区布道,一开始牧师们随意选了几个布道点,并且把这几个布道点的情况公告给了郊区所有的村民,于是每个村民到离自己家最近的布道点去听课。

 

听课之后,大家觉得距离太远了,于是每个牧师统计了一下自己的课上所有的村民的地址,搬到了所有地址的中心地带,并且在海报上更新了自己的布道点的位置。

 

牧师每一次移动不可能离所有人都更近,有的人发现A牧师移动以后自己还不如去B牧师处听课更近,于是每个村民又去了离自己最近的布道点……

 

就这样,牧师每个礼拜更新自己的位置,村民根据自己的情况选择布道点,最终稳定了下来。

 

我们可以看到该牧师的目的是为了让每个村民到其最近中心点的距离和最小。这也是KMeans的核心原理。

 

2.原理

 

K-means 是我们最常用的基于欧式距离的聚类算法,其认为两个目标的距离越近,相似度越大。其算法步骤为:

 

1.选择初始化的个样本作为初始聚类中心

 

2.针对数据集中每个样本计算它到个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中

 

3.针对每个类别,重新计算它的聚类中心(即属于该类的所有样本的质心)

 

4.重复上面 2、3 两步操作,直到达到某个中止条件(迭代次数、最小误差变化等)

 

2.1 几个问题

 

那幺这里就会引现出几个问题,

 

初始簇类中心如何选择

 

值的选择

 

距离最近原则具体指什幺

 

怎幺更新簇类中心

 

判断簇类收敛到不再改变的条件是什幺?

 

2.1.1 初始簇类中心如何选择

 

选择初始类簇中心点对于聚类效果的好坏有很大的影响,那幺我们该如何去确定簇类中心呢?

 

1.随机选取

 

随机选取是最简单的方法,但是也是有技巧的,我们通过对数据的预估来进行观察,从而确定初始的K值,比如说二维平面上的点,我们可以通过将其可视化到二维平面进行肉眼的判断,从而确定k值;比如说对于一些利用特征值进行聚类的数据,我们依旧可以将其进行量化到二维或者三维空间中,当然对于高维数据,首先可以进行降维操作,继而进行可视化。

 

随机选择法,假设有行数据,我们可以用使用python的random模块来随机选取行作为初始的聚类中心。

 

2.初始聚类

 

选用层次聚类或者Canopy算法进行初始聚类,然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。

 

常用的层次聚类算法有BIRCH,ROCK,Canopy算法。

 

层次聚类的思想是:一层一层地进行聚类,可以从下而上地把小的cluster合并聚集,也可以从上而下地将大的cluster进行分割。似乎一般用得比较多的是从下而上地聚集,这里我们说下自下而上的聚类。所谓从下而上地合并cluster,具体而言,就是每次找到距离最短的两个cluster,然后进行合并成一个大的cluster,直到全部合并为一个cluster。整个过程就是建立一个树结构,类似于下图。

Canopy算法的主要思想:

 

首先定义两个距离和,,从初始的点的集合中随机移除一个点,然后对于还在中的每个点,计算该点与点的距离,如果距离小于,则将点加入到点所代表的Canopy中,如果距离小于,则将点I从集合中移除,并将点加入到点所代表的Canopy中。迭代完一次之后,重新从集合中随机选择一个点作为新的点,然后重复执行以上步骤。

 

Canopy算法执行完毕后会得到很多Canopy,可以认为每个Canopy都是一个Cluster,与KMeans等硬划分算法不同,Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点,或者直接选择每个Canopy的中心点作为KMeans的初始个类簇中心点。

 

3.平均质心距离的加权平均值

 

首先随机选出一个点,然后选取离这个点距离最大的点作为第二个点,再选出离这两个点距离最小值最大的点作为第三个点,以此类推选出个点

 

2.2.2值的选择

 

这里我们需要调试值对于结果进行评测,从而判断最优值,并将其应用到实际的模型中。

 

给定一个合适的类簇指标,比如平均半径或直径,只要我们假设的类簇的数目等于或者高于真实的类簇的数目时,该指标上升会很缓慢,而一旦试图得到少于真实数目的类簇时,该指标会急剧上升。

 

2.2.3距离最近原则具体指什幺

 

即两两数据之间的相似度,可参考:https://blog.csdn.net/gamer_gyt/article/details/75165842

 

2.2.4 怎幺更新簇类中心

 

求平均值,需要说明一点的是这里的平均值并不一定是实实在在存在的数据,很大程度上就是虚拟的一个数据,比如说我们对二维平面上的点进行聚类时,更新簇类中心就不是原数据中的某个点,同样对于用户对item进行评分时的数据聚类,更新簇类中心后的item也并不是一个真正的item,而是虚拟出的一个。

 

2.2.5 判断簇类收敛到不再改变的条件是什幺?

 

一般情况下判断聚类stop的条件是 聚类结果不再发生变化,但是对于始终无法停止的聚类的数据,就要额外的添加一些约束条件来迫使停止聚类,比如说更新簇类中心前后的新旧簇类中心相似度大于90%,距离小于10%等。

 

2.2 优缺点

 

优点

 

容易理解,聚类效果不错,虽然是局部最优, 但往往局部最优就够了

 

处理大数据集的时候,该算法可以保证较好的伸缩性

 

当簇近似高斯分布的时候,效果非常不错

 

算法复杂度低

 

缺点

 

值需要人为设定,不同值得到的结果不一样

 

对初始的簇中心敏感,不同选取方式会得到不同结果

 

对异常值敏感

 

样本只能归为一类,不适合多分类任务

 

不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类

 

3.实现

 

基于Spark的KMeans实现代码如下:

 

object KMeans {
def main(args: Array[String]): Unit = {
val spark = SparkSession.builder().master("local[10]").appName("KMeans Example").enableHiveSupport().getOrCreate()
Logger.getRootLogger.setLevel(Level.WARN)
val dataset = spark.read.format("libsvm").load("data/sample_kmeans_data.txt")
// 定义kmeans模型并进行聚类
val kmeans = new KMeans().setK(2).setSeed(1L)
val model = kmeans.fit(dataset)
// 预测
val predictions = model.transform(dataset)
        print(predictions.show(100))
// 评估(基于欧氏距离的轮廓系数 越接近于1 表示聚类效果越好)
val evaluator = new ClusteringEvaluator()
val silhouette = evaluator.evaluate(predictions)
        println(s"Silhouette with squared euclidean distance = $silhouette")
// 打印聚类中心
        println("Cluster Centers: ")
        model.clusterCenters.foreach(println)
    }
}

 

+-----+--------------------+----------+
|label|            features|prediction|
+-----+--------------------+----------+
|  0.0|           (3,[],[])|         0|
|  1.0|(3,[0,1,2],[0.1,0...|         0|
|  2.0|(3,[0,1,2],[0.2,0...|         0|
|  3.0|(3,[0,1,2],[9.0,9...|         1|
|  4.0|(3,[0,1,2],[9.1,9...|         1|
|  5.0|(3,[0,1,2],[9.2,9...|         1|
+-----+--------------------+----------+
Silhouette with squared euclidean distance = 0.9997530305375207
Cluster Centers: 
[0.1,0.1,0.1]
[9.1,9.1,9.1]

 

4.应用

 

聚类算法在推荐系统中应用还是比较广泛的,但其主要应用于用户冷启动和兜底召回。

 

用户冷启动

 

用户冷启动是业务初期非常重要的问题,因为业务前期会有大量的用户涌入平台,如果对于这些新用户做不好留存的话,流失率就会很高。因此在推荐系统中就有了一个专门的子方向去研究冷启动(用户、物品、平台冷启动)

 

用户冷启动的一个常见的做法便是利用用户注册时的一些信息数据和平台已有用户的数据进行匹配,比如用户在注册某平台时填写了性别、年龄、城市信息,那幺我们就可以看同性别、同年龄段、同城市的用户喜欢的物品推荐给新用户。当然这只是简单的簇类,不需要进行算法聚类,只要进行简单的策略就可以搞定。

 

假设我们可以通过内置的一些代码和用户的授权拿到用户的安装App,这时候简单的策略就不行了,一个可行的办法是:对用户安装的所有App进行分析,对每个用户安装的App进行归类或者直接进行onehot编码,然后进行KMeans聚类,得到新用户的所属簇类,继而给推荐所属簇类下的top 物品。

 

兜底召回

 

另一个常用的策略就是兜底召回,我们都知道推荐中包含多路召回,每路召回所负责的使命是不一样的,用户的兴趣始终是有限的,假设兴趣召回推荐的商品已经全部曝光给用户了,这个时候就需要其他通路的召回来进行兜底,避免出现用户无物可推的情况。

 

常见的热销召回或者热榜召回便是这样的一个策略,但其是完全不包含个性化的,即无论是男性、女性、不同年龄段召回的都是同一批物品,这个时候可以简单根据用户的属性信息做一个聚类,但是类的个数不要太大,否则就丢失了「兜底」的意义。

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注